[Computer-go] effectiveness of transposition tables for go

Thomas Lavergne thomas.lavergne at reveurs.org
Wed May 12 13:27:40 PDT 2010


Le 12 mai 2010 à 19:30, Don Dailey a écrit :

> Thomas,
> 
> You method sound very sensible if I understand it correctly and it seems to me to be the best.
> 
> I'm not clear on the memory collection when you run out of memory.   Are you saying that you track the "age" of each node, perhaps bumping a global age every time you create a node and just overwrite entries that are old when you are looking for a slot?   

I keep a "current time" variable that I increment each time I start a new walk in the tree. During this walk, I set the age of each node I cross to this value. So when I search for an old node, I look at the difference between node value and current global time. This value tell for how many step I've not gone through this node.

This allow me to find the oldest node to free. The best thing would be to search the oldest node in the full tree but this would be too expensive so, instead I just search in restricted subset of the hashtable. I've tried to add an additional check here to check a more larger subset if I didn't find a node old enough but this doesn't improve significantly the performance.

Freeing nodes on the fly require to be bit carefull about the design of your hashtable but another scheme allow to do it a lot more simply but less cleaner in my opinion. You use a very simple hashtable and when you are out of nodes, you stop a bit just for the time to collect all old nodes and restart searching. This is like a garbage collection scheme (and can be done during pondering to not loose time) and also work very well and have almost the same properties.

> So basically you don't create a big child list until you are sure you need it.   I'm not sure I fully understand your description except for the gist of it.    Do you generate only 1 child at a time or all at once (as soon as you know the parent will start getting expanded. 

I like to see my nodes as node with links to the childs but no childs... Let me explain a bit more.

Remember I don't use real tree so the notion of child is not real here. I just have nodes who represent a state of the goban. In this state there is some valid points to be played and I want to choose the best of them. In order to do this I keep in the node all informations needed to make an UCB+RAVE choice.

When I walk throught the part of the game tree stored as nodes in the hashtable, I always use only information stored in that node to make the choice of the next play and this play allow me to produce the next situation on the goban and so find an eventual next node in the hashtable.

When I come to a goban position for which no node currenly exist, I look at the informations used to choose the last play a decide if I'm confident enough that this is a promising way. If this is the case, I allocate a new heavy node and initialize it: this imply building all it's internal informations needed to choose play from this position so I need to find the valid play at this position and build the list.

For the moment I use a very simple way to choose if I allocate a new node based only on the number of simulation but you can use any scheme you want based on all informations you have.

So, to return to the parallel with the tree with light and heavy nodes, the informations stored in the child list of one of my node can be seen as a light node in a tree based engine: a small information used by the parent to choose next move but without informations about their own childs.

The difference come at the expansion time. In tree based engine, you replace the light node with a full node. From the parent point of view there is no change as it will still use the same information in the node but if the parent choose to go in this node then you will use the childs informations.

In my case, the operation equivalent to expansion to heavier node is adding a node for this child in the hashtable. So the light representation will still be in the parent list but the full information will be in the new node. Using hashtable, this make sense as the light informations is needed by the parent to make it's decision and the heavier one is needed by the child, so each one keep is own data. (in fact the child also need the light data so it is duplicated)

I'm not sure I'm very clear as english is not my native language but I hope this clearer. As an example, this is a rought code for doing this in pseudo-C like. I'm sure there is a lot of errors in it but I hope it will my scheme will be easier to understand with this as like the adage say "some code is worth thousand words" (or something like this ;-) :

struct node_s {
	int nb_simul;
	int nb_win;
	int nb_child;
	int child_point[nb_child];
	int child_simul[nb_child];
	int child_win  [nb_child];
}

search_in_tree(goban, create) {
	node = get_node_for(goban);
	// If no node go for playout
	if (node == NULL) {
		// If needed create the new node
		if (create) {
			node = get_newnode_for(goban);
			initialize(node);
		}
		// Go for a playout
		result = playout(goban);
		// Update and return
		update_node(node, result);
		return result;
	}
	// Select next point to play
	best = -1.0;
	for (i = 0; i < node->nb_child; i++) {
		sc = calc_score(node, i);
		if (sc > best)
			next = i;
	}
	point = node->child_point[next];
	// Play the move and go deeper
	play_a_stone(goban, point);
	result = search_in_tree(goban, (node->ch_simul[next] > 50));
	// Update node and return
	update_node(node, next, result);
	return result;
}





More information about the Computer-go mailing list