Iterative Deepening + Transposition Table

[Dek]

Hi,

I ve been working on my chess program as a hobby, the move generator seems to be correct using bitboard (from 10-30Million node / sec on a core2 duo 1.8), and seems to do perfectly legal (checked with divide/perft). I m bit tired of doing optimisation on it so I thought i ll work on alpha beta + evaluation. Though it seems that a transposition table+iterative deepening (while my opponent thinking for example) would speed up search but I m fairly confused about those two together and I hoped you could help me there

From what i understand iterative deepening, is searching all move with depth 1 and then do the same thing with depth 2 and so on until a time limit has been reached.

The advantage seems to fill up the transposition table, that s where i m bit lost ... The transposition table is checked and filled with the result of the previous search...
- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?
- So when do we put the result in the transposition table ? for the top nodes ? For every nodes ? For the bottom explored node ? Do we have to check the search depth for which the node were inserted inside the transposition table ?

Thanks a lot for your answers

[bob]

Hi,

I ve been working on my chess program as a hobby, the move generator seems to be correct using bitboard (from 10-30Million node / sec on a core2 duo 1.8), and seems to do perfectly legal (checked with divide/perft). I m bit tired of doing optimisation on it so I thought i ll work on alpha beta + evaluation. Though it seems that a transposition table+iterative deepening (while my opponent thinking for example) would speed up search but I m fairly confused about those two together and I hoped you could help me there

From what i understand iterative deepening, is searching all move with depth 1 and then do the same thing with depth 2 and so on until a time limit has been reached.

The advantage seems to fill up the transposition table, that s where i m bit lost ... The transposition table is checked and filled with the result of the previous search...
- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?
- So when do we put the result in the transposition table ? for the top nodes ? For every nodes ? For the bottom explored node ? Do we have to check the search depth for which the node were inserted inside the transposition table ?

Thanks a lot for your answers

There are two parts to a hash entry. The score/bound, and the best move. Between iterations, scores are not very helpful because the next iteration goes one ply deeper and the hash score will be useless. But the best move from the hash table is a good move to search first, and that is where the advantage of iterative deepening shows up...

[Dek]

Hi,

I ve been working on my chess program as a hobby, the move generator seems to be correct using bitboard (from 10-30Million node / sec on a core2 duo 1.8), and seems to do perfectly legal (checked with divide/perft). I m bit tired of doing optimisation on it so I thought i ll work on alpha beta + evaluation. Though it seems that a transposition table+iterative deepening (while my opponent thinking for example) would speed up search but I m fairly confused about those two together and I hoped you could help me there

From what i understand iterative deepening, is searching all move with depth 1 and then do the same thing with depth 2 and so on until a time limit has been reached.

The advantage seems to fill up the transposition table, that s where i m bit lost ... The transposition table is checked and filled with the result of the previous search...
- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?
- So when do we put the result in the transposition table ? for the top nodes ? For every nodes ? For the bottom explored node ? Do we have to check the search depth for which the node were inserted inside the transposition table ?

Thanks a lot for your answers

There are two parts to a hash entry. The score/bound, and the best move. Between iterations, scores are not very helpful because the next iteration goes one ply deeper and the hash score will be useless. But the best move from the hash table is a good move to search first, and that is where the advantage of iterative deepening shows up...

First of all thanks for your reply From what I read it seems pointless to keep the score if it s not really helpful ?

[Harald Johnsen]

- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?

You won't have any cutoff, you'll only use the HT for the move ordering at depth 2.

When you enter your search function you want to search a tree of depth 'D'. So you can not stop your search by using the content of something from the hash table if that content was the result of searching a tree of depth 'd' and 'd' < 'D'.

So when you did your first search at depth 1 all positions stored in the TT had a null subtree ie a subtree of depth 0.
For the search at depth 2 all your root moves will be found in the TT but you can not stop the search.

But you can have transpositions of positions, ie some positions will be visited several times with the same depth but from a different path.

HJ.

[andretaff]

Yes, it is helpful in the lower nodes (in opposition to the root nodes). Assuming it's clear for you that you can reach the same position using two different play lines, that's where the move score will help. Imagine from the starting board, you can go:
e2-e4, e7-e5, b1c3
or
b1-c3, e7-e5, e2-e4

If you have the first one calculated, there's no need to calculate the second board (because it's the same ply, and it's the same board).

[xsadar]

Hi,

I ve been working on my chess program as a hobby, the move generator seems to be correct using bitboard (from 10-30Million node / sec on a core2 duo 1.8), and seems to do perfectly legal (checked with divide/perft). I m bit tired of doing optimisation on it so I thought i ll work on alpha beta + evaluation. Though it seems that a transposition table+iterative deepening (while my opponent thinking for example) would speed up search but I m fairly confused about those two together and I hoped you could help me there

From what i understand iterative deepening, is searching all move with depth 1 and then do the same thing with depth 2 and so on until a time limit has been reached.

The advantage seems to fill up the transposition table, that s where i m bit lost ... The transposition table is checked and filled with the result of the previous search...
- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?
- So when do we put the result in the transposition table ? for the top nodes ? For every nodes ? For the bottom explored node ? Do we have to check the search depth for which the node were inserted inside the transposition table ?

Thanks a lot for your answers

There are two parts to a hash entry. The score/bound, and the best move. Between iterations, scores are not very helpful because the next iteration goes one ply deeper and the hash score will be useless. But the best move from the hash table is a good move to search first, and that is where the advantage of iterative deepening shows up...

First of all thanks for your reply From what I read it seems pointless to keep the score if it s not really helpful ?

When you check the transposition table, and the depth of the current search is less than or equal to the depth of the results in the table, the score may be usable (depending on the bounds). Iterative deepening does not cause these types of hits; they're caused by transpositions (the same position reached by a different set of moves).
When you check the transposition table, and the depth of the current search is greater than the depth of the table's results, you can't use the score, only the best move. This type of hit is caused by both iterative deepening and transpositions. Transposition tables were originally intended for handling transpositions (thus the name) but are also useful for iterative deepening.

If you haven't already, you may want to look at Bruce Morland's page on transposition tables (archived because his site is gone) for further information:
http://web.archive.org/web/200708130110 ... ashing.htm

He also had a lot of useful information on other topics which you may want to look at.

[bob]

Hi,

I ve been working on my chess program as a hobby, the move generator seems to be correct using bitboard (from 10-30Million node / sec on a core2 duo 1.8), and seems to do perfectly legal (checked with divide/perft). I m bit tired of doing optimisation on it so I thought i ll work on alpha beta + evaluation. Though it seems that a transposition table+iterative deepening (while my opponent thinking for example) would speed up search but I m fairly confused about those two together and I hoped you could help me there

From what i understand iterative deepening, is searching all move with depth 1 and then do the same thing with depth 2 and so on until a time limit has been reached.

The advantage seems to fill up the transposition table, that s where i m bit lost ... The transposition table is checked and filled with the result of the previous search...
- If we search at depth 1, the x current move will end up in the transposition table with a bad evaluation (depth 1 isnt reliable I guess), so when we start depth 2, we ll get a huge hit on transposition table hence we shouldnt rely on transposition table ?
- So when do we put the result in the transposition table ? for the top nodes ? For every nodes ? For the bottom explored node ? Do we have to check the search depth for which the node were inserted inside the transposition table ?

Thanks a lot for your answers

There are two parts to a hash entry. The score/bound, and the best move. Between iterations, scores are not very helpful because the next iteration goes one ply deeper and the hash score will be useless. But the best move from the hash table is a good move to search first, and that is where the advantage of iterative deepening shows up...

First of all thanks for your reply From what I read it seems pointless to keep the score if it s not really helpful ?

The score is not very helpful in middlegame positions. Finding a transposition with enough depth left to use the score is not very common, particularly if you use PVS where only a few nodes are searched with anything but a null-window anyway. But in endgames, the scores and bounds become much more effective and they make a huge difference in speed/depth in endings.