Solving the chess game (quantum computer wise)

[loop quantum gravity]

can a quantum computer exist which is strong enough solve the regular chess game?

In my mind I also invented a game of a 9x9 sort of chess game with another king and the purpose is to catch at least one king, I believe such a game would be even harder than the usual game.

I am learning Game theory, wow I didn't think it's so hard...:-)

 

[QuarkyMeson]

Quantum computers don't have a “strength” in the way you're imagining, per se. They're either quantum or they aren't. The advantage of quantum computing lies in the algorithmic speed up of certain classical algorithms. Then of course you'd have the classical analogues of more qubits more better and specifically quantum things like gate accuracy.

A cursory google search shows that chess is normally computed via Monte Carlo Tree Search, which would run in time $\mathcal{O}(B^d)$, where B is the branching factor and d is the depth or number of turns to look in the future. A Quantum computer could see some advantage here using Grover's Search, which would reduce the time complexity to $\mathcal{O}(B^{d/2})$ .

So, there is some advantage, but it's not something people are going to invest time in running on real hardware anytime soon.

As far as, can you solve chest? You can do that with a classical computer now, given infinite compute and/or time (or at least for all practical purposes). With a quantum computer you could do that in slightly less infinite compute and/or time.

As an aside, I've read a bit more, it seems most advanced chess solvers are using ML because chess is technically a structured game, so a true quantum speed up might not exist.

 

[FactChecker]

"Solve" is too strong a word.
A chess game "solution" depends on what the other player does at each move. It's a game theory problem and most game players benefit by being unpredictable, with some random behavior.
Perhaps "understand" is a better word.
I don't see a clear advantage for quantum computers unless somehow the moves of the opponent are predetermined.

 

[loop quantum gravity]

"Solve" is too strong a word.
A chess game "solution" depends on what the other player does at each move. It's a game theory problem and most game players benefit by being unpredictable, with some random behavior.
Perhaps "understand" is a better word.
I don't see a clear advantage for quantum computers unless somehow the moves of the opponent are predetermined.

I know the terminology either black has a winning strategy whatever the white does etc with the white or there will always settle for stalemate.

I wonder why there isn't an exact number of possible games and our best estimate is of Shannon from information theory.

 

[QuarkyMeson]

I wonder why there isn't an exact number of possible games and our best estimate is of Shannon from information theory.

The same issue as why it's not a solved game practically. The number of possible games is finite, but it's absurdly large. You would need either infinite compute and/or time to calculate the total number of games exactly. Shannon's number is just a back of the envelope approximation, it's a lower bound.

 

[loop quantum gravity]

The same issue as why it's not a solved game practically. The number of possible games is finite, but it's absurdly large. You would need either infinite compute and/or time to calculate the total number of games exactly. Shannon's number is just a back of the envelope approximation, it's a lower bound.

I have some gut feeling that with technology speeding up in twenty years time the game wiil be solved.

Obviously no one really knows if that will come true as the world is already in a sort of turmoil.

 

[FactChecker]

I know the terminology either black has a winning strategy whatever the white does etc with the white or there will always settle for stalemate.

I wonder why there isn't an exact number of possible games and our best estimate is of Shannon from information theory.

Your solution would have to to include the best answers for all 100! possible alternative combinations of opponent moves. That's quite a complicated "solution", but I guess it fits the definition.

 

[loop quantum gravity]

Your solution would have to to include the best answers for all 100! possible alternative combinations of opponent moves. That's quite a complicated "solution", but I guess it fits the definition.

Can you explain why is it 100 factorial?

I know it's hard to count all possible outcomes; but it's no impossible.

 

[FactChecker]

Can you explain why is it 100 factorial?

I'm sorry. I just made that up without thinking. All I know is that it would be a huge number.

I know it's hard to count all possible outcomes; but it's no impossible.

It's far too hard for me to figure out.

 

[PeroK]

I know it's hard to count all possible outcomes; but it's no impossible.

It is effectively impossible. You can only estimate the number of moves in every position.

I doubt there will ever be a full mathematical solution to chess.

 

[loop quantum gravity]

I'm sorry. I just made that up without thinking. All I know is that it would be a huge number.

It's far too hard for me to figure out.

no, I understand it would be an enormous number and one needs to speedup the technology so that a computer would do the job (obviously), but evem then a human needs to check that there are no mistakes in the code.

Eventually we'll solve chess game and we'll invent even harder games....
I wonder how it would be interesting to use DE in game theory and vice versa.
DE=Differential Equations.

 

[PeroK]

Eventually we'll solve chess game and we'll invent even harder games....

Even if chess is solved, nothing changes in terms of human play.

 

[javisot]

can a quantum computer exist which is strong enough solve the regular chess game?

In my mind I also invented a game of a 9x9 sort of chess game with another king and the purpose is to catch at least one king, I believe such a game would be even harder than the usual game.

I am learning Game theory, wow I didn't think it's so hard...:-)

These are two very different views of chess. In one, you assume that there is a way to calculate "the next best move for you" given a certain distribution of pieces on the board, and given the classic rules and conditions of chess.

The other view is that there is a "chess textbook" where all possible chess moves are compiled, numbered, and labeled (with very exotic names), given the classical rules and conditions of chess. In this view, you select moves, not isolated actions, and simply reproduce them from beginning to end.

That vision of a fast and aggressive game, like Kasparov, or a positional and slow game, like Capablanca. We don't know if either of the two approaches solves chess, or if both can, but it wouldn't be surprising if it could. There are games that are far worse than chess, computationally speaking.

 

[FactChecker]

I'm not sure that there is a solution. That would imply white, who has the advantage of the first move, has moves that guarantee black can not draw or win.
There may be a "solution" in the sense of white being able to prevent a loss.

 

[loop quantum gravity]

I'm not sure that there is a solution. That would imply white, who has the advantage of the first move, has moves that guarantee black can not draw or win.
There may be a "solution" in the sense of white being able to prevent a loss.

That's a weak solution. As you know with mathematical riddles one needs to practice quite a lot and then perhaps gain intuition for the game.

I am not really good in playing in chess, but as I play in PS5 NHL and other games in the most difficult level eventually I'll find how to solve the classical game and nothing will stop me. I have a lot of stamina; both physically and mentally.