The Evolution of Chess AI – Fluency

The Evolution of Chess AI

This week 50 years ago, Bobby Fischer defeated Boris Spassky to become the Chess World Champion in one of the most famous series of matches in the history of game. To celebrate this anniversary, Fluency explores how the 1,500-year-old-game has pioneered research in Artificial Intelligence and how chess engines have developed since their inception in the 1940s.

Chess is regarded by many as the ultimate game of strategy. The brutal and unforgiving sport requires near-perfect execution at the top level to achieve victory, with Grandmasters having to evaluate dozens of positions before making a move. A study by Robert Sapolsky, Professor of neurology and neurosurgery at Stanford University has shown that Grandmasters can burn up to 6,000 calories a day over the course of an intense, multi-day tournament (ESPN), demonstrating the extreme mental stress these players experience.

The depth of thinking required in chess provided great interest to Alan Turing, the father of artificial intelligence. Having famously created the “Bombe” computer during World War II, capable of decrypting an enigma message every two minutes, Turing was acutely aware of the potential computers had in solving complex problems. Chess was no exception.

The First Chess Engine

In 1946, Turing began his research into the first chess program which was based off the following principles:

Each piece had a ‘value’ (for example, Pawn = 1, Bishop = 3.5, Rook = 5)
Every possible move and countermove would be examined
Each position generated would be evaluated based on the value of the pieces that each player held. The move that gained the most ‘value’ for a player would be selected

Since during the opening phase of a game most positions would have the same value, Turing also introduced some positional criteria to the program’s evaluation system.

Dr Dietrich Prinz implemented this program into the Ferranti Mark 1 in 1951, making one of the first computer games in history. Despite the memory limitations of the Ferranti, the program could solve ‘mate-in-two’ problems in 15-20 minutes, brute-forcing its way through the thousands of possible moves until the checkmate sequence was found.

The Minimax Algorithm and its Limitations

The Minimax Algorithm is used throughout the world of decision making, being at the core of philosophy, statistics and even warfare. The whole concept of the algorithm is to discover which decision will generate the smallest possible loss along with the greatest minimum gain. This is achieved by evaluating all possible sequences of moves which creates what computer scientists call a ‘search-tree’.

Minimax is perfectly suited to pair with Turing’s program, but as previously discussed, chess is an extremely complex game with more possible moves than there are grains of sand on all the beaches of the world. Computers (at least right now) simply aren’t capable of this level of analysis, so how were computer scientists able to mitigate the extreme computational load required by engines?

Pruning the Tree

In 1921 the great Cuban Grandmaster José Raúl Capablanca was asked by an aspiring chess player how many moves he looked ahead, to which he jokingly responded “Only one, but it’s always the right one!”

Despite downplaying the extent of his calculations, this quote highlights the importance of intuition and instinct in chess. With years of experience, players like Capablanca are able to find the best moves without having to analyse thousands, like the computers do, giving them a critical advantage. Minimising the number of positions evaluated the chess engine, or “pruning the tree” became the next key area of research for computer scientists, and this remains a fundamental part of artificial intelligence to this day.

This was eventually achieved by teaching engines only the stronger opening sequences of moves in the game, as well as training it to recognise patterns on the board described by Grandmasters to be positionally advantageous (this would include instances where the enemy king is under threat, leading to a potential checkmate). These improvements to the chess engine combined with advances in computational power led to the first victory of a machine in a competitive tournament setting, achieved by the Mac Hack program in 1967.

A machine will always remain a machine, that is to say a tool to help the player work and prepare. Never shall I be beaten by a machine! Never will a program be invented that surpasses human intelligence.
Garry Kasparov, World Chess Champion, 1984 – 2005

Crazy Bird

Over the next 30 years, further advancements in computational power led the chess engine to be a genuine force to be reckoned with. In 1979, Ken Thompson (creator of the programming language B) developed the machine Belle, the first chess engine to have a master-level FIDE rating of 2150. But despite the machine now being able to analyse over 5,000 positions a second, it was still unable to compete with Grandmasters, further demonstrating the power of human intuition. However, this all changed in the 90s with the help of the computer science prodigy Feng-hsiung Hsu, nicknamed ‘Crazy Bird’ by his peers due to his eccentricity.

Hsu was one of the brilliant minds behind the IBM chess supercomputer Deep Blue, which famously defeated one of the greatest player in the game’s history, Garry Kasparov in a six-match series in 1997. The machine could analyse approximately 200 million positions a second and contained a highly detailed library of chess opening theory. At this point, the human brain was simply unable to compete with the machine, and chess engines have been dominating Grandmasters ever since.

The Rebirth of the Chess Engine

By the 2010s, it had been clearly established that the human was no match for the chess engine, so why were we still teaching them? At this point the computer was powerful enough to mimic the thinking process of the human brain via the use of neural networks, and Google applied this technique in the AlphaZero engine. The machine required absolutely no training from humans, and after nine hours and 44 million games with itself, it thrashed the previously dominant engine Stockfish 9 in a 100-game series (28 wins, 72 draws, 0 losses). This was a ground-breaking moment in artificial intelligence, demonstrating the power of generalised reinforcement-learning in problem solving.

As a result of the lack of human input in its training, AlphaZero developed a totally original style of play, combining elements of unconventional post-modern opening theory with exciting piece sacrifices reminiscent the romantic era of chess in the 1800s, placing more of an emphasis on positional play than nature of the pieces of the board. Its unusual and ruthless style can also be seen in the Asian strategy games Go and Shogi.

Conclusions

Artificial intelligence has completely changed the way that chess is played. With the help of chess engines, Grandmasters are now able to plan prepare for their games in extreme depth, sometimes memorising up to 15-20 moves of their openings. Although some chess commentators worry that this extreme perfectionism can make top level gameplay tedious, AlphaZero proves that however highly polished chess gets, AI can still blow the sport wide open.

Let's Stay in Touch

Follow us on LinkedIn for more data-led content and inspiration.

How brands can leverage Data Science

June 2, 2023

Services Expertise Views About Contact How brands can leverage Data Science In today’s digital landscape, brands are inundated with an overwhelming amount of data. However, without the right tools and expertise, this data can remain untapped potential. Enter data science.

Meet the Team: Georgina Wong

May 5, 2023

Services Expertise Views About Contact Meet The Team: Georgina Wong Fluency’s Lead Consultant Georgie Wong discusses her love for finding patterns in data, fitness and travel! “I love finding the all-important patterns, trends and ‘gems’ of insights that will make

Meet the Team: Tinashe ‘Tin’ Mukarati

April 25, 2023

Services Expertise Views About Contact Meet The Team: Tinashe ‘Tin’ Mukarati While the UK is eagerly waiting for spring to arrive, Fluency’s Tinashe Mukarati is donning a turtle-neck sweater as Cape Town heads into Autumn. That’s despite the temperature fluctuating