# HG changeset patch
# User Mike Pavone <pavone@retrodev.com>
# Date 1342428904 25200
# Node ID 7d4e51b4769aa4f993526632ad945ec653b9d643
# Parent  ba17edeea7c7cf1f6ed7b3ffcea1ab64bad34484
Add hashset based pruning

diff -r ba17edeea7c7 -r 7d4e51b4769a src/lifter.tp
--- a/src/lifter.tp	Mon Jul 16 01:24:47 2012 -0700
+++ b/src/lifter.tp	Mon Jul 16 01:55:04 2012 -0700
@@ -100,6 +100,7 @@
 		#{
 			curbest <- (field clone) advance: "A"
 			states <- #[field]
+			visitedStates <- sets hash
 			bestMove:withMaxSteps <- :self :max{
 				n <- 0
 				while: { if: (states length) > 0 { if: n < max { not: (curbest succeeded) } } } do: {
@@ -110,15 +111,18 @@
 						foreach: candidates :idx move {
 							curfield <- curstate clone
 							curfield advance: (move cmd)
-							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) {
-									nextstates append: curfield
+							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) {
+										nextstates append: curfield
+									}
 								}
 							}
 						}
@@ -198,14 +202,15 @@
 			os write: 2 "--------iteration results-------\n"
 			os write: 2 "Best:\n"
 			(finder curbest) printGrid
+			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 "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
 		}
diff -r ba17edeea7c7 -r 7d4e51b4769a src/sim.tp
--- a/src/sim.tp	Mon Jul 16 01:24:47 2012 -0700
+++ b/src/sim.tp	Mon Jul 16 01:55:04 2012 -0700
@@ -371,6 +371,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
diff -r ba17edeea7c7 -r 7d4e51b4769a tuningresults.txt
--- a/tuningresults.txt	Mon Jul 16 01:24:47 2012 -0700
+++ b/tuningresults.txt	Mon Jul 16 01:55:04 2012 -0700
@@ -27,3 +27,47 @@
 maps/contest6.map: 702 (1:19.07)
 maps/contest7.map: 869 (0:08.58)
 maps/contest8.map: 707 (6:25.68)
+
+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)
+-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)
+-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)
+-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)