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.