Author: Dieter Buerssner
Date: 13:08:50 07/15/04
Go up one level in this thread
On July 14, 2004 at 13:24:53, Stuart Cracraft wrote:
>Please see if you see anything obvious with my basic search.
>Any comment you make is welcome.
Some suggestions inside the code.
>search(depth,alpha,beta)
> if draw-rules-met return draw
> if extensions-met depth+=1
This might indicate a small bug (that many engines have). I guess, in
"extension-met" you look if king is in check. And in draw-rules-met you look for
50 move rule draw. To decide for 50-moves-rule draw, in general, you have to
know, if you are in check (might be mate) or not.
> if depth <= 0 return quiesce()
> try to retrieve hash position of current position
> if length retrieved >= depth then
> if flag is VALID, return score from hash table for position
> if flag is LOWERBOUND, set alpha to MAX(score-from-table,alpha)
> if flag is UPPERBOUND, set beta to MIN(score-from-table,beta)
I'd try for the first debugging phase, to take out the adjustment of bounds. It
can make things more complicated.
if flag is LOWERBOUND and score >= beta return score
if flag is UPPERBOUND and score <= alpha return score
Your pseudo code does not show it, but perhaps you collect a PV. Say hash score
score is LOWERBOUND, and between alpha and beta. The score might be exactly
score (so actually VALID). Now your search may not find a good move to store in
hash and a PV anymore, because you set alpha to score, and the score is outside
of this window. When you store later down, you will actually store the pos as
UPPERBOUND now. Sometimes it will happen, that with a different search window
and the same depth ("draft") you will get different results. I think, one has to
live with this, more or less. When adjusting the bounds like above, probability
for this might become higher (my guess). So for debugging phase, it might be
better to not aggressively adjust bounds in the first phase.
> if alpha>=beta return score
> set flag meaning hashed
As Paul mentioned ...
> endif
> if null-move-ok, do it (not endgame, not incheck, not 2 in a row already)
> if hashed flag above is set, add a value to make hashed move be searched 1st
> generate moves
> if hashed flag was set add value to make hashed move 1st
> make & search 1st move with best = search(depth-1,-beta,-alpha)
> unmake
> while (best < beta)
> if best > alpha
> alpha = best
> set best move to current move if top of tree
> :
> endif
> if search timed out, return(best)
> if end of move list, break from while-loop
> make next move
> value = -search(depth-1,-alpha-1,-alpha)
> if (value > alpha && value < beta)
> best = -search(depth-1,-beta,-value)
Similar argument as above. Perhaps during debugging phase adjust the window less
aggressively, and do
best = -search(depth-1,-beta,-alpha)
> else if (value > best)
> best = value
> set best move to current move if top of tree
> unmake
> end
> if no legal moves found
> if incheck
> best = -MATE+depth
> else
> best = STALEMATE
> endif
> flag = VALID
> if (best <= alpha) flag = UBOUND
> if (best >= beta) flag = LBOUND
> if (length <= depth and there is a best move to store)
> store(depth, best, flag, move)
Hmmm. Looks buggy and suboptimal. best is just a "random value" from the last
searched move in case of fail low. It might be alpha-100, while an earlier move
got alpha. This will give you a wrong bound. Or you want to do fail soft and
initialize best to -INFSCORE at the top of the search, and do the searches and
the logic inside all with value instead of depth, and update both, best and
alpha.
Why the if in frong of the store?
> endif
> return(best)
And here possibly returns the wrong upper bound.
Regards,
Dieter
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.