Scripts/AlphaBeta
< Scripts
Jump to navigation
Jump to search
Download old (pre J6.01) version of this script: File:Alphabeta.ijs [{{#file: "alphabeta.ijs"}} Download script: alphabeta.ijs ]
NB. definitions used here default =: [ , (}.~ #)~ NB. alpha-beta minimization NB. This is a base class for alpha-beta minimization. Classes NB. that extend this class are expected to provide the following NB. functions: NB. NB. suggestmoves NB. y is position,player;sortflag NB. if sortflag is 1, the moves should returned best move first NB. Result is (list of newposn;newplayer;move) ,&< (state info for next call) NB. The monadic case is the first call; after that the dyad is called, NB. with x set to the state info returned by the previous call NB. Each call returns as many moves as can be gathered quickly. NB. NB. evalposn NB. y is position,<player NB. Result is best guess at the value of the game from the point NB. of view of that player (_1 = dead loss, 1 = forced win) NB. NB. checkterminal NB. y is position,<player NB. Result is 0 if position is not terminal, or NB. 1;value is position is terminal NB. NB. and optionally: NB. NB. canonposnplayer NB. y is (boxed) posnplayer NB. result is (boxed) canonical posnplayer coclass 'alphabeta' NB. NOTE: in this file, 'posn' and 'move' are always boxed NB. posnplayer is posn,<player NB. Dummy canonposn in case none specified by user NB. y is posn,<player NB. result is canonical (posn,<player) ; (uncanoninst) ; (symmetries) NB. uncanoninst will be passed in to uncanonmove NB. symmetries will be passed in to suggestmoves canonposnplayer =: ]"1 NB. Dummy posnplayertochar in case none specified by user NB. Convert position to string, prefixed by player# posnplayertochar =: 3 : 0"1 posn =. 0{::y (": 1{:: y) , 5!:5 <'posn' ) NB. x is minimum allocation for table NB. y is mask of table entries to keep NB. We reinit the table, and reinstall the symbols and values that NB. were indicated to be kept purgexposition =: 4 : 0 NB. Save the symbol names we want to keep savesyms =. 5 s: y # xpositioninspt {. xpositionsyms NB. Reinit the symbol table 10 s: xpositionreinitval NB. Reallocate the tables xpositionsyms =: x ((>. #) {. ]) s: savesyms xpositiondata =: x ((>. #) {. ]) y # xpositioninspt {. xpositiondata xpositioninspt =: #savesyms NILRET ) NB. Called to allocate xposition table. y is size of initial allocation initxposition =: 3 : 0 if. ifdefined 'xpositionreinitval' do. 10 s: xpositionreinitval end. xpositionreinitval =: 0 s: 10 xpositionsyms =: y # s: <'' xpositiondata =: y # <'' xpositioninspt =: 0 NILRET ) NB. y is list of (boxed position),player#[;other stuff] NB. Convert the posnplayers to canonical form; then look them up NB. to see which ones have been encountered before. Return NB. (old positions),&<(new positions) NB. where each old position is (evaluation parms);posn;player;(other stuff) NB. and each new position is handle;posn;player;(other stuff) NB. NB. Keep the records in order, since the best one comes first checkxposition =: 3 : 0 NB. Convert positions to canonical form canonpos =. canonposnplayer@(2&{.)"1 y otherstuff =. 2 }."1 y NB. Get a symbol for the posnplayers sym =. s: charpp =. <@posnplayertochar canonpos NB. Discard duplicates - but if the character value is '', it means we are NB. not bothering with saving a symbol for this value, so don't let those values get NB. treated as equivalent nubmsk =. (~: sym) +. charpp = <'' sym =. nubmsk # sym nuby =. canonpos ,.&(nubmsk&#) otherstuff NB. Look up the symbols, see which are old oldsym =. xpositioninspt > m =. (xpositioninspt {. xpositionsyms) i. sym NB. Build the return (((oldsym # m) { xpositiondata) ,. oldsym # nuby) ,&< sym ;"_1&((-. oldsym)&#) nuby ) NB. x is (unboxed) record to save, y is handle returned by 'checkxposition' NB. No result; the table is modified addxposition =: 4 : 0 NB. Reallocate table if it is full if. xpositioninspt = #xpositionsyms do. xpositionsyms =: ({.~ >.@(1.25&*)@#) xpositionsyms xpositiondata =: (#xpositionsyms) {. xpositiondata end. NB. Install the item at the next point in the table xpositionsyms =: y xpositioninspt} xpositionsyms xpositiondata =: (<x) xpositioninspt} xpositiondata xpositioninspt =: >: xpositioninspt NILRET ) NB.*v-- findmove find one move of the game NB. x is anything NB. y is position;player#;max depth allowed NB. Result is new position;player;max depth;game value;move that was made findmove =: 4 : 0 movect =: 0 valmove =. x searchtree y,_2;2;1;1 NB. If there is no move, the starting position was terminal: return it if. 4 > #valmove do. y return. end. NB. The move is found. Purge the saved list of positions of NB. everything that wasn't terminal. We assume that the second NB. element in each data box is the exact-evaluation flag 512 purgexposition 1&{@> xpositioninspt {. xpositiondata qprintf 'movect ' (1 2{valmove),(2{y),(0 3{valmove) ) NB.*v-- searchtree alpha-beta algorithm to search game tree NB. run alpha-beta minimization NB. x is anything, passed along to the other functions NB. y is position;player#;max depth allowed;alpha;beta;posn type[;fullreturn] NB. player# is 0 or 1 NB. alpha is the negative of the best value that the moving player has been able to NB. guarantee so far by taking a branch of the tree that does not NB. lead to the parent of the move being considered NB. beta is the best value that the moving player has been able to NB. guarantee by choosing among alternative moves at the current level NB. (i. e. it is the negative of the best value his opponent is able to get) NB. posn type is 1 if all moves are first options (i. e. predicted best); NB. alternating between 2 and 3 (starting with 2) once a second choice NB. is tried. Type 3 positions do not need to worry about order of successors. NB. NB. result is (game value,terminal flag)[;posn;player;move] NB. the game value is a value between _1 and 1, always represented NB. from the point of view of the player making the move (_1 is a NB. dead loss, 1 a forced win). Terminal flag is 1 if we know this NB. is a correct answer NB. the move describes the move we selected. the move may not be part of the NB. returned value if fullreturn is not 1 (default 0) NB. NB. start by calling with alpha=_1,beta=1 searchtree =: 4 : 0 movect =: >: movect posnplayer =. 2 {. y 'depth alpha beta postype fullreturn' =. 2 3 4 5 6 { y default '';0;0;_1;1;1;0 NB. If the position is terminal, return the value with no move, and terminal flag set if. >{. r =. checkterminal posnplayer do. ,<>|.r return. end. NB. If depth is 0, we have to stop searching. Force an evaluation and return NB. whatever is available, with no move if. depth = 0 do. ,<(evalposn posnplayer),0 return. end. NB. initialize state that will be supplied to the next level newdepth =. <: depth NB. Successors of types 2 and 3 alternate; the first successor to type NB. 1 is type 1, the others are type 2 newpostype =. postype { 0 1 3 2 NB. Init to 'no best move found yet' bestmove =. 0$a: NB. Start off indicating exact evaluation exacteval =. 1 NB. Get a list of moves, initializing the move-finder. This returns NB. a few moves 'posmovelist nextstate' =. suggestmoves posnplayer,<(postype ~: 3) NB. Now process all the moves, until we have done them all or we have found NB. a refutation of the move that got us here while. #posmovelist do. NB. Convert all the positions to canonical form NB. Establish a handle for each position, and see if it has been evaluated already NB. Each posnplayer gets a flag meaning 'previously evaluated', and either a NB. symbol or the results of the evaluation 'oldposns newposns' =. checkxposition posmovelist NB. Looking at all the positions that have been evaluated, get the best result and NB. use it. oldposns is list of evaluation ; move if. #prevevals =. 0 ocol oldposns do. NB. if all the evaluations were exact, remember that exacteval =. exacteval *. *./ 1 {"1 prevevals if. (-moveval =. <./ mv =. 0 {"1 prevevals) > alpha do. bestmove =. (<(mv i.!.0 moveval);1 2 3) { oldposns alpha =. -moveval end. if. alpha >: beta do. break. end. NB. refutation! end. NB. Now consider the positions that have not already been evaluated. NB. newposns is handle;posn;player;move NB. For each yet-to-be-evaluated position, evaluate it, save the result, NB. and stop if we have hit a refutation for_p. newposns do. 'moveval exact' =. >{. x searchtree (1 2{p),newdepth;(-beta);(-alpha);newpostype NB. Remember the value for this position so we don't have to look at it again. NB. But if the symbol is the empty symbol, we don't bother saving (moveval,exact) addxposition^:(~:/@(2&{.)@]) 0 {:: p exacteval =. exacteval *. exact if. (-moveval) > alpha do. alpha =. -moveval bestmove =. 1 2 3 { p end. if. alpha >: beta do. break. end. NB. refutation! NB. After the first move, successors of type-1 positions become type 2 newpostype =. 2 >. newpostype end. if. alpha >: beta do. break. end. NB. Get more moves, if there are any 'posmovelist nextstate' =. nextstate suggestmoves posnplayer,<(postype ~: 3) end. NB. If a full return was called for, return the selected move bestmove ,~^:fullreturn ,<alpha,exacteval *. alpha < beta )
Contributed by Henry Rich
CategoryGames CategoryLiterate [[Category:Scripts R.7]