Cat and Mice

Four white pieces (the mice) are placed on one side of a chessboard, and one black piece (the cat) is placed at the opposite side. The game is played by the following rules:

 Black wins if it reaches the opposite side.
 White wins if it blocks black in such a way that black can not make any move anymore.
 Only diagonal moves (of length 1) on empty squares are allowed.
 White only moves forward.
 Black can move backward and forward.
 Black may make the first move, then white makes a move, and so on...

Is this game computable (i.e. is it possible to decide beforehand who wins the game, no matter how hard his opponent tries to avoid this)?

 

Answer:

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, for each game situation, calculate C_white(player whose move it is,game situation) and C_black(player whose move it is,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.