Skip to content
Newer
Older
100644 101 lines (70 sloc) 2.63 KB
1e9a1d0 @furroy messing around with building libraries of funcs
furroy authored
1 ###################
2 # trees !
3 ###################
4
5 empty-tree = nil
6
7 make-tree t = cons (cons t nil) nil
8
9 add-child t c = if (null? t)
10 c
11 cons (append (head t) c) nil
12
13 first-child t = tail (head t)
14
15 next-sibling t = tail t
16
17 data t = head (head t)
18
19 traverse-prefix t f = if (null? t) (f nil)
20 do
21 f (data t)
22 traverse (first-child t) f
23 traverse (next-sibling t) f
24
25 traverse = traverse-prefix
26
27 #depth-search t f = if (null? t) nil
28 # do
29 # c = first-child t
30 # if (null? c) (f (data t)) nil
31 # depth-search c f
32 # depth-search (next-sibling c) f
33 #traverse-tree t s a = s t a
34 #print-tree-depth t = traverse-tree t depth-search print
35 #print-tree-breadth t = traverse-tree t breadth-search print
36
37
38 # private-inner function for finding the children
39 inner-children c = if (eq c nil) nil
40 cons (head c) (inner-children (next-sibling c))
41
42 # children - make a list of the children we can map over
43 children t = if (eq t nil) nil
44 inner-children (first-child t)
45
46 ###########################
47 # silly testing funcs
48 ###########################
49
50
51 # 1
52 # 2 3 4 5
53 #6 7 8 9 10 11
54 # 12
55 # trees are stored as a list with root node value, then first-child, then siblings, all recursively
56
57 test-tree = [[1, [2, [6], [7], [8] ], [3], [4, [9, [12] ]], [5, [10], [11] ]]]
58 test-small-tree = [[1, [2, [6], [7], [8] ] ]]
59 tiny-tree = [[1, [2]]]
60
61 t1 = make-tree 1
62 t2 = make-tree 2
63 t6 = make-tree 6
64 t7 = make-tree 7
65 t8 = make-tree 8
66
67 test-build2 = (add-child (add-child (add-child t2 t6) t7) t8)
68
69 test-build = (add-child t1 (test-build2))
70
71
72 tmt4 = add-child (make-tree 4) (add-child (add-child (make-tree 4) (make-tree 12)) (make-tree 7))
73 tmt5 = add-child (make-tree 5) (add-child (add-child (make-tree 10) (make-tree 5)) (make-tree 6))
74 tmt1 = add-child (make-tree 1) (add-child (add-child (make-tree 1) (make-tree 2)) (make-tree 3))
75 test-minimax-tree = add-child (add-child (add-child (make-tree 5) tmt4) tmt5) tmt1
76
77
78 ######################################################
79 # messing around with basic minimax alpha/beta pruning
80 ######################################################
81
82 alpha-beta t = alpha-beta-tree t 4 -999999 999999
83
84 alpha-beta-eval t = data t
85
86 alpha-beta-tree t d alpha beta = if (null? t) alpha
87 if (or (null? (first-child t)) (lte d 0)) (alpha-beta-eval t)
88 alpha-beta-inside (first-child t) (-- d) alpha beta
89
90
91 alpha-beta-inside t d alpha beta = if (null? t) alpha
92 do
93 val = (* -1 (alpha-beta-tree t d (- 0 beta) (- 0 alpha) ) )
94 if (gte val beta) val
95 if (gt val alpha)
96 alpha-beta-tree (next-sibling t) d val beta
97 alpha-beta-tree (next-sibling t) d alpha beta
98
99 test = alpha-beta test-minimax-tree
100
Something went wrong with that request. Please try again.