Mercurial > repos > icfp2012

changeset 65:aa822c683e28

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge
author Mike Pavone <pavone@retrodev.com>
date Mon, 16 Jul 2012 04:35:43 -0700
parents 3d058b4889a2 (diff) ca86c88c2336 (current diff)
children cffcf36f1610
files src/sim.tp
diffstat 8 files changed, 345 insertions(+), 52 deletions(-) [+]
line wrap: on
line diff
--- a/Makefile	Sun Jul 15 22:24:35 2012 -0700
+++ b/Makefile	Mon Jul 16 04:35:43 2012 -0700
@@ -16,7 +16,7 @@
 build/lifter.tp.c : src/sim.tp src/lifter.tp
 
 $(OUTDIR)/% : $(OBJDIR)/%.tp.c
-	gcc -ggdb -I$(TPDIR) -o $@ $< $(TPDIR)/runtime/object.c -lgc
+	gcc -O2 -I$(TPDIR) -o $@ $< $(TPDIR)/runtime/object.c -lgc
 
 $(OBJDIR)/%.tp.c : $(SRCDIR)/%.tp
 	$(TPC) -basedir $(TPDIR)/ -i src $(TPFLAGS) $< -o $@
--- a/PACKAGES-TESTING	Sun Jul 15 22:24:35 2012 -0700
+++ b/PACKAGES-TESTING	Mon Jul 16 04:35:43 2012 -0700
@@ -0,0 +1,2 @@
+libgc-dev
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lifter	Mon Jul 16 04:35:43 2012 -0700
@@ -0,0 +1,4 @@
+#!/bin/sh
+
+bin/lifter -is 4 -as 3 -cs 128
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/makesub	Mon Jul 16 04:35:43 2012 -0700
@@ -0,0 +1,5 @@
+#!/bin/sh
+dest=icfp-96850422.tgz
+rm -f $dest
+tar -cvzf $dest src/*.tp bin/lifter lifter install README PACKAGES-TESTING
+
--- a/src/lifter.tp	Sun Jul 15 22:24:35 2012 -0700
+++ b/src/lifter.tp	Mon Jul 16 04:35:43 2012 -0700
@@ -100,8 +100,10 @@
 		#{
 			curbest <- (field clone) advance: "A"
 			states <- #[field]
+			visitedStates <- sets hash
 			bestMove:withMaxSteps <- :self :max{
 				n <- 0
+				hashelim <- 0
 				while: { if: (states length) > 0 { if: n < max { not: (curbest succeeded) } } } do: {
 					nextstates <- #[]
 					foreach: states :idx curstate {
@@ -118,7 +120,10 @@
 								//check theoretical max score for current map state
 								//discard paths that can never be better than our current best
 								if: (curfield maxScore) > (curbest score) {
-									nextstates append: curfield
+									if: (not: (visitedStates contains?: curfield)) {
+										visitedStates add: curfield
+										nextstates append: curfield
+									}
 								}
 							}
 						}
@@ -133,14 +138,52 @@
 				}
 			}
 			cullStatesTo <- :n {
-				print: "culling " . (states length) . " to " . n . "\n"
-				states <- topN: states n
-				print: "states length is now " . (states length) . "\n"
+				os write: 2 "culling " . (states length) . " to " . n . "\n"
+				if: n < (states length) {
+					states <- topN: states n
+				}
+				os write: 2 "states length is now " . (states length) . "\n"
 			}
 		}
 	}
 	
-	main <- {
+	main <- :args {
+		initmaxsteps <- 6
+		aftermaxsteps <- 5
+		cullstates <- 8
+		curarg <- 1
+		cullwhenover <- 0
+		while: { curarg < (args length) } do: {
+			if: (args get: curarg) = "-is" {
+				curarg <- curarg + 1
+				if: curarg < (args length) {
+					initmaxsteps <- ((args get: curarg) int32)
+				}
+			} else: {
+				if: (args get: curarg) = "-as" {
+					curarg <- curarg + 1
+					if: curarg < (args length) {
+						aftermaxsteps <- ((args get: curarg) int32)
+					}
+				} else: {
+					if: (args get: curarg) = "-cs" {
+						curarg <- curarg + 1
+						if: curarg < (args length) {
+							cullstates <- ((args get: curarg) int32)
+						}
+					} else: {
+						if: (args get: curarg) = "-co" {
+							curarg <- curarg + 1
+							if: curarg < (args length) {
+								cullwhenover <- ((args get: curarg) int32)
+							}	
+						}
+					}
+				}
+			}
+			curarg <- curarg + 1
+		}
+		
 		text <- sim readFd: 0
 		initial <- (sim state) fromStr: text
 		os write: 2 text
@@ -148,40 +191,43 @@
 		os write: 2 "height: " . (string: (initial height)) . "\n"
 		
 		finder <- moveFinder: initial
-		initmaxsteps <- 6
+		
 		maxsteps <- initmaxsteps
 		while: { bestMove: finder withMaxSteps: maxsteps } do: {
-			best <- -1000000
-			bestscore <- -1000000
-			foreach: (finder states) :idx el {
-				h <- (el heuristic)
-				s <- (el score)
-				if: (h > best) {
-					best <- h
-				}
-				if: (s > bestscore) {
-					bestscore <- s
-				}
+			//best <- -1000000
+			//bestscore <- -1000000
+			//foreach: (finder states) :idx el {
+			//	h <- (el heuristic)
+			//	s <- (el score)
+			//	if: (h > best) {
+			//		best <- h
+			//	}
+			//	if: (s > bestscore) {
+			//		bestscore <- s
+			//	}
+			//}
+			if: ((finder states) length) > cullwhenover {
+				finder cullStatesTo: cullstates
 			}
-			finder cullStatesTo: 8
-			maxsteps <- initmaxsteps - 1
+			maxsteps <- aftermaxsteps
 			os write: 2 "--------iteration results-------\n"
 			os write: 2 "Best:\n"
 			(finder curbest) printGrid
-			os write: 2 "Current before cull\n"
-			os write: 2 " Best Heuristic: " . best . "\n"
-			os write: 2 " Best Score: " . bestscore . "\n"
-			os write: 2 "After cull:\n"
-			foreach: (finder states) :idx el{
-				os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\n"
-				os write: 2 " " . idx . " Score: " . (el score) . "\n"
-			}
+			//os write: 2 "Hash: " . ((finder curbest) hash)
+			//os write: 2 "Current before cull\n"
+			//os write: 2 " Best Heuristic: " . best . "\n"
+			//os write: 2 " Best Score: " . bestscore . "\n"
+			//os write: 2 "After cull:\n"
+			//foreach: (finder states) :idx el{
+			//	os write: 2 " " . idx . " Heuristic: " . (el heuristic) . "\n"
+			//	os write: 2 " " . idx . " Score: " . (el score) . "\n"
+			//}
 			//os write: 2 "Current:\n"
 			//(finder playfield) printGrid
 		}
 		os write: 2 "---------------\n"
 		os write: 2 "End Best:\n"
 		(finder curbest) printGrid
-		
+		0
 	}
 }
--- a/src/sim.tp	Sun Jul 15 22:24:35 2012 -0700
+++ b/src/sim.tp	Mon Jul 16 04:35:43 2012 -0700
@@ -32,7 +32,7 @@
 				string <- idStr
 				isrobot <- { false }
 				eq <- :other { id = (other id) }
-				navigable <- { cannav }				
+				navigable <- cannav
 			}
 			typedict set: (ret id) ret
 			ret
@@ -186,9 +186,7 @@
 						} 
 					}}
 					here <- calcIndex: x y
-					//TODO: Add wait move when rocks are in motion
-					//(amove: here "W") 
-					cur <- #[(amove: here "A")]
+					cur <- #[(amove: here "A") (amove: here "W")]
 					up <- amove: (calcIndex: x y + 1) "U"
 					down <- amove: (calcIndex: x y - 1) "D"
 					left <- amove: (calcIndex: x - 1 y) "L"
@@ -201,7 +199,10 @@
 					cur
 				}
 				distanceFrom:to <- :x y celltype {
-					//print: "calculating distance from " . x . ", " . y . " to " . celltype . "\n"
+					//debugLog: "calculating distance from " . x . ", " . y . " to " . celltype . "\n"
+					if: (celltype eq: (cellTypes closedLift)) {
+						celltype navigable!: true
+					}
 					moves <- validMoves: x y
 					curdist <- 0
 					visited <- _nextGrid
@@ -212,14 +213,17 @@
 					while: { if: notfound { (moves length) > 0 } } do: {
 						nextmoves <- #[]
 						curdist <- curdist + 1
+						//debugLog: "moves at distance " . curdist . "\n"
 						foreach: moves :idx move {
 							curpos <- move index
+							//debugLog: "" . move . " " . (grid get: curpos) . "\n"
 							if: (not: (visited get: curpos)) {
 								if: ((grid get: curpos) eq: celltype) {
 									notfound <- false
 								} else: {
 									visited set: curpos true
 									foreach: (validMoves: (calcX: curpos) (calcY: curpos)) :idx move {
+										
 										nextmoves append: move
 									}
 								}
@@ -227,7 +231,14 @@
 						}
 						moves <- nextmoves
 					}
-					curdist
+					if: (celltype eq: (cellTypes closedLift)) {
+						celltype navigable!: false
+					}
+					if: notfound {
+						-1
+					} else: {
+						curdist
+					}
 				}
 				getRobot <- { _robot }
 				updatePos <- :obj Index {
@@ -244,11 +255,32 @@
 				heuristic <- {
 					if: (not: _heuristicValid) {
 						dest <- if: (_robot collected) = lambdaCount {
-							cellTypes openLift
+							dist <- (distanceFrom: (_robot x) (_robot y) to: (cellTypes openLift))
+							if: dist < 0 {
+								//debugLog: "open lift unreachable\n"
+								_heuristic <- (_robot collected) * 50 -  (moves length)
+							} else: {
+								//debugLog: "open lift unreachable at distance" . dist . "\n"
+								_heuristic <- (_robot collected) * 75 - dist -  (moves length)
+							}
 						} else: {
-							cellTypes lambda
+							mult <- 0
+							liftdist <- (distanceFrom: (_robot x) (_robot y) to: (cellTypes closedLift))
+							if: liftdist < 0 {
+								mult <- 50
+							} else: {
+								mult <- 75
+							}
+							lambdadist <- (distanceFrom: (_robot x) (_robot y) to: (cellTypes lambda))
+							if: lambdadist < 0 {
+								//debugLog: "lambda unreachable with lift multilier " . mult . "\n"
+								_heuristic <- score
+							} else: {
+								//debugLog: "lambda reachable at distance " . lambdadist . " lift multilier " . mult . "\n"
+								_heuristic <- (_robot collected) * mult - lambdadist - (moves length)
+							}
 						}
-						_heuristic <- score - (distanceFrom: (_robot x) (_robot y) to: dest)
+						//_heuristic <- (_robot collected) * 75 - (distanceFrom: (_robot x) (_robot y) to: (cellTypes openLift) -  (moves length)
 						_heuristicValid <- true
 					}
 					_heuristic
@@ -316,21 +348,34 @@
 					addPoints: (_robot collected) * 25
 				}
 				advance <- :roboCmd {
-					_heuristicValid <- false
-					if: roboCmd = "A" {
-						moves append: roboCmd
-						abort
-					}
+					if: roboCmd = "?" {
+						os write: 2 "valid moves: "
+						valid <- validMoves: (_robot x) (_robot y)
+						foreach: valid :idx el {
+							os write: 2 (el cmd)
+						}
+						os write: 2 "\n"
+					} else: {
+						if: roboCmd = "h" {
+							os write: 2 "heuristic: " . heuristic . "\n"
+						} else: {
+							_heuristicValid <- false
+							if: roboCmd = "A" {
+								moves append: roboCmd
+								abort
+							}
 					
-					if: (not: _ended) {
-						_robot doCmd: roboCmd
-						score <- score - 1
-						moves append: roboCmd
-						doUpdate:
-						checkForDeath:
-						swapGrids:
-						if: (moves length) >= _maxmoves {
-							abort
+							if: (not: _ended) {
+								_robot doCmd: roboCmd
+								score <- score - 1
+								moves append: roboCmd
+								doUpdate:
+								checkForDeath:
+								swapGrids:
+								if: (moves length) >= _maxmoves {
+									abort
+								}
+							}
 						}
 					}
 					self
@@ -378,6 +423,14 @@
 					myclone lambdaCount!: lambdaCount
 					myclone
 				}
+				hash <- {
+					value <- ((grid get: 0) id) * 128
+					foreach: grid :idx el {
+						value <- 1000003 * value + (el id)
+					}
+					//TODO add in any important state from outside grid
+					value
+				}
 			}
 			foreach: in_grid :index el{
 				_nextGrid append: el
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tuning.sh	Mon Jul 16 04:35:43 2012 -0700
@@ -0,0 +1,12 @@
+#!/bin/sh
+echo $@ >> tuningresults.txt
+echo >> tuningresults.txt
+
+for file in maps/contest1.map maps/contest2.map maps/contest3.map maps/contest4.map maps/contest5.map maps/contest6.map maps/contest7.map maps/contest8.map; do
+	/usr/bin/time -f %E -o tuntiming.txt bin/lifter $@ < $file 2>tunout.txt
+	text=`tail -n 6 tunout.txt`
+	score=`echo $text | sed 's/.*score: \([0-9]*\).*/\1/'`
+	time=`cat tuntiming.txt`
+	echo "$file: $score ($time)";
+	echo "$file: $score ($time)" >> tuningresults.txt
+done
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tuningresults.txt	Mon Jul 16 04:35:43 2012 -0700
@@ -0,0 +1,171 @@
+-is 2 -as 1 -cs 500
+
+maps/contest1.map: 212 (0:01.22)
+maps/contest2.map: 275 (0:03.92)
+maps/contest3.map: 275 (0:05.03)
+maps/contest4.map: 575 (0:06.50)
+maps/contest5.map: 1295 (0:23.83)
+maps/contest6.map: 702 (1:19.81)
+maps/contest7.map: 869 (0:08.49)
+maps/contest8.map: 707 (6:22.09)
+
+total: 4910
+
+-is 2 -as 1 -cs 750
+
+maps/contest1.map: 212 (0:01.80)
+maps/contest2.map: 281 (0:04.25)
+maps/contest3.map: 275 (0:08.77)
+maps/contest4.map: 575 (0:10.54)
+maps/contest5.map: 1295 (0:36.98)
+maps/contest6.map: 702 (2:03.55)
+maps/contest7.map: 869 (0:12.54)
+
+total: 4209
+
+-is 5 -as 1 -cs 500
+
+maps/contest1.map: 212 (0:01.26)
+maps/contest2.map: 275 (0:03.90)
+maps/contest3.map: 275 (0:05.03)
+maps/contest4.map: 575 (0:06.49)
+maps/contest5.map: 1295 (0:23.74)
+maps/contest6.map: 702 (1:19.07)
+maps/contest7.map: 869 (0:08.58)
+maps/contest8.map: 707 (6:25.68)
+
+total: 4910
+
+With hashset pruning
+
+
+-is 2 -as 1 -cs 500
+
+maps/contest1.map: 212 (0:00.38)
+maps/contest2.map: 281 (0:02.96)
+maps/contest3.map: 275 (0:06.45)
+maps/contest4.map: 575 (0:08.57)
+maps/contest5.map: 1303 (0:31.95)
+maps/contest6.map: 1133 (1:53.77)
+maps/contest7.map: 869 (0:08.74)
+maps/contest8.map: 273 (1:41.30)
+
+total: 4921
+
+-is 4 -as 3 -cs 250
+
+maps/contest1.map: 212 (0:00.32)
+maps/contest2.map: 281 (0:03.74)
+maps/contest3.map: 275 (0:06.65)
+maps/contest4.map: 575 (0:06.63)
+maps/contest5.map: 1295 (1:09.76)
+maps/contest6.map: 1103 (1:21.92)
+maps/contest7.map: 869 (0:05.88)
+maps/contest8.map: 659 (2:13.52)
+
+total: 5269
+
+-is 4 -as 3 -cs 64
+
+maps/contest1.map: 212 (0:00.18)
+maps/contest2.map: 275 (0:01.41)
+maps/contest3.map: 275 (0:01.76)
+maps/contest4.map: 563 (0:03.32)
+maps/contest5.map: 1293 (0:11.39)
+maps/contest6.map: 1131 (0:15.09)
+maps/contest7.map: 869 (0:01.51)
+maps/contest8.map: 237 (0:23.60)
+
+total: 4580
+
+-is 5 -as 4 -cs 64
+
+maps/contest1.map: 212 (0:00.16)
+maps/contest2.map: 136 (0:01.10)
+maps/contest3.map: 275 (0:02.44)
+maps/contest4.map: 575 (0:02.98)
+maps/contest5.map: 1293 (0:30.78)
+maps/contest6.map: 1131 (0:16.51)
+maps/contest7.map: 869 (0:01.92)
+maps/contest8.map: 272 (0:55.84)
+
+total: 4763
+
+-is 1 -as 1 -cs 128 -co 3000
+
+maps/contest1.map: 212 (0:00.32)
+maps/contest2.map: 281 (0:03.24)
+maps/contest3.map: 275 (0:08.19)
+maps/contest4.map: 575 (0:16.44)
+maps/contest5.map: 1293 (1:07.18)
+maps/contest6.map: 1133 (2:53.12)
+maps/contest7.map: 869 (0:13.08)
+maps/contest8.map: 268 (2:26.28)
+
+total: 4906
+
+Don't check/add hashset until after other checks
+
+
+-is 5 -as 4 -cs 64
+
+maps/contest1.map: 212 (0:00.20)
+maps/contest2.map: 143 (0:01.34)
+maps/contest3.map: 275 (0:02.90)
+maps/contest4.map: 575 (0:03.64)
+maps/contest5.map: 1293 (0:44.88)
+maps/contest6.map: 1131 (0:20.06)
+maps/contest7.map: 869 (0:02.30)
+maps/contest8.map: 661 (1:15.42)
+-is 2 -as 1 -cs 750
+
+maps/contest1.map: 212 (0:00.32)
+maps/contest2.map: 281 (0:05.12)
+maps/contest3.map: 275 (0:11.36)
+maps/contest4.map: 575 (0:13.63)
+maps/contest5.map: 1295 (1:22.96)
+maps/contest6.map: 1129 (3:55.69)
+maps/contest7.map: 869 (0:17.09)
+maps/contest8.map: 707 (3:11.48)
+
+Updated Heuristic
+
+-is 4 -as 3 -cs 64
+
+maps/contest1.map: 212 (0:00.20)
+maps/contest2.map: 280 (0:00.93)
+maps/contest3.map: 275 (0:02.30)
+maps/contest4.map: 563 (0:05.61)
+maps/contest5.map: 1299 (0:21.50)
+maps/contest6.map: 1131 (0:20.65)
+maps/contest7.map: 869 (0:01.97)
+maps/contest8.map: 706 (0:44.52)
+
+total: 5335
+
+-is 2 -as 1 -cs 500
+
+maps/contest1.map: 212 (0:00.31)
+maps/contest2.map: 281 (0:03.94)
+maps/contest3.map: 275 (0:08.50)
+maps/contest4.map: 575 (0:11.71)
+maps/contest5.map: 1303 (0:59.64)
+maps/contest6.map: 1129 (2:38.82)
+maps/contest7.map: 869 (0:10.03)
+maps/contest8.map: 706 (2:17.12)
+
+total: 5350
+
+-is 4 -as 3 -cs 128
+
+maps/contest1.map: 212 (0:00.26)
+maps/contest2.map: 280 (0:01.73)
+maps/contest3.map: 275 (0:04.44)
+maps/contest4.map: 575 (0:05.67)
+maps/contest5.map: 1303 (0:40.64)
+maps/contest6.map: 1129 (0:45.35)
+maps/contest7.map: 869 (0:03.90)
+maps/contest8.map: 706 (1:36.11)
+
+total: 5349
+