In the August of 2022 I was working at a summer camp in New Hampshire. In that time I decided to undertake the challenge of writing a chess engine from scratch in Python by the end of the summer. Apart from the graphics library (that I still had a file for from my intro CS course) this entire project was/is written using only basic python. This meant that I had to first program a game of chess, visuals and rules, and then conceive of and code a chess engine. 

This is a project I have revisited a couple times but has been on hold since August 2023. Further progress requires a top to bottom restart for which I currently do not have the time

The current best performing implementation of the chess engine uses a minimax tree with alpha-beta pruning, however, it does this in an iterative manner. Similar to an iterative deepening DFS, the minimax tree is constructed one layer of depth at a time and is repeatedly traversed from the root and expanded to further depths until the allowed resources (time) run out. Unlike an iterative deepening DFS, the resulting tree is stored in memory. Though this may seem to defeat the purpose of iterative deepening, this is done with good reason. This sacrifice, in terms of memory, has the goal of optimizing the order in which the children of a node are visited. After being visited, a node's array of children is sorted from best to worst so the next iteration reaches the best child first. This significantly increases the amount of branches that can be pruned for future deeper iterations to improve performance.

The benefit of the iterative deepening approach is twofold. First, it solves the problem of determining what depth to search at since it will go as far as it can in the time provided. Second, it allows for the optimization of the alpha-beta pruning described above. 

The heuristic function that evaluates leaf nodes uses imbalances in material, development, pawn advancement, and king confinement to quantify the quality of positions. How these different imbalances are weighted is still a work in progress that has proven very difficult to optimize for all stages of a chess game. (it works but could probably work a lot better if some variables were thoroughly tested and optimized)

The final component of the chess engine is a dictionary (HashMap) of evaluated positions. This dictionary has keys made of tuples that store a position and the depth at which the position was evaluated. The values paired with those keys are the position's values. Before a node is expanded or evaluated, the dictionary is checked for that position. If it is present, it has already been evaluated elsewhere in the tree and need not be further expanded or evaluated. This is particularly effective later in the game when the branching factor drops and the depth of the tree increase.

The current iteration (chess 3) is capable of winning against inexperienced players and has beaten chess.com bots rated up to about 800 ELO (which is about that of the average human). This is clearly not close to the desired level of play I hope for it to eventually achieve since my current rating is about 1460 (Sept 2024) and the goal I set myself is for it to beat me consistently.

In its current state, given a limit of about 2 minutes (3000 evaluated positions) per move, the engine struggles to get beyond a depth of 4 in the opening, and beyond a depth of 8 to 10 in basic pawn endgames. This means that it is still rather shortsighted in all stages of the game and struggles to see the benefits of moves that secure long-term advantages. These are issues that could be improved by changing the position evaluator with a lot of hard coded analysis functions, but this approach will not solve the underlying problems with the software. Instead, I believe many of its weaknesses currently lie in issues with the implementation of the algorithm and in limitations of using a hard-coded heuristic function at all.

There are many changes that are either already being worked on, or lie in the near future of the chess program:

I am currently writing "chess 5" which is the 5th version of the chess software and the final version that will be written using Python and the Zelle's graphics library. Future iterations will be implemented using C++ to improve performance and control of memory allocation.

Chess 3 (the current best) was lacking in a variety of ways. Chess 5 is the first iteration that will fully implement the entire game of chess (without ignoring any rule) with the new addition of En-Passant and a variety of drawing conditions that were not implemented in chess 3. Additionally, there will be significant improvements to the separation of front- and back- end and the use multi-threading to prevent the freezing of the interface while the engine is running. 

 In terms of the engine, Chess 5 will feature a plethora of improvements to linear efficiency: The storage, hashing, expansion and cloning of Gamestates are all seeing alterations that should reduce the resources required in move calculation. In terms of the algorithm, there will be experimentation with using aspects of MCTS, especially the tree traversal and UCB1 formula. The second goal is to create an alternative heuristic generator that uses a neural network to determine the potential of a position. My goal is to not rely on a massive preexisting dataset so this generator will be trained on a dataset consisting only of its own games, and retrained, or at least revisited, after each game it plays.

Both Chess 3 and Chess 5 can be found here.