Something obious on IID that not everybody does

[Dann Corbit]

When doing an IID search, we are performing the search because the position is not already in the hash table.

Some programs go ahead and do a hash table lookup anyway on the IID pass. That is obviously a waste of time, because the reason we are doing the search is that we had a hash table miss to start with.

So if you are on an IID pass, do not bother to perform the hash table lookup. It's just a waste of cycles.

[H.G.Muller]

Let me make sure I understand this. You mean that in the entire tree that is traversed in the initial reduced-depth search(es) none of the nodes should bother to look in the hash table?

This is indeed non-obvious. I suppose you tested this, because from a purely theoretical point of view I can see many objections:

* The position might not be in the hash table because it was overwritten. Most of its daughters might still be in the hash table at a depth equal to or better than you need, so that an IDD search that you intended as, say, a 3-ply search effectively becomes a 1 ply search. This effect should be biggest in a replacing scheme that is very liberal in overwriting, without much rehash. (In a 50% full table 28% of the initially entered elements are lost due to collisions, without rehash)

* Even for a new position that was formerly pruned by alpha-beta, positions in the tree might be in the hash because they were reached through another path where they were not pruned. This especially holds in end-games, where Kings can move through many paths to the same destination square.

* Using the hash in the sub-tree can be benificial because the sub-tree search fills the hash itself. Again in end-games, if you are busy doing a 23-ply search, and because of a promotion everything gets re-evaluated and you need to visit formerly pruned nodes, moving a Pawn that you did not touch before with still 20 plies to go... You might want to start with a 10-ply IDD pilot search then, to weed out the variations that started racing with a Pawn that could finally be caught by the enemy King. But such a search will be extremely expensive if it cannot use the hash for building its own, local table: The 5 'alpha-node plies' for the losing side will search all 8 King moves, leading to 8^5 = 32K end-leaves, while in fact there are of course only 64 final King positions!

* If I don't store the earlier IDD pass in the hash, when I later embark on the full search, deeper nodes in it will have to do IDD again, because they also find nothing in the hash. Say I first encounter a (suspected beta) node with still 8 plies to go, and decide to do an IDD pilot search at 6 ply. When I later do the 8-ply search I will encounter at remaining_depth 6 nodes that the pilot did to 4 ply, and at depth 4 nodes that the pilot did to depth 2. The hash could have provided very useful guidance, these are still beta nodes, and if I did not let my initial pilot use the hash I probably am going to do 4-ply and 2-ply IDD pilots in those nodes as well. If I allow my pilot to write the hash, I might as well have allowed it to read it: the lookup and memory access would have to be done anyway, and the reading would be essentially free.

So even if you tested this idea thoroughly, the results might be very dependent on the hash-table implementation (rehash, replacement policy), the stage of the game (middle- vs end-game), and the details of the IDD strategy (in which nodes, how much depth reduction in the pilot, multiple pilots or not).

[Zach Wegner]

I think he was talking only about the same node we are doing the reduced depth searches for, not the whole subtree of course. Most people implement IID by just calling search again, which means they probe hash, generate moves, etc. multiple times for the same position.

[H.G.Muller]

Well, even then point 1 would still be valid: this node might have been overwritten, but all daughters might be in the hash. If you suppress the hash probe on the first level after the node for which you do the IID (which are likely to be alpha nodes, because the IID you do in a beta node) you would only discover that this branch has been searched before at the grand-daughter level, at the expense of ~40 times as many hash probes...

So only if the number of lost entries due to over-writes is less than one in 40, you start to gain something. And then I don't even count the overhead of generating the moves at the daughter level.

[Zach Wegner]

No, you still probe hash for the child positions, just not the position you are doing IID for. Most people implement IID by doing a reduced depth search _without making any moves_ and using the pv move from that as the hash move. So, any hash probes you do on these "children" would give the exact same result. Nothing is added or removed from the hash in between the probes, the program is just going like this:
probe hash
no move found, reduce depth and start over
probe hash
no move found, reduce depth and start over
...

If you explicitly write out a move loop that searches each child with reduced depth, then you don't have to worry about this.

[Daniel Shawul]

Zach,
i guess that this is obvious for you probably because probably because your search is non recursive?
i also don't probe the hashtable twice, but i still generate the moves again.
I tried to do this but left it later because my move generation is incremental and is complicated. Implementing IID in a non-recursive search is a bit hard (even harder than null move).
The stack element at the point of where we try IID may be corrupted.
For example, the alpha-beta bounds should be saved befroe doing IID and restored later.

[H.G.Muller]

..., the program is just going like this:
probe hash
no move found, reduce depth and start over
probe hash
no move found, reduce depth and start over
...

This seems an awful lot like replacing asisgnment statements a=b; in your program by:

Code: Select all

while(a>b) a--;


which achieves the same but makes little sense from the viewpoint of efficiency (if a is an integer).

I can't think of any reason why you would not always do it like this (whether your search is recursive or not):

Code: Select all

probe hash
if(no move found) reduced depth = 0;
else              reduced depth = hash depth

while(reduced depth < desired depth)
increase depth and start over


The inefficiency does not come so much from probing the hash, though: after the first probe this is essentially free, since the relevant entry will be cached. It is mainly the funny way of reducing the depth step by step, to empirically find out when it is low enough, while that information was available from the outset...

[Tord Romstad]

No, you still probe hash for the child positions, just not the position you are doing IID for.

If that is the only point of Dann's idea, it cannot possibly be worth much. The number of hash probes you save will be extremely tiny. Besides, even these few hash probes will be essentially free. After the first, unsuccessful probe, the relevant hash table entry will be loaded into the cache, and looking it up again is a very cheap operation.

Tord

[Daniel Shawul]

Some things are not necessarily free though. 3fold repetition detection,
interior node recognizer probes (without cache), also if you do internal eval() without eval cache... Anyway i think that this will not give a measurable speed as IID is tried a few times only.

[H.G.Muller]

Well, I guess that it goes without saying that it never helps to do exactly the same thing twice, even if it is cheap...

But about the 3-fold repetition detection: don't you do that from the same hash table entry? Even before looking at what the move is the hash table recommends for this position, you can look at the number of previous visits. If that was two, you declare a draw straight away, and you never get to wondering what the move or the depth is, or how you should commence IID. If the position was not in the hash table, apparently it was no repetition.

[Daniel Shawul]

Code: Select all

But about the 3-fold repetition detection: don't you do that from the same hash table entry? Even before looking at what the move is the hash table recommends for this position, you can look at the number of previous visits. If that was two, you declare a draw straight away, and you never get to wondering what the move or the depth is, or how you should commence IID. If the position was not in the hash table, apparently it was no repetition.

The point is that you are going to look at previous positions twice.
Obviously the position is not a repetition (since we would have stopped search if it was), but you are doing the work twice just to prove it is not a reptition when once is enough. The hashtable will not be any help since we only try IID where we don't have a hashtable move.

[David Weller]

GES skips hash probe and move generation when IID-ing

HG raises some interesting questions though ...

[H.G.Muller]

The point is that you are going to look at previous positions twice.
Obviously the position is not a repetition (since we would have stopped search if it was), but you are doing the work twice just to prove it is not a reptition when once is enough. The hashtable will not be any help since we only try IID where we don't have a hashtable move.

Perhaps the thing I do not properly understand is how you are going to find out if it is a repetition if it is not in the hash table. If it is not, I don't have to worry about doing that twice, because I don't even know how to do it once.

Apparently, you have a way to find out if something is a repetition without the aid of the hash table. I have no such way, for me every position that occured before (in the game or in the tree) is kept in the hash table, so if it is not in the hash table, it was no repetition.

[Alessandro Scotti]

Perhaps the thing I do not properly understand is how you are going to find out if it is a repetition if it is not in the hash table. If it is not, I don't have to worry about doing that twice, because I don't even know how to do it once.

Apparently, you have a way to find out if something is a repetition without the aid of the hash table. I have no such way, for me every position that occured before (in the game or in the tree) is kept in the hash table, so if it is not in the hash table, it was no repetition.

The "other" typical method is a simple loop comparing the hash code of the current position with that of positions that occurred earlier in the game or in the search path.
Looks amazingly inefficient, but works fairly well in practice.

[Zach Wegner]

Hello All,

Zach,
i guess that this is obvious for you probably because probably because your search is non recursive?
i also don't probe the hashtable twice, but i still generate the moves again.
I tried to do this but left it later because my move generation is incremental and is complicated. Implementing IID in a non-recursive search is a bit hard (even harder than null move).
The stack element at the point of where we try IID may be corrupted.
For example, the alpha-beta bounds should be saved befroe doing IID and restored later.

Well, I think it's more because of the way I implement IID--I am aware of the inefficiency I have. I actually do probe each time, but I don't generate moves/attacks. I didn't find IID too hard to implement, but I didn't use the same stack element. Here's the relevant code:

Code: Select all

                /*internal iterative deepening*/
                if (!board->hashmove[sb->ply] && sb->alpha + 1 != sb->beta && !board->threatm[sb->ply] && sb->depth > 3 * PLY && sb->donull)
                {
                        SEARCH(sb->depth - 3 * PLY, sb->ply, sb->alpha, sb->beta, 1, NODEPV, IID1);
iid1:                   val = (sb + 1)->rv;
                        if (val > sb->alpha && val < sb->beta)
                                board->hashmove[sb->ply] = MOVE(board->pv[sb->ply][sb->ply]);
                }
                else
                {
                        genattacks(board);
                        if (board->incheck[sb->ply])
                                board->firstmove[sb->ply + 1] = genevasions(board, board->firstmove[sb->ply], board->incheck[sb->ply]);
                        else
                                board->firstmove[sb->ply + 1] = gen(board, board->firstmove[sb->ply]);
                }

I can't think of any reason why you would not always do it like this:

Calling search again is slightly inefficient, but it makes the code clearer. I have a bunch of initializations at the beginning of search (as well as null move), plus I have all of the nonrecursive stack stuff to deal with, so it would end up making the code a lot longer and more error prone.

The "other" typical method is a simple loop comparing the hash code of the current position with that of positions that occurred earlier in the game or in the search path.
Looks amazingly inefficient, but works fairly well in practice.

That is what I do. It has the advantage of being error free i.e. not dependent on the hash table, which overwrites. Also you only have to check positions of the same side to move, and only as far back as the last irreversible move (capture/pawn move).

Zach

[H.G.Muller]

That is what I do. It has the advantage of being error free i.e. not dependent on the hash table, which overwrites. Also you only have to check positions of the same side to move, and only as far back as the last irreversible move (capture/pawn move).

Doing in the hash table can also be error free: simply protect any entry that has a non-zero repeat count from overwrite.

The only thing against it I can imagine is the extra space the repeat count requires in the big hash table, (i.e. times a few million) while it is only used in a couple of hundred entries at most. But usually there are constraints to the size of a hash-table entry w.r.t. memory alignment that forces a larger-than-strictly-necessary entry, and I simply use a byte for this that otherwise would have been there as a filler.

With a 4-byte hash lock I could not cram the score (+boundary type) , the best move and the depth in 4 bytes, so to keep word alignment I am forced to 12-byte entries. Besides the hash lock I then store upper and lower bound to the score (two short int), depth (1 byte) and move (2 bytes), so there is one byte left to use for the repeat count. The latter requires only 3 bits (it runs from 0 to 4), if really needed I could have packed them together with the move (there are 4 unused bits there).

If size in the main hash were an issue, I would have made a secondary hash table (a few hundred entries) small enough to be always in cache (128 entries or so) for which the index could be derived from the main hash key (by and'ing with 127, say), and do the repeat lookups there. It seems strange that you accept the overhead of a linear search for data that can be so easily hashed, while worrying about the overhead of a recursive call...