Creating a Chess AI

View my Chess AI in action here

Chess is one of the most popular games on the planet. Many people have tried to create a chess AI, that can play chess at a high level. The best attempt so far was AlphaZero by Google. The software managed to learn how to play chess in a number of hours, and defeat some of the best computer players such as Stockfish.

During my free time these university holidays, I thought it would be a great idea to create my own chess AI. While I certainly wouldn’t be able to reach the levels of Google and Stockfish in my short time available, it seemed like a decent challenge.

Creating a chess AI in the conventional manner essentially means creating a list of all possible moves, and choosing the best move for the player. This is basically what chess algorithms tend to do, but they also have many different tricks that are applied to make this process much more efficient. Several of these were applied to my algorithm such as, the evaluation function, min-max and alpha-beta pruning.

Evaluation Function 🔗︎

The evaluation function is how the program views the board. For my program I used a very simple method for this calculation. The program finds all pieces on the board, and gives them a certain value, based on their importance. For example, a Queen is worth 1000 points while a Pawn is only worth 100. The sum of all of the current players pieces, minus those of the opponent create a value for the board. The goal of the program is to increase the value of the board by taking opponents pieces and keeping its own pieces alive.

Min-Max Algorithm 🔗︎

When maximising the value of the board, it’s important that the best option is taken for the long term. For example there is no point taking a Pawn with your Queen, only to lose your Queen immediately after. Therefore the min-max algorithm is used. This algorithm looks at possible futures of the board, and finds the board that maximises the worst possible board. This helps to prevent the program from making bad decisions.

Alpha-Beta Pruning 🔗︎

Alpha-Beta pruning is a very useful tool, it means that there are many branches of the search tree that do not need to be looked at. For example, if the min-max of one part of the tree is greater than the maximum of another part, then there is no way that the new part of the tree is better than the min-max has already found. This means that this part of the tree does not need to be searched, and can be skipped.

Summary 🔗︎

There are many ways to improve this algorithm. All of these improvements result in the algorithm being able to search further into the tree of possible moves. Other techniques to be used include:

  • A hash table for your evaluations
  • Move ordering.
  • Iterative deepening
  • Quiescence search

There are even ways to include machine learning and neural networks into the algorithm.

These parts may be included in my chess game, feel free to check back to see if I have made any progress!

The sources below were a very big help in learning about this topic:

Building a Simple Chess AI