Author: Stuart Cracraft
Date: 21:11:01 09/18/04
Go up one level in this thread
On September 18, 2004 at 17:18:44, Robert Hyatt wrote: >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. Thanks -- appreciate it -- had that code a long time (since stealing it from a Tony Marsland article.) > > >> 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.