[computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

  Hi,

On Mon, Mar 10, 2008 at 08:07:14PM -0400, Don Dailey wrote:
> > What is the justification of using the parent playout count instead of
> > the node playout count itself?
> >
> >   
> I don't know if it makes much difference how this is done, and I don't
> know how everybody else is doing it.      I allocate all the children at
> once and do not have to store pointers to each child,  just one pointer
> to the first child and a counter so that I know how many children there
> are.   On average I'm probably expanding every other time in the middle
> of the game. 

I really so far use just a completely unoptimized

	struct tree_node {
		/*
		 *            +------+
		 *            | node |
		 *            +------+
		 *          / <- parent
		 * +------+   v- sibling +------+
		 * | node | ------------ | node |
		 * +------+              +------+
		 *    | <- children          |
		 * +------+   +------+   +------+   +------+
		 * | node | - | node |   | node | - | node |
		 * +------+   +------+   +------+   +------+
		 */
		struct tree_node *parent, *sibling, *children;

		coord_t coord;
		int playouts; // # of playouts coming through this node
		int wins; // # of wins coming through this node
		float value; // wins/playouts
	};

even with no memory pools, every node allocated separately. This is one
of the things I'm likely to optimize when I get to that again, but so
far my feeling is that I'm fast and small enough not to really bother.
;-) And I can be sure that there are no bugs at least in this part of
the code.

-- 
				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