How close can we come to proving that white draws?

[towforce]

Entering an unassisted engine in ICCF could be a good way to gauge how strong ICCF players are relative to it.

Do we have any way of estimating the elo rating of top level correspondence chess (TLCC)? Since affordable computers became better than humans, has the gap between TLCC and tournament control computer chess been constant?

The correlations in this post suggest that chess becomes drawn at elo rating 5237 - but I'm guessing that TLCC has not reached that level yet?

The ICCF only gives "over the board" ratings - link.

So - we take engines tuned for time controls of, say, 1-3 minutes and let them think for 24 hours per move. Hmmmmm.

We know that elo v time forms an "S" shaped curve - but my personal experience is that engines make fewer mistakes when they have longer to think. 24 hours thinking would probably eliminate most of the blunders, thus making the engines close to unbeatable.

We might be able to find out without an ICCF tournament - let the engines play each other at a time control of 24 hours per move. Just need enough people with powerful computers to be willing to let them work on chess moves for 24 hours a day...

[Dann Corbit]

An engine line that wins 1000 games out of 1000 or that draws 1000 games out of 1000 is not a proof.
Consider that the branching factor of chess is 36 and therefore the branching factor of perfect Alpha Beta is therefore 6 (given perfect move ordering),
The best engines have branching factors of less than 1.5, so what gives?
They are doing unsound pruning like null move pruning, LMR pruning, etc.
These methods do what humans do... They ignore the poor looking moves and put more effort into the good looking moves.
The only problem is that once in a blue moon the terrible looking move is the right one, and until you have exhausted the solution space you have proven nothing.

The fact that great engines almost never lose is not a demonstration that chess is a draw. It is a demonstration that chess (between extremely powerful agents which only examine a microscopic fraction of the possible moves) is a very drawing game.

[towforce]

An engine line that wins 1000 games out of 1000 or that draws 1000 games out of 1000 is not a proof.

I agree. Albert Silver said that nearly all top correspondence games that are completed end in draws. I was just investigating how close top engines are to top correspondence players. The answer is that we don't know, but from what has been said, maybe not very far behind.

Consider that the branching factor of chess is 36 and therefore the branching factor of perfect Alpha Beta is therefore 6 (given perfect move ordering),
The best engines have branching factors of less than 1.5, so what gives?
They are doing unsound pruning like null move pruning, LMR pruning, etc.
These methods do what humans do... They ignore the poor looking moves and put more effort into the good looking moves.
The only problem is that once in a blue moon the terrible looking move is the right one, and until you have exhausted the solution space you have proven nothing.

The fact that great engines almost never lose is not a demonstration that chess is a draw. It is a demonstration that chess (between extremely powerful agents which only examine a microscopic fraction of the possible moves) is a very drawing game.

My personal experience of having chess programs analyse single positions overnight is that it dramatically reduces their likelihood of making a blunder. This could be due to iterative deepening uncovering mistakes that get missed at tournament time controls.

As a man with a lot of chess hardware, you must have some experience of analysing the same position with the same engine on both slow hardware and fast hardware: don't you find fewer blunders on faster hardware? If so, wouldn't you agree that this would improve the chances of getting a draw rather than losing?

[Dann Corbit]

As a man with a lot of chess hardware, you must have some experience of analysing the same position with the same engine on both slow hardware and fast hardware: don't you find fewer blunders on faster hardware? If so, wouldn't you agree that this would improve the chances of getting a draw rather than losing?

I have analyzed individual positions for more than a week.
Deep analysis will mean fewer blunders. This is due to how reductions work. If we search longer and longer and a tactic is missed, eventually the depth may overcome my reductions and I may find a blunder because of a very clever tactic.

It is also true that deep searches may turn up brilliant moves due to the same mechanism.

I think it is no different than human chess in this aspect:
The longer you think about something the better your move choice.
If you analyze 10,000 bullet chess moves you will find more errors than if you analyze 10,000 correspondence chess moves for that reason.

You are also increasing your probability of winning.
In general, I think that the deeper your searches the better your chance of winning and if your searches are twice as deep as your opponent you have a very good chance of winning.

I think that we have several effects that add to the notion that chess is drawn that are (possibly) somewhat misleading.
The top experts are all using the top engines to help them analyze. I think that this equalizes the field to a large degree.
The net effect of this is that we have a very large pool of very nearly equal players. What is the expected outcome under this scenario?

Another factor (in which I am a guilty party) is that book makers sought fairness and in doing so looked for openings with scores very close to zero.
This is another way of saying we collected drawish openings because we wanted to try for fairness. Some books were entirely constructed from drawn game collections. This is another way of bending the needle towards "chess is a drawish game".

Now, all that having been said, I guess that chess is a draw with perfect play. Do not imagine that I am arguing against that possibility ( or even probability ). However, one should not confuse "horse sense" with "proof"

[jefk]

back to the topic of the this thread....
Whether you like it or not from a math point of view,
it's related to some pratical experience in the game of chess.
https://en.wikipedia.org/wiki/First-mov ... e_in_chess

For a mathematical 'proof', as i suggested earlier, the easiest
way imho is not with computer calculation, whether it's
with brute force, or using tricks as graph theory (*).

What i would suggest in math, although not an expert, is
that there is a class of games, where can be logically derived
from the rules (and possibly with some way of (backward/complete)
induction, that the first move is an advantage, and with best play
cannot lose. Think of tictactoe maybe, and then expand upward
in complexity. In other words, we need to show that in such
a game, by principle, the firstmover can avoid a loss (thus there
is (probably) no zugzwang, or other disadvantage for the first move
player in such games, although there still can be a win for the
second player if the first player makes one -or more- mistakes
(in practical, human chess, it often means more than one (little) mistake.

Conjecture 1): there exist a class of games (as described above)
with such an 'advantage' for the first move, that in principle
the first mover with perfect play cannot lose.
Yes this conjecture nr 1 is a rather broad one, i must confess but
right now i don't know of a better word in the discipline of math/game theory
NB don't lecture me about what conjecture can mean in urban slang
or whatever; i'm now talking math (almost upon request) so look it up
https://en.wikipedia.org/wiki/Conjectur ... onjectures

conjecture2) for lots of such as on above conj1) games,
starting from the most simple ones, it's possible to derive
with logical reasoning that the first mover indeed cannot
lose, and thus such a game indeed falls under the class (as in conj1);
this looks like circular reasoning (tautology) but it's not.

For the rest i leave it to the math professors
(not the programmers, although such things become interesting
in the broad field of logical AI, not simple chess algorithms)


(*) in general within game theory, the field of graph/network
theory seems to be coming up as an important/useful discipline
https://www.or2018.be/slides/Ljubic.pdf
So also in chess this field is coming up
https://www.or2018.be/slides/Ljubic.pdf
https://blogs.cornell.edu/info2040/2017 ... ibly-more/
In chronological order:
https://arxiv.org/abs/math/9905198
https://www.jstor.org/stable/10.4169/co ... .278?seq=1
http://snap.stanford.edu/class/cs224w-2 ... -final.pdf
https://syncedreview.com/2020/11/06/dee ... landscape/

Two tools

https://www.sciencedirect.com/science/a ... 1018301687
Maybe interesting for (AI) programmers still interested in chess but
becoming bored with simple search algorithms:

PS apparently in the zipproth/cerebellum some sort of network
is used (in the backsolving) but it's still 'brute force' ofcourse.
Although (DC) it's not about draw games (like apparently in your CAP)
but -like normally in chess opening theory- about trying to seek
a fundamental advantage from the start with an optimal opening strategy
(NB forgot to mention earlier as 7th project, Chess Assistant, the only
program to my knowledge where you can combine stuff as statistics
and score (eg. from CAP) but then the minimax (as in Aquarium) didn't
work in the versions i (years ago) i looked at (something to fix maybe !??!!
Or update Aquarium to also being able to combine score with statistics
and (as i suggested earlier, 'sharpness').

[OneTrickPony]

Finding a proof seems pretty hopeless to me.
We just don't have any math tools suited for this kind of task. We are left with a situation where engines will get strong enough to guarantee a draw but it's going to be impossible to prove they are 100% correct.
I would start with something simpler than chess. Let's try to proof something like 5vs5 rook endgame is a draw:
[d]1k2r3/ppppp3/8/8/8/8/PPPPP3/1K2R3 w - - 3 26

It just seems hopeless to me. I am yet to see a convincing attempt which is not based on:

1)full search
2)game being so trivial that math tools work for it but wouldn't work for a more complicated game.

It's a bit similar to Goldbach hypothesis (the one about prime numbers). We know it's true, we can verify it for very large numbers and when we graph it it's clear that the bigger the number the more ways there is to satisfy the hypothesis. Still, searching deep enough and seeing how obvious it is is not enough for a proof. For the purpose of this task chess is infinite search space as well (at least for foreseeable future it will stay that way) and we know way more about behaviour of prime numbers than we do about chess at least as far as formal math goes.

[jefk]

onetrickpony,
well (again) i suggest / hinted first, to look /trying to prove
a first move advantage. second, to start with looking at simpler
games than chess; make a smaller board, and simply the rules.
Then find a logical derivation for such (an exceptional) game that the first
mover has an advantage ergo cannot lose,
If you like you then also could try to expand the
board size, and by complete induction, still prove it;s a 'first mover
advantage' game, even if it would be an n*n game.

Don't be awed by infinity, in number theory there are converging series
eg 1/2 + 1/4 + 1/8 + 1/16 etc and you don't have to calculate this brute force.
The solution is proven to converge and the answer is 2.
There are lots of such examples.
and chess does not even can have an infinite nr of moves, (if Black wants to draw,
i think this has been proven with the help of the 3 move/position draw repetition
rule; or otherwise it's a conjecture because of the 50 move endgame draw rule



But anyway, i'm not a math professor. and not these days am
going to work on that (although i'm a little bit intrigued, i must confess).
Like you may have noticed, i still do correspondence chess,
but in the meantime i'll keep watching this forum, although
its mainly about chess, and when using my suggested method
it might become purely gametheory/math, not much related
to chess anymore. maybe something for the programmer subforum
just a suggestion, anyway good luck (you and/or others)

[jefk]

here's a tentative 'proof' , first for some class of
(more simple) games than chess, with a clear first
move advantage, to also actually 'prove the first mover
indeed has the advantage (even for math fundamentalists:

Lemma 1) assume a game where the first mover always can win
(which you can prove), eg fill in four quadrants in a rectangular
and the last player is losing per definition; then the
first player always wins, and per definition has
a (in fact a big) first move advantage. 4-in-arow
is a more complicated example, but anyway the
first mover obviously has the advantage)

Corollary 2) assume a game, where the first mover cannot always
win; then the only (or at least an important) logical definition
of a first move 'advantage' is to have more options available.
With random play then the first mover also what have
a statistical advantage, but statistics (as in chess) is not a proof.
Define the nr of options as the nr of legal moves, then
when the first mover has dimished the nr of options for the second
player(eg squares to move to or whatever) then it's proven .

3) Eureka

Now for a more complicated game as chess, i'm not sure yet if
Black has less options (less legal moves) in all situations (maybe not)
NB in the first stages of the opening, Black ofcourse has
the same nr of options as White. However this *may* become
less after a while (hint look at pawn moves, a Black pawn can be
restricted in its mobility by a White pawn).
So then we have already proven a White advantage,
but then, back to this tread, this means White cannot lose,
ergo can always win! (QED Eureka, if you believe it or not)

PS if and only if the above wouldn't work (nr of legal moves),
then we could diminish the nr of 'options' for Black with obviously
tactical mistakes within ply 30 or so (eg. blundering a piece, and then
again Black gets after while less options. However then ofcourse
some math fundamentalist may argue that there are tactical
sequences thinkable longer than 30 or so, which means we
still cannot prove/demonstrate a White advantage.
hmm i couldn't care less about it, because i think the
pawn moves have already maybe done the trick.
(Feel free trying to shoot a 'hole' in my 'proof' )

"pawns are the soul of chess" (Philidor)

[towforce]

in general within game theory, the field of graph/network
theory seems to be coming up as an important/useful discipline
https://www.or2018.be/slides/Ljubic.pdf
So also in chess this field is coming up
https://www.or2018.be/slides/Ljubic.pdf
https://blogs.cornell.edu/info2040/2017 ... ibly-more/

Graph theory is probably the "obvious" place to look for answers, but I am not optimistic. Four years ago, I found myself resolving a big Hamiltonian path, and I found that none of the well-known graph theory algorithms were able to do it. However, I tried with a SAT solver, and found that I was then able to solve the problem.

For me, the resolution (if anyone bothers to do it) is likely to come from a way of bypassing the size of the game tree - e.g.

1. Extension of things that can easily be proved (e.g. proving that the conditions required to win material don't exist in the opening position)

2. Finding an emergent pattern (I explained in detail in the "Is Chess Solved" thread why I think that chess is likely to have an emergent pattern which is a lot smaller than you'd expect). There are problems: there's no guarantee that an emergent pattern exists, or even how big it would be if it does exist. Also, it might be difficult to prove that it applies to all positions. The good news is that if you can solve chess this way, you can probably then solve most complex systems that aren't random

[jefk]

pfew, towforce,
impressive, i'll have to look up your posting
in a older 'solving chess' thread to read about
emerging patterns.

Meanwhile, some here suggested that proving that
White can always draw would be an important first
step, and i'm close to already have proven this now
(in my previous posting).

Yet, unfortunately, after this step, the second step
in the actual game of chess (not a game where White
always can win) becomes a lot harder, i think.

But you climb a mountain step by step
(Chinese saying)

PS those who suggest we will never solve chess
or not within trillions of years or so, obviously don't
believe in the socalled 'singularity' (personally i'm
also a bit skeptic about some expectations about
AGI and later possibly superintelligence, but that's
another story. In our simple AI fruitfly game of
chess improvements have gone fast last decades,
one unexpected step by such another but different step
again, but nevertheless fast (even also in Go, remember?)