As a semester work at university, a fellow student and I had to write a paper about implementing a chess computer in Python as well as implementing it afterwards.
Note: You can find the paper as well as the Jupyter notebook to play against the chess computer on GitHub. However, both are written and documented in German. The source code is in English, though.
The chess computer consists of two major components and three enhancements. Furthermore, the game play was implemented using the Python-Chess package.
The first component is the evaluation heuristic. It is a simple one invented by Tomasz Michniewski. The so called simple evaluation heuristic consists of two parts: Simple piece values and piece-squared tables.
The piece values are the values the pieces have by simply existing. The easiest metric to see, which player is in front, is to count the pieces' values and compare it to the enemy's one. However, it is not only important how many pieces you have, but where they are located. This is where piece-squared tables come into play. They give bonuses for good positions and sanction bad positions.
I do not want to into detail how these values were examined. Checkout the paper to find out more.
The second component is Alpha-Beta Pruning. A computer cannot evaluate all possible positions. Okay, maybe a big one with enough computational power and memory can do this, but not a computer everyone has at home. So the idea is to cut all branches of the game tree that seem not worth to evaluate them. This way, the computer is able to reduce the game tree and only evaluates the important moves and positions.
Move ordering is the first enhancement of Alpha-Beta Pruning. Instead of randomly choose a position or move from the list of possible ones and evaluate it, the computer sorts them beforehand. The good news: Evaluating good moves and positions first, the Alpha-Beta Pruning can cut more branches and therefore can evaluate more positions in advance.
The second enhancement of Alpha-Beta Pruning is quiescence search. Let's suppose the computer reaches depth 8 and wants to evaluate the position, return everything and decide on the best move. What if the position is not a quite position? A quite position is a position, where no player can capture another player's piece. The idea is to check whether a position is a quite position and if not, go deeper into that branch.
This way, the computer is able to make even better decisions, even though it might loose one additional depth level.
The third enhancement we implemented are transposition tables.
In chess there are many transpositions.
Assume that player A can make a a1 on which the player B reacts with b1.
Player A now can make an independent move a2 where player B reacts with b2.
The two resulting sequences [a1, b1, a2, b2] and [a2, b2, a1, b1] are transpositions leading to the same position.
If the first sequence was already evaluated, it is good to store the result in a hash table. When the second sequence needs to be evaluated, the already computed result can be used instead of re-calculating it. This safes a lot of time!
Due to the time, hard- and software constraints the final chess computer has (only) an approximate elo value of 1400-1500. Implementing certain parts in C or Cython as well as using multithreading or multiprocessing for the searches would increase the computer's performance. However, this was not allowed under the given circumstances.
Again, if you are interested in playing against it or just viewing our solution, checkout the corresponding GitHub repository.