3-move ballots

[Rein Halbersma]

Rein,

you can take the move sequence as an integral plan from the perspective of black. If next tot that you execute these plan moves first, without changing remaining search-depth, then you will immediately start with the 3 positions as you described.

Then the search will see a win for the first position, so confirming the game plan, for the other 2 positions it will find a draw.
If the initial score is negative from the perspective of black (for position 2 and 3), reason to stick to this plan (as it will give a sure draw).
In case blacks position is slightly better, the program will look for alternatives.

I guess there is some old literature available for computer chess to work with (min)plans.
As shared in an earlier post, all these ideas were abandoned due to the straightforward suc6 of alpha-beta .

But I might consider it in a next Damage Engine....
Do other engines work with mini-plans ??

Bert

Mini-plans sounds like a good idea, but you have to be pretty sure (in a statistical sense) that you can combine many move sequences into super moves. Another direction I'd like to explore some day is Monte Carlo search.

[BertTuyt]

Rein, also in the Raichenbach example, the program clearly identifies relatively quickly the right move 38-33 with a huge advantage for white.
The challenge is to find the moves belonging to an overall plan without search depth sacrifice.

Bert

[BertTuyt]

Yep Monte Carlo is now the big thing in GO !!
Do you have literature where search and mini-plans are combined??

Bert

[Rein Halbersma]

Yep Monte Carlo is now the big thing in GO !!
Do you have literature where search and mini-plans are combined??

Bert

The Games Group at UAlberta (of Chinook fame) did a project on Sokoban in the 90s. They used a lot of the macro-move ideas that you described. You might try to google for it.

[Ed Gilbert]

So after a hard days night , and 50.000 seconds later at ply 29 my program finds the right move (already somewhat earlier :) ) , but still with a relatively small positive score.
Are there other programs out there, who see immediate the 18-23 move with a huge score?
At least after the move sequence , as described by Rein, Damage sees the DB-win.

Not really. After 791 seconds, kingsrow gets to depth 26 with a search score of 24. I was not present when it passed depth 27. It got to depth 28 at 7995 seconds and a search score of 84. It likes 18-23 almost immediately, but of course that could just be luck. This is using 3 threads on the Q6600, and the 7pc db, because that is how it happened to be configured at the time I started the search.

-- Ed

[TAILLE]

Hi,


Black to move

If hou have a problem with this position that means you a have a problem with your eval function.
Due to the presence of white man 28 and black man 18 Damy do not see any advantage for black in this initial position.
After 1...18-23 2.28x19 14x34 3.40x29 we reach the following position


Black to move

and the situation has changed dramatically because now the Damy evaluation function is able to detect a significant advantage for black be removing defence and attack against white man 24 and be using the arrow 13-8-2 against 24.
That means that 1...18-23 is chosen immediatly by Damy and the score gets better and better with deeper analysis.

Let's now suppose your evaluation of the white 24 outpost is not that sophisticated because you prefer to rely on speed and deep search rather than on a sophisticated evaluation. In that case we will surely reach the following position


white to move

If you cannot reach this position you need certainly to improve your search algorithm. In Damy I implemented a forcing move detection in order to extend a little the search.

If your evaluation function is now able to detect a significant advantage for black then everything is OK and you will chose the 1...18-23 move. If not change your program!

It does not matter for me if the initial position is a win or not. Even if you manage to prove that the last diagram is a win for black you do not have proved that black will win after 1...18-23 2.28x19 14x34 3.40x29 10-14 4.41-37?!

If, in the initial position, you change the position of black man 11 then the intial position may become a draw position but in this case there is no harm to chose again 1...18-23 is it?

[Rein Halbersma]

It does not matter for me if the initial position is a win or not. Even if you manage to prove that the last diagram is a win for black you do not have proved that black will win after 1...18-23 2.28x19 14x34 3.40x29 10-14 4.41-37?!

If, in the initial position, you change the position of black man 11 then the intial position may become a draw position but in this case there is no harm to chose again 1...18-23 is it?

Gerard,

I agree with all your points. 18-23 gives a forcing sequence to a favorable position which is at least a draw and likely more. There is hardly any risk of losing for black. So one could add a pattern in the eval or an extension based on this pattern in the search.

However, 18-23 also commits black to the forcing sequence. There might be other (better) plans (maybe not in this position). E.g. in the Raichenbach examples, the plan is not to exchange 13-19x19 but to use 13-18 in combination with a black piece on <22>. The question is can you program also the interaction between such long range plans using eval patterns and search extensions?

Rein

[TAILLE]

It does not matter for me if the initial position is a win or not. Even if you manage to prove that the last diagram is a win for black you do not have proved that black will win after 1...18-23 2.28x19 14x34 3.40x29 10-14 4.41-37?!

If, in the initial position, you change the position of black man 11 then the intial position may become a draw position but in this case there is no harm to chose again 1...18-23 is it?

Gerard,

I agree with all your points. 18-23 gives a forcing sequence to a favorable position which is at least a draw and likely more. There is hardly any risk of losing for black. So one could add a pattern in the eval or an extension based on this pattern in the search.

However, 18-23 also commits black to the forcing sequence. There might be other (better) plans (maybe not in this position). E.g. in the Raichenbach examples, the plan is not to exchange 13-19x19 but to use 13-18 in combination with a black piece on <22>. The question is can you program also the interaction between such long range plans using eval patterns and search extensions?

Rein

What is your point Rein?
Though 18-23 seems to give a immediat advantage to black (according to the eval function) a deeper analysis might reveal a move leading to a better advantage or might reveal that 18-23 is not as good as it looks isn't it?

[BertTuyt]

Gerard,

do you have such a (debug) option to trace if a specific position has been found/reached...
I guess that you have typically implemented these things we are just discussing.
And apparently we are not yet successful.
Within this context, any news about Damy matches with KingsRow??

Bert

[TAILLE]

Gerard,

do you have such a (debug) option to trace if a specific position has been found/reached...
I guess that you have typically implemented these things we are just discussing.
And apparently we are not yet successful.
Within this context, any news about Damy matches with KingsRow??

Bert

Hi Bert,

It is indeed very easy to know if a position has been reached during a search:
In debug mode you have a lot of possibilities and for example you can trace each time you access (read or/and write) the hash table with the hashkey of the position
In release mode I only can look in the hashtable whether or not the corresponding entry has been created (as soon as I put on the board a given position I have a function that gives me the cotent on the hashtable).
No match for the moment with Kingsrow: I do not have finish the handling of all outposts and I need some more work on dynamic evaluation. Concerning the handling of kings it is almost finished and I intend (certainly in March) to run 2-move ballots against Kingsrow beginning with the two following positions:



Depending of the result I will see if I need some other thematic matchs.

Did somebody already experiment thematic matchs?

[TAILLE]

Mini-plans sounds like a good idea, but you have to be pretty sure (in a statistical sense) that you can combine many move sequences into super moves. Another direction I'd like to explore some day is Monte Carlo search.

Hi Rein,

Compare to the go tree, the draughts tree is very very thin. Do you really think the Monte Carlo search could be efficient in draughts?
In do not use mini-plans but I have now a quite efficient extension mechanism for forcing moves.

As a consequence it takes less than 2 minutes for Damy to reach the second diagramme above

[Rein Halbersma]

Mini-plans sounds like a good idea, but you have to be pretty sure (in a statistical sense) that you can combine many move sequences into super moves. Another direction I'd like to explore some day is Monte Carlo search.

Hi Rein,

Compare to the go tree, the draughts tree is very very thin. Do you really think the Monte Carlo search could be efficient in draughts?
In do not use mini-plans but I have now a quite efficient extension mechanism for forcing moves.

As a consequence it takes less than 2 minutes for Damy to reach the second diagramme above

HI Gerard,

I don't know how Monte Carlo draughts will do. Perhaps alpha-beta is superior, who knows. From my limited knowledge of that literature, it seems that there is at least much more potential to exploit parallelism.

Very impressive extension mechanism! Can you tell what the nominal search depth was that was required to reach the 2nd diagram? Also, can Damy see the move 34. 38-33! from Raichenbach-Springer already on white's 20th move? How long/deep does it have to think/search for it?

Rein

[TAILLE]

Mini-plans sounds like a good idea, but you have to be pretty sure (in a statistical sense) that you can combine many move sequences into super moves. Another direction I'd like to explore some day is Monte Carlo search.

Hi Rein,

Compare to the go tree, the draughts tree is very very thin. Do you really think the Monte Carlo search could be efficient in draughts?
In do not use mini-plans but I have now a quite efficient extension mechanism for forcing moves.

As a consequence it takes less than 2 minutes for Damy to reach the second diagramme above

HI Gerard,

I don't know how Monte Carlo draughts will do. Perhaps alpha-beta is superior, who knows. From my limited knowledge of that literature, it seems that there is at least much more potential to exploit parallelism.

Very impressive extension mechanism! Can you tell what the nominal search depth was that was required to reach the 2nd diagram? Also, can Damy see the move 34. 38-33! from Raichenbach-Springer already on white's 20th move? How long/deep does it have to think/search for it?

Rein

Hi Rein,

Though I do not like alpha-beta, for draughts game, I consider alpha-beta superior to Monte Carlo even if I agree Monte Carlo allow better parallelism.

Oops, I do not know how I can answer your question on the nominal search depth I used to reach the 2nd diagram because this “nominal search depth” does not exist in Damy implementation for a simple reason: I manage something I could call “virtual depth”; suppose a value N for the “virtual depth” of a given node. Damy calculate what will be the “virtual depth” of the different successors. In general the supposed best move will be attributed the “virtual depth” N-2 and the other moves the value N-3. In certain conditions a successor may receive other values (N, N-1, N-3, N-4 or even 0). To answer your question on my search depth required to reach the second diagram I used the figure 36 for the initial “virtual depth”.

Your question concerning the Raichenbach-Springer game is not that clear. Do you consider that 34.38-33 is a winning move? What about the positional sacrifice 34…20-24 35.29x20 10-15 36.45-40 15x24 37.40-34 8-12 38.33-29 24x33 39.39x8 3x12
In addition the black moves preceding 34.38-33 are not forced are they?

[BertTuyt]

Gerard regarding your remark:

Though I do not like alpha-beta, for draughts game

Which algorithm do you like best.
And do you have a quantitative comparison with alpha-beta...

Bert

[TAILLE]

Gerard regarding your remark:

Though I do not like alpha-beta, for draughts game

Which algorithm do you like best.
And do you have a quantitative comparison with alpha-beta...

Bert

Hi Bert,

After many hesitations between "MTD-f" and "MTD-f best" I eventually reached the following conclusion:
1) For running a game the "MTD-f best" have my preference (it is definitely my choice for Damy)
2) For solving a problem (i.e. for proving a win) the "MTD-f" algorithm might be better

I do not have any comparaison with alpha-beta.

I used this alpha-beta procedure about 7-8 years ago but I changed my mind after having studied the MTD-f algorithm and after having discovered that the MTD-f algorithm seems simply the natural algorithm used by the humans!!!
If a human considers he has a advangeous position (e.g an evaluation of +30 for a computer) then when analysing the different suites he will naturally eliminate all suites leading to a smaller advantage etc. etc. which is exactly the MTD-f algorithm!
To go further I even think that a human used basically the MTD-f best algorithm.
The alpha-beta seems a pure computer approach never used by a human. The theoritical basis for the alpha-beta algorithm is very sound but it leads to a lot af calculation and thus cannot be efficient. A great progress has been made by the use a zero-wide-windows which is a big step towards the MTD-f algorithm isn't it? Even with this great progress the humans still don't use this algorithm.
I cannot prove alpha-beta is less efficient that MTD-f best approach (and it is not my goal to prove it!) but my feeling is that the human approach should be the best one.
I always try to imitate the human approach and in this context I added some major improvments (?) to the MTD-f best algorithm itself, like the "virtual depth" I mentionned earlier: along a given variant a human will typically used a lot of time for the considered best move and far less time on the other moves. That is exactly what I do in Damy with my "virtual depth".