Search Algorithm

[Joost Buijs]

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)

I don't know what to think about XBoard, although it is a very nice gesture of HGM that he puts so much work into it, it still looks like something that stems from the middle ages, but I have to admit that it does the job pretty well.

The GUI of Bert is clearly the best looking but I have the impression that it is by no means a finished product, no wonder when you have a full-time job, in the past I encountered this problem myself, I started with many projects but I never found the time to finish them. Another problem is that it is based on MFC/ATL so you will never be able to compile or run it under Linux. It seems that in the nearby future MSVS is starting to address Linux as well, who knows what will happen.

Building a basic GUI from scratch is not so much work as it seems, I did this in the past for Chess and Othello, but adding all these extra things like multi-engine support makes it more complicated of course. And I think that like me most people rather like to work on their engine instead of a GUI.

[Fabien Letouzey]

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.

I did compile Moby Dam for OS X (as it was called back then) before the Scan 2.0 release. The reason is precisely that I needed a DXP engine to test my implementation.

I'll tell you an anecdote because I think there is an important message in it. Additionally to minor issues (like include files), there was a fatal error: function "Y" (I don't remember its actual name) didn't exist on my system. I look for information and understand that it's a Linux-RT extension. Obviously, it's not portable. (I think) I fixed it by using gettimeofday instead; let's call it "X". Then I contacted Harm and he explained what happened: the Linux man page for X claimed that it was deprecated and should be replaced by Y (which is not portable). Harm followed the advice and that's where the problem came from. The story ended well: Harm told me that he put X back in. I haven't tried to compile the 2016 version but it should be close to compiling straight out of the box. For completeness, X is not marked as deprecated on my system.

Oh, I'm finding a source of information:
---
In Linux and BSDs, you can use the gettimeofday() function. This populates a timeval struct which has a field for seconds since the epoch and a field for microseconds. This function is deprecated. The higher resolution clock_gettime() is the favored replacement, however Mac OS X does not implement it. I'm not sure if Windows implements either of these.
---
http://stackoverflow.com/questions/5303 ... -c/5303898

Since then, I have a different view of what man pages actually are. They are not software documentation; they just describe how things work on your machine, at the time you're reading it (so no guarantee about any future change). While I am glad that Unix is gaining a lot of traction (thanks in big part to mobile devices), I think that the hegemony of Linux is actually a threat to portability. At the very least, I suggest that Linux developpers be critical in their interpretation of Linux documentation. End of rant.

Back to Moby Dam. So just like I needed it when I implemented DXP after Leiden 2015, I will need another engine if I am to develop tools around a different protocol (that Moby Dam is obviously not going to support).

[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

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.

It can dump a pdn to disk, it can even print out only the results + headers.

[Fabien Letouzey]

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.

Scan says that not reducing captures is a tiny gain, at least in very fast TC. As you are proposing a change that concerns high-depth pruning, I tried to launch a slower test and it was rather neutral when I stopped it; presumably, it would have taken days to reach a conclusion. During the test I specifically made changes that are supposed to magnify the result (regardless of sign). I therefore conclude that the actual effect, if any, is below the 1 Elo level. However I note that, since this change likely affects the branching factor (say multiplying it by (1 + epsilon)), it is not possible to safely extrapolate to tournament conditions. There is a remote possibility that it actually has an impact.

In other words: do whichever you prefer, it likely doesn't matter.

[Fabien Letouzey]

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.

I don't understand the "Since I have to start from scratch completely" part; what is making you say this?

You mentioned before that we could start by adding move and position encoding to UCI. Proposals have already been made in the "Protocols and tools" thread. You know the encoding I use in Hub and I suggest using that, and Ed is proposing FEN for positions here: http://fmjd.org/bb3/viewtopic.php?p=116551#p116551
Later in the thread, I argue against it. You are welcome to join the conversation.

In any case, once you have implemented UCI you don't need anything else like EPD or PDN: that's for external tools to do and I already proposed to do that. What I'm asking in such a scenario is that the adaptation of UCI to draughts is carefully done by discussing it first. There are issues other than move and position representation that can wait for now but will have to be handled later. Once we agree on a protocol, I can start implementing.

Furthermore, I can easily handle both Hub and UCI in Scan as they are very similar in spirit. I'm saying this because Bert has already implemented Hub in his GUI: I will continue to support this possibility without him having to rewrite anything.

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.

For completeness I restate here what I did for Scan. I used nearly "random" games (actually material-only search with root-move shuffling). The reason I'm saying this is that you don't have to start from a collection of high-quality games; there are alternatives.

[Joost Buijs]

It can dump a pdn to disk, it can even print out only the results + headers.

Ok, but do you mean it can dump all games at once to PDN or do you have to do it one by one by hand so to speak? I know Klaas is very restrictive about his game database.

[Joost Buijs]

I don't understand the "Since I have to start from scratch completely" part; what is making you say this?

What I mean is that I almost have my engine ready, but I still don't know what the easiest way is to get it playing. I still have to build all other things from scratch before I'm able to do anything useful with it. Right now I'm finishing implementing DXP, to produce a large number of games I have to build a self-play module, I still have to program a Texel style tuning module with smp conjugate-gradient to tune the evaluation parameters and I probably have to add a second protocol like UCI besides DXP.

You mentioned before that we could start by adding move and position encoding to UCI. Proposals have already been made in the "Protocols and tools" thread. You know the encoding I use in Hub and I suggest using that, and Ed is proposing FEN for positions here: http://fmjd.org/bb3/viewtopic.php?p=116551#p116551
Later in the thread, I argue against it. You are welcome to join the conversation.

When I'm finished with DXP I will take a look at it.

In any case, once you have implemented UCI you don't need anything else like EPD or PDN: that's for external tools to do and I already proposed to do that. What I'm asking in such a scenario is that the adaptation of UCI to draughts is carefully done by discussing it first. There are issues other than move and position representation that can wait for now but will have to be handled later. Once we agree on a protocol, I can start implementing.

Probably there are other issues, on first sight it looks as if it will be enough to alter the board and move representation and to remove the castling flags from the FEN.

Furthermore, I can easily handle both Hub and UCI in Scan as they are very similar in spirit. I'm saying this because Bert has already implemented Hub in his GUI: I will continue to support this possibility without him having to rewrite anything.

Maybe there are several Hub versions, I only saw the one that Bert uses in his demo engine and that one is very basic.

For completeness I restate here what I did for Scan. I used nearly "random" games (actually material-only search with root-move shuffling). The reason I'm saying this is that you don't have to start from a collection of high-quality games; there are alternatives.

That there are other ways besides using hq-games to start with is clear, it is my intention to generate the games myself and to start these games at positions which are generated by my perft function at a certain fixed depth.

[Joost Buijs]

Scan says that not reducing captures is a tiny gain, at least in very fast TC. As you are proposing a change that concerns high-depth pruning, I tried to launch a slower test and it was rather neutral when I stopped it; presumably, it would have taken days to reach a conclusion. During the test I specifically made changes that are supposed to magnify the result (regardless of sign). I therefore conclude that the actual effect, if any, is below the 1 Elo level. However I note that, since this change likely affects the branching factor (say multiplying it by (1 + epsilon)), it is not possible to safely extrapolate to tournament conditions. There is a remote possibility that it actually has an impact.

In other words: do whichever you prefer, it likely doesn't matter.

Thanks for testing!

Since it is tactically safer I will keep it in like it is than, I already had the impression that it doesn't have a negative impact on the branching factor.

[Rein Halbersma]

It can dump a pdn to disk, it can even print out only the results + headers.

Ok, but do you mean it can dump all games at once to PDN or do you have to do it one by one by hand so to speak? I know Klaas is very restrictive about his game database.

You can dump all games to disk in one go. It will be a few hundred Mb if I recall correctly.

[Joost Buijs]

It can dump a pdn to disk, it can even print out only the results + headers.

Ok, but do you mean it can dump all games at once to PDN or do you have to do it one by one by hand so to speak? I know Klaas is very restrictive about his game database.

You can dump all games to disk in one go. It will be a few hundred Mb if I recall correctly.

Rein,

Thanks!

Good to know, before I start with building the opening-book and tuning my evaluation function I will buy turbo-base, it is also nice to see what kind of lines people play, in my opinion computers are tactically very strong but positionally humans are still on top.

Joost

[Joost Buijs]

After a lot of sweat and tears my program finally played a game against Kingsrow via DXP, there is still a lot to do before it can play a complete match but at least the DXP routines are basically working. When I was watching the game I had the impression that my program still has a bit lack of depth, and that Kingsrow is strategically better but the game ended in a draw and I'm very happy with this result.

Time controls were 600 sec. for the whole game, Kingsrow run at 8 cores and my program at 10.

Code: Select all

[Event "Game 1, opening 31-27 17-22"]
[Date "2016.12.17"]
[White "Kingsrow 1.58"]
[Black "Argus v1.0 x64"]
[Result "1-1"]
[FEN "W:W27,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,22"]
1. 36-31 16-21 2. 27x16 22-28 3. 33x22 18x36 4. 32-28 11-17 5. 39-33 19-23 6. 28x19 14x23 7. 44-39 10-14 8. 37-32 12-18
9. 41-37 7-11 10. 16x7 1x12 11. 34-30 17-21 12. 30-25 14-19 13. 25x14 9x20 14. 35-30 4-9 15. 46-41 21-26 16. 30-25 6-11
17. 25x14 9x20 18. 40-34 5-10 19. 50-44 10-14 20. 34-30 11-16 21. 30-25 12-17 22. 32-28 23x32 23. 37x28 8-12 24. 33-29 3-9
25. 39-33 2-8 26. 45-40 17-22 27. 28x17 12x21 28. 40-35 20-24 29. 29x20 15x24 30. 33-29 24x33 31. 38x29 18-23 32. 29x18 13x22
33. 44-40 8-13 34. 35-30 22-27 35. 42-37 13-18 36. 43-38 9-13 37. 48-42 19-23 38. 40-34 13-19 39. 34-29 23x34 40. 30x39 19-24
41. 39-34 18-23 42. 38-33 14-19 43. 33-28 23x32 44. 37x28 27-32 45. 28x37 19-23 46. 49-44 23-28 47. 44-39 21-27 48. 34-30 *

[Joost Buijs]

After making some changes to my repetition detection because I thought I saw something fishy I played a second game, this game was very equal and also ended in a draw, maybe draughts is really very drawish.

After programming whole day and drinking several bottles of Belgian beer I'm done for today.

Joost

Code: Select all

[Event "Game 1, opening 31-27 17-22 32-28"]
[Date "2016.12.17"]
[White "Kingsrow 1.58"]
[Black "Argus v1.0 x64"]
[Result "1-1"]
[FEN "B:W27,28,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,22"]
1. ... 22x31 2. 36x27 20-25 3. 27-22 18x27 4. 28-23 19x28 5. 33x31 16-21 6. 31-26 15-20 7. 26x17 11x22 8. 39-33 14-19
9. 44-39 10-14 10. 37-32 6-11 11. 41-37 11-17 12. 46-41 7-11 13. 41-36 22-27 14. 32x21 17x26 15. 38-32 5-10 16. 43-38 10-15
17. 49-43 4-10 18. 33-28 12-18 19. 50-44 19-23 20. 28x19 14x23 21. 39-33 11-17 22. 44-39 1-7 23. 33-28 7-12 24. 28x19 13x24
25. 32-27 9-13 26. 37-32 2-7 27. 42-37 3-9 28. 47-42 17-22 29. 39-33 22x31 30. 36x27 18-22 31. 27x18 12x23 32. 33-28 24-29
33. 28x19 13x24 34. 34x23 24-30 35. 35x24 20x18 36. 32-28 10-14 37. 38-32 14-19 38. 42-38 18-23 39. 43-39 25-30 40. 40-35 26-31
41. 35x11 31x44 42. 28x19 44-49 43. 19-14 49x7 44. 14x3 7-1 45. 48-43 1-6 46. 43-38 6-1 47. 38-33 1-6 48. 33-29 *

[Fabien Letouzey]

Hi Joost,

After making some changes to my repetition detection because I thought I saw something fishy I played a second game, this game was very equal and also ended in a draw, maybe draughts is really very drawish.

Sure, draughts is extremely drawish. Killer draughts is much more interesting, to the level of other games.

Nonetheless it's still an accomplishment if you can easily draw against Kingsrow. Or perhaps Gérard is right and that you more or less "can't lose" if you access 8+ pieces endgame tables. For the record: I don't think so.

Fabien.

[Joost Buijs]

Hi Joost,

After making some changes to my repetition detection because I thought I saw something fishy I played a second game, this game was very equal and also ended in a draw, maybe draughts is really very drawish.

Sure, draughts is extremely drawish. Killer draughts is much more interesting, to the level of other games.

Nonetheless it's still an accomplishment if you can easily draw against Kingsrow. Or perhaps Gérard is right and that you more or less "can't lose" if you access 8+ pieces endgame tables. For the record: I don't think so.

Fabien.

Hi Fabien,

I tried a few games at 60 sec. for the whole game and that goes more difficult, maybe one out of 2 is a draw. I can clearly see that my evaluation function is not good enough yet and that the trouble always starts in the late midgame when it runs out of moves. I don't know the rules of killer draughts, when it is not too complicated to implement I can give this a try in the future. First I want to improve the current program, still a lot of things need to be done.

The only virtue of my program is that it is fast, roughly twice as fast as the competition, the search and evaluation are still very primitive, which I want to improve of course.

Accessing 8P egdb helps, but like you I think that a game already gets decided at a much earlier stage.

Joost

[BertTuyt]

I observed the same, that when playing only with a material based function and endgame databases, I could sometimes draw against competition.
However when losing it was most related to long-term disadvantages far beyond the search horizon (like breakthrough, wing locks, and outposts).

On the other hand i also belief when one (for example) constantly could reach 30 ply, than the evaluation knowledge which always should guarantee a draw, could be minimal.
In other words, there must be diminishing returns in the evaluation when search depth explodes.

In the late middle game (many 10/10 positions) often the program starts to play perfectly, and only based on search and databases.

And applying a destructive strategy, like evaluation of own material (value of a man and king) as a little less compared with the opponent, could help in finding the draw, as with reduced material, complexity reduces, and search depth increases.

But it has often stated here, not losing is not the problem, the challenge is winning....

Bert