Creating a Chess Engine — Sepentia

As AI is a buzzword nowadays, let’s talk mathematics and implement some real positional statistics and some algorithms that you have used in CP but never in real life. Ever thought about how Samay Raina’s chess.com bot plays against you at 1800 ElO? As Most of your answers will be: we will collect all his game data on how he plays and then train a model that replicates his moves but I mean how you can train something that has 121 million possibilities maybe Chess.com personalise some of his blunders in his bot but that’s not how it works.

So, when I was watching Nakamura vs Pragg ( 98.8 vs 98.3 ) I just out of curiosity got a question about how these accuracies are calculated. answer: chess engine ( Stockfish ).

How do they work?

Chess Engine uses a very simple and standard algorithm minimax ( https://leetcode.com/problems/can-i-win/description/ ) just in case you are a leetcode grinder here’s a task for you & you know the drill moreover, minimax is not an optimal algorithm to calculate the best move on the square board of 64 blocks where positional statistics changes after every move.

So here’s my experience of coding a Chess Engine (Sepentia) of 1500 ElO at a depth of 4 for non-chess players: ELO is a rating stat, and depth is the number of moves you calculate ahead in the game tree to evaluate possible moves.

The game tree shows all the possible moves that White can make from a particular position and the algo’s evaluation of each position that results from those moves. According to the algorithm best move for white is 3c which leads to +1.4 pawn in white’s material scoring

First, we will check all the valid moves available on the chessboard then we use the minimax algorithm to explore each level of the possible game tree where each level represents a player’s turn, and each node represents a possible board position after a move. The main objective of the minimax algorithm is to evaluate maximising moves for your turn and evaluating minimising moves for the opponent ( for now, consider this for material on the board algo will always try to have your maximum material on the chessboard for you and minimum for the opponent ). The main problem with the minimax algorithm is its computational complexity, especially where the branching factor (number of possible moves) is high Minimax explores the entire game tree to find the best move which is not optimal because you are lazy(human) and you cannot travel each node.

Here comes the alpha-beta pruning algorithm: When a maximising player finds a move with a value greater than or equal to beta, it means that the opponent has a better move elsewhere. Therefore, the maximising doesn’t need to explore further down this branch. It cuts off the exploration and returns the current best move with value beta.

The image shows a chess decision tree, but not the full picture! Alpha-Beta Pruning helps chess engines explore moves efficiently. Imagine White can make two moves (A & B). If the engine finds Move A leads to a better score (+8) than B (+1) for White, it can ignore the rest of B’s branches. Why? Because White is guaranteed a better outcome with A, no matter what Black plays under B. This pruning saves time by focusing on promising paths.

OK, now we know how a game tree works and how we search inside a game tree but the problem is in chess there’s a huge role of positional scores, pawn structures, centre control, forking and pins all these parameters make a chess engine how are we gonna tackle all this? well, we have some desired data on the internet through which we can make this possible as each piece has a different value as a material and different value on different positions of the chessboard Example:

king = 0 ( you cannot capture king ), Queen = 9, Rook = 5, Bishop = 3, Knight= 3, pawn=1 [these all are material value ).

Positional scores: every piece on the chessboard will have a different position score on 64 blocks based on studies. ex: The value 0.0 represents the lowest score, meaning the worst position for a knight. The values increase as we move towards the centre of the board, indicating better positions example: a knight placed in the centre (rows 2 to 5, columns 2 to 5) would have higher scores compared to those placed on the edges with the highest score, 0.7, is assigned to the centre-most squares (row 3, column 3 to 6) the score gradually decreases as we move away from the centre. The role of these scores in the code is to help evaluate the relative strength of different positions on the board for each type of piece during the algorithm’s decision-making process, these scores are used to prioritize moves that lead to positions with higher scores.

The image shows a positional scoring system used in a chess engine. Each number represents the engine’s evaluation of a position on the board. Positive scores favour White (lighter squares), and negative scores favour Black (darker squares). Higher numbers mean a bigger advantage. For example, +1.4 pawns favour White by over a pawn.

The positional score of a piece reflects its strength based on its position on the board and in chess, certain positions are more advantageous for pieces than others for example, a knight in the centre of the board has more mobility and control over squares than a knight stuck in a corner. Similarly, a rook on an open file has more attacking potential than a rook blocked by pawns by incorporating positional scores into the evaluation function of a chess engine, the engine can make smarter decisions about which moves to prioritize. For instance, the engine might prefer moving a piece to a square where it has better control over the board or can support other pieces more effectively.

Each square shows a score for a specific piece (king, queen, pawn) relative to its position on the board. Positive numbers favour White (upper half of the board), and negative numbers favour Black (lower half). Higher numbers mean a bigger advantage. For instance, a pawn in the centre of the board (e4/d5) might have a score of 0.5, indicating a slight advantage. Conversely, a pawn far from the centre (a3/h7) might score -0.5, a slight disadvantage.

Now let’s understand how the ordering of moves is done and why the ordering of moves is very important for a chess engine to make the decision.

By ordering moves, the engine reduces the search space, focusing on the most promising moves first this pruning of less promising moves makes the search more efficient, allowing the engine to explore deeper and find better moves within a given time frame.

I have divided ordering moves into 2 steps: capture moves and quiet moves.

Capture moves are those moves where a piece captures an opponent’s piece and Quiet moves are those moves where a piece moves to a square without capturing any opponent’s piece. Capture moves are sorted based on the value of the piece being captured higher-valued pieces are prioritized for capture. This is implemented using a lambda function that retrieves the piece value from the piece_score dictionary and sorts the capture moves in descending order of piece value. Quiet moves are sorted based on the value of the target square each square has a positional score that indicates how good it is for a piece to occupy that square the piece_position_scores dictionary stores these positional scores for each piece type on each square of the board and quiet moves are sorted in descending order of the positional score of the target square and evaluating quiet moves based on positional scores helps the engine identify moves that improve the overall position of its pieces this ensures that the engine doesn’t just capture pieces but also aims to improve its position on the board, leading to better long-term prospects and then I’m returning the summation of both the operations.

move ordering is very important let’s calculate this situation: the best move for black here is to do castling to safeguard his king and white has 2 options: trade his queen with black’s queen or play white can open his lines for rook and target black’s king

When evaluating the chessboard, we consider two main factors: intrinsic value and positional value. Intrinsic value is like the importance of a department in a company; it’s how valuable the piece is in isolation. Positional value is akin to the location of the department within the company’s offices. A sales department located in a prime location (like controlling the centre of the board) is more valuable than one in a less desirable area (like trapped in a corner). Checkmate in chess is like one company buying out another. If one company decisively takes over, its value rises while the other company’s value becomes zero. Stalemate, on the other hand, is like a merger negotiation that stalls. No company wins or loses; the value remains static. The total score of the chessboard, calculated by summing up the intrinsic and positional values of all pieces, gives an overall appraisal of the game state. This evaluation is essential for a chess engine’s decision-making process. It helps the engine decide which moves are better than others, formulate long-term strategies, and even determine the order in which moves should be explored during the search process.

To understand move-ordering in deep refer to this article: https://kevinbinz.com/tag/chess/

Now we have an understanding of how the engine works let’s understand how to make it efficient?

Imagine you’re playing chess and you have to decide which move to make where each move you can make leads to another set of possible moves for your opponent, and those moves lead to even more moves, forming a tree-like structure this structure is called a game tree.

Let’s say you’re considering three possible moves, labeled A, B, and C. Each of these moves leads to two possible responses from your opponent, and each of those responses leads to another two possible moves from you, and so on.

A
          /   \
       Opp1  Opp2
      / \     / \
    B1   B2  C1   C2
   / \   / \ / \  / \
   ...   ... ...  ...

the game tree is much larger and deeper, but for this example, we’ll keep it simple. Alpha-Beta Pruning: Imagine you have to explore this entire game tree to find the best move. It would take a lot of time and computational power. This is where alpha-beta pruning comes in. Alpha-beta pruning is a way to reduce the number of nodes explored in the game tree by eliminating branches that can’t possibly lead to a better outcome. Alpha: Represents the best (highest) value found so far by any means along the path for the maximizing player (e.g., white). Beta: Represents the best (lowest) value found so far by any means along the path for the minimizing player (e.g., black). If the algorithm finds a move that is better than the current alpha (for the maximizing player) or beta (for the minimizing player), it updates the alpha or beta accordingly. If, during the exploration of the subtree, the algorithm finds a node where the beta of the minimizing player becomes less than or equal to the alpha of the maximizing player, it knows that the maximizing player won’t choose this path because the minimizing player has a better option elsewhere. So, the algorithm prunes (cuts off) this branch and doesn’t explore it further.

In the context of game trees, depth refers to how many moves ahead the algorithm is exploring. Each level of depth represents a move by one player (e.g., white), followed by a response by the opponent (e.g., black).

Depth 0 (Initial Board)
             /   \
    Depth 1     Depth 1
    (White)      (Black)
      / \          / \
 Depth 2 Depth 2 Depth 2 Depth 2
(White) (Black) (White) (Black)
  ...     ...      ...     ...

In this tree, the root node represents the initial board position.
Each subsequent level of nodes represents the possible moves by each player.
The depth of the tree indicates how many moves ahead the algorithm is exploring.

How we are achieving depth?

Using recursion ( yeah, you got it if there’s a recursion there must be a problem with time and memory hold on we will sort this later) for now let’s understand recursive calls in this engine. The depth of the game tree corresponds to the recursion depth of the algorithm and recursive calls continue until a stopping condition is met, such as reaching the desired depth or encountering a terminal node (checkmate) and more importantly recursive calls allow the algorithm to evaluate positions at different depths, considering the moves of both players and after exploring a branch of the tree, recursive calls backtrack to explore other branches this backtracking process effectively explores the entire tree up to the specified depth.

The code uses recursion to explore chess moves. The function checks each move (branch), then calls itself for the opponent’s replies (sub-branches). It keeps track of the best score found so far. Alpha-Beta pruning helps avoid exploring branches that won’t lead to a better outcome, searching faster.

Now you must say “Hehe, just increase the recursive calls, right? Boost the depth and the engine will get better? Let me ask you something: ‘It’s just money, right? Tell the government to print more and poverty will be eradicated!”

Let’s understand why NOT.

As the depth of the game tree increases, the number of nodes explored and the computational power required also increase exponentially this has significant effects on both memory and CPU power When we explore additional levels of depth, the number of nodes in the tree grows exponentially and more memory is required to store information about each node, including board positions, scores, and move sequences and deeper searches require more memory to hold the additional nodes, potentially leading to memory overflow or excessive memory consumption which ultimately leads to more time.

Here this line comes in “Yeah, you got it if there’s a recursion there must be a problem with time and memory hold on we will sort this later”

For now let’s understand how I’m handling memory and computational resources to make my chess engine more fast and accurate Using a Transposition table is the most crucial step I choose to tackle this problem:

A transposition table is essentially a cache that stores previously computed positions and their evaluations it’s like a memory bank that remembers positions encountered during the search. Let’s understand how it works and how it is helping my algo: Each position in the game is hashed to create a unique identifier and this hash serves as the key to store and retrieve information about the position in the transposition table when a position is evaluated during the search, its evaluation value, depth, and other relevant information are stored in the transposition table whereas this information is associated with the hashed position.

there are 2 branches one is often visited and one is newly visited so as you are seeing that in often visited branches V:600 and W:300 is already evaluated so we stored these node info in the transposition table and when we visited the new branch and we had to calculate the same position that is already calculated we simply used the node info from transposition table this helped us avoid re-evaluation of position which saved us time and memory

Before evaluating a position, the algorithm checks if it has already been evaluated and stored in the transposition table and if the position is found in the table and its depth is sufficient, the algorithm can use the stored evaluation value instead of re-evaluating the position and if the stored depth is less than the current depth, the information may not be reliable, and the position may need to be re-evaluated. During deep searches, many positions are revisited due to branching in the game tree and the transposition table helps avoid re-evaluating these positions. With the transposition table, the algorithm can safely increase the depth of the search without running out of memory even with limited memory resources, the table ensures that previously explored positions are available for reference.

Gaurav, We tackled the memory but how we are managing the time you may have saved memory but what about time?

OK, let’s understand it with an analogy: Imagine you’re building a puzzle, and each friend helps with a different section. The depth of the task represents its complexity, like adding more layers to the puzzle. Recursive calls break down complex tasks into smaller parts, just as you might divide a puzzle into smaller sections to solve them. As depth increases, so does the demand for memory and processing power.

Here multiprocessing helps by distributing the workload across multiple CPU cores, allowing tasks to be completed faster and more efficiently.

By far you have got an answer of using multiprocessing let’s understand how it gonna help Sepentia: In Sepentia, the search process involves exploring possible moves and counter-moves where this search can be broken down into independent tasks that can be executed simultaneously.

While one process explores a particular branch, other processes can generate moves for subsequent branches, thus overlapping computation and improving efficiency which helps to process more positions per second.

I also tried to use GPU for achieving parallelism but failed to fight with the architecture of my Mac here’s a intuition on how GPU can help to make Sepentia better : GPUs are highly parallel processors that excel at performing many computations simultaneously by offloading certain computational tasks to GPUs, Sepentia can achieve even greater performance gains, especially in tasks like evaluating positions and performing deep searches.

Benchmark: 1500 ELO at depth 4 (depth can be increased or decreased manually according to your CPU cores and Performance)

Benchmarking Tool: Stockfish 11 lite

Github: https://github.com/EuclidStellar/Sepentia-ChessEngine

LinkedIn Post : https://www.linkedin.com/feed/update/urn:li:activity:7196593217780285442/

Just adding an image of when Sepentia defeated the MrBeast bot on chess.com just in case he replies to this medium article.