Introduction
The chess bot AlphaMove was proposed in xkcd #3045.
The text of the comic describes the logic as simply:
- sort the list of legal moves alphabetically and pick the middle one
From the image, we know:
And from the alt-text, we also know:
- round down, for an even number of moves
- it's possible to get 6 knights on the board
I wanted to know:
Can an AlphaMove bot actually reach the position shown in the comic?
The answer is: yes!
1. e4 Nc6 2. f3 e5 3. d4 Nxd4 4. c4 Bc5 5. h3 Nc6 6.
Kd2 Nd4 7. Kd3 Qg5 8. h4 Qxg2 9. Kc3 Ne7 10. Kd3 a5
11. Kc3 Qg3 12. Kd2 d5 13. Kc3 Qf2 14. f4 dxe4 15. Ne2
The AlphaMove Algorithm
The snippet below implements the algorithm as described, using the Python chess package, with AlphaMove playing against itself:
import chess
def alpha_move(board):
san_moves = [board.san(move) for move in board.legal_moves]
sorted_moves = sorted(san_moves, key=lambda x: x.lower())
if len(san_moves) % 2 == 1:
middle_move = len(san_moves) // 2
else:
middle_move = len(san_moves) // 2 - 1
return sorted_moves[middle_move]
def play_game():
board = chess.Board()
while not board.is_game_over():
move = alpha_move(board)
board.push_san(move)
return board
play_game()
Initially my code was rounding up, playing 1. f3.
While poking around online, I ran into Explain XKCD and they give moves for the "6 knights game" mentioned in the alt-text. They also started with 1. e4.
I hadn't been certain the "6 knights" was a real thing, or that it was the expected behavior of AlphaMove vs. AlphaMove. But after some more fiddling, I was able to get my code rounding down and was able to reproduce that game too.
It looks like this after 19. gxf8=N Nge4
And here is the full game (by default, the python chess module halts on 5-fold repetition)
1. e4 e6 2. f3 f5 3. e5 g5 4. d4 d5 5. exd6 g4 6. d7+
Kf7 7. dxc8=N Ke8 8. fxg4 h6 9. gxf5 Kd7 10. g4 h5 11.
fxe6+ Ke8 12. g5 Na6 13. h3 Nc5 14. h4 Ne7 15. Kd2 Ne4
+ 16. Ke1 Nf5 17. g6 Nf6 18. g7 Ng3 19. gxf8=N Nge4
20. Ke2 Ng4 21. Kf3 Ngf2 22. Ke2 Nh3 23. Ke3 Nhf2 24.
Nb6 Nh3 25. Na4 Nhf2 26. Nac3 Nxc3 27. Kxf2 Nxd1+ 28.
Kf3 Qc8 29. c4 Ne3 30. Ke4 Nf5 31. Kd3 Ng3 32. e7 Nxh1
33. Kc2 Qb8 34. d5 Kxe7 35. d6+ Kf6 36. dxc7 Nf2 37.
c8=R Ng4 38. Kd2 Nh2 39. Ke3 Ng4+ 40. Kd4 Nh2 41. Kd5
Nxf1 42. Nc3 Nh2 43. Nce2 Ng4 44. Nd4 Nh6 45. Nd7+ Kf7
46. Ndf3 Qd6+ 47. Ke4 Qd2 48. Nf8 Qd5+ 49. Ke3 Qd2+
50. Ke4 Qd5+ 51. Ke3 Qd2+ 52. Ke4 Qd5+ 53. Ke3 Qd2+
54. Ke4 Qd5+ 55. Ke3 Qd2+ 56. Ke4
Given that we (probably) now have the correct implementation of AlphaMove, can we try to figure out what sequence of moves led to the board shown in the comic?
Is Game 3045 Findable?
This is the target board:
Which is represented by this partial FEN string
r1b1k2r/1pp1nppp/8/p1b1p3/2PnpP1P/2K5/PP3q2/RNBQ1BNR
Since this is xkcd, we'll assume this is actually a reachable board state using AlphaMove. That's PROBABLY the case, but we don't know 100% for certain beforehand. It could just be a random board.
The bigger concern is whether this state is FINDABLE. After just 4 "half-moves" (2 moves each), there are already 197,281 possible positions. Then after just 15 half-moves, there are 2,015,099,950,053,364,471,960 positions. Simply because a position exists, that doesn't mean that we can find it in a reasonable amount of time.
As a casual player, it's easy to invent a series of moves that would result in the position above (not "good moves" necessarily.. just legal moves). But we don't want just "legal moves", we need to reach this position after white plays the "alphabetical middle" move each time. That makes the task much harder.
We do have a few things going in our favor:
First, since we know that white is using AlphaMove, we only need to figure out black's moves. White's moves are totally pre-determined by what black does.
Second, just from looking at it, we can see this state should be reachable in roughly 10-20 moves. Most of the pieces are still on the board and many remain on their home squares. The game isn't so far along that a "directed search" is hopeless.
Third, you can sort of "see" how some pieces must have moved. For example, that knight on d4 probably moved Nb8 -> Nc6 -> Nd4. It COULD have moved Nb8 -> Na6 -> Nb4 -> Nc2 -> Nd4, but it probably didn't because that would be weird.
Together these criteria significantly restrict the search space.
Is that enough? (Yes)
The Code
The usual candidates for searching are:
- Depth first
- Iterative deepening, like DFS, but fancy
- Breadth first
- Best first, like BFS, but fancy
After some experimenting, I decided to implement a "best first search", using the hints above as heuristics to restrict the possibilities.
With "best first search", you need to define what "best" means. The algorithm needs to know whether it is getting closer to the goal.
After a bit of experimentation, I landed on two useful metrics:
- number of mismatched squares
- number of total moves
Basically, we ask the algorithm to favor "short solutions that already have lots of squares correct" and that should guide it to quickly finding a solution with "all the squares correct"
This is the code. Kinda long for a blog post.
import heapq
from chess import Board
import chess.pgn
# 1D string representation of the target board state
target_a64 = 'r.b.k..r.pp.nppp........p.b.p.....PnpP.P..K.....PP..Nq..RNBQ.B.R'
# Human-generated list of moves that might be made by black
likely_black_moves = [
'a6', 'a5',
'd6', 'd5', 'dxe4', 'dxe5', 'dxe6',
'e6', 'e5', 'e4',
'Nc6', 'Nd4', 'Nxd4',
'Qe7', 'Qf6', 'Qg5', 'Qh4',
'Qh2', 'Qg2', 'Qf2', 'Qd2', 'Qc2',
'Qh3', 'Qg3', 'Qf3', 'Qd3', 'Qc3',
'Qg3', 'Qxg3', 'Qf2', 'Qxf2', 'Qxg2', 'Qg3', 'Qf3',
'Bc5', 'Bd6', 'Be7',
'Ne7',
]
# Human-generated list of moves that might be made by white
likely_white_moves = [
'c3', 'c4',
'd3', 'd4', 'd5',
'e3', 'e4', 'e5',
'f3', 'f4',
'g3', 'g4', 'g5',
'h3', 'h4',
'Ne2',
'Ke1',
'Kc2', 'Kd2', 'Ke2', 'Kf2', 'Kg2', 'Kh2',
'Kc3', 'Kd3', 'Ke3', 'Kf3', 'Kg3', 'Kh3',
'Kc4', 'Kd4', 'Ke4', 'Kf4', 'Kg4', 'Kh4',
]
def alpha_move(board):
"""
Selects the move that is alphabetically in the middle of the list of legal moves.
"""
san_moves = [board.san(move) for move in board.legal_moves]
sorted_moves = sorted(san_moves, key=lambda x: x.lower())
if len(san_moves) % 2 == 1:
middle_move = len(san_moves) // 2
else:
middle_move = len(san_moves) // 2 - 1
return sorted_moves[middle_move]
class QueueItem:
"""
A node in our search tree.
This holds the current board state and the fitness of that state.
"""
def __init__(self, board):
self.board = board
# 1D string representation of the board state
self.a64 = str(board).replace(' ', '').replace('\n', '')
# The number of squares that are different from the target state
wrong_squares = sum(1 for a, b in zip(self.a64, target_a64) if a != b)
# The number of moves made so far
move_num = len(board.move_stack)
# Fitness is the product of the two values above
self.fitness = wrong_squares * move_num
def __lt__(self, other):
# Compare based on fitness
return self.fitness < other.fitness
def best_first_search(start_board):
# the priority queue
priority_queue = []
# avoid repeating the board state
seen_positions = set()
# push the first item onto the queue
start_move = QueueItem(start_board)
heapq.heappush(priority_queue, start_move)
while priority_queue:
# pop the item with the best fitness
current_stack = heapq.heappop(priority_queue)
current_board = current_stack.board
# check every possible continuation for black
for black_move in current_board.legal_moves:
black_move_san = current_board.san(black_move)
# skip if that move was unlikely to be made
if black_move_san not in likely_black_moves:
continue
# make the move
next_board = current_board.copy()
next_board.push_san(black_move_san)
# the white move is the middle of the alphabetically sorted list
white_move_san = alpha_move(next_board)
# skip if that move was unlikely to be made
if white_move_san not in likely_white_moves:
continue
next_board.push_san(white_move_san)
# we made 2 moves that are likely
next_stack = QueueItem(next_board)
# skip if we have already seen this board state
if next_stack.a64 in seen_positions:
continue
seen_positions.add(next_stack.a64)
# check if we are we done
if next_stack.a64 == target_a64:
return next_stack.board
# we like the progress, but we aren't done yet
# so push this new state into the queue
heapq.heappush(priority_queue, next_stack)
return None
def make_pgn(board):
"""
Helper function to print the moves in PGN format
"""
game = chess.pgn.Game()
game.setup(chess.Board())
node = game
for move in board.move_stack:
node = node.add_variation(move)
return game.variations[0]
board = Board()
board.push_san(alpha_move(board))
found = best_first_search(board)
print(make_pgn(found))
And here is the solution, which it finds after a reasonable ~3200 steps.
1. e4 Nc6 2. f3 e5 3. d4 Nxd4 4. c4 Bc5 5. h3 Nc6 6.
Kd2 Nd4 7. Kd3 Qg5 8. h4 Qxg2 9. Kc3 Ne7 10. Kd3 a5
11. Kc3 Qg3 12. Kd2 d5 13. Kc3 Qf2 14. f4 dxe4 15. Ne2
A few aspects of the search are worth noting:
Pruning the unlikely and impossible moves is crucial. This prevents the algorithm from needing to examine A TON of board states that definitely never happened in the target game. For example, we know there is a pawn on c4. We don't know for certain whether that was due to c2c4 versus c2c3 .. c3c4, but we know for sure that c4c5 was never played. We speed things up a lot by limiting the search to moves that could have actually happened in this particular game. These lists were guesses based on intuition after manually inspecting the board. The move Bb4 was possible, but I thought it was unlikely that the bishop had retreated, so I didn't include it. The move Qh4 seemed likely, so I included it, but it wasn't actually played and the queen stopped at Qg5 instead.
Tracking the list of "seen positions" is necessary. This prevents "loops" where the pieces just shuffle around and repeat the same moves. The existence of repeats could cause the search to run forever, or to try the same few positions over and over again.
The choice of fitness metric matters. I checked what happens if either the "number of incorrect squares" or "path length" metric is used by itself. Both succeed, but much more slowly.
The "path length" metric finds the solution after ~85,500 steps. I believe that using "path length" alone is equivalent to performing breadth-first search.
The "incorrect squares" metric finds the solution after ~103,200 steps. It's not immediately obvious that "number of incorrect squares" is even a good fitness metric, since it gives the same penalty to a piece that is off by 1 square and a piece that is on the wrong side of the board. My guess is that a smarter "edit distance" metric for chess would be expensive to compute, so the trade-off might not be worth it.
What's interesting is that combining the two metrics is so effective (~3200 steps), since neither is amazing by itself.
Conclusion
This was amusing. I made a few mistakes along the way:
My initial code was "rounding-up". I didn't realize that until learning that AlphaMove vs AlphaMove should result in the "6 knights" game, which my code didn't do.
I kept going back and forth between trying to find the position with a tree search and trying to find it by hand with computer assistance. I felt like I was getting somewhere on intuition. But looking at the actual solution, I now suspect that finding it by hand is borderline impossible.
Finally, I was missing a few items from the "likely moves" lists at first. The "likely moves" heuristic is great for pruning the search space, but if the list is missing any of the "actual moves", then the algorithm will fail to find a solution. That's a problem when you don't know for sure whether a solution exists. I made several edits to the "likely moves" lists before getting it right.
That's it. I was initially interested in how AlphaMove plays, which pieces it favors, how oftens it draws against other bots, etc. But then I got intrigued by trying to generate the board from the comic because it seemed feasible. I might follow up on those other questions soon, TBD.