How many Qubits need to slove chess?

Discussion of anything and everything relating to chess playing software and machines.

Moderator: Ras

jp
Posts: 1483
Joined: Mon Apr 23, 2018 7:54 am

Re: How many Qubits need to slove chess?

Post by jp »

Raphexon wrote: Wed Jul 03, 2019 5:10 pm What do you mean with perfectly?
32 piece tablebase kind of perfect?
Yes.
Raphexon wrote: Wed Jul 03, 2019 5:10 pm Or weakly solved like checkers? In that it only has the perfect solution from start (initial position) and only plays perfectly if opponent also plays perfectly.
Ummm, the checkers situation is different.

"The crucial part of Schaeffer’s computer proof involved playing out every possible endgame involving fewer than 10 pieces. The result is an endgame database of 39 trillion positions. By contrast, there are only 19 different opening moves in draughts. Schaeffer’s proof shows that each of these leads to a draw in the endgame database, providing neither player makes a mistake.

Schaeffer was able to get his result by searching only a subset of board positions rather than all of them, since some of them can be considered equivalent. He carried out a mere 10^14 calculations to complete the proof in under two decades."
- New Scientist

If you could mathematically prove chess is a draw without having a 32-man TB, that would be another kind of "solve".

But I don't see how you can do that. Alpha-beta won't help with that. It sounds like Schaeffer used the very high degree of symmetry in checkers as a key part of the proof.
Raphexon
Posts: 476
Joined: Sun Mar 17, 2019 12:00 pm
Full name: Henk Drost

Re: How many Qubits need to slove chess?

Post by Raphexon »

jp wrote: Wed Jul 03, 2019 6:22 pm
Raphexon wrote: Wed Jul 03, 2019 5:10 pm What do you mean with perfectly?
32 piece tablebase kind of perfect?
Yes.
Raphexon wrote: Wed Jul 03, 2019 5:10 pm Or weakly solved like checkers? In that it only has the perfect solution from start (initial position) and only plays perfectly if opponent also plays perfectly.
Ummm, the checkers situation is different.

"The crucial part of Schaeffer’s computer proof involved playing out every possible endgame involving fewer than 10 pieces. The result is an endgame database of 39 trillion positions. By contrast, there are only 19 different opening moves in draughts. Schaeffer’s proof shows that each of these leads to a draw in the endgame database, providing neither player makes a mistake.

Schaeffer was able to get his result by searching only a subset of board positions rather than all of them, since some of them can be considered equivalent. He carried out a mere 10^14 calculations to complete the proof in under two decades."
- New Scientist

If you could mathematically prove chess is a draw without having a 32-man TB, that would be another kind of "solve".

But I don't see how you can do that. Alpha-beta won't help with that. It sounds like Schaeffer used the very high degree of symmetry in checkers as a key part of the proof.
It's not different. The symmetry just saved some time (a few years at most) by not needing to check every opening moves. Since some are equal.

A simple A/B algorithm converges to minimax and only needs time to reach the optimal move.

Gardner's minichess is also (weakly) solved btw (with Stockfish actually), its state space complexity is close to checkers but was trivially solved on a weak laptop.