How to Build a Chess AI with Python
Building a game AI can be really difficult, especially when the rules of the game are complex. We’re lucky, chess is fairly simple to understand and the rules are clearly defined.
However, the many possibilities offered by this game make it very complicated to design an efficient algorithm to play it. Let’s take a look at how to do just that.
Python-Chess
The aim of this article is to design an artificial intelligence algorithm for chess. It is not to reproduce all the logic of the game in Python. So we’re going to use a library that will take care of all this logic, as well as the display of the board. Start by installing python-chess:
pip install chessLet me explain the basics of this library. You can create a game by retrieving a Board object:
import chess
board = chess.Board()If you display it, you get either a console display or an image, depending on the Python environment. For this article, I’ll be using a Jupyter Notebook, so I can take advantage of the image display.
If you’re using the console, use print(board) instead:
r n b q k b n r
p p p p p p p p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
P P P P P P P P
R N B Q K B N RYou can retrieve the list of possible moves with board.legal_moves. You can find out which player must play with board.turn, which returns True if white must play, otherwise False. You can play moves with board.push(move). And much more…
Random Moves
Let’s start with the simplest possible artificial intelligence: it only makes random moves, out of all possible moves. To do this, simply use random.
import random
def random_move(board):
moves = list(board.legal_moves)
move = random.choice(moves)
return moveLet’s try this:
move = random_move(board) board.push(move) board
Well, it works, but as you can imagine, it’s not great. At least it saves us the trouble of playing alone!
Board Evaluation
To improve our algorithm a little, we need to find the best possible moves. But how can a simple algorithm know which move is the best? We need to evaluate the board. Each possible move will have an impact on the board’s evaluation, either by increasing or decreasing its score.
To evaluate the board, start by assigning a value to each piece. Since the least important piece is the pawn, we’ll give it a low score, unlike the queen, which is the most important piece (with the king of course). Let’s say a pawn is worth 1, a bishop or knight 3, a rook 5, a queen 9, and a king 0 (because we can’t take it).
Secondly, since chess is a zero-sum game, when one player wins, the other loses. The board’s value when White wins is therefore the opposite of its value when he loses. By convention, we assign negative values to black pieces and positive values to white pieces.
To sum up, a rating of -2 means, for example, that white has lost 2 pawns. An evaluation of +1 means they have one more pawn.
In Python, we can store the values of the pieces in a simple dictionary.
piece_values = {
chess.PAWN: 1,
chess.KNIGHT: 3,
chess.BISHOP: 3,
chess.ROOK: 5,
chess.QUEEN: 9,
chess.KING: 0
}We can now build our evaluation function using chess :
def evaluate_board(board):
score = 0
for square in chess.SQUARES:
piece = board.piece_at(square)
if piece is not None:
if piece.color == chess.WHITE:
score += piece_values[piece.piece_type]
else:
score -= piece_values[piece.piece_type]
return scoreLet’s try our evaluation function:
board = chess.Board()
evaluation = evaluate_board(board)
print(f"Evaluation with all pieces: {evaluation}")
# remove a white pawn
board.remove_piece_at(chess.E2)
evaluation = evaluate_board(board)
print(f"Evaluation without a white pawn: {evaluation}")
# remove a black rook
board.remove_piece_at(chess.A8)
evaluation = evaluate_board(board)
print(f"Evaluation without a black rook: {evaluation}")Evaluation with all pieces: 0
Evaluation without a white pawn: -1
Evaluation without a black rook: 4Finding the Best Move
To find the best move, all we have to do now is test all possible moves and see which one leads to the most advantageous board evaluation according to our color.
def best_move_using_simple_evaluation(board):
white_to_play = board.turn
best_score = -9999 if white_to_play else 9999
best_move = random_move(board)
for move in board.legal_moves: # we try each possible move to find the best
board.push(move)
score = evaluate_board(board)
board.pop()
if score > best_score and white_to_play:
best_score = score
best_move = move
elif score < best_score and not white_to_play:
best_score = score
best_move = move
return best_moveIn practice, our algorithm still kind of sucks, because all that changes is that it will take pieces if it can. If it can’t take pieces, its moves remain pretty much random (pretty much because the move it chooses is always in the same place in the list of possible moves in this case).
move = best_move_using_simple_evaluation(board) board.push(move) board
After a few moves, both players have lost a few pieces because this AI just tries to capture pieces…
Minimax
Minimax is an algorithm used to minimize the worst-case potential loss. In other words, it’s an algorithm that considers all the opponent’s best responses to a situation and chooses the strategy so that the opponent’s best response penalizes us as little as possible.
Minimax is based on the principle of searching through the game tree to determine the best move for a player.
To implement it in Python, here is what we need to do:
- Representation of the Game State: The chessboard and the current positions of all the pieces are represented as a data structure in computer memory.
- Generating Possible Moves: The algorithm generates all possible moves for the current player at a given game state.
- Evaluating the Game State: For each possible move, the algorithm evaluates the resulting game state. This evaluation function assigns a numerical value to the position, indicating how favorable it is for the player.
- Minimax Search: The algorithm performs a depth-limited search of the game tree, considering both the player’s moves and the opponent’s counter-moves. It alternates between maximizing the evaluation function for the player and minimizing it for the opponent at each level of the tree.
- Recursive Evaluation: The minimax algorithm evaluates the game states recursively, starting from the current position and exploring each move’s consequences up to a certain depth. It uses the evaluation function to assign scores to intermediate positions, assuming both players make optimal moves.
- Terminal States: The algorithm continues the search until it reaches a terminal state, which can be a checkmate, stalemate, or a predefined depth limit.
- Selecting the Best Move: After evaluating all possible moves and their consequences, the algorithm chooses the move that leads to the highest evaluated position. This move is considered the best move for the current player at the given game state.
We already have the 3 first steps. We’ll implement the steps 4 to 6, and implement the best move selection in the function we used earlier.
Here is the minimax implementation:
def minimax(board, depth, white_to_play):
if depth == 0 or board.is_game_over():
return evaluate_board(board)
if white_to_play:
best_score = -99999
for move in board.legal_moves:
board.push(move)
score = minimax(board, depth - 1, False)
board.pop()
best_score = max(score, best_score)
return best_score
else:
best_score = 99999
for move in board.legal_moves:
board.push(move)
score = minimax(board, depth - 1, True)
board.pop()
best_score = min(score, best_score)
return best_scoreNow we just need to modify our function that calculates the best move to calculate the score using minimax.
def best_move_using_minimax(board, depth):
white_to_play = board.turn
best_score = -99999 if white_to_play else 99999
best_move = random_move(board)
for move in board.legal_moves:
board.push(move)
score = minimax(board, depth - 1, not white_to_play)
board.pop()
if score > best_score and white_to_play:
best_score = score
best_move = move
elif score < best_score and not white_to_play:
best_score = score
best_move = move
return best_moveHere is a position I got after a few moves:
It’s already a little better, but our algorithm consumes far too many resources…
Optimized Minimax
We’ll use alpha-beta pruning to optimize our minimax algorithm. It allows us to disregard some branches in the minimax search tree, so we can keep the same depth for the calculations while using fewer resources.
We just add an extra step between steps 5 and 6:
- Pruning with Alpha-Beta: This technique eliminates branches of the game tree that are guaranteed to be worse than previously explored alternatives. It reduces the number of positions that need to be evaluated, speeding up the search process.
def minimax(board, depth, alpha, beta, white_to_play):
if depth == 0:
return evaluate_board(board), None
if white_to_play:
best_score = -9999
best_move = None
for move in board.legal_moves:
board.push(move)
score, _ = minimax(board, depth - 1, alpha, beta, False)
board.pop()
if score > best_score:
best_score = score
best_move = move
alpha = max(alpha, best_score)
if alpha >= beta:
break
return best_score, best_move
else:
best_score = 9999
best_move = None
for move in board.legal_moves:
board.push(move)
score, _ = minimax(board, depth - 1, alpha, beta, True)
board.pop()
if score < best_score:
best_score = score
best_move = move
beta = min(beta, best_score)
if alpha >= beta:
break
return best_score, best_moveThis algorithm is a simple minimax optimization, as it does not change the result.
Taking Pieces Position into Account
Our evaluation function is very basic. It assigns a fixed value to the pieces and therefore doesn’t take their position into account. However, we know that a knight in a corner is less important than a knight in the center. Similarly, a pawn approaching the opponent’s camp is more important than a pawn that hasn’t moved, as it is likely to turn into a queen.
So we’re going to change our evaluation function to take account of the position of the pieces. So let’s start by changing our dictionary
piece_values_with_position = {
chess.PAWN: [
[0, 0, 0, 0, 0, 0, 0, 0],
[50, 50, 50, 50, 50, 50, 50, 50],
[10, 10, 20, 30, 30, 20, 10, 10],
[5, 5, 10, 25, 25, 10, 5, 5],
[0, 0, 0, 20, 20, 0, 0, 0],
[5, -5, -10, 0, 0, -10, -5, 5],
[5, 10, 10, -20, -20, 10, 10, 5],
[0, 0, 0, 0, 0, 0, 0, 0]
],
chess.KNIGHT: [
[-50, -40, -30, -30, -30, -30, -40, -50],
[-40, -20, 0, 0, 0, 0, -20, -40],
[-30, 0, 10, 15, 15, 10, 0, -30],
[-30, 5, 15, 20, 20, 15, 5, -30],
[-30, 0, 15, 20, 20, 15, 0, -30],
[-30, 5, 10, 15, 15, 10, 5, -30],
[-40, -20, 0, 5, 5, 0, -20, -40],
[-50, -40, -30, -30, -30, -30, -40, -50]
],
chess.BISHOP: [
[-20, -10, -10, -10, -10, -10, -10, -20],
[-10, 0, 0, 0, 0, 0, 0, -10],
[-10, 0, 5, 10, 10, 5, 0, -10],
[-10, 5, 5, 10, 10, 5, 5, -10],
[-10, 0, 10, 10, 10, 10, 0, -10],
[-10, 10, 10, 10, 10, 10, 10, -10],
[-10, 5, 0, 0, 0, 0, 5, -10],
[-20, -10, -10, -10, -10, -10, -10, -20]
],
chess.ROOK: [
[0, 0, 0, 0, 0, 0, 0, 0],
[5, 10, 10, 10, 10, 10, 10, 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, 0, 0, 0, 0, 0, 0, -5],
[0, 0, 0, 5, 5, 0, 0, 0]
],
chess.QUEEN: [
[-20, -10, -10, -5, -5, -10, -10, -20],
[-10, 0, 0, 0, 0, 0, 0, -10],
[-10, 0, 5, 5, 5, 5, 0, -10],
[-5, 0, 5, 5, 5, 5, 0, -5],
[0, 0, 5, 5, 5, 5, 0, -5],
[-10, 5, 5, 5, 5, 5, 0, -10],
[-10, 0, 5, 0, 0, 0, 0, -10],
[-20, -10, -10, -5, -5, -10, -10, -20]
],
chess.KING: [
[-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],
[-20, -30, -30, -40, -40, -30, -30, -20],
[-10, -20, -20, -20, -20, -20, -20, -10],
[20, 20, 0, 0, 0, 0, 20, 20],
[20, 30, 10, 0, 0, 10, 30, 20]
]
}We now use a list containing the score for each position of the piece on the board. The higher the score, the stronger the piece.
Now, we can rewrite our evaluation function:
# a little helper function to calculate pieces values
def get_piece_value(piece, x, y):
if piece.piece_type == chess.PAWN:
return 100 + piece_values_with_position[piece.piece_type][x][y]
elif piece.piece_type == chess.KNIGHT:
return 320 + piece_values_with_position[piece.piece_type][x][y]
elif piece.piece_type == chess.BISHOP:
return 330 + piece_values_with_position[piece.piece_type][x][y]
elif piece.piece_type == chess.ROOK:
return 500 + piece_values_with_position[piece.piece_type][x][y]
elif piece.piece_type == chess.QUEEN:
return 900 + piece_values_with_position[piece.piece_type][x][y]
elif piece.piece_type == chess.KING:
return 20000 + piece_values_with_position[piece.piece_type][x][y]
else:
return 0
def evaluate_board(board):
score = 0
for i in range(8):
for j in range(8):
piece = board.piece_at(chess.square(i, j))
if piece is not None:
if piece.color == chess.WHITE:
score += get_piece_value(piece, i, j)
else:
score -= get_piece_value(piece, i, j)
return scoreWe don’t even need to modify our algorithm since it’s independent of the evaluation function we use. So we can directly try our new evaluation function:
move = best_move_using_minimax(board, 5)
board.push(move)
boardWe now have an algorithm that plays pretty well. For example, for me, with a depth of 5, it has always played e4 first, which is one of the most played and best first moves in chess.
Here is what I got after a few moves:
Final Note
We now have an algorithm, admittedly a basic one, but one that doesn’t make too many mistakes and is perfectly capable of beating a beginner.
To do better, we’d need more resources to increase the depth or a neural network-based algorithm trained on a large number of games.
For more information about chess programming, you can check https://www.chessprogramming.org/Main_Page.
To explore more of my stories, click here!
If you want to be notified every time I publish a new story, subscribe to me via email by clicking here!
If you’re not subscribed to Medium yet and wish to support me or get access to all my stories, you can use my link:
