Feike Boomstra 's Horizon Draughts Program

[BertTuyt]

Rein,
that's exactly what i want to find out.

My evaluation has progressed through > 20 years I'm already dealing with this addiction.
So most likely I have included all kinds of knowledge which was related to horizon effects (or whatever) at the time search depth was relatively low.
Basically I really don't have a clue anymore which know-how is really important and which is nice to have and therefore not really relevant.

Do the others (as I did) want to share there size (in lines) of the evaluation function, guess we are all dealing with the same exploding complexity

Bert

[TAILLE]

Rein,
that's exactly what i want to find out.

My evaluation has progressed through > 20 years I'm already dealing with this addiction.
So most likely I have included all kinds of knowledge which was related to horizon effects (or whatever) at the time search depth was relatively low.
Basically I really don't have a clue anymore which know-how is really important and which is nice to have and therefore not really relevant.

Do the others (as I did) want to share there size (in lines) of the evaluation function, guess we are all dealing with the same exploding complexity

Bert

My evaluation function is rather complex and the code is dispatching through several files so that the number of lines dedicated to the evaluation function is difficult to view. I guess it is somewhere between 40.000 and 50.000 (including blank lines and comments) but I guess you cannot compare this figure to yours because it includes a lot of code for various special extensions in order to detect a breakthrough. In addition I have to say that I am reviewing all the code in order firstly to clean up the code (I know that a lot of lines are no longer in use => the number of lines will decrease) and secondly to introduce special extensions for detecting weak outposts (=> the number of lines will increase).

It seems that my approach is very different to yours. The word "evaluation" can have several defintions and comparaisons are almost impossible. I think I understand your evaluation as a "static" evaluation detecting various pattern, but my evaluation does not fit such defintion because it is a very "dynamic" evaluation including recursive searches.

[TAILLE]

The 4 stage plan you are describing is at least a 12 ply search! E.g. 1. 42-38 8-12 2. 47-42 12-17 3. 33-28 17-22 4. 28x17 11x31 5. 36x27 18-22 6. 27x18 13x22. This alone is enough to convince me that you cannot put any preference for 42-38 vs 43-38 in an evaluation function. I think it is just too context dependent whether black can make a good pressure attack.

Moreover, there are also other considerations in case the game becomes classical. E.g. after 43-38 18-23 33-28 you still can exchange 37-31x31 and after 21-26 catch again with 47-42x31. After 42-38 18-23 33-28 white runs a small risk of leaving piece 36 behind. Of course in this particular position, that are two arguments for 43-38 over 42-38 and I probably would play 43-38 myself (for what it's worth anyway), but it requires a search, not an evalulation to make that decision.

A simple eval with only material, terrain, tempo, balance and formation counting would already prefer 43-38 over 42-38. At least mine does E.g. 42-38 destroys 37-42-48 and 33-39-44, but 43-38 maintains both of them and even builds 33-38-43.

Rein

I agree with you Rein a lot of considerations have to be taken in consideration in such position. As a human player my analyse tell me that 42-38 will lead to a semi-classic strategy with probably an advantage to black and 43-38 will probably lead to a classic game with equal chances. The point I would like to show is that any pattern can be a strategic strength or a strategic weakness depending of the exact configuration.
You are talking about the line 37-42-48 against the black man 26. Of course it is a very important consideration but you cannot evaluate such configuration without taking into account a great number of other considerations. To be short if the black man on 26 is weak (passive, isolated) and if the white man on 27 is strong (no potentiel black attack against it) then the line 37-42-48 has value near from 0 and an added white man on 47 may even be a weakness (non active man). If on the contrary the black 26 man is strong as a support of an attack against white 27 then the configuration 37-42-47-48 has a very high value.
A strong player will see this quite quickly without analysing any variant.
For a program we all know it is another story. You consider it must be a search problem and I perfectly understand your point but that does not mean that it is the only way to try to solve such difficulty. For me it is a very interesting challenge!

[Rein Halbersma]

I agree with you Rein a lot of considerations have to be taken in consideration in such position. As a human player my analyse tell me that 42-38 will lead to a semi-classic strategy with probably an advantage to black and 43-38 will probably lead to a classic game with equal chances. The point I would like to show is that any pattern can be a strategic strength or a strategic weakness depending of the exact configuration.
You are talking about the line 37-42-48 against the black man 26. Of course it is a very important consideration but you cannot evaluate such configuration without taking into account a great number of other considerations. To be short if the black man on 26 is weak (passive, isolated) and if the white man on 27 is strong (no potentiel black attack against it) then the line 37-42-48 has value near from 0 and an added white man on 47 may even be a weakness (non active man). If on the contrary the black 26 man is strong as a support of an attack against white 27 then the configuration 37-42-47-48 has a very high value.
A strong player will see this quite quickly without analysing any variant.
For a program we all know it is another story. You consider it must be a search problem and I perfectly understand your point but that does not mean that it is the only way to try to solve such difficulty. For me it is a very interesting challenge!

Hi Gérard,

Of course there are many ways to do things. Ideally, a program would do what you seem to be doing: full-width search near the root, selective search at intermediate depth, quiescence search at the horizon, and evaluation at the leafs. Determining the transition between these phases is precisely the difficulty in tuning a good program. In any case, for the time being I prefer to minimize my program complexity by having a small static eval. I currently only have material, mobility, tempo, center, balance, formations and the elementary lock patterns. The search takes care of the rest.

Moreover, there are many ambiguous eval terms such as terrain and breakthrough that are not really possible to evaluate statically. Your ideas on the French forum about the relation between tempo and terrain are very good (and they have been discussed in the draughts literature as well, from which I got similar ideas a few years ago), but they require at least a 2-ply (or even 4-ply) bit-parallel look-ahead to compute it reasonably correctly. For breakthrough as well, you can pre-compute a lot of patterns and evaluate them statically during a search, or you can use such patterns for dynamic search extensions. A priori, I don't know which is best.

What I do know is that a chess program like StockFish has 15 thousand lines of code in total, with a fairly minimal evaluation function. Most of the special pawn patterns are evaluated dynamically, perhaps with a few patterns to trigger the extensions. Perhaps something similar also works in draughts.

Rein

[BertTuyt]

I did several other tests where Damage with a "crippled" evaluation function played against Horizon a fixed depth (10 Ply each) 2-ballot 158-game match.
I used 3 types of evaluation functions for Damage (in all tests Damage had a 7Piece DB and Horizon a 6Piece DB)
1) M : Material only
2) MB : Material + Breakthrough
3) MBD: Material + Breakthrough + Distribution (think you could also name this "balance", how the pieces are balanced over centre and left/right wings)

Especially in the test with MB, I have seen that at the time the breakthrough was detected it was too late to stop the opponent from promoting.

Anyway, here the results (10Ply search for Damage as Horizon, and Horizon played with the normal evaluation function):
Score is from the perspective of Damage

Code: Select all

M:     0+  118- 5=   35?
MB:    1+  116- 17=  24?
MBD:   4+  81-  54=  19?

Although the ? score can influence the overall score, it is interesting to see the effect of the Distribution-routine (despite limited statistics).
This routine is really small (only counting in some areas the number of man and opponent man and some if then else adjustments), however the routine seems to be very effective.
I wonder if the strength of this routine is related to the combination with Breakthrough() or that also on a stand-alone base Distribution() works quite well.

A 16Ply match with Damage + MBD did win against a 10Ply Horizon (with full evaluation) 42+ 22- 94= (in this case i already checked all the ?games).

As the original 10Ply Damage -10Ply Horizon match was a win for the (unmodified) Damage ( 37+ 12- 109= ), I will test further the effect of the routines which I did not include yet.
I would be not surprised when in the end a large portion of the Damage evaluation code would become obsolete..

Keep you all posted,

Bert

[BertTuyt]

Rein/Gerard,

Moreover, there are many ambiguous eval terms such as terrain and breakthrough that are not really possible to evaluate statically. Your ideas on the French forum about the relation between tempo and terrain are very good (and they have been discussed in the draughts literature as well, from which I got similar ideas a few years ago), but they require at least a 2-ply (or even 4-ply) bit-parallel look-ahead to compute it reasonably correctly.

Could you explain these ideas, as I didn't follow the discussions within French forum.

Bert

[Rein Halbersma]

Rein/Gerard,

Moreover, there are many ambiguous eval terms such as terrain and breakthrough that are not really possible to evaluate statically. Your ideas on the French forum about the relation between tempo and terrain are very good (and they have been discussed in the draughts literature as well, from which I got similar ideas a few years ago), but they require at least a 2-ply (or even 4-ply) bit-parallel look-ahead to compute it reasonably correctly.

Could you explain these ideas, as I didn't follow the discussions within French forum.

Bert

Bert,

You can read it at this thread http://www.ffjd.fr/Web/index.php?page=f ... sujet=9434 (Google translate is your best friend, there is a toolbar that does this automatically).

Rein

[Rein Halbersma]

I didn't use the Frank DLL as I wanted to understand myself how this socket() thing worked.
And I did want to be dependant on a DLL I not fully understood
So this is just a quick and dirty implementation which helped me also to understand the internals

Bert

I am currently finishing my own DXP implementation. It's based on the Boost Asio library and it works on both Windows and Linux (and Mac). Compared to Frank's code I made a stricter separation between the two layers. Layer 1 does the connect/accept stuff. Layer 1 also reads and writes plain old C-style strings from the socket. All the parsing into DXP messages is done in Layer 2. With Frank's code, Layer 1 does the translation from DXP message to strings behind the scenes (it's in the DLL) and I wanted to decouple this. Layer 1 code is about 150 lines.

Layer 2 is also implemented differently from Frank's code. Rather than the static union of structs, I have a dynamic class hierarchy where all the various DXP message types are derived from an abstract message class. Parsing is done through a design pattern called Factory Method. Each message type "registers" itself to the factory (a simple map storing the message type's header and a creator function). This way, the parser does not need to know anything about the number of different message types. This makes the design very flexible for future extensions. Layer 2 code is about a 100 lines for each message type.

So far, I can connect to Dam2.2 and Kingsrow on my own pc, and send and receive commands. The Follower mode has a bug currently and I haven't been able to receive an incoming connection from Dam or Kingsrow. I also haven't written a proper controller yet to let the engine respond to the various messages. I'm thinking of writing a Layer 3 that defines an Engine interface so that other programmers can simply derive from that interface to implement a fully functional DXP engine without worrying about any socket stuff. When it's done, I will publish this stuff under the Boost license.

Rein

[Ed Gilbert]

The Follower mode has a bug currently and I haven't been able to receive an incoming connection from Dam or Kingsrow.

Rein, I know it is a natural tendency to think that the engine performing the server side of the connect process should be the Follower, but in fact the client/server connect procedure is completely separate from the Follower/Initiator dxp protocol, and there is a good reason to keep them separate. When using dxp across an internet connection such as in the kingsrow vs. damage matches, and in typical home network environments that have NAT routers, some changes have to be made to one of the routers to allow the connection to be made. Normally the routers will block all connection requests originating from outside the user's private home network, and so the router at the dxp server needs to be set to forward all traffic for the dxp socket port to the particular machine that is going to be the dxp server. When Bert and I first tried to run a dxp match, Bert had not yet implemented the 2-move ballots in damage, so kingsrow had to be the Initiator. Bert had also tied the Initiator to client and Follower to server functions, so since damage had to be Follower that meant it also had to be the dxp server for the connect process. I had previously set my router to do the necessary port forwarding expecting that kingsrow would be the server for the connect, but when we found damage had to be the server, we couldn't connect because Bert's router was not doing the port forwarding. Every router is a little different in their features and user interfaces, and it can take a little hunting to find the necessary command to make the change. Anyway the point is to keep the connection process separate from the Initiator/Follower functions.

-- Ed

[Rein Halbersma]

The Follower mode has a bug currently and I haven't been able to receive an incoming connection from Dam or Kingsrow.

Rein, I know it is a natural tendency to think that the engine performing the server side of the connect process should be the Follower, but in fact the client/server connect procedure is completely separate from the Follower/Initiator dxp protocol, and there is a good reason to keep them separate. When using dxp across an internet connection such as in the kingsrow vs. damage matches, and in typical home network environments that have NAT routers, some changes have to be made to one of the routers to allow the connection to be made. Normally the routers will block all connection requests originating from outside the user's private home network, and so the router at the dxp server needs to be set to forward all traffic for the dxp socket port to the particular machine that is going to be the dxp server. When Bert and I first tried to run a dxp match, Bert had not yet implemented the 2-move ballots in damage, so kingsrow had to be the Initiator. Bert had also tied the Initiator to client and Follower to server functions, so since damage had to be Follower that meant it also had to be the dxp server for the connect process. I had previously set my router to do the necessary port forwarding expecting that kingsrow would be the server for the connect, but when we found damage had to be the server, we couldn't connect because Bert's router was not doing the port forwarding. Every router is a little different in their features and user interfaces, and it can take a little hunting to find the necessary command to make the change. Anyway the point is to keep the connection process separate from the Initiator/Follower functions.

-- Ed

Hi Ed,

Thanks for reminding me that Follower/Initiator is not tied to client/server. That was a slip of the pen. Indeed the DXP description states that the Initiator role is tied to the first program to send a GAMEREQ message. However, for a future DXP tournament Server, the server should be the Initiator!

I don't think that my bug is related to this. E.g., I can let Kingsrow and Dam2.2 play a match against each other on my computer (using the localhost 127.0.0.1 as the IP address). I can also connect to both Kingsrow and Dam2.2 (again using 127.0.0.1). What doesn't succeed yet it to let either program connect to my program. So I think it's most probably a programming bug on my part. Boost Asio treats connect and accept asymmetrically, so perhaps I need to study the documentation a bit more.

In any case, thanks for the information on the port forwarding issues, which I will have to figure out for my router in case I want to connect to other computers in my home network or across the internet.

Rein

[BertTuyt]

So I activated another part of the Damage function this time and played another 158games match.
This time I activated the Front-Post routine (or voorpost, hope some-one has a better English name).
Added to the other results, I now have the next overview:

Code: Select all

M:     0+  118- 5=   35?
MB:    1+  116- 17=  24?
MBD:   4+  81-  54=  19?
MBDF:  17+ 73-  68=  0?

0? as I analyzed all ?-games this time
Browsing through several games I encountered several lock-situations , these are typically longer-term mobility killers which are not bypassed through the search.
It is evident that I have all kinds of locks programmed in Damage (but not activated yet).

I was thinking that maybe locking patterns is something which could be auto-detected and recognized and categorized through a computer program itself.
Does some-one knows if this has been tried before in Draughts / Checkers.
I know that Stef has implemented something in Truus for auto-detection (or something alike) for combination patterns.

But I assume that with current search-depth this method is no longer of much relevance (in time when programs searched 4 - 6 plies, this might be different).
When a locking position is created by one of the 2 players, one should see a longer term drop in mobility.
I need to think about this, but I find it interesting to study somewhat more....

Bert


Bert

[BertTuyt]

Wanted to add, that basically one can measure normal mobility, which is just the legal number of moves, and dynamic mobility, the actual number of moves which do not lead to short/long term ( X Ply) material loss (and or breakthrough).
See below pattern , for example.

Basically it is not a lock but the man on 11 has the overall effect that the man on 16 and 17 are not able to move (think this is called a hanging man).
One longer term boundary condition is that the empty square on 6 can not be occupied by black, for a real long term immobility (and 17-22 is also forbidden, and .. and .. ) !

Apple has a algorithm to recognize the face of a specific person in many pictures/photos based on one example, think we could really do more in our domain with the detection of specific patterns (in stead of trying to hard-code all, by examining studying and analyzing zillions of games).

Bert

[TAILLE]

Wanted to add, that basically one can measure normal mobility, which is just the legal number of moves, and dynamic mobility, the actual number of moves which do not lead to short/long term ( X Ply) material loss (and or breakthrough).
See below pattern , for example.

Basically it is not a lock but the man on 11 has the overall effect that the man on 16 and 17 are not able to move (think this is called a hanging man).
One longer term boundary condition is that the empty square on 6 can not be occupied by black, for a real long term immobility (and 17-22 is also forbidden, and .. and .. ) !

Apple has a algorithm to recognize the face of a specific person in many pictures/photos based on one example, think we could really do more in our domain with the detection of specific patterns (in stead of trying to hard-code all, by examining studying and analyzing zillions of games).

Bert

The idea of detecting specific pattern is of course interesting. The challenge is difficult but why not trying ?
The pattern you show is a good example but beaware that a lot of patterns may be strong or weak depending of the surroundings. For example in the following diagram :



If the totoal number of men on the board is not very high then, if there is no black man on square 6 I prefer black position because 3 black men are involved against 4 white men. I even can say that black man 11 is strong in this case! BTW if you add a black man on 6 the black position becomes far less interesting unless there is a white man on 28 that could be considered under pressure. The best place to add a black man here is on square 1. The move 01-06 would be very weak indead and may even be weaker than 01-07.

[BertTuyt]

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

[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