From 407ad58bcd6fa8e00e4d1277307668d785f8945a Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Wed, 30 Sep 2009 10:04:39 +0200
Subject: [PATCH] UCT: Normalize tree results, dividing them by number of
 threads

---
 uct/tree.c | 29 +++++++++++++++++++++++++++++
 uct/tree.h |  3 +++
 uct/uct.c  |  2 ++
 3 files changed, 34 insertions(+)

diff --git a/uct/tree.c b/uct/tree.c
index 262bd59..07ad237 100644
--- a/uct/tree.c
+++ b/uct/tree.c
@@ -304,6 +304,35 @@ tree_merge(struct tree *dest, struct tree *src)
 }
 
 
+static void
+tree_node_normalize(struct tree_node *node, int factor)
+{
+	for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
+		tree_node_normalize(node, factor);
+
+#define normalize(s1, s2, t) node->s2.t = node->s1.t + (node->s2.t - node->s1.t) / factor;
+	normalize(pamaf, amaf, playouts);
+	normalize(pamaf, amaf, wins);
+	normalize(pamaf, amaf, value);
+
+	normalize(pu, u, playouts);
+	normalize(pu, u, wins);
+	normalize(pu, u, value);
+#undef normalize
+}
+
+/* Normalize a tree, dividing the amaf and u values by given
+ * factor; otherwise, simulations run in independent threads
+ * two trees built upon the same board. To correctly handle
+ * results taken from previous simulation run, they are backed
+ * up in tree. */
+void
+tree_normalize(struct tree *tree, int factor)
+{
+	tree_node_normalize(tree->root, factor);
+}
+
+
 /* Tree symmetry: When possible, we will localize the tree to a single part
  * of the board in tree_expand_node() and possibly flip along symmetry axes
  * to another part of the board in tree_promote_at(). We follow b->symmetry
diff --git a/uct/tree.h b/uct/tree.h
index e8fb3c3..f7d4b32 100644
--- a/uct/tree.h
+++ b/uct/tree.h
@@ -41,6 +41,8 @@ struct tree_node {
 	struct move_stats prior;
 	/* XXX: Should be way for policies to add their own stats */
 	struct move_stats amaf;
+	/* Stats before starting playout; used for multi-thread normalization. */
+	struct move_stats pu, pamaf;
 #define NODE_HINT_NOAMAF 0x80
 	int hints;
 };
@@ -62,6 +64,7 @@ void tree_save(struct tree *tree, struct board *b, int thres);
 void tree_load(struct tree *tree, struct board *b);
 struct tree *tree_copy(struct tree *tree);
 void tree_merge(struct tree *dest, struct tree *src);
+void tree_normalize(struct tree *tree, int factor);
 
 void tree_expand_node(struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int radar, struct uct_policy *policy, int parity);
 void tree_delete_node(struct tree *tree, struct tree_node *node);
diff --git a/uct/uct.c b/uct/uct.c
index 3d8ebfe..72b0ac6 100644
--- a/uct/uct.c
+++ b/uct/uct.c
@@ -428,6 +428,8 @@ uct_genmove(struct engine *e, struct board *b, enum stone color)
 			pthread_mutex_unlock(&finish_serializer);
 		}
 		pthread_mutex_unlock(&finish_mutex);
+
+		tree_normalize(u->t, u->threads);
 	}
 
 	if (UDEBUGL(2))
-- 
2.11.4.GIT