The Brains Behind the Boards: How Chess Engines Think
You feel bored on Chess.com one day, and you decide to watch the Computer Chess Championship, and it suddenly strikes you as to how these chess engines think.
Not all chess engines think the same way, there's actually mainly 5 ways that chess engines think, here's a chart to give a brief overview.
| Algorithm | Pros | Cons |
| Minimax | -Simple and easy to understand | -Computationally expensive |
| -Guarantees optimal play if both players play optimally | -Requires extensive search space | |
| Alpha-Beta Pruning | -Optimises Minimax by pruning unneeded branches, saving computational time | -Still faces issues with deep searches |
| -Can significantly speed up Minimax without largely affecting outcome | -Performance highly depends on move ordering | |
| Monte Carlos Tree Search | -Efficient in large, complex search spaces | -Can be slow to finding the best moves in a chess position |
| -Balances exploration and exploitation | -Requires significant computing power | |
| Deep Reinforcement Learning | -Can play very unique moves, sometimes more human like, or creative | -Requires training for a long time |
| -Can handle highly complex positions | -Black-box nature makes it hard to understand or explain certain decisions |
Minimax:
Minimax builds a tree using every possible chess move up to its programmed depth and then scores each move, and with enough training, it almost guarantees good playing skills, however since it needs to compute a vast number of moves, it is extremely intensive on the computer calculating every singular move, normally DIY chess engines are programmed to a depth of up to around 3. Depth 3 has around 24,500 all the way to 42,875 possible moves. If we double it to a depth of 6 the 24,500 becomes 1.05 billion and 42,875 becomes 1.84 billion. So minimax for high-end chess engine models like Stockfish isn't feasible.
Illustration of how minimax works Credit: https://cs.stanford.edu/people/eroberts/courses/soco/projects/2003-04/intelligent-search/minimax.html
One of the first notable chess engines that used minimax was Mack Hack VI, which was developed by Richard Greenblatt at MIT in 1967. Mack Hack used a depth of 4-5 and the speed was limited by the computer which was a PDP-6. In 1967 it also played in the Boston Amateur Championship winning 2 games and drawing 2. By the end of 1968, it earned a USCF rating of 1529.
Another one that deserves a mention is Chess 4.5 which searched 5 piles deep, the reason why I mention Chess 4.5 is because it won the champion title in the WCCC in 1977.
Along with those two, our beloved Deep Blue also used Minimax, except this time it searches with a depth of 12, and as we all know, in 1997 it beat Kasparov.
And finally, there's one last one, that's still widely used today, Fritz is actually also running on minimax, though it also uses alpha-beta pruning to make it more efficient, we'll get to alpha-beta pruning next. It searches 8-10 piles and is widely used today. However, with modern times it has turned to NNUE, though Fritz might still use minimax with alpha-beta pruning as a backbone.
Alpha-Beta Pruning
Alpha-Beta Pruning isn't a completely separate algorithm entity, rather it's a method that helps optimise minimax by pruning off moves that it believes are not good so it doesn't have to do a full search with moves that aren't good and reduces the computation intensity. However, a weakness is that it could overlook brilliant moves like sacrifices as it might prune off those moves.
An image to demonstrate Alpha-Beta Pruning
Most chess engines that used minimax also used alpha-beta pruning to reduce the intensity of the calculations, like Fritz, Chess 4.5, and Deep Blue. However, before completely switching to NNUE in 2020, Stockfish also used alpha-beta pruning. Now you might be scratching your head wondering what NNUE means, we'll cover that very soon.
Monte Carlos Tree Search(MCTS)
Monte Carlos Tree Search(MCTS) is a similar, but different algorithm compared to alpha-beta pruning. Instead of looking at every singular possible move it looks at the most, or a few of the most promising ones and builds on them using neural nets to guide the simulation while its NNUE gives an evaluation.
An image illustrating MCTS. Credit: https://www.mdpi.com/2076-3417/13/3/1936
Now is also a good time to explain what NNUE is. NNUE stands for Efficiently Updatable Neural Network. The purpose of an NNUE is to evaluate each move using the vast database of data it has been trained with.
Back to MCTS, MCTS is rather a younger algorithm compared to minimax or alpha-beta pruning, because of its computational complexity.
Since our computers nowadays are much more powerful than the ones in the 20th century, we have quite a few that use or have upgraded to MCTS.
AlphaZero is a chess engine that demonstrates the effectiveness of MCTS combined with Deep Reinforced learning, which we'll get to later. AlphaZero beat Stockfish and temporarily held 1st place. After Google accomplished its goals with AlphaZero they decommissioned it.
Since Lc0 used the same methods as AlphaZero it also uses MCTS with Deep Reinforced Learning. Currently standing at 3rd place, although before Torch came down the block it was 2nd trailing behind Stockfish.
After Fritz turned to NNUE it also turned to MCTS with Fat Fritz being developed in 2020 using NNUE MCTS for more power and for it to play chess more effectively, unlike its predecessor Fritz 18 Neuronal, which is still partly using alpha-beta pruning.
A notable mention is the Komodo Dragon, otherwise known as Dragon, although it probably relies on alpha-beta pruning it most likely has certain elements of MCTS inside its code. As you can see from the list of engines most of the top engines have switched to or use an MCTS move searching algorithm, which demonstrates its power and effectiveness of it.
Deep Reinforcement Learning
Deep Reinforcement Learning isn't a specific algorithm, but a way that engines learn, which can and will determine the engine's playing style and also determine how long it will take to train a chess engine. Deep reinforcement learning, instead of feeding information to the engine makes the engine play itself, or another bot, or human to make it learn. Generally, it takes longer to learn with this method since it's trial and error. However, the fruits of going through this method is that it's more creative and plays more human-like.
I've mentioned 2 notable examples that use deep reinforcement learning which are AlphaZero and Lc0.
And that sums up all the primary methods that chess engines use to evaluate and choose their moves. By now you probably are bored out of your mind, but next time you head over to watch the Computer Chess Championship on chess.com appreciate all the thinking they're doing.
