Author: Bas Hamstra
Date: 08:46:02 11/25/99
Go up one level in this thread
Hi Andreas, Very interesting. Thank you for sharing this interesting data. May I make a suggestion? You did it for an opening and a mate. Could you (if not too much trouble) try it for a couple of random WAC positions? I am curious how the results would vary at realistic non-opening random positions. Regards, Bas Hamstra. On November 25, 1999 at 09:13:15, Andreas Stabel wrote: >I've made a program that searches a position to a given ply and stores all >the different positions in a hash table. This way I can see how effective >hashing would be if it was perfect. > >In the table below the first column is total nodes in the tree without >hashing, the second is unique nodes with the en passant target square >set each time a pawn is moved two forward and the third column is the >number of unique nodes if the en passant target square is set only if >there exist a pawn which is able to hit en passant. > >The reason why column two and three leads to different numbers is if the >en passant target square is set it will lead to a different position from >the same position if it is not set. > >Table from opening position: > | | Unique nodes | Unique nodes >Ply| Total # nodes | ep = pawn two | ep = opposite pawn can hit >---+---------------+---------------+--------------+------------ >0 | 1 | 1 | 1 | >1 | 21 | 21 | 21 | >2 | 421 | 421 | 421 | >3 | 9323 | 8023 | 5783 | >4 | 206604 | 109262 | 77796 | >5 | 5072213 | 1300096 | 877419 | >6 | 124132537 | 14200473 | 9564038 | > >I must say I am astonished by the huge reduction in number of nodes from >column two to three. The only changes I did to my program was to put in >a test in the makemove routine to see if there is a pawn of opposite colour >beside the destination square of a pawn which is moved two forward. If there >is no such pawn, the en passant target square is not set. > >This is a very simple thing to implement and it seems to give a big saving >in the opening phase of the game. Perhaps this is something you should do >in your chess programs. I even would suggest that the PGN (or FEN or EPD) >standard should be changed to demand that the en passant target square only >is legal if there exist a pawn to hit. This way we would get rid of a lot >of ambiguity and unnecessary en passant checking. > >Another thing to note about this table is that the savings compared to no >hash table is enormous. Whith perfects hashing the number of nodes at ply >six is nearly a tenth of the nodes with no hashing. This is even more >apparent if we use a limited tree from an endgame. The table below was >made from a position which has a very limited tree and is a mate in 16. >(It is pretty fun to solve,, so if you haven't seen it before you shoud try.) >Here the saving is a factor of 1200 at ply 19. Perhaps it would be even >greater if more of the pieces were not pawns, because then there would be >more cases where two different move sequenses lead to the same position. > >FEN: 8/1p1p1p1p/3P1P2/pp5P/kp6/1p4P1/1P4P1/2K5 w - - 0 1 >-------------------------------------------------------------------- >Ply | Total Nodes | Factor | Unique nodes | Factor | Total/Unique | >----+--------------+--------+--------------+--------+--------------| > 0 | 1 | | 1 | | 1.000 | > 1 | 6 | 6.00 | 6 | 6.00 | 1.000 | > 2 | 15 | 2.50 | 15 | 2.50 | 1.000 | > 3 | 63 | 4.20 | 45 | 3.00 | 1.400 | > 4 | 104 | 1.65 | 59 | 1.31 | 1.763 | > 5 | 346 | 3.33 | 97 | 1.64 | 3.567 | > 6 | 383 | 1.11 | 109 | 1.12 | 3.514 | > 7 | 614 | 1.60 | 153 | 1.40 | 4.013 | > 8 | 837 | 1.36 | 194 | 1.27 | 4.314 | > 9 | 2192 | 2.62 | 319 | 1.64 | 6.871 | > 10 | 3179 | 1.45 | 406 | 1.27 | 7.830 | > 11 | 9503 | 2.99 | 775 | 1.91 | 12.262 | > 12 | 11736 | 1.23 | 1153 | 1.49 | 10.179 | > 13 | 34120 | 2.91 | 3095 | 2.68 | 11.024 | > 14 | 70896 | 2.08 | 5130 | 1.66 | 13.820 | > 15 | 533472 | 7.52 | 13387 | 2.61 | 39.850 | > 16 | 2127928 | 3.99 | 38883 | 2.90 | 54.726 | > 17 | 22832393 | 10.73 | 102922 | 2.65 | 221.842 | > 18 | 125735032 | 5.51 | 392455 | 3.81 | 320.381 | > 19 | 1550058818 | 12.33 | 1282910 | 3.27 | 1208.237 | > 20 | 13249444278 | 8.55 | 3148114 | 2.45 | 4208.693 | > 21 | | | 6304981 | 2.00 | | > 22 | | | 14390115 | 2.28 | | >-------------------------------------------------------------------- > >Best Regards >Andreas Stabel
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.