Question regarding transposition tables (to clear or not)

[Roman Hartmann]

...
For this sort of thing, it is not uncommon to use a circular ring buffer of the last 100 plies that were played (you can store the whole game but there is no point in it unless you want to be able to play the whole game back for learning purposes or something like that).

You can use your half move clock to figure out how far backwards you will have to look.

You can use information from this structure to figure out if there is either 100 plies non-reversible or 3-fold repeat (obviously, if an irreversible move has been played, the 3-fold repeat does not have to be investigated beyond that boundary either).

I do store the whole game in a move-stack. Of course there is no real need in doing that when you use a GUI but I started with a console mode and you need to do something like that to take back (all) moves.

As you point out this information can be used to detect a 3-fold and that's what I'm currently doing.

best regards
Roman

[Ron Murawski]

You are in error when you assume I would only accept hash entries with a draft of 2 + (8 * 8) or more. Again, this is my fault because I'm not being clear enough. The aging is 1/4 ply per game ply, or 1/2 ply per chess game move. The integer depth is unaffected until the 1/4 plies add up to a whole ply. (For pruning decisions I ignore fractional plies.)

OK, I see. There is a loss of information here though. When you ignore the fractional plies, that means that you're rounding down at some point. If the move numbers were not 0 and 2 but 3 and 4, then you would lose a full ply of useful hash information. This is also dangerous in that fractional plies can make a difference in the search, and you can accept cutoffs from entries with too low of a draft. This last part I haven't tested personally, but I was told that by Bob Hyatt and Tord Romstad a few years ago on CCC, and it makes sense to me. A quarter or eighth of a ply here, and it ends up allowing a full ply later down the tree, which leads to seeing a checkmate earlier, and so on. It's also just a philosophical thing for me, I would rather not lose some good cutoffs and make some bad ones just to save some bits in the hash table.

In my testing it was quite rare to find missed pruning decisions. After playing several thousand test games I decided that the method worked fine in practice.

Maybe someday I'll re-try your method and see if it makes any difference.

That is of course true. It's quite possible that there's no real measurable difference between the methods. If it works fine for you, then there's no reason to mess with it. But in this case I think it would be worth testing, it might bring you some precious Elo.

Zach, you said you base replacement decisions on age and depth --
What is your formula?

Ron

My replacement formula is pretty complicated. I'll post some simplified code, and an explanation.

Code: Select all

    best_slot = 0;
    best_depth = MAX_PLY * PLY + 1024;
    for (x = 0; x < HASH_SLOT_COUNT; x++)
    {
        hashkey = entry->entry[x].hashkey;
        data = entry->entry[x].data;
        if (hashkeys_match())
        {
            if (HASH_DEPTH(data) > sb->depth)
                return;
            else
            {
                best_slot = x;
                break;
            }
        }
        else if (HASH_DEPTH(data) - age_difference(HASH_AGE(data)) * 2 * PLY < best_depth)
        {
            best_slot = x;
            best_depth = HASH_DEPTH(data) - age_difference(HASH_AGE(data)) * 2 * PLY;
        }
    }
    /* Check to see if we should overwrite the entry. */
    if (HASH_TYPE(entry->entry[best_slot].data) != HASH_EXACT_BOUND || type == HASH_EXACT_BOUND ||
        age_difference(HASH_AGE(entry->entry[best_slot].data)) > 0)
    {
        store_position();
    }
}

This means a position is stored when:
1. If the same position is in the hashtable already, it is only overwritten if the depth is greater now.
2. Otherwise, a slot in the hashtable with the lowest sum of depth + age is chosen to be overwritten. It is only overwritten when one of these conditions are met:
2. It is a PV node
3. The position stored in the table isn't a PV node
4. The position stored in the table is a PV node, but from an old search

The number of slots selected from right now is 4, which adds up to a cache line. As you can see, the age is multiplied by 2*PLY to be on the same scale as depth. This scaling is proper only when ponder is off, as the age is incremented after every search. I doubt it really makes a difference, but I should probably do something about it.

Thanks for the look at your code. Interesting!

You said: "If the move numbers were not 0 and 2 but 3 and 4, then you would lose a full ply of useful hash information. "
The move numbers would have to be 0 and 4 (or 2 and 6, etc.) for this to happen.

I think we'll agree to disagree whether my method loses information. In my mind, if an existing hash node did not get updated during one search, then it seems very unlikely to me that it would cause a cutoff during the following search.

I could argue that your method loses information because it overwrites non-pv nodes that might cause future cutoffs or because it doesn't overwrite old pv nodes soon enough. But I think we both agree that this usually doesn't matter.

Hash aging with minimal information loss can be achieved by clearing all the dead, impossible-to-get-to positions. But: That's not so easy to do!

Ron