From a7d7542dc646a5fd124ef71e71ce260889f1701b Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Tue, 2 Feb 2016 19:24:50 +0100 Subject: Moved to 1415 directory --- .../StdGameTree_en_StdRoseTree/StdGameTree.dcl | 13 ++++++ .../StdGameTree_en_StdRoseTree/StdGameTree.icl | 54 ++++++++++++++++++++++ .../StdGameTree_en_StdRoseTree/StdRoseTree.dcl | 20 ++++++++ .../StdGameTree_en_StdRoseTree/StdRoseTree.icl | 38 +++++++++++++++ 4 files changed, 125 insertions(+) create mode 100644 1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl create mode 100644 1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl create mode 100644 1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl create mode 100644 1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl (limited to '1415/files/practicum/StdGameTree_en_StdRoseTree') diff --git a/1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl b/1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.dcl new file mode 100644 index 0000000..85948a2 --- /dev/null +++ b/1415/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/1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl b/1415/files/practicum/StdGameTree_en_StdRoseTree/StdGameTree.icl new file mode 100644 index 0000000..57e7ef6 --- /dev/null +++ b/1415/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/1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl b/1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.dcl new file mode 100644 index 0000000..5d6609d --- /dev/null +++ b/1415/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/1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl b/1415/files/practicum/StdGameTree_en_StdRoseTree/StdRoseTree.icl new file mode 100644 index 0000000..ddefbca --- /dev/null +++ b/1415/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] -- cgit v1.2.3