Chess Engines

Ever since its appearance in India around the 6th century CE , humans have dominated the game of chess. However, in recent years, computers have become an unstoppable force in the chess scene, where even the top players in the world can not even hope to come near them.  Though this was not always the case. As early as the 1980s, many would laugh at the thought of a computer beating a human. But in 1997, the chess computer Deep Blue, developed by IBM, beat reigning chess world champion at the time, Garry Kasparov. So how did computers achieve this seemingly impossible feat ?

​

What is Combinatorial Game Theory (CGT) ?

Game Theory (GT) is generally applied to study and analyze games or situations that require chance or where you have impartial knowledge of the states involved. On the other hand, Combinatorial Game Theory(CGT) is the study of the best strategies and moves given that players involved have a perfect knowledge of the position at hand. CGT and GT may seem like the same thing, however there is an important distinction between the two. In Game Theory, players are assumed to be moving simultaneously without any knowledge of the board or situation at hand. However, in a game like chess, both players have a clear view of the board and each move is made in sequence and not simultaneously. Hence we apply Combinatorial Game Theory to chess.

 

What is a Chess Engine?

A chess engine is a sophisticated software program that can play chess and analyze different moves. It does several evaluations and searches before reaching the best possible solution. A chess engine is usually a back end with a command-line interface with no graphics.  As time has gone on, programming techniques have improved, enabling the engines to be more selective in the lines that they analyze and to acquire a better positional understanding. 

 

How does a Chess Engine work?

When the software program is evaluating a position during the game, it calculates all different possible and legal moves and finds the most optimal move to make. In Combinatorial Game Theory, these moves are represented as a "game tree"

 

What is a Game Tree ?

A game tree is essentially a road map starting at the initial position and containing all possible moves from each position. For example in a game of tic-tac-toe. The first level of the tree would be the empty game mat. It would then branch out into 9 different levels or Plies because there are 9 different ways for player one to draw an X. After player one makes a move, player 2 can respond in 8 different ways. After that there are seven ways for player one to respond, etc. The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes, with our technology in the 21st century it is easy for computers to handle and sort this much data . In comparison, there are over 10^40 estimated possible moves in a chess game (legal moves, that is). Hence making it impossible to find every possible move and outcome with our current technology, but the computer can still see enough moves to outclass any human. However a lot of time has passed since Deep Blue was created, our most powerful engine currently is Stockfish 15 and can see an approximately 70 million plies per second. If we were in the 70s and 80s many would have scoffed at the thought, then again the idea that a computer could beat a human was also ridiculed. 

​

Endgame Tables

As time has gone by, some chess engines have started to use endgame tables instead of game trees when there are less pieces on the board (7 pieces or fewer) as it requires less resources and time to sift through. End game tables are important because instead of calculating the best move for a position, it can just cross check with a pre-calculated position to give the best move for the position. 

​

Final Thoughts 

Even though we are well past the time of humans vs computers being a fair match up, engineers are still innovating new algorithms allowing chess computers to see even farther into the game tree. Game Theory is often associated with only games; however, Game trees and tables don't only apply to games. In warfare, Game Trees are used to simulate where the most optimal resource placement is. In Politics Game Theory is used to predict the possibilities of what might happen if a specific law is passed. In conclusion Game Theory has many viable uses in the real world, and chess is only one of them.