This is why chess will not be solved in the next 100 Years

[Chessqueen]

A huge game-tree size is no proof that the game cannot be solved. It just suggests that it might be difficult to solve the game by brute-force search.

Take for example the game of Nim. (For those who don't know it: a number of 'tokens' is distributen over a number of heaps, and two players take turns in removing as many tokens as they want (but at least 1) from a heap of their choice. He who takes the last token wins.) The game tree can be made arbitrariy complex by driving up the number of heaps and tokens. Yet there exists a simple algorithm to evaluate any state as win or loss without search.

You are correct Muller, also for those that believe that 10x10 draughts is a simple game they should go to Youtube,com and learn how to play it, and see if they can beat this computer at level 3 ==> https://lidraughts.org/ . Honestly 10x10 draughts is more complex than currently known in literature .The complexity is closer to chess than 8x8 Checkers. and 12x12 draughts is more complex than chess and very tactical, and 14x14 draughts is more complex than GO and very strategical game. More complex means a game has a higher GTC, not necessarily it is more difficult, especially 14x14 draughts will be a tough game for computers to solve in the next 40 years. Methods that are known to be highly successful for 8x8 checkers and 10x10 draughts will start to crumble. There is virtually no use for an opening book and endgame databases, search depth will be strategically insignificant evaluation becomes increasingly difficult to learn. So maybe AlphaGO like techniques start to get useful here.

8x8 Checkers 6.32^49
10x10 Draughts 8.95^110 8.95^110 5.0 x 10^104 almost as complicated as Chess to solve
12x12 Draughts 13.36^200 =1.4 x 10^225 as complicated as Chess and may be more to solve
14x14 Draughts 18.42^320 = 7.8 x 10^404 much more complicated than GO

Learn how to play Draughts 10x10 at youtube.com==> After three days of learning the rules and playing this challenging game, I managed to beat this computer at Level 3 https://lidraughts.org/

[Chessqueen]

A huge game-tree size is no proof that the game cannot be solved. It just suggests that it might be difficult to solve the game by brute-force search.

Take for example the game of Nim. (For those who don't know it: a number of 'tokens' is distributen over a number of heaps, and two players take turns in removing as many tokens as they want (but at least 1) from a heap of their choice. He who takes the last token wins.) The game tree can be made arbitrariy complex by driving up the number of heaps and tokens. Yet there exists a simple algorithm to evaluate any state as win or loss without search.

You are correct Muller, also for those that believe that 10x10 draughts is a simple game they should go to Youtube,com and learn how to play it, and see if they can beat this computer at level 3 ==> https://lidraughts.org/ . Honestly 10x10 draughts is more complex than currently known in literature .The complexity is closer to chess than 8x8 Checkers. and 12x12 draughts is more complex than chess and very tactical, and 14x14 draughts is more complex than GO and very strategical game. More complex means a game has a higher GTC, not necessarily it is more difficult, especially 14x14 draughts will be a tough game for computers to solve in the next 40 years. Methods that are known to be highly successful for 8x8 checkers and 10x10 draughts will start to crumble. There is virtually no use for an opening book and endgame databases, search depth will be strategically insignificant evaluation becomes increasingly difficult to learn. So maybe AlphaGO like techniques start to get useful here.

8x8 Checkers 6.32^49
10x10 Draughts 8.95^110 8.95^110 5.0 x 10^104 almost as complicated as Chess to solve
12x12 Draughts 13.36^200 =1.4 x 10^225 as complicated as Chess and may be more to solve
14x14 Draughts 18.42^320 = 7.8 x 10^404 much more complicated than GO

Learn how to play Draughts 10x10 at youtube.com==> After three days of learning the rules and playing this challenging game, I managed to beat this computer at Level 3 https://lidraughts.org/

Note: As you can see GM Ivanchuck playing 10x10 Draughts, it is not that easy and he has been playing for more than 10 years ==> and competing in tournament ==> https://www.youtube.com/watch? Finally the very best players[/size] ==> [size=120] and
==> more

[towforce]

I cannot think of a way to solve chess using a quantum computer right now, but I think that one could answer questions of the type, "find a position that meets the following (static) criteria" (e.g. the eight queens puzzle).

There are 7 types of piece (pawn, rook, knight, white square bishop, black square bishop, queen, king) and two teams, for a total of 14 piece types. I'm going to say 15, to allow for an empty square.

To represent the state of 64 squares, you would therefore need 14*64=896 qubits. A set of rules would be implemented (pawns cannot go on first or last row, exactly one king per team, max one piece per square etc).

The qubits in a true/false superposition would then represent every possible chess position. The upper limit for the number of possible positions (a number which would be MASSIVELY higher than the actual limit when the rules are applied) would be 15^64=1.9e75 . The quantum computer would be "looking at" all these positions at the same time. If a position met the specified static criteria, the superposition would collapse into this position.