Computer Draughts 2012

[Rein Halbersma]

I tried in the past to apply the MCP procedure but eventually I was not satisfied but I have to say that my search algorithm is based on MTD-f and not PVS. As a consequence the issue may be different for you?
I understood MCP was build only for CUT nodes because for these nodes the probability to prune after the MCP may be high. In the other hand the probability to prune after a MCP on an ALL node should be very low and I suspect it is not very efficient. Did you measure a real gain be including these ALL nodes?
Concerning a CUT node the MCP procedure seems interesting but it fails in a very common situation. Take a position which is really a CUT node because a (simple or complex) combination exists in this position. The MCP procedure will not work in this case and this procedure will appear as a waste of time.

I like Multi-Cut very much and it can also be done cheaply within the LMR framework. It's useful to regard Multi-Cut as "Early Move Pruning". So if you only keep an extra counter storing the number of LMR fail-highs so far, you can then simply return after the first C out of M moves have failed high on their LMR-reduced searches.

Your example of a single combination being present that will cause a fail-high should normally not give any trouble because if the reduced LMR search fails-high, the re-search to full depth will also (and cheaply because of the TT) fail high. The only possible problem is that the reduction is too deep for the combination to be detected, but then it will be detected in a later iteration. A nice property of LMR is that the reductions are roughly log(depth) * log(move_number) which are monotonically increasing in depth for any move_number. This means that every move will eventually be searched. So LMR is a correct search.

But this case above is not really the case that convinced me to not use the MCP procedure.
The key point for me is the surrounding strategies and in particular the strategies used against an opponent white 24 man (black 27 man). If you are white with a man on square 24 you may often see an advantage for white though black might have a good opportunity to surround white. If you apply the MCP procedure you will only confirm the advantage for white and you will miss the black strategy due to the reduction occurring in the MCP procedure. You mentioned Damage was not very strong with a white man 24. Don’t you think one reason could be the use of the MCP procedure?

I think the output 24/27 situation can best be dealt with through a semi-dynamic search (like SEE in chess), but it's pure speculation at this point and I would be interested in hearing anything that you have tried!

Rein

[Rein Halbersma]

Part III

Late Move Reductions, is applied during the Zero-Window PVS search for Non-PV nodes.
Basically the mechanism should be applied for ALL-nodes, but when the search enters this phase, most likely this condition is valid.
The actual implementation is given below:

Boundary condition for LMR:
* bPV is true (but i should probably omit this test, as i is most likely impossible here to have a PV-node ). (So discussing your own code helps, and forces me to re-check )
* Actual SearchDepth >= 3
* First 4 moves already searched with no LMR (the 4 is hardcoded, should I change that )
* No Capture possible (cant remember myself why i added/implemented this condition, so need to rethink) .
* The reduced search-depth SEARCH_LMR_DEPTHREDUCTIONFACTOR is 2 ply.
* the else iMWScore = iAlfa + 1 ; is a (maybe) non-elegant way in forcing a normal PVS-ZW search, and a normal re-search with the orginal search-depth in case no fail-low takes place.

In the code one can read, that damage also doesnt count a promotion as an extra ply.
The boolean bDDepth is true when the next search is 1 Ply less, and calculated as:

Code: Select all

bDDepth = !( iNMoves == 1 || iNewDepth == 0 ) ;

Hi Bert,

Again interesting to read your LMR implementation. Did you ever try the Stockfish type of depth reductions which scale like log(depth) * log(move_number)? It gives a much smoother curve than discontinuous jumps like depth>=3, move_number>=4, reduction=2 etc. Plus it is guaranteed to search every move eventually (which is nice to have if you are doing analysis).

Rein

[Rein Halbersma]

I do not really understand why it is important to avoid switching moves at the root. If two moves are quite identical then this switchling is only natural isn't it.
BTW granulartity is essential for Damy because I use the MTD-f procedure.

I agree it is good to have a somewhat coarse granularity. IIRC, Dam 2.2. uses the full 32-bit integer to express eval scores and its searches converge extremely slowly. It doesn't make sense to measure scores with that type of precision.

With Ed I have discussed some kind of generalized root driver that is a hybrid between aspiration-PVS and MTD. PVS is move-based (after a fail-low/high at the root, you first adjust the window, then move), whereas MTD is value-based (after a fail-low/high at the root, you first adjust the move, then window). I want to try using a priority queue of moves to be searched where I use a multi-criterion comparison function (e.g. based on depth, window, score). The search then simply iterates until time is up, pops the front of the queue to search, and then re-inserts the move into the queue with a new priority. Depending on the criterion you can then re-search the same node with a different depth/window, or search a different move with the same parameters etc.

This essentially replaces a nested multi-loop (depth, window, move number) and single-criterion comparison function (score), with a single-loop (move number) and multi-criterion comparison function (depth, window, score). I think it is much easier to experiment with the latter than the former (because interchanging loops is harder than adjusting a comparison function).

For your information my evaluation of a position is a one byte value; from -126 (loosing position) to +126 (winning position). The 3 values -128, -127 and +126 are reserved values used for different purposes.
I guess my evaluation have the same granularity of yours between -45 and +45 but outside this range I make a compression in the spirit of the logarithm function:
+65 correspond to your +100 (advantage of 1 man)
+79 correspond to your +200 (advantage of 2 men)
etc.
The calculation of the eval function is made in the "standard" format but, just before returning the result, the eval function compresses the result on one byte.
A side effect of this approach is that I gain rooms in the hash table!

I thought your hash entries were something like 40 bytes in the past? Have you changed to a compacter format? I'm remodelling 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).

Rein

[Rein Halbersma]

LMR is the last procedure I decided to abandoned, after having used it for about one year.
As you I did not apply reduction on moves leading to a capture, simply because such moves could be part of a combination.

How does your capture detection work with search reductions? Do you distinguish moves leading to "active" captures (e.g. after 38-32) from moves leading to "passive" captures (e.g. after 37-32)? I think it's more dangerous to reduce 37-32 than 38-32 in the above position, because 37-32 gives a free tempo to black.

[TAILLE]

Hi Rein,

LMR is the last procedure I decided to abandoned, after having used it for about one year.
As you I did not apply reduction on moves leading to a capture, simply because such moves could be part of a combination.

How does your capture detection work with search reductions? Do you distinguish moves leading to "active" captures (e.g. after 38-32) from moves leading to "passive" captures (e.g. after 37-32)? I think it's more dangerous to reduce 37-32 than 38-32 in the above position, because 37-32 gives a free tempo to black.

I do not quite understand your point.
Why do you think it is dangerous to reduce 37-32? I you think it is dangerous to give black a free move that means that you suppose 37-32 may be really a bad move. With this assumption:
If the reduced search confirmed 38-32 is a bad move everything is OK
If the reduced search finds that 37-32 is a good move that means a cutoff has been found where we expected a fail low result. In that case a research without reduction would take place and the 37-32 move will be correctly evaluated (i.e. it is a bad move).

[TAILLE]

I agree it is good to have a somewhat coarse granularity. IIRC, Dam 2.2. uses the full 32-bit integer to express eval scores and its searches converge extremely slowly. It doesn't make sense to measure scores with that type of precision.

With Ed I have discussed some kind of generalized root driver that is a hybrid between aspiration-PVS and MTD. PVS is move-based (after a fail-low/high at the root, you first adjust the window, then move), whereas MTD is value-based (after a fail-low/high at the root, you first adjust the move, then window). I want to try using a priority queue of moves to be searched where I use a multi-criterion comparison function (e.g. based on depth, window, score). The search then simply iterates until time is up, pops the front of the queue to search, and then re-inserts the move into the queue with a new priority. Depending on the criterion you can then re-search the same node with a different depth/window, or search a different move with the same parameters etc.

This essentially replaces a nested multi-loop (depth, window, move number) and single-criterion comparison function (score), with a single-loop (move number) and multi-criterion comparison function (depth, window, score). I think it is much easier to experiment with the latter than the former (because interchanging loops is harder than adjusting a comparison function).
Rein

That is exactly my approach.
I have root driver that decides which move has to be evaluated and what test value has to be taken for this move.
In some cases the root driver may effectively decide to research immediatly the same move but with another test value.
BTW I find easier and more efficient to analyse only one move (at the root position) at a time. In other words all my threads are always working on the subtree of the same move at the root position.

I thought your hash entries were something like 40 bytes in the past? Have you changed to a compacter format? I'm remodelling 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).
Rein

You are right Rein I changed my hash implementation. Now my entry in the hash table has 16 bytes including the value of the position as well as two boundaries. I am not quite sure that handling the two boundaries in the hash table is really a gain but that is another difficult subject.

[BertTuyt]

Rein, so far I used LMR as is, so I didnt modify parameters to find the optimum.

Although I know (and also studied Stockfish code, especially YBWC) i didn't remember the modification you mentioned.
But I need to take a look again to the Stockfish code.
It is really a huge pool of interesting ideas, recommended for everyone within the Draughts community to study.
But sometimes you only understand the beauty of implementation, when you are dealing with the topic yourself, and then you start to understand the intelligent choices being made....

Bert

[BertTuyt]

Part IV

In below table you find the Damage Search-time for a 19 ply Search as a function of FHR MCP and LMR.

To compare apples and pears with other programs, I will provide herewith the definition of an X ply search:
* In this overview (and also during the Kingsrow-Damage match), search extension mechanisms were switched off.
* If a position only has 1 legal move (mostly in case of a capture), the move is not considered as an additional ply.
* A promotion to king move is not counted as an additional ply.
* The normal search stops at ply depth 0, when the side to move has no capture and the opponent has no thread capture. So the position must be really quiet.
* Hereafter the Q-search starts, if the static evaluation does not exceed beta (sort of 0-move condition), and the position contains recognized "shot"-patterns (in the case of Damage, the base conditions for a 1 sacrifice - 2 capture shot). Only the moves which are based on these characteristics are tested.

Code: Select all

FHR	MCP	LMR	Time Sec.)	%	        F
0	  0	  0	  4554,9    100,0%          1,0
1	  0	  0	  1379,2    30,3%	        3,3
0	  1	  0	  202,6      4,4%	        22,5
0	  0	  1	  79,5       1,7%	        57,3
1	  1	  0	  83         1,8%	        54,9
1	  0	  1	  33,3       0,7%	        136,8
0	  1	  1	  18,3       0,4%	        249,2
1	  1	  1	  15,4       0,3%	        295,8

From the table it becomes clear that (at least in the current implementation) LMR and MCP ( as a good second) are by far the most important factors for the search time reduction.
In the end FHR adds to the equation although to a lesser extend than the other 2.

Bert

[BertTuyt]

In the most recent post i forgot to mention that the position used for the search comparison is the initial game position ( so black 1 - 20, white 31 - 50).

Bert

[BertTuyt]

In a previous post I mentioned that the sequence of reduction mechanisms is MCP - FHR - LMR.
I already questioned if it doesn't make sense to start with FHR.
I did a quick test and (more or less) to my surprise the search time for a 19 ply search reduced from 15.4 sec to 8.7 sec !
As I didn't use this modification so far in actual 158 game match, I have no idea to what extend this yields improvement and if it affect robustness/reliability of the search.
Nevertheless less than 10 sec for a 19 ply is not that bad......

Bert

[TAILLE]

Hi Bert,

In a previous post I mentioned that the sequence of reduction mechanisms is MCP - FHR - LMR.
I already questioned if it doesn't make sense to start with FHR.
I did a quick test and (more or less) to my surprise the search time for a 19 ply search reduced from 15.4 sec to 8.7 sec !
As I didn't use this modification so far in actual 158 game match, I have no idea to what extend this yields improvement and if it affect robustness/reliability of the search.
Nevertheless less than 10 sec for a 19 ply is not that bad......

Bert

The figure of about 10" to reach ply 19 is interesting because it gives a indication concerning the reduction level used by the program but objectively its meaning is very unclear.
By introducing a very agressive (and stupid?) reduction we are all able to reach ply 19 in a fraction of second. I suspect such program might be very strong in certain situations but very weak in others and the global result is quite uncertain.
So far the only good measure seems to be a "standard" 158 games (or more?) against another program like Kingsrow. Maybe somebody have other ideas to give an evaluation of the strength of a program but I do not like very much the time to reach ply 19 under reduction mechanism.

[Rein Halbersma]

How does your capture detection work with search reductions? Do you distinguish moves leading to "active" captures (e.g. after 38-32) from moves leading to "passive" captures (e.g. after 37-32)? I think it's more dangerous to reduce 37-32 than 38-32 in the above position, because 37-32 gives a free tempo to black.

I do not quite understand your point.
Why do you think it is dangerous to reduce 37-32? I you think it is dangerous to give black a free move that means that you suppose 37-32 may be really a bad move. With this assumption:
If the reduced search confirmed 38-32 is a bad move everything is OK
If the reduced search finds that 37-32 is a good move that means a cutoff has been found where we expected a fail low result. In that case a research without reduction would take place and the 37-32 move will be correctly evaluated (i.e. it is a bad move).

OK, I get your point. But if moves like 37-32 are often bad, it's a waste of time to do both a reduced and a full depth search.

But my question still stands: when you were experimenting with LMR, did you distinguish between moves like 37-32 (leading to capture thread for white) and moves like 38-32 (leading to immediate capture by black)? If so, did you do LMR on both of them, or only one of them or neither of them? More generally, what kind of distinction did you make fo rmoves leading to captures?

Rein

[Rein Halbersma]

That is exactly my approach.
I have root driver that decides which move has to be evaluated and what test value has to be taken for this move.
In some cases the root driver may effectively decide to research immediatly the same move but with another test value.
BTW I find easier and more efficient to analyse only one move (at the root position) at a time. In other words all my threads are always working on the subtree of the same move at the root position.

That's great to hear that you already use this approach, because I had never seen this in open source programs and I wondered if it was a good direction to experiment with. It's the second time that you independently used a method that I also was thinking about. 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. So it's good that the fruitful exchange of ideas on this forum has confirmed two ideas already for me

Rein

[TAILLE]

How does your capture detection work with search reductions? Do you distinguish moves leading to "active" captures (e.g. after 38-32) from moves leading to "passive" captures (e.g. after 37-32)? I think it's more dangerous to reduce 37-32 than 38-32 in the above position, because 37-32 gives a free tempo to black.

I do not quite understand your point.
Why do you think it is dangerous to reduce 37-32? I you think it is dangerous to give black a free move that means that you suppose 37-32 may be really a bad move. With this assumption:
If the reduced search confirmed 38-32 is a bad move everything is OK
If the reduced search finds that 37-32 is a good move that means a cutoff has been found where we expected a fail low result. In that case a research without reduction would take place and the 37-32 move will be correctly evaluated (i.e. it is a bad move).

OK, I get your point. But if moves like 37-32 are often bad, it's a waste of time to do both a reduced and a full depth search.

But my question still stands: when you were experimenting with LMR, did you distinguish between moves like 37-32 (leading to capture thread for white) and moves like 38-32 (leading to immediate capture by black)? If so, did you do LMR on both of them, or only one of them or neither of them? More generally, what kind of distinction did you make fo rmoves leading to captures?

Rein

Hi Rein,
The main points of my LMR implementation were the following :
1) LMR can only take place on a move expected to be a bad move.
2) a move potentially as part of a combination is not considered a bad move
3) The decision to reduce is made after the captures

Taking you diagram white has 5 moves
38-33, 38-32, 37-32, 31-36 and 47-41
Due to point 3 above I consider in really the 5 following “super moves”
38-33
38-32 27x38 42x33
37-32
37-31 27x36
47-41
What about point 2 above? After the “super move” 37-31 27x36 it is still to white to play; thus I consider this super move could be part of a combination and it will not be reduced at this stage.
It remains 4 super moves which will be analyzed taking into account point 1.

Suppose you consider that white root position is difficult for white and the test value is for example -20. That means that only the super moves leading to a white value lesser than -20 could be reduced.
Finally you will decide what means for you “late” reduction i.e. which number of super moves you will not be reduced.

Of course a multi capture positions is more complex to analyze but the idea is the same. As soon as your reduction strategy is clear in your mind you will always find an good approach for programming won’t you?

[Rein Halbersma]

BTW I find easier and more efficient to analyse only one move (at the root position) at a time. In other words all my threads are always working on the subtree of the same move at the root position.

This is an interesting remark. A single-threaded root driver calling a parallel MTD combines the best of both worlds, because you can do the window updating without having to pass it to the many threads searching subtrees.

One thing that I would need to resolve with MTD is getting a PV back efficiently. With PVS, I simply pass an extra array that collects this whenever alpha is improved. I also experimented doing this on non-PV nodes and the overhead wasn't too bad, so perhaps I can make it work. The alternative is always doing the PV variation in a single thread, but that would probably kill too much of the parallel gains.