D-Wave Systems breaks the 1000 qubit quantum computing barri

[Dann Corbit]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

If you just used alpha-beta and no other pruning techniques, then if the algorithm had no errors, the depth achieved would equal the proof depth, since alpha-beta provably gets the same result as pure mini-max.
But you could not use null move pruning or LMR or any other techniques of that nature.

[Dann Corbit]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

If you just used alpha-beta and no other pruning techniques, then if the algorithm had no errors, the depth achieved would equal the proof depth, since alpha-beta provably gets the same result as pure mini-max.
But you could not use null move pruning or LMR or any other techniques of that nature.

A proof search might be able to get deeper, especially with something like this GPU move generator:
https://github.com/ankan-ban/perft_gpu

[Dirt]

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.

In building a tablebase you only care about what the result is from each position you can move to, not how you got there. A position with just two kings is always a draw, no matter how many moves were made.

I'm not saying this is easy. I have almost no idea how long it would take. A thousand years? A trillion years? I don't know.

By the way, have you implemented Syzygy tablebases in Crafty, or are you planning to?

[bob]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

25 plies is doable from the opening position, although it would be a traditional selective 25 plies (reductions, null-move, pruning, etc.) I don't know that anyone has actually searched 25 full plies from the start positions however... It would be extremely slow.

[Dann Corbit]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

25 plies is doable from the opening position, although it would be a traditional selective 25 plies (reductions, null-move, pruning, etc.) I don't know that anyone has actually searched 25 full plies from the start positions however... It would be extremely slow.

With traditional search (null move on, LMR on, etc.) I have done a 53 ply search using Stockfish. I am pretty sure that others have gone deeper. Note that the search took 28 days (ran for thirty, but never got to the next ply).

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - acd 53; acs 2405347; bm d4; c0 "e4"; c2 "perft 1 20 perft 2 400 perft 3 8902 perft 4 197281 perft 5 4865609 perft 6 119060324"; c3 "e4"; cce 38; ce 24; id "Fundamental Opening Position"; pm e4 {2379495} d4 {1725526} Nf3 {483679} c4 {479713} g3 {39820} f4 {35589} b3 {27764} Nc3 {13010} e3 {2686} b4 {2458} g4 {2450} c3 {1654} d3 {1649} a3 {1150} h3 {717} a4 {552} h4 {425} f3 {363} Nh3 {82} Na3 {28}; pv d4 Nf6 c4 e6 Nf3 b6 a3 Bb7 Nc3; white_wins 1826279; black_wins 1425008; draws 1430947; Opening Fundamental opening position. Anderssen Opening: General. ; CaxtonID: 0 ECO: A00;

Of course, this proves exactly nothing about checkmates from the root position.

[bob]

Certainly one can't say with 100% accuracy that chess is
drawn because that has yet to be proven, and most likely never will.

no need for 100 pct accuracy with mathematical rigour. Since, 'm
a physicist, and you started talking about what happens on earh,
i challenge you to prove with 100 pct certainty that the sun
is revolving around the earth and not the other way around.
We then are getting in the area of the philosopphy of science,
now i'm not going to quote Feyerabend, but its not always
as easy as you might state. Saying straightaway what i think
of your claims that brute force calculation is needed, well i disagree,
and more politiely, i say/write i would agree to disagree.

Other example of excessive mathematical rigorous demands;
Flipping a coin will result in 50 pct chance getting heads or tails.
ok, another game than chess, but i'm going to give just an example:
If someone says nope the chance is 50.000000001 whereby
1 is approaching infinite, then most people would agree its 50 pct.
Even if someone is saying it's 49,99999 pct whereby the nr
of nines is approaching infinity.

Now if i say i'm 99,99999.... (and so on). pct certain ie have
found on the basis of my research and reasonings that
chess is a draw with the current rules, that's the same as
stating for me it is 100 pct certain. A complete rigorous 'proof' ?
Nope. Did Schaeffer did a *complete* brute force calculation ?
No he did *not*. I have his book, One jump ahead, and
he has used pruning ,and obviously has used endgame bases.
Then he claims he has found the result, checkers is a draw
and anybody believes him because he is a professor.

Well i have found chess is a draw but it's not found
at a university; nevertheless is still intend to write
paper about my findings, although i suspect that
most professors would say its not a proof already
because of the 'not invented here' syndrome.
Without having looked at my data. Why bother with
my data if you already know your answer; "chess
will never be solved' and so on (i disagree).

Then some agreements: yes the minimax depends
on the quality of the eval, while Komodo is not
perfect, the deeper the search, the better it becomes,
at least as a *start* for approaching the syzygy tables.
Again, like i said, if those tables give a draw, then
the result is a draw.

For Merlino, i not only have found chess is not mate
within x moves, i have proven it's never mate.
It's a draw. Maybe you can tell us what is a proof for you;
brute force calculation ? But we know that alfa-beta
is just as good. Alfa beta calculation ? Well i have done
that, my opening database in bb36 is pruned in a similar
way as alfa-beta. Why i use minimax to backsolve
these opening data then ? Answer because they are stored
on disc, just like eg Aquarium is using minimax in Idea.

But why bother with the data huh. I offered to demonstrate
my 30 million posbase where chess has been analyzed
from scratch, much better than eg. the CAP data.
But ofcourse got no PM from anybody. Well no problem, i
will write my article , first at academia.edu, then
maybe later at arxiv at Cornell or so. Those who
disagree may disagree. Same for ME.

So imhjo chess is a draw with 100 pct certainty and i
found that result with quite rigorous computer
analysis already some years ago. But some people
will never believe such results; you might as well
spend your time trying to find flaws in the syzygy endgame
tablebases; they *might* contain errors you know !
well have fun.

jef

PS as for the math people, is Monte Carlo analysis sound ?
If not, how sound is it then ? Can you find a winning strategy
for White with Monte Carlo analysis ? If not, what is
that saying to you ? stuff enough for some fun Phd work
(but the conclusion for chess already is clear for me).
Kuhn and many others have shown that the academic
world usually also consists of biased thinking, take
as example theoretical physics, one group is doing string
theory, the other is fighting it, and doing eg loop quantum
gravity. The truth is in the measurements. Like eg the
results in correspondence chess. Approaching 50 pct.
How much is 2 times 50 ? (question for mr Hyatt)
oh and you may add a % to the result.

It has already been proven that the earth revolves around the sun. Not with hand-waving and assumptions. As far as chess, all you have to do is offer proof that it is a draw. But the proof has to be an actual proof, like the proof showing the speed of light, proof showing gravity bends light, etc. That's nowhere near related to solving chess.

proving EXACTLY how many stars are in the universe might be related, because you would have to count every one, not guess.

"approaching 50%" means nothing.

[JVMerlino]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

25 plies is doable from the opening position, although it would be a traditional selective 25 plies (reductions, null-move, pruning, etc.) I don't know that anyone has actually searched 25 full plies from the start positions however... It would be extremely slow.

With traditional search (null move on, LMR on, etc.) I have done a 53 ply search using Stockfish. I am pretty sure that others have gone deeper. Note that the search took 28 days (ran for thirty, but never got to the next ply).

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - acd 53; acs 2405347; bm d4; c0 "e4"; c2 "perft 1 20 perft 2 400 perft 3 8902 perft 4 197281 perft 5 4865609 perft 6 119060324"; c3 "e4"; cce 38; ce 24; id "Fundamental Opening Position"; pm e4 {2379495} d4 {1725526} Nf3 {483679} c4 {479713} g3 {39820} f4 {35589} b3 {27764} Nc3 {13010} e3 {2686} b4 {2458} g4 {2450} c3 {1654} d3 {1649} a3 {1150} h3 {717} a4 {552} h4 {425} f3 {363} Nh3 {82} Na3 {28}; pv d4 Nf6 c4 e6 Nf3 b6 a3 Bb7 Nc3; white_wins 1826279; black_wins 1425008; draws 1430947; Opening Fundamental opening position. Anderssen Opening: General. ; CaxtonID: 0 ECO: A00;

Of course, this proves exactly nothing about checkmates from the root position.

Precisely. So I wonder if anybody has bothered to do the kind of search that would result in a proof.

[Dann Corbit]

Here's a topical question. My apologies if this is a stupid question or common knowledge....

To what depth has the initial position been searched (presumably by brute force?) to PROVE that a win cannot be forced within that number of moves? In other words, has somebody said "I have proven that it is not possible to force checkmate within N ply", where N is something like 25?

Now that I think about it, I would be kind of shocked if it was even that high a number....

jm

25 plies is doable from the opening position, although it would be a traditional selective 25 plies (reductions, null-move, pruning, etc.) I don't know that anyone has actually searched 25 full plies from the start positions however... It would be extremely slow.

With traditional search (null move on, LMR on, etc.) I have done a 53 ply search using Stockfish. I am pretty sure that others have gone deeper. Note that the search took 28 days (ran for thirty, but never got to the next ply).

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - acd 53; acs 2405347; bm d4; c0 "e4"; c2 "perft 1 20 perft 2 400 perft 3 8902 perft 4 197281 perft 5 4865609 perft 6 119060324"; c3 "e4"; cce 38; ce 24; id "Fundamental Opening Position"; pm e4 {2379495} d4 {1725526} Nf3 {483679} c4 {479713} g3 {39820} f4 {35589} b3 {27764} Nc3 {13010} e3 {2686} b4 {2458} g4 {2450} c3 {1654} d3 {1649} a3 {1150} h3 {717} a4 {552} h4 {425} f3 {363} Nh3 {82} Na3 {28}; pv d4 Nf6 c4 e6 Nf3 b6 a3 Bb7 Nc3; white_wins 1826279; black_wins 1425008; draws 1430947; Opening Fundamental opening position. Anderssen Opening: General. ; CaxtonID: 0 ECO: A00;

Of course, this proves exactly nothing about checkmates from the root position.

Precisely. So I wonder if anybody has bothered to do the kind of search that would result in a proof.

I doubt if anyone will bother with such a search until the hardware improves. I don't think anyone expects to find a forced checkmate within the first 100 plies, or it very likely would have been discovered already. With nothing but Alpha Beta search on current hardware, it would take millenniums to get deep enough to find something interesting (in all likelihood). Now, a super-fast proof search using GPU cards might prove interesting. We have a super fast GPU move generator, but nobody has bothered to write a proof search yet. The latest cards have a form of recursion and they are getting a lot more memory now, so maybe that sort of thing is not far off.

Of course, it is possible that there is a checkmate in the first 25 plies and we just have not found it yet. But I would not want to spend ten years of computer time to find out, since it seems so improbable.

[jefk]

[quote="Dann Corbit"]
Of course, it is possible that there [b]is[/b] a checkmate in the first 25 plies and we just have not found it yet. [/quote]

then all opening theory would be wrong.
But it isn't.
Going a step further, selfmade/computer generated opening theory
also is correct, especially if its wide enough ofcourse
and storing the data on a disk gives you a decision tree
which you can use, a bit similar like hashtables; but
not fast dynamically changing (yet?). In other words we not only
should use game statistics, but also can use the decision tree
with backsolving, yes this is minimax, a similar (= same) minimax
as Neumann talked about and thus it's sound. Yet more
robust if we add game statistics (eg because of missing or
incorrect sidelines in between, and stuff like that).

The bigger the opening database, provided high quality, the better
the predictions for the opening phase of the game. What i found
and this is not suprising, is that Black can equalize. Quoting
Magnus Carlsen in some interview after an important game,
"obviously neither side can win unless a mistake is made"

Talking about proofs, there is a difference between math and
physics. In physics, we talk about a theory,(eg relativity) or
even ' laws' (Newton). A proper theory should be falsifiable
according to the philosophy of science by Popper.

Math is much more rigid, but i wonder whether we need
to adhere to such rigour in computational science. We
do wether predictions, other simulations, and often believe
the results, depending on the accuracy; for which you get
a feel after a while, comparing it with reality.

As for Newton, eg F=M x a(cceler), nowadays we have
the more fundamental quantum mechanics. Can you
prove this Newton law with quantum mechanics ?
Nope, but a statistical derivation is possible just as
a statistical ' proof' of the ideal gas law is possible
starting of with Boltzmann equations. Can you
prove an apple falls to the earth ? Nope, some quantum
mysticists might argue it might fly if you influence
it with telekinetic powers or so; hogwash i would say.
It are not for nothing called Newton's laws.

When using math to describe real world phenomena
the methodology of physics is better suitable than
the rigid math methodology (see also eg Imre Lakatos,
Proofs and Refutations). Now chess is a real world game,
and my preliminary chess laws are
1) action gives reaction, ergo Black can always
have a drawing method from the initial position
2) the outcome of a perfect game is a draw.
3) using deep opening trees eg ply 50=x, it can be inferred that
chess certainly cannot be a mate in x (50) from the start.

ad 3) claiming that there might be unexplored sidelines is
erroneous, because you go outside the alfa/beta limits.
where there is nothing to be found.

As for the experiments, ie starting from (wide) opening trees,
ask other experts eg Kaufman, whether you can 'solve
chess' as a win for White. Maybe Larry still even believes you
can draw against e4 with the RL Breyer (and maybe that's true).

In the poll starting this thread a majority is stating that
we will ' never solve chess'. Well if they mean it cannot
be solved as a win for White, then i agree. Thus it's
a draw. Yet another thought experiment.

My theory, ie law of chess is that it is a draw. In pure math
just a (strong) conjecture but who cares. With Popper
you now can try to falsify this claim, eg find a winning line
for White. Or try to make apples fly with your mental
powers; good luck and have fun.

Jef

PS as for my suggestions computational sciences don't need
rigid mathematical methodology, i haven't explored this are
further, but maybe some other blokes here do have some
knowledge about such things. Anyway, although we
ofcourse also have mathematical game theory, my
new insight for more complex games is that for such
games with large degrees of freedom (ie possible moves
for Black) we do not have to adhere to rigid math theory
(which might change later anyway as well); already with
other, in fact more common scientific methods, such as
the solid and commonly accepted methods in physics,
we can find conclusions. Any talk about about mathematical
solving or proving thus can be placed in the realm of
Platonic and impractical speculations; another thought
universe indeed.

PS2 ofcourse i need to write down my findings more in detail,
not just state that chess is a draw, but write a comprehensive
article, possibly with the above discussions about methodology
as well, and plenty examples to corroborate the claims.
Initially it won't be a scientific paper, and neither a phd thesis.
So whether some people would disagree with it, i don't care.

[jefk]

[quote="Dann Corbit"]
A proof search might be able to get deeper, especially with something like this GPU move generator: https://github.com/ankan-ban/perft_gpu[/quote]

exactly, the positions can be stored on disk; it's surprising people
somehow always start back with some Ram/hashtable search,
as if that wouldn't be repeating what has been done already
countless nr of times.

My argument is that such a position generator can be combined
with alfa-beta pruning, and thus not using a brute force
method of storing all positions, but only those which count.

Now if you would do that, you would basically get a similar
sort of project as Arshah; although not rigidly alfa-beta, this
thing is storing also humans games including their mistakes
(usually quickly punished by the engine unless kasparovian
sacrifices), and thus is widening the tree considerably.
Not rigidly alfa-beta, but who cares. Have a look
at his work i suggest, ask him if possible to fix his
download installation, and have a look; there is no
way White can achieve a lasting advantage; in chess.

And more in general, probably for other games such as chess
as well. Unless you get a severe reduction of the nr of playable options/moves during the game such as in 4-in-a-row..

jef

PS1 as for methodology Imre Lakatos i mentioned have a look
https://en.wikipedia.org/wiki/Imre_Lakatos
Just blindly following the methods used by Shaeffer and
think they are obligatory for chess is not useful imho.