Author: Robert Hyatt
Date: 19:54:28 01/22/04
Go up one level in this thread
On January 22, 2004 at 14:31:24, Michel Langeveld wrote:
>Olithink uses hashing as follow in its search.c.
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...
> 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.
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.