Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question about details of hashing (olithink)

Author: Michel Langeveld

Date: 21:16:55 01/22/04

Go up one level in this thread


On January 22, 2004 at 22:54:28, Robert Hyatt wrote:

>On January 22, 2004 at 14:31:24, Michel Langeveld wrote:
>
>>Olithink uses hashing as follow in its search.c.

I like this program. It's probably the most compact bitboard program with a lot
of accessoires (2 hashtables  depth preffered and always replace, Killers,
alphabeta, pawnhashtable, history heuristic)

>I'm not an olithink guru, but I will make a couple of guesses...
>
>
>>Questions in the code marked with //
>>
>>int search(int on_move, int ply, int depth, int alpha, int beta, int do_null)
>>{
>>	int n, i, j, w, c, hflag, nolegal;
>>	Move bestmove = 0, move = 0;
>>
>>	if ((++nodes & 0x1fff) == 0) {
>>		if (bioskey()) inputmove(pmove ? ONMOVE(pmove) : COL_N);
>>		if (!pmove && (nodes*10)/nps*250 > mytime) { sabort = 1; return alpha; }
>>	}
>>
>>	if (ply && depth && checkfordraw(1)) return 0;
>>	pvlength[ply] = ply;
>>
>>	c = attacked(kingpos[on_move], on_move);
>>	if (c) depth++;
>>	else if (nstack && IS_PROM(movestack[nstack-1])) depth++;
>>	if (depth < 0) depth = 0;
>>
>>        //*** Ply gets updated each move ... Why does it not look in the hash
>>        //*** If ply == 0?
>>
>
>I assume ply=0 is the first ply of search?  If so, there is no point in
>hashing there.  You need a best move and score, not a quick termination
>due to hashing...

Yes correct. ply=0 is the first ply of the search. And this rule is indeed to
make sure there is a PV incase the search can't complete the total iteration
after this.

>
>>	hflag = lookUpH(depth, &w, &move);
>>	if (ply && hflag) {
>>		if (hflag == 1) if (w >= beta) return beta;
>>		if (hflag == 2) { do_null = 0; if (w < alpha) return alpha; }
>>	}
>>
>>        //*** hflag == 0 means NULLMOVE
>>        //*** hflag == 1 means hashscore was >= beta
>>        //*** hflag == 2 means hashscore was <= alpha
>>        //*** hflag == 4 means EXACT bound
>>
>>        //*** why doesn't it use EXACT and NULLMOVES, is this non-optimal impl?
>>

>It is _possible_ that 0 means "avoid doing a null-move here?"  IE the usual
>hash trick to not do null-move when the hash hit has insufficient draft to
>use the position normally, but it has enough draft to prove that a null-move
>would not fail high.

Hflag=0 means that the lookup did not match with a hashmove. I thought it was a
nullmove but that is not correct since a nullmove is stored as a
"betabound"=value >= beta.

const u32 hashSize = 0x100000; // This is 16 MB
const u32 hashMask = 0x0FFFFE; // This must be hashSize - 2

int lookUpH(int depth, int *w, Move *move) {
	HashREC *h = hashREC + (hashBoard & hashMask);
	if (h->rec != hashBoard && (++h)->rec != hashBoard) return 0;
	*move = h->move;
	if (h->depth == depth) {
		*w = h->w;
		return h->flag;
	}
	return 0;
}

The program searches 10% faster If someone changes to code into:

if (ply && hflag) {
   if (hflag == 1) if (w >= beta) return beta;
   if (hflag == 2) { do_null = 0; if (w < alpha) return alpha; }
   if (hflag == 4) { return w; }
}

old:
10*   2893   4548668      1  b1c3 b8c6 i1h3 i8h6 c3d5 d7d6 d2d4 c8d7 c1g5 h6f5
10*   8803   8783064      0  i1h3 i8h6 h3f4 h6f5 d2d3 d7d6 c1d2 c8d7 g1f3 g8f6

new:
10*   2907   4602628      1  b1c3 b8c6 i1h3 i8h6 c3d5 d7d6 d2d4 c8d7 c1g5 h6f5
10*   7978   7742139      0  i1h3 i8h6 h3f4 h6f5 d2d3 d7d6 c1d2 c8d7 g1f3 g8f6

I think also age will improve hashing efficiency.

The lookupH function works also a bit faster if you use:

if (h->depth >= depth) {

Else a hashtable lookup with a 9 ply is not used in a search with 8 ply for
example.

>Otherwise I couldn't guess.  I don't differentiate between a position stored
>from a null-move search and a non-null-move search, other than hashing the
>signature to handle the change in side to move.
>
>
>
>>	if (!c && do_null && depth && ply && bitcount(R000BitB[on_move] &
>>(~R000BitB[PAWN[on_move]])) > 3) {
>>		donullmove();
>>		w = -search(on_move^1, ply+1, depth - 3 - (depth > 5), -beta, -beta + 1, 0);
>>		undonullmove();
>>		if (w >= beta) {
>>			storeH(0, depth, w, 1);
>>			return w;
>>		}
>>	}
>>
>>	if (!ply) move = pv[0][0];
>>	hashmv[ply] = move;
>>	hflag = move ? 1 : 0;
>>	nolegal = 1;
>>	n = 0;
>>
>>	if (depth == 0 && !c) {
>>		w = eval(on_move, alpha, beta);
>>		if (w > alpha) alpha = w;
>>		if (alpha >= beta) return beta;
>>
>>                //Funny QSearch implementation ... this generates
>>                //captures
>>		n = generate_moves(on_move, ply, 1);
>>		if (n == 0) return w;
>>		hflag = 0;
>>	}
>>
>>	i = 0;
>>	do {
>>		if (i == 1) hflag = 0;
>>		if (n == 0 && !hflag) {
>>			if (c) 	n = generate_check_esc(on_move, ply, 0);
>>			else n = generate_moves(on_move, ply, 0);
>>
>>			if (i == 1) {
>>					for (j = 0; j < n; j++) {
>>						if (IDENTMV(movelist[j][ply], hashmv[ply])) {
>>							movelist[j][ply] = movelist[n-1][ply];
>>							break;
>>						}
>>					}
>>				}
>>			if (n == 0) break;
>>			}
>>		if (!hflag) move = pick(ply, n-i);
>>		if (!depth && !c && P_TO(move) != EMPTY && swap(move) < -150) continue;
>>
>>		domove(move);
>>		if (!c && attacked(kingpos[on_move], on_move)) { undomove(); continue;}
>>		w = -search(on_move^1, ply+1, depth-1, -beta, -alpha, 1);
>>		if (nolegal) nolegal=0;
>>		undomove();
>>		if (sabort) break;
>>
>>		if (w >= beta)  {
>>			if (P_TO(move) == EMPTY)  {
>>			  killer2[ply] = killer[ply];
>>			  killer[ply] = move;
>>			}
>>			history[move & 0xFFFF] += depth;
>>			storeH(move, depth, w, 1);
>>			return beta;
>>
>>                        //*** Why store score w, and return beta
>>                        //*** Doesn't this work bugs in the hand?
>>		}
>
>
>That looks like non-failsoft.  You never return a value < alpha or > beta.
>
>
>
>
>>		if (w > alpha) {
>>			pv[ply][ply] = bestmove = move;
>>			for (j = ply+1; j < pvlength[ply+1]; j++) pv[ply][j] = pv[ply+1][j];
>>			pvlength[ply] = pvlength[ply+1];
>>			alpha = w;
>>			if (alpha == 32499 - ply) break;
>>		}
>>	} while (++i < n || hflag);
>>	if (sabort) return alpha;
>>
>>	if (nolegal) {
>>		if (c) return -32500 + ply;
>>		else if (depth) return 0;
>>	} else
>>	storeH(bestmove, depth, alpha, bestmove ? 4 : 2);
>>	return alpha;
>>}



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.