diff options
Diffstat (limited to 'files/practicum/StdGameTree_en_StdRoseTree')
4 files changed, 125 insertions, 0 deletions
diff --git a/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl b/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl new file mode 100644 index 0000000..85948a2 --- /dev/null +++ b/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl @@ -0,0 +1,13 @@ +definition module StdGameTree
+
+import StdRoseTree
+
+:: Moves s :== s -> [s]
+:: Worth s w :== s -> w
+
+gametree :: (Moves s) s -> RoseTree s
+minimaxvalue :: (RoseTree w) -> w | Ord,~ w
+ab_minimaxvalue :: (w,w) (RoseTree w) -> w | Ord,~,Eq w
+minimaxtree :: (RoseTree w) -> RoseTree w | Ord,~ w
+
+nextmoves :: PruneDepth (Worth s w) (Moves s) s -> [s] | Ord,~,Eq w
diff --git a/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl b/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl new file mode 100644 index 0000000..57e7ef6 --- /dev/null +++ b/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl @@ -0,0 +1,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
diff --git a/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl b/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl new file mode 100644 index 0000000..5d6609d --- /dev/null +++ b/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl @@ -0,0 +1,20 @@ +definition module StdRoseTree
+
+import StdClass
+
+/** This module defines rose trees.
+*/
+:: RoseTree a = Node a [RoseTree a]
+:: Children a :== a -> [a]
+:: PruneDepth :== Int
+
+iteratetree :: !(Children a) a -> RoseTree a
+
+root :: !(RoseTree a) -> a
+children :: !(RoseTree a) -> [RoseTree a]
+depth :: !(RoseTree a) -> Int
+
+maptree :: (a -> b) !(RoseTree a) -> RoseTree b
+prunetree :: !PruneDepth !(RoseTree a) -> RoseTree a
+bonsai :: !(RoseTree a) -> RoseTree a | Eq a
+paths :: !(RoseTree a) -> [[a]]
diff --git a/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl b/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl new file mode 100644 index 0000000..ddefbca --- /dev/null +++ b/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl @@ -0,0 +1,38 @@ +implementation module StdRoseTree
+
+/** This module defines rose trees.
+*/
+import StdEnv
+
+root :: !(RoseTree a) -> a
+root (Node r _) = r
+
+children :: !(RoseTree a) -> [RoseTree a]
+children (Node _ ts) = ts
+
+depth :: !(RoseTree a) -> Int
+depth (Node _ []) = 1
+depth (Node _ xs) = 1 + maxList (map depth xs)
+
+prunetree :: !PruneDepth !(RoseTree a) -> RoseTree a
+prunetree d (Node x ts)
+| d <= 1 = Node x []
+| otherwise = Node x (map (prunetree (d-1)) ts)
+
+bonsai :: !(RoseTree a) -> RoseTree a | Eq a
+bonsai t = bonsai` [] t
+where
+ bonsai` :: ![a] !(RoseTree a) -> RoseTree a | Eq a
+ bonsai` path (Node v ts) = Node v (filter (\t -> not (isMember (root t) [v:path]))
+ (map (bonsai` [v:path]) ts)
+ )
+
+iteratetree :: !(Children a) a -> RoseTree a
+iteratetree f s = Node s (map (iteratetree f) (f s))
+
+maptree :: (a -> b) !(RoseTree a) -> RoseTree b
+maptree f (Node x ts) = Node (f x) (map (maptree f) ts)
+
+paths :: !(RoseTree a) -> [[a]]
+paths (Node x []) = [[x]]
+paths (Node x ts) = [[x:path] \\ t <- ts, path <- paths t]
|