A hashing problem.

[Chan Rasjid]

I have a hashing situation I cannot resolve.

My engine found a PV at root and say the first 3 moves are pv1, pv2, pv3. It played pv1 as the best move and the opponent followed this line and replied with pv2. At the next root search a variable followPV is set to "true" when it is verified the move list has pv3 which will be the first move tried (swapped to the front).

For some reason, I do a hash probe at the very start of rootsearch():

Code: Select all

if (probehit) {
switch (type){
case EXACT :
...
case LOWER:
assert(!followPV);// triggered, why?
hashmove = ...; //info I have lost 

}

}

I can't understand why the assert is triggered. I am certain my hashing is ok and has no collision with more than 32 bits for signature. This assert failure is very recent and almost never triggered before. I expect there should be a probe hit with EXACT and hashmove = pv3, not a probe hit of LOWER.

Can anyone help.

Thanks,
Rasjid

[Chan Rasjid]

I have a hashing situation I cannot resolve.

My engine found a PV at root and say the first 3 moves are pv1, pv2, pv3. It played pv1 as the best move and the opponent followed this line and replied with pv2. At the next root search a variable followPV is set to "true" when it is verified the move list has pv3 which will be the first move tried (swapped to the front).

For some reason, I do a hash probe at the very start of rootsearch():

Code: Select all

if (probehit) {
switch (type){
case EXACT :
...
case LOWER:
assert(!followPV);// triggered, why?
hashmove = ...; //info I have lost 

}

}

I can't understand why the assert is triggered. I am certain my hashing is ok and has no collision with more than 32 bits for signature. This assert failure is very recent and almost never triggered before. I expect there should be a probe hit with EXACT and hashmove = pv3, not a probe hit of LOWER.

Can anyone help.

Thanks,
Rasjid

I think that any probe hit should not be LOWER is correct.

I think I have found the bug and, as usual, must have been introduced through code changes. It is due to a "corrupted PV" not properly initialized. At startup, it should be:
pv[0][0] = 0;
pv[0][1] = 0;//(this was missing) so there is no opponent best moves yet;

The opponent was wrongly taken to be following PV by comparing just pv[0][1] (corrupted ) not knowing there was no PV yet; ie PV[0][0] == 0.

BTW, my experience with maintaining the PV or monitoring following PV through a variable bool isFollowPV could easily be a recurring source of bug.

Does anyone know if it is not necessary to care about isFollowPV?

Best Regards,
Rasjid

[bob]

I have a hashing situation I cannot resolve.

My engine found a PV at root and say the first 3 moves are pv1, pv2, pv3. It played pv1 as the best move and the opponent followed this line and replied with pv2. At the next root search a variable followPV is set to "true" when it is verified the move list has pv3 which will be the first move tried (swapped to the front).

For some reason, I do a hash probe at the very start of rootsearch():

Code: Select all

if (probehit) {
switch (type){
case EXACT :
...
case LOWER:
assert(!followPV);// triggered, why?
hashmove = ...; //info I have lost 

}

}

I can't understand why the assert is triggered. I am certain my hashing is ok and has no collision with more than 32 bits for signature. This assert failure is very recent and almost never triggered before. I expect there should be a probe hit with EXACT and hashmove = pv3, not a probe hit of LOWER.

Can anyone help.

Thanks,
Rasjid

Strange things happen with respect to hashing. All that matters is the signature match. And entries can get overwritten at unexpected times. To solve this, the last thing I do in Crafty before starting the next iteration is to take the current PV array, and make certain the correct best move is stored for each PV move. I take the original signature, and if it matches a hash entry, I simply stuff the PV move into the entry. If it doesn't match a hash entry, I create one that contains the correct move, but a "worthless" type. I repeat for each move in the PV. Then this never happens.

[Chan Rasjid]

I am not too sure what you mean. I guess it relates to my original post and that a PV should usually be intact in the TT.

Some programmers seem to be confident that a PV will always be intact in the TT and do not think there is a need to keep an array pv[][]. This is also what I think and it is the reason I have an assert() in my OP. Although I cannot (yet) see how the PV could be overwritten, I have the pv array as it is clean and might be of some benefit. I am confident in my hashing implementation as the codes are old and well asserted, like any hashmove should be verified to be in the move list and it never failed. My signature has 64-26 = 38 bits so the collision should be near zero! The 26 bits store a board piece/color/type index to monitor if a TT entry is outdated and unreachable at root and they too contribute a little to signature verification. I still have to think a little if I could resolved, once and for all, if the PV could be overwritten - they should not be.

My guess of what you mean is that after every iteration, you would make/unmake the pv moves and verify through the hash key that the pv moves/nodes are ok in the TT (which should be). If not, you would "note" it with a "worthless" type. I don't know why you do this as the number of nodes of the TT that are affected for a search go into many thousands.

As for me, I now want to have a greater certainty that my program is "without" bugs so I care about the asserts whenever I make any code changes.

Best Regards,
Rasjid

[bob]

I am not too sure what you mean. I guess it relates to my original post and that a PV should usually be intact in the TT.

Some programmers seem to be confident that a PV will always be intact in the TT and do not think there is a need to keep an array pv[][]. This is also what I think and it is the reason I have an assert() in my OP. Although I cannot (yet) see how the PV could be overwritten, I have the pv array as it is clean and might be of some benefit. I am confident in my hashing implementation as the codes are old and well asserted, like any hashmove should be verified to be in the move list and it never failed. My signature has 64-26 = 38 bits so the collision should be near zero! The 26 bits store a board piece/color/type index to monitor if a TT entry is outdated and unreachable at root and they too contribute a little to signature verification. I still have to think a little if I could resolved, once and for all, if the PV could be overwritten - they should not be.

My guess of what you mean is that after every iteration, you would make/unmake the pv moves and verify through the hash key that the pv moves/nodes are ok in the TT (which should be). If not, you would "note" it with a "worthless" type. I don't know why you do this as the number of nodes of the TT that are affected for a search go into many thousands.

As for me, I now want to have a greater certainty that my program is "without" bugs so I care about the asserts whenever I make any code changes.

Best Regards,
Rasjid

I can absolutely guarantee you that if you depend on always extracting the PV from the hash table, you will be disappointed. Extensions change the depth of sub-trees, and the farther from the root you go, the greater the chance that a PV move will get overwritten by a different of the same position but with greater depth (draft). And a different best move.

The PV array is the right way to do this, and then rather than having explicit code to order the PV moves first, I simply stuff the PV moves into the hash table between iterations so that I will always have a hash move to make me follow the PV for as far as it goes.

When you are trying to mentally grasp what is going on, don't think about the PV moves near the root, think about those that are farther from the root. Where transpositions can occur with more frequency, and where you can have depths that are different enough that overwrites occur. Think about reaching a position P from a sequence of moves with zero checks, so that at the 20th move in the PV, you have a draft (remaining depth) of 4, and you store the best (PV) move. Then you search a different path, perhaps with lots of checks, so that you again reach this position via a different (sometimes even shorter) path, and now you have a larger remaining depth and you overwrite with a different move and score, same position.

[Chan Rasjid]

I am not too sure what you mean. I guess it relates to my original post and that a PV should usually be intact in the TT.

Some programmers seem to be confident that a PV will always be intact in the TT and do not think there is a need to keep an array pv[][]. This is also what I think and it is the reason I have an assert() in my OP. Although I cannot (yet) see how the PV could be overwritten, I have the pv array as it is clean and might be of some benefit. I am confident in my hashing implementation as the codes are old and well asserted, like any hashmove should be verified to be in the move list and it never failed. My signature has 64-26 = 38 bits so the collision should be near zero! The 26 bits store a board piece/color/type index to monitor if a TT entry is outdated and unreachable at root and they too contribute a little to signature verification. I still have to think a little if I could resolved, once and for all, if the PV could be overwritten - they should not be.

My guess of what you mean is that after every iteration, you would make/unmake the pv moves and verify through the hash key that the pv moves/nodes are ok in the TT (which should be). If not, you would "note" it with a "worthless" type. I don't know why you do this as the number of nodes of the TT that are affected for a search go into many thousands.

As for me, I now want to have a greater certainty that my program is "without" bugs so I care about the asserts whenever I make any code changes.

Best Regards,
Rasjid

I can absolutely guarantee you that if you depend on always extracting the PV from the hash table, you will be disappointed. Extensions change the depth of sub-trees, and the farther from the root you go, the greater the chance that a PV move will get overwritten by a different of the same position but with greater depth (draft). And a different best move.

The PV array is the right way to do this, and then rather than having explicit code to order the PV moves first, I simply stuff the PV moves into the hash table between iterations so that I will always have a hash move to make me follow the PV for as far as it goes.

When you are trying to mentally grasp what is going on, don't think about the PV moves near the root, think about those that are farther from the root. Where transpositions can occur with more frequency, and where you can have depths that are different enough that overwrites occur. Think about reaching a position P from a sequence of moves with zero checks, so that at the 20th move in the PV, you have a draft (remaining depth) of 4, and you store the best (PV) move. Then you search a different path, perhaps with lots of checks, so that you again reach this position via a different (sometimes even shorter) path, and now you have a larger remaining depth and you overwrite with a different move and score, same position.

"You have spoken...". Your experience is better than mine.

OK, this is exactly what I wanted to resolve and I had a little inkling about "IF" the same node could be reached after the PV through transposition higher up, whatsoever..., that came back with another best move, type = lower ... but hashed and failed to alter the PV.

Rasjid

[bob]

I am not too sure what you mean. I guess it relates to my original post and that a PV should usually be intact in the TT.

Some programmers seem to be confident that a PV will always be intact in the TT and do not think there is a need to keep an array pv[][]. This is also what I think and it is the reason I have an assert() in my OP. Although I cannot (yet) see how the PV could be overwritten, I have the pv array as it is clean and might be of some benefit. I am confident in my hashing implementation as the codes are old and well asserted, like any hashmove should be verified to be in the move list and it never failed. My signature has 64-26 = 38 bits so the collision should be near zero! The 26 bits store a board piece/color/type index to monitor if a TT entry is outdated and unreachable at root and they too contribute a little to signature verification. I still have to think a little if I could resolved, once and for all, if the PV could be overwritten - they should not be.

My guess of what you mean is that after every iteration, you would make/unmake the pv moves and verify through the hash key that the pv moves/nodes are ok in the TT (which should be). If not, you would "note" it with a "worthless" type. I don't know why you do this as the number of nodes of the TT that are affected for a search go into many thousands.

As for me, I now want to have a greater certainty that my program is "without" bugs so I care about the asserts whenever I make any code changes.

Best Regards,
Rasjid

I can absolutely guarantee you that if you depend on always extracting the PV from the hash table, you will be disappointed. Extensions change the depth of sub-trees, and the farther from the root you go, the greater the chance that a PV move will get overwritten by a different of the same position but with greater depth (draft). And a different best move.

The PV array is the right way to do this, and then rather than having explicit code to order the PV moves first, I simply stuff the PV moves into the hash table between iterations so that I will always have a hash move to make me follow the PV for as far as it goes.

When you are trying to mentally grasp what is going on, don't think about the PV moves near the root, think about those that are farther from the root. Where transpositions can occur with more frequency, and where you can have depths that are different enough that overwrites occur. Think about reaching a position P from a sequence of moves with zero checks, so that at the 20th move in the PV, you have a draft (remaining depth) of 4, and you store the best (PV) move. Then you search a different path, perhaps with lots of checks, so that you again reach this position via a different (sometimes even shorter) path, and now you have a larger remaining depth and you overwrite with a different move and score, same position.

"You have spoken...". Your experience is better than mine.

OK, this is exactly what I wanted to resolve and I had a little inkling about "IF" the same node could be reached after the PV through transposition higher up, whatsoever..., that came back with another best move, type = lower ... but hashed and failed to alter the PV.

Rasjid

This is an old topic. The first time someone suggested using the hash table to retrieve the PV I tried it as I liked the idea of dumping the PV array as well. What I did was after an iteration completed, I retrieved as much of the PV as I could from the hash table. And then I computed the static evaluation (this was back in the days when crafty hashed everything including q-search). And I noticed that in a major of cases, the PV score and the static eval did not agree. As I looked further, I found that some PVs were impossibly long (if you added up the length, adjusted for checks, etc, the PV was still too long) and some where impossibly short. You can already get short PVs with the PV array, thanks to exact hash hits. And I even probe at the end of a hash hit PV to see if I can retrieve additional moves to fill out the PV.

In short, this hashing stuff is about 50% engineering and 50% voodoo. I simply insist that in Crafty, I be able to see the end of the PV and be able to call Evaluate() from that position and get the same score as was backed up during the search, so that I can debug things.

[Chan Rasjid]

I am not too sure what you mean. I guess it relates to my original post and that a PV should usually be intact in the TT.

Some programmers seem to be confident that a PV will always be intact in the TT and do not think there is a need to keep an array pv[][]. This is also what I think and it is the reason I have an assert() in my OP. Although I cannot (yet) see how the PV could be overwritten, I have the pv array as it is clean and might be of some benefit. I am confident in my hashing implementation as the codes are old and well asserted, like any hashmove should be verified to be in the move list and it never failed. My signature has 64-26 = 38 bits so the collision should be near zero! The 26 bits store a board piece/color/type index to monitor if a TT entry is outdated and unreachable at root and they too contribute a little to signature verification. I still have to think a little if I could resolved, once and for all, if the PV could be overwritten - they should not be.

My guess of what you mean is that after every iteration, you would make/unmake the pv moves and verify through the hash key that the pv moves/nodes are ok in the TT (which should be). If not, you would "note" it with a "worthless" type. I don't know why you do this as the number of nodes of the TT that are affected for a search go into many thousands.

As for me, I now want to have a greater certainty that my program is "without" bugs so I care about the asserts whenever I make any code changes.

Best Regards,
Rasjid

I can absolutely guarantee you that if you depend on always extracting the PV from the hash table, you will be disappointed. Extensions change the depth of sub-trees, and the farther from the root you go, the greater the chance that a PV move will get overwritten by a different of the same position but with greater depth (draft). And a different best move.

The PV array is the right way to do this, and then rather than having explicit code to order the PV moves first, I simply stuff the PV moves into the hash table between iterations so that I will always have a hash move to make me follow the PV for as far as it goes.

When you are trying to mentally grasp what is going on, don't think about the PV moves near the root, think about those that are farther from the root. Where transpositions can occur with more frequency, and where you can have depths that are different enough that overwrites occur. Think about reaching a position P from a sequence of moves with zero checks, so that at the 20th move in the PV, you have a draft (remaining depth) of 4, and you store the best (PV) move. Then you search a different path, perhaps with lots of checks, so that you again reach this position via a different (sometimes even shorter) path, and now you have a larger remaining depth and you overwrite with a different move and score, same position.

"You have spoken...". Your experience is better than mine.

OK, this is exactly what I wanted to resolve and I had a little inkling about "IF" the same node could be reached after the PV through transposition higher up, whatsoever..., that came back with another best move, type = lower ... but hashed and failed to alter the PV.

Rasjid

This is an old topic. The first time someone suggested using the hash table to retrieve the PV I tried it as I liked the idea of dumping the PV array as well. What I did was after an iteration completed, I retrieved as much of the PV as I could from the hash table. And then I computed the static evaluation (this was back in the days when crafty hashed everything including q-search). And I noticed that in a major of cases, the PV score and the static eval did not agree. As I looked further, I found that some PVs were impossibly long (if you added up the length, adjusted for checks, etc, the PV was still too long) and some where impossibly short. You can already get short PVs with the PV array, thanks to exact hash hits. And I even probe at the end of a hash hit PV to see if I can retrieve additional moves to fill out the PV.

In short, this hashing stuff is about 50% engineering and 50% voodoo. I simply insist that in Crafty, I be able to see the end of the PV and be able to call Evaluate() from that position and get the same score as was backed up during the search, so that I can debug things.

Thanks.

It should be an old topic but I could have missed the details.

I think the the logical explanation you gave is rigorous. I was thinking of asking if you did some tests of it.

So my implementation is ok and I will see if I need to take any action.

Best Regards,
Rasjid.