Author: Stuart Cracraft
Date: 10:19:12 09/18/04
Go up one level in this thread
On September 18, 2004 at 11:09:26, Robert Hyatt wrote:
>On September 18, 2004 at 04:05:38, Sune Fischer wrote:
>
>>
>>I decided to try out the triangular PV thing Bob
>>speaks so highly of, to see if it improves move ordering...
>>
>>I was careful to terminate the PV on all exact scores - of course.
>>Still I was getting illegal moves in the PV.
>>
>>It turned out to be a hash/nullmove problem.
>>
>>See, in the hash I adjust the window down on UPPER bounds, ie.
>>something like:
>> if (flag==UPPER && score<beta)
>> beta = score;
>
>Are you doing PVS? If so you won't do this a dozen times during a long search,
>most likely. But I do this in Crafty as well, and it doesn't _ever_ get illegal
>moves in the PV.
>
>
>>
>>The idea is that if we know the score is in the interval [x,y]
>>then there is no reason to search with a window of [x,y+z].
>>It's a common trick I believe.
>>
>>Unfortunately, the search will occasionally fail high on the new beta, in my
>>case it was a nullmove that failed-high.
>>
>>That's clearly contradictive with what the hash just told us so
>>it doesn't actually make any sense, but apparently it happens anyway
>>(instability?).
>>
>>Now the score at the previous node might be an exact value (or a fail high later
>>on), and the PV will now be concatenated from an old search branch.
>>
>
>That can't happen. You don't update the PV on a fail high, ever. Only if score
>is > alpha and < beta...
>
>
>
>
>
>>
>>I can't see that I am doing anything wrong.
>>Perhaps adjusting beta is just not a good idea?
>>
>>-S.
Anyone see anything obviously wrong with hashing, null move,
triangular array handling, or best move updating in the following
pseudo-code?
search(depth,ply,alpha,beta)
save original entry depth in sdepth
:
extensions checked here modify depth variable
if modified depth <= 0 return quiescence(alpha,beta)
hashed=0
if (retrieve(&length, &score, &flag, &hashmv))
if (length >= sdepth)
if (flag == VALID) return(score);
if (flag == LBOUND) alpha = MAX(alpha, score);
if (flag == UBOUND) beta = MIN(beta, score);
if (alpha >= beta) return(score);
if (legalmove2(bd,hashmv)) hashed=1
fi
fi
best = alpha
nulled=0
if (okay to do null move && not in check && not inside pv)
nulled=1
make null move
#define R 2
value = -search(sdepth-R-1,ply+1,-beta,-beta+1)
unmake null move
if value >= beta return(value)
fi
if hash move legal or if no hash move, generate moves, sort, process 1st mv
incremental legal move counter
search move (may be hash)
best = -search(modified depth,ply+1,-beta,-alpha)
fi
while (best < beta)
if (best > alpha)
backup the pv in the triangular array
if ply == 0 save move as best as long as no time control timeout
update history heuristic for this move to be += (1<<modified depth)
fi
if (timeout()) return(best) and set flag so that best move won't be changed
make next move
if side on move not in check
increment legal move counter
value = -search(modified depth-1,-alpha-1,-alpha)
if (value > alpha && value < beta)
value = -search(modified depth-1,-beta,-value
else if (value > best)
best = value
if top ply save move as best as long as no time control timeout
backup the pv in the triangular array
fi
unmakemove
fi
if legal move counter is 0
if in check
best = -MATE + ply
else
best = STALEMATE
fi
fi
done:
flag = VALID
if best <= alpha flag = UBOUND
if best >= beta flag = LBOUND
if length <= depth
store(depth,best,flag,best move)
return best
Stuart
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.