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 W_white(game situation) and W_black(game situation) which denote whether a player has won in a certain game situation:

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

Now we define C_white(player whose move it is, game situation) and C_black(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:

• C_white(white, game situation) holds if and only if W_black(game situation) does not hold and there exists a white move w in "game situation" for which C_white(black, "game situation after move w") holds.
• C_white(black, game situation) holds if and only if W_white(game situation) holds or for all possible black moves b in "game situation", C_white(white, "game situation after move b") holds.
• C_black(white, game situation) holds if and only if W_black(game situation) holds or for all possible white moves w in "game situation", C_black(black, "game situation after move w") holds.
• C_black(black, game situation) holds if and only if W_white(game situation) does not hold and there exists a black move b in "game situation" for which C_black(white, "game situation after move b") holds.

Now holds:

• The game is computable and white can always win if C_white(black, begin situation).
• The game is computable and black can always win if C_black(black, begin situation).
• The game is not computable if both C_white(black, begin situation) and C_black(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 32⁵=33554432 possible game situations. Therefore, a computer program can calculate C_white(player whose move it is, game situation) and C_black(player whose move it is, game situation) for each game situation within reasonable time. With the help of such a program one finds that C_white(black, game situation) holds, and therefore that white can always win.

Back to the puzzle