Making a Chess Bot From Scratch

I’ve recently had the opportunity to tutor a a chess prodigy. Our tutoring covers coding and robotics, so I gave him some chess-themed projects we could work on, and he jumped at the chance to program his own computer to play chess. At his level, I can’t teach him chess, but I can help him teach chess to a computer.

This post covers a lot of the material I have development for him, and serves as an introduction to making AI play games and some simple techniques to optimise them.

1. Getting a Simulation

The first thing is to create an environment for the AI to play in.

Because we want to make a chess bot, and not a game of chess, we opted to use the Chess library for Python. The Chess library has a simple API and a lot of features, making it a great choice.

The simplest example of playing chess with the library is:

import chess

board = chess.Board()

while not board.is_game_over():
  print(board)
  move = input('Enter a move: ')
  board.push_san(move)

Note, here board.push_san takes in the Standard Algebraic Notation (SAN) for a move. SAN describes the ending position of a piece. For example, e4 means move a pawn to e4.

This code has some problems:

1. It’ll crash if it’s given an invalid move.
2. The board isn’t easy to read.
3. We don’t have a chess bot!

The first two problems are minor - the chess prodigy has no issues reading the board, and he doesn’t enter invalid moves. While it would be nice to fix these, our goal is to make a chess bot.

2. Making an AI Control the Simulation

Now that we’ve made a basic environment, we need a way for our AI to send moves to the chess board.

def bot_move(board):
  # Think about the best move ...
  return 'a2a4'

Note, our chess moves are primarily in UCI, which stores the starting square and ending square of the move. For example, a2a4 moves the piece on a2 to a4.

While moving a pawn to a4 isn’t a great move, we just need something simple so we know that our bot is making moves. Once it can make moves, we’ll code it so it can make good moves.

Updating our main loop, we get:

while not board.is_game_over():
  bot_move = bot_move(board)
  board.push_uci(bot_move)

  print(board)

  move = input('Enter a move: ')
  board.push_san(move)

Now whenever we play a move, our bot responds with a4. After we make a second move, the game crashes.

Our bot is blindly playing a4, regardless of whether it is a valid move. Let’s try to teach our bot some other moves!

3. Pre-Programmed Moves

These are the simplest to implement. Basically we teach our bot simple if this then that responses. This a really effective approach in chess, as we have what are called “Book Moves” which are essentially just the best moves in a situation.

For example, the London System is the moves:

1.d4 d5
2.Nf3 Nf6
3.Bf4

Assuming our bot is playing white, we could hard-code it so first it moves d4, then if our opponent plays d5, the bot responds Nf3, and if our opponent develops with Nf6, the bot replies Bf4.

Note, from this point on, most code is pseudo code to make the key concepts clearer.

To add this as code, we need to make our own book of chess moves:

# Remember, we need to use UCI notation instead of SAN.
book = {
  None: 'd2d4'         # Bot's opening move
  'd7d5': 'Ng1Nf3',    # Bot's response to d5
  'Ng8Nf6': 'Bc1Bf4'   # Bot's response to Nf6
}

def bot_move(board):
  last_move = board.peek() # Get the most recent move
  last_move_uci = last_move.uci() # Convert it to UCI notation

  return book[last_move_uci] # Return that move from the book.

Now our bot can play the London!

However, our approach is flawed. The bot doesn’t have a memory. When someone plays Nf6, our bot replies Bf4, regardless of the previous moves.

To fix this, we will give our bot a memory.

4. Giving our Bot a Memory

Instead of making moves based on the last move, let’s make the bot remember a history of moves, and then play the next move in the sequence.

history = ''
book = {
  '': 'd2d4'         # Bot's opening move
  'd2d4d7d5': 'Ng1Nf3',    # Bot's response to d5, after having played d2d4
  'd2d4d7d5Ng1Nf3Ng8Nf6': 'Bc1Bf4'   # Bot's response to Nf6, after having played d2d4, d7d5, Ng1Nf3
}

def bot_move(board):
  global history
  last_move = board.peek() # Get the most recent move
  last_move_uci = last_move.uci() # Convert it to UCI notation
  history += last_move_uci

  move = book[last_move_uci] # Get the move the bot will make
  history += move # Add the bot's move to the history

  return move

Now our bot can remember sequences of moves, and make longer responses. We could build on this to encode multiple different openings and lines, such as the Ruy Lopez or Grünfeld, just by adding them to our book. However, that will be left as an exercise for the reader.

Our bot has two main issues now:

1) It’s only been programmed to play as white.

Making the bot play as black is relatively simple. First, it needs a book for black, then it needs a way to know whether it is playing white or black. Note, This could be done with a single book, but it’s clearer to make a separate book for black.

2) It can only play book moves.

Only making book moves is a big problem. After 3 moves, there are already over 9 million possible chess games. We can’t possibly program all of them! We need our bot to think about moves without relying on our book.

5. Letting our Bot Play Non-Book Moves

At the moment, our bot can only make pre-programmed moves. While we can get pretty far with this, it will only be able to play the moves we have programmed. As soon as the game goes off-book, or we run out of pre-programmed moves, our bot will be stuck.

In order for our bot to be an intelligent chess player, rather than a glorified flow-chart, we will need to let it calculate what move might be good, rather than relying on pre-programmed instructions.

For the bot to know what move is best, it needs a way to score each move. We’ll acheive this by creating an evaluation function, which analyses a board and produces a score. To use it, we’ll simulate making a move, evaluate the new board and compare the score to every other move we could have made in that position.

Our bot can see playing d4 maximizes the score, so it will play d4.

5.1 How do we Score Positions?

We need to turn a chess position into a single number for our bot to decide what is best.

The simplest evaluation is the material, which is the sum of all pieces on the board.

Note, we don’t score the King, because it cannot be captured.

Using the + and - scores, we will get a single number that will tell us how strong the position is, and who is winning. For example, if our evaluation returns +1, it’s a slight advantage for white. If it is -9, it’s a large advantage for black.

A simple implementation would look like:

def material_evaluation(board):
  piece_values = {
    chess.PAWN: 1,
    chess.BISHOP: 3,
    chess.KNIGHT: 3,
    chess.ROOK: 5,
    chess.QUEEN: 9
  }

  score = 0
  # Loop over all squares
  for square in chess.SQUARES: 
    piece = board.piece_at(square)
    # There's not a piece on this square. Skip it.
    if not piece:
      continue
    # If the piece is white, add its value to the score.
    # Otherwise, subtract its score.
    if piece.color == chess.WHITE:
      score += piece_values[piece.piece_type]
    else:
      score -= piece_values[piece.piece_type]
  return score

5.2 Letting our Bot Evaluate Moves

Now, we can add some extra code to our bot to let it play book moves, then once the game has gone off book, it will begin using the evaluation function we gave it.

def bot_move(board):
  global history
  last_move = board.peek() # Get the most recent move
  last_move_uci = last_move.uci() # Convert it to UCI notation
  history += last_move_uci

  move = book.get(last_move_uci) # Get the move the bot will make
  if move == None:
    # We need to calculate a position as we don't have a book move to respond with.
    best_score = None
    best_move = None
    for move in board.legal_moves:
      # Make the move
      board.push(move)
      # Score the new position
      score = material_evaluation(board)
      # Undo the move
      board.pop()

      if best_score is None or score > best_score:
        best_move = move
        best_score = score

    # We've looked over every move. Play the best move we've found.
    move = best_move

  history += move # Add the bot's move to the history
  return move

6. Next Steps

Our bot can now play a mix of book and non-book moves by calculating the best move in a given position. However, this bot is still really weak. The main issues are that it only scores moves that capture pieces, and it only looks one move into the future. This means it will give up its queen to take a pawn, which doesn’t make for a good chess player!

To fix these shortcomings, we’ll need two major changes:

1. Extra evaluation functions
2. Looking further into the future

6.1 Extra Evaluations

Instead of only scoring based on the captures, we could add extra evaluations based on other factors. For example, we could look at how far advanced the bot’s pawns are, or reward it for placing it’s king in a corner. A pawn on the 7th rank might be worth a lot, because it can promote into a queen if it reaches the 8th rank. We want to incentivise our bot making useful moves.

This will let the bot begin to play a positional style of chess, where it is not just trying to take pieces, but is trying to make its own position stronger.

6.2 Looking in to the Future

The bot currently only looks at its next move. To make the bot smarter, it will need to look ahead further. Maybe it can make a capture, but will end up in checkmate. To avoid this short-sighted style of play, we will simulate multiple moves into the future (for both our bot and our opponent) and choose the move that leads to the best future for us.

This can best be thought of as a tree, where each potential board branches from the previous board.

7. Conclusion

Hopefully this has been an insightful look at how to get started with AI playing games. While this is tailored to chess, these principles can be applied to many other games.

Look out for a follow up post once we’ve made some more progress. I’ll include any insights the chess prodigy can come up with!