Author: Andreas Stabel
Date: 06:13:15 11/25/99
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.01 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.