Mercurial > repos > icfp2012

annotate src/lifter.tp @ 67:ff8d7b4499f5 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Submission prep
author Mike Pavone <pavone@retrodev.com>
date Mon, 16 Jul 2012 04:48:50 -0700
parents ff2b38518a58
children
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]
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
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
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
115 if: (curfield ended) {
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
116 if: (curfield score) > (curbest score) {
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
117 curbest <- curfield
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
118 }
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
119 } else: {
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
120 //check theoretical max score for current map state
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
121 //discard paths that can never be better than our current best
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
122 if: (curfield maxScore) > (curbest score) {
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
123 if: (not: (visitedStates contains?: curfield)) {
ff2b38518a58 Updated heuristic
Mike Pavone <pavone@retrodev.com>
parents: 61
diff changeset
124 visitedStates add: curfield
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
125 nextstates append: curfield
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
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 {
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
141 if: n < (states length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
142 states <- topN: states n
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
143 }
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
144 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
145 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
146 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
147
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
148 main <- :args {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
149 initmaxsteps <- 6
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
150 aftermaxsteps <- 5
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
151 cullstates <- 8
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
152 curarg <- 1
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
153 cullwhenover <- 0
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
154 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
155 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
156 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
157 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
158 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
159 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
160 } else: {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
161 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
162 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
163 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
164 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
165 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
166 } else: {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
167 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
168 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
169 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
170 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
171 }
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
172 } else: {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
173 if: (args get: curarg) = "-co" {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
174 curarg <- curarg + 1
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
175 if: curarg < (args length) {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
176 cullwhenover <- ((args get: curarg) int32)
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
177 }
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
178 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
179 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
180 }
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 curarg <- curarg + 1
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
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
185 text <- sim readFd: 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
186 initial <- (sim state) fromStr: text
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
187
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
188 finder <- moveFinder: initial
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
189
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
190 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
191 while: { bestMove: finder withMaxSteps: maxsteps } do: {
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
192 if: ((finder states) length) > cullwhenover {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
193 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
194 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
195 maxsteps <- aftermaxsteps
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
196 }
67
ff8d7b4499f5 Submission prep
Mike Pavone <pavone@retrodev.com>
parents: 62
diff changeset
197 (finder curbest) printMoves
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
198 0
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
199 }
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
200 }