files/practicum/StdGameTree.icl

   1 implementation module StdGameTree
   2
   3 import StdRoseTree
   4 import StdEnv
   5
   6 //      bereken game tree met moves functie en begin toestand:
   7 gametree                                                        :: (Moves s) s -> RoseTree s
   8 gametree moves s                                        = iteratetree moves s
   9
  10 //      bereken minimax-waarde van de root van de game tree:
  11 minimaxvalue                                            :: (RoseTree w) -> w | Ord,~ w
  12 minimaxvalue (Node w [])                        = w
  13 minimaxvalue (Node _ ts)                        = w
  14 where   ws                                                      = map minimaxvalue ts
  15                 w                                                       = ~(minList ws)
  16
  17 //      bereken minimax-waarde m.b.v. alpha-beta pruning:
  18 ab_minimaxvalue                                         :: (w,w) (RoseTree w) -> w | Ord,~,Eq w
  19 ab_minimaxvalue (a,b) (Node w [ ])      = max a (min w b)
  20 ab_minimaxvalue (a,b) (Node _ ts)       = bound (a,b) ts
  21 where
  22         bound                                                   :: (w,w) [RoseTree w] -> w | Ord,~,Eq w
  23         bound (a,b) []                                  = a
  24         bound (a,b) [t : ts]                    = if (a` == b) a` (bound (a`,b) ts)
  25         where a`                                                = ~ (ab_minimaxvalue (~b,~a) t)
  26
  27 //      bereken minimax-waarden van alle nodes van de game tree:
  28 minimaxtree                                                     :: (RoseTree w) -> RoseTree w | Ord,~ w
  29 minimaxtree (Node w [])                         = Node w []
  30 minimaxtree (Node _ ts)                         = Node w ts`
  31 where   ts`                                                     = map minimaxtree ts
  32                 w                                                       = ~(minList (map root ts`))
  33
  34 //      bereken look-ahead van n ronden, en bereken alle minimax-waarden van de nodes:
  35 minimax                                                         :: PruneDepth (Worth s w) (Moves s) -> s -> RoseTree w | Ord, ~ w
  36 minimax n w moves                                       = minimaxtree
  37                                                                         o (maptree w)
  38                                                                         o (prunetree (2*n))
  39                                                                         o (gametree moves)
  40
  41 //      selecteer optimale volgende zet, met look-ahead n ronden, gebruik makend van minimax waarden
  42 //  van alle nodes van de game tree:
  43 nextmoves                                                       :: PruneDepth (Worth s w) (Moves s) s -> [s] | Ord,~,Eq w
  44 nextmoves n w moves s                           = [ s` \\ s` <- moves s
  45                                                                                 & w` <- children mtree
  46                                                                                 | ~(root w`) == root mtree
  47                                                                           ]
  48 where mtree                                                     = minimax n w moves s
  49
  50 //      sorting sub trees for better states first:
  51 high (Node w ts)                                        = Node w (sortBy higher (map low  ts))
  52 low  (Node w ts)                                        = Node w (sortBy lower  (map high ts))
  53 higher t1 t2                                            = root t1 >  root t2
  54 lower  t1 t2                                            = root t1 <= root t2