Feike Boomstra 's Horizon Draughts Program

[TAILLE]

I fixed the symmetry bugs in the voorpost eval. Horizon evaluates a voorpost formation in a similar way for the 6 advanced center squares. For black these are 27, 28, 29, 32, 33, and 34. For each square there are two functions, one for evaluating white attacks coming from the northeast direction and another from northwest. Take the example of a black voorpost on square 33. White can attack from the northeast direction by placing a backing man on 42 and an attacking man on 38. Similarly black can defend by placing a backing man on 20 and a defending man on 24. The voorpost evaluations do not consider the case where there is a backing black man on 29. It only evaluates the cases where the white attacks can result in one or more exchanges of the voorpost square. The basic idea of the eval is to count both the number of potential white attacking and black defending men, as well as the number of moves required to attain the attacking and defensive positions for the first and second waves of attacks.

For a black voorpost on 33 the candidates for a white backing man are the set {42, 47, 48}, and for the white attacking man they are {38, 43, 48, 49}. The code below identifies a backing and attacking white man and returns the number of plies required to achieve these positions.

Code: Select all

his_min_backing_steps = calc_dist_2((FLD43), (FLD48 | FLD49), &his_pieces_used, white_man);
his_min_attack_steps = calc_dist_3((FLD39), (FLD44), (FLD49 | FLD50), &his_pieces_used, white_man);

The function keeps track of which white men are used in the bitboard his_pieces_used, so that once it assigns a man to be used for backing it does not also use it for attacking.

Notice that there is a bit of overlap in the sets of backing and attacking. It is important that in identifying a backing man the priority should be to check 43 first, then 48, and 49 last. If 49 was checked before 48, then there is a potential for error because 49 can be used either for backing or attacking where 48 can only be used for backing. This is the source of the bug, because the same calc_dist_x functions are used not only for attacks from the northeast, but also for those from the northwest, and also for identifying defending pieces in the southeast and southwest directions. The calc_dist functions always search the bitboards starting at the lowest bit numbers first. This doesn't work for the case of white attacks from the northwest, as there the white backing set is {44, 49, 50}, attack set is {39, 43, 48, 49}, and 50 should be considered for backing before 49. It is also incorrect for identifying black defensive backing men from the southwest.

To fix the bugs, I wrote a similar set of calc_dist_x functions that search the bitboard sets in the opposite direction, i.e. starting at msb and advancing towards lsb, and then substituted calls to the new functions for the appropriate directions. The horizon eval now passes all symmetry tests.

-- Ed

The Horizon evaluation for voorpost you describe above looks like the evaluation I had in Damy some years ago. Then I completly changed my mind because regularly I was facing a very bad evaluation in very common situations like the following :


where some other white and black men have to be added.

The black voorpost seems very strong when considering potential attacks and defenses but any human body will tell you it is indeed very weak and black will probably lose this voorpost more or less quickly.
This kind of position may happen with almost all voorpost and it would be a pity to miss this point.

[Ed Gilbert]

Hi Gerard,

Is your point that 1) the horizon voorpost eval is not complete enough because it does not consider enough context to see the shot in your example, or 2) the horizon eval tries to do too much, which will never be completely successful because of tactical considerations which are beyond the scope of even the most comprehensive eval? If your point is 2) then I agree. There are 2 C source files in horizon dedicated to evaluating voorpost squares. In total it is about 6000 lines of code. In comparison, the kingsrow sources for voorpost squares is less than 100 lines. I think I get a good percentage of the benefit for a tiny percentage of the horizon cost.

-- Ed

[TAILLE]

Hi Gerard,

Is your point that 1) the horizon voorpost eval is not complete enough because it does not consider enough context to see the shot in your example, or 2) the horizon eval tries to do too much, which will never be completely successful because of tactical considerations which are beyond the scope of even the most comprehensive eval? If your point is 2) then I agree. There are 2 C source files in horizon dedicated to evaluating voorpost squares. In total it is about 6000 lines of code. In comparison, the kingsrow sources for voorpost squares is less than 100 lines. I think I get a good percentage of the benefit for a tiny percentage of the horizon cost.

-- Ed

My view is that the horizon voorpost eval might not have the most efficient size. It is either too much or not complete enough. Surely Feike planned to continue to work on this point. In Damy the number of lines is far less than Horizon figure because I prefered to developped a special extension in order to know if a voorpost is weak or not.

[BertTuyt]

I have now finished the match Damage - Horizon.
In total 158 games were played, with 10 minutes for every program.
End result (from the perspective of Damage) 25+ 5- 128=
The 5 games won by Horizon are 45, 68, 125, 139 and 144.

Attached ( for those who are interested) all the games played ( in .pdn).
Think the match was interesting for both programs, with mutual learning opportunities.

Bert

[BertTuyt]

As already mentioned in a previous message, the tnode structure is a key element in the Horizon architecture.

Code: Select all

struct tnode {
	unsigned long long man_king;				// bit array [0..] man = 1 king = 0
	unsigned long long white_black;				// bit array [0..] white = 1 black = 0
	unsigned long long occ_empty;				// bit array [0..] occupied = 1 empty = 0
	unsigned int hash_key;						// the hash key related to the board position
	unsigned short int status;
	unsigned char nr_of_white_man;
	unsigned char nr_of_black_man;
	unsigned char nr_of_white_king;
	unsigned char nr_of_black_king;
	unsigned char total_nr_of_pieces;
	char depth;									// debug
	struct tnode *previous_node;
};

The (unsigned int ) hashkey is based on the Zobrist method.
Horizon uses a 32-bit key, maybe to avoid hash-collisions it is better to switch to a 64bit implementation (at least Damage uses a 64bit int, I'm not sure what other program use these days).
The Zobrist method is based on the Xor of all the piece-type position-index, on the Draughts board.
See init code below:

Code: Select all

long calc_initial_hash_key(NodePnt node)
{	
	register long temp;
	register BitArray cur_bit;
	int i,j;

	if (node->status & IS_WHITE_ON_MOVE) temp = WHITE_HASH;
	else temp = 0;

	for (j=0; j<50; j++) {	
		
		i = ext_to_int[j+1];
		cur_bit = bits[i];

		if (node->occ_empty & cur_bit) {				// true means occupied
		
			if (node->man_king& cur_bit) {				// true means a man
			
				if (node->white_black & cur_bit)		// true means white
					temp = temp ^ white_man_hash[i];
				else
					temp = temp ^ black_man_hash[i];

			} else {	
				
				if (node->white_black & cur_bit)		// true means white
					temp = temp ^ white_king_hash[i];
				else
					temp = temp ^ black_king_hash[i];
			}
		}
	}

	return temp;
}

Also after each move the hash-key is updated by the populate_node() function ( void populate_node(WsPnt ws, NodePnt node, int idx, NodePnt prev_node) ).
To my knowledge is Kingsrow the only program which does not have an incremental hash-key, but uses a somewhat different function (Ed hope I'm right here).

The program has a hash table of 64 MByte ( HASH_ARRAY_SIZE 0x4000000 ) entries.
Each entry is a hash_node structure, described by:

Code: Select all

struct hash_node {
	unsigned long long man_king;				// bit array [0..] man = 1 king = 0
	unsigned long long white_black;				// bit array [0..] white = 1 black = 0
	unsigned long long occ_empty;				// bit array [0..] occupied = 1 empty = 0
	short int upperbound;						// upperbound used in alphabeta pruning
	short int lowerbound;						// lowerbound used in alphabeta pruning
	short int distance_from_root;
	unsigned short int status;
	short int search_depth;
	unsigned char best_move_idx;				// the best move from a previous search depth
	char depth;									// debug

};

By storing all the relevant bitfields, one has a certainty if the hash-entry belongs to a specific Board position. The drawback of this memory-intensive approach (1 hash_node = 36 Bytes) is the total size of the hash-table (more then 2 GByte).
The parallel search shares the hash table with all search-threads. To avoid hash table collision contamination Horizon uses multiple locks (as the use of only 1 lock will have a dramatic impact on search-efficiency). In Damage this potential problem is bypassed by using the suggestion of Bob Hyat (author chess-engine Crafty, see "A lock-less transposition table implementation for parallel search chess engines")
The multiple hash-lock method is depicted below:

Code: Select all

hash_lock_grab(&hash_lock[node->hash_key & LOCK_MASK]);

Here the parameter LOCK_MASK is defined as; #define LOCK_MASK LOCK_ARRAY_SIZE - 1 , and LOCK_ARRAY_SIZE is defined as: #define LOCK_ARRAY_SIZE 0x100

Bert

[TAILLE]

Hi,

By storing all the relevant bitfields, one has a certainty if the hash-entry belongs to a specific Board position. The drawback of this memory-intensive approach (1 hash_node = 36 Bytes) is the total size of the hash-table (more then 2 GByte).
The parallel search shares the hash table with all search-threads. To avoid hash table collision contamination Horizon uses multiple locks (as the use of only 1 lock will have a dramatic impact on search-efficiency). In Damage this potential problem is bypassed by using the suggestion of Bob Hyat (author chess-engine Crafty, see "A lock-less transposition table implementation for parallel search chess engines")
The multiple hash-lock method is depicted below:
Bert

In Damy a hash entry has a 24 bytes size and, as Bert, I use a lock-less transposition table implementation.

I do not quite understand why Feike decided to store the distance_from_root in the hash. Do somebody has an idea ?

[Rein Halbersma]

Hi,

By storing all the relevant bitfields, one has a certainty if the hash-entry belongs to a specific Board position. The drawback of this memory-intensive approach (1 hash_node = 36 Bytes) is the total size of the hash-table (more then 2 GByte).
The parallel search shares the hash table with all search-threads. To avoid hash table collision contamination Horizon uses multiple locks (as the use of only 1 lock will have a dramatic impact on search-efficiency). In Damage this potential problem is bypassed by using the suggestion of Bob Hyat (author chess-engine Crafty, see "A lock-less transposition table implementation for parallel search chess engines")
The multiple hash-lock method is depicted below:
Bert

In Damy a hash entry has a 24 bytes size and, as Bert, I use a lock-less transposition table implementation.

I do not quite understand why Feike decided to store the distance_from_root in the hash. Do somebody has an idea ?

In <Mistral> I have 8-byte hash entries, consisting of a 32-bit hash signature, a 16-bit signed integer for the score, and an unsigned 16-bit integer for the node type, search depth and index of the best move in the list of all moves. I do have 64-bit hash keys, but only store the upper 32-bits as signature.

Perhaps Feike used distance_to_root as an ageing field to overwrite old entries, but that explanation only makes sense if distance_to_root means distance to the initial position of the game, not the initial position of the search. I should look at the code to see what is being done.

I think it is a big advantage to have a hash entry that fits into a 64-byte cache line. Remember, most hash entry lookups come from main memory and are not already present in the cache. I have organized my hash key as an array of buckets, where each bucket is an array of 8 hash entries. Whenever I do a hash lookup, an entire bucket is loaded into a single cache line. I then loop over the bucket to find the entry. Having 36-byte or 24-byte entries is a bit expensive as you can have hash entries straddling cache lines. Making the entries 32-bytes would allow you to load buckets of 2 entries at the same time.

Rein

[MichelG]

I fixed the symmetry bugs in the voorpost eval.
-- Ed

One should ask why the symmetry bugs exists in the first place; the entire eval function is coded twice, for black and for white. Do you think the small performance gain is worth that effort?

Dragon only evaluates from white's point of view, the reverses the position, calls the same code and subtracts the value for black. No symmetry bugs exist this way, and the code is a lot easier and faster to maintain, for only the cost of about 2% speed.

Michel

[Ed Gilbert]

Dragon only evaluates from white's point of view, the reverses the position, calls the same code and subtracts the value for black. No symmetry bugs exist this way, and the code is a lot easier and faster to maintain, for only the cost of about 2% speed.

That is a reasonable way to solve the problem. You can also do what Rein does, using templated functions that reverse the eval logic at compile time.

-- Ed

[BertTuyt]

Rein, you are right!!

Perhaps Feike used distance_to_root as an ageing field to overwrite old entries, but that explanation only makes sense if distance_to_root means distance to the initial position of the game, not the initial position of the search. I should look at the code to see what is being done.

See the next code within Horizon:

Code: Select all

g = search(root, beta-1, beta, current_ply_nr, depth, 0, true);

short int search(NodePnt node, int alpha, int beta, int distance_from_root, int depth, int ThreadID, bool pv)

The curent_ply_nr starts at the root with 0, after every move (white/black) this parameter is incremented with 1.

Another example is the function which calculates the maximum search-depth obtained (although the function name is somewhat misleading).

Code: Select all

unsigned int get_max_distance_from_root(void) 
{
	unsigned int result = 0;

	for(int i = 0; i < ActiveThreads; i++)
		if (Threads[i].max_distance_from_root > result) result = Threads[i].max_distance_from_root;

	return result - current_ply_nr;

}

Bert

[BertTuyt]

Below the code Horizon uses for cycle-detection ( = loop).
I tested this on the famous example from Gerard, but here also hash-tables seems to block recognition.

Code: Select all

int check_nodes(NodePnt node1, NodePnt node2)
{
	if (node1->hash_key    != node2->hash_key)    return 0;
	if (node1->occ_empty   != node2->occ_empty)   return 0;
	if (node1->man_king    != node2->man_king)    return 0;
	if (node1->white_black != node2->white_black) return 0;

	return 1;
}


int is_cycle(NodePnt node)
{	
	NodePnt compare_node = node;

	if (!(node->status & IS_CYCLE_POSSIBLE)) return 0;

	while (1)
	{	
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-1
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-2
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-3
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-4
		if (check_nodes(node, compare_node)) return 1;
	}
}

Bert

[BertTuyt]

Maybe interesting, an overview of all the status bits in the tnode structure (node->status).

Code: Select all

#define IS_WHITE_ON_MOVE 0x1                   // the color of the next move in this position, WHITE = 1, BLACK = 0
#define IS_MAX_NODE 0x2                        // the nature of the node: MAX_NODE = 1, MIN_NODE = 0
#define IS_EVALUATED 0x4                       // is the node allready evaluated
#define IS_USELESS_SACRIFICE 0x8               // too much losses
#define IS_NOT_IN_HASH 0x10                    // node is not found in the hash (anymore)
#define IS_EXACT_VALUE 0x20                    // evaluation value is coming from the endgame database
#define IS_CYCLE_POSSIBLE 0x40                 // both sides a king and no move done with man
#define IS_JUST_PROMOTED 0x80                  // color on move promoted in this ply
#define IS_EXTENDED 0x100                      // is extended in this branch
#define HAS_EXTENSION_CONDITION 0x200          // to signal extension condition appearing for the first time
#define IS_QUIESCENCE 0x400
#define HAD_TO_CAPTURE 0x800
#define HAD_ONCE_A_WHITE_KING 0x1000
#define HAD_ONCE_A_BLACK_KING 0x2000

Bert

[TAILLE]

Below the code Horizon uses for cycle-detection ( = loop).
I tested this on the famous example from Gerard, but here also hash-tables seems to block recognition.

Code: Select all

int check_nodes(NodePnt node1, NodePnt node2)
{
	if (node1->hash_key    != node2->hash_key)    return 0;
	if (node1->occ_empty   != node2->occ_empty)   return 0;
	if (node1->man_king    != node2->man_king)    return 0;
	if (node1->white_black != node2->white_black) return 0;

	return 1;
}


int is_cycle(NodePnt node)
{	
	NodePnt compare_node = node;

	if (!(node->status & IS_CYCLE_POSSIBLE)) return 0;

	while (1)
	{	
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-1
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-2
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-3
		compare_node = compare_node->previous_node; if (compare_node == NULL) return 0;
		if (!(compare_node->status & IS_CYCLE_POSSIBLE)) return 0; //-4
		if (check_nodes(node, compare_node)) return 1;
	}
}

Bert

Seeing this code and what I made in Damy I suspect Feike did not want to resolve my so called "famous example" but wanted only to solve the GHI problem. Maybe further analysis will show what was realy Feike's goal.

[BertTuyt]

The Horizon search function is based on the MTD(f) algorithm (Aske Plaat).
Below is an first extract (the second part will be discussed in a later stage) of the AlphaBetaWithMemory function:

Code: Select all

// the mean search routine. Is called from mtdf.
short int search(NodePnt node, int alpha, int beta, int distance_from_root, int depth, int ThreadID, bool pv)
{	int g;
	int z;
	struct tnode next_node;
	struct work_space_move_generator ws;
	unsigned int next_move;

	int max_node = (node->status & IS_MAX_NODE);

	if (stop_flag)
		return 0;

	Threads[ThreadID].nr_of_nodes_visited++;

	// check whether node in hash, update best move according found or not
	if ((g = Node_in_Hash(node, alpha, beta, distance_from_root, &ws, ThreadID)))
		return g; // cutoff found in hash

	// check if node is part of a cycle
	if (is_cycle(node)) {	
		store_leaf_node(ThreadID, node, 1, 0, distance_from_root, IS_EVALUATED);
		return 1;  // return a draw
	}

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

Some observations/comments/remarks (so far):
* The Node_in_Hash(node, alpha, beta, distance_from_root, &ws, ThreadID) function does not forward alpha and beta as pointers, therefore the routine does not modify these parameters, which is a potential improvement (Note, how do you think about this?).

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

* Set Capture ( set_capture(&ws, node) ) sets the capture flag in ws and node->status

Code: Select all

void set_capture(WsPnt ws, NodePnt node)
{
	ws->capture = (ws->max_nr_of_captures > 0);
	if (ws->capture) node->status = node->status | HAD_TO_CAPTURE;
}

* The condition whether the search should be terminated ( if (depth <= material_to_depth_reduction(node)) { ) is a "sort of" Forward pruning Technique. I want to discuss this in part 2, as I'm still not sure if the implementation works and/or is logical sound (but as I can be wrong, I would like to hear your opinion ). Horizon does not use (at least I did not detect other mechanisms for depth reduction). I suspect this is maybe part of the search-inefficiency as Ed and I suspect, negatively impacts the strength of Horizon. Damage uses Fail High Reduction ( FHR, Feldmann), Multi Cut Pruning (MCP) and Late Move Reduction (LMR) .

* The steps to determine if the search should stop and/or a Quiscence-search should be started is detected through:

Code: Select all

	set_quiscence(&ws, node);

		if (ws.quiescence) {

This routine and the Material_to_depth_reduction is covered in Part 2.

* Bascically search-extenstions are also not (yet) implemented (altough some flags are set in the node-Status, but not (yet) used in the alphabeta.v.2.6.cpp file (altough in the earlier v2.5. file some attemps were made, therefore I get the impression that most likely the v.2.6. version was work in progress, and not yet fully developed !!)

End of Part I...

Bert

[Rein Halbersma]

The Horizon search function is based on the MTD(f) algorithm (Aske Plaat).
Below is an first extract (the second part will be discussed in a later stage) of the AlphaBetaWithMemory function:

Some observations/comments/remarks (so far):
* The Node_in_Hash(node, alpha, beta, distance_from_root, &ws, ThreadID) function does not forward alpha and beta as pointers, therefore the routine does not modify these parameters, which is a potential improvement (Note, how do you think about this?).

Bert

Bert,

In MTD-f you don't need to update alpha. Every move that raises alpha is automatically a cutoff because alpha = beta - 1 for all calls to the search. This is precisely one of the benefits cited on Aske Plaat's webpage.

Rein