search statistics

[JacquesRW]

Looking at the source code for Neuromancer, a possible cause for the low legality rates could be due to your transposition table being a set of entries. As far as I'm aware, most engines use a bucket system, where you index into a bucket of 4/8 entries (depending on entry size, to be 64byte aligned), and then do whatever replacement scheme. With the entries only, whenever there is a hash collision (two different positions get given the same index), they will overwrite each other. In your search, before pruning with the hash table score you check first that the tt hash is the same as the current position hash, is it possible you've forgotten to do this before testing the move for legality? In tandem with the above collisions it could explain the legality rates, especially in midgame positions when different moves may not change the lower bits in the hash (the only bits that matter for modulo table size, as the table is nowhere near big enough for the index to be affected by the later bits). Your calculating hash key code looks perfect as far as I can tell.

[tcusr]

Looking at the source code for Neuromancer, a possible cause for the low legality rates could be due to your transposition table being a set of entries. As far as I'm aware, most engines use a bucket system, where you index into a bucket of 4/8 entries (depending on entry size, to be 64byte aligned), and then do whatever replacement scheme. With the entries only, whenever there is a hash collision (two different positions get given the same index), they will overwrite each other.

i thought that the bucket system was an improvement to squeeze out more performance out of the TT, i was very wrong apparently.
but how does always-replace work in the bucket? i still have to check for something (depth or age).

In your search, before pruning with the hash table score you check first that the tt hash is the same as the current position hash, is it possible you've forgotten to do this before testing the move for legality? In tandem with the above collisions it could explain the legality rates, especially in midgame positions when different moves may not change the lower bits in the hash (the only bits that matter for modulo table size, as the table is nowhere near big enough for the index to be affected by the later bits). Your calculating hash key code looks perfect as far as I can tell.

i don't check for the legality of the tt move because i don't use staged move generation, i generate all the moves and if the tt move happens to be there i give it a very high score.
i never bothered to check if it was actually there for the same reason why i did not implement a bucket system in the first place

thank you for checking out my code, i'm going to fix it ASAP.

[JacquesRW]

i thought that the bucket system was an improvement to squeeze out more performance out of the TT, i was very wrong apparently.
but how does always-replace work in the bucket? i still have to check for something (depth or age).

My always-replace system is first to replace entries from previous searches, if there are none then entries with the same key but lower depth (instead of replacing a collision that's also in the bucket first), and then if there are none of those I just replace the entry with lowest depth. Testing a few different schemes probably wouldn't hurt, I need to as I'm fairly sure prioritising replacing entries from 1 search ago is not a good idea.

i don't check for the legality of the tt move because i don't use staged move generation, i generate all the moves and if the tt move happens to be there i give it a very high score.

Ah yeah so its probably just getting a collision, and getting a move for a different position.

[tcusr]

i thought that the bucket system was an improvement to squeeze out more performance out of the TT, i was very wrong apparently.
but how does always-replace work in the bucket? i still have to check for something (depth or age).

My always-replace system is first to replace entries from previous searches, if there are none then entries with the same key but lower depth (instead of replacing a collision that's also in the bucket first), and then if there are none of those I just replace the entry with lowest depth. Testing a few different schemes probably wouldn't hurt, I need to as I'm fairly sure prioritising replacing entries from 1 search ago is not a good idea.

i don't check for the legality of the tt move because i don't use staged move generation, i generate all the moves and if the tt move happens to be there i give it a very high score.

Ah yeah so its probably just getting a collision, and getting a move for a different position.

it worked! 0% of illegal tt moves on all my test positions.
i still have to tweak my entry so that i can add a new "age" member and still fit in 16 bytes. i'll test more replacement schemes after.
thank you man!

[likeawizard]

Code: Select all

info depth 1  AB nodes 1        QS nodes 21       (95.45%) cutoff by tt move 0       (0.00 %) cutoff by capture 0       (0.00%)

I am working on creating such stats inside my own engine so I can properly start tweaking my search function. How can you have 1 AB and 21 QS nodes at the starting pos? Shouldn't it be 1 AB the actual start position and 20 QS - positions after all the 20 legal moves?

[JacquesRW]

Code: Select all

info depth 1  AB nodes 1        QS nodes 21       (95.45%) cutoff by tt move 0       (0.00 %) cutoff by capture 0       (0.00%)

I am working on creating such stats inside my own engine so I can properly start tweaking my search function. How can you have 1 AB and 21 QS nodes at the starting pos? Shouldn't it be 1 AB the actual start position and 20 QS - positions after all the 20 legal moves?

The QS should be the 0 at depth 1 because there are no captures, when are you counting the nodes in AB and QS?

[likeawizard]

The line is taken from the data in the OP, so that question should be addressed to the author.

The way I count them is:
I increment qNodes at the top of my qSearch function.
I increment regular nodes inside my negamax function but only after the depth check where I run the qSearch at depth=0.

So when I run my search on the start position. I run the negamax on the start pos so I get AB = 1, then I call 20 negamax with depth=0 which are then run as qSearches.

So it makes sense for there to be 1 AB and 20 QS, but the author is reporting 21 QS.

Here's my code:
AB++ https://github.com/likeawizard/chess-go ... eta.go#L22
QS++ https://github.com/likeawizard/chess-go ... eta.go#L98

[JacquesRW]

The line is taken from the data in the OP, so that question should be addressed to the author.

The way I count them is:
I increment qNodes at the top of my qSearch function.
I increment regular nodes inside my negamax function but only after the depth check where I run the qSearch at depth=0.

So when I run my search on the start position. I run the negamax on the start pos so I get AB = 1, then I call 20 negamax with depth=0 which are then run as qSearches.

So it makes sense for there to be 1 AB and 20 QS, but the author is reporting 21 QS.

Here's my code:
AB++ https://github.com/likeawizard/chess-go ... eta.go#L22
QS++ https://github.com/likeawizard/chess-go ... eta.go#L98

Ah sorry I should’ve read more carefully.

[tcusr]

Code: Select all

info depth 1  AB nodes 1        QS nodes 21       (95.45%) cutoff by tt move 0       (0.00 %) cutoff by capture 0       (0.00%)

I am working on creating such stats inside my own engine so I can properly start tweaking my search function. How can you have 1 AB and 21 QS nodes at the starting pos? Shouldn't it be 1 AB the actual start position and 20 QS - positions after all the 20 legal moves?

i count AB nodes only if depth > 0 because otherwise i would count nodes twice wouldn't i? (when reporting them to the GUI, not specifically here).
to get the QS nodes i just changed the counter that is increased inside QS, this way AB + QS is the same number of nodes that my engine reports to the GUI when normally searching.

[likeawizard]

i count AB nodes only if depth > 0 because otherwise i would count nodes twice wouldn't i? (when reporting them to the GUI, not specifically here).
to get the QS nodes i just changed the counter that is increased inside QS, this way AB + QS is the same number of nodes that my engine reports to the GUI when normally searching.

Yea, that all makes sense to me. But you report hitting 1 AB (initial position depth=1) and then 21 QS... Since there are only 20 legal moves in the starting position where does that one extra QS come from? Is it a miscalculation of QS nodes, like calculating a QS twice for some reason or including the 1 AB to the count of QS? Or does your QS actually looks at a reply of black in one of the 20 moves? The percentage you report implies 21/22 = 95.45% (QS/(AB+QS))