Developing an AI for Quantum Chess: Part 1

Developing an AI for Quantum Chess: Part 1

In January 2016, a team of researchers announced their intentions to develop an artificial intelligence (AI) that could play quantum chess. The idea was ambitious, but the challenges were even greater. In this article, we'll explore the first attempts at creating a Quantum Chess AI and what went wrong.

The Challenges of Quantum Chess

Quantum chess is based on classical chess, but with a twist: quantum mechanics. The game involves making moves that take into account the probabilistic nature of quantum superpositions. This means that a single move can exist in multiple states simultaneously, and the AI must navigate these complex possibilities to win.

The branching factor of Quantum Chess is much higher than classical chess. In fact, for a single queen, there are roughly 30 times as many possible moves. This means that the number of positions to evaluate grows exponentially with the number of plies (moves). The AI must develop strong heuristics to prune the search space and focus on relevant positions.

The First Attempt: StoQfish

The first attempt at creating a Quantum Chess AI was called StoQfish. The team started by using an open-source chess engine called Stockfish as a basis for their quantum AI. They split the quantum superposition underlying the state of the game into a series of classical states and sampled them according to their (squared) amplitude in the superposition.

The idea was to use these classical states as input to Stockfish, which would return its own weighted distribution of the best classical moves. However, this approach had limited success and significant failures. Stockfish is highly optimized for classical chess, which means that there are some positions it cannot process.

For example, consider a scenario where a King is in superposition of being captured and not captured. If one of these Kings is captured, the board will no longer contain a King. This poses a problem for Stockfish, as it expects to find a valid King on the board at all times.

Failed Strategies

The team tried several strategies to overcome these challenges, including:

  • Introducing a King onto boards where he was missing.
  • Hacking Stockfish to abandon its obsession with the King.
  • Asking Stockfish to evaluate positions instead of returning the next best move.

However, each of these strategies had significant limitations and ultimately failed. The team realized that they needed to develop their own Minimax algorithm with custom evaluation heuristics to overcome the challenges of Quantum Chess.

The Next Steps

In the next article, we'll explore the development of Hal 9000, a quantum AI that uses a custom Minimax search with its own evaluation heuristics. We'll examine what went wrong with the first attempts and how the team overcame these challenges to create a more robust Quantum Chess AI.