annotate src/lifter.tp @ 62:ff2b38518a58

Updated heuristic
author Mike Pavone <pavone@retrodev.com>
date Mon, 16 Jul 2012 04:03:03 -0700
parents f851895ea67a
children ff8d7b4499f5
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 {
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
141 os write: 2 "culling " . (states length) . " to " . n . "\n"
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
142 if: n < (states length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
143 states <- topN: states n
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
144 }
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
145 os write: 2 "states length is now " . (states length) . "\n"
53
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
146 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
147 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
148 }
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
149
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
150 main <- :args {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
151 initmaxsteps <- 6
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
152 aftermaxsteps <- 5
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
153 cullstates <- 8
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
154 curarg <- 1
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
155 cullwhenover <- 0
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
156 while: { curarg < (args length) } do: {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
157 if: (args get: curarg) = "-is" {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
158 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
159 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
160 initmaxsteps <- ((args get: curarg) int32)
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
161 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
162 } else: {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
163 if: (args get: curarg) = "-as" {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
164 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
165 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
166 aftermaxsteps <- ((args get: curarg) int32)
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
167 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
168 } else: {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
169 if: (args get: curarg) = "-cs" {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
170 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
171 if: curarg < (args length) {
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
172 cullstates <- ((args get: curarg) int32)
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
173 }
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
174 } else: {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
175 if: (args get: curarg) = "-co" {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
176 curarg <- curarg + 1
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
177 if: curarg < (args length) {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
178 cullwhenover <- ((args get: curarg) int32)
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
179 }
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
180 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
181 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
182 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
183 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
184 curarg <- curarg + 1
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
185 }
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
186
20
50a456168c25 Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents: 3
diff changeset
187 text <- sim readFd: 0
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
188 initial <- (sim state) fromStr: text
20
50a456168c25 Split readFd out of readFile for use in lifter. Add code to read map from stdin to lifter using code in sim
Mike Pavone <pavone@retrodev.com>
parents: 3
diff changeset
189 os write: 2 text
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
190 os write: 2 "width: " . (string: (initial width)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
191 os write: 2 "height: " . (string: (initial height)) . "\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
192
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
193 finder <- moveFinder: initial
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
194
53
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
195 maxsteps <- initmaxsteps
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
196 while: { bestMove: finder withMaxSteps: maxsteps } do: {
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
197 //best <- -1000000
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
198 //bestscore <- -1000000
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
199 //foreach: (finder states) :idx el {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
200 // h <- (el heuristic)
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
201 // s <- (el score)
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
202 // if: (h > best) {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
203 // best <- h
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
204 // }
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
205 // if: (s > bestscore) {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
206 // bestscore <- s
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
207 // }
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
208 //}
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
209 if: ((finder states) length) > cullwhenover {
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
210 finder cullStatesTo: cullstates
53
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
211 }
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
212 maxsteps <- aftermaxsteps
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
213 os write: 2 "--------iteration results-------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
214 os write: 2 "Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
215 (finder curbest) printGrid
61
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
216 //os write: 2 "Hash: " . ((finder curbest) hash)
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
217 //os write: 2 "Current before cull\n"
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
218 //os write: 2 " Best Heuristic: " . best . "\n"
f851895ea67a Add cullwhenover option and more tuning results
Mike Pavone <pavone@retrodev.com>
parents: 60
diff changeset
219 //os write: 2 " Best Score: " . bestscore . "\n"
60
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
220 //os write: 2 "After cull:\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
221 //foreach: (finder states) :idx el{
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
222 // os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
223 // os write: 2 " " . idx . " Score: " . (el score) . "\n"
7d4e51b4769a Add hashset based pruning
Mike Pavone <pavone@retrodev.com>
parents: 57
diff changeset
224 //}
53
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
225 //os write: 2 "Current:\n"
fbeedb3aa239 Add heuristic for evaluating non-terminal states. Cull to 8 states based on heuristic rather than just a single one based on score.
Mike Pavone <pavone@retrodev.com>
parents: 45
diff changeset
226 //(finder playfield) printGrid
39
9bccdb3ac979 Add priority queue implementation to lifter. Add methods for cloning playfield and determining valid moves.
Mike Pavone <pavone@retrodev.com>
parents: 31
diff changeset
227 }
44
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
228 os write: 2 "---------------\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
229 os write: 2 "End Best:\n"
0c09730c173e Robot works on simple maps now
Mike Pavone <pavone@retrodev.com>
parents: 39
diff changeset
230 (finder curbest) printGrid
57
397089dccb32 Compile with -O2. Add tuning parameters and tuning results script
Mike Pavone <pavone@retrodev.com>
parents: 53
diff changeset
231 0
3
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
232 }
bb29dcd46cbf Put dummy code in placeholder source files. Create makefile.
Mike Pavone <pavone@retrodev.com>
parents: 0
diff changeset
233 }