D-Wave Systems breaks the 1000 qubit quantum computing barri

[Ozymandias]

In the practical sense, I conjecture that chess will be solved first by a heuristic searcher, running on conventional digital computers, that can't be beaten anymore (that is: the draw rate reaches 100.000%).

Would that unbeatable computer run the engine alone, or would it have access to a book, that covers the most complicated of openings? I'm thinking of the Poisoned Pawn, the King's Gambit, the Botvinnik variation of the Anti-Meran Gambit… all of those are very well researched, so their complexities have been sorted out, for the most part. If the computer can access that data, it may attain a draw today, but if it has to play those positions on its own, it'll be quite a long time before it becomes unbeatable.

[bob]

Code: Select all

64532931270784997255072947271902112972253434591521878478176684793280
...
78103877548969836316850807142144192493125768499429376

That's a bit of an upper bound, though. I've seen estimates of 10^46 or so possible positions, which it may be possible to build a database for. It would be at least Ceres sized, and perhaps as large as the Earth. Actually calculating the data would take a non-trivial amount of time.

It's probably best to make something like a 26 piece tablebase and solve chess from that, It still looks too hard to bother with just for a game.

In chess the number of possible positions is not enough. There are two fold and three fold repetitions hanging around that are the same as the original position, yet the third time can end the game, where the first or second can't. So the number of plies of search is way larger than the limit you might compute by the raw number of positions. I think 2^160 or so has been one pretty good guess for total positions, and that is quite enough to thwart anything over the next N years, but beyond that, proving the game is won, lost or drawn is much harder.

[Dirt]

In chess the number of possible positions is not enough. There are two fold and three fold repetitions hanging around that are the same as the original position, yet the third time can end the game, where the first or second can't. So the number of plies of search is way larger than the limit you might compute by the raw number of positions. I think 2^160 or so has been one pretty good guess for total positions, and that is quite enough to thwart anything over the next N years, but beyond that, proving the game is won, lost or drawn is much harder.

Repetitions can change a win into a draw. That will only change the theoretical result if it pushes the next pawn move or capture out past 50 moves. Keeping track of the moves till a zeroing move is a constant overhead. It doesn't increase the complexity by a factor of 2^54.

[mvk]

In the practical sense, I conjecture that chess will be solved first by a heuristic searcher, running on conventional digital computers, that can't be beaten anymore (that is: the draw rate reaches 100.000%).

Would that unbeatable computer run the engine alone, or would it have access to a book, that covers the most complicated of openings?

The first one to achieve this would still be guided by an opening book, I suppose. Why make it harder than necessary.

[bob]

In chess the number of possible positions is not enough. There are two fold and three fold repetitions hanging around that are the same as the original position, yet the third time can end the game, where the first or second can't. So the number of plies of search is way larger than the limit you might compute by the raw number of positions. I think 2^160 or so has been one pretty good guess for total positions, and that is quite enough to thwart anything over the next N years, but beyond that, proving the game is won, lost or drawn is much harder.

Repetitions can change a win into a draw. That will only change the theoretical result if it pushes the next pawn move or capture out past 50 moves. Keeping track of the moves till a zeroing move is a constant overhead. It doesn't increase the complexity by a factor of 2^54.

It increases it by an absolutely huge amount. Take the number of positions at 2^160. How many different pathways are there in that? How many pathways with the same position repeated twice but not three times? How many pathways with no pawn pushes or captures between 50 consecutive moves that is optimally played? Or more simply, how many different pathways are their through the SAME position? Because each of those is potentially different from the others due to 50 move and 3-fold repetition rules...

[Dirt]

It increases it by an absolutely huge amount. Take the number of positions at 2^160. How many different pathways are there in that? How many pathways with the same position repeated twice but not three times? How many pathways with no pawn pushes or captures between 50 consecutive moves that is optimally played? Or more simply, how many different pathways are their through the SAME position? Because each of those is potentially different from the others due to 50 move and 3-fold repetition rules...

You only need to store the number of moves, with optimal play, until a zeroing move. If the 50 move counter in a position plus that number of moves is 50 or more, it's a draw. Otherwise it's whatever result is stored for the position. This is at most seven bits per position, and on average much less.

Why are you writing about pathways? They don't matter.

[bob]

It increases it by an absolutely huge amount. Take the number of positions at 2^160. How many different pathways are there in that? How many pathways with the same position repeated twice but not three times? How many pathways with no pawn pushes or captures between 50 consecutive moves that is optimally played? Or more simply, how many different pathways are their through the SAME position? Because each of those is potentially different from the others due to 50 move and 3-fold repetition rules...

You only need to store the number of moves, with optimal play, until a zeroing move. If the 50 move counter in a position plus that number of moves is 50 or more, it's a draw. Otherwise it's whatever result is stored for the position. This is at most seven bits per position, and on average much less.

Why are you writing about pathways? They don't matter.

You need the move list. You need a list of ALL positions searched so far since you have to recognize repetitions and 50 move rule draws. You need to store the movelist for each ply, up to 5500 of 'em. This is really a computationally IMPOSSIBLE task, regardless of computing platform needed.

Pathways don't matter? When you reach position P from path A, is it a repetition? What about position P fro path B? Is IT a repetition? If you want to argue depth-first alpha/beta is good enough, that's fine. Back to sort(38^5500) as the upper bound on the potential search space.

In chess it is not just the positions that count, it is the pathways to those positions, thanks to the 50 move rule and 3-fold repetition. That is one huge search space worst-case. Who knows what best-case is? If the game is a draw, then you will almost certainly have to search to depth 11,000 plies to make sure there is no way out.

And if you want to use this to analyze the game, do you keep spending a zillion years to re-search for the next positions someone asks about?

We can barely do 7 piece endings reasonably today. Over four trillion different positions. You are only lacking another factor of (rough estimate) maybe 48^25 ~ 10^55 or so. Suppose you only have to deal with just those positions to build your tree, using alpha/beta you get ~10^27. A program MIGHT hit 10^6 positions per second today. You only need 10^21 seconds. Or roughly 700 trillion years? Think you can reach a billion nodes per second? 700 billion years then. With alpha/beta. No guarantee I am not off a zero or two either way. Doesn't really matter with the age of the universe only 20 billion years and counting.

I am not sure you are thinking about just how large this number is. A lot of things can happen potentially, regarding computing. Solving the game of chess is NOT among them.

[jefk]

[quote="bob"] If the game is a draw, then you will almost certainly have to search to depth 11,000 plies to make sure there is no way out.
[/quote]

Well in top correspondence chess they don't play out drawish games,
the ICCF rules are already allowing 6men egtb's (with 50 move rule)
to decide whether and endgame is a draw. And we know (see eg other posting) that in top correspondence chess the drawing percentage is approaching 100 pct. With the current rules.

Despite the immense high nr of possible positions, most positions i.e. mistakes can be discarded because they lead to a win (for Black or White), for example, unless a sound sacrifice, in situations where one side lost a piece in the opening or (early) middle game it's fair to say that this side will lose for sure against solid (correspondence) play.

And if we would analyze 'only' games which are played reasonably well
it's possible to build up a tree, and see if an (opening) strategy can lead to a win. In *theory* there *could* be an still unfound strategy (eg with 1.d4 with steadily but slowly increasing positional advantage), still leading to a win but the chances for that are slim; and if there is *no* winning strategy(*) there is a theorem by Zermelo that the game then is a draw. This also holds true for chess although ' proving' there is no winning strategy according to proper mathematical methodology i
ndeed is a difficult task.

The empirical approach not using GM evals like eg with the NIC yearbooks but a simple Stockfish approach in a huge positionbase with now apparently some 8 billion positions has yielded nothing at:
http://www.arshah.com/
Installation doesn't work anymore, but a year ago i looked at it
and all initial values were zero (backsolved via lines after every game)
and they stayed zero. Not surprising for me, although the quality of the database of this Arshah system didn't look great; i played some games on ICC with my own book, still often managed to win with standard
time control, due to my faster comp and a later stockfish and better worked out opening strategies. Apparently arshah(C) still is running sometimes on Fics so you could have a look.

So despite not believing anymore in such a ' holy grail' i admit i still search sometimes for better/promising lines starting with 1.d4, fundamentally i can' t find more ' backsolved' advantage than eg 0.16 or so with Komodo, and that's not enough to guarantee a win. So for me it's obvious that chess with it's current rules is a draw, and in the end my most promising lines will also be equalized, although this would significantly and maybe unnecessarily increase the size of my already large opening book leading to nothing and being able to demonstrate that provided i would live that long

jef

PS (*) other example (not related to a two person non-chance game with perfect information, but a game of chance): Q) is the game of roulette a draw or a loss ? Answer: this depends on the commission for the Casino.
Do you need to simulate it with quantum computers into trill-bill-gazillions of millennia to find the answer ? No sir. With such games you need to have an *edge*, otherwise forget it. In Blackjack apparently a player with card counting could have a theoretical edge that's proven.
But in chess, even if White would have a slight edge, the drawing margin of the game prevents a fundamental win for White. And even the 'edge' is doubtful some experts argue that while White has the first move, by releasing the info which opening he wants to play, Black can use such info to his advantage thus cancelling out the 'edge'. Ergo chess = an =.

[Ozymandias]

In the practical sense, I conjecture that chess will be solved first by a heuristic searcher, running on conventional digital computers, that can't be beaten anymore (that is: the draw rate reaches 100.000%).

Would that unbeatable computer run the engine alone, or would it have access to a book, that covers the most complicated of openings?

The first one to achieve this would still be guided by an opening book, I suppose. Why make it harder than necessary.

Then, as soon as an "adequate" book is presented, I think Komodo, on strong hardware and at LTC, would already be unbeatable. Of course, the tricky part is to compile such a book. Any defeat of the engine, could be chalked up, to the book not providing a good "starting" position.

[jefk]

[quote="Ozymandias"]
Then, as soon as an "adequate" book is presented, I think Komodo, on strong hardware and at LTC, would already be unbeatable.[/quote]

Unless (it's beaten) by itself on stronger hardware; (or not).
If the 'first' (current-fast) hardware is already fast enough, i think
you're right. Winning with Black is much more difficult in
computer chess btw, but having a drawing strategy for Black
isn't so difficult, and fundamentally certainly not impossible.

So i had a look at my book again, corrected the 'best' line, and
now i'm back again at only 0.12 for 1.d4, 1.c4, or 1.g3 (1.e4?! at
0.10; at least with Stockfish, Komodo overrates open positions).
But i don't have sufficiently fast hardware yet, so i can't
exclude an occasional loss still, now and then. For Black. With
White i'm already almost never losing (on ICC, bookbuilder(C)).

Correcting some theoretical stuff about Zermelo i wrote, first the theorem
https://en.wikipedia.org/wiki/Zermelo's ... ite_note-1
Well i was talking about a winning strategy. To be more precise,
the theorem talks about 'if the game *cannot* end in a draw' .
Example for the game of Hex
http://hkumath.hku.hk/~ntw/EMB(giftedst ... -2008).pdf
Now back to chess: ofcourse it *can* end in a draw,
so only thing Black has to do is finding a 'drawing strategy'
(in theory also for White, but my drawing strategy with 1.d4
now works well enough with Komodo i think(.

So what is such a drawing strategy for Black:
well first of all,

A) having excellent book moves, cancelling
any White advantage. Against 1.d4, Slav, against e4, Sicilian,
against 1.c4 the reversed Sicilian (tricky btw but possible).
B) not letting White making positional progress, or having
counter attacks, eg with Sicilian making progress at the queenside.
C) keeping in mind the drawing rules in middle- or endgame,
eg 3 x position repetitition, or 50 (pawn) move rule.

That's all.
So Black has a drawing strategy, ergo
chess (indeed) = an =

QED


jef

PS again, no pure mathematical 'proof' of ' solving' the game yet,
but i'm making progress; at least in my own views
To show how mathematicians discuss such things in overcomplicated
ways, here's another example of an game theoretical article
discussing chess (have fun):
http://www-history.mcs.st-and.ac.uk/Pro ... s/Ch4.html
Maybe after Zermelo some arguments from socalled
graph theory can lead to more convincing arguments
Black indeed has ie can have a (fundamental) drawing
strategy in chess; then i consider chess to be solved..

www.superchess.blogspot.com
http://www.amazon.com/Jef-Kaan/e/B00V58K4G6