h48

commit ce2d2d1339b2e0f8f7bb4c5392acf4fbf4e00f03
parent 1272e304b6367c7dd94d25acf88b2843adabb93a
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sat,  5 Oct 2024 23:01:10 +0200

Merge branch 'master' of tronto.net:h48

Diffstat:
M
src/solvers/h48/gendata_h48.h
 | 
31
+++++++++++++++++++++++++++++++
M
tools/expected_distributions.h
 | 
67
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

2 files changed, 97 insertions(+), 1 deletion(-)
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
@@ -277,6 +277,37 @@ gendata_h48k2(gendata_h48_arg_t *arg)
 	static const uint8_t shortdepth = 8;
 	static const uint64_t capacity = 10000019;
 	static const uint64_t randomizer = 10000079;
+
+	/*
+	 * A good base value for the k=2 tables have few positions with value
+	 * 0, because those are treated as lower bound 0 and require a second
+	 * lookup in another table, and at the same time not too many positions
+	 * with value 3, because some of those are under-estimates.
+	 *
+	 * The following values for the base have been hand-picked. I first
+	 * performed some statistics on the frequency of these values, but
+	 * they turned out to be unreliable. I have not figured out why yet.
+	 * In the end I resorted to generating the same table with multiple
+	 * base value and see what was best.
+	 *
+	 * A curious case is h3, which has this distribution for base 8:
+	 *   [0] = 6686828
+	 *   [1] = 63867852
+	 *   [2] = 392789689
+	 *   [3] = 477195231
+	 *
+	 * and this for base 9:
+	 *   [0] = 70554680
+	 *   [1] = 392789689
+	 *   [2] = 462294676
+	 *   [3] = 14900555
+	 *
+	 * I ended up picking base 8 to have a much lower count of elements
+	 * with value 0, at the cost of a less precise estimate for the higher
+	 * values. But I am not 100% confident this is the optimal choice,
+	 * so I'll leave it here for future considerations.
+	 */
+	 
 	static const uint8_t base[] = {
 		[0]  = 8,
 		[1]  = 8,
diff --git a/tools/expected_distributions.h b/tools/expected_distributions.h
@@ -43,6 +43,71 @@ uint64_t expected_h48[12][9][21] = {
 			[3] = 41281787,
 		},
 	},
+	[2] = {
+		[2] = {
+			[0] = 6391286,
+			[1] = 55494785,
+			[2] = 252389935,
+			[3] = 155993794,
+		},
+	},
+	[3] = {
+		[2] = {
+			[0] = 6686828,
+			[1] = 63867852,
+			[2] = 392789689,
+			[3] = 477195231,
+		},
+
+	},
+	[4] = {
+		[2] = {
+			[0] = 77147213,
+			[1] = 543379415,
+			[2] = 1139570251,
+			[3] = 120982321,
+		},
+	},
+	[5] = {
+		[2] = {
+			[0] = 82471284,
+			[1] = 687850732,
+			[2] = 2345840746,
+			[3] = 645995638,
+		},
+	},
+	[6] = {
+		[2] = {
+			[0] = 85941099,
+			[1] = 804752968,
+			[2] = 4077248182,
+			[3] = 2556374551,
+		},
+	},
+	[7] = {
+		[2] = {
+			[0] = 88529761,
+			[1] = 897323475,
+			[2] = 6126260791,
+			[3] = 7936519573,
+		},
+	},
+	[8] = {
+		/* Unknown */
+		[2] = {0},
+	},
+	[9] = {
+		/* Unknown */
+		[2] = {0},
+	},
+	[10] = {
+		/* Unknown */
+		[2] = {0},
+	},
+	[11] = {
+		/* Unknown */
+		[2] = {0},
+	},
 };
 
 static bool
@@ -82,7 +147,7 @@ unknown_h48(uint8_t h, uint8_t k)
 	if (k == 4 && h != 0)
 		return true;
 
-	return k == 2 && h > 1;
+	return k == 2 && h > 7;
 }
 
 STATIC bool