The Rising Tide of AI – Chess and Computers

A history of chess computing and a look into the future

Chess has been an important hurdle in the continuous quest to reach the peak of the AI competence-landscape. But while AI enthusiasts may have turned their attention to other areas, chess still remains an ‘unsolved’ game. That is to say, even with the top chess computers being able to outclass Magnus Carlsen, there is still no strategy for perfect play.

Will such a strategy ever exist, and how might we reach it? And what does the history of chess computing have to tell us about this question and the future of chess as a whole?

How did we get here?

It is often claimed that chess computing began in 1769 with the invention of ‘The Mechanical Turk’, a machine that could seemingly move the chess pieces and play on its own, however, it was found to be a fraud. A human was hidden inside the box and used magnets to move the pieces. It wasn’t until almost 200 years later in the 1950s that the first chess programs were invented (on paper), with the first by Alan Turing in 1951 called ‘TuroChamp’. Six years later, with the advent of digital computing, the first computer program was able to play a full game of chess thanks to the work of Alex Bernstein.

Since then, chess computing has made breakthrough after breakthrough. First toppling novices, working their way through masters with ‘Belle’ in 1983 being the first machine to achieve master-level play, and finally toppling the reigning world champion in 1997 with IBM’s Deep Blue. Programmes continued to develop going above and beyond any human as
well as branching out into games like Go, which many thought would be unassailable for
decades.

How did they do it?

The earliest algorithms used to search chess moves generally fell into two categories. ‘Type A’ would brute force through every move possible on the board, evaluating move after countermove to a certain depth and selecting the best branch of the resulting tree to decide on its move. ‘Type B’ now called ‘forward pruning’ would immediately eliminate the majority of the moves only selecting a few which looked sensible, this would allow for a greater depth of analysis on those moves.

Type B may be more akin to how a human plays chess, we don’t consider every single move on the board in every position and we certainly don’t consider every single move and the resulting lines to any kind of depth. However, how does the computer decide which moves to ‘prune’? In reality, this type of searching resulted in sub-optimal play. The computer would often eliminate the better moves because the initial selection algorithm was poor. In fact, Type-A advocates realised that the time the computer spent deciding to eliminate moves initially could simply be spent actually checking those moves – a principle which is employed in chess computers to this day.

Chess algorithms continued to get more advanced, taking advantage of more efficient searching and selecting. The most advanced chess program is AlphaZero, which uses a ‘Monte-Carlo’ tree search. While Deep Blue may have been an “alarm clock”, AlphaZero certainly isn’t – given only the rules it was able to play against itself millions of times until it surpassed all human players and all other chess computer programmes.

Does the perfect chess game exist, what would it mean if we found it?

Scientists categorise games like chess into those which have been ‘solved’ and those which are ‘unsolved’. A solved game, broadly speaking, has a ‘perfect’ strategy. Given players play this way, the outcome of any position can be predicted. For example, if you have played noughts and crosses enough times you will eventually figure out you can force a draw no
matter what your opponent does. Interestingly, Connect4 is also a solved game, that is to say, with perfect play the first player will always win.

Chess, however, despite the superiority of chess computers and AlphaZero, remains an unsolved game. There are various degrees to which a game can be solved, for example an algorithm that always secures a win or a draw for a player from the start of the game would ‘weakly solve’ the game. Alternatively, an algorithm that can produce perfect moves from any position, even if mistakes have already been made would constitute a ‘strongly solving’ the game. It may simply be a matter of time before chess is solved, seemingly the “only” barrier to this is the sheer number of variations from the current starting position (much greater than the number of atoms in the universe).

If chess were solved, what would the implications be? It could be the case that people would lose interest in the game, but looking at other solved games, this seems unlikely. Go has been weakly solved for the 5x5 and 7x7 board, and yet this revelation did nothing to damage the popularity of the game. Ultimately, humans don’t seem to mind if a game can
be played perfectly from any position, as long as the degree of complexity is high enough that they themselves can’t ever figure out the perfect moves.