Feike Boomstra 's Horizon Draughts Program

[BertTuyt]

Gerard, think you "forgot" to add your specific remarks in your last post.

Bert

[TAILLE]

Gerard, i agree that in the end a base pattern could be surrounded by a huge nested if then else.
But I think our challenge is to use the computer more in finding these patterns, assign a score, and later cluster and categorize them.

I played already multiple 10Ply fixed depth search games, and when I add more evaluation elements, the games becomes every time more interesting.
It is a pity that we never (so far) really tried to use the computer itself to detect all these patterns.
In one of the games played in the last 2 days, i saw this pattern, which I very much liked.
With proper coding I guess the program should find these opportunities or threads (depends on which side yo are).



Bascially this is not a direct breakthrough, or a direct lock, but in a indirect way (and also based on the other man on the board in the actual game) the black man traps 2 white man.
So reducing actual mobility for white, and as a result black has 1 active man more to play with....

Bert

I see basically 2 key points linked together : the number of men involved and the mobility. What are the conditions to decide that a pattern is advantageous for a side. When I look at the previous examples I conclude at a disadvantage for a given side when both following conditions are fullfilled :
1) the concerned side has involved more men than the other side
2) All these men involded are more or less blocked : mobility default
It is essential to say that the side with the less number of men do not need mobility.

The challenge is then the following : to be able to detect that a given number of men are blocked with almost no mobility by a smaller number of opponent men.



In the above example, 3 black men (6, 16, 17) are "controled" by 2 white men (26, 27). Are these 3 black men "blocked" by the 2 white men ? This is crucial for evaluating the pattern. If black can add a man on 8 then the black pattern gain a lot of mobility and you cannot say that the considered 3 black men are blocked. If no black man can come on 8 square then the mobility of the 3 black men becomes very low and we can conclude at a white advantage (of course with no white man on 31 and 36)

[BertTuyt]

I did several fixed-depth matches between Damage (with 7P DB) and Horizon (6P DB).
In all these (158-games) matches the evaluation function was unchanged.
In the below table all match scores (from the perspective of Damage win = 2 points, draw = 1 point, loose 0 points, all points devided by 158) are depicted.

Code: Select all

                                    Horizon

            depth      4        6       8       10       12

Damage         4       1.53    0.75
               5               1.10 
               6               1.30     0.73
               7                        1.11 
               8                        1.08    0.75                      
               9                                0.92
              10                                1.16     0.79
              11                                         0.99
              12                                         1.06

Interesting to see is the reduced score from the perspective of Damage for equal search-depth, when overal search-depth is increasing.
Although I agree with Ed that the number of games should be increased to improve statistics (so I need to implement 3-move ballots), there is a clear trend visible.
I don't have a good explanation for the diminishing return.
It could be that some elements in the Damage evaluation are related to some short term horizon effects, which are (with increased search depth) taken over (and or recognized) by the search itself.

Anyway It seems that:
1) The Damage evaluation is better then Horizon
2) A difference of 1 ply (at higher ply depth) could offset this difference.
3) There seems to be a diminishing return at higher search depth for the better Damage evaluation function.

Bert

[BertTuyt]

And here the individual match results

Code: Select all

Damage Ply Horizon Ply    +       -      =     score
       4           4     103      20     35    1.53
       4           6     27       66     65    0.75
       5           6     54       38     66    1.10
       6           6     73       26     59    1.30
       6           8     11       54     93    0.73
       7           8     46       28     84    1.11
       8           8     42       29     87    1.08
       8           10    15       55     88    0.75
       9           10    23       36     99    0.92
       10          10    37       12     109   1.16
       10          12    9        42     107   0.79
       11          12    17       27     114   0.94
       12          12    27       17     114   1.06

Bert

[Marcel Kosters]

In (again) late response to one of Berts posts:

- A freely available Windows edition (32 bits and 64 bits) of Horizon sounds very interesting and indeed stimulating for the draughts public! I also applaud the (further) development of such programs as Kingsrow and TurboDambase. There will always be a (very small) market for the more advanced software. A basic but good free programm may even boost interest for such programms.

- There is a development that gives me the hope to say that there will be a draughts tournament server available quite soon. Aimed primarily at people playing eachother online. But no doubt a tournament room for draughts programms can be discussed with the developer. Bert, is this what you had in mind with your suggestion of a tournament server?

I try to read this forum but every now and then I miss quite some messages. For ideas / suggestions / questions concerning KNDB everybody is very much welcome to contact me directly at marcelkosters at gmail.com or to point me to the relevant forum thread. Of course I keep trying to read up on this and other parts of the forum, but response as you can see may take some time and there is a chance of me missing a post while reading up.

Marcel
(KNDB board member responsible for ICT)

[BertTuyt]

Marcel,

There is a development that gives me the hope to say that there will be a draughts tournament server available quite soon. Aimed primarily at people playing each other online. But no doubt a tournament room for draughts programs can be discussed with the developer. Bert, is this what you had in mind with your suggestion of a tournament server?

Yes this what I'm partly looking for, and already again a big step forward (there was a draughts server some time ago, but for whatever reason it disappeared ).
It is also possible that this server runs on a "normal" PC, so that also individuals can organize/initiate engine tournaments...

Bert

[Marcel Kosters]

Marcel,

There is a development that gives me the hope to say that there will be a draughts tournament server available quite soon. Aimed primarily at people playing each other online. But no doubt a tournament room for draughts programs can be discussed with the developer. Bert, is this what you had in mind with your suggestion of a tournament server?

Yes this what I'm partly looking for, and already again a big step forward (there was a draughts server some time ago, but for whatever reason it disappeared ).
It is also possible that this server runs on a "normal" PC, so that also individuals can organize/initiate engine tournaments...

Bert

I'll post if / when there is a chance for a server as I mentioned before. For other solutions, no doubt there is enough know how in this thread. The old damserver had to be discontinued because it was not managable anymore due to lack of documentation, expertise and manpower / -time. The server disruptions were of such a kind that in the end playing on the server was not enjoyable anymore to say the least.

[BertTuyt]

ED, I'm also working on a Hybrid Damage with the Horizon Evaluation.

You somewhere wrote that you often run multiple instances of KingsRow.
I was planning do do the same with damage (so most likely a Damage with the original evaluation and a Damage with the Horizon evaluation), which I can change as a setting when the program is started (so not a separate .exe).

My question, do you use something like CreateToolhelp32Snapshot() in the detection code (this I found while browsing the Internet).
And just out of curiosity do you also change the Header Name of the program (so KingsRow[2] or something like that, so you can still "see" who is who)??

Bert

[Ed Gilbert]

My question, do you use something like CreateToolhelp32Snapshot() in the detection code (this I found while browsing the Internet).
And just out of curiosity do you also change the Header Name of the program (so KingsRow[2] or something like that, so you can still "see" who is who)??

Bert, yes when multiple instances of kingsrow are running, each subsequent instance after the first gets a numeric suffix e.g. [1], [2], ..., added to the name shown in program window title bar, and this same suffix gets added to all filenames that the program writes, such as log files and engine match result files. In this way the multiple instances do not interfere with each other, except of course in that they compete for ram and cpu resources. With 16 instances running I can give each instance 128mb for hashtable, 700mb for the egdb driver, and 1 search thread with pondering off, and then I can run 8 simultaneous engine matches.

To manage the numeric instance number I use a named semaphore. When you create a Windows semaphore with a name, the name is globally visible to all processes. Use some convention for how you will name the semaphores for each instance. At startup, try to CreateSemaphore with the name for instance 0, and if that fails you know there is already an instance 0 of your program running, so then try to create one for instance 1, 2, etc., until you succeed.

-- Ed

[BertTuyt]

This time another part of the horizon Evaluation function.
Below the first 3 elements of this function

Code: Select all

	white =
		wcount_item(white_endgame, 0) +
		wcount_item(node->nr_of_white_man * 1000, 1) +
		wcount_item(node->nr_of_white_king * white_king_value, 2) +

The first element is always 0, as the evaluation returns when a DB-position is found.
Also the next item is logical (with a score of 1000 points for every man).

The white_king_value (and black ) is dynamically calculated with:

Code: Select all

if (node->nr_of_black_king) white_king_value = king_value_with_other_king[node->nr_of_black_man];
	else white_king_value = king_value_without_other_king[node->nr_of_black_man];

So based on the number of opponents man and if a black_king is on the board the white_king_value is determined.

The tables king_value_with_other_king and king_value_without_kings is depected below:

Code: Select all

const int king_value_without_other_king[21] = {2700, 2800, 2900, 3000, 3100, 3100, 3200, 3200, 3200, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 2500, 1800, 1700, 1600} ;
const int king_value_with_other_king[21] =    {3000, 3000, 3000, 3000, 3100, 3100, 3200, 3200, 3200, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 2500, 1800, 1700, 1600} ;

Here I have an issue with the logic, why is the score lower for a white_king if no black king is available (i would expect the opposite).
Next to that, why does the king_value drop so much when many opponent pieces are on the board.
I can imagine that the king become less effective when the position is still crowded.
But on the other hand if one can promote a white man to king in these situations, with the cost of 1 man, then you gain 1600 - 1800 points (dependant on the number of black man 20 - 18 ), but you loose 2 man (1 man promoted to king, and one sacrisfice), which is 2000 points.
So overall the score is negative, so I assume Horizon will not consider this (and from the perspective of the opponents, allow the other color to make such a move).

But maybe im wrong, so i hope some-one out there can help me...

Bert

[TAILLE]

Hi Bert,

For the value of king, according to Horizon point of view I do not see a real difference if the opponent as a king or not.

Code: Select all

const int king_value_without_other_king[21] = {2700, 2800, 2900, 3000, 3100, 3100, 3200, 3200, 3200, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 2500, 1800, 1700, 1600} ;
const int king_value_with_other_king[21] =    {3000, 3000, 3000, 3000, 3100, 3100, 3200, 3200, 3200, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 3100, 2500, 1800, 1700, 1600} ;

The difference is only for the first three values :
const int king_value_without_other_king[21] = {2700, 2800, 2900,
but these values will certainly never be used because we are probably in the egdb.

Concerning your other comment on value 1800, 1700 and 1600 I do not see here again any interest in practice because I hardly imagine a position with a white king when the opponent has still 18-20 men and maybe one or more kings!!!

Because I do not see a real difference for the value of king, depending of the existence of an opponent king, I do not like the above Horizon figures

[TAILLE]

Hi Bert,

This time another part of the horizon Evaluation function.
Below the first 3 elements of this function

Code: Select all

	white =
		wcount_item(white_endgame, 0) +
		wcount_item(node->nr_of_white_man * 1000, 1) +
		wcount_item(node->nr_of_white_king * white_king_value, 2) +

The first element is always 0, as the evaluation returns when a DB-position is found.
Also the next item is logical (with a score of 1000 points for every man).

The white_king_value (and black ) is dynamically calculated with:
...
Bert

BTW do you know if Horizon used also a dynamic value for the men? As an exemple I prefer an advantage of 1 man in the middle of the game rather than in the end of the game simply because this advantage will last more time which increase the probablity to find the win.

[Ed Gilbert]

Next to that, why does the king_value drop so much when many opponent pieces are on the board.
I can imagine that the king become less effective when the position is still crowded.
But on the other hand if one can promote a white man to king in these situations, with the cost of 1 man, then you gain 1600 - 1800 points (dependant on the number of black man 20 - 18 ), but you loose 2 man (1 man promoted to king, and one sacrisfice), which is 2000 points.
So overall the score is negative, so I assume Horizon will not consider this (and from the perspective of the opponents, allow the other color to make such a move).

This makes sense to me. To sacrifice a man to promote to a king when most pieces are still on the board is risky, as it is not uncommon that the opponent will be able to force an even exchange of your king for a man, and then you'll be down a man and without the king.

-- Ed

[BertTuyt]

Gerard, regarding your question

BTW do you know if Horizon used also a dynamic value for the men? As an exemple I prefer an advantage of 1 man in the middle of the game rather than in the end of the game simply because this advantage will last more time which increase the probablity to find the win.

I guess that Horizon uses a static value for the man ( = 1000 points), see below code:

Code: Select all

wcount_item(node->nr_of_white_man * 1000, 1) +

But it could be that in a later stage some value modification takes place.
I will most likely find out, as I will browse (and explain) all Horizon Evaluation elments in the weeks/months to come.

Will keep you all posted

Bert

[BertTuyt]

This weekend I read an interesting analysis from Ton Sijbrands (interesting as usual).
He discussed the game Mor Seck - Baljakin.
Especially the next position is interesting (black to play)



The (apparently) winning move from Baljakin was 16-21!!.
Although a sacrifice, basically now with 2 black man , 5 white man are trapped ( so very much in line with our recent discussion that it is important to detect these type of patterns).

Damage did not find this winning move, and also did not find a draw in the later moves.

Maybe other programs do better here.

Bert