Mercurial > repos > icfp2012

annotate src/lifter.tp @ 57:397089dccb32

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Compile with -O2. Add tuning parameters and tuning results script
author Mike Pavone <pavone@retrodev.com>
date Sun, 15 Jul 2012 23:55:29 -0700
parents fbeedb3aa239
children 7d4e51b4769a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
91 abs <- :val {
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
92 if: val < 0 { 0 - val } else: { val }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
93 }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
94
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
95 distanceFrom:to <- :sx sy :dx dy {
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
96 (abs: sx - dx) + (abs: sy - dy)
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
97 }
f7a1daaec925 Use dictionary
Mike Pavone <pavone@retrodev.com>
parents: 28
diff changeset
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]
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
103 bestMove:withMaxSteps <- :self :max{
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
104 n <- 0
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
105 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
106 nextstates <- #[]
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
107 foreach: states :idx curstate {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
108 me <-curstate getRobot
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
109 candidates <- curstate validMoves: (me x) (me y)
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
110 foreach: candidates :idx move {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
111 curfield <- curstate clone
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
112 curfield advance: (move cmd)
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
113 if: (curfield ended) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
114 if: (curfield score) > (curbest score) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
115 curbest <- curfield
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
116 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
117 } else: {
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
118 //check theoretical max score for current map state
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
119 //discard paths that can never be better than our current best
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
120 if: (curfield maxScore) > (curbest score) {
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
121 nextstates append: curfield
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
122 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
123 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
124 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
125 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
126 states <- nextstates
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
127 n <- n + 1
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 if: (curbest succeeded) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
130 false
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
131 } 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
132 (states length) > 0
44
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 }
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
135 cullStatesTo <- :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
136 print: "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
137 if: n < (states length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
138 states <- topN: states n
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
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 print: "states length is now " . (states length) . "\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
141 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
142 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
143 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
144
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
145 main <- :args {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
146 initmaxsteps <- 6
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
147 aftermaxsteps <- 5
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
148 cullstates <- 8
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
149 curarg <- 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
150 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
151 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
152 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
153 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
154 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
155 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
156 } else: {
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) = "-as" {
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 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
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) = "-cs" {
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 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
167 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
168 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
169 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
170 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
171 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
172 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
173
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
174 text <- sim readFd: 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
175 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
176 os write: 2 text
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
177 os write: 2 "width: " . (string: (initial width)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
178 os write: 2 "height: " . (string: (initial height)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
179
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
180 finder <- moveFinder: initial
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
181
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
182 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
183 while: { bestMove: finder withMaxSteps: maxsteps } 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
184 best <- -1000000
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
185 bestscore <- -1000000
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
186 foreach: (finder states) :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
187 h <- (el 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
188 s <- (el score)
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
189 if: (h > best) {
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
190 best <- h
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
191 }
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
192 if: (s > bestscore) {
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
193 bestscore <- s
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
194 }
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 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
196 finder cullStatesTo: cullstates
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
197 maxsteps <- aftermaxsteps
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
198 os write: 2 "--------iteration results-------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
199 os write: 2 "Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
200 (finder curbest) printGrid
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
201 os write: 2 "Current before cull\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
202 os write: 2 " Best Heuristic: " . best . "\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
203 os write: 2 " Best Score: " . bestscore . "\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
204 os write: 2 "After cull:\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
205 foreach: (finder states) :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
206 os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\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
207 os write: 2 " " . idx . " Score: " . (el score) . "\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
208 }
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
209 //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
210 //(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
211 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
212 os write: 2 "---------------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
213 os write: 2 "End Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
214 (finder curbest) printGrid
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
215 0
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
216 }
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
217 }