Writing a chess program in one day
The post is about how to write a simple computer chess program within one day with only a few lines of code. The program will be written in Python and contains all main parts of a chess engine. It will be the basis of refinements and enhancements which I will show in future postings.
Every chess program has 3 important parts:
- The representation of the board
- The board evaluation
- The search
As a starting point, I use the Python package “chess” https://python-chess.readthedocs.io, which is a library for move generation, move validation, support for printing the board and more.
Board representation
The main component of the chess library is a “Board”-object which represents the pieces on the chess board, and has methods for move-generation and checking the status of the board (for example checking for mate). The object has a move-stack on which you can push and pop moves, for making a move and taking back a move.
An SVG component can be used to display a graphical representation of the board as above in a “Jupyter”-notebook.
Board evaluation
A position on the chess board can be evaluated if it is won by one side or it is a draw. If none of these conditions is satisfied we need an estimate of how likely it is that a player wins.
In this simple implementation, the estimate is done by two factors the “material” (pieces on board) and the positions of the pieces. For each sort of pieces, different values are calculated depending on the squares the pieces are located. This is done with so-called “piece-square” tables. See below for the implementation.
The function returns -9999 if white is mated, 9999 if black is mated and 0 for a draw. In all other situations, it returns an evaluation as the sum of the material and the sum of position values via piece-square tables. If black is in turn then the negative value is returned as needed by the negamax implementation of the search (see below).
Piece-square tables
I used the piece-square tables from https://www.chessprogramming.org/Simplified_Evaluation_Function
For each sort of piece, a different table is defined. If the value on a square is positive then the program tries to place a piece on that square if the value is negative it avoids to move to that square. The value of the whole position is calculated by summing over all pieces of both sides.
For pawns, the program is encouraged to advance the pawns. Additionally, we try to discourage the engine from leaving central pawns unmoved. Pawns on f2, g2 or c2 and b2 should not move tof3, etc.
Knights are simply encouraged to go to the center. Standing on the edge is a bad idea.
Bishops should avoid corners and borders.
Rooks should occupy the 7th rank and avoid a, h columns
Queens should avoid corners and borders and stay in the center.
Kings should stand behind the pawn shelter. This is only good for the opening and middle game phase. The endgame needs a different table. I will do this in a future enhancement of the program.
Search
For lookahead, I use Depth-First search that starts at the root and explores up to a fixed depth along each branch before backtracking. The value of the position is calculated via Minimax and Alphabeta pruning is used with the Negamax implementation.
At the maximum search depth, the search is extended by searching all capture moves, the so-called quiescence search to avoid the “Horizon Effect”.
The function which implements the move selection in the root position consists of two parts. The first part tries to find a move in the opening book and gives it back. The “chess” library has a function to access opening books in the “Polyglot” format. I used the “bookfish” opening book which I downloaded from http://rebel13.nl/download/books.html. A random weighted move is selected from all possible moves of the book in this position.
The second part calculates the move if the book is empty. For each move in the position, the search (alphabeta) is conducted and the best move is chosen.
To play against the program inside a Jupyter notebook you can evaluate the following cell to compute a computer move (with a search depth of 3), and display the board.
To make a human move you can use:
Match against Stockfish
Stockfish https://stockfishchess.org/ is one of the strongest chess-engines in these days. I use it to test my program with a search depth of 3.
After loading the Stockfish engine with the UCI component of the library I wrote some code to collect all the moves of the game in a list (“movehistory”) and write them to a portable game notation file.
At the end of the game, the final board position is displayed.
[Event “Example”]
[Site “Linz”]
[Date “2018–12–24”]
[Round “1”]
[White “MyChess”]
[Black “Stockfish9”]
[Result “0–1”]
1. d4 d5 2. c4 e6 3. Nc3 Nf6 4. Nf3 Bb4 5. cxd5 exd5 6. Bg5 O-O 7. e3 h6 8. Bh4 Bf5 9. Bd3 Bxd3 10. Qxd3 Nbd7 11. O-O c6 12. a3 Be7 13. Bxf6 Nxf6 14. e4 Nxe4 15. Nxe4 dxe4 16. Qxe4 Bf6 17. Ne5 Re8 18. Rfe1 Qb6 19. b4 Rad8 20. Rad1 a5 21. bxa5 Qxa5 22. Rb1 Qa4 23. Rb4 Qxa3 24. Rxb7 Qa4 25. Qb1 Qxd4 26. Nxf7 Rxe1+ 27. Qxe1 Rd7 28. Qe8+ Kh7 29. Ng5+ Bxg5 30. Qxd7 Qa1+ 31. Qd1 Qxd1# 0–1
In the opening phase, both programs used the opening books. Considering the limited amount of knowledge of my program it played some solid moves. The end of the game showed the negative effects of the limited search depth of my engine.
There are a lot of things that can be done to improve the strength of the program. For example a more sophisticated evaluation function or a better search procedure. I will cover this in future posts.
The next post:
The Jupyter notebooks can be found at https://github.com/astoeckl/mediumchess/
