Created by John - Summer 2025
Heavily Frameworked by lichess-bot
which is a free bridge between the Lichess Bot API
and chess engines. Much of the provided code allows for me to run the engines on
lichess with minimal setup and with much of the UCI (communication between the server
and computers) taken care of. My code is in the /engines folder. My code makes use of
the python-chess package for board
representation and the number of functions it provides.
The /engines folder contains the iterations of chess engines I made. Since a lot of the
concepts build on each other, I chose to make iterative versions of the engine through
the process. The implemented versions right now are described below.
- RandomEngine: Picks a random legal move (used to set up the other technology like the lichess bootstrapping and python-chess).
- MinimaxEngine: Implements the minimax algorithm with a basic envaluation function based only on piece value.
- MinimaxOptimizedEngine: Implements the minimax algorithm with alpha-beta pruning for speed with a more complex evaluation function utilizing piece value and heuristic piece placement.
- MinimaxQuiescenceEngine: Implements previous version of minimax with alpha-beta pruning with quiescence search.
- MinimaxMoveOrderingEngine: Implement pervious version of quiescence search with move ordering changes for higher pruning rates.
The concepts behind the engines are further explored in the Algorithms/Ideas section.
You can run one version of these engines at a time. To run a specific engine, change the engine: name: in the config.yml file to the name of the version you want to run. The engine classes are instantiated in the homemade.py file (at the bottom) so if you would like to change things like the depth you can change it from that file (since it is a parameter passed in when creating the bot). Otherwise, all of the code for the bots are in the /engines folder under their specific subfolder.
Note that you need to create a bot account and give the oauth token at the top of the config.yml file.
To run the bot, make sure you are in the virtual environment and have all requirements installed.
source venv/bin/activate to start virtual environment and deactivate to stop it.
pip install -r requirements.txt with the virtual environment running to install needed dependencies.
Then run python lichess-bot.py to start the engine.
We can consider the minimax algorithm in 2 main phases.
- First, we need to build to tree of possible moves.
- Second, we need to evaluate back up the tree, alternating which player we are maximizing for.
Because we evaluate in this alternating fashion up the tree (minimax refers to the fact that at one level you will try to maximize the evaluation and on the next you will minimize), the baked in assumption is that the opponent will make the best move possible for themselves. Lets go through a quick example.
This is our starting position. We will show the algorithm that can be used to determine what the chess engine, as white, should play.
We first build the next level of the tree of possible moves by looking at both of the possible knight moves, to take the bishop or to take the queen.
Then we can go one step further and make the possible responses black has in each of the 2 positions. When white takes the bishop, the queen can move to many squares, we only consider the recapture of the knight and the move one square down for simplicity. When white takes the queen, black can move their bishop to the bottom left square or to the middle of the miniboard.
Now that we have created the possible move tree, we should evaluate each of the ending positions. We will use a simple evaluation function that only considers the piece values (shown above). Negative/lower values are better for black and positive/higher values are better for white.
After evaluating the possible positions we can go back up the tree and do the minimax comparisions.
At the middle level we are trying to minimze the value (because it would be black to move). On the left side of the tree we compare the 2 positions and see that the one with an evaluation of -9 is better for black than the position with an evaluation of -6, so the -9 gets passed up the tree. On the right side of the tree we compare the 2 positions, and because we see an evaluation of 0 for both, we just pass up the 0 from the first position we evaluated.
Now at the top level we try to maximize the score and we compare the -9 from the left tree and 0 from the right tree. Because we want the better score for white we choose the 0 from the right tree and that is how the engine decides to capture the queen.
A complement to the minimax algorithm is alpha-beta pruning. With alpha-beta pruning, we can eliminate some evaluations that occur at the leaves of the tree during minimax. The image below from GeeksForGeeks demonstrates a case where we can skip an evaluation at a leaf node because no matter what the value is, the decisions being made further up the tree will not change.
Consider a similar process to the minimax as discussed above. In the actual implementation of a minimax algorithm, we generally make recursive calls which means that from a node (in this case a chess position) we call minimax on the left tree and then the right tree (or however many more trees there are, there are usually more than 2 possible moves a player can make on their turn in any given chess position). That means that in information from previous trees are known while evaluating the right trees so we can pass in information from above to allow the lower level nodes to know when to skip.
For this example, lets consider the left branch of A. At node B we evaluate node D before node E. At node
D we do the evaluation to the left position which yiels 3 before evaluating the right child which yields 5. We
then make the evaluation at D for the maximum of its branches which chooses 5. We then go back up to node B and
evaluate the right child knowing that the left child's (D) value is 5. At E we evaluate the left child and get
6 and at this point we know we can skip the evaluation of the right child. Consider:
- If the right child of
Eis greater than 6, thenEwill pick it and pass it up toB. SinceBwill pick the minimum from its 2 childrenDandE, it will pick 5 from the left childD. - If the right child of
Eis less than 6, thenEwill pick the 6 from its left child since atEwe maximize the value.
Because in both cases we don't end up caring about the value of E's right child, we can skip the evaluation function
and save our algorithm some time.
Evaluation functions also provide their own challenge and opportunity for improvement. These have to be heursitic in their minimax usage because the minimax tree grows so quickly that we have to stop evaluating before we reach an ending state (either player winning or a draw). The minimax example used simple piece values. The more complex versions of the engines use a more complex evaluation function that considers the piece values in addition to the piece placements (shown below is an example for the pawn tables, notice how a pawn on the opponents second to last rank is worth more, because it is close to being promoted). We have a table of heuristic value adjustments for each piece type.
Quiescence search aims to aliviate the horizon problem. Notice the flat bottom of the tree's shown in the minimax and alpha-beta pruning examples. What if the very next move was the one that was critical to the variation (a critical recapture or check or checkmate). We have to set a depth with normal minimax because otherwise it tries to evaluate too many positions so we force the algorithm to have this flat bottom.
Quiescence search refers to allowing the engine to continue evaluating in positions where critical moves are likely. In practice (at least in these engines) it makes sense to continue evaluating captures and checks in a position, even after the depth has been hit on the minimax portion of the evaluation. This adds a relatively small amount of additional time for computation to not miss any critical "very next moves" that minimax alone cannot recognize the importance of.
We've already shown how alpha-beta pruning allows our engine to avoid wasting time on evaluations of positions that cannot change the outcome of the algorithm. We can increase the rate of pruned positinos by considering the order that positions are evaluated in. When better positions come earlier in the evaluation, we prune more branches. Obviously we can't know which moves and positions are better while evaluating (because that is what we are trying to find!), but we can take a heursitic approach and assume that captures and checks are on average better than moves that aren't captures and checks. By moving captures and checks to be first in our generated list of possible moves to check, we prune more positions and save more time with the help of alpha-beta pruning.
- Instead of making a computer designed for maximum strength, try to make a human understandable one (like Allie)
- Make neural network and reinforcement learning based bots
- Making a chess engine adapt or train to be better against humans rather than just play the best moves (an exploitative strategy instead of just best which might not always be the best against humans)
- Bot trains on human mistakes and it focuses on your mistakes in games to force those motifs
- Testing llms on chess like Nate Silver did for poker (maybe a larger scale study)
- Evaluating where computers play worst (what types of positions)
- Bots to maximize interest in the game to keep people playing for as long as possible (an engagement based bot instead of strength based)
- LLM that walks with you to analyze a game
- Make a bot to maximize for variants (3 check, antichess)
- https://news.asu.edu/20250116-science-and-technology-brilliant-move-mathematicians-latest-gambit-new-chess-ai
- https://arxiv.org/pdf/2402.04494
- https://hkopp.github.io/2020/01/chess-engine-design
- https://medium.com/data-science/dissecting-stockfish-part-1-in-depth-look-at-a-chess-engine-7fddd1d83579, https://medium.com/data-science/dissecting-stockfish-part-2-in-depth-look-at-a-chess-engine-2643cdc35c9a, https://medium.com/data-science/dissecting-stockfish-part-3-in-depth-look-at-a-chess-engine-51b59e532bb4
- https://www.chessprogramming.org/Main_Page
- https://github.com/Kyle-L/Simple-Chess-Engine
- https://fivethirtyeight.com/features/rage-against-the-machines/
- https://www.freecodecamp.org/news/simple-chess-ai-step-by-step-1d55a9266977/
- https://chessengines.super.site/
- https://byanofsky.com/2017/07/06/building-a-simple-chess-ai/
- https://healeycodes.com/building-my-own-chess-engine
- https://www.maiachess.com/