Houdini 6 has been released

[Dann Corbit]

From a mathematical point of view, chess is a finite game and can be trivially solved by application of the minimax algorithm, but I don't believe you can produce a proof that chess is a draw which can be verified within our lifetime. Zermelo's theorem will in any event not be of help in tackling the computational effort. So chess may be "solved" according to some definitions, but it is not "weakly solved" within the normal meaning of that term.

again a very definite statement, but eg. Prof Jaap vd Herik states that chess probably will be solved in a few decades, with the developments going faster than expected; that is, weakly solved, i presume.
Minimax ? i thought that alfa-beta is universal validity ? maybe not for some math purist, but for a weak solution that doesn't matter.

Then i don't think it's a pure computational problem, i once had this discussion with Bob Hyatt, showing him some games which have been solved without brute force computation. So i do think one of the theorems of Zermelo can be applied, at least in a common sense matter.
If you cannot find a winning advantage (from the opening) than it's a draw, simple as that. Look at some results H6 vs Kom11, only one win out of 33 games. We are approaching the dreaded draw zone...

If the two strongest engines have a billion draws in a row and zero wins between them at very long time control on a giant array of CPU cores, it won't prove anything as far as weakly or strongly proven result for chess.

That is because strong chess engines do unsound pruning because it wins more games. But for the same reason, these same engines can miss important tactical shots. Sometimes, to solve a problem, you have to turn off or at least turn down null move pruning, for instance.

One can argue that the game may be "practically proven" and in a common sense sort of way this is true. But to actually prove a game it has to be exhaustive. So, for instance, alpha-beta pruning can be used because it is sound, but null move pruning cannot be used in a proof.

The fabulous depths and results that you see with advanced chess engines is due to un-sound pruning. Mathematically, it does not produce the same result as a mini-max search {as alpha-beta does} which is to say it does not always produce the right answer. What it does do is to help find a really good, really deep answer really fast.

[syzygy]

From a mathematical point of view, chess is a finite game and can be trivially solved by application of the minimax algorithm, but I don't believe you can produce a proof that chess is a draw which can be verified within our lifetime. Zermelo's theorem will in any event not be of help in tackling the computational effort. So chess may be "solved" according to some definitions, but it is not "weakly solved" within the normal meaning of that term.

again a very definite statement, but eg. Prof Jaap vd Herik states that chess probably will be solved in a few decades, with the developments going faster than expected; that is, weakly solved, i presume.

If Van den Herik really made such statement, then I hope he was not serious. Perhaps looking for funding... which does not make saying such things excusable though, for someone in his position.

Minimax ? i thought that alfa-beta is universal validity ? maybe not for some math purist, but for a weak solution that doesn't matter.

Who cares about the advantages of alpha-beta if we don't care about running time anyway? This is my point: sure, chess is a trivial, finite problem in a mathematical sense: use minimax or use alpha-beta, I don't care if running time is not important, just don't use something like a hash table that will destroy any mathematical certainty with its hash collisions. But from a computational point of view the problem is simply very much infeasible with current technology (and also with quantum computing if that should ever become practical).

Then i don't think it's a pure computational problem, i once had this discussion with Bob Hyatt, showing him some games which have been solved without brute force computation. So i do think one of the theorems of Zermelo can be applied, at least in a common sense matter.

In case of a finite game you can turn Zermelo's theorem into something constructive. But what you end up with is minimax. Minimax is clearly not going to cut it. Alpha-beta won't do, either.

Sure, I cannot exclude that someone may discover a brilliant formula for quickly calculating provably optimal moves, but at this time there is no shred of evidence that a formula like that may exist for chess. Certainly any serious prediction of "chess will be weakly solved within XX years" cannot rely on the hope of a totally unexpected mathematical miracle being discovered.

If you cannot find a winning advantage (from the opening) than it's a draw, simple as that. Look at some results H6 vs Kom11, only one win out of 33 games. We are approaching the dreaded draw zone...

Which perhaps proves something for you, but not for any mathematician. Again, for your purposes chess may have been solved a decade ago, but "weakly solved" has a particular meaning and chess very definitely has not been "weakly solved" and will not be "weakly solved" within our lifetime (a very safe bet).

[duncan]

personally i still think, that with application of Zermelo's theorem,
chess is solved and the outcome is a draw of course.
But i'm not going to repeat my arguments

why would Zermelo's theorem lead you to think chess is a draw ?
wiki quote

When applied to chess, Zermelo's Theorem states "either white can force a win, or black can force a win, or both sides can force at least a draw".[4][5]

[duncan]

Then i don't think it's a pure computational problem, i once had this discussion with Bob Hyatt, showing him some games which have been solved without brute force computation.

can you link to some games. ?

Look at some results H6 vs Kom11, only one win out of 33 games. We are approaching the dreaded draw zone...

if of the 10^120 chess games. 10^6 are won for white all more than 50 moves, is this phenomenon not something you would expect to see ?

[syzygy]

Then i don't think it's a pure computational problem, i once had this discussion with Bob Hyatt, showing him some games which have been solved without brute force computation.

can you link to some games. ?

A famous example of a game "solved" without brute force computation is Hex:
https://en.wikipedia.org/wiki/Hex_%28bo ... and_proofs

Although it can be proven that the first player has a winning strategy, we do not know that strategy. Hex is therefore only "ultraweakly solved".

A famous example of a game "strongly solved" (known optimal strategy from every position) without brute force computation is Nim:
https://en.wikipedia.org/wiki/Nim#Mathematical_theory

[duncan]

eg. Prof Jaap vd Herik states that chess probably will be solved in a few decades, with the developments going faster than expected; that is, weakly solved, i presume.

Prof Jaap vd Herik believes ultimate truth in chess eludes us (..whether win lose or draw for white?)


The Construction of an Omniscient Endgame Data Base.
https://chessprogramming.wikispaces.com ... ournal#8_2

[duncan]

Then i don't think it's a pure computational problem, i once had this discussion with Bob Hyatt, showing him some games which have been solved without brute force computation.

can you link to some games. ?

A famous example of a game "solved" without brute force computation is Hex:
https://en.wikipedia.org/wiki/Hex_%28bo ... and_proofs

Although it can be proven that the first player has a winning strategy, we do not know that strategy. Hex is therefore only "ultraweakly solved".

A famous example of a game "strongly solved" (known optimal strategy from every position) without brute force computation is Nim:
https://en.wikipedia.org/wiki/Nim#Mathematical_theory

are there any chess positions have been solved without brute force computation.?

[syzygy]

are there any chess positions have been solved without brute force computation.?

Sure:
[D]4k3/p1p1p1p1/PpPpPpPp/1P1P1P1P/8/8/4R3/4K3 w - - 0 1
I don't need to exhaustively consider all possible moves or positions to prove that this is a draw with optimal play by black.

[Leo]

This item I found online gives me a feel for how hard it would be to solve chess:

Many show interest in what is to expect from 8-man endings. First, take note that the longest 6-man mate took 262 moves (KRN-KNN). Moving to 7-man endings doubled this value. Second, 8-man tablebases include much more endings with both sides having relatively equal strength. All this gives us a strong hope to discover a mate in more than 1000 moves in one of 8-man endgames. Unfortunately the size of 8-man tablebases will be 100 times larger than the size of 7-man tablebases. To fully compute them, one will need about 10 PB (10,000 TB) of disk space and 50 TB of RAM. Only the top 10 supercomputers can solve the 8-man problem in 2014. The first 1000-move mate is unlikely to be found until 2020 when a part of a TOP100 supercomputer may be allowed to be used for solving this task.

[duncan]

are there any chess positions have been solved without brute force computation.?

Sure:
[D]4k3/p1p1p1p1/PpPpPpPp/1P1P1P1P/8/8/4R3/4K3 w - - 0 1
I don't need to exhaustively consider all possible moves or positions to prove that this is a draw with optimal play by black.

thanks for the position.

do you know if any engines realise it is a draw ?