Making a simple chess engine
Using python/python-chess to develop a simple chess engineIntroduction
In my last Lichess blog, Toadofsky suggested me, in case I was interested in engine development, some code as a way of testing an engine's accuracy against a set of puzzles. I thank him for the link and told him that, although I had looked into engine development, I hadn't do it so far because I don't think I can add anything new. And I don't think I can.
On another comment Toscani, shared a video by Bartek Spitza, which in 6 minutes and 44 seconds explains very well the steps of minimax engine development.
Inspired by this video I decided to write this new blog. My aim is to share the little I know about chess engine development in a practical way.
It is typical to explain programming concepts using the so called pseudo-code. Here I will use python. I think python is (or at least can be) a very readable language. The advantage is that the code can actually run. Is python a good language to build chess engines? I don't think so, it is too slow.
There are 2 main types of engines that I know of. There is the minmax/nagmax type and machine learning type like AlphaZero or Leela Chess Zero
A number of Lichess users have been written about their engines. Here is a short list:
- Liquid Search Engine human gameplay analysis
- Tofiks 1.3.0. is looking good!
- GuineaBot3 - A new learning bot!
Having some experience with neural networks, although mainly in a different context, I dare say that developing a simple neural network chess engine is way more difficult that a simple minimax type engine. Consequently this blog will focus exclusively on the minimax type of engine.
I also want to mention a couple of other Lichess blogs that I have found:
I repeat here my last blog warning:
Before continuing a word of caution, although as a statistical researcher I program in python every day I am not a developer. This means that while typically, but not always, I manage to get things done my programming is not elegant, sophisticated or efficient.
The imports for this project are:
import pandas as pd
import numpy as np
import scipy.stats as sps
import matplotlib.pyplot as plt
import chess
import chess.engine
Part 1: a very simple engine
For our minimax chess engine to work we need to implement:
- a board score,
- the minimax algorithm.
The board score
The board score returns the value of the position on the board. In my implementation if the board score is positive White is winning and if negative Black is winning. Consequently White will want to make moves that maximize the value of the board while Black will want to make moves that minimize the value of the board. Hence the use the minimax algorithm to choose the best move.
One of the simplest implementations of a board score is to attribute values to pieces and then determine the value of the board by subtracting the total value of the Black pieces from the total value of the White pieces. The following implementation is based on the code I found here.
def its_draw(board):
draw = False
if (board.is_stalemate() or # draw
board.is_fivefold_repetition() or
board.is_insufficient_material() or
board.is_seventyfive_moves() or
board.can_claim_draw() #inclues 3 fold repetition and 50 move rule
):
draw = True
return draw
def simple_board_score(board):
if board.is_checkmate():
if board.turn:
score = -np.inf #white was checkmated
else:
score = np.inf #black was checkmated
elif its_draw(board):
score = 0.0
else:
score = 0.0
for (piece, value) in [(chess.PAWN, 100),
(chess.BISHOP, 300),
(chess.KING, 1000),
(chess.QUEEN, 900),
(chess.KNIGHT, 300),
(chess.ROOK, 500)]:
score = (score +
len(board.pieces(piece, chess.WHITE))*
value)
score = (score -
len(board.pieces(piece, chess.BLACK))*
value)
#end for
#end if
return score
More information on chess piece value here.
Note that the 3 fold repetition and the 50 move rule are not automatic draws. They just allow one or both of the players to claim a draw, but in practical terms it is a draw.
The minimax algorithm
The minimax algorithm can be recursive or iterative. A recursive function is a function that calls itself. The typical example for programming beginners is a recursive function to calculate a factorial.
The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For instance the factorial of 3 is 3! = 3*2*1 = 6.
Iterative and recursive implementations of a factorial are:
def iterative_factorial(n):
fact = 1
for i in range(1,n+1):
fact=fact*i
return fact
def recursive_factorial(n):
if n==0:
return 1
fact = n*recursive_factorial(n-1)
return fact
The recursive version is much faster than the iterative one. You can test that by, for example, doing:
%timeit iterative_factorial(12)
%timeit recursive_factorial(12)
I prefer the recursive minimax because (1) the iterative version would be a lot more complicated to implement, (2) the recursive version is more legible.
The minimax algorithm can be recursively implemented as follows:
def minimax(board, depth):
if (depth==0) or (board.is_game_over()) or (its_draw(board)):
return board_score(board)
if board.turn: # White's turn
opt_value = -np.inf
for move in board.legal_moves:
board.push(move)
## White maximizes the board score
opt_value = np.max([opt_value,minimax(board, depth - 1)])
board.pop()
return opt_value
else: # Black's turn
opt_value = np.inf
for move in board.legal_moves:
board.push(move)
## Black minimizes the board score
opt_value = np.min([opt_value,minimax(board, depth - 1)])
board.pop()
return opt_value
#end if
Move calculation example
The next figure shows a board that was setup as follows:
fen = '8/6R1/5k2/8/3p4/3K4/8/8 w - - 0 1'
board = chess.Board(fen)
display(board)
Can this algorithm find the best moves? It's White's turn. Clearly the best moves are Rd7 or Rg4 so that the d4 pawn can be capture on the next White's turn. If Kxd4 then Kxg7 and it will be a draw. If the rook moves to any other squares than rather than d7 or g4 the king will be able to come and protect the pawn so it will take more turns for White to be able to capture the pawn on d4.
To be able to actually run the minimax algorithm I wrote the following function:
def get_legal_moves_scores(board,depth=3):
score = []
moves = []
for move in board.legal_moves:
board.push(move)
score.append(minimax(board, depth))
moves.append(move)
board.pop()
## end for
legal_moves_scores = pd.DataFrame(
{'Score':score,'Move':moves}
).sort_values('Score')
return legal_moves_scores
The function iterates though the current board legal moves and calculates their scores and puts them in a pandas dataframe and sorts them ascending, so the best move for White will be in
legal_moves_scores['Move'].values[-1]
The scores for the available moves in this example board calculated at a depth of 3 are:
| Score | Move |
|---|---|
| -100 | d3c2 |
| -100 | d3e2 |
| -100 | d3d2 |
| 0 | d3c4 |
| 0 | d3d4 |
| 0 | d3e4 |
| 0 | g7g6 |
| 0 | g7g5 |
| 0 | g7e7 |
| 0 | g7f7 |
| 400 | g7b7 |
| 400 | g7c7 |
| 400 | g7g3 |
| 400 | g7g2 |
| 400 | g7g1 |
| 400 | g7h7 |
| 400 | g7a7 |
| 400 | g7g8 |
| 500 | g7g4 |
| 500 | g7d7 |
The engine found the moves Rd7 or Rg4 at the depth of 3. The depth is very important for the quality of the moves found, but going further than a depth of 3 running this code will it require a lot of patience .
Let's now play a game against Stockfish
The first thing we need is to "start" the engine:
engine = chess.engine.SimpleEngine.popen_uci('stockfish-ubuntu-x86-64-avx2')
Then setup the initial board:
board = chess.Board()
Choose a depth to which calculate the moves:
depth = 3
Play the game:
while (not board.is_game_over()) and (not its_draw(board)):
legal_moves_scores = get_legal_moves_scores(board,depth=depth)
## my engine playing White so it will
## choose the most valuable move
my_move = legal_moves_scores['Move'].values[-1]
board.push(my_move)
## Stockfish plays
stockfish = engine.play(board,
limit=chess.engine.Limit(depth=depth))
board.push(stockfish.move)
#end while
25 moves and 2 hours later Stockfish won the game. This game moves were: 1. a4 c6 2. b4 e6 3. Ba3 a5 4. c3 Nf6 5. bxa5 Be7 6. d4 O-O 7. e4 Nxe4 8. f4 d5 9. g4 e5 10. Bxe7 Qxe7 11. Qf3 Qh4+ 12. Kd1 Bxg4 13. Be2 Bxf3 14. Nxf3 Qxf4 15. Rf1 Qe3 16. Nxe5 Nxc3+ 17. Nxc3 Qxd4+ 18. Bd3 Qxc3 19. Rb1 Qxe5 20. h4 Qd4 21. Kc2 Rxa5 22. Bxh7+ Kxh7 23. Rxb7 Rxa4 24. Rxb8 Rxb8 25. h5 Rc4#
Let's now calculate this game accuracy
Game accuracy
Using the tools I developed for my previous blog I got the following accuracy numbers:
| White | Black | |
|---|---|---|
| Mean accuracy | 85 | 96 |
Lichess' advantage chart for this game is:
Part 2: slightly improved algorithms
There at least 2 things that can be to improve the above algorithms:
- improve how the board is evaluated,
- use alpha-beta pruning, to speed up the minimax algorithm. For an explanation see the wikipedia and also this video.
An typical example of board evaluation improvement consists in changing the value of a piece depending on the square it is in. For instance, in general, is better to have knights in the center than on the rim.
Having never thought about what are the best values for this squares for the sake of example in this blog I took the values from Bartek Spitza's engine Sophia.
Therefore, for instance, the value of the white knight, will be altered based on the following matrix:
| A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|
| -50 | -40 | -30 | -30 | -30 | -30 | -40 | -50 |
| -40 | -20 | 0 | 5 | 5 | 0 | -20 | -40 |
| -30 | 5 | 10 | 15 | 15 | 10 | 5 | -30 |
| -30 | 0 | 15 | 20 | 20 | 15 | 0 | -30 |
| -30 | 5 | 15 | 20 | 20 | 15 | 5 | -30 |
| -30 | 0 | 10 | 15 | 15 | 10 | 0 | -30 |
| -40 | -20 | 0 | 0 | 0 | 0 | -20 | -40 |
| -50 | -40 | -30 | -30 | -30 | -30 | -40 | -50 |
I have also added an incentive for checks, captures and castling.
The improved board score is:
def improved_simple_board_score(board):
wpawn_sqr_values = np.array(
[
## A B C D E F G H
0, 0, 0, 0, 0, 0, 0, 0, #1
5, 10, 10,-20,-20, 10, 10, 5, #2
5, -5,-10, 0, 0,-10, -5, 5, #3
0, 0, 0, 20, 20, 0, 0, 0, #4
5, 5, 10, 25, 25, 10, 5, 5, #5
10, 10, 20, 30, 30, 20, 10, 10, #6
50, 50, 50, 50, 50, 50, 50, 50, #7
0, 0, 0, 0, 0, 0, 0, 0 #8
])
wknight_sqr_values = np.array(
[
-50,-40,-30,-30,-30,-30,-40,-50,
-40,-20, 0, 5, 5, 0,-20,-40,
-30, 5, 10, 15, 15, 10, 5,-30,
-30, 0, 15, 20, 20, 15, 0,-30,
-30, 5, 15, 20, 20, 15, 5,-30,
-30, 0, 10, 15, 15, 10, 0,-30,
-40,-20, 0, 0, 0, 0,-20,-40,
-50,-40,-30,-30,-30,-30,-40,-50
])
wbishop_sqr_values = np.array(
[
-20,-10,-10,-10,-10,-10,-10,-20,
-10, 5, 0, 0, 0, 0, 5,-10,
-10, 10, 10, 10, 10, 10, 10,-10,
-10, 0, 10, 10, 10, 10, 0,-10,
-10, 5, 5, 10, 10, 5, 5,-10,
-10, 0, 5, 10, 10, 5, 0,-10,
-10, 0, 0, 0, 0, 0, 0,-10,
-20,-10,-10,-10,-10,-10,-10,-20
])
wrook_sqr_values = np.array(
[
0, 0, 5, 10, 10, 5, 0, 0,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
5, 10, 10, 10, 10, 10, 10, 5,
0, 0, 0, 0, 0, 0, 0, 0,
])
wqueen_sqr_values = np.array(
[
-20,-10,-10, -5, -5,-10,-10,-20,
-10, 0, 5, 0, 0, 0, 0,-10,
-10, 5, 5, 5, 5, 5, 0,-10,
0, 0, 5, 5, 5, 5, 0, -5,
-5, 0, 5, 5, 5, 5, 0, -5,
-10, 0, 5, 5, 5, 5, 0,-10,
-10, 0, 0, 0, 0, 0, 0,-10,
-20,-10,-10, -5, -5,-10,-10,-20,
])
wking_sqr_values = np.array(
[
20, 30, 10, 0, 0, 10, 30, 20,
20, 20, 0, 0, 0, 0, 20, 20,
-10, -20, -20, -20, -20, -20, -20, -10,
-20, -30, -30, -40, -40, -30, -30, -20,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
])
piece_value = {
chess.PAWN: 100,
chess.KNIGHT: 300,
chess.BISHOP: 300,
chess.KING: 1000,
chess.ROOK: 500,
chess.QUEEN: 900,
}
white_sqr_values = {
chess.PAWN: 1+wpawn_sqr_values/piece_value[chess.PAWN],
chess.KNIGHT: 1+wknight_sqr_values/piece_value[chess.KNIGHT],
chess.BISHOP: 1+wbishop_sqr_values/piece_value[chess.BISHOP],
chess.KING: 1+wking_sqr_values/piece_value[chess.KING],
chess.ROOK: 1+wrook_sqr_values/piece_value[chess.ROOK],
chess.QUEEN: 1+wqueen_sqr_values/piece_value[chess.QUEEN],
}
## calculate the board score
if board.is_checkmate():
if board.turn:
score = -np.inf #white was checkmated
else:
score = np.inf #black was checkmated
elif its_draw(board):
score = 0.0
else:
score = 0.0
for piece in piece_value:
## white valuation
wpieces_loc = board.pieces(piece, chess.WHITE).tolist()
score = (score +
(white_sqr_values[piece]*wpieces_loc).sum()*
piece_value[piece])
## black valuation
bpieces_loc = board.pieces(piece, chess.BLACK).tolist()
score = (score -
(white_sqr_values[piece][::-1]*bpieces_loc).sum()
*piece_value[piece])
#end for
if board.turn: # White's turn
if board.is_check(): #White is in check
score = score - 50
if board.move_stack:
last_move = board.move_stack[-1]
if board.is_capture(last_move):
score = score - 20
if board.is_kingside_castling(last_move):
score = score - 25
if board.is_queenside_castling(last_move):
score = score - 20
#end if
else:
if board.is_check(): #Black is in check
score = score + 50
if board.move_stack:
last_move = board.move_stack[-1]
if board.is_capture(last_move):
score = score + 20
if board.is_kingside_castling(last_move):
score = score + 25
if board.is_queenside_castling(last_move):
score = score + 20
#end if
#end if
#end if
return score
The minimax algorithm with alpha-beta pruning is:
def alpha_beta(board, depth, alpha, beta):
if (depth==0) or (board.is_game_over()) or (its_draw(board)):
return improved_simple_board_score(board)
if board.turn: # White's turn
opt_value = -np.inf
for move in board.legal_moves:
board.push(move)
## White maximizes the board score
opt_value = np.max([opt_value,
alpha_beta(board, depth - 1, alpha, beta)])
board.pop()
if opt_value > beta:
break # beta cutoff
alpha = np.max([alpha, opt_value])
return opt_value
else: # Black's turn
opt_value = np.inf
for move in board.legal_moves:
board.push(move)
## Black minimizes the board score
opt_value = np.min([opt_value,
alpha_beta(board, depth - 1, alpha, beta)])
board.pop()
if opt_value < alpha:
break # alpha cutoff
beta = min([beta, opt_value])
return opt_value
Let's play Stockfish again
I used the same techniques as before, but this time calling the alpha-beta and improved board score functions.
My engine played a 88 move game, 2.5 hours game against Stockfish: 1. Nf3 c6 2. Nc3 Nf6 3. d4 d5 4. Bg5 Bg4 5. Ne5 Bf5 6. e3 e6 7. Bd3 Bg6 8. Bxg6 hxg6 9. O-O Be7 10. Qf3 O-O 11. Rad1 Qe8 12. Nd3 Qc8 13. Rfe1 Qc7 14. Bh4 Qa5 15. Bg5 Re8 16. Nf4 Nbd7 17. Nd3 Rab8 18. Nf4 Ra8 19. Nd3 Rad8 20. Nf4 Bb4 21. Nd3 Bd6 22. h3 Ra8 23. b4 Bxb4 24. Nxb4 Qxb4 25. Rd3 Nh7 26. Bh4 Qa5 27. Rb1 b6 28. e4 Rec8 29. exd5 cxd5 30. Ne2 Rxc2 31. Ra3 Qd2 32. Ng3 Qxd4 33. Be7 Qe5 34. Qe3 Qxe3 35. fxe3 Rc4 36. Rb2 Nhf6 37. Rb1 Nh7 38. Rb2 Nhf6 39. Rb1 Ne8 40. Rb2 Rc7 41. Rab3 Nef6 42. Rb1 Rc2 43. R3b2 Rxb2 44. Rxb2 Re8 45. Bxf6 gxf6 46. e4 f5 47. exd5 exd5 48. Re2 Re5 49. a3 Kg7 50. a4 Kf8 51. h4 Re7 52. Rxe7 Kxe7 53. Ne2 Kf6 54. Nc3 Ke5 55. Nb5 a5 56. Na7 Kf4 57. Kh2 Kg4 58. g3 f6 59. Nb5 Ne5 60. Nd4 Nd7 61. Nc2 f4 62. gxf4 Kxh4 63. Ne3 d4 64. Nd5 d3 65. Ne7 Nc5 66. Nxg6+ Kh5 67. f5 Kg4 68. Kg1 Kg5 69. Nh8 Kxf5 70. Nf7 Ke6 71. Nd8+ Kd5 72. Nc6 Kxc6 73. Kf1 Ne4 74. Ke1 d2+ 75. Ke2 f5 76. Kf1 d1=Q+ 77. Kg2 Qxa4 78. Kf1 f4 79. Kg1 f3 80. Kh2 f2 81. Kg2 Qa1 82. Kf3 Qd1+ 83. Kf4 Qd2+ 84. Kf5 Nd6+ 85. Kg4 Qe2+ 86. Kg3 f1=Q 87. Kh4 Qf4+ 88. Kh3 Qeh2#
Note that using the alpha-beta punning improved significantly the algorithm running time, even with a more complex board score function.
Game accuracy
This game accuracy was:
| White | Black | |
|---|---|---|
| Mean accuracy | 88 | 91 |
The Lichess' advantage chart is:
Final thoughts
If you want to know more about this subject, a web search on minimax algorithms applied to chess will bring up a wealth of resources that you will be able to explore.
Clearly having a good board score function is essential for the performance of the minimax algorithm. That is a quite difficult task. In contrast when it comes to ML algorithms, while neural network concepts are more complex, the evaluation functions are learned rather than hardcoded (see Acquisition of Chess Knowledge in AlphaZero, pg 4).
Finally I made a study with these 2 games plus a few others, namely the engine against me (study M48G4uxY).
