Exploring the computational complexity of chess. Code snippets in Python so you can do the same.

I have been learning chess (again) and how to program a chess engine (for the first time) over the last month. After skimming some introductory texts, I was convinced that building a simple chess engine one that would put up a fair fight against a casual player would take no more than a few days.
I was wrong.
But I made it there in the end and created a toy chess engine (healeycodes/andoma) that I am proud of. It can play a game of chess and solve simple chess puzzles like mate-in-two or mate-in-three. It has a slim UCI interface which means it can be hooked up to lichess.org via lichess-bot a bridge between the lichess API and chess bots.
The first speed bump in its development was grasping the computational the complexity of chess how fast, and wide, the search tree grows. When a chess game starts, white can open in twenty different ways and black can respond in twenty different ways also. After the first full turn, there are 400 variations possible. After the third full turn, there are over 119 million.
Claude Shannon calculated that there are around 10^120 possible games of chess in his seminal paper Programming a Computer for Playing Chess in 1950. In Rage Against the Machines, Nate Silver quotes Diego Rasskin-Gutman, who said:
There are more possible chess games than the number of atoms in the universe.
Given unlimited resources, it actually doesnt take many lines of code to calculate every legal variation of chess. Here, the Python package python-chess is used for board representation and legal move generation.
from chess import Board, Move, STARTING_FEN
# an adjacency list
positions ={}# depth-first search from a FEN stringdefgenerate_tree(fen):
board = Board(fen)
legal_moves =list(board.legal_moves)if fen in positions:
positions[fen]+= legal_moves
else:
positions[fen]= legal_moves
for move in legal_moves:
board.push(move)
next_fen = board.fen()
board.pop()
generate_tree(next_fen)try:
generate_tree(STARTING_FEN)except RecursionError:print(len(positions)+sum(len(p)for p in positions))
This program throws a RecursionError and prints 59691 the number of different positions the search tree contained when it crashed. All we need to fix this, is another universe to run the program in.
Given that there are computational limits to abide by, as well as the time control rules of chess, improvements over a naive brute force search must be made.
Evaluation
In order to search for good positions, it is necessary to understand what makes a good position good. The most simplistic way of describing a positions strength is to compare the total value material of each side.
Tomasz Michniewski, author of the Simplified Evaluation Function, defined some values that are designed specifically to compensate for the lack of any other chess knowledge. This is perfect for me a beginner chess player.
This snippet sums the material on the initial board using Michniewskis piece values.
import chess
piece_values ={
chess.PAWN:100,
chess.ROOK:500,
chess.KNIGHT:320,
chess.BISHOP:330,
chess.QUEEN:900,
chess.KING:20000}
board = chess.Board(chess.STARTING_FEN)
white_material =0
black_material =0for square in chess.SQUARES:
piece = board.piece_at(square)ifnot piece:continueif piece.color == chess.WHITE:
white_material += piece_values[piece.piece_type]else:
black_material += piece_values[piece.piece_type]
Michniewski also provides piece-square tables, which alter the value of a piece depending on which square it sits on. For example, its better for pawns to progress up the board and its better for knights to be near the center of the board.
The bonus of a square may be positive, neutral, or negative. The piece-square tables are presented from Whites POV and must be mirrored for Black.
# a knight’s bonuses depending on square
-50,-40,-30,-30,-30,-30,-40,-50,
-40,-20, 0, 0, 0, 0,-20,-40,
-30, 0, 10, 15, 15, 10, 0,-30,
-30, 5, 15, 20, 20, 15, 5,-30,
-30, 0, 15, 20, 20, 15, 0,-30,
-30, 5, 10, 15, 15, 10, 5,-30,
-40,-20, 0, 5, 5, 0,-20,-40,
-50,-40,-30,-30,-30,-30,-40,-50,
For the king, Michniewski provides two tables one for the middle game and one for the end game. He defines the end game as being either if:
Both sides have no queens or
Every side which has a queen has additionally no other pieces or one minorpiece maximum.
The evaluation of a chess board is one of the things thats kept me interested in chess engines. Evaluation rules are easy to add and take away. I refactored the code from Go to Python to be able to prototype different rules faster.
After piece-square tables, one might look at pawn structure, mobility, center control, connectivity, trapped pieces, king safety, space, tempo, and other patterns (this list is taken from the Chess Programming Wikis Evaluation page).
Searching With Minimax
Minimax is a search algorithm that finds the next optimal move by minimizing the potential loss in a worst case scenario. Chess is a game of perfect information by looking at the board its possible to know exactly what an opponent is capable of. However, this search for moves is limited by the evaluation function and the depth that computing resources are able to reach.
The search space is a tree of legal moves which grows exponentially at every level (the average branching factor is around 35). By the time the tree is explored, the path to many future boards is known as well as which path restricts the opponents possible gains the most.
The leaf nodes of the tree return the evaluation of their current state. Non-leaf nodes inherit their value from a descendant node. Eventually, the recursive function reduces down to a value for the given board.
This function can be used to pick the next best move by calling it on every legal move available in the current turn. A great visual resource for this algorithm is Sebastian Lagues Algorithms Explained minimax and alpha-beta pruning.
defminimax(board, depth, maximizing_player):if depth ==0or board.is_game_over():return evaluate(board)if maximizing_player:
value =-float(‘inf’)for move in board.legal_moves:
board.push(move)
value =max(value, minimax(board, depth -1,False))
board.pop()return value
else:
value =float(‘inf’)for move in board.legal_moves:
board.push(move)
value =min(value, minimax(board, depth -1,True))
board.pop()return value
Alpha-beta pruning
My chess engine uses alpha-beta pruning as an improvement over the naive minimax algorithm which does not fare well against the exponential nature of chess. Branches of the search tree can be eliminated when it is clear that another branch shows more promise. This significantly reduces the number of moves required to be generated.
By reducing the depth of branches that will not bear fruit we can search deeper down the better parts of the tree.
The speed of alpha-beta pruning can be increased by applying move ordering. This is where the more promising branches of the search tree are searched first which means less time is spent in the worst branches as they will be cut off early.
Move ordering cannot be 100% accurate but its a powerful optimization.
In my engine, a cheap (but not perfect) move_value function is used to sort the initial legal move nodes from best to worst. The logic of this function is capture in its docstring:
”’
How good is a move?
A promotion is great.
A weaker piece taking a stronger piece is good.
A stronger piece taking a weaker piece is bad.
Also consider the position change via piece-square table.
”’
Communication and the UCI Protocol
The Universal Chess Interface (UCI) is a open protocol to hook up chess engines to user interfaces. The communication is done through standard input and standard output and messages end with \n. The move format is long algebraic notation like e2e4, or e1g1 for white short castling, and an example of a promotion to queen is a7a8q.
There are many configuration commands in the specification and it initially seemed overwhelming. After debugging, I found that not many were required to get a chess engine to the Hello World stage.
In order to hook my chess engine up to lichess via lichess-bot, I implemented the following. These commands are send to the engine from lichess-bot:

• uci – the engine reports its name, authors, and uciok
• isready – the engine reports that its ready: readyok
• position startpos moves e2e4 – the engine sets its internal state to match the list of moves
• go – the engine should now calculate and respond with the next best move, like g8f6

A Promise
I have found a great joy interacting with the chess community over the last month. Lichess is a fantastic resource and endlessly fun to play on. The UI is slick and light and the post-match analysis is revealing and simple to use. Its open source and relies on donations and sponsorships.
I took breaks from writing this article to play chess against Dad on a real board. Were missing a white rook and use a pencil sharpener as a replacement piece. He has been telling me stories about playing chess decades ago before IBMs Deep Blue emerged and beat Garry Kasparov, the reigning world champion, on its second attempt in 1997.
If you are within my social circle, you will have experienced me evangelizing chess and chess engines over the last month now that I have published this, I promise to chill out a little bit
Other Resources
To build healeycodes/andoma, I used the following resources (and recommend all of them).
Thanks to Jez9999 for the Alpha-Beta pruning example image.