Parallel search

[BertTuyt]

Ed, your result challenged me to find the cause of the measured time difference between Damage and KingsRow.

This morning ( Sunday 25-January), I did a similar test, but now with the MCP (Multi-Cut-Pruning) deactivated.

The minimum time i recorded now was 4.88 sec.
However I see some "search-instability" in 2 areas.

1) Sometimes the program needs 1 ply more 25Ply or 26Ply.
2) And for a given Ply-Depth ( 25 or 26) I see difference in the time needed to solve the position: 25Ply 4.88 sec - 9.05 sec, 26Ply: 10.72 sec - 15.48sec).

Do you see the same "instability" with the same "order of magnitude?

Next to that I still have the feeling that when exact values are mixed with artificial, this has consequences for the alfa-beta implementation.
Otherwise stated I believe that when using exact values, some additional tricks are possible, which you don't use in the "normal" alfa-beta framework.

Example: in case the starting position is a database-position, and all the nodes visited have exact values. Also assume that the starting position is not a Draw (then you don't need a search-process).

If in between you "see" a Draw-value, you can stop the search from that point directly. I implemented this, so I check database-value at every node.

The search values will increase with increasing depth in case of a Win , and decrease in case of a Loose. So starting alfa and beta can already be modified for this. As I don't have DTW or DTC Databases only WDL, I need a "mechanism" to guide the search. For this reason I include in the database-value total piece count and material-difference. In this way the program is "motivated" to reduce the complexity in the position. Although this reduction will not always bring the absolute Win within the search-horizon, It helps to find a path towards this goal.

If you see a hash-table entry with a value >= beta but search depth > hash-depth, you "normally" only use the hash-move as a starting point. But if you know that when going "deeper" values only will further increase, you could already stop here.

I think there are many more issues related to the mix of exact and calculated values, maybe you have also some "tricks".

Bert

[TAILLE]

Ed, damage takes 29.2 sec. (examining around 144406604 positions, 4.9 MNodes/sec. ).

So room for optimization.

Im interested what the score is of the other programs ?

Bert

Hi Bert, Ed
I cannot answer Bert question because I do not need such optimised functionnality in Damy. My approach is totaly different.
First of all I stored on the disk all DTC tables with 6 kings or more so let's take a position with 5 kings as a maximum. For example the following one from the 7 pieces endgame database.

White to move

The WLD table tells us that there are 2 winning moves : 15-29 and 15-24. How Damy will choose between them ? I launch 2 theads (I only have a dual core), one will try and search the next conversion and the other will build the complete DTC table corresponding to the position of the men. In a real game with let'us say only 10 or 20 seconds for each move, Damy will be forced to choose a move before having solved the problem. In that case it will choose one of the two winning moves, by chance. But here is the interesting point : the second thread continue to build the DTC table on the time of the opponent move and on the following moves if necessary.
In this example the second thread will finish the job in less that 2 minutes; that means that after 3 or 4 moves Damy will be able to definitly play the best moves.
For your information the DTC values for 15-29 and 15-24 are 100 and 104 plies respectively.

Gérard

[BertTuyt]

Gerard,

interesting approach to build the DTC table during game-play.
Do you do that for all positions or only when the "specific" DTC table is not available ( example > 6 pieces)?

What's your record DTC value you have found so far?

Bert

[Ed Gilbert]

Bert, my quad core is tied up with other calculations now so I cannot test the repeatability of that search. I don't think I typically see as much variation as you have on endgame searches, but I could be wrong.

You can see from my search log that I also form an endgame eval score for db positions that encourage progress towards the win. It is important that these eval scores work in harmony with other heuristic scores for non-db positions. Unlike this test position, most searches will have a mix of both types. In kingsrow I use values 0 - 2000 for non-db positions, and 2000 - 4000 for db wins. The values from 3950 - 4000 are reserved for positions where the game is over. For these I return (4000 - search depth).

-- Ed

[TAILLE]

Gerard,

interesting approach to build the DTC table during game-play.
Do you do that for all positions or only when the "specific" DTC table is not available ( example > 6 pieces)?

What's your record DTC value you have found so far?

Bert

Hi Bert
Of course I build the DTC table only if the "specific" DTC table is not available.
Because I calculated DTC tables only for positions with 6 or more kings, I do not know the record DTC value for the 7 pieces endgame data base.
I remember that Ed. mentionned the following one :


White to move

After having generated the corresponding DTC table, Damy found a DTC value equal to 107 plies.

Due to the 25 moves rule this position is, as consequence, a draw. It's a pity but it's life.

Gérard

[Rein Halbersma]

Gerard,

interesting approach to build the DTC table during game-play.
Do you do that for all positions or only when the "specific" DTC table is not available ( example > 6 pieces)?

What's your record DTC value you have found so far?

Bert

Hi Bert
Of course I build the DTC table only if the "specific" DTC table is not available.
Because I calculated DTC tables only for positions with 6 or more kings, I do not know the record DTC value for the 7 pieces endgame data base.
I remember that Ed. mentionned the following one :


White to move

After having generated the corresponding DTC table, Damy found a DTC value equal to 107 plies.

Due to the 25 moves rule this position is, as consequence, a draw. It's a pity but it's life.

Gérard

Suppose you play this in a computer tournament where your opponent does not have the 7 piece db. Would you give a draw? Or would you play until you have done 25 moves each and then give a draw? What should a referee decide? (if this position happens at move 65 e.g. , then you only have 10 moves before arbitration!)

Rein

[TAILLE]

Suppose you play this in a computer tournament where your opponent does not have the 7 piece db. Would you give a draw? Or would you play until you have done 25 moves each and then give a draw? What should a referee decide? (if this position happens at move 65 e.g. , then you only have 10 moves before arbitration!)

Rein

Hi Rein,

Damy will continue to play, choosing the best move according to DTC table, and Damy will stop to play after 25 moves without any conversion.

Concerning the decision of a referee I am not able to answer the question but I am interested with the answer because it is obvious, in such situation, that we will reach the 75th move before reaching the 25th move without any conversion.

Gérard

[Ed Gilbert]

Hi Gerard,

I am curious about your motivation for computing the dtc info 'on the fly' for some positions while having it already computed on disk for others. Why not precompute them for all endgame positions and avoid the search-time complexity? What does Damy do if it finds itself running on a single-core computer? I have the dtc info for 2 - 7 piece positions (except 6x1) and almost 1/4 of the 8 piece positions and it consumes only 9gb of disk space. I'm not storing info for positions with dtc values less than 10 plies. This excludes most positions which explains the small size. There is not much use for this data as the normal search can easily find the path to these conversions.

As a practical matter, I don't think the dtc databases are necessary to properly play out endgames. Somewhere earlier in one of these threads I reported on a test game using the longest 5k vs. 3k dtc position. I set up a game between 2 instances of kingsrow, with the dtc enabled version playing the losing side and the winning side played with only WLD info. The winning side was able to finish the game with only a couple of minor mis-steps. I think that conversion heuristics might be sufficient to guide the game to a successful conclusion in nearly all cases.

BTW, I have the plane tickets for Paris, so kingsrow's participation in the May tournament is assured. I don't have hotel reservations yet. Sometime soon I will get myself a gmail account so we can exchange emails, as both my verizon and prodigy email accounts use the same ATT mail servers which consistently reject email from your domain.

-- Ed

[TAILLE]

Hi Ed.

I am curious about your motivation for computing the dtc info 'on the fly' for some positions while having it already computed on disk for others. Why not precompute them for all endgame positions and avoid the search-time complexity?

My motivation is only to gain time during endgame generation process. By avoiding calculating the DTC tables I can build a faster algorithm to build only the WLD tables. It may not be relevant for the 7 pieces endgames db but it may be more interesting for 8 or more pieces.
You can also imagine that building a DTC table when WLD table is already built does not imply a complex algorithm.
For Damy a DTC table is very simple. There no compression because it is only a table with one byte per position index.

Of course your appraoch is very correct. It is only another way to solve the problem.

What does Damy do if it finds itself running on a single-core computer?

I do not see a reason to run Damy on a single processor. On the contrary, I will look for running Damy on 4 or 8 processors.
If I really need to have a version of Damy using only one processor I think I will calculate only the DTC table and play according to WLD tables till the end of DTC table generation.

BTW, I have the plane tickets for Paris, so kingsrow's participation in the May tournament is assured. I don't have hotel reservations yet. Sometime soon I will get myself a gmail account so we can exchange emails, as both my verizon and prodigy email accounts use the same ATT mail servers which consistently reject email from your domain.

Very good news indeed.

Gérard

[Ed Gilbert]

Hi Gerard,

In one respect your method is better, because you learn the exact dtc values, where I learn values that are either exactly correct or off by one ply. I am simply saving off the dtc information as I build WLD databases, but I think it is imprecise, although good enough to play the correct moves. During WLD builds, I first do two conversion passes, one black-to-move and then a white-to-move pass, where I resolve all captures and man moves. Then I do a series of non-conversion passes. The first non-conversion pass resolves some btm positions, and these positions get saved as dtc 1. The next non-conversion pass resolves some wtm positions, and these get saved as dtc 2, but in fact some of these will be dtc 1 if the btm successor position along the pv is a conversion move. I do not distinguish between the two possibilities. On each iteration this uncertainty of +0, -1 plies exists. So my data has this small uncertainty. But on the positive side, it is no extra work to compute this data, it is essentially a free side effect of building the WLD db.

-- Ed

[TAILLE]

Hi Gerard,

In one respect your method is better, because you learn the exact dtc values, where I learn values that are either exactly correct or off by one ply. I am simply saving off the dtc information as I build WLD databases, but I think it is imprecise, although good enough to play the correct moves. During WLD builds, I first do two conversion passes, one black-to-move and then a white-to-move pass, where I resolve all captures and man moves.

Up to this point it is the same for Damy

Then I do a series of non-conversion passes. The first non-conversion pass resolves some btm positions, and these positions get saved as dtc 1. The next non-conversion pass resolves some wtm positions, and these get saved as dtc 2, but in fact some of these will be dtc 1 if the btm successor position along the pv is a conversion move. I do not distinguish between the two possibilities. On each iteration this uncertainty of +0, -1 plies exists. So my data has this small uncertainty. But on the positive side, it is no extra work to compute this data, it is essentially a free side effect of building the WLD db.
-- Ed

From this point our algorithms are different :
I do a serie of non-conversion passes looking only to new losing positions. Each time I found such losing position I marked all non resolved predecessors as winning positions and I continue the pass.
When no more losing positions are found all remaining positions are marked as draw positions. With this approach the number of passes may be far lesser than the worst DTC value but I cannot estimate the expected gain.

Gérard

[BertTuyt]

As I don't use (and or have) Distance-to-win databases, i need some help here.
In the next diagram, with white to move, what is the smallest DTW, and what is the DTW for 5-10 and 46-41 ?
If some-one could give me also the shortest win-path I would appreciate this.

<img src="http://fmjd.org/dias2/save/12341300845.png">

Thanks

Bert

[ildjarn]

As I don't use (and or have) Distance-to-win databases, i need some help here.
In the next diagram, with white to move, what is the smallest DTW, and what is the DTW for 5-10 and 46-41 ?
If some-one could give me also the shortest win-path I would appreciate this.

<img src="http://fmjd.org/dias2/save/12341300845.png">

Thanks

Bert

DTW for 5-10 is 6, DTW for 46-41 is also 6.

Shortest win is 6 (between {} equal-length moves) :
1. 05-10 { 23-18, 23-29, 23-32, 26-31, 26-37, 26-42, 46-41 } 39-44 { 39-50, 39-43, 39-33, 39-22, 39-11, 39-06, 39-30, 39-25} 2. 10-04 { 10-15, 23-18, 23-29, 23-41, 26-37 } 44-50 { 44-49, 44-39, 44-33 } 3. 23-18 { 23-32, 23-37, 26-31, 26-37 } 50-45 4. 18-13 { 26-37, 46-23 } 45-50 { 45-40, 45-34, 45-29, 45-07, 45-01 } 5. 46-28 50x09 6. 04x13 { 04x18, 04x22, 04x27, 04x31, 04x36 }

[BertTuyt]

The i7 940 (2.93 GHZ) is a quad-core processor with the re-introduction of multithreading.
So to the "outside" world the processor appears to have 8 virtual/logical cores, in reality 4 physical cores.

As Damage automatically detects (and use) the number of available cores/processors, I did a small test to measure the potential speed-up.

The search-algorithm I used was based on the YBWC.

The Results:

Cores MNodes/Sec
1 2.7
2 4.6
3 6.2
4 7.7
5 8.7
6 9.6
7 10.2
8 10.6

So one clearly sees that after 4 cores the speed-increase reduces , but going to 8 cores is still interesting as it is 38% faster!

Also worth to mention the max-speed detected , over 10 MNodes/sec !!!

Bert

[BertTuyt]

Forgot to mention that the mentioned speeds were based on a 17ply search from the initial position.

Bert