Category Archives: Games

King & Rook vs King

Rooks are built for survival to the endgame, which is why the basic endgame of king and rook versus a lone king is one of the first that players learn. On a standard 8×8 chessboard a king and rook can always force a checkmate against a lone king from every one of the 175,168 legal positions where it is the stronger side’s turn to move. The king and rook also win in 90% of the 223,944 legal positions where it is the lone king’s turn to move, but in 22,244 of them the lone king is either already stalemated or can immediately capture the rook. Starting from any winning position the king and rook can force checkmate in at most 16 moves with perfect play by both sides.

What about larger boards? A recently published paper defined a general strategy for n×n boards and formally proved that by following it the king and rook will always force checkmate against any defence by the lone king. The strategy in the paper works for any n greater than 3—there are no legal positions on 1×1 or 2×2 boards and the winning strategy on a 3×3 board is easy to discover. At this point we need to specify that the 50 move rule is not in force, or else the proportion of legal positions that are winning for the king and rook will become vanishingly small as the board size increases.

What about infinite boards? For a board stretching to infinity in all directions there is no hope of checkmate: from any square a lone king can move to 8 adjacent squares, and a king and rook together cannot control more than 6 of them. For the same reason a king and rook cannot checkmate a lone king on a finite board in the shape of a torus. But what about an infinite quadrant, where there is a square for every pair (x,y) of natural numbers and (1,1) is the single corner square?

An infinite quadrant chessboard

A natural plan for the lone king is to run away from the corner as fast as possible, and if the rook tries to box it in then the king can move to the square diagonally adjacent to the rook and threaten to capture it, forcing it further away. The only way to stop the lone king from chasing the rook further and further away from the corner is for it to be defended by its king, and surprisingly there is a neat strategy to achieve this from any starting position. The strategy is to use the rook to box in the lone king to make it traverse two sides of a large square drawn on the board, while the other king moves along the diagonal which takes half as many moves to get to the same end point. Here are the gory details:

  1. Suppose the lone king starts on the square (x,y) and the other king starts on the square (p,q).
  2. The rook first makes two moves to get to the square (x + 2, n) boxing in the lone king (where n is a large number we will define later).
  3. The lone king makes ny moves to get to the square (x + 1, n – 1).
  4. Meanwhile, the other king makes max((n + 1) – p, (n + 1) – q) moves to get to the square (n + 1, n + 1).
  5. When the lone king arrives at the square (x + 1, n – 1) to attack the rook at (x + 2, n), the rook makes one move to the square (n,n).
  6. The long king makes n – (x + 2) moves to get to the square (n – 1, n – 1).

In total the king and rook together make n + 4 – min(p, q) moves, and the lone king makes 2n – (x + y + 2) moves. Thus by choosing any n ≥ 6 + x + y – min(p,q) the king and rook can arrange that when the lone king arrives at the square (n – 1, n – 1) to attack the rook at (n,n), the rook is defended by its king at (n + 1, n + 1).

Instead of immediately running toward the rook the lone king can complicate matters by trying to pin the other king to an edge and stop it moving to its rendezvous square, but the rook can always help its king to escape and once free the strategy above can be restarted. And once the lone king is boxed in by a rook defended by a king, it can be driven to the corner and checkmated with a technique similar to the one used on a standard 8×8 chessboard.

We have shown that a king and rook can force a checkmate against a lone king from any initial position on an infinite quadrant, but what about a half-infinite board that has one edge and no corners? From what starting positions can a king and rook force a checkmate against a lone king?

A half-infinite chessboard

Advertisements

Fox & Hounds

Fox & Hounds is a simple two-player game played on the light squares of a chessboard. Here is the initial position with the position of the fox marked by F, the position of the hounds marked by H, and the empty light squares marked by * symbols:

Fox to move
+--------+
|* * F * |
| * * * *|
|* * * * |
| * * * *|
|* * * * |
| * * * *|
|* * * * |
| H H H H|
+--------+

The fox moves first, and can move to any empty diagonally adjacent square. When it is the hounds’ turn to move one hound is chosen to move to an empty diagonally adjacent square, but hounds can only move up the board. The hounds win by blocking the fox so it can’t move:

Fox to move
+--------+
|* F H * |
| H H * *|
|* * H * |
| * * * *|
|* * * * |
| * * * *|
|* * * * |
| * * * *|
+--------+

The fox wins by escaping from the hounds, which is simplest to define as positions in which it is the hounds’ turn to move but no hound can move:

Hounds to move
+--------+
|H * H H |
| * * * *|
|* * * * |
| * * * *|
|* * * F |
| * * * H|
|* * * * |
| * * * *|
+--------+

However, in practice as soon as the fox gets around the hounds it is easy (and boring) for the fox to make waiting moves until the hounds run out of moves, so we expand our definition of winning positions for the fox to include positions where the fox has escaped into an area of two or more squares that no hound can ever reach:

Hounds to move
+--------+
|* * * * |
| * * * *|
|* * * * |
| H * H *|
|* * * * |
| F H H *|
|* * * * |
| * * * *|
+--------+

The area needs to have at least two squares so the fox can make waiting moves while the hounds exhaust all their moves. Now, before polluting your intuition by reading the following analysis, I recommend getting a feeling for the game on your own terms by playing a few rounds as the fox and as the hounds.

Solving the Game

If you’re like me there are only so many times you can play this game without needing to know who wins with perfect play, and fortunately it is feasible to compute this with the following algorithm:

  1. Compute the set of reachable positions from the initial position.
  2. Annotate each reachable position where the fox has won as Fox win in 0 and each reachable position where the hounds have won as Hounds win in 0.
  3. Order the possible position evaluations like so:
    Hounds win in 0 < Hounds win in 1 < Hounds win in 2 < ··· < Fox win in 2 < Fox win in 1 < Fox win in 0
  4. For every reachable position where all the next positions have been annotated with an evaluation, if it is the fox’ turn to move then pick the maximum evaluation, and if it is the hounds’ turn to move then pick the minimum evaluation. In both cases increment the N in the win in N part of the evaluation and annotate the position with this adjusted evaluation.

This is an example of dynamic programming, and its computational complexity depends on the number of reachable positions, not the number of possible games. This is usually a huge speed-up: for example, in the classic game of noughts and crosses there are 5,478 reachable positions but 255,168 possible games.

This algorithm is coded in the solve Haskell package, and here is the result of running it on a range of possible board sizes:

Board size Reachable positions Possible games Initial position evaluation Time Memory
2×2 1 1 Hounds win in 0 1s 200Mb
4×4 83 178 Hounds win in 8 1s 200Mb
6×6 8,175 ~1011 Fox win in 21 2s 200Mb
8×8 709,868 ~1029 Hounds win in 44 3m 650Mb
10×10 69,575,678 ~1055 Hounds win in 72 8h 41Gb

The performance results were gathered using GHC version 8.0.1 on an Intel(R) Xeon(R) Gold 6136 CPU @ 3.00GHz. The exact number of possible games for Fox & Hounds played on a standard 8×8 board is 360,552,037,329,667,882,019,232,833,884. If you’re wondering why the hounds win in zero moves on a 2×2 board, it is because the poor fox is already trapped in the initial position:

Fox to move
+--+
|F |
| H|
+--+

Designing an AI Player

Once the game was solved, my plan was to use the solution to create a strong Fox & Hounds AI player on a standard 8×8 board. And indeed, when faced with a winning position, the game solution does make it easy for an AI player to win the game. But what should an AI player do when faced with a losing position? For example, when playing as the fox from the initial position?

When faced with a hard problem, my mathematician instincts tell me to solve an easier problem instead. So let’s begin with the problem of how to play as the hounds in a losing position. To make the discussion more concrete, consider the first reachable position that is losing for the hounds, which we call the opposite position:

Fox to move
+--------+
|* * * * |
| * F * *|
|* * * * |
| * * * *|
|* * * * |
| * * * *|
|* * * H |
| H H * H|
+--------+
Evaluation: Fox win in 29

Hounds opening tip: don’t play this as your first move! Observe that this is a win in 29 moves for the fox, so with best play the hounds can delay defeat for a long time. Since the game stops as soon as the fox escapes, the N in the evaluation Fox win in N is a useful positional measure, and we use this to design a strategy for the hounds in a losing position: the AI player simply plays to delay defeat as long as possible. This same strategy is also used in solved chess endgames to create AI players that are hard to defeat when defending lost endgames such as Queen vs Rook. Try it for yourself on the opposite position, or this tricky position that is also losing for the hounds.

What Does the Fox Play?

So much for the easier problem. Unfortunately, the same strategy does not result in a strong fox AI player when playing in a losing position, but the reason why is instructive. Most games that the hounds win take about the same number of moves, because all the hounds have to move all the way up the board to trap the fox. Thus a fox playing to delay defeat will stay away from the hounds to avoid any early traps, and wait for the hounds to simply march up the board in a line for an easy win.

This last part contains the kernel of an idea for a fox strategy. First, call a position a FoxBox if the fox is contained by the hounds, such as the initial position or any of the following:

+--------+    +--------+    +--------+
|* * * * |    |* * H * |    |H * H F |
| * F * *|    | F * * *|    | * * H *|
|* * * * |    |* * H * |    |* * * H |
| * * * *|    | H H * *|    | * * * *|
|* * H H |    |* * * * |    |* * * * |
| H H * *|    | * * * *|    | * * * *|
|* * * * |    |* * * * |    |* * * * |
| * * * *|    | * * * *|    | * * * *|
+--------+    +--------+    +--------+

A simple strategy for the hounds is to play moves that maintain FoxBox positions whenever possible, and if the fox forces a non-FoxBox position then return to a FoxBox position at the earliest opportunity. Thus, when the fox is faced with a losing position, to make winning the game as complicated as possible for the hounds, the fox should avoid FoxBox positions.

The dynamic programming technique can be repeated to calculate the number of moves B required for the hounds to force a FoxBox position. Since every won position for the hounds is a FoxBox position, the B value will be finite in every position that is losing for the fox. Unfortunately, when used as a positional measure, the B value offers no guidance for the fox in FoxBox positions (such as the initial position).

A better positional measure is the maximum B value that the fox can force over the course of the whole game starting from the current position, and this can be calculated by dynamic programming yet again. When playing as the fox in a losing position, the strategy of the AI player is to maximize this quantity, which will hopefully lead to a position far from a FoxBox in which the hounds will make a mistake. For example, the B value in the initial position is 0, because it is already a FoxBox position, but the maximum value that the fox can force over the course of the game is 6, and this provides the motivation for the fox to start harassing the hounds as soon as possible.

The Fairest Fuzz Factor

At this point we have defined the strategy of the AI player when playing in a losing position as the fox or the hounds. To make the game interesting, when playing in a winning position the AI player also plays to maximize the same quantity as the losing side, but restricted to moves that preserve the win. Thus, when playing as the fox in a winning position, the AI plays toward the longest possible victory, and when playing as the hounds in a winning position, the AI plays toward the maximum finite B value.

The AI player also includes a fuzz factor to make the game more interesting: with probability p it does not follow its defined strategy but instead picks a move at random from the available moves. With the addition of a fuzz factor p > 0 a fox can now win from the initial position against an AI player, and using dynamic programming (of course) it is possible to calculate the probability of this happening as a function of p if it plays according to an optimal strategy. Using binary search on p the fairest fuzz factor for the AI player is determined to be p = 0.006935, which gives the fox exactly 50% chance of winning:

Fuzz factor (p) Fox wins from initial position Hounds win from opposite position
0.000000 0.000 0.000
0.003906 0.326 0.150
0.005859 0.444 0.215
0.006836 0.495 0.245
0.006897 0.498 0.247
0.006927 0.499 0.248
0.006935 0.500 0.248
0.006943 0.500 0.249
0.006958 0.501 0.249
0.007080 0.507 0.253
0.007324 0.518 0.260
0.007812 0.541 0.275
0.015625 0.780 0.466
0.031250 0.943 0.696
0.062500 0.995 0.890
0.125000 1.000 0.979
0.250000 1.000 0.997
0.500000 1.000 0.998
1.000000 1.000 0.999

Just for fun, the table also includes the probability that the hounds win from the opposite position against a fox AI player with the given fuzz factor.

Conclusion

After solving the game, I was able to answer any question I had about the game with modest programming effort. The hardest part of constructing a strong fox AI player for losing positions was coming up with good questions to ask starting with the concept of the FoxBox. And perhaps there are better questions to ask that would result in stronger Fox & Hounds AI players. There is a lesson here for our Big Data future: even when all the data on a problem domain is available, creative work is still needed to solve real-world problems.