Hello, i have an alpha beta algorithm with transposition tables. in my implementation i get an inaccessible memory error when my program runs. I cannot locate my error. I think my main problem is to build the hash. I cannot understand how to build the hash. The problem is that the hash needs a size but i cannot give it a size because the hash grows during the program? Or did i misunderstood something? Second is the array for calculating the zobrist keys. I have a two-dimensional array where there are two position in the second dimension. One for the black player and one for the white player. In the function init_hashes (see below) i fill them with random numbers. Afterwards to calculate the key i go through the 8 x 8 positions (a game like checkers, clobber) and test if there is a white or a black stone and accordingly to this i take the random number from dimension one or two and do the XOR operation. Is this correct? Probably one could tell me where my problem lies: I commented the code a bit.

#define hash_exact 0
#define hash_alpha 1
#define hash_beta 2
typedef struct hash{
        long long key;
        int depth;
        int value;
        int flags;
}HASHE;

//the game is a 8x8 field and there are the colors
//white and black. it is a game like clobber or checkers
long long init_table[64][2];
//my hash where to store the positions.
//the value 2^64 i'm not sure about. I didn't found anything
//which explained how to dimension this hash
HASHE hash_table[2^64];

.....
void class::init_hashes()
{
        for (int i = 0; i < 64; i++)
        {
                init_table[0] = rand64();
                init_table[1] = rand64();
        }
}

int class::probe_hash(int depth, int alpha, int beta)
{
        long long zob_key = zobrist_key();
        HASHE * h = &hash_table[zob_key % 2^64];
        //HASHE * h = &hash_table[0];


        if(h->key == zob_key)
        {
                if(h->depth >= depth)
                {
                        if((h->flags == hash_exact))
                                return h->value;
                        if((h->flags == hash_alpha) && (h->value <= alpha))
                                return alpha;
                        if((h->flags == hash_beta) && (h->value >=beta))
                                return beta;
                }
                //bestMove = h->move;
        }
        return 0;
}

void record_hash(int depth, int val, int hashf)
{
        //HASHE * h = &hash_table[zobrist_key() % 64];
        HASHE * h = &hash_table[zobrist_key() % 2^64];

        //THE PROGRAM CANNOT DO THE FOLLOWING INSTRUCTION
        // bUT THERE IS ENOUGH MEMORY LEFT I TRIED THIS!!!!!
        h->key = zobrist_key();
        h->value = val;
        h->flags = hashf;
        h->depth = depth;
        //h->move = bestMove;
}

HASHE hash_table[2^64];


There is no way your computer have that amount of memory, even by swapping on a gigangitic array of hard drives. The only reason you see that there is enough memory left is that the array if never allocated, which explain the bad memory access.

Lets ignore HASHE's size:

2^64 byte = 2^54K = 2^44meg = 2^34 Gig = 2^24 Tera.

You are trying to alloc an array big enough to fit the internet.

This line

HASHE hash_table[2^64];

should cause a crash. You're asking the computer to allocate room for 18,446,744,073,709,551,616 records!!!

I'll try to explain transposition tables:

Think of your hash like a key, or a fingerprint. The key consists of bits. The key is ALWAYS a fixed length in terms of the number of bits. If it's a 16 bit key, there are 65535 possibe keys.

In the code you have it looks like you're trying to use a 64 bit key, and actually allocate space for every possible key!

To create the key you pre-initialize a table of 'sub keys'. Each piece, at each position, gets it's own unique sub key (which is just a random number);


int subkey[MAX_PLAYER][PIECE_TYPES][BOARD_WIDTH][BOARD_HEIGHT];

At each of these locations you just make a random number.

subKey[WHITE][KNIGHT][x][y] = randomNumberGenerator(2^32);  // 2^32 or 2^64 if you want 'long long'.

To compute a hash key for any given board, you go through each piece and start XORing the appropriate subkeys in..

piece = myBoard[x][y];switch ( piece){    case PAWN:       myBoard.hashKey = myBoard.hashKey XOR subKey[WHITE][PAWN][x][y];       break;}

Of course you wouldn't actually recompute an entire hash for each board, which is why we're using XOR, but this is the best way to start and verify that your hasing is working.


You still need a place to store you hash keys. For this you make a table. The table does not have to be able to store EVERY SINGLE HASH PERMUATION. As long a your hash table length is a power of 2 in size, you can do this:

HASH_RECORD bigHashTable[ 2 ^ 16];...bigHashTable [ myBoard.hashKey & 0xFFFF].alphaScore = alphaScore;

See what I'm getting at? For precision, you store a copy of the hash key in your hash structure.

bigHashTable[myHashKey].bigLongPreciseVersionOfMyHash = myBoard.hashKey;

This way you can use the hash as a quick index in to the transposition table, and you also get to use it to make sure two boards are really identical.

That's generally how hasing works. In your move generator you'll usually have routines like movePiece() which will modify a given boards hash code.

For example, if you moved a PAWN from 1,1, to 1,2 you'd do this:

myBoard.hashKey = myBoard.hashKey XOR subKey[WHITE][PAWN][1][1];myBoard.hashKey = myBoard.hashKey XOR subKey[WHITE][PAWN][1][2];

This removes the pawn from 1, 1, and then places it back at 1, 2, as a hash key.

You'll need to add special hash codes for things like castling, did the king move, whos' turn is it, etc. because there are many boards that look identical from the pieces but are not identical at all.

I hope this has helped. Getting transposition working can be a lot of work simply because finding mistakes is tough to do. I wrote something about this awhile ago here on GameDev in this forum..

On my website, under 'My Projects' I have a not-so-technical description of ChessPig, my Chess program. You might find it helpful, but like I said, it's not very technical.


Will

Great!
Thanks a lot for your detailed explanation!
I realize the my failure i've done.
Calculating the hash keys i got yet (hopefully)
But i've still a little problem with the hash where the positions are to be stored.
Because there is the structure:

typedef struct hash{        long long key;        int depth;        int value;        int flags;}HASHE;

and in function probeHash to check whether a found position
is already within the hash
there is the statement:

HASHE * h = &hash_table[zobrist_key() % table_size()];

there is my problem. This hash_table (i think this is the hash_table where the positions are stored) has to be instantiated in the beginning or not, but how - the size should be something dynamic because i do not know how many positions will be stored at the end? And how do i get the table_size because
something like hash_table.size() is only available for arrays and not my structure.
If you could explain these last two things i would be very glad.

Thanks for your help. Really.

You're trying to cut-and-paste move transposition in to your code and it's probably not going to work. It's VERY hard to get working because it's very hard hard to debug.

Honestly, I think you should stop and try to understand how hashing works.


That said...

Pre allocate the hash table. You DO know the size.. table_size().

HASHE hash_table[table_size()];

Will

You can't possibly store all the positions that you visit, or at least not under slow time controls, so what you do is set a fixed size for the hash table, or perhaps make the size an option, but you certainly don't change the size in the middle of a search. If you don't have space to add a new position, you need to forget something. How you decide what to forget is called a "replacement scheme", and there is some literature over what schemes are best. One reasonable way of doing it is trying to put your position on the entry that it should go to (zobrist%table_size), or the next entry, or the next, or the next. This would be called "using 4 probes". If they are all occupied, you can replace the one that had the lowest depth left, or some other simple heuristic of that sort. If they all had more depth than the new position, don't store the new position.

Well, there are many details to decide, and the only way to determine which set of decisions works best for your program is testing.

Anyway, if you are just trying to get your hash working, try using a really simple replacement scheme: overwrite if the new position has more depth left. Once you get that working, you can refine your replacement scheme.

isn't 2^64 in C++, the same as 2 xor 64?

in other words 66 entries?

Quote: Original post by Nice Coder
isn't 2^64 in C++, the same as 2 xor 64?

in other words 66 entries?

That is true.. Looking back at the original code posting I can't actually seem to find 2^64 defined in code, only in the comment.

Except:

the line:

zob_key % 2^64

which is used to cap the index in to an array.

Trouble all around. lol. Good eye NC.