Mercurial > repos > icfp2012
annotate src/lifter.tp @ 62:ff2b38518a58
Updated heuristic
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 16 Jul 2012 04:03:03 -0700 |
parents | f851895ea67a |
children | ff8d7b4499f5 |
rev | line source |
---|---|
3
bb29dcd46cbf
Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents:
0
diff
changeset
|
1 #{ |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
2 swap <- :arr from to { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
3 a <- arr get: from |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
4 b <- arr get: to |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
5 arr set: from b |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
6 arr set: to a |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
7 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
8 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
9 median <- :arr idx1 idx2 idx3 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
10 val1 <- (arr get: idx1) heuristic |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
11 val2 <- (arr get: idx2) heuristic |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
12 val3 <- (arr get: idx3) heuristic |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
13 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
14 if: val2 > val1 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
15 if: val3 > val2 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
16 idx2 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
17 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
18 if: val3 > val1 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
19 idx3 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
20 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
21 idx1 |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
22 } |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
23 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
24 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
25 //val1 >= val2 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
26 if: val3 > val1 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
27 idx1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
28 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
29 //val1 >= val3 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
30 if: val3 > val2 { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
31 idx3 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
32 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
33 idx2 |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
34 } |
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
35 } |
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
36 } |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
37 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
38 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
39 partition <- :arr left right pivotidx { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
40 pivotval <- (arr get: pivotidx) heuristic |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
41 //move pivot to end |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
42 swap: arr pivotidx right |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
43 i <- left |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
44 storeidx <- left |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
45 while: { i < right } do: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
46 if: ((arr get: i) heuristic) < pivotval { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
47 swap: arr storeidx i |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
48 storeidx <- storeidx + 1 |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
49 } |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
50 i <- i + 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
51 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
52 swap: arr storeidx right |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
53 storeidx |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
54 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
55 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
56 //quickselect shamelessly translated from pseudocode on Wikipedia |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
57 select <- :arr left right n { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
58 pivotidx <- median: arr left right (left + (right - left) / 2) |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
59 newpivotidx <- partition: arr left right pivotidx |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
60 pivotdist <- newpivotidx - left + 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
61 while: { pivotdist != n } do: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
62 if: n < pivotdist { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
63 right <- newpivotidx - 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
64 } else: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
65 n <- n - pivotdist |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
66 left <- newpivotidx + 1 |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
67 } |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
68 pivotidx <- median: arr left right (left + (right - right) / 2) |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
69 newpivotidx <- partition: arr left right pivotidx |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
70 pivotdist <- newpivotidx - left + 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
71 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
72 newpivotidx |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
73 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
74 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
75 topN <- :arr n { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
76 curidx <- (select: arr 0 (arr length) - 1 ((arr length) - n)) + 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
77 newarr <- #[] |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
78 while: { curidx < (arr length) } do: { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
79 newarr append: (arr get: curidx) |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
80 curidx <- curidx + 1 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
81 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
82 newarr |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
83 } |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
84 |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
85 printArr <- :arr { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
86 foreach: arr :idx el { |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
87 print: "" . idx . ": " . (el heuristic) . "\n" |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
88 } |
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
89 } |
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
90 |
31 | 91 abs <- :val { |
92 if: val < 0 { 0 - val } else: { val } | |
93 } | |
94 | |
95 distanceFrom:to <- :sx sy :dx dy { | |
96 (abs: sx - dx) + (abs: sy - dy) | |
97 } | |
98 | |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
99 moveFinder <- :field { |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
100 #{ |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
101 curbest <- (field clone) advance: "A" |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
102 states <- #[field] |
60 | 103 visitedStates <- sets hash |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
104 bestMove:withMaxSteps <- :self :max{ |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
105 n <- 0 |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
106 hashelim <- 0 |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
107 while: { if: (states length) > 0 { if: n < max { not: (curbest succeeded) } } } do: { |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
108 nextstates <- #[] |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
109 foreach: states :idx curstate { |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
110 me <-curstate getRobot |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
111 candidates <- curstate validMoves: (me x) (me y) |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
112 foreach: candidates :idx move { |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
113 curfield <- curstate clone |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
114 curfield advance: (move cmd) |
62 | 115 if: (curfield ended) { |
116 if: (curfield score) > (curbest score) { | |
117 curbest <- curfield | |
118 } | |
119 } else: { | |
120 //check theoretical max score for current map state | |
121 //discard paths that can never be better than our current best | |
122 if: (curfield maxScore) > (curbest score) { | |
123 if: (not: (visitedStates contains?: curfield)) { | |
124 visitedStates add: curfield | |
60 | 125 nextstates append: curfield |
126 } | |
45
9f1ca5ba2684
Discard entries for which we can easily tell that it will be impossible for them to be better than the current best. This allows us to terminate when we cannot solve the map
Mike Pavone <pavone@retrodev.com>
parents:
44
diff
changeset
|
127 } |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
128 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
129 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
130 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
131 states <- nextstates |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
132 n <- n + 1 |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
133 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
134 if: (curbest succeeded) { |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
135 false |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
136 } else: { |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
137 (states length) > 0 |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
138 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
139 } |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
140 cullStatesTo <- :n { |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
141 os write: 2 "culling " . (states length) . " to " . n . "\n" |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
142 if: n < (states length) { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
143 states <- topN: states n |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
144 } |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
145 os write: 2 "states length is now " . (states length) . "\n" |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
146 } |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
147 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
148 } |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
149 |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
150 main <- :args { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
151 initmaxsteps <- 6 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
152 aftermaxsteps <- 5 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
153 cullstates <- 8 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
154 curarg <- 1 |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
155 cullwhenover <- 0 |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
156 while: { curarg < (args length) } do: { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
157 if: (args get: curarg) = "-is" { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
158 curarg <- curarg + 1 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
159 if: curarg < (args length) { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
160 initmaxsteps <- ((args get: curarg) int32) |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
161 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
162 } else: { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
163 if: (args get: curarg) = "-as" { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
164 curarg <- curarg + 1 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
165 if: curarg < (args length) { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
166 aftermaxsteps <- ((args get: curarg) int32) |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
167 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
168 } else: { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
169 if: (args get: curarg) = "-cs" { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
170 curarg <- curarg + 1 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
171 if: curarg < (args length) { |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
172 cullstates <- ((args get: curarg) int32) |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
173 } |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
174 } else: { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
175 if: (args get: curarg) = "-co" { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
176 curarg <- curarg + 1 |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
177 if: curarg < (args length) { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
178 cullwhenover <- ((args get: curarg) int32) |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
179 } |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
180 } |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
181 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
182 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
183 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
184 curarg <- curarg + 1 |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
185 } |
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
186 |
20
50a456168c25
Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents:
3
diff
changeset
|
187 text <- sim readFd: 0 |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
188 initial <- (sim state) fromStr: text |
20
50a456168c25
Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents:
3
diff
changeset
|
189 os write: 2 text |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
190 os write: 2 "width: " . (string: (initial width)) . "\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
191 os write: 2 "height: " . (string: (initial height)) . "\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
192 |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
193 finder <- moveFinder: initial |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
194 |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
195 maxsteps <- initmaxsteps |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
196 while: { bestMove: finder withMaxSteps: maxsteps } do: { |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
197 //best <- -1000000 |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
198 //bestscore <- -1000000 |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
199 //foreach: (finder states) :idx el { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
200 // h <- (el heuristic) |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
201 // s <- (el score) |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
202 // if: (h > best) { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
203 // best <- h |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
204 // } |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
205 // if: (s > bestscore) { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
206 // bestscore <- s |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
207 // } |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
208 //} |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
209 if: ((finder states) length) > cullwhenover { |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
210 finder cullStatesTo: cullstates |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
211 } |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
212 maxsteps <- aftermaxsteps |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
213 os write: 2 "--------iteration results-------\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
214 os write: 2 "Best:\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
215 (finder curbest) printGrid |
61
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
216 //os write: 2 "Hash: " . ((finder curbest) hash) |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
217 //os write: 2 "Current before cull\n" |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
218 //os write: 2 " Best Heuristic: " . best . "\n" |
f851895ea67a
Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents:
60
diff
changeset
|
219 //os write: 2 " Best Score: " . bestscore . "\n" |
60 | 220 //os write: 2 "After cull:\n" |
221 //foreach: (finder states) :idx el{ | |
222 // os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\n" | |
223 // os write: 2 " " . idx . " Score: " . (el score) . "\n" | |
224 //} | |
53
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
225 //os write: 2 "Current:\n" |
fbeedb3aa239
Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents:
45
diff
changeset
|
226 //(finder playfield) printGrid |
39
9bccdb3ac979
Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents:
31
diff
changeset
|
227 } |
44
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
228 os write: 2 "---------------\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
229 os write: 2 "End Best:\n" |
0c09730c173e
Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents:
39
diff
changeset
|
230 (finder curbest) printGrid |
57
397089dccb32
Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents:
53
diff
changeset
|
231 0 |
3
bb29dcd46cbf
Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents:
0
diff
changeset
|
232 } |
bb29dcd46cbf
Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents:
0
diff
changeset
|
233 } |