Advertisement
AI Games

How Do Chess Engines Work?

How do chess engines work?

Introduction

You would be forgiven for not thinking of chess as a headline-grabbing sport. However, since the Netflix series “The Queen’s Gambit” became a hit, chess has captured the imaginations of millions. More recently, chess competitions and accusations of cheating have made headlines.

As the sport is dealing with those recent controversies, chess engines are taking advantage of recent advances in technology to make their mark.

Also Read: AI & data-driven Starbucks – Deep Brew

What is a chess engine?

A simple way of thinking of a chess engine is to imagine a combination of chess boards and a powerful computer. The word ‘engine’ describes software programs that are capable of playing and analyzing chess. The engine is the technology behind what you see on the screen. It is the power that searches for and processes potential candidate moves on the board.

As computer technology has taken leaps forward over the past two decades, chess engines have transformed, too.

When were chess engines invented?

Experts believe that chess has been played for almost 2,000 years. Compared to that, the history of chess engines is much shorter. Still, the earliest attempt at creating a chess engine is over 200 years old. That may sound impressive – until you realize that 1796’s “Automaton” was a fake. A leading human player hid inside the so-called engine and played others.

The next milestone in chess engine development took until the early 1950s when codebreaker and programmer Alan Turing developed software that really could play this zero-sum game. Over the following decades, other programmers continued using different command-line interfaces to finetune the concept and improve chess engines until they could beat humans.

One of the most high-profile examples of this is the 1996 and 1997 series of matches between IBM’s supercomputer Deep Blue and Russian chess grandmaster Garry Kasparov. When Deep Blue won the second match of this series of six, the computer made history in the world of chess.

Also Read: AI Search Prediction for Online Dictionaries

How have chess engines affected human play?

Chess engines have raised the game for human players. Ever since chess programs became powerful enough to draw with or even beat human players, they also became training tools. Traditionally, human players have learned and improved their skills by analyzing the moves of their peers. Understanding the strategies applied by grandmasters helped budding players sharpen their game of chess.

Chess engines have allowed human players to accelerate their progress, by adding a different level of understanding and knowledge to the game. Today, one of the main purposes of chess engines is to act as training tools. They allow players at any level to generate ideas and analyze specific chess positions. The idea is to be able to review more options for play in less computing time than humans could on their own.

Source: YouTube

Chess engines become progressively faster thanks to tools like transposition tables that store the results of previous searches. Accessing the results of earlier alpha-beta pruning reduces search time as the transposition table size increases.

Using chess engines to prepare for tournaments can certainly help players up their game and progress through the ranks. However, there is a dark side to the ability to analyze and compare different options so quickly. Chess engines have given rise to cheating in the sport. They have become so powerful that it takes nothing more than a mobile phone and an app to access assistance.

The latest, high-profile cheating scandal in chess has been publicized far beyond chess itself. When newcomer Hans Niemann beat the world’s leading player, Magnus Carlsen, Carlsen accused Niemann of cheating. Niemann had a history of winning illegitimately when playing on chess.com. He was banned from the platform as a consequence. Carlsen, on the other hand, has been at the top of his game for nearly two decades, ever since becoming a grandmaster at the age of 13.

Whilst those recent accusations are still being examined, chess.com has taken steps to tighten up procedures and identify cheaters before they can affect the outcome of important chess games.

The rise of chess engines has created another type of game, too. When playing chess traditionally meant two humans facing each other across a board, spectators can now watch chess engines playing each other. This different kind of battle has its own attraction, and it may give competitors a clue as to which engine can best support the development of their game. 

How does a traditional chess engine work?

All chess engines are based on complex software. Today, the industry distinguishes between two main types of chess engines – traditional and neural network engines. Traditional chess engines have been trained by human players, whereas neural network engines follow algorithms. More about them below.

Despite their differences, most traditional chess engines are focused on doing two things as part of their analysis: they evaluate and search. What does that mean in practice?

During the complex evaluation function, chess engines look at critical positions and consider which one is better. Each engine has its own way of weighting a given position. The software takes into account the material on each side, pawn structure, potential threats, the safety of the king, and more factors. Once its analysis is complete, the engine displays an evaluation – or ‘eval’ – number.

Evaluation numbers are based on the scoring that human chess players normally use. Minor pieces score three points each and pawns are worth one point, for example. Once the engine has accumulated its score, it is shown as an eval number. Seeing a +2 for the white pieces, for example, means that this current position is about two pawns better than the black pieces.

The search part refers to how far ahead a chess engine can look. Traditional engines assess promising moves by layers. Each move is known as a ply as in a 2-ply search. An engine that analyzes 30 plies is looking at 15 white moves and 15 black moves. Even a chess engine searching at a search depth of 20-ply is looking further ahead than most humans can. Some of the more powerful engines can analyze 50-ply deep today.

This search process takes time, although the search time is significantly shorter than comparative human reasoning. Chess engines start by considering all possible moves from a given position. Imagine a tree that branches out ever further. Even after less than a handful of initial moves, that chess tree consists of billions of branches. Assessing billions of positions and moves becomes impractical at this stage, even for the most powerful computers.

To stay in control of their chess tree, engines employ pruning. This is generally known as an alpha-beta algorithm, alpha-beta search, or AB minimax search. The engines simply discard obviously bad moves and develop their search chess tree based on the most promising positions.

Despite not having endless search time, chess engines also conduct a quiescence search, assessing non-winning moves. This is the engine’s attempt at not being caught out by the limits of a fixed-depth search.

The strongest chess engines are driven by the highest levels of CPU processing power. The higher the CPU of chess computers, servers, or phones you are using, the more powerful the engine becomes.

What is a neural network engine, and how is it different?

Neural network (NN) chess engines utilize machine learning (ML), a subfield of artificial intelligence (AI) technology. Rather than being programmed by human chess players, the engines are programmed with powerful search algorithms and then fed with data, aka chess games. They learn from those games without any need for further human input.

The more games a NN chess engine can digest, the more conclusions it can draw, increasing its ability in the process. The machine – or engine – mimics human learning without needing humans to train it. The data supplied to the engines could be derived from grandmaster games. Alternatively, the engine can generate its own data by playing games against itself.

NN chess engines use a method called Monte Carlo tree search (MCTS), selecting their next move based on potential and probable outcomes of different playouts. The easiest way to picture this is to think of the engine quickly playing itself in different matches and selecting the move that has the biggest chance of winning.

Like their traditional counterparts, NN chess engines benefit from powerful CPUs. But even more so, they need strong graphics processing units (GPUs) similar to those used in gaming computers to process neural nets at usable speeds. 

Where can I watch chess engines playing?

Watching present-day chess engines play each other has become a bit of a spectator sport in recent years. Chess.com now runs the Computer Chess Championship (CCC) where fans can follow along as chess engines are battling it out amongst themselves.

 

What are the top chess engines, how do they work, and how do they differ?

If you are keen to find out more about some of the leading modern engines, traditional and neural network based, take a look at the overview below.

Traditional Chess Engines

Here is our selection of seven of the leading traditionally programmed chess engines. 

Komodo

Considered to be the second-strongest chess engine after Stockfish, Komodo was named after the Indonesian lizardthat also serves as its logo. Developed by Don Dailey, it is now heavily influenced by grandmaster Larry Kaufman, which gives this engine a more human style.

How it works exactly, remains proprietary, but the owners claim to employ an A/B search function and a sophisticated algorithm based on grandmaster understanding.

Komodo MC

Komodo MC uses the same evaluation functions, techniques, and tools as Komodo. But its search is utilizing the Monte Carlo chess tree search method instead of A/B. Komodo MC is on its way to becoming as strong as Komodo.

Houdini

Like the magician it is named after, this chess engine is particularly powerful when it comes to escaping tricky situations and positions. Plus, its search function is extremely fast, making Houdini a strong contender when faster time controls are being applied. Like Komodo, Houdini was commercially developed.

Fire

Fire was privately developed by Norman Schmidt and remains a non-commercial engine. It was first released in 2010 and has been growing a following ever since.

Ethereal

Ethereal takes a slightly different approach. This open-source engine was developed by programmer Andrew Grant as a way of helping him learn from its performance and sharpen his own programming skills.

The engine was inspired by Stockfish and has been around since 2016, making it one of the newer options.

Shredder

Shredder is an 18-time world computer chess champion. This engine was created in the 1990s by German programmer Stefan Meyer-Kahlen and continues to perform well in championships. Meyer-Kahlen also invented universal chess interface (UCI), another chess engine protocol.

Laser

Another relatively new arrival, Laser was created and launched in 2015 by brothers Michael and Jeffrey An. At the time, both were students in California. Today, this open-source chess engine is available on GitHub.

Neural Network Engines

Check out our list of three leading neural network chess engines, following in the footsteps of Leela Chess Zero (Lc0). 

Leelenstein

Leelenstein makes use of much of the original code from Lc0, but its neural net is different. Leelenstein’s approach is based on supervised learning. It takes its information from millions of games that have been previously played by chess engines rather than learning from its own games. At the time of writing, it was not (yet?) as strong as Lc0.

Antifish

Antifish’s name says it all. This NN chess engine was developed to beat Stockfish. It uses code from Lc0, but its neural net is exclusively based on games played between Stockfish and Lc0. The goal is to beat Stockfish. However, at this moment, Antifish is not as strong as Leelenstein or Lc0.

Allie

Allie takes a different approach from its competitors, thanks to its own Monte Carlo search tree, selection of moves, and code used for computational time management. This engine works with any net, and programmer Adam Treat is looking to add an A/B minimax algorithm search option to make Allie more versatile.

Also Read: Self taught AI will be the end of us

Conclusion

Chess engines can change the way players assess a single position, random moves, or an entire game. They have the potential to improve the playing strength of professionals as well as amateurs looking to improve their performance in quick games. Whether a player starts with the white pieces or reacts with the black pieces, techniques like alpha-beta pruning applied by chess engines make winning more likely.

Advertisement