Game Theory · Information Theory

The Devil’s Chessboard (Problem)

DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.

The Devil’s Chessboard is an information theory problem in game theoretic setting. As one may or may not have  heard before, the Devil’s Chessboard is a rather intimidating problem, or at least when one first learns about the problem. If one attempts to play the game (with the Devil) without any kind of strategy or by using pure luck, it is rather impossible to win the game as the probability of choosing the correct move is \frac{1}{64} (or about 1.56\%).

Furthermore, the problem can be extended to larger grids, which decreases the chance of choosing the correct move exponentially, if we choose to play the game by using only luck. In fact, some of these game theoretic problems does not even have a winning strategy (Note: Simply put, a winning strategy is a strategy in which the player(s) is(are) guaranteed to win.); in case a winning strategy exists, what is it; if the winning strategy does not exists, what is the best strategy to tackle the problem. In this article, we are going to examine the Devil’s Chessboard, and come up with the best strategy to play the game.

The Game Setting

Imagine this. You and a friend both studies mathematics in your undergraduate studies.  Envying your ability to reason, God decided to send both of you to the Devil. Contrary to the legend, the Devil did not send both of you to burn for eternity immediately. Instead, he would like to play a game with you. If both of you win the game, then you will be released and proceed with life. Otherwise, you will suffer for the rest of the eternity.

The game is as follows: there is an isolated room in which no communication to the outside realm is possible. In the center, there is a table, and on top of the table there is a 8 \times 8 chessboard. You and your friend are to follow the Devil one at a time into the room, where further actions will be taken. For simplicity, we will refer to A and B as first and second person that enters the room respectively.

Once A and the Devil are in the room, the Devil will perform the following steps:

  1. Seal the door (presumably with magic) so that no communication to the outside world is possible.
  2. Make 64 coins identical in colour, weight, etc magically appear on top each square of the chessboard; since it is done by magic, you cannot interfere with this process.
  3. The Devil then points at a square at random, and mark the position of the square on the chessboard as a proof; of course, the mark is invisible to human naked eye until the game is over.
  4. A is allowed to flip one coin on the chessboard, should s/he chooses to.
  5. A will be lead out of the room to avoid any form of collusion with $B$.

During this whole process, A is to remain silent, otherwise both of the players will be sent to Hell for eternity immediately.

Now B will enter the room with the Devil. After the Devil seals the room (again, with magic), B will get a chance to examine the board and then to pick a square on the board. If s/he choose the exact same square the Devil did, then both players are released immediately. Otherwise, both of you go to Hell. Finally, the Devil agrees that he will not cheat by manipulating the marked square; hoping that you succeed and to annoy God, the Devil allows you and your friend to have a discussion to come up with a strategy before the game starts.

Is there a winning strategy in which you and your friend will be guaranteed freedom? If there is, can you find out what the strategy is? If not, what would be the best strategy to maximize the probability of escaping Hell? The solutions will be posted next time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s