Re: [Bug-gnubg] Gnubg's Cache and Plies > 3 - problem?

[Jonathan Kinsey]

Note that all 32 bits are used if REDUCTION_CODE is defined. I'm not sure what
the "reduction code" does exactly (something about reducing the number of rolls
used in evaluations for a quicker less accurate calculation?), is it a failed
experiment or is it actually used in general?

I'm all for removing this code if it was found to have little use.

Jon


Michael Petch wrote:
>
> Hi Guys,
>
> We seem to have a problem with the cache and it seems to relate to 4ply. The
> issue Michael Depreli found seems to shift around based on size of cache.
>>From my tests things seem correct if cache is 0 and the bigger it gets the
> more likely there are problems.
>
> I began reviewing cache.c and have a major concern that 4 ply exceeds our
> ability to represent a cache key uniquely. I am thinking out loud here, so
> anyone can correct me. Eval.c has this:
>
> /*
> * Bit 00-01: nPlies
> * Bit 02 : fCubeful
> * Bit 03-10: rNoise
> * Bit 11 : fMove
> * Bit 12 : fUsePrune
> * Bit 13-17: anScore[ 0 ]
> * Bit 18-22: anScore[ 1 ]
> * Bit 23-26: log2(nCube)
> * Bit 27-28: fCubeOwner
> * Bit 29 : fCrawford
> */
>
> iKey = (
> ( nPlies ) |
> ( pec->fCubeful << 2 ) |
> ( ( ( (int) ( pec->rNoise * 1000 ) ) & 0x00FF ) << 3 ) |
> ( pci->fMove << 11 ) );
>
> Clearly nPlies is forced to the 2 low bits.
>
> The problem with this is that 2 bits represents 4 values (plies):
> 00,01,10,11 (0-3) Of course nPlies = 4 will be 100 (3 bits) when or'ed with
> ( pec->fCubeful << 2 ) will inadvertently turn the cubeful flag on even when
> its fCubeful is 0. As well 4 ply now becomes 0 ply!. One might say the code
> could be revised to be:
>
> iKey = (
> ( nPlies & 0x03 ) |
> ( pec->fCubeful << 2 ) |
> ( ( ( (int) ( pec->rNoise * 1000 ) ) & 0x00FF ) << 3 ) |
> ( pci->fMove << 11 ) );
>
> The code is also automatically assuming other variables don't exceed their
> expected values (Except Noise, it masks off any extra bits in the code
> snippet above. This would sop the plies from colliding with the other flags
> but 0ply and 4ply are the same, 1ply and 5ply are the same etc).
>
> To make things worse cache.c also uses these keys in the hashing function.
> In cache.c comparisons are done based on the raw keys (eg):
>
> if ((pc->entries[l].nd_primary.nEvalContext != e->nEvalContext ||
> memcmp(pc->entries[l].nd_primary.key.auch, e->key.auch,
> sizeof(e->key.auch)) != 0))
> { /* Not in primary slot */
> if ((pc->entries[l].nd_secondary.nEvalContext != e->nEvalContext ||
> memcmp(pc->entries[l].nd_secondary.key.auch, e->key.auch,
> sizeof(e->key.auch)) != 0))
> { /* Cache miss */
>
> So now the raw bits of the keys are being compared. But we know ply levels
> can't be uniquely store for plies above 3. So now we get false hits in the
> cache (4ply return 0 ply results). This seems to jive with what Michael
> Depreli and I are seeing when a large cache size is used.
>
> Basically 2 bits isn't enough to accurately describe plies, and is
> ptoentially cascading into cache issues. There seems to be an extra 3 bits
> of the structure above that aren't used. Coincidentally There has been
> discussion of changing this Key (for performance reasons I believe). I think
> we need to do something immediately to deal with the ply issues and the
> cache.
>
> When the cache size is set to 0 there is no problem because nothing gets
> stored and all evals are done from scratch. The bigger the cache the more
> likely you will have 4 ply colliding with 0 ply, 5ply with 1 ply etc.
> And of
> course When ply> 3 of one can't trust the cubeful flag isn't being
> obliterated, and who knows what that is doing to results.
>
> I consider this a serious issue. Any thought or feedback would be
> welcome. I
> May also be missing something, so let me know
>
> Michael
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Bug-gnubg mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/bug-gnubg

---

New! Receive and respond to mail from other email accounts from within Hotmail Find out how.