HomeThe Queen's Gambit and complexity
In 2020, the world rediscovered the passion for chess after the huge success of the Netflix limited series The Queen's Gambit. It tells the story of a highly skilled chess player on her road to greatness. During her evolution, the audience gets to see how complex a single move can be and the repercussions each may have. But how hard can an 8x8 board game be?
The game structure and a clear set of rules are appealing for applied mathematics professionals. Those characteristics have turned chess into a classic background for many case studies, especially in game theory and combinatorial optimization.
The first field seeks to understand the interactions between rational players, where each one wants to maximize their gain. The culmination of this effort is to know which of the three possible outcomes of a match (white wins, black wins, or draw) occurs if the two players play it perfectly. Currently, experts are far from knowing the answers, even when supported by the best supercomputers. It is possible to imagine its complexity by comparing it to another 8x8 game, checkers, which was solved in 2007 [1]. This simpler game took nearly 28 years to crack while investigating a game that could have 5 x 1020 (500 billion billion) possible positions.
The second case is illustrated by the Knight's Tour problem. It consists of finding a sequence of moves that allow the knight to visit every square on the board exactly once.
Figure: A solution for the Knight's Tour
For the classic 8x8 board, the problem has been solved. There are 19 x 1015 (19 million billion) directed tours possible [2]. This is far from any estimate someone could guess by just looking at the board and already having difficulty to find only one feasible tour!
Being a chess master requires extraordinary analytical skills, since the player has to predict so many scenarios in advance. We could incorrectly think that there is a “limited” number of games and that, after a few years, you may know how to proceed in a specific situation. Again, the perception is far from reality. A chess game has, on average, 80 rounds and about three sensible (meaningful) moves on each round which generates nearly 1040 possible sensible games. This means much more than it would be possible for the entire population on the planet to play every day, even since the Earth’s formation!
These examples highlight the difference in magnitude between the real complexity of a problem and the perception that we may have of it. Society has witnessed many times where AI has beaten the great game masters, in matches such as Deep Blue v. Kasparov and Watson v. Ken Jennings. This creates a false sense that every mathematically formulated problem can be solved in just a few minutes by a machine. Advances in data processing, like quantum computing, and GPGPU, have significantly increased computers’ solving capacities. However, given the number of possible solutions, we still rely on people's creativity to build efficient algorithms for solving complex problems.
References
[1] Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P. & Sutphen, S. (2007), 'Checkers Is Solved', Science , 1144079+.
[2] The On-Line Encyclopedia of Integer Sequences - OEIS Foundation Inc. (2020).
Co-author: Emmanuel Marchal - Managing Partner at Cassotis Consulting