Feike Boomstra 's Horizon Draughts Program
Re: Feike Boomstra 's Horizon Draughts Program
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 :Ed Gilbert wrote: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.
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.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);
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

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.
Gérard
-
- Posts: 802
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Re: Feike Boomstra 's Horizon Draughts Program
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
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
Re: Feike Boomstra 's Horizon Draughts Program
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.Ed Gilbert wrote: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
Gérard
Re: Feike Boomstra 's Horizon Draughts Program
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
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
- Attachments
-
- DXPMatch Damage Horizon January 2011.pdn
- Match Damage-Horizon January 2011
- (171.25 KiB) Downloaded 94 times
Re: Feike Boomstra 's Horizon Draughts Program
As already mentioned in a previous message, the tnode structure is a key element in the Horizon architecture.
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:
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:
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:
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
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;
};
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;
}
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
};
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]);
Bert
Re: Feike Boomstra 's Horizon Draughts Program
Hi,
I do not quite understand why Feike decided to store the distance_from_root in the hash. Do somebody has an idea ?
In Damy a hash entry has a 24 bytes size and, as Bert, I use a lock-less transposition table implementation.BertTuyt wrote: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
I do not quite understand why Feike decided to store the distance_from_root in the hash. Do somebody has an idea ?
Gérard
-
- Posts: 1690
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Feike Boomstra 's Horizon Draughts Program
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.TAILLE wrote:Hi,
In Damy a hash entry has a 24 bytes size and, as Bert, I use a lock-less transposition table implementation.BertTuyt wrote: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
I do not quite understand why Feike decided to store the distance_from_root in the hash. Do somebody has an idea ?
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
Re: Feike Boomstra 's Horizon Draughts Program
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?Ed Gilbert wrote:I fixed the symmetry bugs in the voorpost eval.
-- Ed
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
-
- Posts: 802
- Joined: Sat Apr 28, 2007 14:53
- Real name: Ed Gilbert
- Location: Morristown, NJ USA
- Contact:
Re: Feike Boomstra 's Horizon Draughts Program
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.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.
-- Ed
Re: Feike Boomstra 's Horizon Draughts Program
Rein, you are right!!
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).
Bert
See the next code within Horizon: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.
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)
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;
}
Re: Feike Boomstra 's Horizon Draughts Program
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.
Bert
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;
}
}
Re: Feike Boomstra 's Horizon Draughts Program
Maybe interesting, an overview of all the status bits in the tnode structure (node->status).
Bert
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
Re: Feike Boomstra 's Horizon Draughts Program
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 wrote: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.BertCode: 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; } }
Gérard
Re: Feike Boomstra 's Horizon Draughts Program
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?).
* 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
* 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:
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
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;
}
}
* 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 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) {
* 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
-
- Posts: 1690
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Feike Boomstra 's Horizon Draughts Program
Bert,BertTuyt wrote: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
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