Search Algorithm

[Joost Buijs]

Yesterday I finally added LMR to my search and it seems to work ok, it gives me an additional depth of ~4 ply at the starting position and some more later on in the game, it still needs to be tuned, momentarily I use 'rule of thumb' reduction values.
There is one question though, I don't know what to do with captures, to me it seems a capture is more or less the same as a check-evasion in chess, they are both forced. Atm. I turn off LMR at capture-nodes, maybe this is not necessary at all, since I still have no means of checking the playing strength of my program in an easy way I wonder what people in this community think about this subject.

[TAILLE]

Yesterday I finally added LMR to my search and it seems to work ok, it gives me an additional depth of ~4 ply at the starting position and some more later on in the game, it still needs to be tuned, momentarily I use 'rule of thumb' reduction values.
There is one question though, I don't know what to do with captures, to me it seems a capture is more or less the same as a check-evasion in chess, they are both forced. Atm. I turn off LMR at capture-nodes, maybe this is not necessary at all, since I still have no means of checking the playing strength of my program in an easy way I wonder what people in this community think about this subject.

Hi Joost,

Though I do not consider LMR to be the best method allowing to explore deeper the best moves, the LMR method is at least a serious improvment in this direction. The main default of the procedure in an alpha-beta context is the following:
at a node candidate to LMR you need to sort the successors according to their estimated values in order to explore the best moves at full depth and the remaining one at a lower depth, but, due to alpha-beta procedure, you do not have an estimated value of the successor nodes but only a bound value, especially in case of bad moves!!
As a consequence you will explore at full depth the best moves (that is very good isn't it?) but you do not really know how to reduce the following ones because you do not know how bad are the different following moves.
Another important point is the following: let us take a 12x12 position (not very far from the end game). If you have the choice between 10 moves and you find after an exploration at full depth of the three best moves that the position seems quite equal, then the probability to have a draw position is high and it make sense to reduce the following moves. On the other hand if after an exploration at full depth of the three best moves you find that the position has a value estimated to +50 you can conclude that you are in a very delicate situation between the draw and the win and will be stupid to reduce the exploration of the other moves unless these other moves do not lead to any advantage.

Considering now the capture nodes I do not see why we should treat them differently. In cases where you have the choice between 2 or 3 different captures I suspect LMR will not apply anyway but if you are the choice between let's say between 10 different captures you prefer exploring at full depth the best capture moves don't you?

[Joost Buijs]

Considering now the capture nodes I do not see why we should treat them differently. In cases where you have the choice between 2 or 3 different captures I suspect LMR will not apply anyway but if you are the choice between let's say between 10 different captures you prefer exploring at full depth the best capture moves don't you?

I simply asked because I don't know what the experience of other programmers is. You are right that in most cases LMR won't trigger because there are not many capture-moves at a node, at very low depths LMR already triggers after 1 or 2 moves and it happens often that these are capture-moves. With chess it is my experience that using LMR on nodes where the side to move is in check weakens the engine considerably, in my opinion captures in draughts are more or less comparable to check-evasions in chess and this is why I have the feeling that disabling LMR at capture-nodes might be beneficial.

I guess the only way to find out what is best is by trial and error and therefore I need to get my engine to play against itself or against others. The difficulty is that I still don't know what protocol to use, there is DXP, Guide and Hub, all these protocols are very basic. I have a DXP implementation 90% finished but I feel reluctant to continue with it since the protocol is difficult to use and lacks many things compared to CECP or UCI.

Joost

[Fabien Letouzey]

Hi Joost,

I simply asked because I don't know what the experience of other programmers is. You are right that in most cases LMR won't trigger because there are not many capture-moves at a node, at very low depths LMR already triggers after 1 or 2 moves and it happens often that these are capture-moves. With chess it is my experience that using LMR on nodes where the side to move is in check weakens the engine considerably, in my opinion captures in draughts are more or less comparable to check-evasions in chess and this is why I have the feeling that disabling LMR at capture-nodes might be beneficial.

While there is indeed a superficial similarity in terms of branching factor, there are also important differences. For instance, quiet check evasions are often passive while chess is all about pressure. I have never tried (or even considered) reducing captures in draughts; I will launch something tonight and let you know. In any case I expect little effect, and suggest not reducing them as a tactically-safe default.

I guess the only way to find out what is best is by trial and error and therefore I need to get my engine to play against itself or against others. The difficulty is that I still don't know what protocol to use, there is DXP, Guide and Hub, all these protocols are very basic. I have a DXP implementation 90% finished but I feel reluctant to continue with it since the protocol is difficult to use and lacks many things compared to CECP or UCI.

I don't remember Guide in details, but I think it handles engine parameters. In which way do you find it too basic?

I am open to a change in protocol such as expanding Hub or using UCI (or Guide), and we can always discuss that in a separate thread. But ultimately the one who decides is the GUI author (Bert for now) because, by construction, the effort is much larger. What I mean is that, for me, the goal of a protocol is to simplify the engine.

Fabien.

[Ed Gilbert]

In kingsrow I do not exclude captures from lmr, but I don't think I ever tested it the other way, assuming most captures wouldn't have enough moves for the reduction to get used. I also do not reduce as much in lmr as the typical reductions I see in chess, and IIRC as much as Scan does. I keep track of depth in fractions of a ply so I have the ability to reduce with better resolution than a whole ply.

About dxp, while I agree it's not ideal, at least it gives you immediate access to running matches against some of the other programs. Does guide or hub do that? One thing I dislike about dxp is that there is no facility for incremental time control. I added this to kingsrow's implementation of dxp, and also added it to my local copy of Scan. If anyone else is interested in doing this, maybe we could agree on a standard way of doing it.

-- Ed

[Joost Buijs]

Hi Joost,

I simply asked because I don't know what the experience of other programmers is. You are right that in most cases LMR won't trigger because there are not many capture-moves at a node, at very low depths LMR already triggers after 1 or 2 moves and it happens often that these are capture-moves. With chess it is my experience that using LMR on nodes where the side to move is in check weakens the engine considerably, in my opinion captures in draughts are more or less comparable to check-evasions in chess and this is why I have the feeling that disabling LMR at capture-nodes might be beneficial.

While there is indeed a superficial similarity in terms of branching factor, there are also important differences. For instance, quiet check evasions are often passive while chess is all about pressure. I have never tried (or even considered) reducing captures in draughts; I will launch something tonight and let you know. In any case I expect little effect, and suggest not reducing them as a tactically-safe default.

I guess the only way to find out what is best is by trial and error and therefore I need to get my engine to play against itself or against others. The difficulty is that I still don't know what protocol to use, there is DXP, Guide and Hub, all these protocols are very basic. I have a DXP implementation 90% finished but I feel reluctant to continue with it since the protocol is difficult to use and lacks many things compared to CECP or UCI.

I don't remember Guide in details, but I think it handles engine parameters. In which way do you find it too basic?

I am open to a change in protocol such as expanding Hub or using UCI (or Guide), and we can always discuss that in a separate thread. But ultimately the one who decides is the GUI author (Bert for now) because, by construction, the effort is much larger. What I mean is that, for me, the goal of a protocol is to simplify the engine.

Fabien.

Hi Fabien,

Thanks! For the time being I will leave it like it is.

To be honest I never looked at Guide after I noticed that the last draft is from 2004, now that I look at it, it seems to be more complete than expected, and you are right it has a means of sending configuration parameters to the engine. What I miss are all these handy tools you have In the chess world like e.g. Cutechess-cli, most chess GUI's have provisions for running testsuites and running multi-engine tournaments, this is something I clearly miss.

From a protocol point of view it is easy to convert UCI to draughts, you only have to change the FEN and move format, when there are no tools and GUI that support this it is not very useful. A basic GUI is not very difficult to create, I did this for chess years ago and it was a lot less time consuming as building an engine from the ground up, the point is that programming the engine already takes a lot of effort and that I don't want to spend too much time on other things.

Joost

[Joost Buijs]

In kingsrow I do not exclude captures from lmr, but I don't think I ever tested it the other way, assuming most captures wouldn't have enough moves for the reduction to get used. I also do not reduce as much in lmr as the typical reductions I see in chess, and IIRC as much as Scan does. I keep track of depth in fractions of a ply so I have the ability to reduce with better resolution than a whole ply.

About dxp, while I agree it's not ideal, at least it gives you immediate access to running matches against some of the other programs. Does guide or hub do that? One thing I dislike about dxp is that there is no facility for incremental time control. I added this to kingsrow's implementation of dxp, and also added it to my local copy of Scan. If anyone else is interested in doing this, maybe we could agree on a standard way of doing it.

-- Ed

Draughts is completely new for me, atm. I use the LMR formula from my chess program adjusted for the average lower number of moves in Draughts, it seems to work ok but still has to be optimized. I don't use fractional plies, with the current formula the smallest reduction is 1 ply and the largest is 3.

I can finish my DXP implementation within a couple of hours or so, I only have to add some Winsock2 routines and it will be finished. I'm certainly interested in adding your modification for incremental time control, I assume it does not break the protocol as it is right now?

Joost

[Ed Gilbert]

I'm certainly interested in adding your modification for incremental time control, I assume it does not break the protocol as it is right now?

I added a token I named in the source code DXP_GAMEREQ_FISCHER. It is similar to DXP_GAMEREQ, with version, initiator name, and follower color fields identical. An 'F' is sent as the first character in the message instead of 'R'. But at character offset 36 is a 6-character field for the initial time in seconds. Any ASCII number format (integer, fixed point, scientific notation, etc.) is valid. Then at character offset 42 is a 6-character field for the time increment, also in seconds. These 2 new fields are instead of the time and moves fields in DXP_GAMEREQ. The remaining fields for the start position are the same as with DXP_GAMEREQ, except they start at character offset 48 instead of 42.

It does not break the existing protocol. The Initiator can send a GAMEREQ message to start a game with for a fixed time and number of moves, or send GAMEREQ_FISCHER message to start a game using incremental time.

-- Ed

[Joost Buijs]

I'm certainly interested in adding your modification for incremental time control, I assume it does not break the protocol as it is right now?

I added a token I named in the source code DXP_GAMEREQ_FISCHER. It is similar to DXP_GAMEREQ, with version, initiator name, and follower color fields identical. An 'F' is sent as the first character in the message instead of 'R'. But at character offset 36 is a 6-character field for the initial time in seconds. Any ASCII number format (integer, fixed point, scientific notation, etc.) is valid. Then at character offset 42 is a 6-character field for the time increment, also in seconds. These 2 new fields are instead of the time and moves fields in DXP_GAMEREQ. The remaining fields for the start position are the same as with DXP_GAMEREQ, except they start at character offset 48 instead of 42.

It does not break the existing protocol. The Initiator can send a GAMEREQ message to start a game with for a fixed time and number of moves, or send GAMEREQ_FISCHER message to start a game using incremental time.

-- Ed

Ed,

Tomorrow I have some time to work on the program, I will add the ITC modification you made to DXP and try to get everything running. Maybe a nice experiment to put the program on my spare machine to enable others to play against it via the internet, the evaluation function is still very immature but I hope it will be able to grab a draw now and then.

Joost

[Fabien Letouzey]

To be honest I never looked at Guide after I noticed that the last draft is from 2004, now that I look at it, it seems to be more complete than expected, and you are right it has a means of sending configuration parameters to the engine. What I miss are all these handy tools you have In the chess world like e.g. Cutechess-cli, most chess GUI's have provisions for running testsuites and running multi-engine tournaments, this is something I clearly miss.

From a protocol point of view it is easy to convert UCI to draughts, you only have to change the FEN and move format, when there are no tools and GUI that support this it is not very useful. A basic GUI is not very difficult to create, I did this for chess years ago and it was a lot less time consuming as building an engine from the ground up, the point is that programming the engine already takes a lot of effort and that I don't want to spend too much time on other things.

I can write some tools (and have done so in the past), so don't lose hope.

There are limits on what I'm ready to do however. Multi-engine tournaments is too much for instance, at least as a first step. You can still use a script (say in Python) for the high-level organisation if you want this; I did it long ago for gauntlets. I can write the lower-level parts like "n games between engine A and engine B", some simple EPD-like testing, and maybe something else I'm not thinking of right now (time-to-depth / branching factor is a possibility). Some people here might not know that in chess, EPD is FEN + additional fields like the move that the engine is supposed to find; very handy. I can ultimately support different protocols, although two is a maximum as a starting point. I'm not opposed to growing the tools afterwards (after a pause), I'm just trying to state clearly that implementing an endless stream of features is not my thing. There's no end and it defeats the sense of progress. Hopefully other programmers can relate.

If you think you can work with such limitations (which admittedly might feel alien to Windows users), I propose that you join the "Protocols and tools" thread and write down what you need in detail. I'm not going to remember that the information I'm looking for is in the "Search" thread page 40 ... Instead of saying "same as Cutechess-CLI v34.198" (I'm just guessing here: a huge monster over the years), focus on the essential like "I need to play games vs. another engine using protocol A, opening position specified like B, time control C, adjudication D, ...". Take into account that I'm using a Mac for development. To experiment with protocol A, I need an additional engine that implements it; otherwise it's a guessing game combined with the joy of remote debugging. Of course, the engine doesn't have to be strong.

[Joost Buijs]

To be honest I never looked at Guide after I noticed that the last draft is from 2004, now that I look at it, it seems to be more complete than expected, and you are right it has a means of sending configuration parameters to the engine. What I miss are all these handy tools you have In the chess world like e.g. Cutechess-cli, most chess GUI's have provisions for running testsuites and running multi-engine tournaments, this is something I clearly miss.

From a protocol point of view it is easy to convert UCI to draughts, you only have to change the FEN and move format, when there are no tools and GUI that support this it is not very useful. A basic GUI is not very difficult to create, I did this for chess years ago and it was a lot less time consuming as building an engine from the ground up, the point is that programming the engine already takes a lot of effort and that I don't want to spend too much time on other things.

I can write some tools (and have done so in the past), so don't lose hope.

There are limits on what I'm ready to do however. Multi-engine tournaments is too much for instance, at least as a first step. You can still use a script (say in Python) for the high-level organisation if you want this; I did it long ago for gauntlets. I can write the lower-level parts like "n games between engine A and engine B", some simple EPD-like testing, and maybe something else I'm not thinking of right now (time-to-depth / branching factor is a possibility). Some people here might not know that in chess, EPD is FEN + additional fields like the move that the engine is supposed to find; very handy. I can ultimately support different protocols, although two is a maximum as a starting point. I'm not opposed to growing the tools afterwards (after a pause), I'm just trying to state clearly that implementing an endless stream of features is not my thing. There's no end and it defeats the sense of progress. Hopefully other programmers can relate.

If you think you can work with such limitations (which admittedly might feel alien to Windows users), I propose that you join the "Protocols and tools" thread and write down what you need in detail. I'm not going to remember that the information I'm looking for is in the "Search" thread page 40 ... Instead of saying "same as Cutechess-CLI v34.198" (I'm just guessing here: a huge monster over the years), focus on the essential like "I need to play games vs. another engine using protocol A, opening position specified like B, time control C, adjudication D, ...". Take into account that I'm using a Mac for development. To experiment with protocol A, I need an additional engine that implements it; otherwise it's a guessing game combined with the joy of remote debugging. Of course, the engine doesn't have to be strong.

In the past I used Linux starting with versions below 1.0 and I have Linux running in a Hyper-V VM so using Linux or the shell is not completely alien to me, I just find that programming under Visual studio is a lot easier than everything there is under Linux. Flawless debugging and refactoring and the new VS2017 that is released a couple of weeks ago is even better.

Since I have to start from scratch completely I'm thinking about implementing UCI and modifying it to support 10x10 international draughts, the same holds for FEN, EPD and PGN. Maybe PDN resembles PGN but I have no need to support all kinds of different game types and the draughts FEN looks really alien to me.

To have a tool like Cutechess-cli that supports playing 2 engines against each other with very fast time controls over DXP would be nice to have, and something that resembles LittleBlitzer which supports playing multi-engine matches (gauntlet and round-robin) would be perfect.

First of all I need to get a database of games between strong players, since there is nothing to find on the internet I have to create them myself, maybe by selfplay and bootstrapping or by having Scan and Kingsrow fighting it out over a number of different opening positions.

Joost

[Rein Halbersma]

Take into account that I'm using a Mac for development. To experiment with protocol A, I need an additional engine that implements it; otherwise it's a guessing game combined with the joy of remote debugging. Of course, the engine doesn't have to be strong.

Moby Dam works out of the box on Linux using the provided Makefile (both Clang and gcc as compilers). So you should not have any trouble getting it to work on Mac.

[Rein Halbersma]

First of all I need to get a database of games between strong players, since there is nothing to find on the internet I have to create them myself, maybe by selfplay and bootstrapping or by having Scan and Kingsrow fighting it out over a number of different opening positions.

TurboDambase has the option of printing out all games in PDN format. That's around 500 thousand games. You can buy it at http://www.turbodambase.nl/tdamhome.php

[Rein Halbersma]

Instead of saying "same as Cutechess-CLI v34.198" (I'm just guessing here: a huge monster over the years), focus on the essential like "I need to play games vs. another engine using protocol A, opening position specified like B, time control C, adjudication D, ...".

I once exchanged emails with the developer of CuteChess-cli. He said it would be fairly straightforward to implement a Draughts interface for it by subclassing Chess::board and ChessEngine (IIRC, he stated that cutechess-cli didn't know anything about chess, it was just a relay between engines, complete rule-agnostic). Going that route, one could make a separate branch on the Github repo for cutedraughts-cli and keep the draughts interface in sync with all future development of the main repo.

It would be an upfront investment to learning a part of the cutechess-cli library (not sure how much of it) but it would save an enormous amount of feature duplication.

Similarly, for GUI development, I think the biggest benefits for the least amount of work is getting XBoard to work (it already worked in the now deprecated Alien edition, but the multiple-captures were a pain, one had to double-click every move twice, IIRC)

[Joost Buijs]

First of all I need to get a database of games between strong players, since there is nothing to find on the internet I have to create them myself, maybe by selfplay and bootstrapping or by having Scan and Kingsrow fighting it out over a number of different opening positions.

TurboDambase has the option of printing out all games in PDN format. That's around 500 thousand games. You can buy it at http://www.turbodambase.nl/tdamhome.php

What do you mean by printing out, on paper? If it can dump all the games to disk in PDN format at once by just the press of a button maybe I will buy it to make Klaas Bor happy, but I doubt that all the 500.000 games are played between players of IGM (GMI?) level. I know Klaas from the past since he was a friend of Gijsbert Wiesenekker.