moves from hashtable

[Guetti]

After implementing a basic transposition table, I of course try the move from the TT first if I have one. Unfortunately, the percentage of the positions where I have a move from the TT is only around 10-15% of all the positions where this sorting could be performed. Is this normal? Which move should I try if I don't have a move from the TT?

[bob]

After implementing a basic transposition table, I of course try the move from the TT first if I have one. Unfortunately, the percentage of the positions where I have a move from the TT is only around 10-15% of all the positions where this sorting could be performed. Is this normal? Which move should I try if I don't have a move from the TT?

That is completely normal.

As far as your second question goes, most order like this:

1. hash move
2. winning/equal captures in SEE order
3. killer moves
4. rest of moves in whatever order you want, although most use just generated order by this point.

If no hash move is present, just drop into #2. Or, if this is a PV node, you could try Internal Iterative Deepening to get a better first move to search.

[Harald Johnsen]

Check that you don't overwrite the hash move (with zero) when you are at an ALL node. It was not clear if you have an hash move in 15% of all nodes or 15% of nodes where you have a TT hit.

HJ.

[Guetti]

Check that you don't overwrite the hash move (with zero) when you are at an ALL node. It was not clear if you have an hash move in 15% of all nodes or 15% of nodes where you have a TT hit.

HJ.

What I meant is before I generate moves I try the move from the hashtable, and only in about 10-15% of all cases I have a move from the hashtable, in the other 85% I either don't had a hash hit or I had a hit but no best move stored in the table. I was actually interested how big this number is to estimate how effective this sorting is, therefore I implemented 2 counters.
If this is normal, then I have to optimize the sorting of the moves I generate.

[Tord Romstad]

What I meant is before I generate moves I try the move from the hashtable, and only in about 10-15% of all cases I have a move from the hashtable, in the other 85% I either don't had a hash hit or I had a hit but no best move stored in the table. I was actually interested how big this number is to estimate how effective this sorting is, therefore I implemented 2 counters.
If this is normal, then I have to optimize the sorting of the moves I generate.

I haven't made any measurements, but 10-15% sounds quite reasonable. When you start a new iteration, only about 50% of the nodes from the last iteration have a best move in the hash table, and most of the nodes you visit during iteration N+1 were not visited in iteration N (because most nodes are close to the leaves, about one ply beyond the deepest nodes you searched during iteration N).

However, the number of hash moves found at nodes close to the root should be quite high.

Tord

[Guetti]

What I meant is before I generate moves I try the move from the hashtable, and only in about 10-15% of all cases I have a move from the hashtable, in the other 85% I either don't had a hash hit or I had a hit but no best move stored in the table. I was actually interested how big this number is to estimate how effective this sorting is, therefore I implemented 2 counters.
If this is normal, then I have to optimize the sorting of the moves I generate.

I haven't made any measurements, but 10-15% sounds quite reasonable. When you start a new iteration, only about 50% of the nodes from the last iteration have a best move in the hash table, and most of the nodes you visit during iteration N+1 were not visited in iteration N (because most nodes are close to the leaves, about one ply beyond the deepest nodes you searched during iteration N).

However, the number of hash moves found at nodes close to the root should be quite high.

Tord

Hm, I think the TT is working ok, even though there still might be bugs.
I think my move ordering is very bad. I currently only order the hashmove and captures with SEE. The search after 1. e4 e5 2. Nf3 looks like that:

Code: Select all

ply   score     time       nodes    pv
   1       0        0          35    b8c6 
   2     -12        0          94    g8f6 
   3     -12        0         153    g8f6 
   4     -12        0         217    g8f6 
   5     -12        0         370    g8f6 
   6     -12        0         547    g8f6 
   7     -12        0         868    g8f6 
   8     -12        0        1839    g8f6 
   9      -6     1535    20638372    f8d6 b1c3 g8f6 f1c4 b8c6 e1g1 e8g8 d2d4 a8b8 

It gets quickly at depth 8 because of the TT entries from the previous search, but then the nodes explode.
Yes, and it doesn't know that it is bad to put the bishop in front of a pawn.

[sje]

From Reuben Fine:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

[Guetti]

From Reuben Fine:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

I don't know want you want to express with posting Fine #70, but just in case, although I see prominent effects of the TT in endgame positions, in the starting position in gave me only one additional ply. The NPS hit of implementing TT was around 15-20%. I think I really have to improve the move ordering next.

Code: Select all

Trying 15s
 ply   score     time       nodes    pv
   1     137        0           3    a1b2 
   2     125        0          14    a1b2 a7b6 
   3     129        0          87    a1b2 a7b6 b2c3 
   4     129        0         219    a1b2 a7b6 b2c3 b6c7 
   5     133        0         425    a1b2 a7b6 b2c3 b6c7 c3d3 
   6     131        0         683    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 
   7     131        0        1164    a1b2 a7b6 b2c3 b6c7 c3d3 c7d7 d3e3 
   8     133        0        1971    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 
   9     133        0        2788    a1b2 a7b6 b2c3 b6c7 c3c4 c7b6 c4d3 b6c7 d3e3 
  10     133        1        9106    a1b2 a7b6 b2c2 b6c7 c2b3 
  11     133        1       13910    a1b2 a7b6 b2c2 b6c7 c2b3 c7b6 b3c4 b6a6 c4c3 a6b6 
  12     133        2       21856    a1b2 a7b6 b2c2 b6c7 c2d2 c7d7 d2c3 d7c7 c3b3 c7b6 b3c4 b6c7 
  13     133        3       31064    a1b2 a7b6 b2c2 b6c7 c2d3 c7b6 d3d2 b6a6 d2c2 a6a7 c2b3 a7b6 b3c4 
  14     133        4       39486    a1b2 a7b6 b2c2 b6c7 c2b1 c7d7 b1a2 d7c7 a2b3 c7b6 b3c3 b6b7 c3d3 b7b6 
  15     133        5       48964    a1b2 a7b6 b2c2 b6c7 c2d3 c7b6 d3d2 b6a6 d2c1 a6b7 c1d1 b7a6 d1d2 a6b6 
  16     131        6       68160    a1b2 a7b6 b2c2 b6c7 c2d2 c7b7 d2d3 b7b6 d3e2 b6c7 e2e1 c7b6 e1f2 b6c7 f2e3 c7d7 
  17     131        7       79229    a1b2 a7b6 b2c2 b6c7 c2d2 c7b7 d2d3 b7b6 d3e2 b6c7 e2d1 c7d7 d1c1 d7e7 c1c2 e7f6 c2d3 
  18     131        9      108622    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b6 a1a2 b6a6 
  19     131       10      126290    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7a8 a2b3 a8a7 b3c3 a7b7 c3d2 b7c8 d2e2 c8d7 e2e3 
  20     131       10      143936    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7a8 a2b3 a8a7 b3c3 a7b7 c3d2 b7c8 d2e2 c8d7 e2d3 
  21     131       11      160921    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7b8 a2a3 b8b7 a3b3 b7a7 b3c3 a7b7 c3d2 b7c8 d2e2 c8d7 e2d3 
  22     131       13      181501    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7b8 a2a3 b8b7 a3b3 b7a7 b3c3 a7b7 c3d2 b7c8 d2e2 c8d7 e2d3 d7e7 
  23     131       14      208550    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7b8 a2a3 b8b7 a3b3 b7a7 b3c3 a7b7 c3d2 b7c8 d2d1 c8d7 d1c2 d7e7 c2d3 
  24     131       16      252092    a1b2 a7a8 b2c2 a8b8 c2b1 b8a7 b1a1 a7b7 a1a2 b7b8 a2a3 b8b7 a3b3 b7a7 b3c3 a7b7 c3d2 b7c8 d2d1 c8d7 d1c2 d7c8 c2d2 c8b7 
>>25     181       20      316159    a1b2 *
  25     255       24      394632    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e2 b6a6 e2f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4g5 d7e7 g5f5 e7f7 f5g5 f7g7 f4f5 g7f8 g5f6 
  26     253       28      473839    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e2 b6a6 e2f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4h5 d7e7 h5g5 e7d8 g5f5 d8e7 f5g5 
  27     253       31      549241    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6a6 e1f1 a6a7 f1f2 a7b6 f2e3 b6a6 e3e2 a6b7 e2f3 b7c7 f3g3 c7d7 g3h4 d7e7 h4g5 e7f8 g5f6 f8g8 f6f5 
  28     255       36      653869    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6a6 e1f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4g5 d7e7 g5f5 e7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5f4 f8e8 f4e4 e8d7 
  29     255       41      756004    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6a6 e1f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4g5 d7e7 g5g6 e7e8 g6f6 e8f8 f6f5 f8f7 f5g5 f7g7 f4f5 g7f8 g5f6 f8e8 f6e6 
  30     256       50      955645    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6a6 e1f2 a6b6 f2g3 b6c7 g3h4 c7d7 h4g5 d7e7 g5f5 e7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8d8 f6f7 d8d7 
  31     253       67     1334105    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8f7 f4f5 
  32     253       79     1589895    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8d8 f4e3 d8c7 
  33     253       93     1857300    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8f8 f4e4 f8f7 e4f5 
  34     251      133     2672266    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8f8 f4e4 f8e8 e4d3 e8d7 
  35     253      198     3972934    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5f4 f8e8 f4g4 e8f8 g4g5 f8g8 g5f4 g8f7 f4f5 
  36     253      288     5636378    a1b1 a7b6 b1c2 b6a6 c2d1 a6b6 d1e1 b6c7 e1f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5f4 f8e8 f4g4 e8d8 g4f3 d8d7 f3g3 d7c7 g3f4 
  37     263      539    10224708    a1b1 a7b6 b1c2 b6a6 c2d2 a6b6 d2e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g4 f7f6 f4f5 f6e7 g4g5 e7f7 f5f6 f7f8 g5f4 f8e8 f4g4 e8f8 g4g5 f8f7 g5f5 f7e8 f5e6 
  38     262     1352    24422273    a1b1 a7b6 b1c2 b6a6 c2d2 a6b6 d2e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8d8 f4e3 d8d7 e3f3 d7d8 f3e4 d8c7 f6f7 c7b6 

38 (3/3) 2.62  15.01  26931944  a1b1 a7b6 b1c2 b6a6 c2d2 a6b6 d2e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g4 f8e8 g4f4 e8d8 f4e3 d8d7 e3f3 d7d8 f3e4 d8c7 f6f7 c7b6 
Score: 2.62  Time: 15.01  Ply: 38/49
Nodes:  26931944  NPS: 1794k

So, the main options what do do next are:

- Nullmove
- History heuristics
- Killer moves
- Internal Iterative deepening
- ...

Until I decide I want to do some code clean up first. Furthermore I want to implement a function that inverts the position in order to see if I get the same results.