7
$\begingroup$

Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require?

The game of checkers has already been solved through back in 2007 after years of number crunching. But they don't expect that chess will be able to be solved the same way because the problem is an order of magnitude more difficult. There are an estimated $10^{40}$ legal chess positions and about $10^{120}$ possible games.

$\endgroup$
  • 4
    $\begingroup$ Related: Chess SE: Will quantum computers solve chess? $\endgroup$ – Sanchayan Dutta Apr 1 at 4:20
  • 2
    $\begingroup$ You'd perhaps like Scott Aaronson's article The Limits of Quantum (especially p. ~67) and blog post NAND now for something completely different. Also, check Bremermann's article on the theoretical limitations of solving chess and this review for a brief discussion on NAND trees. $\endgroup$ – Sanchayan Dutta Apr 1 at 7:52
  • $\begingroup$ I don't agree with all of the pessimism in the Chess.SE thread, and I don't agree with the framing of the question as "black-to-move/white-to-move/black-to-move..." not fitting into a quantum algorithm. I do like thinking about such "high-concept," easy-to-state questions. Although specific to chess, research on deep neural networks is cracking the problem much faster than quantum computers likely ever will, but asking about "what kind of games, if any, could a quantum computer tackle" is attractive. $\endgroup$ – Mark S Apr 3 at 16:45
3
$\begingroup$

As an initial matter, let's ask "what is the classical computational complexity of solving 'mate-in-$n$' type games?" For example, is it even in $\mathcal{NP}$ to know, given a certain chess position, that white can mate in $10$ or fewer moves?

It's been known for a while that we can consider such questions as a "quantified boolean formula" (QBF) question. Let's rephrase our question as:

$$\exists w_1\forall b_1\exists w_2\forall b_2\cdots\exists w_n:\phi(w_1,b_1,w_2,b_2,\cdots,w_n)?$$

This "mate-in-$n$" statement can be read as "given a state of the board $\phi$ encoding the rules of chess, does there exist a move by white such that for moves by black, there is a countermove by white such that... the moves applied to the board $\phi$ will lead to a mate by white?"

This "mate-in-$n$" is precisely a way to think about the polynomial hierarchy $\mathcal{PH}$. The mate-in-$10$ is at the $10^{th}$ level of the hierarchy (or maybe it's the $20^{th}$) because there are $20$ iterations of for-alls and there-exists. $\phi$ is easy to evaluate (polynomial evaluation of whether there's a mate or not). The number of qubits would be polynomial in $n$ I think (high thousands?).

Letting $n$ vary polynomialy distinguishes $\mathcal{PH}$ from $\mathcal{PSPACE}$. Magically, although we know that $\mathcal{BQP}\subseteq\mathcal{PSPACE}$, it's likely that $\mathcal{BQP}$ and $\mathcal{PH}$ are incomparable. I think the implication is that certain well-framed QBF-style questions can be answered faster than classical algorithms.

For chess proper, most games can be completed in about $50$ moves or less. So we can say "is there a mate-in-$50$ for white, given the starting position?"

Chess has a lot of asymmetry that may make it difficult to frame in the right way. Weichi (Go) may be a better candidate for pondering. I suspect a toy game, based on forrelation, can be built where a quantum computer can outperform a classical computer.

EDIT

To think about how to utilize such an algorithm, let's take the QBF a little bit more. The output of the QBF is either a "YES" (a forced mate is possible) or "NO" (a forced mate is not possible).

Say we are white, and we have a quantum QBF-solver that can be fed a given board position with black to move, and will spit out whether there's a winning strategy for black (i.e. YES or NO). It is our turn to move.

We can cycle through all of the available moves for white by making a putative move, and ask our quantum QBF-solver whether black has a winning response. If we find a move where black doesn't have a winning response we can take that line.

In the comments, you suggest that chess isn't likely played out in $50$ moves starting from the initial board, and that $6000$ moves is more likely.

Nonetheless even accepting $6000$ is the better estimate, I maintain that the number of qubits is polynomial in the depth of the tree you are willing to review, otherwise you haven't got a practical algorithm.

$\endgroup$
  • $\begingroup$ Interesting. But I disagree with your proposal to try to see if there is a mate-in-50 for white, given the starting position. My reason is that the expected solution for chess if chess gets solved will likely be the same as the solution found for checkers, where with perfect play the game is a draw. To prove that, you won't be able to stop at 50 moves but will likely have to go the limit, which is estimated to be close to 6000 moves: chess.com/blog/kurtgodden/the-longest-possible-chess-game $\endgroup$ – lkessler Apr 3 at 4:34
  • $\begingroup$ I like your edit much better. The only qualm I have with it is that you are not considering that there are 3 results: win +1, loss -1 and draw =0. Yes, you want to follow the lines that black does not have a win, but of those, you should prefer a line where you win rather than just draw. $\endgroup$ – lkessler Apr 4 at 19:56
  • 1
    $\begingroup$ I think then a minor tweak to $\phi$ would be to have white make a putative move, and ask the QBF-oracle if black has a winning or drawing response, and only take a line that leads to a win for white. If there are no winning lines, then take a drawing line if possible. If there are no winning or drawing lines, then resign. We don't need to know what the line is, we just need our QBF solver to us whether a forced mate is possible. $\endgroup$ – Mark S Apr 4 at 20:21
2
$\begingroup$

Speculatively expanding on previous answer

Quantum computers tend to outperform classical computers in determining global properties of functions. Further, the properties tend to be some measure of global symmetry. Based on the global symmetry, the probability amplitudes can constructively (and destructively) interfere, in ways that a classical computer could not.

Let's look at chess for a moment.

  1. Deciding a winning position in chess, e.g. a mate, seems very much a local property of the board. There may be many pieces left on a board, but many of the pieces are irrelevant to the mating position. Of course pawn structure is a global property in a way, but pawns and many pieces (knights/kings/bad-color bishops) only have a local influence.

  2. Chess by its nature is very asymmetric. Castling of course is a very asymmetric move, but I also mean, for example, that a bishop behaves significantly differently than a knight or a queen. A pawn captures differently than it moves.

Let's compare chess to wei-chi/go/paduk.

  1. Wei-chi has much more of a global feel to it than chess. Each stone can have both a long-range and a short-range impact. Life and death may hinge on being able to connect to a far-away island.

  2. The rules of wei-chi are much more symmetric, in a sense that "all stones are born equal." There are some asymmetries, of course, such as the ko rule. The edge-of-the-board is different than the center, which is a bit of asymmetry; however, there's nothing quite like the dramatic difference in strength between a queen and a knight or a pawn.

Ignoring such ko-rule asymmetries for now, let's let black be $0$, white be $1$, let $x\in\{0,1,blank\}$, and $f(x_1^1,x_1^2,\cdots,x_1^{19},\cdots,x_{19}^{19})$ be a function that takes a $19\times 19$ wei-chi board (e.g., a board after two consecutive passes), and returns whether white or black or neither has more claimed territory. I'm pretty sure $f$ is not that difficult to calculate, at least to a first level. Once black places the first stone, we can ask the same about the new board position with a new function $f^1$, and so on. Here $f^1$ is just like $f$ but one of the values of one of the $x^i_j$ has been fixed to $0$.

Speculatively, a quantum computer may be able to answer such a global property of $f$ as "is there a move for black, such that for all moves by white, there's a countermove by black, such that... black ends up with more territory?" With the placement of each of the stones, it feels like maybe there's constructive/destructive interference at work.

Speculating very much even more, perhaps we can construct a toy "battleship-style" or "Kiregspiel" style wei-chi game, where white $f$ and black $g$ take turns placing stones secretly on their respective board, and the value of the board is determined by a measure of the correlation between $f$ and the Fourier transform of $g$. We know a quantum computer is likely to outperform a classical computer for such a "forrelation" game; working backwards to create rules for such a game may be possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.