 |
| |
|
|
|
|
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, for each game situation, calculate
Cwhite(player whose move it is,game situation)
and Cblack(player whose move it is,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
|
| |
|
|
Copyright © 1996-2012. RJE-productions. All rights reserved. No part of this website may be published, in any form or by any means, without the prior permission of the authors.
|
