Computer Chess Club Archives

Search

Messages

Subject: Programming tip: high entropy bitstream for hash codes

Author: Steven Edwards

Date: 07:19:36 08/20/03

It's useful to have a small, fast, portable, and deterministic source of high
entropy (pseudorandom) bits for generating hash codes for accessesing
transposition tables.  One approach given by Bob Hyatt in Crafty is to use a
good sized state table of pseudorandom values, much like the typical C library
function random(), and use these to produce the bitstream.

I use a somewhat different technique that I believe is better for the limited
purposes of generating the relatively short pseudorandom bitstream needed by
most chess applications.  The high entropy  generator in the CT toolkit is very
simple: the Nth bit of the stream is defined as the number of non distinct prime
factors of N, modulo two.  Here's an example implementation:


typedef CTQwrd CTHash;  // CTQwrd -> unsigned long long int

class CTHC
{
public:
    static void ClassInit(void);
    static void ClassTerm(void);

    static CTHash HashManSqVec[CTManRCLen][CTSqLen];
    static CTHash HashCstlVec[CTCstlLen];
    static CTHash HashEPSqVec[CTSqLen];
    static CTHash HashResultVec[CTResultLen];

private:
    static const bool IsFactorCountOdd(const CTQwrd theNumber);
    static const unsigned int GenerateNextHashBit(void);
    static const CTHash GenerateNextHash(void);

    static CTQwrd HashBitOrdinal;
};

CTHash CTHC::HashManSqVec[CTManRCLen][CTSqLen];
CTHash CTHC::HashCstlVec[CTCstlLen];
CTHash CTHC::HashEPSqVec[CTSqLen];
CTHash CTHC::HashResultVec[CTResultLen];

CTQwrd CTHC::HashBitOrdinal = 0;

const bool CTHC::IsFactorCountOdd(const CTQwrd theNumber)
{
    bool theFlag;

    if (theNumber < 2) theFlag = false;
    else
    {
        CTQwrd theTarget = theNumber;
        CTQwrd theFactorCount = 0;
        CTQwrd theTrialFactor = 2;

        while ((theTrialFactor * theTrialFactor) <= theTarget)
        {
            if (theTarget % theTrialFactor) theTrialFactor++;
            else
            {
                do
                {
                    theTarget /= theTrialFactor;
                    theFactorCount++;
                }
                while (!(theTarget % theTrialFactor));
            };
        };

        if (theTarget > 1) theFactorCount++;
        theFlag = ((theFactorCount % 2) == 1);
    };
    return (theFlag);
}

const unsigned int CTHC::GenerateNextHashBit(void)
{
    return (IsFactorCountOdd(HashBitOrdinal++) ? 1 : 0);
}

const CTHash CTHC::GenerateNextHash(void)
{
    CTHash theHash = 0;

    for (unsigned int bitIndex = 0; bitIndex < (sizeof(CTHash) * CTByteBitLen);
bitIndex++)
    {
        theHash <<= 1;
        theHash |= GenerateNextHashBit();
    };
    return (theHash);
}

void CTHC::ClassInit(void)
{
    // Initialize the man/sq hash code array

    for (unsigned int manIndex = CTManWhitePawn; manIndex <= CTManBlackKing;
manIndex++)
        for (unsigned int sqIndex = CTSqA1; sqIndex <= CTSqH8; sqIndex++)
            HashManSqVec[CTMan(manIndex)][CTSq(sqIndex)] = GenerateNextHash();

    // Initialize the castling ability hash code array

    for (unsigned int cstlIndex = 0; cstlIndex < CTCstlLen; cstlIndex++)
        HashCstlVec[CTCstl(cstlIndex)] = GenerateNextHash();

    // Initialize the en passant file hash code array

    for (unsigned int sqIndex = CTSqA1; sqIndex <= CTSqH8; sqIndex++)
        HashEPSqVec[CTSq(sqIndex)] = GenerateNextHash();

    // Initialize the game result hash code array

    for (unsigned int resultIndex = 0; resultIndex <= CTResultLen;
resultIndex++)
        HashResultVec[CTSq(resultIndex)] = GenerateNextHash();
}

void CTHC::ClassTerm(void)
{
}

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.