Search Algorithm

[BertTuyt]

Rein, thanks for your post.

Basically DQL is part of an even bigger activity which I certainly will share in time.
My intention is to expand the DQL language based on the wishes of all interested.
As I want to honor the TurboDambase initiative I wont distribute the .cgd files (for good/known reasons).
But if you want I can distribute the Damage GUI so others can "play" with it..

I want to work somewhat more on the speed of DQL.
As you might know the TB-format (although proprietary, but that is a different discussion ) was optimized for memory size.
PDN on the other hand seems to be designed for readability.

In both cases the format as is, is not optimal for the DQL purpose.
So I want to convert both formats to an internal optimization after opening and reading the file, which will have a significant effect on processing speed.
That the resulting internal data will approach 1 GigaByte is most likely not an issue....

But, as stated before, where you can really help, is the type of language commands/keywords you need (or is needed most likely within the Draughts community) to support all kind of complex data mining questions.....

Bert

[BertTuyt]

I have based the internal DQL pattern matching on Bitboards , which resulted in an interesting speed increase.
Next to that I have also now implemented the :wtm (white to move) :btm (black to move) and :equal ( material in terms of white man, black man, white king and black equal for white and black) keywords.
It is also possible to add comment ( ; ...... ) in the DQL script.

See below screen shot 1.5 sec and 22167 matches (which correspond with the TurboDambase result).

Basically it is relatively straightforward to also introduce parallel ( 4 - 6 cores, or whatever) pattern search which will yield a further speed boost!

Bert

[BertTuyt]

With the ":output" keyword a .fen or .pdn file will be produced containing the matching position/games.

Code: Select all

; Outpost 24 example with FEN Output (5-Nov-2013)
(match
:output
(position m13 m15 m20 m25 e19 e30 e35 M24 M29)
)
; End DQL script

If the filename is omitted (as in this example) the default name is DQL.fen.
See attachment.

I did not check yet if the FEN output is without error..

Bert

[BertTuyt]

Damage has several operating modes which can be changed via de "enginemode X" command
see below list of options:

Code: Select all

#define ENGINE_MODE_NORMAL				     0 ; Normal mode
#define ENGINE_MODE_ANALYSIS				   1 ; Analysis mode, Damage starts first with the move played
#define ENGINE_MODE_GAME					    2 ; Damage plays a game against ...... Damage
#define ENGINE_MODE_MATCH				      3 ; DXP Match
#define ENGINE_MODE_LEARN					   4 ; Learn Mode (for the time being not fully implemented)
#define ENGINE_MODE_BOOK_UPDATE			   5 ; Update or Generate DOE Book
#define ENGINE_MODE_GEN_ENDGAMEDATABASE	 6 ; Update or Generate Endgame Databases
#define ENGINE_MODE_INFINITE_ANALYSIS		7 ; Infinite Analysis, with scores for ALL Moves
#define ENGINE_MODE_FEN					     8 ; Damage processes a FEN input file and generates a result file

The mode is visualized through a LED in the Engine Window (see below picture).

The FEN Mode was implemented recently (this week) to enable the "further" analysis of a DQL.fen file (generated trough the Damage GUI DQL parser).
An example of such an analysis file is attached to this post.

Every FEN position was analyzed by applying a 16-ply search. An output example is depicted below:

Code: Select all

   1.87 FEN:1     1.59 16.06 -0.10 17-21 
   3.31 FEN:2     1.17 16.10  0.18 42-38 
   4.07 FEN:3     0.50 16.01  2.56 27-21 *>
   5.15 FEN:4     0.80 16.11  0.04 18-22 
   6.43 FEN:5     1.01 16.00  0.10 18x9 
   8.95 FEN:6     2.26 16.11 -0.02 42-38 
   9.91 FEN:7     0.69 16.00  1.48 21-16 *>
  10.92 FEN:8     0.73 16.04 -0.14 17-22 
  12.09 FEN:9     0.89 16.01 -0.08 9-14 
  15.44 FEN:10    3.07 16.06  2.50 27-22 *>
  21.22 FEN:11    5.51 16.07  0.20 5-10 
  22.51 FEN:12    1.01 16.03  0.60 48-42 
  32.04 FEN:13    9.25 16.10  0.40 37-32 
  32.90 FEN:14    0.58 16.03 -0.12 14-19 
  33.56 FEN:15    0.37 16.07 -1.86 14-19 *<

The first number is the total time (in seconds) so far, followed by the FEN identification, time (in seconds) for this specific FEN, ply and best move index, move score ( from the perspective of white, 1.00 is the value of 1 man), best move, and indication ( "*>" or "*<") if the score exceeds the positive ( > 1.0 ) or negative ( < -1.0) threshold.

The "*>" or "*<" indicate a positive score > 1.0 ( *>) or a negative score < -1.0 for white ( *<).
Below the position (with the base pattern) from FEN:15 ( as the file is not self-explaining, I should add as a comment also the info from the DQL.fen file).



Black to move attacks the outpost on 24 via 14-19.
Basically the best move is 27-21 losing the outpost, but white tried to defend the piece via 40-35.
Black follows with 19x30 35x24 22-28 (!) 33x22 16-21 27x16 18x27 32x21 26x17 29x18 20x49.

In the attached file 605 patterns were found with a search score (after 16 ply) > 1.0 and 310 with a score < -1.0

Bert

[BertTuyt]

I also introduced the compound square designator ( [....] ) in DQL.
This enables more complex match criteria.
The expression m[3,4,5,9,10,14] indicates (for example) the condition for "at least"" 1 piece of piece type m on the squares 3 , 4, 5, 9, 10 and 14.

See below code for a DQL script:

Code: Select all

; Outpost on 24 example with compound square designator [...]  (7-Nov-2011)
(match
:output
(position m[3,4,5,9,10,14] m13 m15 m20 m25 e19 e30 e35 M24 M29 :equal)
)
; End Outpost example

I couldn't check if all output was valid, but in the Mega2005 file 22368 matches were found.

Bert

[BertTuyt]

A few (simple) DQL keywords for the position filter were added:

:nocapture , side to move does not have a capture
:nothread , opponent side does not thread other pieces (so opponent to move does not have a capture).
:quiet , nocapture + nothread, so both sides don't have a capture.

Bert

[ildjarn]

Some things that may be interesting:
:capture [X] : capture of X pieces
:zugzwang : Best move for side to move would be 'pass'
:wonlost : Win after being in a lost position (although 'lost' may be a bit difficult to define)
:turc : Coup turc

(and nitpick: :threat, not :thread)

[BertTuyt]

Some things that may be interesting:
:capture [X] : capture of X pieces
:zugzwang : Best move for side to move would be 'pass'
:wonlost : Win after being in a lost position (although 'lost' may be a bit difficult to define)
:turc : Coup turc

(and nitpick: :threat, not :thread)

I will change threa....

Your suggestions are interesting!
On my list of DQL things to do is also ":Xcapture Y", which finds positions where the next move is a move with Y captures . As this option is also available in TurboDambase it is logical to include this.

I'm also thinking about including a dynamic tree-search as keyword (maybe just :search ) in the position list, and to process the results in whatever way. This enables also the option to find and identify :zugzwang positions, and maybe :wonlost.

Next to that I'm also thinking about something like :move 32-18 19-23 ...... which defines a move sequence, and the parser should find positions which are the result of such a move sequence, or the move list is applied after the position is detected (do you have a preference or do you want both?).

To improve DQL readability it might be required in the future to include the #define option (example #define :turc move1 move 2 move3 ....)

So work to do, but the next keyword i'm working on will be :count.

Just a few options:
:count M 12 20 , the white man count should be between 12 and 20
:count e[1,2,3,4,5,6,7,8,9,10] 8, 8 empty squares on 1-10
:count m[8,9,10,14,15,20] 1 infinite, at least 1 black man in this area.....

Bert

[Catherine]

Hi Bert,
I dont know if it is possible to know according to you, what at the essentials elements that doing the strong of Damage. i thing that you continuing work on his strenght. thanks and good continuation

[BertTuyt]

Catherine, to my opinion (others might have a different point of view) the strength of Damage (and other programs like Kingsrow, Damy, Dragon, Maximus, to name a few) is a combination of the search process and the evaluation function. I guess that an opening book and an endgame database (although the minimum should be 6 pieces) is of lesser importance.

With respect to the search it is beneficial to have a parallel implementation (like YBWC)to utilize all cores of a processor (as clock speed these days seems to stabilize at 3.0 - 3.5 GhZ). Next to that to avoid the examination of non-interesting positions (which by the way is most likely already 99% of the search-nodes) , it is important to include (next to plain alpha-beta) mechanism for pruning and selective deepening. The challenge here of course is to extend interesting lines and a balanced pruning without throwing the baby away with the bathwater. Damage uses next to PVS, MCP (Multi-cut-pruning), FHR (Fail High Reduction) and LMR (Late Move Reduction). The LMR is sometimes too aggressive and i need to work on this (which i do).

The most difficult part of the program (and to my opinion the most important part) is the evaluation function, as it contained much hand coded patterns (and there are no general applicable domain-independent tricks, as for example in the search). In the case of Damage I implemented the usual evaluation elements like breakthrough (promotion to king), locks, outpost, material distribution to name a few. The problem is here that for every good "pattern" there are counter examples which you need to code as well, and which make the code unreadable in the end, and also maintenance becomes very difficult.

Last but not least, to really have a stable program one needs to test very often. For this purpose I'm glad we nowadays can rely on DXP which enables automatic matches against other programs (like Kingsrow). Damage for example has played more as 10.000 games against Kingsrow and I'm still learning.....

The problem of testing is that it is time consuming. One has to replay all the interesting games (I normally only review the games lost by Damage), and then one has to find/recognize the "fatal" error, and translate that in improved code (search and/or evaluation). It would be great if this process could be automated, but this is really a difficult task ..

Bert

[BertTuyt]

I have restarted work on DQL.
I now implemented the :markall keyword.
In the previous implementation only the first position in a game matching the DQL pattern was marked.
And search continued with the next game (as is done in Turbodambase).
With the :markall keyword all positions in a game ar now examined.
See below code:

Code: Select all

; Outpost on 24 example with :markall keyword 18-Nov-2013
(match
:markall
(position m13 m15 m20 m25 e19 e30 e35 M24 M29 :equal :quiet)
)
; End Outpost example

Initially 22753 matches were found (in the Mega2005 Database), with :markall this number becomes 292528.

Bert

[BertTuyt]

Added to DQL :lastmovefrom and :lastmoveto which indicate the from and the to square (and the specific piece) of the last move played.

See below code, where the last move was 14-19 with a black piece (m) :

Code: Select all

; Outpost on 24 example with :lastmove  (19-Nov-2013)
(match
(position  m13 m15 m20 m25 m19 e30 e35 M24 M29 :equal :wtm 
:lastmovefrom m14 :lastmoveto m19)
)
; End Outpost example

In total 9370 matches, whatever...

Bert

[Catherine]

THanks Bert for this explaination, thanks. I have a great admiration for program and it is a pleasure for me to know these thinks about them. I have a dream: play like a computer program, no joke. it is why these informations was important for me. thank again and god bless you all for the great job that you are doing.

[Catherine]

Hi Bert and others programmers, i have a question, what is the importance of Nodes/s, I see that Dragon sometime 0.5M/s.
I see also that it have almost 5 move of advance on Dam 2.2 when they play the dxp games. Thanks

[MichelG]

Hi Bert and others programmers, i have a question, what is the importance of Nodes/s, I see that Dragon sometime 0.5M/s.
I see also that it have almost 5 move of advance on Dam 2.2 when they play the dxp games. Thanks

But nodes/second and depth are a bit arbitrary measures. Within one program they are useful, but you can not really compare the values from one program to the other.

Dragon measures nodes/s as evaluations per second. That is, only the end of each branch is counted. It's value can vary from 0.2 M/s on a single core 32 bit machine, to 8 M/s on my 6-core 64 bit machine. Some others also count the interior nodes; this makes a difference of about a factor 2.

Depth is also an arbitrary value, because each program has it's own search extensions and pruning algorithm, you can't say that program X is stronger than program Y, even if it's depth is many ply more.

I still don't have DXP working correctly against dam 2.2, but my guess is that dragon (and damage and kingsrow) should be about 300 elo points stronger than it (on my 6 core machine)

Michel