The Legendary Grob Bot
The bot is made up of two major components: board evaluation and move searching.
Features
Minimax Search
Minmax is a decision rule for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain.
Alpha-beta pruning
The Alpha-Beta pruning algorithm is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of the game tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move.
Move ordering
For the alpha-beta algorithm to perform well, the best moves need to be searched first, so we guess an approximate evaluation of a move and sort the order we search the moves.
"Quiescence" search
Most chess programs, at the end of the main search perform a more limited quiescence search, containing fewer moves. The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made. This search is needed to avoid the horizon effect. Simply stopping your search when you reach the desired depth and then evaluate, is very dangerous. Consider the situation where the last move you consider is QxP. If you stop there and evaluate, you might think that you have won a pawn. But what if you were to search one move deeper and find that the next move is PxQ? You didn't win a pawn, you actually lost a queen. Hence the need to make sure that you are evaluating only quiescent (quiet) positions.
Transposition Tables
A Transposition Table is a database that stores results of previously performed searches. It is a way to greatly reduce the search space of a chess tree with little negative impact.
Positional Piece Bonuses
Piece-Square Tables, a simple way to assign values to specific pieces on specific squares. A table is created for each piece of each color, and values assigned to each square. This scheme is fast, since the evaluation term from the piece square tables can be incrementally updated as moves are made and unmade in the search tree.
Smart Endgame Evaluation
To win at endgames, our bot prioritizes two things in the endgame:
- push opponent king towards edge of the board
- moves kings closer to each other
This is because most checkmates with few pieces happen on the edge of the board.
Opening book (includes Bongcloud Rapid Response Technology™)
We store a small sample of grandmaster games and if there is a response to an opening move we do it blindly.
If the opponent plays the
bongcloud, we
detect it with our Bongcloud Rapid Response Technology™ (BRRT) and respectfully
respond with 2. Ke2 Ke7 3. Ke1 Ke8.
Stuff we didn't get to
- Zobrist hashing
- Pawn Structure
- Partial Move ordering
- Bishop Pair / choosing the correct bishop color
- Optimizing code to run faster
Built With
- jupyter
- python-chess
Log in or sign up for Devpost to join the conversation.