Author: Vincent Diepeveen
Date: 07:09:10 08/06/00
Go up one level in this thread
Implementing fail soft PVS with negamax and double nullmove is a matter of a few minutes, implementation with all details shouldn't take much longer as a few hours, toying with it about a year or 5 before you decide you do it a certain way and that's it. Note that the initial alfa and beta in most programs is not -infinite,infinite. In DIEP it is, but that has everyone to figure out himself whether it saves nodes. It sure does in my draughtsprogram. Millions of nodes. Evaluation and move ordering not that well in draughts prog. You can take real big risks, for example you can search with a certain nullwindow value, if that fails low you research with -infinite,infinite. If it fails high, then skip to next ply. Tricks like that. Many tricks to try. I only got PVS to work great. Usually you skip plies only quick if you already search very deep. I prefer searching efficient in positions where scores go down. /* depth: depth left like if iteration = 9 ply then 9,8,7...0 or less if reduction depth. realply: starting with 0,1,....n for storage in tables */ int pvs(depth,realply,side,alfa,beta) { int cutoff,score,paralfa,parbeta,best,.. ; if( cutoff=GetHash(...) ) return(cutoff); /* score==0 should be repetition score, you can't return that from hashtable */ if( depth <= 0 ) return(qsearch(-beta,-alfa,side); /* double nullmove */ if( !incheck && (realply <= 1 // first 2 ply you always can nullmove, || movelist[realply-1] || movelist[realply-2] ) { /* so we do NOT nullmove if the previous 2 moves were nullmoves or if we are in check */ R = 2; /* in DIEP i'm using R=3, but i do checks in qsearch */ movelist[realply] = 0; /* 0 means we do nullmove this real move */ score = -pvs(depth-1-R,realply+1,side^1,-beta,-beta+1); /* we nullmove with a nullwindow of [beta-1,beta], as we are only interested in getting a cutoff */ if( score >= beta ) { StoreHash(..); return(score); } } /* now search the moves */ paralfa = alfa; parbeta = beta; best = -infinite; for( all moves ) { DoMove(side,move); /* don't integrate that datastructure into your search actually i don't even do that for nullmove. I do a DoMove(nullmove) there */ score = -pvs(depth-1,realply+1,side^1,-parbeta,-paralfa); if( score > best ) { if( score >= beta ) { StoreHash(..); return(score); } best = score; if( score > alfa ) paralfa = score; parbeta = paralfa + 1; /* set window after first move to alfa,alfa+1 */ } } StoreHash(..); return(best); } On August 05, 2000 at 12:29:21, Tim Foden wrote: >On August 05, 2000 at 11:37:01, Larry Griffiths wrote: > >>Which Algorithm is considered the best now-adays. >> >>NegaScout? MTD? PVS? Others? I am looking to implement one of the best search >>type algorithms in my program. I would like to get it into the 2000 rated range >>as this has been my lifetime goal. Then, maybe install winboard or something so >>it can compete against other programs to get a rating. >>I dont like MTD as it seems to be complex. > >It is generally possible, and I would say advisable, to implement the search in >small steps. Get one version working before moving on to the more complex >version. > >Thus the searches you mention above, plus plain A-B search, can be ranked in >order of implementaion: >1) Alpha-Beta >2) PV-search >3) NegaScout >4) MTD(f) > >To get from 1) to 2), you need to implement null-window search for non-PV lines. > >To get from 2) to 3), you implement the safe forward pruning near the leaves, or >use razoring if you have extensions. > >You might want to switch 2) and 3) around. > >To get from the 3) to 4) you add the MTD(f) driver on top of the whole thing. > >The thing to remember about MTD(f) (if my memory serves me well) is that I think >it requires a fail-soft version of the underlying search. Fail soft is: when >you detect a cut-off (value >= beta) you return (value). Fail hard is you >return (beta). > >At some point it would be advisable to implement the Null move heuristic. > >All of this is from some hazy memory, so please forgive me if I turn out to be >talking nonsense. :o) > >BTW, I don't necessarily think you need the "best" search algorithm. Just a >good one. I really don't think MTD(f) is a requirement to get a program that is >2000 (or even 2500) rated.
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.