Solution to: Cat & Mouse

There are three possible outcomes:

• yes, the game is computable and white can always win;
• yes, the game is computable and black can always win;
• no, the game is not computable.

We define Wwhite(game situation) and Wblack(game situation) which denote whether a player has won in a certain game situation:

• Wwhite(game situation) holds if and only if white has won in "game situation" (i.e., black cannot make any move anymore).
• Wblack(game situation) holds if and only if black has won in "game situation" (i.e., black has reached the opposite side).

Now we define Cwhite(player whose move it is, game situation) and Cblack(player whose move it is, game situation) which denote whether a player can always win in a game situation in which the move is with a certain player:

• Cwhite(white, game situation) holds if and only if Wblack(game situation) does not hold and there exists a white move w in "game situation" for which Cwhite(black, "game situation after move w") holds.
• Cwhite(black, game situation) holds if and only if Wwhite(game situation) holds or for all possible black moves b in "game situation", Cwhite(white, "game situation after move b") holds.
• Cblack(white, game situation) holds if and only if Wblack(game situation) holds or for all possible white moves w in "game situation", Cblack(black, "game situation after move w") holds.
• Cblack(black, game situation) holds if and only if Wwhite(game situation) does not hold and there exists a black move b in "game situation" for which Cblack(white, "game situation after move b") holds.

Now holds:

• The game is computable and white can always win if Cwhite(black, begin situation).
• The game is computable and black can always win if Cblack(black, begin situation).
• The game is not computable if both Cwhite(black, begin situation) and Cblack(black, begin situation) do not hold.

Because there are only five pieces, which can each be on at most 32 fields, there are at most 325=33554432 possible game situations. Therefore, a computer program can calculate Cwhite(player whose move it is, game situation) and Cblack(player whose move it is, game situation) for each game situation within reasonable time. With the help of such a program one finds that Cwhite(black, game situation) holds, and therefore that white can always win.

Back to the puzzle
This website uses cookies. By further use of this website, or by clicking on 'Continue', you give permission for the use of cookies. If you want more information, look at our cookie policy.