DNN-Guided-MiniMax-Chess

My chess algorithm uses an implementation of the MiniMax algorithm guided by an ensemble model containing a deep neural network and a custom heuristic estimate to guide the agent’s decisions at each move, allowing it to play a competent game of chess against a user inside a Discord server environment.

Full paper on DNN functionality

Graphical Interface

The script uses Discord and its custom emoji system as a graphical interface to represent the board so that we could test the bot in a collaborative environment. The program first generates an ASCII representation of the board in the terminal using the python-chess module, then uses a conversion function and a set of 26 custom emojis inside a Discord server to print out the entire board using those custom emojis. Players can then interact with the bot, and play the AI using the .chess command. It will then edit its initial message to reflect updates in the board state and list of possible moves.

Command List

To begin a game you tell the program what gamemode you want to play:

• .chess 1: Starts a manual chess game, in which the moves for both sides are manual. Effective at playing other users in the discord server without any AI interference.
• .chess 2 Starts a chess game against the AI, in which the user plays white and the AI plays black.
• .chess 3 Starts a game where the AI plays both sides against itself, making moves until the game is completed or aborted. All other commands are also preceded by the .chess command, which directs your next argument into the program.
• undo: undoes the last move and reverts the board to the previous position and the previous players turn
• reset: resets the game board and restarts the program, taking the player back to gamemode selection
• exit or quit: exits the program
• print: prints the current state of the game board

You can tell the program what move to make by typing in one of the provided options it gives you for possible moves, this is case sensitive.

MiniMax

My agent uses an implementation of the Minimax algorithm to make decisions about where to move and how to play out the game. To calculate the next move we populate the MiniMax tree with the values of the heuristic of each move and determining the best possible move for each turn. The AI and heuristic algorithm is built on top of the python-chess module, which is already equipped with all of the functionality needed to run a fully functional chess board inside of the code.

https://python-chess.readthedocs.io/en/latest/

This allows the script to easily get a list of possible moves from any position on the board, and test different board positions inside of MiniMax through a standalone chess object. MiniMax is configured to take the current position and whose turn it is as inputs, it then generates the list of possible moves, and iterates through them calling itself recursively for every possible board position, pruning off unnecessary moves with the alpha-beta pruning method. In order to make the MiniMax algorithm more efficient and help it prune more branches, MiniMax also uses a move ordering method that orders the evaluated moves by their evaluation score, exploring better branches first. By testing these possibilities first, we increase the number of branches MiniMax is able to prune on average, decreasing the runtime. Minimax explores branches in an iterative deepening pattern, exploring as deep as it can in the allotted runtime (5s default).

Custom Heuristic Calculations

The heuristic algorithms score of the board that MiniMax uses to choose moves is determined by a weighted map of piece values. The map is first populated by the relative piece values. For example, in chess the Queen is worth 9 points, Rook’s are worth 5, Knights and Bishops 3, and Pawns 1. The heuristic algorithm will use these scores to add up the total material score for each side (out of 39), and the difference between those scores represents a large portion of the heuristic weighting of a board position for the bot. This map is then weighted by several additional factors, the first of which is to observe where each piece is on the board. The algorithm will favor pieces that are more developed on the board and placed in a more advantageous position. For a pawn this means the closer it is to the opponent's end of the board, the better the modifier. For a Knight, we favored pieces placed closer to the center of the board, so they can reach more squares. Each piece has a respective piece map that can be found in the positionMap.py file of the code repository. These maps were custom made for our project but were inspired by the maps found in similar algorithms from the chessprogramming.com wiki.

https://www.chessprogramming.org/Simplified_Evaluation_Function#Piece-Square_Tables

The map is also weighted by whether a piece is under attack or not. This attack factor is defined by calculating the total trade values of opponent pieces attacking it from the number of friendly pieces defending it. If this attack factor is negative (trading the piece would result in a loss of material) we know the piece is under attack and the 20% heuristic weight for that piece gets reduced by 50%. Additionally, all other attacks that the piece is creating get nullified if the piece is vulnerable, as it will likely be captured the next turn anyways before it has a chance to attack if defensive options aren’t taken. Comparing weighted piece values is generally a pretty good way of seeing who is winning in a position, so that makes up the majority of our heuristic element. The last piece of the custom heuristic is to check whether either side has castled, and whether they still have castling rights, as these are generally advantagous positions. MiniMax uses an iterative deepening tree, which in the current implementation caps out at a 5 second computation time. The tree stores a hasmap of calculated positions to avoid recalcuating positions reacehd through different move combinations on the board, and typically reaches a depth of 4-6 moves depending on the board complexity. I did also develop and experiment with a version of MiniMax that multithreads the top layer of the calculation tree to all of the available CPU threads available in the machine its hosted on, which on my machine reduces computation times by about 90%, allowing for an additional layer and search to a depth of four. Unfortunately this multithreaded version of the MiniMax algorithm is unstable when used with the current Discord representation of the bot, and so is disabled by default.

Deep Neural Network Layer

The network architecture consisted of a four-layer Linear Neural Network. Node representation remained uniform throughout the input and hidden layers. Each layer consisted of 808 nodes which coincided with the encoded 808 binary input from the dataset used. The binary input was the encoded FEN representation of the chess board. ReLU activation functions were utilized for each hidden layer resulting in 3 layers of ReLU activation functions. No activation function was employed for our output as the goal was to keep the networks prediction within the correct range of [-15, 15] rather then manipulating our raw prediction into the ranges of [-1, 1] or [0,1]. More detail about the setup and testing of the Neural Network can be found in the paper at the top of this document

Performance and Future Improvements

Testing our ensemble model on chess.com we were able to assign a rough chess ELO rating of $600-800$ to our engine, and observe its game-play style. It performs well during the opening and middle stages of the game, with the manual heuristic checks preventing poor moves in which our agent would lose pieces or give up important board positions, and the deep learning model helping to weight common effective human chess strategies higher and perform more complex sequences of moves. This style of play helps the agent maintain a reasonable board position into the middle-game and appear as though it can keep up with quite competent players. This quickly falls apart in the endgame however, as it's manual heuristic is not complex enough to classify detailed endgame positions, in which positioning is significantly more important. The deep learning model also did not help significantly with this stage, as it did not effectively learn checkmating patterns and incentives useful to help close out close games in the ending stages of the game. These late game weaknesses led to losses against pretty much any competent chess player, and highlighted the most glaring weaknesses of the models chosen for this engine. It is also worth noting that the endgame weaknesses of our ensemble method are pronounced even further when only the manual heuristic is used, but that the opening and early game are helped significantly by this ensemble configuration. One of the future directions I would like to explore is how to make the model reliable in these more nuanced game states. Much research has been conducted on reinforcement learning and deep Q-networks and may prove to be a potential solution to our models reliability issue. I recently discovered that Double Q-Learning can rid the bias of the Q value estimator by using an opposite estimator network resulting in further stabilizing the model. Ultimately I have run out of time to work on this project for now, but I may come back to it in the future with some of these improvments.