How many distinct chess games are possible, and which is the longest?

SeanEnglish

Haha, KiloNewton...

Your solution definitely shows it can be done, but its kinda funny how not talking the h2 pawn earlier ended up making it impossible to reach the exact position at the end(but yeah, you definitely don't have to make a new one, the point is there)

Now what about if no pawns promote? are sextupled pawns on the a file still possible? 

kiloNewton
SeanEnglish wrote:

Haha, KiloNewton...

......you definitely don't have to make a new one

if you want to promote, you can move all 6 pawns of a-file one one square forward.

kiloNewton
SeanEnglish wrote:

...

Now what about if no pawns promote? are sextupled pawns on the a file still possible? 

hmm, its a tricky one. need thinking for a while.

Remellion

Impossible. The black f, g, h pawns will not have enough white pieces to capture to all be captured. At minimum 2 must go to the c-file and 1 to the d-file - that's 11 captures and only 9 white units missing. (c and d are not typos - the a through e pawns are assumed to be captured on their own files as well.) It's an old problem and very basic.

I suppose the next step up would be this, still rather simple puzzle. (Taken from this thread, post #30 at present; courtesy of one TheMushroomDealer.)

Legal? If yes, minimum number of moves to reach?

kiloNewton

@131 possible

kiloNewton



Remellion

Good efficient setup!

But not optimal. The lower limit is 32.0 moves. It can be proven, and also constructed. (Obviously not a unique PG, but still mildly challenging.) Can you do it?

kiloNewton

34 moves



close huh?

SeanEnglish

33.5 but I cannot for the life of me figure out how to get it down further.

Similar to yours Kilo, but I wanted to make sure white's c-pawn and blacks f-pawn get their initial double moves in.

SeanEnglish
Remellion wrote:

...The lower limit is 32.0 moves. It can be proven, and also constructed...

haha, I would like to see an example in chess like this that can be proven, but not constructed("So, I can prove to you that this position can be reached in 40 moves, but its impossible to actually construct a game that does it.")

I think you might have meant "32 was proven to be a lower bound, then a game with 32 was constructed, which gave us an upper bound. since the upper bound and lower bound agree, its exactly 32" I just thought it was kind of funny because while I'm not playing chess, I'm a student of mathematics and unlike chess, there are many instances where you can prove existance and also prove unsolvability(such as the Fundamental Theorem of Algebra garuntees the existance of roots of complex polynomials, but the unsolvability of the quintic shows that there's no way to find those roots in general) 

The idea of having something like that in chess though is... silly to me:) 

SeanEnglish

Also, Remellion, lately I've been thinking about where algebraic chess notation could fit into retro problems or problems similar to retro problems. specifically, the fact that the algebraic notation of chess actually holds very little information, and can only be so "slim" if you will, since the starting position is known. So, if given a string like ... 0. Nb5 Rxa2 1. Bxa2 Kxa2, since you don't know what moves came before this, so you recieve much less information about the game.

So, I guess my question for you is(since you seem rather knowledgeable about retros and other such puzzles), do you know if anyone has tried to devise legality puzzles based on algebraic notation? 

kiloNewton

as Remillion said 32 move solution  is constructed - he has the solution.

but i am not asking him to post the solution now.

its better others wreck their brain untill giveup.

kiloNewton

Smile or wreck their brain untill they sleep!

Remellion
SeanEnglish wrote:
Remellion wrote:

...The lower limit is 32.0 moves. It can be proven, and also constructed...


I think you might have meant "32 was proven to be a lower bound, then a game with 32 was constructed, which gave us an upper bound. since the upper bound and lower bound agree, its exactly 32".

Yep, that's what I meant. The bit about construction was just to make sure it's clear I have a solution at hand and not just a bunch of words. Chess has finite states - I don't think it's the case that there are true but unprovable statements about it (within constraints that castling is legal unless proven, en passant illegal unless proven, 50-move convention, etc).

SeanEnglish wrote:

Also, Remellion, lately I've been thinking about where algebraic chess notation could fit into retro problems or problems similar to retro problems. specifically, the fact that the algebraic notation of chess actually holds very little information, and can only be so "slim" if you will, since the starting position is known. So, if given a string like ... 0. Nb5 Rxa2 1. Bxa2 Kxa2, since you don't know what moves came before this, so you recieve much less information about the game.

So, I guess my question for you is(since you seem rather knowledgeable about retros and other such puzzles), do you know if anyone has tried to devise legality puzzles based on algebraic notation? 

Try this thread? The objective is to find from a set of moves in some unknown position, the (minimum) number and identity of incompatible moves such that the rest are legal. e.g. which is invalid: white to move {Ka1+ Ka3+ Kb2+ Kc1+}; or one in descriptive {KxN# KxB# KxR# KxQ#}

Also, there are synthetic games, where the complete score of a game is determined by giving a set of moves. e.g. Find the game ending in 5...Rh1#. Or another in 5. Ng3#. Google "Alain Brobecker" - his website has a good listing of those.

Uncia_Uncia
That 32.0 move construction required some fine tuning. I can't post diagrams on my phone, so I'll just dump the moves here: 1. b4 g5 2. h4 a5 3. hxg5 axb4 4. c4 f5 5. Rh4 Ra3 6. Re4 Re3 7. dxe3 fxe4 8. Nc3 Nf6 9. gxf6 Bh6 10. a4 Bf4 11. a5 h5 12. a6 h4 13. a7 h3 14. a8=Q b5 15. Ra6 h2 16. Rd6 exd6 17. Qc6 dxc6 18. exf4 h1=Q 19. g4 Qf3 20. exf3 Rh7 21. Be3 Rf7 22. Bc5 dxc5 23. Qc2 bxc3 24. Ne2 Qd5 25. cxd5 Bf5 26. Nc1 Nd7 27. Bc4 Nf8 28. Nd3 Ne6 29. gxf5 exd3 30. dxe6 dxc2 31. Ke2 bxc4 32. exf7+ Kd7
Remellion

Diagram for Uncia_Uncia's solution:

 

The moves speak for themselves - 32.0 construction. Well done!

The proof is loosely as thus: Start with simple inventory. Each side made at least 9 pawn captures, and each side is missing 9 units -> all of the missing units were captured by pawns.

Look at the pawns - the greedy approach of minimising pawn moves is "obviously" best. So we want as many double pawn moves as possible, like SeanEnglish tried. That would be 3 from each side, and that fixes most of the pawn paths, e.g. white c2-c4xdxexf, and d- through h-pawns capturing towards f.

So the issue is how to feed the missing units to the pawns. Rooks take 2 moves each. Bishops take 3 for both (b/c of white c1/black f8 takes 2 moves). Queens at least 1. White b-pawn/black g-pawn is another 1 move. If you were to plot out the squares on which these occur, the remaining 3 captures become quite fixed: two knights take 4 moves (not 3, due to parity arguments) and the promoted a/h-pawns 1 move each (the tricky bit - a8=Q-c6 and h1=Q-f3.)

9P captures + 4P moves + 6 by promoted P + 4N +3B + 4R + 1Q + 1K = 32 ply per side. So the lower bound is set at 32.0 moves for this final configuration.

SeanEnglish

Ahh yes, well done. 32 moves it is. Remellion, most of your proof for the lower bound seems quite solid, but when I was trying to work out a lower bound myself, I was looking at only three moves with the knights. I can see how a parity argument can show that it must be white's move if the board is identical to the original position, but I guess I'm missing how it applies here?

Remellion

Paper and pen. Plot the capture squares for each side. (Uncia_Uncia did converge on the same scheme I had, suggesting it is optimal.) Minimising Q and B moves, and setting the white b-/black g-pawn to die on b4/g5 results in many of the capture squares already taken. Also note which squares the Rs can die on, and then the remaining squares within reach by the Ns are of colours such that an even number of total moves is needed.

OK, maybe "by inspection" would be more accurate but sounds less rigorous. And technically it is still a parity argument. :P

Uncia_Uncia

The knights caused me some headache, as I was bent on using only 3 knight moves. Then I took some time to think and realized that the knights have to be captured on opposite coloured squares, that is, 4 knight moves are needed. Else the other pieces cannot be used optimally. It was a nice construction problem.

Benzodiazepine

No offence, but this is a bit like asking how many distinct games of "Mensch ärgere dich nicht" are possible?

It's plain retarded.

Untracking Comments