How to create your own chess bot
If you are well familiar with chess then it would be more of a fun thing. I loved playing chess since my childhood and wanted to build a chess engine that would beat me. If you are having the same instinct, you're gonna enjoy this article!
There are two kinds of chess engines as of now. One relies on search algorithms and some heuristic techniques while the other use machine learning. Stockfish and Alphazero are the two leading examples of these two kinds of engines respectively. In this article, we limit ourselves to hardcoded techniques used in Stockfish-like engines.
Let’s begin . . .
If we observe humans playing chess closely, They follow the following steps: 1. check all the possible moves we have. 2. Predict opponent's reaction move 3. Play the move which is most beneficial. The same thing can be achieved using the minimax algorithm. It assumes that our opponent will play a winning move too and constructs a tree such that the leaves of the tree are the end states of the game and one just need to follow the path to winning game state.
In simple words - the minimax algorithm initially assumes all the possible moves are equally likely to happen. For each such move, it explores the next possible moves played by an opponent player and the process goes on until we reach the end of the game. Leaves of the tree represent the end states of the game, here we evaluate the state and backtrack these values and update the intermediate node values. Please refer references below to know more about minimax.
But here’s one catch, for chess, the number of possible nodes at each level explodes exponentially such that even modern machines can’t compute them in real-time. To date, no algorithm can solve the chess game completely. Then, how we are going to build our chess engine 🤔.. Here is the trick, we limit the search tree to maximum feasible depth and then evaluate the board state using some heuristic techniques. This way we might not get the winning move but we can get the possible optimal move.
Now, as we have understood the working mechanism, we can start implementing it. The implementation can be divided into three parts- search algorithm, evaluation matrix, and connecting engine to bot API. I have used python, you can try it in c/c++ to improve the performance.
- Search Algorithm:
It is the core block for every chess engine and thus it has a high impact on the final performance. A good search algorithm can make a huge difference. One can read plenty of things from CPW’s search page. I used alpha-beta pruning search algorithm, an improvisation of minmax algorithm. Using alpha-beta pruning we can skip the unwanted searches as shown in fig below.
Python chess library made all the chess operations super easy. It allowed me to only focus on the algorithm part thanks to Niklas Fiekas. Below code snippet is an implementation of alpha-beta pruning. (project git link is at the end).
def alphabeta(board,depth,maximize,alph,bet):
if time.time()-start_time>=Time:
return 0.0
if board.is_checkmate():
return -float('inf') if maximize else float('inf')
if board.can_claim_draw() or board.is_stalemate():
return 0.0
if depth==0:
return quinscence_search(board,1,maximize,alp,bet)
moves=list(board.legal_moves)
if maximize:
score = -float('inf')
for move in moves:
board.push(move)
score=max(alphabeta(board,depth-1,not maximize,alp,bet),score)
alp=max(score,alp)
board.pop()
if alp>bet:
break
return score
else:
score=float('inf')
for move in moves:
board.push(move)
score=min(alphabeta(board,depth-1,not maximize,alp,bet),score)
bet=min(score,bet)
board.pop()
if bet<alp:
break
return scoreThe speed of alpha-beta pruning can be increased by applying move ordering. Move ordering is a technique, where before applying a search algorithm, all the possible moves are arranged in order using a simple evaluation technique such that the most promising moves are followed by the worst. So when we apply alpha-beta pruning, it will explore promising nodes first and hence can cut off unwanted branches early.
Fixed depth search algorithms can cause horizon effect, especially during captures, i.e If the last explored node (leaf of search tree) is a capture-move then our algorithm would consider it as a rewarding move but, in general such offensive moves are followed by reactive offensive move. And as our search algorithm is constrained by its depth, it doesn’t consider subsequent moves and can cause serious damage. Here comes the Quinscence search, used to extend search at the unstable node, until we get the stable/quiet node.
2. Evaluation Matrix
This is the process where we quantify the board state i.e by evaluation function you can measure how better your position in the game. This function is necessary to evaluate the leaves (end nodes) of search algorithm. There are many evaluation methods including one using neural networks, but being a beginner I used Michniewski’s simplified evaluation function.
As its name suggests, it is very naive and easy to implement evaluation method. In this method, points are awarded to the types of pieces you have, plus the positional advantage of each piece.
Note: I have used different values for piece values as well as positional scores.
In short, board value= piece value + positional value at each square.
3. Link the chess engine to Lichess bot API (optional)
For communicating chess engine to any user interface we generally use UCI protocol. To link the chess engine to lichess API, you need to open a bot account at lichess.org then install lichess-bot - it is the bridge between your engine to lichess API. Thats it!!
You can play with your bot now and try to beat him 🤗
For more detailed implementation, please check my github repo
