Search Algorithm

[TAILLE]

Gerard,

It is my intention to return a draw value when this happens, if you keep moving around the result will always be draw, it is standard practice in chess programs, nothing fancy.

Joost

Joost,

Look at the "loop detection and hash table" subject I openned in 2010. You will see some issues and a reference to the famous GHI problem.

Gerard,

Discussions about subjects comparable to the one you mention have been going on for years at the chess forums.

What i'm going to do is to keep track of al the hashes that appear during the game and during the search, secondly I have to maintain a counter that counts all the plies after the last irreversible move, with this information it is very simple to detect a repetition by scanning backwards through the table with hashes using 2 ply steps. This is only needed when there are kings on the board though, so I hope it doesn't have much impact on speed.

I know that in combination with the hash-table there can be an undesirable effect but engine development is always full of compromises.

Joost

I undestand your point Joost. In addition if you have followed the chess discussion on this subject I guess you have the best information on it!

[Rein Halbersma]

Hi Rein,

As you perfectly know I experimented for many years standard algorithms, alpha-beta first and then MTD-f procedure but I experiment now new ideas.

First idea:
From that experience I got the feeling that these procedures are nor "natural" and are not quite efficient to detect and explore the best moves. The main problem is the following: on a CUT node you explore only the previous "cutting move" and if it works your are happy not considering the other moves! In reality there is a main drawback with that: you do not have a reliable estimation of the value of the CUT node but only a bound value. As a consequence you may waste a lot of time in the following iterations because you will explore again and again only the "cutting move" where it may exist a far better move which would be handled far more rapidly.
My very first idea is to always give a node the best evaluation taking into account the time allowed to analyse this particular position.

Second idea:
Another strong idea is the following: by changing the order of moves you can reach a position via different variants. Especially if this position is on the PV you will reach this position and the following ones many times (several times during each iterations). That means in particular that you will generate this position, you will calculate its hash and you eventually generate the successors and all that many times. With the technology evolution you can avoid a great part of this job by keeping in memory millions of positions instead of handling a huge hash table.

I developped a lot of other ideas but these are my two main starting ideas. I imagine that you could be disturbed because that means abandonning standard alpha-beta procedure and I confess I hesitated a long time before daring exploring these new ideas.

My intention is certainly not to convince you but to show you an other approach. The first results are here but I have still a lot of work on the table!

Hi Gérard,

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

BTW, I have been thinking of another approach we discussed here many years ago. The position you showed has 3 kings, and 47 open squares. That means that there are 16.215 different placements of these kings. You could then partition the search space as a fully acyclic graph of sets of 16.215 positions. Cycles can only occur within each set of 16.215 positions, but not between sets. So you only do man moves and moves leading to captures and then you lookup the resulting 5-piece position, but for all 16.215 configurations in one go. If you encode the indexing 5-piece database such that all king placements form a contiguous array, you can basically resolve each set of the acyclic graph in parallel on 16.215 positions. I think this would give a very small search tree compared to endless cycles of moving kings around.

Is this something you have experimented with?

Rein

[TAILLE]

Hi Rein,

As you perfectly know I experimented for many years standard algorithms, alpha-beta first and then MTD-f procedure but I experiment now new ideas.

First idea:
From that experience I got the feeling that these procedures are nor "natural" and are not quite efficient to detect and explore the best moves. The main problem is the following: on a CUT node you explore only the previous "cutting move" and if it works your are happy not considering the other moves! In reality there is a main drawback with that: you do not have a reliable estimation of the value of the CUT node but only a bound value. As a consequence you may waste a lot of time in the following iterations because you will explore again and again only the "cutting move" where it may exist a far better move which would be handled far more rapidly.
My very first idea is to always give a node the best evaluation taking into account the time allowed to analyse this particular position.

Second idea:
Another strong idea is the following: by changing the order of moves you can reach a position via different variants. Especially if this position is on the PV you will reach this position and the following ones many times (several times during each iterations). That means in particular that you will generate this position, you will calculate its hash and you eventually generate the successors and all that many times. With the technology evolution you can avoid a great part of this job by keeping in memory millions of positions instead of handling a huge hash table.

I developped a lot of other ideas but these are my two main starting ideas. I imagine that you could be disturbed because that means abandonning standard alpha-beta procedure and I confess I hesitated a long time before daring exploring these new ideas.

My intention is certainly not to convince you but to show you an other approach. The first results are here but I have still a lot of work on the table!

Hi Gérard,

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

BTW, I have been thinking of another approach we discussed here many years ago. The position you showed has 3 kings, and 47 open squares. That means that there are 16.215 different placements of these kings. You could then partition the search space as a fully acyclic graph of sets of 16.215 positions. Cycles can only occur within each set of 16.215 positions, but not between sets. So you only do man moves and moves leading to captures and then you lookup the resulting 5-piece position, but for all 16.215 configurations in one go. If you encode the indexing 5-piece database such that all king placements form a contiguous array, you can basically resolve each set of the acyclic graph in parallel on 16.215 positions. I think this would give a very small search tree compared to endless cycles of moving kings around.

Is this something you have experimented with?

Rein

Hi Rein,

About two years ago I tried to analyse a position representation based on such approach: as soon as the position has at least one king in each side my idea was to create a "global position" based only on the men placements with a special generating procedure to find the "global positions" that can be reached and to find if a loop can be forced by one side, in the initial "global position". Unfortunetly I had to give up because I did not find a good solution to make this work.

[TAILLE]

Hi Gérard,

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

BTW, I have been thinking of another approach we discussed here many years ago. The position you showed has 3 kings, and 47 open squares. That means that there are 16.215 different placements of these kings. You could then partition the search space as a fully acyclic graph of sets of 16.215 positions. Cycles can only occur within each set of 16.215 positions, but not between sets. So you only do man moves and moves leading to captures and then you lookup the resulting 5-piece position, but for all 16.215 configurations in one go. If you encode the indexing 5-piece database such that all king placements form a contiguous array, you can basically resolve each set of the acyclic graph in parallel on 16.215 positions. I think this would give a very small search tree compared to endless cycles of moving kings around.

Is this something you have experimented with?

Rein

Rein,

Last year I build also a Monte Carlo version of Damy. Though the result was quite poor I have been impressed by the logic of the UCT algorithm and my current version is clearly issued from this algorithm.

[Fabien Letouzey]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

In Scan the effect is tiny; it's only a couple of Elo points at most, so it wouldn't fit well with your minimal design. That being said, endgame tables (6 pieces) are worth only 10 Elo or so ; that might be unusual or surprising.

[Joost Buijs]

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

I think Woldouby position is white to move, shouldn't there be a white man on 34 instead of 39?
I've added printing the PV to my program and it show the following variation to the drawn position:

34-29 23x34 30x39 12-17 28-23 19x28 33x11 16x7 27x16 18-22 39-33 14-19 32-28 22-27 37-32 7-12 32x21 26x17 28-22 17x39 38-33 39x28 16-11 28-32 11-6 32-37 6-1 12-17 1-6

I didn't check the variation, so it might be wrong.

Endgame databases can be useful to find a win in equal positions or a draw in difficult positions, but don't you think that it is wiser to focus on opening and midgame play? It is my feeling that a game should be won earlier on and not by a lucky shot in the endgame.

Joost

[Joost Buijs]

Another question: How effective is repetition detection in draughts to diminish the size of the tree during endgames, any figures known?

In Scan the effect is tiny; it's only a couple of Elo points at most, so it wouldn't fit well with your minimal design. That being said, endgame tables (6 pieces) are worth only 10 Elo or so ; that might be unusual or surprising.

Hi Fabien,

Yes, I was wondering if the added cost is worth the additional playing strength, but on the other hand it only has to be checked when there are kings on the board, I will probably add it, if it slows down too much I can always throw it out.

10 Elo gain for 6p egtb is not very surprising, I my opinion strong opening and midgame play is way more important and egtb is just icing on the cake.

It will take some more months before my program is ready to play, the search is almost finished although I still have to add additional pruning and LMR. The evaluation function is still completely void, this will take the most effort. Unfortunately I can't work more than ~8 hours a week on it.

Joost

[Fabien Letouzey]

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

IMO best-first search is underappreciated and often not recognised when it is used (e.g. in opening books). It was studied in the 90's but with a big mistake: scoring the leaves using eval is too costly overall. If instead one performs an alpha-beta search, the overhead becomes tolerable.

The general pattern goes like this:

Code: Select all

while true
  pick leaf
  expand leaf
  score new leaves
  back up scores

You have to choose heuristics for these steps, so the space is huge. Opening-book construction, PN-search, and MCTS are popular instances. It can also be used for analysis, as it simulates the user algorithmically. Possibly this would be the best way to solve draughts engames (wild guess).

Usually the emphasis is on modelling errors, especially at the leaves. You can back up confidence intervals or mean/variance pairs, with simplistic assumptions to allow easy replacement of the min/max operators. It's also possible, and in fact common, to keep min/max and focus on which leaf to expand instead.

I recommend the following articles:
"Parallel Randomized (Minimax) Best-First Search" (2 related articles)
"Game-Tree Searching by Min/Max Approximation"
I used a similar approach for Scan's opening book.

I note however that Gérard seems to be using depth-first search.

Fabien.

[Rein Halbersma]

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

IMO best-first search is underappreciated and often not recognised when it is used (e.g. in opening books). It was studied in the 90's but with a big mistake: scoring the leaves using eval is too costly overall. If instead one performs an alpha-beta search, the overhead becomes tolerable.

The general pattern goes like this:

Code: Select all

while true
  pick leaf
  expand leaf
  score new leaves
  back up scores

This framework is something that I have been experimenting with for a while. See e.g. this old discussion viewtopic.php?f=53&t=3498&start=32. One thing I wrote there I still agree with:

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).

I recommend the following articles:
"Parallel Randomized (Minimax) Best-First Search" (2 related articles)
"Game-Tree Searching by Min/Max Approximation"

Fabien.

Thanks for these articles. Added to my TODO list

[TAILLE]

Hi Joost,

What do you mean by "it STARTS seeing the draw". I easily imagine that the probablity of the draw is near 100% but because the program continues its iterations I suspect the draw is not 100% sure is it?


Black to play

Damy proves the 100% sure draw with the following PV:
1...17-22 2.28x17 21x12 3.33-28 24-29 4.39-33 12-17 5.33x24 17-21
Here the PV continues with 6.25-20 14x34 7.24-20 23-29 8.20-15 34-39 etc.
and on the common variant 6.38-33 23-29 7.28-23 19x39 8.24x44 Damy chooses the very common continuation 8... 18-23 9.27-22 13-18 10.22x13 14-19 11.13x24 21-27 etc. and the 8p db is then reached very quickly.

Note : I cannot tell you if the draw is proved at 28 plies or another figure because Damy ignores the ply notion.

I think Woldouby position is white to move, shouldn't there be a white man on 34 instead of 39?
I've added printing the PV to my program and it show the following variation to the drawn position:

34-29 23x34 30x39 12-17 28-23 19x28 33x11 16x7 27x16 18-22 39-33 14-19 32-28 22-27 37-32 7-12 32x21 26x17 28-22 17x39 38-33 39x28 16-11 28-32 11-6 32-37 6-1 12-17 1-6

I didn't check the variation, so it might be wrong.

Endgame databases can be useful to find a win in equal positions or a draw in difficult positions, but don't you think that it is wiser to focus on opening and midgame play? It is my feeling that a game should be won earlier on and not by a lucky shot in the endgame.

Joost

Hi Joost,

I am never been able to determine which is the best : working at the opening phase, or the middle phase or the endgame. For me the opening phase normally gives only the style of the game and we cannot expect any advantage in this phase. The middle game is of course essentiel. It is the phase in which the best player is able to create a growing advantage. But don't forget that in many case the advantage is not sufficiant to win and in this case your program have to be very strong in the endgame in order to find the draw or in order to create a difficult situation and an error of your opponent.

Let's take a very simple example.

Computer Olympiade Leiden Rapid CCD 2016 : Ronde 13, Maximus - Scan, position after 45th move

White to play

Scan built during the middle game a beautiful position but Maximus managed to offer a strong resistance to reach this draw position. Unfortunately Maximus is not strong enough in the endgame and instead of playing 46.48-43! which is obvious for any program having the 8p egdb, Maximus played the losing move 46.48-42?

For human game we are very very often in the same position: one of the player manages to build a significant advantage in the middle game but the losing move appears really in the endgame phase.

That the reason why I cannot decide which phase of the game is the most important. To be able to build an advantage in the middle game is without any doubt essentiel but to be able to play the endgame without any error is also essential isn't it?

[Joost Buijs]

Hi Joost,

I am never been able to determine which is the best : working at the opening phase, or the middle phase or the endgame. For me the opening phase normally gives only the style of the game and we cannot expect any advantage in this phase. The middle game is of course essentiel. It is the phase in which the best player is able to create a growing advantage. But don't forget that in many case the advantage is not sufficiant to win and in this case your program have to be very strong in the endgame in order to find the draw or in order to create a difficult situation and an error of your opponent.

Let's take a very simple example.

Computer Olympiade Leiden Rapid CCD 2016 : Ronde 13, Maximus - Scan, position after 45th move

White to play

Scan built during the middle game a beautiful position but Maximus managed to offer a strong resistance to reach this draw position. Unfortunately Maximus is not strong enough in the endgame and instead of playing 46.48-43! which is obvious for any program having the 8p egdb, Maximus played the losing move 46.48-42?

For human game we are very very often in the same position: one of the player manages to build a significant advantage in the middle game but the losing move appears really in the endgame phase.

That the reason why I cannot decide which phase of the game is the most important. To be able to build an advantage in the middle game is without any doubt essentiel but to be able to play the endgame without any error is also essential isn't it?

I fully agree with you that all phases of the game are important, what I meant to say is that you should not put too much emphasis on the endgame database alone.
In your example Maximus played 46.48_42? losing because it didn't have a 8p database, but it might as well be because it didn't understand the position and that with a better evaluation it would have played a different/better move.

I am not a draughts player, for me it is difficult to comprehend what is going when I see these diagrams, but I know for one that the game is very drawish, if both players don't make big mistakes the result will almost always be a draw, maybe there is not much to gain anymore and are the top-engines already at that level, it would be a pity because in that case the game is more or less dead.

Joost

[Krzysztof Grzelak]

Gerard if you think that Maximus lost because he had no 8p database. I believe that database are important but not the most important. If the engine has a losing position and is the best base will not help. The very base only speeds up the end of the game and nothing else.

[Krzysztof Grzelak]

I believe that the draughts are three important phase of the game.

1. Debut - although not all the developers they use the book.
2. The middle game - the most important element of the whole lot. Here is the most errors and the element determines the outcome of the party.
3. The base ends - if the engine makes a mistake in the middle game and is the best base ends will not help.

The program Maximus lost engine part and important information herewith is whether to have a base. It is also worth remembering that good engine does not need or the book or the base.

[TAILLE]

I don't need much persuasion to abandon alpha-beta! And that is not a revolutionary step in itself. E.g., Monte Carlo tree search and opening book generation also keep a big search graph in memory and fill the leaf values by simulation and direct evaluation respectively. Also, Aart Bik's deep-perft calculation show that a draughts search graph is very much redundant. He keeps all unique positions to depth 22 in memory (or on disk, and then loads them as needed) and does shallow perft(6) computations on the graph leafs.

IMO best-first search is underappreciated and often not recognised when it is used (e.g. in opening books). It was studied in the 90's but with a big mistake: scoring the leaves using eval is too costly overall. If instead one performs an alpha-beta search, the overhead becomes tolerable.

The general pattern goes like this:

Code: Select all

while true
  pick leaf
  expand leaf
  score new leaves
  back up scores

You have to choose heuristics for these steps, so the space is huge. Opening-book construction, PN-search, and MCTS are popular instances. It can also be used for analysis, as it simulates the user algorithmically. Possibly this would be the best way to solve draughts engames (wild guess).

Usually the emphasis is on modelling errors, especially at the leaves. You can back up confidence intervals or mean/variance pairs, with simplistic assumptions to allow easy replacement of the min/max operators. It's also possible, and in fact common, to keep min/max and focus on which leaf to expand instead.

I recommend the following articles:
"Parallel Randomized (Minimax) Best-First Search" (2 related articles)
"Game-Tree Searching by Min/Max Approximation"
I used a similar approach for Scan's opening book.

I note however that Gérard seems to be using depth-first search.

Fabien.

Hi Fabien,

I am not quite familiar with the wordings "depth-first search" or "best-first search" and so I am a little surprised to learn I am using depth-first search.
I suspect you refers to the "pick leaf" phase but in this phase the path I choose is always based on the move with the highest winning probablity (or the lowest loss probability). It looks for me like a "best-first search" but I do not have a clear definition of this notion.

[Fabien Letouzey]

Hi Gérard,

I am not quite familiar with the wordings "depth-first search" or "best-first search" and so I am a little surprised to learn I am using depth-first search.
I suspect you refers to the "pick leaf" phase but in this phase the path I choose is always based on the move with the highest winning probablity (or the lowest loss probability). It looks for me like a "best-first search" but I do not have a clear definition of this notion.

I don't know how to explain best-first search better than the pseudo-algorithm I described. It is more general than just game-tree search and is common in AI (e.g. pathfinding); Wikipedia to the rescue:

"Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking."
https://en.m.wikipedia.org/wiki/Depth-first_search

"Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule."
https://en.m.wikipedia.org/wiki/Best-first_search

So DFS is the recursive traversal that we all use in tournament programs because it's so fast, while BFS has a much more iterative feel to it: expanded nodes can be far away from each other. If your algorithm is appropriately described by my pseudo-code (with some suitable selection of heuristics), then it's an instance of BFS. Even if you pick a leaf without searching ("best" move at every level), it's still BFS for a specific meaning of "best".

Fabien.