Search with transposition table

[geko]

Hi
below the simple implementation of search with transposition table; the result is bad
in some cases it is necessary to disable the use of the table?
any advice?
thank you
G.

Code: Select all

int search(int side, int depth, int alpha, int beta, u64 zobristKey) {

	char hashf = hashfALPHA;
	int score = -_INFINITE;

	Thash * phashe = &hash_array[zobristKey % HASH_SIZE];

	if (phashe->zobristKey == zobristKey && phashe->depth >= depth) {

		if (phashe->flags == hashfEXACT) {
                        updatePv(phashe->best);
			return phashe->score;
		}
		else
		if (phashe->flags == hashfBETA) {
			if (phashe->score >= beta){
                                updatePv(phashe->best);
				return phashe->score;
                        }
			alpha = max(alpha, phashe->score);
		}
		else if (phashe->flags == hashfALPHA) {
			if (phashe->score < alpha){
                                updatePv(phashe->best);
				return phashe->score;
                        }
			beta = min(beta, phashe->score);
		}
	}

	if (depth == 0)
		return quiescence();

	int n_moves=generateMoves();
	Tmove best;
	for (ii = 0; ii < n_moves; ii++) {
		move = getMoves(ii);
		if (ii == 0)
			memcpy(&best, move, sizeof(Tmove));

		makemove (move);
		val = -search(side ^ 1, depth - 1, -beta, -alpha, makeZobristKey());

		if (val > score){
			memcpy(&best, move, sizeof(Tmove));
			score =  val;
		}
		takeback(move);

		if (score >= beta) {
			storeHash(depth, hashfBETA, zobristKey, score, move);
			return score;
		}
		if (score > alpha) {
			hashf = hashfEXACT;
			memcpy(&best, move, sizeof(Tmove));
                       updatePv(mossa);
		}
	}
	storeHash(depth, hashf, zobristKey, score, &best);
	return score;
}

[User923005]

You failed to check the confirmation bits.
Chances are very good you have a bug in your hash formation.
Most often, this occurs with:
Castle flags
Side to move
E.p. square
Null move

How to fix it:
1. Make two different hash formulations. The first one eats the whole board with all relevant flags and spits out the hash. The second hash is the normal incremental Zobrist hash. When you are in debug mode, check the incremental Zobrist hash against the one that is formed from the ground up. If they disagree, then sprinkle board hash checks in different places that you update your hash until you find the boo-boo.
2. Store the extra bits of the hash in the hash table. (e.g. if you have a 64 bit hash and your hash array is 2^22 elements, then store the other high end hash bits in the hash table (often the high 32 bits of the hash is stored). Check this value against the high 32 bits of the current position when you retrieve the hash.

Follow these two simple steps and you will solve your hashing problem. It is as easy as that.

[geko]

thanks User923005, but the hash table looks correct because I use it in the perft function and the results are correct; also because I create the zobristKey NOT incrementally

[User923005]

If the hash table is correct, then using it will improve your search. If it fails to improve the search, then the contents are bad.
If you are not forming the hash table incrementally, that is a mistake anyway that needs to be corrected. It's probably 50 times faster than generating it bit by bit.
It's easy to add the checksum check, won't take 5 minutes. Why not try that at least.

There are of course, other possibilities (e.g. a memcpy() call is overwriting the hash table).

[syzygy]

There seem to be some problems with your code:
- try removing your adjustment of alpha and beta in case you have no immediate hash cutoff, at least for now. I think it is possible to do this somewhat correctly for unclear gains if any (I have done it myself), but you need further checks later in your code. (Suppose the hash table indicates an upper bound lower than your beta, but later you get score > (adjusted) beta: you have a search inconsistency, not a real fail high.)
- although this might be hidden behind getMoves(), there is no indication that you search the move retrieved from the hash first.
- if val > alpha, then update alpha to val. In your code: update alpha to score in the if (score > alpha).
- do not overwrite an existing hash move if you fail low. The move you found is not better than the move already present and probably shouldn't be stored even if no hash move was present.
- as already mentioned, update your zobrist key incrementally as part of makemove()
- I wonder what updatePv() is doing.

Using a memcpy for copying a move seems to indicate that your move datatype is far bigger than the usual 2 or 4 bytes. If that is the case, are you storing all of it in the hashtable?

[geko]

I modified code with advice but no no luck
in RecordHash function now replace value only if slot is free or if hash.depth < depth, is that correct?

There are cases where not to use transposition table?

on 500 match, the strength of engine with transposition table is about equal to version without transposition table

new code is this:

int search(int side, int depth, int alpha, int beta, u64 zobristKey) {
char hashf = hashfALPHA;
int score = -_INFINITE;
Thash * phashe = &hash_array[zobristKey % HASH_SIZE];
if (phashe->zobristKey == zobristKey && phashe->depth >= depth) {
if (phashe->flags == hashfEXACT) {
updatePv(phashe->best);
return phashe->score;
}
else
if (phashe->flags == hashfBETA) {
if (phashe->score >= beta){
updatePv(phashe->best);
return phashe->score;
}
//alpha = max(alpha, phashe->score);
}
else if (phashe->flags == hashfALPHA) {
if (phashe->score < alpha){
updatePv(phashe->best);
return phashe->score;
}
//beta = min(beta, phashe->score);
}
}

if (depth == 0)
return quiescence();
int n_moves=generateMoves();
Tmove best;
for (ii = 0; ii < n_moves; ii++) {
move = getMoves(ii);
if (ii == 0)
memcpy(&best, move, sizeof(Tmove));
makemove (move);
val = -search(side ^ 1, depth - 1, -beta, -alpha, makeZobristKey());
if (val > score){
memcpy(&best, move, sizeof(Tmove));
score = val;
}
takeback(move);
if (score >= beta) {
storeHash(depth, hashfBETA, zobristKey, score, move);
return score;
}
if (score > alpha) {
alpha = score;
hashf = hashfEXACT;
memcpy(&best, move, sizeof(Tmove));
updatePv(move);
}
}
storeHash(depth, hashf, zobristKey, score, &best);
return score;
}

[User923005]

Free slot or greater depth is one replacement scheme that should be plenty good enough to start. Some hash tables are very sophisticated about this sort of thing, even having subtables and lists for multiple entries.

Just having the transposition table move should improve your move ordering immensely.
Your program should be quite a bit faster in searching because you should have 1/4 to 1/3 less searches, give or take.
If there is no difference in strength, there is something wrong.

If your entire source code base is available, it would be much easier to offer assistance, because right now we cannot see your data structures and other necessary items.

[syzygy]

There are cases where not to use transposition table?

No.

on 500 match, the strength of engine with transposition table is about equal to version without transposition table

It should be considerably stronger.

new code is this:

Are you trying the hash move first? This is not visible from your code. Is generateMoves() or getMove() doing another probe of the hashtable?

I'm still not sure what updatePV is doing. You are calling it in cases where you are not in a PV node.

[geko]

hi, my project is available at http://code.google.com/p/butterfly-chess-engine/

I attach at this post the source modified for TT

the function search is in Search.cpp

to build use:
make butterfly-nohash
or
make butterfly-hash

in windows you can use the compiler at http://tdm-gcc.tdragon.net

[geko]

some statistics:

fen startpos

-without transposition table:

info string ply: 8 ...
info score cp 61 depth 8 nodes 38901210 time 109935 pv d2d4 d7d5 e2e3 g8f6 b1c3 b8c6 f1b5 d8d6
info string tot moves: 38.901.210


-with transposition table:

info string ply: 8 ...
info score cp 61 depth 8 nodes 19828751 time 59251 pv d2d4 d7d5 e2e3 g8f6 b1c3 b8c6 f1b5 d8d6
info string tot moves: 19.828.751
info string hash_record: 945.371
info string n_cut_hash: 330.107
info string hash_collisions: 636.288

what about numbers?
the n_cut_hash is poor?
the hash_collisions is high?