Search Algorithm

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 17, 2013 20:36

Herewith the .zip file with the CGuide Class.
This class is responsible for the socket connection (both Guide as DXP).

Bert
Attachments
CGuide.zip
(3 KiB) Downloaded 273 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 17, 2013 20:41

And herewith the CBreakThrough64 class (.zip file) .....

Bert
Attachments
CBreakthrough64.zip
(2.29 KiB) Downloaded 273 times

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Search Algorithm

Post by Rein Halbersma » Sun Feb 17, 2013 21:06

BertTuyt wrote:And herewith the CBreakThrough64 class (.zip file) .....

Bert
Hi Bert, nice to see you open up some of your source code. I'll study it! Are you planning to release more code? Rein

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 17, 2013 21:42

Rein, thanks.

Damage is built on the next classes:
- DraughtsEngineApp
- CEngine
- CSearch64
- CMovegen64
- CEvaluation64
- CBreakthrough64
- CDatabase64
- CBook64
- CGuide

I'm planning to release all sources.
The last source I will release is the Damage Evaluation64 , as this one is still rather dynamic.
And the boundary condition for the Evaluation release is that the Damage version available will win a 158 games match from Kingsrow (under equal circumstances).
Thats also for me the moment to release the evaluation, so others can benefit from this...

Again my goal is not the write the best program or defeat the world-champion.
I want to focus more on computer learning, maybe an option to acquire a PhD.

However I will issue all the changes/improvements in the mean time / soon, which I will make in the Horizon Evaluation.

The reason I will not release all at once, is that I'm now in the process of cleaning the files, removing garbage, and adding some remarks to improve readability.

The only routine really embryonic is the CBook64. I'm now studying the drop-out-expansion principle for Book Generation.
But it also clear that such a Book building is only relevant when i have removed the bugs from the search and from the evaluation..

If you have questions, or suggestions for improvement , be my guest.
And last but not least you are always free to include ideas/concepts/code whatever in your code...

Hope this will also inspire others to share code. :)


Bert

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Search Algorithm

Post by Rein Halbersma » Sun Feb 17, 2013 22:01

BertTuyt wrote:Rein, thanks.

Damage is built on the next classes:
- DraughtsEngineApp
- CEngine
- CSearch64
- CMovegen64
- CEvaluation64
- CBreakthrough64
- CDatabase64
- CBook64
- CGuide

I'm planning to release all sources.
The last source I will release is the Damage Evaluation64 , as this one is still rather dynamic.
And the boundary condition for the Evaluation release is that the Damage version available will win a 158 games match from Kingsrow (under equal circumstances).
Thats also for me the moment to release the evaluation, so others can benefit from this...

Again my goal is not the write the best program or defeat the world-champion.
I want to focus more on computer learning, maybe an option to acquire a PhD.

However I will issue all the changes/improvements in the mean time / soon, which I will make in the Horizon Evaluation.

The reason I will not release all at once, is that I'm now in the process of cleaning the files, removing garbage, and adding some remarks to improve readability.

The only routine really embryonic is the CBook64. I'm now studying the drop-out-expansion principle for Book Generation.
But it also clear that such a Book building is only relevant when i have removed the bugs from the search and from the evaluation..

If you have questions, or suggestions for improvement , be my guest.
And last but not least you are always free to include ideas/concepts/code whatever in your code...

Hope this will also inspire others to share code. :)


Bert
WOw, great stuff! Looking forward to it, in particular to the EngineApp class because that's the part where my library is lacking the most. Will you create a GitHub or BitBucket site to maintain your code?

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 17, 2013 22:27

Rein, for the moment I will release it in this forum.

For the longer term I'm open for suggestions...

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Feb 17, 2013 23:45

The DraughtsEngineApp class.

Bert
Attachments
DraughtsEngineApp.zip
(8.11 KiB) Downloaded 287 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Mon Feb 18, 2013 18:39

Herewith the Led class for the Led I used in the Engine.
I found this Class on the Codeproject website.

On the picture you see the Kingsrow ( 10 Min/Game) - Horizon (20 ply) Match in progress :).
In the Engine Output you see the position & score for the PV (Principal variation).

Think I will provide Match info tomorrow......

Bert
Attachments
Engine.PNG
Engine.PNG (102.74 KiB) Viewed 8567 times
Led.zip
(2.07 KiB) Downloaded 272 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Mon Feb 18, 2013 18:46

The CPDN Class (for .PDN file handling).
Im sure I copied some code from others , but I forgot the source :(
Anyway.......

Bert
Attachments
PDN.zip
(4.7 KiB) Downloaded 266 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue Feb 19, 2013 21:41

Herewith the 20 ply search with the Horizon engine (Damage search and Horizon evaluation).
Interesting to see that at 20 ply the Match results seem to stabilize.
Apparently the Horizon evaluation is lacking some long term patterns which negatively impact the Match score.
As usual all relevant files attached.

Code: Select all

Depth     ELO     W     L    D      U     P
14        191     80    1    77     0     0,25
16        114     52    2    104    0     0,34
18        55      29    4    125    0     0,42
20        58      28    2    128    0     0,42  
Bert
Attachments
Fixed Depth MutiCore.xls
(63.5 KiB) Downloaded 270 times
dxpgames_H10P20.pdn
(157.29 KiB) Downloaded 260 times
DDD-20130219.png
DDD-20130219.png (16.99 KiB) Viewed 8506 times

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue Feb 19, 2013 21:44

The CDatabase64 class.
As a base I used some code (and the compression technique) from Michel.
I added a Cache handling system and some other routines....

Bert
Attachments
CDatabase64.zip
(8.07 KiB) Downloaded 292 times

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Wed Feb 20, 2013 11:43

Bert,

Thanks a lot for all the source code you are posting. Very interesting!

I cannot show you much more than a screenshot of me playing against Damage/Horizon using the web interface :D

Still lots of bugs to fix and things to improve before I can make a demo available. The Damage/Horizon version you made available has been an invaluable aid though!

Regards,
Walter
Attachments
Screenshot.png
Screenshot.png (461 KiB) Viewed 8474 times

Walter Thoen
Posts: 44
Joined: Wed Nov 17, 2010 13:26
Real name: Walter Thoen

Re: Search Algorithm

Post by Walter Thoen » Thu Feb 21, 2013 16:16

Bert,

In order to animate the capture moves nicely it is necessary to know the sequence in which the pieces were captured.

Unfortunately, Damage/Horizon seems to send the captured pieces in an unpredictable manner.

For instance, I got the following two capture move messages:

2013-02-21 16:03:56,347 [6] DEBUG KillerGameServer.Game move 21 23 02 27 28
2013-02-21 16:04:26,239 [10] DEBUG KillerGameServer.Game move 23 43 02 38 28

In the first capture 27 is captured before 28. In the second move 28 is captured before 38.

The captured pieces don't appear ordered by value nor by sequence of capture.

I admit that I didn't check the source code that you recently uploaded, but how are the captured pieces ordered?

Regards,
Walter

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Thu Feb 21, 2013 19:11

Walter, Im now removing junk from the CEngine class (which contain all the command-handler functions, including all secret commands :) ) and which provide a clue.

The explanation is simple,. In the past I used a different coordinate system for the board numbering (which originates back to my first program in the 1970-80 era).
The first square was 46, and the last square was 5. I have changed this in the new version of the hybrid version (and also in Damage).

The capture bits are all contained in the bbCapture Bitboard, so all information regarding capture sequence had disappeared.
I scan this BitBoard from LSB to MSB.

So in the previous case, as mentioned by you, 27 is found before 28, and 38 is found before 28.
In the current Hybrid and Damage version the order is "normal", but still without capture sequence.

If I remember well it is also not prescribed in the GUIDE protocol.
2013-02-21 16:03:56,347 [6] DEBUG KillerGameServer.Game move 21 23 02 27 28
2013-02-21 16:04:26,239 [10] DEBUG KillerGameServer.Game move 23 43 02 38 28
In the Damage GUI however I use a different MoveGenerator which is able to animate the right capture sequence (you can activate this via the animate move option).

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Thu Feb 21, 2013 19:52

And herewith the CEngine class, the main interface between the DraughtsEngineApp and the CSearch64 class .
This class processes all Guide (and many more) commands.

Bert
Attachments
CEngine.zip
(22.23 KiB) Downloaded 273 times

Post Reply