implementation module StdGameTree import StdRoseTree import StdEnv // bereken game tree met moves functie en begin toestand: gametree :: (Moves s) s -> RoseTree s gametree moves s = iteratetree moves s // bereken minimax-waarde van de root van de game tree: minimaxvalue :: (RoseTree w) -> w | Ord,~ w minimaxvalue (Node w []) = w minimaxvalue (Node _ ts) = w where ws = map minimaxvalue ts w = ~(minList ws) // bereken minimax-waarde m.b.v. alpha-beta pruning: ab_minimaxvalue :: (w,w) (RoseTree w) -> w | Ord,~,Eq w ab_minimaxvalue (a,b) (Node w [ ]) = max a (min w b) ab_minimaxvalue (a,b) (Node _ ts) = bound (a,b) ts where bound :: (w,w) [RoseTree w] -> w | Ord,~,Eq w bound (a,b) [] = a bound (a,b) [t : ts] = if (a` == b) a` (bound (a`,b) ts) where a` = ~ (ab_minimaxvalue (~b,~a) t) // bereken minimax-waarden van alle nodes van de game tree: minimaxtree :: (RoseTree w) -> RoseTree w | Ord,~ w minimaxtree (Node w []) = Node w [] minimaxtree (Node _ ts) = Node w ts` where ts` = map minimaxtree ts w = ~(minList (map root ts`)) // bereken look-ahead van n ronden, en bereken alle minimax-waarden van de nodes: minimax :: PruneDepth (Worth s w) (Moves s) -> s -> RoseTree w | Ord, ~ w minimax n w moves = minimaxtree o (maptree w) o (prunetree (2*n)) o (gametree moves) // selecteer optimale volgende zet, met look-ahead n ronden, gebruik makend van minimax waarden // van alle nodes van de game tree: nextmoves :: PruneDepth (Worth s w) (Moves s) s -> [s] | Ord,~,Eq w nextmoves n w moves s = [ s` \\ s` <- moves s & w` <- children mtree | ~(root w`) == root mtree ] where mtree = minimax n w moves s // sorting sub trees for better states first: high (Node w ts) = Node w (sortBy higher (map low ts)) low (Node w ts) = Node w (sortBy lower (map high ts)) higher t1 t2 = root t1 > root t2 lower t1 t2 = root t1 <= root t2