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.