Mercurial > repos > icfp2012

changeset 62:ff2b38518a58

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated heuristic
author Mike Pavone <pavone@retrodev.com>
date Mon, 16 Jul 2012 04:03:03 -0700
parents f851895ea67a
children fcce7192ea2e
files src/lifter.tp src/sim.tp tuningresults.txt
diffstat 3 files changed, 152 insertions(+), 33 deletions(-) [+]
line wrap: on
line diff
--- a/src/lifter.tp	Mon Jul 16 02:20:38 2012 -0700
+++ b/src/lifter.tp	Mon Jul 16 04:03:03 2012 -0700
@@ -112,16 +112,16 @@
 						foreach: candidates :idx move {
 							curfield <- curstate clone
 							curfield advance: (move cmd)
-							if: (not: (visitedStates contains?: curfield)) {
-								visitedStates add: curfield
-								if: (curfield ended) {
-									if: (curfield score) > (curbest score) {
-										curbest <- curfield
-									}
-								} else: {
-									//check theoretical max score for current map state
-									//discard paths that can never be better than our current best
-									if: (curfield maxScore) > (curbest score) {
+							if: (curfield ended) {
+								if: (curfield score) > (curbest score) {
+									curbest <- curfield
+								}
+							} else: {
+								//check theoretical max score for current map state
+								//discard paths that can never be better than our current best
+								if: (curfield maxScore) > (curbest score) {
+									if: (not: (visitedStates contains?: curfield)) {
+										visitedStates add: curfield
 										nextstates append: curfield
 									}
 								}
--- a/src/sim.tp	Mon Jul 16 02:20:38 2012 -0700
+++ b/src/sim.tp	Mon Jul 16 04:03:03 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
@@ -179,9 +179,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"
@@ -194,7 +192,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
@@ -205,14 +206,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
 									}
 								}
@@ -220,7 +224,14 @@
 						}
 						moves <- nextmoves
 					}
-					curdist
+					if: (celltype eq: (cellTypes closedLift)) {
+						celltype navigable!: false
+					}
+					if: notfound {
+						-1
+					} else: {
+						curdist
+					}
 				}
 				getRobot <- { _robot }
 				updatePos <- :obj Index {
@@ -237,11 +248,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
@@ -309,21 +341,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
--- a/tuningresults.txt	Mon Jul 16 02:20:38 2012 -0700
+++ b/tuningresults.txt	Mon Jul 16 04:03:03 2012 -0700
@@ -8,6 +8,9 @@
 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)
@@ -17,6 +20,9 @@
 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)
@@ -28,6 +34,8 @@
 maps/contest7.map: 869 (0:08.58)
 maps/contest8.map: 707 (6:25.68)
 
+total: 4910
+
 With hashset pruning
 
 
@@ -95,3 +103,69 @@
 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
+