Feike Boomstra 's Horizon Draughts Program

[Rein Halbersma]

But that detail aside, I think the code indicates that Horizon uses the copy-make approach to move generation both for the reversible and the irreversible parts of a position. But it also does not have an explicit array of hash keys to do repetition detection. Rather it uses an implicit array through pointer to the previous position.

This is also the way Don Dailey described how his CilkChess program (and its current program Komodo) works. Now we know of course that CilkChess was a very strong parallel program. Part of that was the ease of doing parallel computations by not maintaining a big global state but copying a small state and tracing history through pointers. The Cilkchess state was 192 bytes (3 cache lines) but I think the "tnode" struct of Horizon is even less than 64 bytes (single cache line!!) so the copy overhead should be a lot smaller than in a chess program. Although I have no idea how often (in % of number of move generated) a new thread is spawned, copying a big global state with a long history (several kilobytes?!) could easily be more expensive than the copy-make approach.

Rein

I've implemented Feike's data structure with a Position struct holding
all *current* state information (pieces/kings bitboards, color, hash
key, number of moves since last conversion, and some other counters)
and a pointer to the previous position. I've padded this struct to
make it exactly a 64 byte cache line. During a search, I copy this
struct into a new position, and then make the move on that copy. The
search is then called with a reference to this copy. Afterwards, there
is no undo at all. The perft numbers without bulk-counting show a
minor speed increase.

This data structure is exactly the same as in CilkChess. One big
advantage is that it it makes the search automatically re-entrant
compared to doing make/undo on a fixed position. There was some
discussion on Talkchess a year ago about copy-make vs make-undo. Bob
Hyatt was writing that the excessive copying could blow out the memory
bandwidth. At least with my single core P4 I don't have that problem.
For now, I think I'll keep this new data structure as it would also
remove a few hundred lines in my undo code.

Rein

[BertTuyt]

Rein,

in Damage I also use a copy-make approach.
I never did a detailed comparison with the alternative make-undo, but still I suspect that for me the copy-make is slightly faster.
But the main advantage is transparency, and it is makes life much easier for parallel search...

Bert

[BertTuyt]

Horizon Search, Part 2

Whether the search should be stopped (based on the search-depth compared with the material_to_depth function (which will be covered in Part 3), is determined by the quiescence condition (ws.quiescence) which is determined by set_quiscence(&ws, node); (see below code):

Code: Select all

set_quiscence(&ws, node);

		if (ws.quiescence) {
			g = evaluate(node, 0,0, ThreadID);
			store_leaf_node(ThreadID, node, g, 0, distance_from_root, IS_EVALUATED);

			return g;
		}

void set_quiscence(WsPnt ws, NodePnt node)
{
	bool other_side_ok;

	if (other_side_is_not_on_capture(node)) 
		other_side_ok = true;
	else 
		other_side_ok = false;

	if (more_or_equal_pieces(node)) {	
		
		if (node->total_nr_of_pieces > NR_OF_ENDGAME_PIECES)
			ws->quiescence = (other_side_ok && !(ws->capture));
		else
			ws->quiescence = (!(ws->capture));

	} else 
		
		ws->quiescence = !(ws->capture); // if this side is behind, don't extend the search

	if (ws->quiescence) 
		node->status = node->status | IS_QUIESCENCE;

	return;
}

The condition is relatively straightforward, the search will be terminated (so ws->quiescence = true) if the side to move does not have a capture (ws->capture), otherwise the search will be continued ( ws->quiescence = !(ws->capture); )

There is one exception, if the position is quiet from the perspective of the side to move AND the board position is not contained in the Endgame DB ( if (node->total_nr_of_pieces > NR_OF_ENDGAME_PIECES) AND the material-value difference of the node (from the perspective of the side to move) is greater then or equal compared with the material-value difference at the root THEN also the quiescence condition is determined by the other-side (capture or no capture) ws->quiescence = (other_side_ok && !(ws->capture));

* As the other_side_is_not_on_capture(node) function is "relatively" expensive it is better (from an optimisation point of view) to only call this function when the required condition is valid (in the present case other_side_is_not_on_capture() is called by default).

* The node contains all required information to decide on quiescence, and also the ws->quiescence is no-where else used outside this specific context, it is more elegant to only include node in the function header and return a quiescence boolean as function output.

* Horizon does not include a pattern-based quiescence search-extension mechanism (which is implemented in Damage).

Bert

[BertTuyt]

When you look into the Horizon Search-code you don't see a mechanism for interior DB-node recognition.

Code: Select all

	generate_legal_moves(node, &ws, node->status & IS_WHITE_ON_MOVE, ws.best_move);			// all legal moves collected in ws

	if (ws.nr_of_legal_moves == 0)				     // we are done in this branch
	{
		if (max_node)
			g = -INFINITY + 1;						// that's a pity, no more moves
		else
			g = +INFINITY -1;						// that's fine, opponent has no more moves
		store_leaf_node(ThreadID, node, g, 0, distance_from_root, IS_EVALUATED);

		return g;
	}

	set_capture(&ws, node);

	if (depth <= material_to_depth_reduction(node)) {

		set_quiscence(&ws, node);

		if (ws.quiescence) {
			g = evaluate(node, 0,0, ThreadID);
			store_leaf_node(ThreadID, node, g, 0, distance_from_root, IS_EVALUATED);

			return g;
		}
	}

Bascially after the Movegenerator call and the check on the number of legal moves , one could add the check if the position is quiet for the side to move (as most compressed DB's dont store the capture positions), and if the total number of pieces is equal/below the NR_OF_ENDGAME_PIECES.
At least Damage has implemented this mechanism.
Im interested to learn if other Programs also include this option, and if one recognizes this as a possible improvement?

Bert

[Ed Gilbert]

Bascially after the Movegenerator call and the check on the number of legal moves , one could add the check if the position is quiet for the side to move (as most compressed DB's dont store the capture positions), and if the total number of pieces is equal/below the NR_OF_ENDGAME_PIECES.
At least Damage has implemented this mechanism.
Im interested to learn if other Programs also include this option, and if one recognizes this as a possible improvement?

Years ago when I first started using endgame dbs I did not probe at interior nodes, and kingrow's endgame play was noticeably poorer than Martin Fierz's cake program because of it. Martin explained this to me and then I started probing at interior nodes. This usually speeds up the search because you can often cutoff a branch right there and return a value.

-- Ed

[TAILLE]

Bascially after the Movegenerator call and the check on the number of legal moves , one could add the check if the position is quiet for the side to move (as most compressed DB's dont store the capture positions), and if the total number of pieces is equal/below the NR_OF_ENDGAME_PIECES.
At least Damage has implemented this mechanism.
Im interested to learn if other Programs also include this option, and if one recognizes this as a possible improvement?

Years ago when I first started using endgame dbs I did not probe at interior nodes, and kingrow's endgame play was noticeably poorer than Martin Fierz's cake program because of it. Martin explained this to me and then I started probing at interior nodes. This usually speeds up the search because you can often cutoff a branch right there and return a value.

-- Ed

In Damy I probe also at interior node and I go even farther. If for example I reach a node 5x5 pieces and a capture of 2 pieces has to be done I know for sure that this capture allow to reach the db. In that case I call the db interface which is able to use the move generator in order to solve a capture.

[Ed Gilbert]

Years ago when I first started using endgame dbs I did not probe at interior nodes, and kingrow's endgame play was noticeably poorer than Martin Fierz's cake program because of it. Martin explained this to me and then I started probing at interior nodes. This usually speeds up the search because you can often cutoff a branch right there and return a value.

I hit the submit button a little too quickly. I wanted to add that for db draw positions I return one of the special db draw values (+/-1, 3, or 5) based on the material imbalance. For db win or db loss I continue searching, as heuristics are needed to find the shortest path to win, or longest path to a loss.

-- Ed

[TAILLE]

* The Node_in_Hash function stores the best-move in ws (ws->best_move = hash[node->hash_key].best_move_idx; // save best move). There is no additional move ordering algorithm detected in Horizon (Note, Damage for example use the history-heuristics for move ordering, I'm interested in the options other programs use in addition

* Move ordering (based on the best move index ) is done is the MoveGenerator (generate_legal_moves(node, &ws, node->status & IS_WHITE_ON_MOVE, ws.best_move); // all legal moves collected in ws)

* Another option to use the Transposition table is Enhanced Transposition Cutoff ( ETC), which looks at the children of a node, which is implemented in Damage.
Bert

In Damy I initially used an additional ordering (based on the static evaluation of the children) but for the moment I removed this functionality because my new evaluation becomes very time consuming.
Concerning the best_move in the hash table, I used in Damy 64bits to store this best_move. I perfectly now that an index on 1 byte is largely enough but with my format I can generate the corresponding move wihtout calling the move generator.
Finally I use the ETC only in the high part of the tree (when it still remains about 7 plies).

[BertTuyt]

Gerard,

I don't do this (yet) in Damage, but is sounds like an effective approach.
I normally continue with the normal search when the position is not quiet.
But in case the number of pieces indicates that this is a DB position (independent if there is a capture or not), a "specific" DB-optimized search is most likely better (as the normal search goes through a garbage of overhead, you don't need in this case, like move ordering, .......... ).

Also based on a similar conversion I had with Ed, I'm thinking to remove the DB-routines out of the Evaluation function....

By the way, the average Horizon Evaluation function takes 0.77 uSec (on my 2.93 GHz i7).
Is this in line with your eval timing?
And last but not least, Horizon did not implement the lazy evaluation concept.
Do you do , and if not, whats is hen the rational?
As I think when the material-value is way outside the alpha-beta windows, and with the other eval elements you will not compensated, then full-evaluation does not make anysense...

Bert

[BertTuyt]

Gerard,

guess you set all bit positions which will change in 1 64-bit word (think we have discussed this in the past).
Only issue was that if the from and to fields are the same for the piece to move, then this information was lost (but for the search it does not matter, only for move display the pv information, or whatever)...

Concerning the best_move in the hash table, I used in Damy 64bits to store this best_move. I perfectly now that an index on 1 byte is largely enough but with my format I can generate the corresponding move without calling the move generator.

Bert

[TAILLE]

Gerard,

I don't do this (yet) in Damage, but is sounds like an effective approach.
I normally continue with the normal search when the position is not quiet.
But in case the number of pieces indicates that this is a DB position (independent if there is a capture or not), a "specific" DB-optimized search is most likely better (as the normal search goes through a garbage of overhead, you don't need in this case, like move ordering, .......... ).

Also based on a similar conversion I had with Ed, I'm thinking to remove the DB-routines out of the Evaluation function....

By the way, the average Horizon Evaluation function takes 0.77 uSec (on my 2.93 GHz i7).
Is this in line with your eval timing?
And last but not least, Horizon did not implement the lazy evaluation concept.
Do you do , and if not, whats is hen the rational?
As I think when the material-value is way outside the alpha-beta windows, and with the other eval elements you will not compensated, then full-evaluation does not make anysense...

Bert

When you are talking about an "average evaluation function time" I suspect you have in mind a "static" evaluation. Because the Damy evaluation is "dynamic" I am completly unable to answer your question.
Two specific points are really dynamic:
1) Evaluation of a potentiel promotion => specific recursive search algorithm to calculate effectively the distance to promotion
2) Evaluation of a voorpost (still in development) => specific recursive search algorithm to calculate if the voorpost is weak or not
As you see Damy evaluation is able to continue some search in addition to the "normal" search and then I cannot separate clearly the search and the evaluation.

[BertTuyt]

The decision to prune a branch in Horizon is based upon the next code:

Code: Select all

	if (depth <= material_to_depth_reduction(node)) {

Below the function material_to_depth_reduction() is listed:

Code: Select all

int material_to_depth_reduction(NodePnt node) {

	// used for the depth reduction.
	// the color on move must have the highest possible score, so depth_reduction should be big if score is low

	int result;

	if (node->status & IS_WHITE_ON_MOVE)
		result = (((node->nr_of_black_man -  node->nr_of_white_man) + (node->nr_of_black_king - node->nr_of_white_king)));
	else // black on move
		result = (((node->nr_of_white_man -  node->nr_of_black_man) + (node->nr_of_white_king - node->nr_of_black_king)));

	if (result < 0) result = -result;

	return result;
}

Here I strugle to understand the rational (Hope you will help me here)
So if there is a materal difference (and independant if this is positive/negative for the side to move, based on the next condition if (result < 0) result = -result;) then this will yield a pruning of the node near the end of the search-process ( if (depth <= material_to_depth_reduction(node)) { ). Also the "value" of a man and a king here is equal?

To my opinion pruning of a branch an/or reducing the search-depth should be based if one had a useless (and avoidable) sacrifice or one has initiated (also an avoidable) breakthrough (so free path for a man to promote to king) for the other player. A sacrifice which creates an own breakthrough is of course an advantage.
In de current algorithm (but i did not test this) im afraid that this will also reject combinations (or shots) near the end of the search variation , where one has sacrified several pieces , and then is prepared for the final kill. Due to the material imbalance, the material_to_depth_reduction() function will terminate the search in these cases too early.
Also if the material imbalance is already there from the root of the search, the condition remains valid through the search.

Again i could be wrong here, and I like your input, especially related to:
* Do you understand (and can you) explain the Horizon material_to_depth_reduction() method/principle?
* What is to your opinion the set of conditions to prune ( and/or reduce depth) for a specific move sequence in general (and/or what do you apply in your program)?

Bert

[Ed Gilbert]

Here I strugle to understand the rational (Hope you will help me here)
So if there is a materal difference (and independant if this is positive/negative for the side to move, based on the next condition if (result < 0) result = -result;) then this will yield a pruning of the node near the end of the search-process ( if (depth <= material_to_depth_reduction(node)) { ). Also the "value" of a man and a king here is equal?

Bert, I don't understand how this is supposed to work either. Usually pruning is based on the difference between the static evaluation and either alpha or beta. If static eval is much lower than alpha or much greater than beta, and the position is quiet, then one can consider pruning. This code looks like it could prune the PV if there was a material imbalance at the root position, based on the man and king counts.

-- Ed

[ildjarn]

Below the function material_to_depth_reduction() is listed:

Code: Select all

int material_to_depth_reduction(NodePnt node) {

	// used for the depth reduction.
	// the color on move must have the highest possible score, so depth_reduction should be big if score is low

	int result;

	if (node->status & IS_WHITE_ON_MOVE)
		result = (((node->nr_of_black_man -  node->nr_of_white_man) + (node->nr_of_black_king - node->nr_of_white_king)));
	else // black on move
		result = (((node->nr_of_white_man -  node->nr_of_black_man) + (node->nr_of_white_king - node->nr_of_black_king)));

	if (result < 0) result = -result;

	return result;
}

[Stupid question]
Isn't it easier to write this as

Code: Select all

int material_to_depth_reduction(NodePnt node) {
        return abs ((node->nr_of_black_man -  node->nr_of_white_man) + (node->nr_of_black_king - node->nr_of_white_king));
}

?
[/stupid question]

[BertTuyt]

Ed,

I feel the same. Based on a static evaluation of material difference in comparison with alpha and beta, is most likely a better approach for pruning.
In Damage I only compare with beta and a parallel condition should be that the other side to move does not have a breakthrough.
Do you use in Kingsrow both alpha and beta for comparison , and/or do you have other methods to identify a useless sacrifice?

But to make a long story short, I tend to believe the code is wrong here or incomplete.
When you go to the previous version of the routine (so version 2.5 in stead of version 2.6, which I used now) you see that this optimization is new for 2.6 and another approach was chosen in version 2.5 . I don't know if the recent version was work in progress, and even i don't know if there was already a "working " Horizon program based on the "new" search .
This routine (material_to_depth_reduction) was explicitly mentioned in the comments at the beginning of the file:

//V2.6 major change in stopping "weggevertje"
// this version implements depth reduction

Maybe Harm Jetten knows.
Anyway i guess i need to study the history of the other search routines (and also have a look at the original BoomstraDam files) to get a better understanding.
But at least here is an opportunity for improvement.

Bert