Perft(7) challenge position #3

[Ajedrecista]

Hello Yuri:

What is highest number of legal moves in a position, ever observed?

In perft<14, not in puzzles

https://www.chess.com/forum/view/fun-wi ... ible-moves

I have an idea:

1.- Download huge PGN files like CCRL 40/4. There are others like CEGT, Frank's Amateur Schach...

2.- Use Norm's PGN utility 'truncate':

Code: Select all

=========================(50) truncate =============================

"truncate" removes all plies (half-moves) in each game that occur
after a user-specified "maximum_plies". 

Results are not removed. 

"truncate" removes existing "PlyCount" tags.

"truncate" removes comments, nags, variations and major symbolic
annotation symbols (!, !!, ?, ??, !?, ?!, +-, -+, +/-, -/+, +=,
=+, +/=, =/+, =, ~, and N).

Syntax:   truncate filename.pgn maximum_plies

Example:  truncate alpha.pgn 50

Output:   outU.pgn

Comments:

     1. To remove all game moves but leave the results:

          truncate alpha.pgn 0

     2. New "PlyCount" tags can be inserted using the program 
        "plyCount".

====================================================================

Download the whole package of PGN utilities if you have not got them.

I would use truncate file.pgn 13 since you want perft < 14. Make sure that the uncompressed PGN is in the same folder than the PGN utility.

3.- Run the tool Joined from the command prompt. Make sure that the truncated PGN is in the same folder than joined.exe executable. Download link of Joined.

Example run:

Code: Select all

C:\[...]\joined>joined -h
Illegal option: h !
Usage&#58; joined &#91;<*.PGN, *.FEN or *.EPD file>&#93; &#91;-<options>&#93;
Legal options are&#58;
   -p        &#58; Print messages to both stderr and stdout
   -q        &#58; Quit after scanning input file
   -r        &#58; Initial value for random algorithm
   -s        &#58; Print messages only to stdout
   -v<number>&#58; Set verbose level to <number> &#40;default 4&#41;
      The numbers may be added. The numbers are&#58;
       1&#58; Print PGN
       2&#58; Calculate number of legal moves in all positions
       4&#58; Print progress &#40;default&#41;
       8&#58; Print all warnings
      16&#58; Check PGN
      32&#58; Report result = '*'
      64&#58; Get statistics on all types of moves
***** Error exit *****

C&#58;\&#91;...&#93;\joined>joined beta.pgn -q -v126
Scanning file beta.pgn containing 10637 bytes !
Read 12 games with 1384 moves, 264 lines, 10637 bytes !
Got max. 187 moves in game 4 before line 92 !
Got 37861 legal moves in 1396 positons !
Got max. 52 legal moves after move 34 in game 3 line 60 !

Total move statistics&#58;
Pawn moves = 323, Knight moves = 251, Bishop moves = 148
Rook moves = 344, Queen moves = 104, King moves = 232
Check moves = 118, Mate moves = 0, Stalemate moves = 0
Hit moves = 268, En passant moves = 0, Pawn two moves = 76
Short castlings = 17, Long castlings = 1
Promotion to queen = 1, Promotion to rook = 0
Promotion to bishop = 0, Promotion to knight = 0

Total game statistics&#58;
White won = 5, Drawn = 6, Black won = 1
Unknown result = 0, Illegal result = 0, Conflicting results = 0
White mated = 0, White stalemated = 0
Black mated = 0, Black stalemated = 0

Number of games with different lengths&#58;
 87&#58;     2,  93&#58;     1,  95&#58;     1,  99&#58;     1, 101&#58;     1, 107&#58;     1
114&#58;     1, 124&#58;     1, 131&#58;     1, 159&#58;     1, 187&#58;     1


C&#58;\&#91;...&#93;\joined>

Of course you can change the verbosity to speed up things, like -v62:

Code: Select all

C:\[...]\joined>joined beta.pgn -q -v62
Scanning file beta.pgn containing 10637 bytes !
Read 12 games with 1384 moves, 264 lines, 10637 bytes !
Got max. 187 moves in game 4 before line 92 !
Got 37861 legal moves in 1396 positons !
Got max. 52 legal moves after move 34 in game 3 line 60 !


C:\[...]\joined>

You just have to read the line Got max. N legal moves after move ... and that is all!

4.- (Optional): you can open the PGN with a text editor like Notepad++ and go to the line where Joined says that you can find the maximum number of legal moves. Since all games are short (13 plies or less), you can play through the game with a GUI and check the position with a perft counter.

------------------------

I do not know how Joined handles the case where the maximum number of legal moves in the PGN is shared between two or more positions: does it report the first, the last or all positions? I also have other doubt: when you read ... legal moves after move M in game G line L !, this move M may refer to ply. Just check it yourself.

I do not do it myself because I am currently getting astonishing download speeds of circa 25 KB/s, so the step 1 is horribly slow.

As a side note, the current record of legal moves is 218. Please search 218 in your browser in the following CPW page:

chessprogramming - Encoding Moves

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello:

I finally applied my idea. The download was as slow as yesterday.

I am aware that the use of opening books can constrain a lot the variety of paths until ply 13. Anyway, here I go:

Code: Select all

CCRL-404.[1363728].pgn
1,363,728 games.
1,573,163,698 bytes ~ 1500.3 MB.

Code: Select all

C:\[...]\40H-PGN-20160219>truncate

truncate.exe 1.51 (c) 2007-16 Norman Pollock

syntax: truncate filename.pgn maximum_ply

example: truncate alpha.pgn 80

output: outU.pgn

C:\[...]\40H-PGN-20160219>truncate CCRL-404.[1363728].pgn 13

Number of games in CCRL-404.[1363728].pgn is 1363728

Number of games in outU.pgn is 1363728

Number of truncated games in outU.pgn is 1363728

finished: be sure to rename/copy outU.pgn

C:\[...]\40H-PGN-20160219>

Code: Select all

C:\[...]\joined>joined -h
Illegal option: h !
Usage&#58; joined &#91;<*.PGN, *.FEN or *.EPD file>&#93; &#91;-<options>&#93;
Legal options are&#58;
   -p        &#58; Print messages to both stderr and stdout
   -q        &#58; Quit after scanning input file
   -r        &#58; Initial value for random algorithm
   -s        &#58; Print messages only to stdout
   -v<number>&#58; Set verbose level to <number> &#40;default 4&#41;
      The numbers may be added. The numbers are&#58;
       1&#58; Print PGN
       2&#58; Calculate number of legal moves in all positions
       4&#58; Print progress &#40;default&#41;
       8&#58; Print all warnings
      16&#58; Check PGN
      32&#58; Report result = '*'
      64&#58; Get statistics on all types of moves
***** Error exit *****


C&#58;\&#91;...&#93;\joined>joined outU.pgn -q -v62

&#91;...&#93;

Read 1363728 games with 17728464 moves, 20402528 lines, 463639374 bytes !
Got max. 13 moves in game 1 before line 14 !
Got 563250076 legal moves in 19092192 positons !
Got max. 61 legal moves after move 12 in game 987518 line 14758440 !

Of course -v62 means options 2 + 4 + 8 + 16 + 32 = 62 (option 2 is the key in this task). By the way, I got a lot warnings of this kind:

Code: Select all

Got FEN tag <rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1> !

It is good to see that (17728464 moves)/(1363728 games) = 13 moves/game, but the meaning of move is ply here.

Well, the answer to Yuri's question (at least in this PGN) is max.[perft(1) | all positions of all games (plies = 13)] = 61.

I tried to open the truncated PGN of 442.2 MB with Notepad++ 6.9.1 but the file was too big, so I had to split it in five smaller files using a Norm's TXT utility called txtSplit:

Code: Select all

C:\[...]\40H-TXT-20120304>txtSplit

txtSplit.exe 1.01 (c) 2011-12 Norm Pollock

syntax: txtSplit filename.txt split_num

example: txtSplit alpha.pgn 3

output: pt1.txt, pt2.txt, ... , pt5.txt

comment: the split number must be 2-5

C:\[...]\40H-TXT-20120304>txtSplit outU.txt 5

finished: be sure to rename/copy pt*.txt

C:\[...]\40H-TXT-20120304>

Then Notepad++ managed to open the smaller files. Going directly to pt4.txt and looking for the desired line and ply 12 of the game (the sixth black move):

[d]r1b1kb1r/pp1nqppp/2pppn2/7Q/2BPPB2/2N5/PPP2PPP/R3K1NR w KQkq - 5 7

[pgn][Event "CCRL 40/4"]
[Site "CCRL"]
[Date "2012.08.11"]
[Round "173.3.893"]
[White "MicroChess 1976"]
[Black "NEG 0.3d"]
[Result "1/2-1/2"]
[ECO "B10"]
[Opening "Caro-Kann defence"]
[WhiteElo "573"]
[BlackElo "540"]

1. e4 c6 2. Qh5 d6 3. Bc4 e6 4. d4 Qe7 5. Bf4 Nd7 6. Nc3 Ngf6 7. Qg5
1/2-1/2[/pgn]

Please remember that the PGN is truncated. The whole PGN is here, once I downloaded the games of MicroChess 1976, which has less games in the database than NEG 0.3d:

[pgn][Event "CCRL 40/4"]
[Site "CCRL"]
[Date "2012.08.11"]
[Round "173.3.893"]
[White "MicroChess 1976"]
[Black "NEG 0.3d"]
[Result "1/2-1/2"]
[ECO "B10"]
[Opening "Caro-Kann defence"]
[PlyCount "72"]
[WhiteElo "573"]
[BlackElo "540"]

1. e4 c6 2. Qh5 d6 3. Bc4 e6 4. d4 Qe7 5. Bf4 Nd7 6. Nc3 Ngf6 7. Qg5 b6 8. Nf3
c5 9. Nb5 Nxe4 10. Nc7+ Kd8 11. Nxe6+ fxe6 12. Qh5 Rg8 13. Qxh7 Nef6 14. Qg6 a5
15. c3 cxd4 16. Nxd4 e5 17. Nc6+ Kc7 18. Nxe7 Rh8 19. Nd5+ Kc6 20. Bb5+ Kxb5
21. a4+ Ka6 22. Nc7+ Kb7 23. Nxa8 exf4 24. Qf5 Kxa8 25. Rd1 Bb7 26. Rd4 Bxg2
27. Rg1 Bc6 28. Rg6 f3 29. Rc4 Bd5 30. Rc8+ Kb7 31. Rd8 Nc5 32. Qc8+ Ka7 33.
Qc7+ Ka6 34. Qc8+ Ka7 35. Qc7+ Ka6 36. Qc8+ Ka7 1/2-1/2[/pgn]

Just computing some perft values of the position with JetChess:

Code: Select all

r1b1kb1r/pp1nqppp/2pppn2/7Q/2BPPB2/2N5/PPP2PPP/R3K1NR w KQkq - 5 7

perft(1) =              61
perft(2) =           1,398
perft(3) =          76,443
perft(4) =       1,934,131
perft(5) =      98,188,411
perft(6) =   2,674,225,444
perft(7) = 128,746,690,662

I hope no typos.

Regards from Spain.

Ajedrecista.