1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
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
|
