Mercurial > repos > icfp2012

annotate src/lifter.tp @ 60:7d4e51b4769a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add hashset based pruning
author Mike Pavone <pavone@retrodev.com>
date Mon, 16 Jul 2012 01:55:04 -0700
parents 397089dccb32
children f851895ea67a
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
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
106 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
107 nextstates <- #[]
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
108 foreach: states :idx curstate {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
109 me <-curstate getRobot
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
110 candidates <- curstate validMoves: (me x) (me y)
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
111 foreach: candidates :idx move {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
112 curfield <- curstate clone
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
113 curfield advance: (move cmd)
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
114 if: (not: (visitedStates contains?: curfield)) {
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
115 visitedStates add: curfield
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
116 if: (curfield ended) {
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
117 if: (curfield score) > (curbest score) {
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
118 curbest <- curfield
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
119 }
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
120 } else: {
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
121 //check theoretical max score for current map state
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
122 //discard paths that can never be better than our current best
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
123 if: (curfield maxScore) > (curbest score) {
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
124 nextstates append: curfield
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
125 }
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
126 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
127 }
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 states <- nextstates
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
131 n <- n + 1
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
132 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
133 if: (curbest succeeded) {
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
134 false
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
135 } 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
136 (states length) > 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
137 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
138 }
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
139 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
140 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
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 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
145 }
44
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 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
148
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
149 main <- :args {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
150 initmaxsteps <- 6
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
151 aftermaxsteps <- 5
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
152 cullstates <- 8
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
153 curarg <- 1
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 }
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 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
174 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
175 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
176 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
177
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
178 text <- sim readFd: 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
179 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
180 os write: 2 text
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
181 os write: 2 "width: " . (string: (initial width)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
182 os write: 2 "height: " . (string: (initial height)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
183
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
184 finder <- moveFinder: initial
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
185
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
186 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
187 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
188 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
189 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
190 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
191 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
192 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
193 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
194 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
195 }
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull 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 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
197 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
198 }
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
199 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
200 finder cullStatesTo: cullstates
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
201 maxsteps <- aftermaxsteps
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
202 os write: 2 "--------iteration results-------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
203 os write: 2 "Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
204 (finder curbest) printGrid
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
205 os write: 2 "Hash: " . ((finder curbest) hash)
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
206 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
207 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
208 os write: 2 " Best Score: " . bestscore . "\n"
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
209 //os write: 2 "After cull:\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
210 //foreach: (finder states) :idx el{
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
211 // os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
212 // os write: 2 " " . idx . " Score: " . (el score) . "\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
213 //}
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
214 //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
215 //(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
216 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
217 os write: 2 "---------------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
218 os write: 2 "End Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
219 (finder curbest) printGrid
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
220 0
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
221 }
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
222 }