[computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Mon, Mar 10, 2008 at 10:04:18PM -0400, Don Dailey wrote:
> Your method is to allocate 1 node when it's been visited once or twice -
> very natural I agree.   My method is to allocate all the children at
> once, and wait until the parent has been visited some number of times
> (currently 100).   If there are 50 legal moves, that gives on average
> about 1 node allocation every 2 visits, which is what you said you do.  

I _expand_ 1 node when it's been visited twice, not allocate.

To clarify further:

	...
	if (tree_leaf_node(n)) {
		if (n->playouts >= u->expand_p /* 2 */)
			tree_expand_node(t, n, &b2);
			/* Just now occured to me that I should probably
			 * descend to one of the children now yet. */

		result = play_random_game(&b2, stone_other(color), u->gamelen);
		break;
	}
	...

void
tree_expand_node(struct tree *t, struct tree_node *node, struct board *b)
{
	tree_add_child(node, tree_init_node(pass));
        for (int i = 1; i < t->board->size; i++)
                for (int j = 1; j < t->board->size; j++)
			if (board_atxy(b, i, j) == S_NONE)
				tree_add_child(node, tree_init_node(coord(i, j)));
}

-- 
				Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.	-- J. W. von Goethe