transpositiontable, zobrist and > 15% collisions

[xmas79]

The pointer may be useless for now, but you may not remember the fact that it needs to be useless, and decide to use it again later, after you have completely forgotten the restriction.

To do what? The restriction comes from the algorithm, and from my (I'll be conservative here saying "my" and not "chess") algorithm point of view, nothing should be done with that entry, except "replace". So I still don't see the point.

There is a reason to reuse it. Conceptually, when you are reading the code, you are thinking of the pointer as a pointer to the entry corresponding to this position. If you want to write something about this position into the entry, it makes perfect sense to do it through the pointer. If you don't want to allow that, you can make the probing function return a const pointer. However, even in that case, if you decide to read something else from it after a search, it would still be buggy.

Again there is no room for reading something after a search.

This is also very dangerous if you are not the only developer on the project. Other developers may not be aware of such a restriction, and they may decide to use it.

+1

And here you see just how easy it is to make a mistake in this case.

The pointer is not tied to the hash key (as you would conceptually expect from reading the code). It is tied to the hash slot.

By the time you access it again, it may have a different hash key already, from a different position that mapped to the same slot. The slot may now belong to another position. Anything you read from it may be wrong, and anything you write to it will overwrite something that you probably did not intend to overwrite.

I try to be more explicit. IN THE Folkert IMPLEMENTATION there are no multilple buckets for the same hash index, so one hash key will ALWAYS map to the SAME memory address (hash % nEntry). Now when I decide to use my pointer:

1) the TT entry is still the same entry (entryes[hash % nEntry].hash == hash), but I overwrite the entry. No problems at all.
2) the TT entry belongs to another position (entryes[hash % nEntry].hash != hash). First question: how it is possible in a single-threaded search? BTW, I should use the entry (that is a replace operation) .... Uhm... Replacement scheme:
2a) always replace: I replace it, stop. No matter what's inside the TT entry. No prolems.
2b) depth preferred: I have to decide if replace the entry or not. So I read through the pointer, or from some other means, but I will actually end up reading the exact SAME entry from the exact SAME memory address. So no different behaviour.

Now, in a TT implementation with multiple buckets per hash index, this is a bit different because an hash key can map to different hash buckets at different addresses, and there is "space" between the READ use of the hash entry (beginning of the search function) and the WRITE use (the end of the search, or at least after a subtree search), and this can change the content of the buckets at the same hash index, making a store through the pointer a very bad decision.

And of course, in a multithreaded search something more can happen, something so weird that your TT entry will change under your compiler's feet between the two 8 bytes read, as Bob said.

[flok]

That is perfectly valid C++ and is done all the time.

I know, and I'm sorry for not being clear in advance. I didn't say this is the problem, what I really meant is that I generally tend to avoid code patterns that could lead to silly mistakes, and this belongs to one of these IMHO.

Really? But why?

BTW, I would have coded the lookup in this way:

Code: Select all

tptEntry *Tpt::lookup(const uint64_t hash) 
{ 
        unsigned long int index = hash % nEntries; 
        return (entries[index].hash == hash ? &entries[index] : NULL);
} 

That's not thread-safe.

[Dann Corbit]

"2) the TT entry belongs to another position (entryes[hash % nEntry].hash != hash). First question: how it is possible in a single-threaded search? BTW, I should use the entry (that is a replace operation) ."

Here is how it is possible.
You have one hundred million chess positions to search.
You have 10 million hash slots.
There is no way to store all of the positions in those slots.

Imagine a hash table with 16 slots in it.
Your hash lookup would be :

Code: Select all

my_entry = hash_table[my_hash & 0xf];

Since only 16 things fit in the table, if you write things to it quickly, chances are very good that what you are looking for was over-written long ago. That's why bigger hash tables are better than small ones.

Let's make the table huge. Say 100,000,000 16 byte entries so 1.6 GB of hash.
If you search at 10 Million NPS, then in ten seconds you will completely fill the hash table. If you are searching for one minute, you will completely overwrite the table 6 times during your search. The hope is that the entry is fresh enough to still be in the hash. If you do correspondence chess, 24 hour searches, imagine the massive amount of writes to the hash table.

If your hash table were infinite in size, you would always find the entry, assuming that it is in the table. But any new position not searched is not in the table. So when you search the root position of chess, the first hash lookup fails 100% of the time. And when you search the first node for each of the 20 replies, they are also guaranteed to NOT be in the hash because you have not searched them yet. So how does something even get to be in the hash table? The answer is transpositions. If I search:
1. e4 e5 Nc3
And then I search:
1. Nc3 e5 e4
Then I will very likely find the last position in the hash table, because I have searched that identical position already.
[/code]

[matthewlai]

To do what? The restriction comes from the algorithm, and from my (I'll be conservative here saying "my" and not "chess") algorithm point of view, nothing should be done with that entry, except "replace". So I still don't see the point.

Yes, the restriction comes from the algorithm you have now. It may no longer be true if you decide to change the algorithm later, for example, to add the null move flag.

I try to be more explicit. IN THE Folkert IMPLEMENTATION there are no multilple buckets for the same hash index, so one hash key will ALWAYS map to the SAME memory address (hash % nEntry). Now when I decide to use my pointer:

1) the TT entry is still the same entry (entryes[hash % nEntry].hash == hash), but I overwrite the entry. No problems at all.
2) the TT entry belongs to another position (entryes[hash % nEntry].hash != hash). First question: how it is possible in a single-threaded search? BTW, I should use the entry (that is a replace operation) .... Uhm... Replacement scheme:
2a) always replace: I replace it, stop. No matter what's inside the TT entry. No prolems.
2b) depth preferred: I have to decide if replace the entry or not. So I read through the pointer, or from some other means, but I will actually end up reading the exact SAME entry from the exact SAME memory address. So no different behaviour.

Now, in a TT implementation with multiple buckets per hash index, this is a bit different because an hash key can map to different hash buckets at different addresses, and there is "space" between the READ use of the hash entry (beginning of the search function) and the WRITE use (the end of the search, or at least after a subtree search), and this can change the content of the buckets at the same hash index, making a store through the pointer a very bad decision.

And of course, in a multithreaded search something more can happen, something so weird that your TT entry will change under your compiler's feet between the two 8 bytes read, as Bob said.

Yes, the hash key will always map to the same address. However, many hash keys map to the same address. The address may now store another position.

It's possible in a single threaded search if you perform another search before accessing it, because that search would have triggered stores to the TT, and may have stored another position that mapped to the same slot.

If you use always-replace and overwrite the whole entry all the time, this wouldn't be a problem. However, if you are not careful (in a few months time, when you have forgotten about all these restrictions), you may decide that if you got a hit, the entry must belong to this position, and there's no need to write the hash key.

ANYWAYS, the point of all these is not to say that your code is currently buggy. It's not. However, it's a style of coding that makes hard to find bugs easy to creep in, if you ever let your guard down and forget about these not-very-intuitive restrictions while changing your algorithm.

It's safer to just make a copy of the entry (with appropriate synchronization or lock-free check if multithreaded).

[xmas79]

+1

I resign.

[matthewlai]

+1

I resign.

Coincidently, I am doing the same (returning a pointer) in my engine. I never really thought about it until your post. So thank you for that. I'll go change it now .

[xmas79]

+1

I resign.

Coincidently, I am doing the same (returning a pointer) in my engine. I never really thought about it until your post. So thank you for that. I'll go change it now .

Coincidently, I am doing the same (returning by value, actually storing through a pointer passed as an argument) in my engine!!!

LOL

[bob]

The pointer may be useless for now, but you may not remember the fact that it needs to be useless, and decide to use it again later, after you have completely forgotten the restriction.

To do what? The restriction comes from the algorithm, and from my (I'll be conservative here saying "my" and not "chess") algorithm point of view, nothing should be done with that entry, except "replace". So I still don't see the point.

There is a reason to reuse it. Conceptually, when you are reading the code, you are thinking of the pointer as a pointer to the entry corresponding to this position. If you want to write something about this position into the entry, it makes perfect sense to do it through the pointer. If you don't want to allow that, you can make the probing function return a const pointer. However, even in that case, if you decide to read something else from it after a search, it would still be buggy.

Again there is no room for reading something after a search.

This is also very dangerous if you are not the only developer on the project. Other developers may not be aware of such a restriction, and they may decide to use it.

+1

And here you see just how easy it is to make a mistake in this case.

The pointer is not tied to the hash key (as you would conceptually expect from reading the code). It is tied to the hash slot.

By the time you access it again, it may have a different hash key already, from a different position that mapped to the same slot. The slot may now belong to another position. Anything you read from it may be wrong, and anything you write to it will overwrite something that you probably did not intend to overwrite.

I try to be more explicit. IN THE Folkert IMPLEMENTATION there are no multilple buckets for the same hash index, so one hash key will ALWAYS map to the SAME memory address (hash % nEntry). Now when I decide to use my pointer:

1) the TT entry is still the same entry (entryes[hash % nEntry].hash == hash), but I overwrite the entry. No problems at all.
2) the TT entry belongs to another position (entryes[hash % nEntry].hash != hash). First question: how it is possible in a single-threaded search? BTW, I should use the entry (that is a replace operation) .... Uhm... Replacement scheme:
2a) always replace: I replace it, stop. No matter what's inside the TT entry. No prolems.
2b) depth preferred: I have to decide if replace the entry or not. So I read through the pointer, or from some other means, but I will actually end up reading the exact SAME entry from the exact SAME memory address. So no different behaviour.

Now, in a TT implementation with multiple buckets per hash index, this is a bit different because an hash key can map to different hash buckets at different addresses, and there is "space" between the READ use of the hash entry (beginning of the search function) and the WRITE use (the end of the search, or at least after a subtree search), and this can change the content of the buckets at the same hash index, making a store through the pointer a very bad decision.

And of course, in a multithreaded search something more can happen, something so weird that your TT entry will change under your compiler's feet between the two 8 bytes read, as Bob said.

What does buckets have to do with this in a non-threaded search? WHO is going to change the bucket between when you compute the bucket address and when you decide to access an entry within the bucket? The alpha/beta search is a sequential process when only using one thread.

[bob]

General comments

1) It's a good practice to code with multithreaded safety for any resource which might be shared in present and future deployments.

2) The region locking technique for transposition tables with, say, 256 spinlocks per table, is fast and portable. If the number of regions is, say, 16 or more times the number of worker threads, then waiting for a region lock will be rare.

3) Very long time C programmers sometimes flinch at code returning a value which doesn't fit into a register. In the Old Days, returning a structure could fail at times if an interrupt occurred at the wrong time and messed with the stack. Not an easy bug to find! The only worry today is returning a pointer or reference to a temporary value; but a decent compiler will issue a warning. If you ever write a compiler, you'll see how it must be the responsibility of the caller to reserve space for a result and to never access an activation frame for a called function.

4) Operation of a transposition table should be well encapsulated. In Symbolic, all access by a search works through the call pair Probe() and Stash(). Pointer to entries are never exposed and neither is the structure of a table entry. Examples from the perft() table:

Code: Select all

  bool Probe(const Position& position, const ui draft, NodeCount& count);
  void Stash(const Position& position, const ui draft, const NodeCount count);

While I agree with your (1) it is not so easy to do, particularly as you start writing a chess engine and have no appreciation for how parallel search is going to work at all. The best example for not falling into this trap was Crafty, because when I started it in late 1994, I knew it would be parallel pretty soon, and with 20 years of parallel programming experience at the time, I designed it to make parallel search easier rather than harder.

But for this pointer discussion, I don't think it unreasonable at all to compute a pointer, perhaps even do a prefetch (several do this, I have not yet resorted to that), and then de-reference the pointer later in the program. In the case of a TT probe, I can't imagine very many ways where one might somehow change a hash entry after the pointer is computed but before it is de-referenced. IE IID might do that since you step out of the main search and do an iterative-deepening search. Or null-move search. But who in their right mind would compute a TT pointer and then do an IID or null-move search and expect that hash entry to remain untouched. On the other hand, the original pointer might point to an unused entry so if you copy it, you get something useless, while after the search, the TT entry might actually have something useful (a good best move in fact, the reason for doing the IID search in the first place). But if you compute the pointer before doing that search, that's pretty lousy programming design and the program will likely fail in many different ways, not just because of the invalidated TT pointer. I think this is less about the TT indexing he is doing, and more about the incorrect use of the term "collision". What he was thinking was an error is something that happens in at least 75% of the middle game nodes we search.

There's no replacement for good design practices, but once you get a program working, optimization for speed is also a practical thing to do, and avoiding speed just to "keep things simple" seems like a bit of a "tip of the king" and resigning one's self to accepting less than optimal performance just because one is not competent to design optimal code and not introduce silly errors/bugs.

Anything can be misused, including pointers. Doesn't mean they are bad however, just means they require a bit of common sense.

[xmas79]

What does buckets have to do with this in a non-threaded search? WHO is going to change the bucket between when you compute the bucket address and when you decide to access an entry within the bucket? The alpha/beta search is a sequential process when only using one thread.

I was referring to something like (pseudo):

Code: Select all

search(a,b)
{
    score = a;
    ptr = hashProbe();
    TryCutoffByUsingPointer(ptr);
    TryHashMoveByUsingPointer(ptr);
    ForAllMoves {
        Make();
        score = -search(b,a)
        UnMake();
        if (score > b) {
            StoreHashByUsingPointer(ptr);
            return score;
        }
    }
    
    if (alphaImproved ) {
            StoreHashByUsingPointer(ptr);
    }
    return score;
}

After the use of ptr in hash move phase there is a search, and it can be very deep, allowing for the TT to be "trashed". With this logic in mind, here's an example:

Suppose we have 4 buckets per hash slot and suppose 64k entries (0xffff is the key hash mask), it can happen that we get a pointer for the hash key 0x12340000, and we get the hash index 0, so buckets 0, 1, 2, 3, corresponding to memory addresses 0, 16, 32, 48 (eg 16 bytes per entry). Suppose the TT is empty, we stores the hash key 0x12340000 at address 0. Then the search goes (among others) through positions 0xfa020000, 0x12fe0000, 0x16930000, 0x98af0000, 0xffb10000 etc... and then again 0x12340000. All these positions will map to hash index 0, however they will go in different buckets. Eg 0xfa020000 in bucket 1, 0x12fe0000 in bucket 2, 0x16930000 in bucket 3. Now 0x98af0000 and 0xffb10000 must be stored and they will eventually replace the entry 0x12340000 in bucket 0. When the position with hash 0x12340000 will be encountered again, it may be stored at a different bucket, so the pointer to the old hash entry is no longer valid.

Hope it was clear what I meant.