Computer Chess Club Archives


Search

Terms

Messages

Subject: Unique nodes, en passant and perfect hashing

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.