Author: Michel Langeveld
Date: 07:47:22 01/14/04
Go up one level in this thread
On January 13, 2004 at 11:36:55, Robert Hyatt wrote:
>On January 13, 2004 at 10:28:54, Michel Langeveld wrote:
>
>>The idea of Nullmove is that you let a player have the right to do two moves
>>during a game. If he can't win with this right then his position is really bad,
>>and we count it as lost.
>>--------------------------------------------------------------------------------
>>original
>>6 318 343459 -8 b1c3 b8c6 i1h3 d7d6 h3f4 c8f5
>>7 1782 2188112 3 b1c3 d7d5 d2d4 c8f5 i1h3 i8h6 c1f4
>>
>>nullmove with: if (!c && !nullmoved && depth - 1 - R > 0)
>>6 215 227824 -8 b1c3 b8c6 i1h3 d7d6 h3f4 c8f5
>>7 859 1008458 3 i1h3 d7d5 d2d4 c8f5 b1c3 i8h6 c1f4
>>
>>nullmove with :if (!c && !nullmoved)
>>6 59 63778 -3 i1h3 d7d6 g1f3 i8h6 b1c3 b8c6
>>7 342 403509 3 i1h3 d7d5 d2d4 c8f5 c1f4 i8h6 b1c3
>>
>>My question is do I have to protect that after a nullmove we go immediatly into
>>quiesce or can I live without this protection?
>
>That is what I do. If depth-R-1 is <= 0, drop directly into Quiesce(),
>else call Search().
Thanks everybody of this thread for the answers!
I saw that it is difficult to add items to TSCP without introducing bugs.
Did somebody ever do it right?
Since TSCP don't have hashing it uses the PV to order moves. This is important.
In my code the variable follow_pv is not backuped and will be changed by
nullmove.
It is adviced to add, the following:
{
...
BOOL c, f, oldFollowPV;
...
...
//we are not check and did not do a nullmove before
if (!c && !nullmoved)
{
//backup the old follow_pv, this is important
oldFollowPV = follow_pv;
//set the end marker
makenullmove();
x = -search(-beta, -beta + 1, depth - 1 - R, FALSE);
takebacknullmove();
if (x >= beta)
return beta;
//restore that fact that we are not check
c = FALSE;
follow_pv = oldFollowPV;
}
..
}
Then the gain is even bigger
starting position from gothic chess, 533% faster
7 1248 2188112 3 b1c3 d7d5 d2d4 c8f5 i1h3 i8h6 c1f4 (without nm)
7 234 393694 3 b1c3 d7d5 d2d4 c8f5 c1f4 i8h6 i1h3 (with nm)
And in tactical positions nullmove can save even more:
1249% faster... halleeloojaa!
7 2061 3904574 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 (without nm)
7 165 328189 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 (with nm)
>
>>--------------------------------------------------------------------------------
>>
>>/* search() does just that, in negamax fashion */
>>int search(int alpha, int beta, int depth)
>>{
>> int i, j, x;
>> int his_piece;
>> BOOL c, f;
>>
>> int best_score;
>>
>> /* we're as deep as we want to be; call quiesce() to get
>> a reasonable score and return it. */
>> if (depth <= 0)
>> return quiesce(alpha,beta);
>> ++nodes;
>>
>> /* do some housekeeping every 1024 nodes */
>> if ((nodes & 1023) == 0)
>> checkup();
>>
>> pv_length[ply] = ply;
>>
>> /* if this isn't the root of the search tree (where we have
>> to pick a move and can't simply return 0) then check to
>> see if the position is a repeat. if so, we can assume that
>> this line is a draw and return 0. */
>> if (ply && reps())
>> return 0;
>>
>> /* are we too deep? */
>> if (ply >= MAX_PLY - 1)
>> return eval();
>> if (hply >= HIST_STACK - 1)
>> return eval();
>>
>> /* are we in check? */
>> c = in_check(side);
>>
>> //we are not check and did not do a nullmove before
>>
>> //Question : what if clausule can we use here?
>> if (!c && !nullmoved)
>> {
>> //set the end marker
>> first_move[ply + 1] = first_move[ply];
>> makenullmove();
>> x = -search(-beta, -beta + 1, depth - 1 - R);
>> takebacknullmove();
>>
>> if (x >= beta)
>> return beta;
>>
>> //restore that fact that we are not check
>> c = FALSE;
>> }
>>
>> /* if we are in check don't seach deeper */
>> if (c) depth++;
>>
>> gen();
>> if (follow_pv) /* are we following the PV? */
>> sort_pv();
>> f = FALSE;
>>
>> best_score = -10000;
>>
>> /* loop through the moves */
>> for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
>> sort(i);
>> if (!makemove(gen_dat[i].m))
>> continue;
>> f = TRUE;
>>
>> if (best_score == -10000)
>> x = -search(-beta, -alpha, depth - 1);
>> else
>> {
>> x = -search(-(alpha + 1), -alpha, depth - 1);
>> if (x > alpha && x < beta)
>> {
>> x = -search(-beta, -alpha, depth - 1);
>> }
>> }
>>
>> takeback();
>>
>> if (x > best_score) {
>>
>> best_score = x;
>>
>> if (x > alpha) {
>>
>> /* this move caused a cutoff, so increase the history
>> value so it gets ordered high next time we can
>> search it */
>> if (x >= beta) {
>> addkiller(gen_dat[i].m);
>> his_piece = piece[gen_dat[i].m.b.from];
>> history[side][his_piece][gen_dat[i].m.b.to] += depth;
>> return beta;
>> }
>> alpha = x;
>>
>> /* update the PV */
>> pv[ply][ply] = gen_dat[i].m;
>> for (j = ply + 1; j < pv_length[ply + 1]; ++j)
>> pv[ply][j] = pv[ply + 1][j];
>> pv_length[ply] = pv_length[ply + 1];
>> }
>> }
>> }
>>
>> /* no legal moves? then we're in checkmate or stalemate */
>> if (!f) {
>> if (c)
>> return -10000 + ply;
>> else
>> return 0;
>> }
>>
>> /* fifty move draw rule */
>> if (fifty >= 100)
>> return 0;
>>
>> return best_score;
>>}
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.