Chess will never be solved, here's why

Sort:
MARattigan
tygxc wrote:

#201
The vast majority of the positions counted by Tromp make no sense at all with multiple excess promotions. ...

What do you define as an excess promotion?

playerafar

Idea:
Say you could get the 10 to the 45th power - down to 10 to the 35th power.
Or by having a computer do some of the work - like eliminating a gigantic number of positions as solved because they're Superflous.
All kinds of Lone King situations - not to be worried about because they're stalemates or mates or hopeless for Lone King  ...
or Illegal  !
A computer could find a Lot of those !  
but doesn't have to be 'individual cases'.  It could generalize many positions.

But then - if you still have 10 to the 35th ...
that's still Way Too Big a number ...  happy.png

playerafar

In theory - what number could be 'manageable' ?

MARattigan
playerafar wrote:

...
And the number of positions would have to be multiplied by 2 - because it could be either player's move.  That's neater. 

The player on the move is already included in Tromp's figure.

Strictly speaking you should have said approximately 2 (as I should have said approximately 100 to take account of the 50 move rule).

E.g. These board layouts are associated only with positions with White on the move

 

 

And under competition rules the former is associated only with positions with a ply count divisible by 4 and the latter only with positions with a ply count equal to 0.

More germane any board layout in which a king is in check can be associated only with a position in which the owner of the king has the move.

playerafar

In all mates - its nobody's move.  happy.png
In all checks - its one person's move.

Gosh - a computer well programmed could eliminate so many Illegal positions !
Its a project in itself - putting an upper bound on them.

tygxc

#205
An excess promotion is a promotion to a piece needing to borrow from another box of 32 chess pieces.
Look ar the John Tromp homepage for a random position counted by him.
http://tromp.github.io/

See the excess promotions. These positions have no relevance at all solving chess.

tygxc

#207
The number of legal & relevant chess positions is manageable: 5 years on 3 cloud engines.

tygxc

#209
The upper bound 3.8*10^37 contains legal positions only.

MARattigan
tygxc wrote:

#205
An excess promotion is a promotion to a piece needing to borrow from another box of 32 chess pieces.
Look ar the John Tromp homepage for a random position counted by him.
http://tromp.github.io/

See the excess promotions. These positions have no relevance at all solving chess.

Many practical games of chess have resulted in excess promotions, some in multiple excess promotions. I think most people will have used upside down rooks to represent queens at some time.

Why do you think they are irrelevant in perfect chess?

 

MARattigan
tygxc wrote:

#207
The number of legal & relevant chess positions is manageable: 5 years on 3 cloud engines.

#209

The upper bound 3.8*10^37 ...

Have you decided to revert to basic rules?

playerafar
tygxc wrote:

#209
The upper bound 3.8*10^37 contains legal positions only.

Ah ! Interesting !  Less than 10 to the 38th positions !
(I can't resist)  "Impressive.  (one eyebrow up) - Intergalactic travel requiring less than 300 years!"

Elroch
MARattigan wrote:

@playerafaer re #200

John Tromp has probably done the most work on this and gives a provisional upper bound of 10^45.888 legal positions.

See https://tromp.github.io/chess/chess.html section Number of chess diagrams and positions.

That is under current basic rules. It would need to be multiplied by 100 if the 50 move rule is added (as it is in competition rules or basic rules prior to 2017) and by a lot more if the triple repetition rule is taken into account (same comment). But the triple repetition rule can be ignored in weakly solving chess under either set of rules.

The triple (or other number) repetition rule is irrelevant theoretically (i.e. does not affect the value of any position) as long as there is an n-move rule, like the 50 move rule (and also vice versa). The n-move rule could be absurdly large if desired (or even, for theoretical purposes, by defining a game that never ends to be a draw - there is no formal problem with allowing games that have infinite numbers of alternating moves.  The latter might be considered the most natural definition of a draw in a game like chess, if not ideal for practical play where infinite numbers of moves tend to be difficult to fit in, even with blitz finishes happy.png )

The reasoning is that if a player has nothing better to do that repeat position or allow their opponent to repeat position, then it is impossible for them to have a forced win (as long as they have played accurately thus far).  This is formally proved by observing that perfect play always has a min-max distance to victory which falls every move (with players fighting to make it nearer or further in the obvious way).

MARattigan

@Elroch

Is that not what I said?

For a strong solution the triple repetition rule may be relevant as a correct solution needs to deal with all positions, whether arrived at by accurate play or not. 

With this partially specified position

 

White to move, ply count=97
 

 
The evaluation would be win under basic rules with the 50 move rule added.

With the triple repetition rule also added the evaluation would still be win unless the same board layout but with the white king relocated to c8 and Black to play or the same board layout but with white king relocated to c8 and the black king relocated to a1 and White to play  had occurred twice before, in which case the evaluation would be draw.

In the example shown White's win can disappear owing to repeated positions en route to the fastest win. In other positions the win may still be there but the moves would have to change. 

The Syzygy tablebases strongly solve basic rules chess or basic rules chess + 50 move rule for up to 7 men (though they may give an incorrect win evaluation, the correct evaluation can be determined by following the recommended moves) but they don't strongly solve competition rules chess. 

DiogenesDue

...an example of a position that Tygxc considers absurd and irrelevant due to excess promotions (two bishops of the same color).

MARattigan

I believe I've seen a published game with 5 queens on the board.

There's also this with 6 same colour knights

https://www.bing.com/videos/search?q=nakamura+crafty+6+knights&qpvt=nakamura+crafty+6+knights&view=detail&mid=2F6D1B2D9ED4947135C32F6D1B2D9ED4947135C3&&FORM=VRDGAR 

While Nakamura was obviously taking the pr*verbial at the end, with my limited look ahead capability, it looks like he's still playing perfect moves, so that's not relevant.

MARattigan
playerafar wrote:

In all mates - its nobody's move. 
In all checks - its one person's move.

Gosh - a computer well programmed could eliminate so many Illegal positions !
Its a project in itself - putting an upper bound on them.

I used the term 'has the move' which is defined in the FIDE laws to be the case when the opponent has 'made' his move. So in FIDE speak a mated player has the move, it's just that he has no moves he can make.

playerafar

Regarding a game being potentially infinite in length -
because of a 50 move rule - I'm just simply pointing out that isn't possible.  (yes might have been stated here already)
The 50 moves count only starts over - if there's pawn motion - or a capture (if I remember correctly and if it hasn't changed)
that makes the number of 50 move startovers in any game very very 'finite'.  
With a theoretical maximum of 96 pawn moves (since the rows of pawns oppose each other - that 96 figure can probably be proven to be impossibly high) and a maximum number of captures to be 30.
Which actually happens constantly in chess. 
That 30 figure is not theoretical. 
The two Kings left - masters of the Nothing they survey.

From there - (yes I realize this was very possibly mentioned earlier here - but if it was I'm still putting it my way)
Its upper bound on game length is  50 X (30 + 96) = 6300 moves. 
That's two ply of course.  So 12,600 'ply'.  
So at three days per ply ('Daily Chess') ...  that's 37,800 days.  
Less than 110 years for the game !  

tygxc

#224
The longest possible chess game with the 50 moves rule is 5898.5 moves.
However that involves sequences of 49 meaningless moves shuffling around before making an irreversible move: capture or pawn move.
The world record of the longest real chess game was Nikolić–Arsović, Belgrade 1989: 269 moves.

tygxc

#222
Yes, some positions with 4 or even 5 queens or 3 knights can be relevant and thus are not counted. But on the other hand a number of positions with very weird pawn structures, like quadrupled pawns is counted and does not occur in any real game. So the upper bound without excess promotions is a good measure. It is too large, it leaves out some relevant positions, but it counts in some non relevant positions, so it is about right for the purpose.

tygxc

#216
Again: see this scientific paper
https://arxiv.org/pdf/2112.09386.pdf

It gives the upper bound of 3.8521*10^37 legal positions.

32 men 1.89 × 10^33
31 men 1.71 × 10^34
30 men 1.64 × 10^35
29 men 1.53 × 10^36
28 men 5.46 × 10^36
27 men 1.05 × 10^37
26 men 1.08 × 10^37
25 men 6.14 × 10^36
24 men 3.19 × 10^36
23 men 5.66 × 10^35