Alpha-beta procedure

[TAILLE]

Hi Ed., Bert ... and the others

Are you happy with the alpha-beta procedure?

Of course alpha-beta procedure is far better than minimax procedure but it appears now to me that in a game like draughts, were the tactic is present at almost every move, this procedure may not be the best approach.
Let me take a very simple example by exploring the tree beginning with the initial position of the game.
Let’s suppose that position resulting from the sequence 1.32-28 18-23 2.33-29 is better that the position resulting from the sequence 1.32-28 18-23 2.37-32 12-18.
Where is the problem ?
For a human body the sequence 1.32-28 18-23 2.37-32 12-18 will not be explored because it will be seen immediately that 2…23-29 is certainly a winning move and as a consequence, the move 2.37-32 is very bad.
Now, what could happen with the alpha-beta procedure ?
After 1.32-28 18-23 suppose that the first move explored is 2.33-29 which looks very nice. After having evaluated this variant the alpha-beta procedure will explore the move 2.37-32 taking into account the result of the move 2.33-29. Because we are in the beginning of the process it’s impossible to already know that after 2.37-32 the move 2…23-29 is far better than the move 2…12-18 and it is almost certain that this last move will be first explored.
Because the sequence 1.32-28 18-23 2.37-32 12-18 is, for white, worse than the sequence 1.32-28 18-23 2.33-29 it will be conclude that the move 2.37-32 is not the best move, which is very correct, but it will be marked in the hashtable that the “killing” move after 2.37-32 is 2…12-18 which is a terrible error.
Now, when exploring the tree deeper and deeper, the move 2…23-29 will never be discovered and the alpha-beta will loose more and more time to verify that 1.32-28 18-23 2.33-29 remains always better than 1.32-28 18-23 2.37-32 12-18.

Questions :
Do you think it is really a big lost of time for draughts tree exploration ?
Did you find some change in the alpha-beta procedure to improve its efficiency on this point ?

Gérard

[BertTuyt]

Gerard,

i appreciate that within the Draughts community we share more of these ideas. Hope this forum will be the platform for huge Computer Draughts progress.

As i leave now for 2 weeks China (business), i will not be able to study these thoughts.

However, when im back (and Xmas holiday will start), i will take the time to do some research, and give my reply.

In the mean time there is much work to do, as we have to recapture the Draughts Title !!

Bert

[Ed Gilbert]

Hi Gerard,

Are you happy with the alpha-beta procedure?

I'm not sure that 'happy' describes it exactly, but I don't know of anything better. Of course there are several flavors of alphabeta -- aspiration window, PVS, MTD-f, etc. I happen to use a null window search in Kingsrow, but I have tried some others and I did not see a big performance difference between them. Which variation of alphabeta do you use in Damy?

Because the sequence 1.32-28 18-23 2.37-32 12-18 is, for white, worse than the sequence 1.32-28 18-23 2.33-29 it will be conclude that the move 2.37-32 is not the best move, which is very correct, but it will be marked in the hashtable that the “killing” move after 2.37-32 is 2…12-18 which is a terrible error.

I didn't quite follow that, because at the point you reference, the position after 1.32-28 18-23 2.37-32 will not be in the hashtable. I think you are talking about move ordering, and there is a common technique for move ordering using a killer move table, but it is separate from the hashtable. If this killer move table is what you are referring to, then yes it may have 37-32 as the killer move at that point in the search. The killer move is only one of several techniques that I use for move ordering, and it is not the primary technique. It is quite possible that one of the other factors influencing move ordering would cause kingsrow to not place 37-32 at the top of the list of moves to search at that node in the tree.

-- Ed

[TAILLE]

Hi Ed.

Of course I programmed in Damy a lot of techniques to try and improve the basic alpha-beta procedure. Iterative deepening, window size modifications (with extensive use of null window as well as window with a size equal to the value of a man), hashtable, adaptation of the deepness depending of the interest of the current position etc.
I don’t use the killer move approach so my formulation in my previous post was very ambiguous. I only store in the hashtable the best move corresponding to the current iteration.

So let me reformulate the problem (I slightly change my previous example) to avoid a capture:
Let’s assume I begin the iterative deepening process by exploring the tree up to 4 plies
Let’s assume I begin by the sequence 1.32-28 18-23 2.38-32 12-18. After examining the other black answers to 2.38-32 I will put in the hash table that 2…12-18 is actually the best move after 2.38-32.
Let’s assume now that I continue the exploration by examining the sequence 1.32-28 18-23 2.37-32. Because the tree is explored only at 4 plies it may happen that the move ordering procedure cannot decide that 2…23-29 should be examined BEFORE 2…12-18. If then we begin by 1.32-28 18-23 2.37-32 12-18 what will happen if the 1.32-28 18-23 2.37-32 12-18 is considered worse (for white) than the sequence 1.32-28 18-23 2.38-32 …? Firstly the other black moves after 1.32-28 18-23 2.37-32 will not be examined (that means that the move 2…23-29 cannot be discovered at this level of iteration) and secondly the move 2…12-18 is put in the hashtable in order to keep in mind that this was a good move after the sequence 1.32-28 18-23 2.37-32.

Later in the process the tree will be explored up to 5 plies. The first sequence explored could for example be 1.32-28 18-23 2.38-32 12-18 3.42-38 and, some time later, the sequence 1.32-28 18-23 2.37-32 will appear for analysis. May be I am wrong but at this point I use the hashtable in order to see which move I have to examine first and, in this case, I find in the hashtable the move 2…12-18 (of course I would have preferred to find 2…23-29!). Now I will continue one ply in order to evaluate the 1.32-28 18-23 2.37-32 12-18 sequence. If the sequence 1.32-28 18-23 2.37-32 12-18 … remains worse than 1.32-28 18-23 2.38-32 … then again, firstly the other black moves after 1.32-28 18-23 2.37-32 will not be examined and secondly the move 2…12-18 is confirmed as good move in the hashtable.

This can be repeated at each iteration (up to 15 plies or more) and you can see that a lot of time is lost because it is obviously more efficient to eliminate 1.32-28 18-23 2.37-32 by the move 2…23-29! rather than the move 2…12-18.

As a consequence I try and modify my alpha-procedure but, for the time being, I did not obtain very satisfactory results.

Gérard

[Rein Halbersma]

Hi Ed.

This can be repeated at each iteration (up to 15 plies or more) and you can see that a lot of time is lost because it is obviously more efficient to eliminate 1.32-28 18-23 2.37-32 by the move 2…23-29! rather than the move 2…12-18.

As a consequence I try and modify my alpha-procedure but, for the time being, I did not obtain very satisfactory results.

Gérard

Why would this be a big problem?

First of all, 12-18 gives a cutoff and saves searching all other 8 moves like 16-21 through 20-25 (and also 23-29). So whenever 12-18 fails high, it already saves a lot of work compared to negamax, especially if you search it as the first move.

Second, suppose 12-18 does not fail high. This means that all other moves will be searched. Then either 23-29 will be found (if the search is deep enough) or 12-18 will remain the best move (for shallow searches). In that case, when searching with a null-window, 12-18 will then fail low.

This means that one ply higher in the tree, 2.37-32 will fail high and 2.37-32 12-18 becomes the PV instead of 2.33-29. This changs the nature of the node after 37-32 the next iteration since then all other moves will be searched at this point to prove that they are inferior to 12-18. So at this point 23-29 will be found (again, if the search is deep enough) and the PV changes back to 2.33-29.

So 23-29 will only be missed whenever 12-18 keeps failing high at all search depths, in which case it is never part of the PV, or at some point 2.37-32 becomes the PV and 23-29 will then definitely be searched.

[TAILLE]

Why would this be a big problem?

First of all, 12-18 gives a cutoff and saves searching all other 8 moves like 16-21 through 20-25 (and also 23-29). So whenever 12-18 fails high, it already saves a lot of work compared to negamax, especially if you search it as the first move.

Second, suppose 12-18 does not fail high. This means that all other moves will be searched. Then either 23-29 will be found (if the search is deep enough) or 12-18 will remain the best move (for shallow searches). In that case, when searching with a null-window, 12-18 will then fail low.

This means that one ply higher in the tree, 2.37-32 will fail high and 2.37-32 12-18 becomes the PV instead of 2.33-29. This changs the nature of the node after 37-32 the next iteration since then all other moves will be searched at this point to prove that they are inferior to 12-18. So at this point 23-29 will be found (again, if the search is deep enough) and the PV changes back to 2.33-29.

So 23-29 will only be missed whenever 12-18 keeps failing high at all search depths, in which case it is never part of the PV, or at some point 2.37-32 becomes the PV and 23-29 will then definitely be searched.

What do you mean by "fail high" and "fail low" ?

The case I consider is clearly the case where the move 2.37-32 becomes never a part of PV. In that case the move 23-29 is never dicovered.
I am not sure to understand your arguments. It seems that it is not a problem for you because (may be it is a misunderstanding of my part) as long as 2.37-32 is not in the PV then we have a null-window search on this node and as a consequence it does not harm to explore 2...12-18 instead of 2...23-29.
If this is a good understanding then I cannot agree with you because a null-window search with 2...23-29 will be far more efficient than a null-window search with 2...12-18.
In general an argument based on the null-window search seems not relevant because, except for the PV nodes (a very very small part of the search), the search is always a null-windows search.

My view is that the search procedure of a strong player is almost always superior to the search procedure of a program. If I explain to a strong player that during analysing the initial position, my program has eliminated the move 2.37-32 due to 2...12-18 he will certainly burst in laught and conclude that the program may be strong due to its calculation power but that it is really a very poor program in understanding draughts game !
Who is right ? The programmer I am or the strong player ?

Gérard

[Rein Halbersma]

What do you mean by "fail high" and "fail low" ?

fail high = score > beta, fail low = score < alpha (this will give a fail high one ply higher in the tree)

The case I consider is clearly the case where the move 2.37-32 becomes never a part of PV. In that case the move 23-29 is never dicovered.
I am not sure to understand your arguments. It seems that it is not a problem for you because (may be it is a misunderstanding of my part) as long as 2.37-32 is not in the PV then we have a null-window search on this node and as a consequence it does not harm to explore 2...12-18 instead of 2...23-29.
If this is a good understanding then I cannot agree with you because a null-window search with 2...23-29 will be far more efficient than a null-window search with 2...12-18.

If 37-32 12-18 will never be part of the PV, then you are right it is more expensive.

But since 37-32 makes white's left wing more balanced, it is more likely that at the position after 37-32 12-18 looks better than 38-32 12-18, so the former will at some point become the PV, and then 23-29 will definitely be searched.

My view is that the search procedure of a strong player is almost always superior to the search procedure of a program. If I explain to a strong player that during analysing the initial position, my program has eliminated the move 2.37-32 due to 2...12-18 he will certainly burst in laught and conclude that the program may be strong due to its calculation power but that it is really a very poor program in understanding draughts game !
Who is right ? The programmer I am or the strong player ?

Gérard

One thing you can do to be more human-like is looking for tactical patterns like Truus and Dragon do. Perhaps you do this also? Or use the Enhanced Transposition Cutoff (ETC) to see if you can get a cheaper cutoff before do the recursive alpha-beta search?

Rein

[TAILLE]

If 37-32 12-18 will never be part of the PV, then you are right it is more expensive.

But since 37-32 makes white's left wing more balanced, it is more likely that at the position after 37-32 12-18 looks better than 38-32 12-18, so the former will at some point become the PV, and then 23-29 will definitely be searched.

Rein

Yes Rein I agree with you but it was just a exemple to show you the issue.
Through the millions of positions seen by the program I am quite sure that, in number of cases, a move (like 2.37-32) is eliminated by a very inefficient answer (like 2...12-18 instead of 2...23-29).
If this case is not so frequent then we have to forget about this issue. I think it is very dependant of the game. I guess it is not relevant for chess because chess seems to be less tactical than draugths.

I think we now agree on the issue. The point is now to know if it could be really efficient to improve alpha-beta to tackle the point.
ETC is not the solution because the positions after 2.37-32 23-29 are not in the hashtable.
The solution seems to have a "quick" look at every move after 2.37-32 even if 2.37-32 is not part of PV. Of course this must be done only near the top of the tree, when there are enough depth lelft in the search.

Did somebody try this approach ? What results ?

Gérard

[Rein Halbersma]

The solution seems to have a "quick" look at every move after 2.37-32 even if 2.37-32 is not part of PV. Of course this must be done only near the top of the tree, when there are enough depth lelft in the search.

Did somebody try this approach ? What results ?

Gérard

See e.g. this interesting paper (esp. page 11): http://www.cs.vu.nl/~aske/Papers/optim.pdf

What they do is, at every iteration of the iterative deepening, perform a full minimax search for the last 3 plies and record the cheapest cutoff (the one that needs the fewest nodes at the last 3 plies). At the next iteration, this is then used in the move ordering.

This may sound like a lot of overhead, but they claim that the Real Minimal Graph (when you would always search the cheapest cutoff first) is around 4-5 times smaller than the graph that alpha-beta + all the enhancement searches. In the end they save a few % on some positions but it's not a stable result for many other positions.

[TAILLE]

What they do is, at every iteration of the iterative deepening, perform a full minimax search for the last 3 plies and record the cheapest cutoff (the one that needs the fewest nodes at the last 3 plies). At the next iteration, this is then used in the move ordering.

Interesting article thank you Rein.
I will effectively try some new overhead calculation in order to detect moves which may be more efficient to achieve a cutoff. Of course it could be done only rather far from the leaves of the tree. My idea is not to generate a small "minimax tree" but only what I call a small "combination tree" (a tree in which the opponent is always obliged to make a capture).
I don't know if I will gain something but at least it is funny for me to explore such idea which seems interesting for a game like draughts.
You can also find such "combination tree" in chess when the opponent is always facing a check but a in draughts I think that this notion if far more interesting because it can be applied to a very large number of positions
Gérard