Dedicated to everyone who is now watching the acclaimed TV series "The Queen's Gambit". More chess terms in our new translation.
In this article, we will try to understand how chess engines work by porting the sunfish chess engine to Go. Sunfish is notable for its simplicity and small size, but it can still play a decent chess game. Go, on the other hand, is known as a simple and readable programming language, so I hope that together they make a great pair.
To create a chess engine, you first need to decide on three important points:
- How to represent the chessboard (cells, pieces, allowed moves)?
- How do you rate the board (who is more likely to win)?
- How to find the optimal move?
The code snippets in this post are simplified and contain only the most important parts. You can find the complete engine code at github.com/zserge/carnatus (carnatus is the Latin name for sea bass, Sebastes carnatus species).
Cells and shapes
It is important to find a convenient representation of the board that does not take up much space, since thousands of board variations will be stored in memory while searching for the optimal move.
Usually a board is a collection of cells. We will add padding around the standard 8x8 board so that invalid piece moves fall into this area. This will allow us to avoid bounds checking and greatly simplify the code.
We will be using a linear array. The greatest distance a chess piece can move is a 2-square knight's move. Of course, other sliding pieces can move long distances, but such moves will be sequentially evaluated as each square is crossed, which means that the board boundaries will be detected before a piece can go beyond them.
Thus, we need a two-cell space along the edges of the board. We could create a 12x12 board, but since we're representing it as a line array, we need a 12x10 board because the rightmost indent square on the previous line can be used as the left-most indent square on the next line (× = indent):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
In our notation, “a1” would look like 9 × 10 + 1 = 91, and “a8” would look like “2 × 10 + 1” = 21.
Each cell in the board array would represent a chess piece, an empty square, or an indentation zone. could have used numeric constants for these values, but to simplify debugging, we use human-readable characters.Uppercase and lowercase letters will denote shapes, spaces will denote indentation zones, and dots will denote empty cells:
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Decoding of abbreviations
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Finally, we can start writing code:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
Shapes have a certain value. These values are needed to evaluate positions on the board and understand who is winning. Usually a pawn = 100, a knight = 280, a bishop = 320, a rook = 479, a queen = 929, and a king is so valuable that it beats 8 queens (pawns turned into queens) in conjunction with pairs of knights, bishops and rooks. If we have all this wealth, but we lose the king, counting will still show that we will lose.
Each type has a Flip () method that returns the same value after flipping the board before the opponent moves. For shapes, it changes the case of the shape symbol. At the squares, he returns 119 squares (counting from the other end of the board). As for the board, he copies all the pieces from the squares in reverse order, changing their case.
Stroke generator
So, we already have the building blocks for the engine, and now we can think about game positions. Position is a board with pieces and additional states in the game, such as a passage square, a wandering square, and castling possibilities. If we wanted to simplify the game, we could reuse the Board type, but we will create a separate Position type for moves and board evaluation.
What is a move? This is a combination of two cells - the cell where the piece was before the move, and the cell where the piece moved. Position is a chessboard with score, castling rules for each player, and passage / wandering squares. Both types also have a Flip () method for the opponent's moves.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Now we can write the first big method - the allowed moves generator. We only care about the white pieces, since to play black we will turn the board over and move white again.
To generate all valid moves, we need:
- make a list of all one-step moves in each direction for each piece;
- do the same for all cells, ignoring non-white pieces;
- designate a move in every possible direction for each white piece;
- if the length of a piece's move is not limited (rook, bishop, queen), continue to move it until it encounters an obstacle on its way: an opponent's piece or a gap behind the edge of the board
This is a simplified code that does not take into account capture and castling. You can find the full implementation on Github , it is not much different.
To make the direction arithmetic more readable, we will use the direction constants N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
These are all the rules of the game of chess that we need to consider in order to make valid moves. The next step is to apply a move to the position to create a new game position. Without taking into account capturing en route, pawn promotion and castling, the method would look like this:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
He simply moves the piece, marks the cell on which it was previously empty, and flips the board. The full implementation of the method can be found on Github , it handles all special pawn and king moves correctly.
At this stage, you can play chess "man against man", controlling the process and making only legal moves. Or you can create a primitive chess engine that makes random moves until it loses.
But how do we understand that we are losing?
Board rating
Points are awarded for each position on the board. Initially, the score is zero, since both players start on equal terms. After completing a move, the score changes depending on which pieces were captured and how the pieces changed position on the board.
In the simplest case, we can count the pieces on the board and add up their value (minus the opponent's pieces). Such a calculation will show if the king is declared check and checkmate. But this is a very weak assessment system.
A much more accurate and surprisingly simple approach is Shape-to-Square Ratio Tables ( PST- Piece-Square Tables). For each piece, a table is created the same size as a chessboard, where a corresponding value is assigned to each square. These values are empirical, so I just took them from the Sunfish engine.
In fact, more advanced chess engines update PSTs during play because the value of the pieces changes (i.e. pawns become more valuable towards the end of the game). But we will have a simple engine.
To evaluate the position after the move, we need:
- determine the rating of the current position,
- subtract the value of the piece being moved,
- add a new figure value according to the PTS table,
- add the value of the captured piece, if any.
Additionally, we need to adjust the value of the rook during castling and the value of the pawn during the promotion or capture on the passage in the PST table. But in here we will not consider this:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Now we can make a slightly more advanced engine that will choose the best possible move, rather than any of the valid ones.
But real chess engines do deeper analytics and iterate over the branches of possible moves on each side to find the best possible move in the long run.
Search algorithm
The most common search algorithm in chess engines is simpler - depth-first search, which starts at the root and goes down to a given depth limit, repeating all possible moves before returning. For each stroke position value is calculated using a minimax algorithm (minimax) c alpha-beta pruning ( alpha-beta pruning ).
Minimax is a rule used to minimize possible losses in the worst case scenario: the player considers all the best moves of the opponent and chooses such a move so that the best strategy of the opponent brings as many points as possible.
A simple minimax algorithm would be too slow for chess and would require repeating too many moves to find a good one.
Alpha-beta pruning is used to speed up the minimax algorithm by removing nodes that are not worth considering. Alpha-beta clipping is based on the following logic: Imagine that you are playing chess and find a very good move A. You keep looking at the board and find an even better move B. But then you analyze the situation deeper and understand that if you choose on move B, the enemy will declare check and checkmate on you in a few moves. Now you will discard B and not waste time analyzing other possible combinations after B.
Both minimax and alpha-beta clipping are important in understanding how the chess engine works. The Sunfish engine uses an improved MDF (f) search algorithm , which is also a variant of the minimax algorithm combined with clipping.
In our engine, we will gradually increase the search depth and call the MDF (f) algorithm to find the lower and upper bounds of the optimal result. The MDF (f) algorithm will use an alpha-beta clipping iteration with a transposition cache.
Transposition cash is a cache where for each position on the board we memorize the depth, score and move that led us to that position. Then, when considering a new position, it is first checked against the transposition table.
I will not post the code of the search algorithm here, as it is just a few lines of recursive search, but you can always find the full source code of the chess engine on GitHub .
What's next?
If you are interested in simple chess engines, I highly recommend playing with Sunfish. By the way, Sunfish is based on the Micromax engine and comes with some great documentation from the author, which is definitely worth reading.
For our engine in Go, I added a small implementation of the UCI protocol so that it can be used with the PyChess UI. Most likely, it still has a lot of bugs and a lot of potential for improvement, but it was an interesting path: from the idea of developing a chess engine to a ready-made, working computer chess program.
Yes, he is weak, but he plays real chess games!
I hope you enjoyed this article. You can follow me at Github , Twitter or subscribe via rss .