Computer Draughts 2012

[BertTuyt]

Gerard, I recognize your point.

The time to depth tells not the complete story.
You can always throw away the baby with the bath water.
And as they say the proof of the pudding is in the eating.
Which could be realized through a tournament, when you win your implementation might be better (although due to the limited number of games we suffer from quantum statistics).
You can play a (158 games) match against the un-modified version.
And last but not least there is always Kingsrow , who perfectly can spoil your day by proving that all your brilliant ideas dont work ( at least that is/was often my experience).

In the case of Damage, I found out that Damage was often outsearced by Kingsrow, who surprised me with an sudden score explosion.
As (like Ed) im not a hyper-space specialist in Draughts the position itself didn't reveal any clue to me where/how to improve.
So i focused on the search, to reach at least equal plies within a given time frame.
I tested several search-improvement mechanisms in these specific cases, and if Damage was then able to correct the move, or find the winning move, it at least boosted confidence that this might work in general .

In the end the 158 games match was the final test. (and as I played in the last 4 months over 20 matches, you can imagine that most ideas didn't work out the way i expected )

As Damage won the last match for the first time in my history,again this is not a scientific prove, it provides me with the confidence that although the pruning is not always sound, and/or correct in all cases, in general it might work , as the result of around 158 games * 65 moves/game was not that bad.
What I didn't do in detail, is to play matches for all the pruning mechanisms for which I also measured 19-ply initial search timing. It would be great if for the mentioned options search-time scales with match-results !

I'm now doing a quick test against KingsRow with the reverse sequence FHR - MCP (which resulted in the below 10 seconds search-time), and after 60 games (maybe i wont continue till the end) the score is Kingsrow 2 Win, Damage 2 Win, 54 Draw and 2 unknown (the 2 unknowns could spoil the party ).

I know that you focus (for good reasons) on thematic positions, but I hope that you find the time for a 158-game match against Kingsrow, to raise the bar for us all (so there is no need to terminate this addiction on short notice) ....


Bert

[BertTuyt]

Rein/Gerard,

The other was the evaluation of tempo/terrain that you discussed on the French forum a year(?) ago, which I had been discussing privately with Ed

I missed this one, could you share it here on the forum?

Bert

[Rein Halbersma]

Rein/Gerard,

The other was the evaluation of tempo/terrain that you discussed on the French forum a year(?) ago, which I had been discussing privately with Ed

I missed this one, could you share it here on the forum?

Bert

http://www.ffjd.fr/Web/index.php?page=f ... sujet=9434 which can be read in any language that Google Translate supports

[BertTuyt]

Rein,

Iteresting to read your LMR implementation. Did you ever try the Stockfish type of depth reductions which scale like log(depth) * log(move_number)

could you give an specific example/description of the mentioned Stockfish implementation you are referring to?

Bert

[Rein Halbersma]

Rein,

Iteresting to read your LMR implementation. Did you ever try the Stockfish type of depth reductions which scale like log(depth) * log(move_number)

could you give an specific example/description of the mentioned Stockfish implementation you are referring to?

Bert

EDIT: Look at lines 178-185 of the function Search::init() in the file search.cpp on the Stockfish GitHub site

Code: Select all

  // Init reductions array
  for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
  {
      double    pvRed = log(double(hd)) * log(double(mc)) / 3.0;
      double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
      Reductions[1][hd][mc] = (int8_t) (   pvRed >= 1.0 ? floor(   pvRed * int(ONE_PLY)) : 0);
      Reductions[0][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
  }

[BertTuyt]

Rein, are you expanding the hashdata to 128 bit ?

I thought your hash entries were something like 40 bytes in the past? Have you changed to a compacter format? I'm remodeling my hash table to entries of 16 bytes (used to be 8 bytes, but that leaves very little room for interesting information). One thing I want to add are the window-bounds that a node was searched with, this should help to reduce search instabilities (because you can then distinguish scores with respect to different windows).

Damage uses 64 bits implemented in the Hyatt way, so I dont use locks in the parallel implementation.

By the way , I'm still trying to find a use for the new 128 and 256 bit registers/instructions in the new processors being developed.
Did you already find a purpose that makes sense?

Bert

[Rein Halbersma]

Damage uses 64 bits implemented in the Hyatt way, so I dont use locks in the parallel implementation.

By the way , I'm still trying to find a use for the new 128 and 256 bit registers/instructions in the new processors being developed.
Did you already find a purpose that makes sense?

Bert

Bert,

I'm not an expert on any advanced SIMD processor instructions. I try to stay away from such magic

I want to expand my hash entries to have some more information (eval score, and window bounds). The window bounds could potentially reduce search instabilities. E.g. if you have bound-dependent reductions, a search with beta=+5 (i.e. white has a small advantage at the root) could e.g. prune/reduce some desperate black defense that sacrifices a piece. If the search later finds that white actually has a big advantage, then a new search with beta=+80 would stop pruning/reducing the desperate defense, and return a score of say +20 again. Then re-search with beta=+20, might kill the desperate defense again, and return +80. So you could get a cycle of fail-highs/fail-lows. I haven't worked it out exactly, but my intuition is that you should only re-use TT nodes that were previously failing low/high if the current beta is higher/lower than the stored bound.

BTW, the lockless hashing is a potentially dangerous strategy, and you are best advised to inspect the generated assembly code to make sure that atomic 64-bit reads/writes are actually being generated. And you need to do this after every compiler/OS upgrade. See this question I just asked on StackOverflow. In the new C++11 you could use `std::atomic<uint64_t>` for the two 64-bit words to guarantee thread-safety.

Rein

[TAILLE]

Hi Bert,

Rein/Gerard,

The other was the evaluation of tempo/terrain that you discussed on the French forum a year(?) ago, which I had been discussing privately with Ed

I missed this one, could you share it here on the forum?

Bert

http://www.ffjd.fr/Web/index.php?page=f ... sujet=9434 which can be read in any language that Google Translate supports

The evaluation of tempo/terrain is one of my favorite subjects. IMO it is a very powerful analysis used by human but it is quite difficult to use it in a program. I think the first programmer who mange to use efficiently this notion will get a strong advantage over the other programmers. This notion was the main argument for me to try and rebuild completely may eval function. Today I cannot say if I will be able to achieve my goal but at least it is a funny challenge and do not regret to have decided to work on this very interesting topic.

Here is an example of the point:


In this classic game how do you evaluate this position?
White has a lead in development which rather a weakness in a classic game but white has at its disposal the exchange by 34-30x30 which allows it to take a control over the two wings which is a good thing. Another weakness for white is the man on 45 which is very passive.

As a consequence the advantage is certainly for black but how going further?

As a human I am able to build the following analysis:
Suppose white will play 34-30x30. After this the white terrain goes to squares 25,26,27,28,30,33,34,35. The number of white tempos on this terrain is equal to 6 tempos
34-30x30 (1 tempo) and 30-25, 45-40-34-30, 43-38.
The black terrain goes to 16,17,18,23,24 and the number of black tempos on this terrain is also equal to 6 tempos: 1-6-11-16, 3-9-14, 8-13
The result of this analysis is the following: white position is far worse if in the position above it white to play! If is is black to play, black has to look for more terrain and white has a good chance to reach the draw.

The point for a programmer is the following: a human is able to see quite quickly that the difference of one tempo is here very important (it could be the difference between a win or a draw!). However but for the majority of programs (at least for Damy) only a search including millions of positions will make appear that the difference of one tempo is crucial.
Should this position appear at 10 plies from the leaves of the tree, then no difference would be seen by the program.

I hardly accept that a human can run a quick and very efficient analysis which a computer cannot run.
Great challenge isn’it?

[Rein Halbersma]

Here is an example of the point:


In this classic game how do you evaluate this position?
White has a lead in development which rather a weakness in a classic game but white has at its disposal the exchange by 34-30x30 which allows it to take a control over the two wings which is a good thing. Another weakness for white is the man on 45 which is very passive.

As a consequence the advantage is certainly for black but how going further?

As a human I am able to build the following analysis:
Suppose white will play 34-30x30. After this the white terrain goes to squares 25,26,27,28,30,33,34,35. The number of white tempos on this terrain is equal to 6 tempos
34-30x30 (1 tempo) and 30-25, 45-40-34-30, 43-38.
The black terrain goes to 16,17,18,23,24 and the number of black tempos on this terrain is also equal to 6 tempos: 1-6-11-16, 3-9-14, 8-13
The result of this analysis is the following: white position is far worse if in the position above it white to play! If is is black to play, black has to look for more terrain and white has a good chance to reach the draw.

The point for a programmer is the following: a human is able to see quite quickly that the difference of one tempo is here very important (it could be the difference between a win or a draw!). However but for the majority of programs (at least for Damy) only a search including millions of positions will make appear that the difference of one tempo is crucial.
Should this position appear at 10 plies from the leaves of the tree, then no difference would be seen by the program.

I hardly accept that a human can run a quick and very efficient analysis which a computer cannot run.
Great challenge isn’it?

My algorithm works slightly different. I do two parallel bitshifts of both the white and black pieces and assign terrain as follows:
1) if a majority of one color can reach a square (4-0, 3-1, 2-1, X-0 with X=1...4) then that color controls that square
2) if neither color can reach it, or if an equal amount of pieces can reach it, the square is neutral
3) exception to rule 1: if there is a 2-1 situation where two pieces are diagonally opposed, the single opponent piece can slide between the two, and the minority side controls the square
4) captures are ignored

In the position above: this algorithm assigns squares as follows:

So you see that squares 21/16 are controlled by white and not black in my algorithm! Of course, there are tactics that prevent that, but the search should reveal that in deeper iterations.

Then I do the following counting
1) in the initial position, white has 4 tempi more
2) in the terrain situation, white has 6 tempi more
3) in the initial position, white has the move

I add these 3 terms as follows:
1) each tempo in the initial position counts as -1
2) each tempo in the terrain situation counts as +1
3) the move counts as -0.5

So I get that white has -4 + 6 -0.5 = +1.5 so 1.5 move less developed than his controlled terrain: white is not in trouble according to this crude static analysis. However, not having the move here, would be slightly better for white (it wouldn't change the controlled terrain and would give white 1 tempo more "breathing room"). What I try to do with this simple measure is to guide the move ordering towards playing for both more tempo and more terrain, but for any given amount of terrain, it's not good to have more tempo than terrain. I don't believe that it is useful to develop anything substantially more advanced because the cost of computing more refined static measures pretty soon will equal that of a full dynamic search.

The problem of course is that there are several dynamical fights for squares 21, 22 and 29 that will determine how much squares white and black can actually occupy. E.g. 27-21 will open the black possibility 18-22 and 34-30x30 will open the possibility 23-29. Resolving those fights is best done with a full search. E.g. the PV of Kingsrow in this position is a tactical variation 1. 34-30 25x34 2. 39x30 3-9 3. 45-40 1-7 4. 30-25 9-14 5. 43-38 7-11 6. 40-34 11-16 7. 27-22 18x27 8. 32x21 23x43 9. 34-29 16x27 10. 29x9 with a db draw.

[TAILLE]

Hi Rein,

Here is an example of the point:


In this classic game how do you evaluate this position?
White has a lead in development which rather a weakness in a classic game but white has at its disposal the exchange by 34-30x30 which allows it to take a control over the two wings which is a good thing. Another weakness for white is the man on 45 which is very passive.

As a consequence the advantage is certainly for black but how going further?

As a human I am able to build the following analysis:
Suppose white will play 34-30x30. After this the white terrain goes to squares 25,26,27,28,30,33,34,35. The number of white tempos on this terrain is equal to 6 tempos
34-30x30 (1 tempo) and 30-25, 45-40-34-30, 43-38.
The black terrain goes to 16,17,18,23,24 and the number of black tempos on this terrain is also equal to 6 tempos: 1-6-11-16, 3-9-14, 8-13
The result of this analysis is the following: white position is far worse if in the position above it white to play! If is is black to play, black has to look for more terrain and white has a good chance to reach the draw.

The point for a programmer is the following: a human is able to see quite quickly that the difference of one tempo is here very important (it could be the difference between a win or a draw!). However but for the majority of programs (at least for Damy) only a search including millions of positions will make appear that the difference of one tempo is crucial.
Should this position appear at 10 plies from the leaves of the tree, then no difference would be seen by the program.

I hardly accept that a human can run a quick and very efficient analysis which a computer cannot run.
Great challenge isn’it?

My algorithm works slightly different. I do two parallel bitshifts of both the white and black pieces and assign terrain as follows:
1) if a majority of one color can reach a square (4-0, 3-1, 2-1, X-0 with X=1...4) then that color controls that square
2) if neither color can reach it, or if an equal amount of pieces can reach it, the square is neutral
3) exception to rule 1: if there is a 2-1 situation where two pieces are diagonally opposed, the single opponent piece can slide between the two, and the minority side controls the square
4) captures are ignored

In the position above: this algorithm assigns squares as follows:

So you see that squares 21/16 are controlled by white and not black in my algorithm! Of course, there are tactics that prevent that, but the search should reveal that in deeper iterations.

Then I do the following counting
1) in the initial position, white has 4 tempi more
2) in the terrain situation, white has 6 tempi more
3) in the initial position, white has the move

I add these 3 terms as follows:
1) each tempo in the initial position counts as -1
2) each tempo in the terrain situation counts as +1
3) the move counts as -0.5

So I get that white has -4 + 6 -0.5 = +1.5 so 1.5 move less developed than his controlled terrain: white is not in trouble according to this crude static analysis. However, not having the move here, would be slightly better for white (it wouldn't change the controlled terrain and would give white 1 tempo more "breathing room"). What I try to do with this simple measure is to guide the move ordering towards playing for both more tempo and more terrain, but for any given amount of terrain, it's not good to have more tempo than terrain. I don't believe that it is useful to develop anything substantially more advanced because the cost of computing more refined static measures pretty soon will equal that of a full dynamic search.

The problem of course is that there are several dynamical fights for squares 21, 22 and 29 that will determine how much squares white and black can actually occupy. E.g. 27-21 will open the black possibility 18-22 and 34-30x30 will open the possibility 23-29. Resolving those fights is best done with a full search. E.g. the PV of Kingsrow in this position is a tactical variation 1. 34-30 25x34 2. 39x30 3-9 3. 45-40 1-7 4. 30-25 9-14 5. 43-38 7-11 6. 40-34 11-16 7. 27-22 18x27 8. 32x21 23x43 9. 34-29 16x27 10. 29x9 with a db draw.

I have several questions concerning the building of this diagram but let's begin by two basic ones:
1) How do you decide to assign square 16 to white?
2) Will the calculation of this diagram change if, in the original position, I move the white man on square 43 to the square 44 as in the following diagram:

[BertTuyt]

Rein, i still do not complete understand your algorithm.

In the position as given by Gerard, the black man on 1 can reach 6 and 7 (and no white man can do that, at least not in 1 move).
Same for the piece on 3 who can reach 9 in 1 move.
So in your definition does black control the fields/terrain 6, 7, and 9 ?

Do you consider only 1 move ahead (as after multiple moves the terrain you can reach is much larger?
And last bit not least are the bit shift you were mentioning the "more or less traditional" +5/+6/-5/-6 ?
Anyway , i find the topic quite interesting, but first need to understand the basics first

Bert

[BertTuyt]

Gerard, in one of your previous posts you mentioend:

White has a lead in development which rather a weakness in a classic game but white has at its disposal the exchange by 34-30x30 which allows it to take a control over the two wings which is a good thing. Another weakness for white is the man on 45 which is very passive.

Do you have a mathematical expression for wing control, or some ideas, which could be embedded in a algorithm which a computer draughts program can "understand".
So far the thing which i did was defining some (the more or less well known short/long wing lock) wing locks patterns, and when the number of locked pieces was larger than the number of pieces needed to maintain the lock, then this lock was an advantage for the "attacker".

Bert

[TAILLE]

Hi Bert,

Gerard, in one of your previous posts you mentioend:

White has a lead in development which rather a weakness in a classic game but white has at its disposal the exchange by 34-30x30 which allows it to take a control over the two wings which is a good thing. Another weakness for white is the man on 45 which is very passive.

Do you have a mathematical expression for wing control, or some ideas, which could be embedded in a algorithm which a computer draughts program can "understand".
So far the thing which i did was defining some (the more or less well known short/long wing lock) wing locks patterns, and when the number of locked pieces was larger than the number of pieces needed to maintain the lock, then this lock was an advantage for the "attacker".

Bert

I do not quite understand what you mean exactly by mathematical expression.
For Damy it is quite simple.
As soon as you recognize a classical position it is essential to look for the control of squares 25 and 26. If one side control both squares then it controls the 2 wings which could be a great advantage. In other words this side controls a bigger terrain and thus this side gets more tempi on its terrain which could be a decisive advantage.

Of course wing locks patterns are also very very important but a great number of classical positions cannot be evaluated correctly if you ignore the 2 wings control notion.

[Rein Halbersma]

Rein, i still do not complete understand your algorithm.

In the position as given by Gerard, the black man on 1 can reach 6 and 7 (and no white man can do that, at least not in 1 move).
Same for the piece on 3 who can reach 9 in 1 move.
So in your definition does black control the fields/terrain 6, 7, and 9 ?

Do you consider only 1 move ahead (as after multiple moves the terrain you can reach is much larger?
And last bit not least are the bit shift you were mentioning the "more or less traditional" +5/+6/-5/-6 ?
Anyway , i find the topic quite interesting, but first need to understand the basics first

Bert

Hi Bert,

1) yes, squares 6,7 and 9 are controlled by black. In this position, I only indicated the "most advanced" squares for each color, but all squares behind it are also controlled by that color. In case there would be advanced edge pieces (on squares 15 or 16/6 for white) the algorithm also uses the other squares to know that advanced enemy outposts cannot advance any further.
2) I look 2 iterations ahead. Each iteration is a simultaneous move of both black and white pieces, with overlap of multiple pieces reaching a square resolved by majority rule. This algorithm works best in positions that are relativey "open" (little contact between the opposing pieces). With more than 2 iterations, the tactical complications make this algorithm too inaccurate. In closed positions such as Gerard's example, it might even be a better idea to only do 1 iteration. I should try that.
3) the shifts are indeed the "traditional" bit-shifts (which are 6 and 7 for my board because I have 2 ghost columns).

Rein

[Rein Halbersma]

I have several questions concerning the building of this diagram but let's begin by two basic ones:
1) How do you decide to assign square 16 to white?
2) Will the calculation of this diagram change if, in the original position, I move the white man on square 43 to the square 44 as in the following diagram:

1) White can reach square 16 in 2 moves (27-21-16) and black only in 3 (1-7-11-16), so 16 is assigned to white. If Black would have 1 on 7 already, 16 would be neutral, if 1 was on 11 already, 16 would be assigned to black. As soon as black actually reaches 16 in the search, square 21 becomes neutral (both white and black have 2 pieces adjacent to it).
2) The answer is "no", but I know it should be "yes". This is a weakness in the current algorithm.

How does your algorithm assign square 16 to black? Does it "see" that white cannot safely do 27-21-16?

Generally, there are several things that needs to be resolved to make this algorithm work:

1) determining whether a square can be "safely" reached first by a color: I use parallel bitshifts and majority rule to determine that
2) translating reachable squares to the maximally advanced position: this is the most tricky part because my current implementation does not take into account two crucial ingredients
a) left/right imbalance (the example of moving piece on 43 -> 44 is not correctly handled)
b) obstruction of own/enemy pieces (because I do simultaneous bitshifts)
3) assigning scores to current position and maximally advanced position: I used to simply count number of controlled squares and let each square count for 2 tempi, but now I think that N most advanced squares should count (for position with N pieces for each color)

I don't know how sensitive the playing strength is on these issues. I think that the dynamic search should take care of these subtleties: this is a static analysis and it's impossible to get it 100% right. Perhaps Ed can join the discussion as he has also implemented this algorithm but in a slightly different way.

Rein