From d5ac28b1b329e91a1f403601015cd48a2d7dc3a3 Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Mon, 6 Dec 2010 18:36:43 +0100
Subject: [PATCH] UCT descent: Introduce information on last significant node

This will be useful e.g. for pool-rave. The threshold of significancy is
configurable. (The default value comes from the pool RAVE paper.)
---
 uct/internal.h |  5 +++++
 uct/uct.c      | 11 +++++++++++
 uct/walk.c     |  6 ++++++
 3 files changed, 22 insertions(+)

diff --git a/uct/internal.h b/uct/internal.h
index 884e814..4290f18 100644
--- a/uct/internal.h
+++ b/uct/internal.h
@@ -43,6 +43,7 @@ struct uct {
 	unsigned long max_pruned_size;
 	unsigned long pruning_threshold;
 	int mercymin;
+	int significant_threshold;
 
 	int threads;
 	enum uct_thread_model {
@@ -117,6 +118,10 @@ struct uct_descent {
 	/* Value of main tree node (with all value factors, but unbiased
 	 * - without exploration factor), from black's perspective. */
 	struct move_stats value;
+	/* The last "significant" node along the descent (i.e. node
+	 * with higher than configured number of playouts). */
+	struct tree_node *significant;
+	enum stone significant_color; // color of the significant node
 };
 
 
diff --git a/uct/uct.c b/uct/uct.c
index 09d5764..c36d95f 100644
--- a/uct/uct.c
+++ b/uct/uct.c
@@ -525,6 +525,7 @@ uct_state_init(char *arg, struct board *b)
 	u->resign_threshold = 0.2;
 	u->sure_win_threshold = 0.85;
 	u->mercymin = 0;
+	u->significant_threshold = 50;
 	u->expand_p = 2;
 	u->dumpthres = 1000;
 	u->playout_amaf = true;
@@ -893,6 +894,16 @@ uct_state_init(char *arg, struct board *b)
 				 * sequences first moves instead. */
 				u->local_tree_pseqroot = !optval || atoi(optval);
 
+			/** Other heuristics */
+			} else if (!strcasecmp(optname, "significant_threshold") && optval) {
+				/* Some heuristics (XXX: so far, none) rely
+				 * on the knowledge of the last "significant"
+				 * node in the descent. Such a node is
+				 * considered reasonably trustworthy to carry
+				 * some meaningful information in the values
+				 * of the node and its children. */
+				u->significant_threshold = atoi(optval);
+
 			/** Distributed engine slaves setup */
 
 			} else if (!strcasecmp(optname, "slave")) {
diff --git a/uct/walk.c b/uct/walk.c
index 93cf127..da86862 100644
--- a/uct/walk.c
+++ b/uct/walk.c
@@ -306,6 +306,7 @@ uct_playout(struct uct *u, struct board *b, enum stone player_color, struct tree
 	#define DLEN 512
 	struct uct_descent descent[DLEN];
 	descent[0].node = n; descent[0].lnode = NULL;
+	descent[0].significant = NULL;
 	int dlen = 1;
 	/* Total value of the sequence. */
 	struct move_stats seq_value = { .playouts = 0 };
@@ -349,6 +350,11 @@ uct_playout(struct uct *u, struct board *b, enum stone player_color, struct tree
 
 		/*** Perform the descent: */
 
+		if (descent[dlen].node->playouts >= u->significant_threshold) {
+			descent[dlen].significant = n;
+			descent[dlen].significant_color = node_color;
+		}
+
 		seq_value.playouts += descent[dlen].value.playouts;
 		seq_value.value += descent[dlen].value.value * descent[dlen].value.playouts;
 		n = descent[dlen++].node;
-- 
2.11.4.GIT