Let's write a tiny chess engine in Go

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, while still being capable of playing decent chess. Go is also known as a simple and highly readable language, so I hope the two of them could make a great couple.

To build a chess engine one has to decide on three important topics:

The code snippets in this post are simplified and contain only most important parts of code. You may find the full code of the engine at https://github.com/zserge/carnatus (the name comes from latin species name of Gopher rockfish).

Squares and pieces

It is important to find a convenient and memory-efficient board representation, because during the optimal move search thousands of boards would be kept in memory.

A board is typically represented as an array of squares. We would add some padding around the typical 8x8 board so that invalid piece moves would end up in this padding area. This allows us to avoid boundary checks and simplifies code a lot.

We will be using a linear array. The longest move distance that a chess piece can move is a knight move by 2 squares. Of course, other sliding pieces can move over longer distances, but such moves would be evaluated step by step, and board boundaries would be found sooner.

So, we need a 2 square padding around the board. We could create a 12x12 board, but as long as we represent it as a linear array - we only need 12x10 board, because the rightmost padding square from the previous row could also be used as the leftmost padding of the next row (× = padding):

××××××××××
××××××××××
×........×
×........×
×........×
×........×
×........×
×........×
×........×
×........×
××××××××××
××××××××××

In our notation “a1” would be 9×10+1=91, and “a8” would be “2×10+1”=21.

Each cell in the board array would represent a playing piece, an empty square or padding. We could use numerical constants for those values, but to make it easier to debug - let’s use human readable characters. Uppercase and lowercase letters would be pieces, white space would be padding and dots would be empty squares:

          |
          |
 RNBQKBNR |
 PPPPPPPP |
 ........ |
 ........ |
 ........ | <- this looks like a real chess board
 ........ |
 ........ |
 ........ |
 pppppppp |
 rnbkqbnr |
          |
          |

We can finally 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 { ... }

Pieces have values. We need those to estimate board positions and understand who is winning. Typically, a pawn = 100, knight = 280, bishop = 320, rook = 479, queen = 929 and king is some enormously large number that would be greater than 8 queens (pawns turned into queens) + pairs of knights, bishops and rooks. If we have all this wealth but lose the king - the estimation would still show that we will lose.

Each type has a Flip() method that returns the same value after the board is flipped before the opponent’s move. For pieces this inverts the case of the piece symbol. For squares it returns 119-s (counting from the other end of the board). For whole boards is copies all pieces from the squares in the reverse order, flipping their case.

Move generator

We have the building blocks and can now start thinking about the game position. Position is the board with pieces and some additional game state, such as en-passant square, king-passant square and castling options. If we wanted to simplify our chess game - we could probably just reuse the Board type, but here we will create a separate Position type, responsible for board moves and value estimation.

What is a move? It’s a tuple of two squares - the square where the piece was before the move and the square where the piece has moved to. And position is a chess board with score, castling rules for each player and en-passant/king-passant squares. Both types also have a Flip() method for opponent’s moves.

type Move struct {
  from Square
  to   Square
}
func (m Move) Flip() Move { ... }

type Position struct {
  board Board   // current board
  score int     // board score, the higher the better
  wc    [2]bool // white castling possibilities
  bc    [2]bool // black castling possibilities
  ep    Square  // en-passant square where pawn can be captured
  kp    Square  // king passent during castling, where kind can be captured
}
func (p Position) Flip() Position { ... }

We can now write our first big method - valid moves generator. We only care about the white pieces, because to play black we will be flipping the board and making the white move again.

To generate all valid moves we need to:

This is a simplified code that does not care about en-passant and castling. You may find the full implementation on Github, it’s not much different.

To make direction arithmetics more readable we will be using directional 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
}

Yes, that’s all the chess rules we need to consider to make valid moves. The next step would be to apply a move to the position to create the new game position. Without considering en-passant, 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()
}

It simply moves the piece, mark the previous square as empty and flips the board. The full method implementation can be found on Github, it handles all special pawn and king moves correctly.

At this point we can play chess human-vs-human by controlling and making valid moves only. Or we can make a dumb chess engine that makes random moves until it loses.

But how to tell that we are losing?

Board estimation

Every board position has a score. Initially, the score is zero since both players are equal. When a move is made - it changes the score of the board, depending on what pieces were captured and how the pieces changed their positions on board.

In the simplest case, we can just count the pieces on board and sum up their values (minus the pieces of the opponent). This would tell us when the king is lost due to a checkmate. But this is a very poor estimation.

A much better, and surprisingly simple approach is to use piece-square tables (PST). For each piece we create a table, same size as our board, where for each square a matching value is assigned. These values are empirical, so I have simply stolen the PST values from sunfish engine.

In fact, better chess engines change the PST tables during the game because the values of the pieces change over time (i.e. pawns get more valuable towards the end of the game). But we will keep our engine simple.

To estimate the position after the move we need to:

Additionally, we need to adjust PST rook values during castling and pawn value during promotion or en-passant capture. But in this article I will omit that:

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])
  // Adjust PST for the moving piece
  score := pst[p][j] - pst[p][i]
  if q != '.' && q != ' ' && !q.ours() {
    // Adjsut PST for captured piece
    score += pst[q.Flip()][j.Flip()]
  }
  return score
}

Now we can make a slightly better engine that chooses the best available move instead of a valid random one.

But real chess engines look deeper and analyze a tree of possible moves from each side to find the best move in the longest perspective.

Search algorithm

For toy chess engines the most popular search algorithm is depth-first search that starts from root and goes down to the given depth limit, iterating all possible moves before backtracking. For each possible move the value of the position is calculated using minimax algorithm with alpha-beta pruning.

Minimax is a rule used to minimize the worst-case potential loss - a player considers all of the best opponent moves, and selects the move such that the opponent’s best strategy gives a score as large as possible.

Naive minimax would be too slow for chess as it would require iterating too many moves in depth to find a good one.

Alpha-beta pruning is used to speed up minimax by removing nodes not worth consider. An intuition behind A/B pruning is the following. Imagine you are playing chess and found a really good move A. You keep looking at the board and found an even better move B. But you look deeper and see that after move B the opponent will force checkmate you in a few moves. You will no longer consider move B at all and will not waste time on investigating other possible outcomes of move B.

Both minimax rule and A/B pruning are important to understand how chess engines work. Sunfish engine uses an improved MDF(f) search algorithm, which is also a variant of a minimax algorithm with pruning.

In our engine we will gradually increase the search depth and call MDF(f) algorithm to find lower and upper bounds of the optimal score. The MDF(f) algorithm will be using A/B pruning iterations with transposition cache.

Transposition cache is a cache where for each board position we remember the depth, the score and the move that led us into this position. Later, when a new position is considered - it is first looked up in the transposition table.

I will not be posting the code of the search algorithm here, it’s really just a few lines of recursive search, but you can always find the full sources of the chess engine on github.

What’s next

If you are interested in small chess engines, I strongly recommend playing with sunfish. Also, sunfish was based on Micromax engine, which has a wonderful documentation by his author, definitely worth reading.

chess

As for the current engine in Go - I’ve added a tiny UCI protocol implementation so that one could use it with PyChess UI. It’s still probably full of bugs and potential improvements, but it was an interesting path - from early thoughts about chess engine design to the real playable computer chess program.

Yes, it’s weak, but it plays real chess!

I hope you’ve enjoyed this article. You can follow – and contribute to – on Github, Mastodon, Twitter or subscribe via rss.

Mar 21, 2020