Feike Boomstra 's Horizon Draughts Program

[Ed Gilbert]

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

Code:
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]

Joost, I think you are right!

-- Ed

[Ed Gilbert]

Bert,

I'll bet if you delete the pruning, and apply the symmetry bug fixes, then rerun your engine match against horizon you will find that horizon is noticeably improved.

-- Ed

[BertTuyt]

Yes it is easier to write it this way.
I removed all the comments lines out of the routine (and or the code no longer used), see below.
Maybe the if (result < 0) result = -result; part was also intended to be left out...

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_MAX_NODE) {
		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)));
		}
/*	}
	else { // min node
		if (node->status & IS_WHITE_ON_MOVE) {
			result = ((node->nr_of_white_man -  node->nr_of_black_man) + 3*(node->nr_of_white_king - node->nr_of_black_king));
		}
		else { // black on move
			result = ((node->nr_of_black_man -  node->nr_of_white_man) + 3*(node->nr_of_black_king - node->nr_of_white_king));
		}

	}
*/
	if (result < 0) result = -result;
	return result;
}

If you have a clue, please let me know........
By the way: in the part commented out (basically Feike made a difference when he started with the design of this function between min and max nodes, and also used in the min-node formula a 3* for the kings !!

Bert

[BertTuyt]

Ed, you are right.

I see also 3 (small) improvements possible:

* Correct symmetry bugs in the eval functions.
* Apply interior node-recognition for DB-positions.
* Implement correct pruning.

* Something more complicated is a lazy-eval (but can not quantify what this will do).

* And something not related to improvement, but I am in favor (in line with your thoughts) to remove the DB-part from the eval (and especially when you do interior node-recognition, the DB-part from the eval will most likely be never addressed).......

What is your ideas, do you see more low hanging fruit already??

Bert

[Ed Gilbert]

Code: Select all

* Correct symmetry bugs in the eval functions.
* Apply interior node-recognition for DB-positions.
* Implement correct pruning.

* Something more complicated is a lazy-eval (but can not quantify what this will do).

* And something not related to improvement, but I am in favor (in line with your thoughts) to remove the DB-part from the eval (and especially when you do interior node-recognition, the DB-part from the eval will most likely be never addressed).......

What is your ideas, do you see more low hanging fruit already??

Bert, I guess this depends on what your goals are. If your goal is to make horizon as strong as you can with not too much effort then those are reasonable things to do. I only looked at fixing bugs and did not consider adding anything new.

I do not use lazy eval in kingsrow. I played with it years ago and it was only a minor speedup, but caused some other difficulties so for me it was not worth the trouble. It might work better in horizon since its full eval is so detailed.

-- Ed

[TAILLE]

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

We all know that depth-reduction (pruning is only particular case of epth reduction) is a key element of a search algorithm. The criteria for a depth reduction have then to be anaysed in detail. In Damy I applied the two following main principles :
1) First of all I want to avoid to do a depth-reduction when the position may be on the path of a combinaison => the depth-reduction can only occur when the side on move has an certain advantage.
2) Because the purpose of a depth-reduction is to save CPU-time it is interesting to do such reduction as much as possible. With an advantage of 5 men you will always make a great depth-reduction but what about an advantage of one man or 0,5 man or etc.? If you improve the reliablity of your evaluation function then you can probably accept to do a depth-reduction with a rather small advantage. Seeing this I chose to avoid any "lazy evaluation". My choice was to try and build a "strong evaluation" which is able to detect the most sensible aspects of a position (in particular "potential promotion" and "weak voorpost"). In other words my choice was to "lose" time in the evaluation function in order to "win" more time in the search by an efficient depth-reduction.

[BertTuyt]

Gerard,

interesting.
Do you think that a program with the best search-routine and relying only on a perfect voorpost and potential promotion (breakthrough) function, would play far better then a program with additional eval information??

I think that specific draughts knowledge might be of little/no-use when the program is able to detect any combination pattern.
Sometimes you read in Draughts textbook that a specific position is not preferable due to the thread of all kind of combinations, which for computer Draughts program is not an issue.....
What do you think is the value of things like KVO, LVO (korte -lange vleugel opsluiting, .... ) In English locked left or right wings etc...

Bert

[BertTuyt]

Ed,

did you already post me your recent updates of the eval (voorpost) function, then I will include them into the recent Horizon version.

Bert

[Ed Gilbert]

Bert, you have them. See my email sent 1/7/2011 (maybe 1/8 your time) subject "Horizon bug fixes".

-- Ed

[TAILLE]

Gerard,

interesting.
Do you think that a program with the best search-routine and relying only on a perfect voorpost and potential promotion (breakthrough) function, would play far better then a program with additional eval information??

I think that specific draughts knowledge might be of little/no-use when the program is able to detect any combination pattern.
Sometimes you read in Draughts textbook that a specific position is not preferable due to the thread of all kind of combinations, which for computer Draughts program is not an issue.....
What do you think is the value of things like KVO, LVO (korte -lange vleugel opsluiting, .... ) In English locked left or right wings etc...

Bert

A program with the best search-routine and a perfect voorpost and potential promotion function will be very very strong but I think it will be far better with an additional eval information on condition this additional eval information is used efficiently.
The point is the following : as soon as you detect a voorpost or a potential promotion then all other elements in the position are certainly almost negligeable in the evaluation of the position and it could be a good idea to simply ignore this additional eval information (that's not a lazy evaluation : the additional information simply brings almost nothing).
In position however where no voorpost nor potential promotion exist then the additional information becomes essential in order to try and obtain some advantages.
Concerning this additional information the most impotant point is to evaluate essentially the long term patterns like locked wing. I think you can easily ignore almost all short term pattern like tactical threats

[MichelG]

Gerard,

interesting.
Do you think that a program with the best search-routine and relying only on a perfect voorpost and potential promotion (breakthrough) function, would play far better then a program with additional eval information??

Last week i did a match for dragon between a version with and without its breakthrough function. I think the one with won 59%-41% of the score, so having a good breakthrough evaluation is very important. I doubt that relying only on that table would lead to a strong programm though.

Dragon has a big table of pre-calculated breakthough patterns for checkers in the last 5 rows.

What do you think is the value of things like KVO, LVO (korte -lange vleugel opsluiting, .... ) In English locked left or right wings etc...

Dragon doesn't use any of these patterns. I don't think they have much significance in computer play.

Michel

[BertTuyt]

Michel,

how much memory (and how many positions) does your breakthrough table consume (and did you introduce some type of compression).
What do you store in this DB, only the Boolean if a breakthrough is possible or the depth to promotion and the related material needed to get there (like 1 - 2 man sacrifice).
I also started with this approach but at that time I stopped as the table became to big (at that time i didn't have 12 GByte, and as I did not compress, and i stored both depth as material), and last but not least the index function was relatively heavy (in terms of computation time and complexity).

To all other programmers do you use a form of combination pattern Q-search?
My rational for doing do, if you include locked wing patterns (and alike), one can often escape but then a possible 1 - 2 shot is possible (so winning 1 man) for the opponent to move.
If you don't do this, the search score starts to oscillate (as the locked side wants to escape from the locked wing).

Bert

[MichelG]

Michel,

how much memory (and how many positions) does your breakthrough table consume (and did you introduce some type of compression).
What do you store in this DB, only the Boolean if a breakthrough is possible or the depth to promotion and the related material needed to get there (like 1 - 2 man sacrifice).
I also started with this approach but at that time I stopped as the table became to big (at that time i didn't have 12 GByte, and as I did not compress, and i stored both depth as material), and last but not least the index function was relatively heavy (in terms of computation time and complexity).
Bert

It was a long time ago when i build it. It's 100MB in size and covers 400 million positions with checkers on the last five rows. 400m is not enough to handle all such configurations (that would be an undoable 10^11 entries or so), but i think it covers 95+% of positions reached in gameplay.

I just store 1 bit for white breakthough, and 1 for black (whit white to move). In dragon at least, it's not very time consuming at about 1 or 2% cpu its well worth the time.

Computing the table took a few days though, but it was done ages ago.

Michel

[BertTuyt]

Michel, do you include only man ( so white and black) or also positions with kings ?

Bert

[jj]

Hi all,

My breakthrough table uses 2 bits per position: 00 = no breakthrough, 01 = win 1 man (else break), 10 = win 2 men (else break), 11 = win 3 or more men or a real break.
I only store positions with black (the defender) to move. To keep the index function simple I over-dimensioned the table to 20 (squares 6-25) x 2^25 (a 25-bit number containing the black pieces on squares 1-25, ghost bits removed) = 671.088.640 positions (of which 335.497.820 are legal). *2 bits /1 byte = 160 MB, no further compression (suggestions?). Kings are treated as men in the table, so these have to be checked independently if desired (how?). I also just use the current row (rank) of the man, rather than storing the number of moves before crowning.
Generating the table took 9 hours on my old laptop in '08; on my current MacBook it runs in 45 minutes.
Using the table seems to work pretty well in (al)most (all) cases for single men, at a low performance penalty. I agree that a good breakthrough function adds significantly to the playing strength of a program.

As for locked wings (LVO, KVO, etc.), in my experience at least some basic knowledge about this is required to avoid some obvious positional mistakes - or to punish a weaker opponent (like myself) for making them (after a shot). The same goes for the infamous Voorposten ("Outposts" in English?). This immediately saved many points in DXP matches in the "early days" of developing my program.
The question is as always how to score all of this. I like to have my own go at it first, before looking into Feike's material.

I don't have any search extensions yet. No combination pattern Q-search.
Is this what Truus and Flits do, and am I correct that Stef Keetman's thesis was about this? Is this text still available somewhere?
I've not investigated the oscillation effect yet, though I may have stumbled upon it when starting with MTD-f (>1000 iterations for one depth, is this what you mean Bert?).
My thoughts go along the lines of Gérard's for looking at a search algorithm and evaluation function.

No search extensions and pruning, next to no egdb, probably are the main weak spots of Maximus. Which one has the greater impact on middle/endgame play? I feel the lack of an opening book is less of a problem, but then there is the time saved by using one.

Jan-Jaap