Author: Robert Hyatt
Date: 14:18:44 09/18/04
Go up one level in this thread
On September 18, 2004 at 13:19:12, Stuart Cracraft wrote: >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); Where are you backing up the PV here? You are returning an exact score, but apparently no PV. > 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.