deep history pruning

[xr_a_y]

history leaf pruning is a thing. But how about history prune at higher depth with a history score limit that depends on depth ? It seems to be a little win inside Minic, but not really tuned yet.

[bob]

A while back (can't say about today since I have not followed this) history counters were found to be not very useful. With the very deep searches, the same move can be good in parts of the tree and bad in others. When Fruit came out, I played with the history pruning setting on our cluster and discovered that no matter what value was used, Fruit produced the same basic Elo over 30,000 games.

Others can explain if they have had better results. But in Fruit, and in Crafty, the counters simply did not seem to represent much of anything numerically. This is quite a different result from when Schaeffer first defined the history heuristic for move ordering based on 5 ply searches. The numbers look more sensible there since the tree is very small. Today's trees are 25 plies and deeper depending on time control. The numbers become much more muddled / random under that condition.

[xr_a_y]

A while back (can't say about today since I have not followed this) history counters were found to be not very useful. With the very deep searches, the same move can be good in parts of the tree and bad in others. When Fruit came out, I played with the history pruning setting on our cluster and discovered that no matter what value was used, Fruit produced the same basic Elo over 30,000 games.

Others can explain if they have had better results. But in Fruit, and in Crafty, the counters simply did not seem to represent much of anything numerically. This is quite a different result from when Schaeffer first defined the history heuristic for move ordering based on 5 ply searches. The numbers look more sensible there since the tree is very small. Today's trees are 25 plies and deeper depending on time control. The numbers become much more muddled / random under that condition.

ok. This makes sense. When I tried different depth and threshold for this type of pruning in Minic the results were not changing a lot.
Maybe indexing history score by ply can help ? Would make it a bigger table but at least only ply +/- 6 can be taken into account for pruning (and sorting ?)

[bob]

The risk would be cache. IE how big a history table? Most use 4K entries (6 bit from, 6 bit to, to form the index). If you limit depth to 64 plies, 64 * 4K is right big, and you will access different parts of it which is going to have an impact. Will it work? Unknown. Is that "too local" (since the original history heuristic was like a "super killer" list of moves that could be used at any ply in the tree equally.) This might be too restrictive. Would take testing to reach a conclusion.

[fabianVDW]

If you try the history scores indexed by ply, let me know how this worked out for you Vivien, this has been on my "Try THIS" list for along time now and I haven't come around to do it...

But hearing what bob has said maybe it would be more sensible to have history scores indexed by subtree, but this is obviously non trivial. I thought a bit about how to do that, but I don't yet like what I've come up with:
You would need another datastructure also saving the subtree size for each node which have their own history scores(for itself and its subtrees). Let's say in the beginning only the root has clean history scores(0 everywhere). We measure its subtree size again and again and udpate it. If the subtrees at some point exceed a certain size(lets artificially say 1M nodes here), we split up the scores to the root's childs, so every child now manages their own and seperate history scores. I wrote some pseudocde of how to do it in an alpha-beta search, disregarding everything else of the search:

Code: Select all

constant MAXIMUM_HISTORY_SUBTREE_SIZE = 1_000_000;

function alphabeta(..., game_state, history_owner_hash: 64Bit){
	//In the beginning, we would only make root an owner
	node_is_owner = game_state.hash == history_owner_hash;
	history_scores, old_subtree_size = history_table.get(history_owner_hash); //Here one has to make sure that entries in the history table can't be overriden. Maybe a binary search tree or B-Tree can make this cost low
	//***************
	//Use history scores in anyway you need them here
	//***************
	
	subtree_sizes = [1];//Count the current node aswell :)
	for move in available_moves{
		next_state = makemove(game_state, move);
		history_owner = if old_subtree_size > MAXIMUM_HISTORY_SUBTREE_SIZE{ next_state.hash } else{ history_owner_hash }; //If the old subtree size exceeds the threshold, this indicates that the child node itself is owner of a history table
		..., subtree_size = alphabeta(..., next_state, history_owner);
		subtree_sizes.append(subtree_size);
	}
	//****************
	//Update history scores as you normally would here
	//****************
	
	if node_is_owner and subtree_sizes.sum() > MAXIMUM_HISTORY_SUBTREE_SIZE and old_subtree_size <= MAXIMUM_HISTORY_SUBTREE_SIZE{
		//Split history tables up
		for (index, move) in available_moves.iterate().enumerate() {
			next_state = makemove(game_state, move);
			history_table.insert(next_state.hash, subtree_sizes[index].min(MAXIMUM_HISTORY_SUBTREE_SIZE), history_scores); // The min is there that if a child exceeds the threshold by it's own, we need to trick the system into thinking that it hasn't split the tables in the node up yet.
			//The old history scores are also given, we can use these as initial value for the child (maybe divide by 8 or so)
		}
	}
	
	if node_is_owner{
		history_table.update(history_owner_hash, updated_nodes);
	}
	
	return (..., subtree_sizes.sum());
}

"..." means that obvious search stuff has been left out in the pseudocode.

This implementation still leaves some questions... After the history scores of a node have been distributed into its childs, what happens to the node itself? This node then gets history scores all for itself... It should use the history scores of its parent again. Obviously this implementation also disregards the fact that certain subtrees might match with their opinion of history scores of a move until they are relativly big(say 100M), while others strongly disagree already when they are only 0.5M nodes big.

The proposed structure allows for saving even more info than history scores about certain subtrees. I think ideas into that direction have not been explored as widely, at least not as far as I have heard of. Also im not sure if it is worth investing more time into such ideas

[xr_a_y]

Well it was easy to implement, so I tried it yesterday. This was not a success.
I try to accumlate history by ply with a bandwidth of +/-2 6 10 and 20 ply.
I also try different sum strategies to aggregate history from various ply.

Nothing seems to be good, and some were really really bad.
Of course this was tested probably too quickly, so that others may give it a try also.

[xr_a_y]

If you try the history scores indexed by ply, let me know how this worked out for you Vivien, this has been on my "Try THIS" list for along time now and I haven't come around to do it...

But hearing what bob has said maybe it would be more sensible to have history scores indexed by subtree, but this is obviously non trivial. I thought a bit about how to do that, but I don't yet like what I've come up with:
You would need another datastructure also saving the subtree size for each node which have their own history scores(for itself and its subtrees). Let's say in the beginning only the root has clean history scores(0 everywhere). We measure its subtree size again and again and udpate it. If the subtrees at some point exceed a certain size(lets artificially say 1M nodes here), we split up the scores to the root's childs, so every child now manages their own and seperate history scores. I wrote some pseudocde of how to do it in an alpha-beta search, disregarding everything else of the search:

Code: Select all

constant MAXIMUM_HISTORY_SUBTREE_SIZE = 1_000_000;

function alphabeta(..., game_state, history_owner_hash: 64Bit){
	//In the beginning, we would only make root an owner
	node_is_owner = game_state.hash == history_owner_hash;
	history_scores, old_subtree_size = history_table.get(history_owner_hash); //Here one has to make sure that entries in the history table can't be overriden. Maybe a binary search tree or B-Tree can make this cost low
	//***************
	//Use history scores in anyway you need them here
	//***************
	
	subtree_sizes = [1];//Count the current node aswell :)
	for move in available_moves{
		next_state = makemove(game_state, move);
		history_owner = if old_subtree_size > MAXIMUM_HISTORY_SUBTREE_SIZE{ next_state.hash } else{ history_owner_hash }; //If the old subtree size exceeds the threshold, this indicates that the child node itself is owner of a history table
		..., subtree_size = alphabeta(..., next_state, history_owner);
		subtree_sizes.append(subtree_size);
	}
	//****************
	//Update history scores as you normally would here
	//****************
	
	if node_is_owner and subtree_sizes.sum() > MAXIMUM_HISTORY_SUBTREE_SIZE and old_subtree_size <= MAXIMUM_HISTORY_SUBTREE_SIZE{
		//Split history tables up
		for (index, move) in available_moves.iterate().enumerate() {
			next_state = makemove(game_state, move);
			history_table.insert(next_state.hash, subtree_sizes[index].min(MAXIMUM_HISTORY_SUBTREE_SIZE), history_scores); // The min is there that if a child exceeds the threshold by it's own, we need to trick the system into thinking that it hasn't split the tables in the node up yet.
			//The old history scores are also given, we can use these as initial value for the child (maybe divide by 8 or so)
		}
	}
	
	if node_is_owner{
		history_table.update(history_owner_hash, updated_nodes);
	}
	
	return (..., subtree_sizes.sum());
}

"..." means that obvious search stuff has been left out in the pseudocode.

This implementation still leaves some questions... After the history scores of a node have been distributed into its childs, what happens to the node itself? This node then gets history scores all for itself... It should use the history scores of its parent again. Obviously this implementation also disregards the fact that certain subtrees might match with their opinion of history scores of a move until they are relativly big(say 100M), while others strongly disagree already when they are only 0.5M nodes big.

The proposed structure allows for saving even more info than history scores about certain subtrees. I think ideas into that direction have not been explored as widely, at least not as far as I have heard of. Also im not sure if it is worth investing more time into such ideas

Indeed, my next idea is also to somehow apply an "aging method" to the history score but again I feel like I will need to store too much data.

[Michel]

If you try the history scores indexed by ply, let me know how this worked out for you Vivien, this has been on my "Try THIS" list for along time now and I haven't come around to do it...

But hearing what bob has said maybe it would be more sensible to have history scores indexed by subtree, but this is obviously non trivial. I thought a bit about how to do that, but I don't yet like what I've come up with:
You would need another datastructure also saving the subtree size for each node which have their own history scores(for itself and its subtrees). Let's say in the beginning only the root has clean history scores(0 everywhere). We measure its subtree size again and again and udpate it. If the subtrees at some point exceed a certain size(lets artificially say 1M nodes here), we split up the scores to the root's childs, so every child now manages their own and seperate history scores. I wrote some pseudocde of how to do it in an alpha-beta search, disregarding everything else of the search:

Code: Select all

constant MAXIMUM_HISTORY_SUBTREE_SIZE = 1_000_000;

function alphabeta(..., game_state, history_owner_hash: 64Bit){
	//In the beginning, we would only make root an owner
	node_is_owner = game_state.hash == history_owner_hash;
	history_scores, old_subtree_size = history_table.get(history_owner_hash); //Here one has to make sure that entries in the history table can't be overriden. Maybe a binary search tree or B-Tree can make this cost low
	//***************
	//Use history scores in anyway you need them here
	//***************
	
	subtree_sizes = [1];//Count the current node aswell :)
	for move in available_moves{
		next_state = makemove(game_state, move);
		history_owner = if old_subtree_size > MAXIMUM_HISTORY_SUBTREE_SIZE{ next_state.hash } else{ history_owner_hash }; //If the old subtree size exceeds the threshold, this indicates that the child node itself is owner of a history table
		..., subtree_size = alphabeta(..., next_state, history_owner);
		subtree_sizes.append(subtree_size);
	}
	//****************
	//Update history scores as you normally would here
	//****************
	
	if node_is_owner and subtree_sizes.sum() > MAXIMUM_HISTORY_SUBTREE_SIZE and old_subtree_size <= MAXIMUM_HISTORY_SUBTREE_SIZE{
		//Split history tables up
		for (index, move) in available_moves.iterate().enumerate() {
			next_state = makemove(game_state, move);
			history_table.insert(next_state.hash, subtree_sizes[index].min(MAXIMUM_HISTORY_SUBTREE_SIZE), history_scores); // The min is there that if a child exceeds the threshold by it's own, we need to trick the system into thinking that it hasn't split the tables in the node up yet.
			//The old history scores are also given, we can use these as initial value for the child (maybe divide by 8 or so)
		}
	}
	
	if node_is_owner{
		history_table.update(history_owner_hash, updated_nodes);
	}
	
	return (..., subtree_sizes.sum());
}

"..." means that obvious search stuff has been left out in the pseudocode.

This implementation still leaves some questions... After the history scores of a node have been distributed into its childs, what happens to the node itself? This node then gets history scores all for itself... It should use the history scores of its parent again. Obviously this implementation also disregards the fact that certain subtrees might match with their opinion of history scores of a move until they are relativly big(say 100M), while others strongly disagree already when they are only 0.5M nodes big.

The proposed structure allows for saving even more info than history scores about certain subtrees. I think ideas into that direction have not been explored as widely, at least not as far as I have heard of. Also im not sure if it is worth investing more time into such ideas

Indeed, my next idea is also to somehow apply an "aging method" to the history score but again I feel like I will need to store too much data.

Have a look at Stockfish. SF gets large amounts of elo by gathering statistics (including history) during search and using it to guide move ordering.

[xr_a_y]

Have a look at Stockfish. SF gets large amounts of elo by gathering statistics (including history) during search and using it to guide move ordering.

I often look at stockfish but I must admit that history part isn't clear to me for now ...