Handling search inconsistencies in MTD(f)

[jj]

I was wondering if people using MTD(f) are aware of what happens when there are search inconsistencies (as a result of using a transposition table) and how to deal with these situations. I wrote a paper on the subject: http://www.maximusdraughts.org/research ... 20MTDf.pdf.

Comments are welcome!

Jan-Jaap

[Rein Halbersma]

I was wondering if people using MTD(f) are aware of what happens when there are search inconsistencies (as a result of using a transposition table) and how to deal with these situations. I wrote a paper on the subject: http://www.maximusdraughts.org/research ... 20MTDf.pdf.

Comments are welcome!

Jan-Jaap

Nice paper, I just read it on my train commute. I have quite a bit of comments, do you want them publicly or privately? (I'll be nice about it either way )

[jj]

Can you send me a pm? We can always see what is worth sharing.

[TAILLE]

I was wondering if people using MTD(f) are aware of what happens when there are search inconsistencies (as a result of using a transposition table) and how to deal with these situations. I wrote a paper on the subject: http://www.maximusdraughts.org/research ... 20MTDf.pdf.

Comments are welcome!

Jan-Jaap

Hi Jan,

In the past I used MTD(f) for long years and seeing how I implemented the algorithm I cannot have inconsistencies.
Anyway I tried to understand your point and my very first comment is the following:
Why do you say that inconsistencies appear as a result of using a transposition table? In my analysis and seeing the implementation you propose inconstancies may appear even without using transposition table, simply because the pruning and extension mechanisms may depend on the value tested (it is the same with an alpha-beta mechanism where the pruning and extension mechanisms may depend on alpha and beta values).
Do you have an example of an inconsistency purely due to TT and not due to the pruning and extension mechanisms?

Gérard

[jj]

Hi Jan,

In the past I used MTD(f) for long years and seeing how I implemented the algorithm I cannot have inconsistencies.
Anyway I tried to understand your point and my very first comment is the following:
Why do you say that inconsistencies appear as a result of using a transposition table? In my analysis and seeing the implementation you propose inconstancies may appear even without using transposition table, simply because the pruning and extension mechanisms may depend on the value tested (it is the same with an alpha-beta mechanism where the pruning and extension mechanisms may depend on alpha and beta values).
Do you have an example of an inconsistency purely due to TT and not due to the pruning and extension mechanisms?

Gérard

Hi Gérard,

Your comments relate to those of Rein, which means that my paper needs a better introduction.

In my implementation there are no forward pruning and search extensions based on the search window (yet). In that case there will be no search inconsistencies if we don't use a TT. MTD(f) works correctly in that case. If we do use a TT (on which MTD(f) depends) there will always be search inconsistencies, even without forward pruning and extensions and even if we clear the TT before the search. These are caused by the existence of transpositions with different path lengths to the root. The first time we search position p to depth d we store the result. The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d'), but if the entry is no longer present we search to depth d' and get a different result. Or, because of the new search window, the TT entry is found but does not cause a cutoff so we have to search anyway. I have examples where MTD(f) chooses a wrong move (with and without clearing the TT) but I expect these are difficult to reproduce in other programs.

My point is that using a TT implies having search inconsistencies, even in the basic case. And that textbook MTD(f) behaves incorrectly in case 2 with the last pass failing low. Even if (as expected) the second-last pass returns value >= v and the last pass returns value <= v. It is assumed that the last pass (which maximizes over what turn out to be upper bound values) will not change the best move. However, this assumption does not hold in case of search inconsistencies, so a wrong move is chosen. A problem for which an easy fix exists.

How did you solve this problem in (old) Damy? I learned that Ed Gilbert (of course) also has a way of solving this in Kingsrow. But there may be other programmers using MTD(f) who are unaware of this.

Jan-Jaap

[TAILLE]

Hi Jan,

In the past I used MTD(f) for long years and seeing how I implemented the algorithm I cannot have inconsistencies.
Anyway I tried to understand your point and my very first comment is the following:
Why do you say that inconsistencies appear as a result of using a transposition table? In my analysis and seeing the implementation you propose inconstancies may appear even without using transposition table, simply because the pruning and extension mechanisms may depend on the value tested (it is the same with an alpha-beta mechanism where the pruning and extension mechanisms may depend on alpha and beta values).
Do you have an example of an inconsistency purely due to TT and not due to the pruning and extension mechanisms?

Gérard

Hi Gérard,

Your comments relate to those of Rein, which means that my paper needs a better introduction.

In my implementation there are no forward pruning and search extensions based on the search window (yet). In that case there will be no search inconsistencies if we don't use a TT. MTD(f) works correctly in that case. If we do use a TT (on which MTD(f) depends) there will always be search inconsistencies, even without forward pruning and extensions and even if we clear the TT before the search. These are caused by the existence of transpositions with different path lengths to the root. The first time we search position p to depth d we store the result. The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d'), but if the entry is no longer present we search to depth d' and get a different result. Or, because of the new search window, the TT entry is found but does not cause a cutoff so we have to search anyway. I have examples where MTD(f) chooses a wrong move (with and without clearing the TT) but I expect these are difficult to reproduce in other programs.

My point is that using a TT implies having search inconsistencies, even in the basic case. And that textbook MTD(f) behaves incorrectly in case 2 with the last pass failing low. Even if (as expected) the second-last pass returns value >= v and the last pass returns value <= v. It is assumed that the last pass (which maximizes over what turn out to be upper bound values) will not change the best move. However, this assumption does not hold in case of search inconsistencies, so a wrong move is chosen. A problem for which an easy fix exists.

How did you solve this problem in (old) Damy? I learned that Ed Gilbert (of course) also has a way of solving this in Kingsrow. But there may be other programmers using MTD(f) who are unaware of this.

Jan-Jaap

Hi Jan,

I am not sure I fully understand your point but when you say:
"The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d')"
you clearly use a "hidden" extension because instead of using depth d' you use the result of depth d with d' < d.
If you want to avoid any extension you have to use the TT only for the exact depth you need.
Do you have still inconsistancies if you use TT only if the depth in TT is exactly the depth you need?

BTW you have also to solve loops with kings moves but I consider it is another problem isn't it?

[jj]

I am not sure I fully understand your point but when you say:
"The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d')"
you clearly use a "hidden" extension because instead of using depth d' you use the result of depth d with d' < d.
If you want to avoid any extension you have to use the TT only for the exact depth you need.

Yes. But that would be wasteful.

Do you have still inconsistancies if you use TT only if the depth in TT is exactly the depth you need?

No (see page 1).

BTW you have also to solve loops with kings moves but I consider it is another problem isn't it?

Yes, although the two problems are related.

Jan-Jaap

[TAILLE]

I am not sure I fully understand your point but when you say:
"The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d')"
you clearly use a "hidden" extension because instead of using depth d' you use the result of depth d with d' < d.
If you want to avoid any extension you have to use the TT only for the exact depth you need.

Yes. But that would be wasteful.
Jan-Jaap

Theoritically it is wasteful but only when kings are present in each side because with no kings on the board it is of course possible but very improbable to reach a position with two paths with different depths.

Taking aside loop problem do you agree that inconsistencies are related to pruning and (hidden) extension?

[jj]

Theoritically it is wasteful but only when kings are present in each side because with no kings on the board it is of course possible but very improbable to reach a position with two paths with different depths.

Yes, but there is also the issue of the present TT content. Clearing the TT takes time and is also considered wasteful. A previous (ponder) search can fill the TT with useful information. If you don't clear the TT, however, the problem becomes more likely to happen.

Taking aside loop problem do you agree that inconsistencies are related to pruning and (hidden) extension?

Yes. (Not clearing the TT also means hidden extensions, in your terminology.)

[TAILLE]

Theoritically it is wasteful but only when kings are present in each side because with no kings on the board it is of course possible but very improbable to reach a position with two paths with different depths.

Yes, but there is also the issue of the present TT content. Clearing the TT takes time and is also considered wasteful. A previous (ponder) search can fill the TT with useful information. If you don't clear the TT, however, the problem becomes more likely to happen.

Taking aside loop problem do you agree that inconsistencies are related to pruning and (hidden) extension?

Yes. (Not clearing the TT also means hidden extensions, in your terminology.)

Let me try to explain how I excluded any inconsistency for this problem.
First of all I consider pruning, extension and TT are essential in order to have a powerful MTD(f) algorithm. In addition clearing TT is a non-sense because you lost very valuable information. The solution I found is the following:
In your paper you use the fonction rootMT(root, moves, gamma, d) which return a value g. Here you assume that if g < gamma then g is the new upp value otherwise g is the new low. In my implementation I do not consider that the returned g value could always become the new low or the new upp. if g < gamma I only conclude that the new upp is gamma - 1 otherwise I only conclude that gamma is the new low.
Let's take an example:
The initial value for low and upp are -INF and +INF.
If I consider the initial position a little advantageous I may decide to begin by testing the value +20 and run the function rootMT(root, moves, +20, d). If the return value is g = +50 then low is set to +20 and I will run a new test "based" on the g value (and some other criterias): I will try to obtain for g a value greater than +50 and I will run (as you do?) the function rootMT(root, moves, +51, d). Let's now suppose that the return is g = -10. For you it is obviously an inconsistency but not for me. I set simply the upp to +50 and now I have obtained low = +20 ans upp = +50. I will continue by testing the middle value and I will run rootMT(root, moves, +35, d) etc.
That way I cannot have an inconsistency and I can use pruning, extension and TT without major problems.

[jj]

Let me try to explain how I excluded any inconsistency for this problem.
First of all I consider pruning, extension and TT are essential in order to have a powerful MTD(f) algorithm. In addition clearing TT is a non-sense because you lost very valuable information. The solution I found is the following:
In your paper you use the fonction rootMT(root, moves, gamma, d) which return a value g. Here you assume that if g < gamma then g is the new upp value otherwise g is the new low. In my implementation I do not consider that the returned g value could always become the new low or the new upp. if g < gamma I only conclude that the new upp is gamma - 1 otherwise I only conclude that gamma is the new low.
Let's take an example:
The initial value for low and upp are -INF and +INF.
If I consider the initial position a little advantageous I may decide to begin by testing the value +20 and run the function rootMT(root, moves, +20, d). If the return value is g = +50 then low is set to +20 and I will run a new test "based" on the g value (and some other criterias): I will try to obtain for g a value greater than +50 and I will run (as you do?) the function rootMT(root, moves, +51, d). Let's now suppose that the return is g = -10. For you it is obviously an inconsistency but not for me. I set simply the upp to +50 and now I have obtained low = +20 ans upp = +50. I will continue by testing the middle value and I will run rootMT(root, moves, +35, d) etc.
That way I cannot have an inconsistency and I can use pruning, extension and TT without major problems.

Thanks for explaining how you use the algorithm. Yes, you can have variations on MTD(f) like bisection or increasing/decreasing the step size. I wanted to show what can happen in the basic case.
Without pseudo code it is hard to see how your method plays out in different scenarios. You eventually have a last pass, which either fails high or fails low, right? If it was a fail low, how did you select the best move?

[TAILLE]

Yes, you can have variations on MTD(f) like bisection or increasing/decreasing the step size. I wanted to show what can happen in the basic case.

Yes you can implement MTD(f) in various manner and my point was only to show it is quite easy to avoid any inconsistency.
Let's take the basis case you explained in your paper.
If I understand correctly after having run rootMT(root, moves, g(k-2), d) you discover that with move m1 you reach a fail high and a return value g(k-1).
After that an inconsistency occur when you run rootMT(root, moves, g(k-1), d) because you discover now that with move m1 you reach a fail low and a return value < g(k-1).
Following this inconsistency you test all the other moves and if all other moves lead to a fail low then you have a problem to choose the best move. Your proposal is to choose the move m1 which make sense for me if g(k-1) - g(k-2) is small but could be doubtful if g(k-1) - g(k-2) is large. Why? Because the inconsistency discovered on move m1 proved that the return value g(k-1) may be far too optimistic!
We have to undertand clearly that the rootMT(root, moves, g(k-1), d) function is designed primarly for showing a fail high or a fail low. My view is that the exact return value itself is only an additional information that can of course be used but this return value has to be used with caution!

[jj]

Yes, you can have variations on MTD(f) like bisection or increasing/decreasing the step size. I wanted to show what can happen in the basic case.

Yes you can implement MTD(f) in various manner and my point was only to show it is quite easy to avoid any inconsistency.
Let's take the basis case you explained in your paper.
If I understand correctly after having run rootMT(root, moves, g(k-2), d) you discover that with move m1 you reach a fail high and a return value g(k-1).
After that an inconsistency occur when you run rootMT(root, moves, g(k-1), d) because you discover now that with move m1 you reach a fail low and a return value < g(k-1).
Following this inconsistency you test all the other moves and if all other moves lead to a fail low then you have a problem to choose the best move. Your proposal is to choose the move m1 which make sense for me if g(k-1) - g(k-2) is small but could be doubtful if g(k-1) - g(k-2) is large. Why? Because the inconsistency discovered on move m1 proved that the return value g(k-1) may be far too optimistic!
We have to undertand clearly that the rootMT(root, moves, g(k-1), d) function is designed primarly for showing a fail high or a fail low. My view is that the exact return value itself is only an additional information that can of course be used but this return value has to be used with caution!

Yes you are right. So how do you select the best move if the last pass fails low? Or do you re-search until you get a fail high again?

[TAILLE]

Yes, you can have variations on MTD(f) like bisection or increasing/decreasing the step size. I wanted to show what can happen in the basic case.

Yes you can implement MTD(f) in various manner and my point was only to show it is quite easy to avoid any inconsistency.
Let's take the basis case you explained in your paper.
If I understand correctly after having run rootMT(root, moves, g(k-2), d) you discover that with move m1 you reach a fail high and a return value g(k-1).
After that an inconsistency occur when you run rootMT(root, moves, g(k-1), d) because you discover now that with move m1 you reach a fail low and a return value < g(k-1).
Following this inconsistency you test all the other moves and if all other moves lead to a fail low then you have a problem to choose the best move. Your proposal is to choose the move m1 which make sense for me if g(k-1) - g(k-2) is small but could be doubtful if g(k-1) - g(k-2) is large. Why? Because the inconsistency discovered on move m1 proved that the return value g(k-1) may be far too optimistic!
We have to undertand clearly that the rootMT(root, moves, g(k-1), d) function is designed primarly for showing a fail high or a fail low. My view is that the exact return value itself is only an additional information that can of course be used but this return value has to be used with caution!

Yes you are right. So how do you select the best move if the last pass fails low? Or do you re-search until you get a fail high again?

In this scenario after having run rootMT(root, moves, g(k-2),d) I obtained low = g(k-2) and upp = +INF
then after having run rootMT(root, moves, g(k-1), d) I obtained low = g(k-2) and upp = g(k-1);
At this stage the logical continuation is to run the test : rootMT(root, moves, (g(k-1) + g(k-2))/2, d).

BTW, beside this very basic procedure I added some mechanisms to limit the number of tests. Typically in position where one move is obviously far better than any others I run only one test rootMT(root, moves, g(0), d) for a given depth.

[jj]

So how do you select the best move if the last pass fails low? Or do you re-search until you get a fail high again?

In this scenario after having run rootMT(root, moves, g(k-2),d) I obtained low = g(k-2) and upp = +INF
then after having run rootMT(root, moves, g(k-1), d) I obtained low = g(k-2) and upp = g(k-1);
At this stage the logical continuation is to run the test : rootMT(root, moves, (g(k-1) + g(k-2))/2, d).

You are describing the process of choosing gamma. I'm asking what happens when you completed the last pass (edit: when low >= upp). If the last pass failed low, which move do you return as best move?