Search Algorithm

[BertTuyt]

Rein, we all know that parallel search does not scale perfectly.
On the other hand number of cores tend to increase.
So one of my thoughts, (and I very briefly tested it, but without going deeper into it), is to use several search algorithms.
With an arbiter, one can then chose the best move.
In case one search is very effective in finding win/lose values, or combinations, the task of the arbiter should be simple.
It is basically the same as Dreihirn , but then with the computer making move choices.

Bert

[TAILLE]

Rein, we all know that parallel search does not scale perfectly.
On the other hand number of cores tend to increase.
So one of my thoughts, (and I very briefly tested it, but without going deeper into it), is to use several search algorithms.
With an arbiter, one can then chose the best move.
In case one search is very effective in finding win/lose values, or combinations, the task of the arbiter should be simple.
It is basically the same as Dreihirn , but then with the computer making move choices.

Bert

Hi,

I agree with you Bert.

Two main issues tell me to study other approaches:
1) With the increasing of the core numbers the parallel search tends to be less efficient
2) Depending of the phase of the game (the beginning, the middle or the end) the best algorithm may change.

In addition the increasing of memory available allows us to use of new algorithms that could be far more efficient than the classical alpha-beta or MTD-f procedures.

All that are not very clear in my mind but I know that dramatic changes will occur in Damy in the next months.
For the time being I explore an approach in which I store a huge tree instead of handling a huge hashtable. Obviously that will facilitate parallel searches and that will also allow the use of evaluation depending of history (typically you can reduce an advantage depending of the the number of moves made without conversion).
As a consequence a position will also be explore several time but it may happen that it will be compensate by a better use of a many cores.

BTW the figures I give you to resolve the position proposed corespond to an algorithm which does not use an hashtable.

[Catherine]

Hi dear programmers

I followed with a particulary attention all wrote about this new algorithm approach.
I will be glad to know what major difference Mr Taille obtain with his new algorithm compared to classical alpha-beta and Mtd.
For me all prodrammer research before an algorithm wich can find the best move, alpha-beta isn't the best and logical way to get it?
with a solid and stable evaluation algorithm based on alpha beta and parallele search can create a strong program.
I want to say that, trying to built an algorithm thinking like a human, can't be stronger than another with the pure logical alpha beta algorithm.
Human have theire way to play draughts and for me, It's not more logical and deeper than for a program.

[TAILLE]

Hi dear programmers

I followed with a particulary attention all wrote about this new algorithm approach.
I will be glad to know what major difference Mr Taille obtain with his new algorithm compared to classical alpha-beta and Mtd.
For me all prodrammer research before an algorithm wich can find the best move, alpha-beta isn't the best and logical way to get it?
with a solid and stable evaluation algorithm based on alpha beta and parallele search can create a strong program.
I want to say that, trying to built an algorithm thinking like a human, can't be stronger than another with the pure logical alpha beta algorithm.
Human have theire way to play draughts and for me, It's not more logical and deeper than for a program.

Hi Catherine,

To answer your question the major difference I obtain is simply that my new algorithm can resolve the position I proposed.
My standars MTD-f procedure do not find the good move even after 30 minutes.
The reason is for me quite simple : the pruning mechanism is not efficient enough with the MTD-f procedure and it is the same with the alpha-beta procedure.
Of course it is only my own view. I understand you consider alpha-beta is the best algorithm and I will not try to convince you to give up this algorithm!

BTW noboby tells me the time needed to "prove" the win in the position I proposed. I only noted a figure for Kingsrow telling us the time needed to find a correct sequence but does that mean that the win is completely proved?

[Rein Halbersma]

BTW noboby tells me the time needed to "prove" the win in the position I proposed. I only noted a figure for Kingsrow telling us the time needed to find a correct sequence but does that mean that the win is completely proved?

My engine does not have the 8 pc databases, so it will not find the win. I am more interested in the details of your algorithm. How does it work exactly?

[TAILLE]

BTW noboby tells me the time needed to "prove" the win in the position I proposed. I only noted a figure for Kingsrow telling us the time needed to find a correct sequence but does that mean that the win is completely proved?

My engine does not have the 8 pc databases, so it will not find the win. I am more interested in the details of your algorithm. How does it work exactly?

Hi Rein,

Yes, without the 8 db it seems very difficult to resolve this problem.
I noted that you have doubts regarding the usefulness of these new search algorithms designed to solve particular endgames. Certainly you are right. For the moment being my algorithm is build only to resolve difficult endgames but I will let you know if I see some good ideas to extend this algorithm to other part of the game.
Anyway If we want to compare our algorithms we need to exchange some results concerning performance.
I know that some programs are build only to find the best move without trying to prove the win (it is the case with my previous Damy version). For those programs able to prove a win here is an easier position


White to play

How many time do you need to prove the win?
Note I am not really interested by the time needed to find the winning move!

[Rein Halbersma]

BTW noboby tells me the time needed to "prove" the win in the position I proposed. I only noted a figure for Kingsrow telling us the time needed to find a correct sequence but does that mean that the win is completely proved?

My engine does not have the 8 pc databases, so it will not find the win. I am more interested in the details of your algorithm. How does it work exactly?

Hi Rein,

Yes, without the 8 db it seems very difficult to resolve this problem.
I noted that you have doubts regarding the usefulness of these new search algorithms designed to solve particular endgames. Certainly you are right. For the moment being my algorithm is build only to resolve difficult endgames but I will let you know if I see some good ideas to extend this algorithm to other part of the game.
Anyway If we want to compare our algorithms we need to exchange some results concerning performance.
I know that some programs are build only to find the best move without trying to prove the win (it is the case with my previous Damy version). For those programs able to prove a win here is an easier position


White to play

How many time do you need to prove the win?
Note I am not really interested by the time needed to find the winning move!

It takes Kingsrow less than one second to find 8-2!, and then more than 25 minutes to get the score higher than +450 (I stopped after this).

Look, I find proof-algorithms very interesting and useful, but not for playing engines. I have no doubt that a dedicated algorithm will proof a position a lot quicker than it will take alpha-beta type algorithms to proof it. But I doubt whether you could find an algorithm that proofs a position quicker than it takes alpha-beta to *find* the winning move. In other words, I doubt whether you can improve an engine's ELO in a match by replacing alpha-beta with a dedicated prover. Maybe if you do it in certain endgames only. Maybe.

In any case: you have presented so far very little information. Please tell us more about your proof-algorithm. What heuristics does it use to detect progress, how does it avoid endless king sequences etc. It's not very interesting for me to discuss timings for arbitrary positions. Please try and discuss with a bit more constructive examples. Show us some pseudo-code, perhaps some search logs, your general ideas, etc.

[TAILLE]

Hi Rein,

It is a little surprised to see Kingsrow taking 25 minutes without able to prove the win. The point is the following : in this position the moves 8-2 and 39-33 are both winning moves. In such context an algorithm optimised for finding the best move will normally hesitate between the two winning moves and will eventually prove the win for one of them.
FYI Damy proves the win in 5 minutes.

Concerning my new algorithm I am not in position to clarify the details of the algorithm because it changes every day if not every hour !
In any case the basic idea of the algorithm remains unchange and I will try to show you this basic idea.

Let’s take the initial position of a game for which you try to find the best move.
Let’s suppose you begin by analysing the move 33-28 at a depth of 10 plies and you calculate for this variation an evaluation equal to +1.
Now you will explore another move in order to reach a better value (+2 or higher). Let’s take as new variation to analyse the sequence 32-28 18-23 37-32. Of course 37-32 is a well known mistake but how will work your algorithm ? Imagine that after this sequence you try first the answer 12-18 and you prove that white cannot reach the value +2. Your algorithm will conclude that 12-18 is a cutoff move and it may even happen that you will save in your hashtable that 37-32 is a bad move due to the answer 12-18 !?
From this point when you will explore the tree at a higher depth, every time you will analyse the sequence 32-28 18-23 37-32 your algorithm will be happy to analyse in first position the move 12-18 that will lead to a lot of calculation to prove that 12-18 remains a cutoff move.

To summary :
In the first stage of your analyse you gain a lot of time by analysing the position 32-28 18-23 37-32 against the value of +2 but then you will lose a lot of time because if you should have find that 37-32 were a big mistake then you should have been able to put in place a far more efficient pruning.

A human will never make such mistake in their analyse : when analysing 32-28 18-23 37-32 a human will verify if a combinaison can take place and if yes this human will prune any further analyse of this sequence. This is the base of my algorithm : instead of analysing a position against a given value I always analyse a position for itself and I use the value obtained to prune more efficiently in the next iterations.

In other words I think the clue is an efficient pruning mechanism but to be efficient a pruning mechanism has to be based on correct evaluations.

It is obvious that a pruning mechanism can be very efficient for a position and not for another so I am testing several pruning mechanism on various positions in order to find a good compromise.

At least you have now the base of my algorithm !

[Rein Halbersma]

Hi Gérard,

Thanks for your explanation. I think it is very much related to this discussion from more than 7 years ago. If I understand you correctly, you would like to discover the cheapest tactical refutation of 2. 37-32? as soon as possible, instead of relying on accidentally "winning" positional moves like 12-18, which are more expensive to compute. And you seem to have invented a completely new search framework with new datastructure (tree instead of hash table) in order to do that.

But you can do these things inside the classical alpha-beta framework. Take a look at e.g. the Stockfish search algorithm In particular in "Step 9." starting at line 596, they do the ProbCut search enhancement. Because of the nature of chess, they do this when not in check and only look at very good capture moves, when the remaining search depth is at least 5. They then do a search with depth-4 and with an increased window (by 2 pawns). If this shallow and selective search yields a cutoff above the increased window, they will cutoff the full and complete alpha-beta search with the regular window as well.

As a first rough translation of the Stockfish implementation of ProbCut, in draughts we could try and search when not having to capture, only moves that initiate an exchange, and when the remaining depth at least 5. Then search with depth-4 and with a window increased by e.g. 2/3 of a man value. This will effectively look for combinations that will win at least one man without too much positional compensation for the opponent.

Let's take this position that you mention:


Black to move

The ProbCut search here would try 2... 17-22, 2... 19-24 and 2... 23-29. The first move is a simple (positional) exchange that will not produce the required 2/3 of a man value in advantage. The second move will sacrifice 2 men, after which the "combination" can only continue with 3... 20-24, after which black loses the move and is 2 men behind. This leaves the third move and already a 5-ply search will find 2... 23-29 3. 33x24 20x29 4. 34x23 17-22 and now quiescence search will find the complete combination 5. 28x17 19x26 6. 41-37 12x21 with 2 men up.

So what does this mean? When doing iterative deepening with steps of 2 on the diagram, the first few searches at depth=1, 3, 5 and 7 will find the positional 2... 12-18 as the best move. At depth = 9, the reduced ProbCut search that looks at 2... 17-22, 2... 19-24 and 2... 23-29 will find the latter move using a depth=5 search with an increased window of 2/3 of a man value. At depth = 11 and higher, the move 2... 23-29 is remembered from the hash table and will continue to be the best.

Does this seem like a good compromise between regular alpha-beta and your goal of finding cheap combinations?

[Krzysztof Grzelak]

Hi Rein,

It is a little surprised to see Kingsrow taking 25 minutes without able to prove the win. The point is the following : in this position the moves 8-2 and 39-33 are both winning moves. In such context an algorithm optimised for finding the best move will normally hesitate between the two winning moves and will eventually prove the win for one of them.
FYI Damy proves the win in 5 minutes.

Concerning my new algorithm I am not in position to clarify the details of the algorithm because it changes every day if not every hour !
In any case the basic idea of the algorithm remains unchange and I will try to show you this basic idea.

Let’s take the initial position of a game for which you try to find the best move.
Let’s suppose you begin by analysing the move 33-28 at a depth of 10 plies and you calculate for this variation an evaluation equal to +1.
Now you will explore another move in order to reach a better value (+2 or higher). Let’s take as new variation to analyse the sequence 32-28 18-23 37-32. Of course 37-32 is a well known mistake but how will work your algorithm ? Imagine that after this sequence you try first the answer 12-18 and you prove that white cannot reach the value +2. Your algorithm will conclude that 12-18 is a cutoff move and it may even happen that you will save in your hashtable that 37-32 is a bad move due to the answer 12-18 !?
From this point when you will explore the tree at a higher depth, every time you will analyse the sequence 32-28 18-23 37-32 your algorithm will be happy to analyse in first position the move 12-18 that will lead to a lot of calculation to prove that 12-18 remains a cutoff move.

To summary :
In the first stage of your analyse you gain a lot of time by analysing the position 32-28 18-23 37-32 against the value of +2 but then you will lose a lot of time because if you should have find that 37-32 were a big mistake then you should have been able to put in place a far more efficient pruning.

A human will never make such mistake in their analyse : when analysing 32-28 18-23 37-32 a human will verify if a combinaison can take place and if yes this human will prune any further analyse of this sequence. This is the base of my algorithm : instead of analysing a position against a given value I always analyse a position for itself and I use the value obtained to prune more efficiently in the next iterations.

In other words I think the clue is an efficient pruning mechanism but to be efficient a pruning mechanism has to be based on correct evaluations.

It is obvious that a pruning mechanism can be very efficient for a position and not for another so I am testing several pruning mechanism on various positions in order to find a good compromise.

At least you have now the base of my algorithm !

[Rein Halbersma]

Hi Rein,

It is a little surprised to see Kingsrow taking 25 minutes without able to prove the win.

I redid the search and I must have made a mistake earlier to let Kingsrow search when the databases were not yet initialized. When doing this correctly, Kingsrow now finds and proves both wins 8-2 and 39-33 within a few seconds. It also finds that 23-19, 24-19, 34-29, 8-3 are also wins.

[TAILLE]

Hi Rein,

It is a little surprised to see Kingsrow taking 25 minutes without able to prove the win.

I redid the search and I must have made a mistake earlier to let Kingsrow search when the databases were not yet initialized. When doing this correctly, Kingsrow now finds and proves both wins 8-2 and 39-33 within a few seconds. It also finds that 23-19, 24-19, 34-29, 8-3 are also wins.

Rein,

Oops, are sure you put the correct position on your board?


White to play

After 23-19 or 24-19 Damy plays 41-47 and I have to confess it is unable to find any win.
What is the pv towards the win?

[Krzysztof Grzelak]

After moving 23-19 or 24-19 is a draw.

[Rein Halbersma]

Hi Rein,

It is a little surprised to see Kingsrow taking 25 minutes without able to prove the win.

I redid the search and I must have made a mistake earlier to let Kingsrow search when the databases were not yet initialized. When doing this correctly, Kingsrow now finds and proves both wins 8-2 and 39-33 within a few seconds. It also finds that 23-19, 24-19, 34-29, 8-3 are also wins.

Rein,

Oops, are sure you put the correct position on your board?


White to play

After 23-19 or 24-19 Damy plays 41-47 and I have to confess it is unable to find any win.
What is the pv towards the win?

Ah I put 26 on 6, and then everything wins very easily.

[Klaas van der Laan]

Maybe interesting: http://www.technologyreview.com/view/54 ... al-master/