Combine mtd-best & ID iterations

[Michiel Koorn]

Has anyone combined mtd best (bi) and ID iterations? If so what were the bottlenecks?

The basic idea is that there are two uncertainties in the estimate of the pv- move evaluation:
1) upperbound-lowerbound interval: we don't know the exact value of the current evaluation
2) search depth: we don't know if the current best move is the real best move, so what is the value of having an exact score?
Phrased in another way: if two moves are within the error margin for depth d the better way to evaluate them is depth d+1.
In pseudo code

Code: Select all

while time_remaining>0
{
  go through (part of) the move list with alphabeta(pos,gamma-1,gamma,d)
  count faillow
  re-order list based on failhigh / faillow results
  if (&#40;upperbound - lowerbound < error&#41; or faillow_count==1&#41;
  //alternatives estimated within error margin or a best move found
  &#123;
    d++
    reset upper & lower bounds
  &#125;
  else
    gamma= f&#40;gamma, lowerbound, upperbound, stepsize&#41;//adjust gamma to get a better cut off between best move & alternatives
  error = f&#40;error,game phase,d,time_remaining&#41;// adjust allowable error to increase/decrease resolution if desired
&#125;

[Gerd Isenberg]

Has anyone combined mtd best (bi) and ID iterations? If so what were the bottlenecks?

The basic idea is that there are two uncertainties in the estimate of the pv- move evaluation:
1) upperbound-lowerbound interval: we don't know the exact value of the current evaluation
2) search depth: we don't know if the current best move is the real best move, so what is the value of having an exact score?
Phrased in another way: if two moves are within the error margin for depth d the better way to evaluate them is depth d+1.
In pseudo code

Code: Select all

while time_remaining>0
{
  go through (part of) the move list with alphabeta(pos,gamma-1,gamma,d)
  count faillow
  re-order list based on failhigh / faillow results
  if (&#40;upperbound - lowerbound < error&#41; or faillow_count==1&#41;
  //alternatives estimated within error margin or a best move found
  &#123;
    d++
    reset upper & lower bounds
  &#125;
  else
    gamma= f&#40;gamma, lowerbound, upperbound, stepsize&#41;//adjust gamma to get a better cut off between best move & alternatives
  error = f&#40;error,game phase,d,time_remaining&#41;// adjust allowable error to increase/decrease resolution if desired
&#125;

Nope, no idea.

Is what you call mtd best (bi) mentioned in these papers as mtd(bi), the C* or NegaC* like bisection schemes, which requires doubles instead of integers?

Jacek Mandziuk and Daniel Osman (2004) ALPHA-BETA SEARCH ENHANCEMENTS WITH A REAL-VALUE GAME-STATE EVALUATION FUNCTION

with reference to

Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms, pdf

[Michiel Koorn]

Source of the name is is section 3 of http://publishing.eur.nl/ir/repub/asset ... -95-03.pdf, combining the best and bi schemes.

[Gerd Isenberg]

Source of the name is is section 3 of http://publishing.eur.nl/ir/repub/asset ... -95-03.pdf, combining the best and bi schemes.

Thanks. I have no experience with mtd at all, always stuck with PVS.

[bob]

Source of the name is is section 3 of http://publishing.eur.nl/ir/repub/asset ... -95-03.pdf, combining the best and bi schemes.

Thanks. I have no experience with mtd at all, always stuck with PVS.

I worked on it for about 6 months, off and on, mostly on, several years ago. It has some promise, in that a perfect null-window search everywhere goes very fast. But it is the re-searches to tighten the bounds on the final score that was (to me) the killer. 10 re-searches is worse than a single PVS search. I actually have an mtd(f) version (I did not write this one) based on 23.0 that someone used as a project and just presented a paper on it I believe. It seemed to be close to 23.0, but lagged behind by a half-dozen Elo or so.

Personally, with respect to alpha/beta, I think PVS is about as good as it gets.

[Michiel Koorn]

I worked on it for about 6 months, off and on, mostly on, several years ago. It has some promise, in that a perfect null-window search everywhere goes very fast. But it is the re-searches to tighten the bounds on the final score that was (to me) the killer. 10 re-searches is worse than a single PVS search.

The 10 re-searches you are talking about, is that for one fixed depth? Because the only novelty I think I came up with is smearing those re-searches over increasing depth. Basically I propose to search deth and score in parallel. Not doing 170 re-searches over 17 ply depth, but only say 100, by increasing resolution (reducing error) over depth.
I crunched some numbers for stockfish. I wont go so fas as to call them statistics, for lack of sample size( 1 1/2 match). 80% of iterations fall within [-16,16] cp of the previous ply, with no trend over depth. 75% of next best moves are more than 16 cp off. This suggests to me that the algorithm might be feasible for the bulk of moves. The real issue is probably how does it work for the non bulk.

I actually have an mtd(f) version (I did not write this one) based on 23.0 that someone used as a project and just presented a paper on it I believe. It seemed to be close to 23.0, but lagged behind by a half-dozen Elo or so.

I had planned on using stockfish as a test bed (I like its coding style & transparency), but not having to implement the MTD(f) code saves me a lot of work. I code in errors per line, not lines per error. Is it possible to compile crafty with vs 2005 without too much work?

[bob]

I worked on it for about 6 months, off and on, mostly on, several years ago. It has some promise, in that a perfect null-window search everywhere goes very fast. But it is the re-searches to tighten the bounds on the final score that was (to me) the killer. 10 re-searches is worse than a single PVS search.

The 10 re-searches you are talking about, is that for one fixed depth? Because the only novelty I think I came up with is smearing those re-searches over increasing depth. Basically I propose to search deth and score in parallel. Not doing 170 re-searches over 17 ply depth, but only say 100, by increasing resolution (reducing error) over depth.
I crunched some numbers for stockfish. I wont go so fas as to call them statistics, for lack of sample size( 1 1/2 match). 80% of iterations fall within [-16,16] cp of the previous ply, with no trend over depth. 75% of next best moves are more than 16 cp off. This suggests to me that the algorithm might be feasible for the bulk of moves. The real issue is probably how does it work for the non bulk.

I actually have an mtd(f) version (I did not write this one) based on 23.0 that someone used as a project and just presented a paper on it I believe. It seemed to be close to 23.0, but lagged behind by a half-dozen Elo or so.

I had planned on using stockfish as a test bed (I like its coding style & transparency), but not having to implement the MTD(f) code saves me a lot of work. I code in errors per line, not lines per error. Is it possible to compile crafty with vs 2005 without too much work?

I don't see how you can go to the next depth before you get some idea of what the best value is at the current depth. If your estimate is too low, most any move could fail high and be considered best. If the estimate is too high, everything will fail low and again you have no idea which move is best. My "10 passes" comment was for a single iteration. Sometimes you can do it in 2-3-4 passes, sometimes more. It doesn't take much to push you beyond the search space of normal PVS.

Changing the depth as you change the window offset seems problematic, because depth can change the final score also.

[Michiel Koorn]

I don't see how you can go to the next depth before you get some idea of what the best value is at the current depth.

Some idea is defined as highest- lowest<error or no more than one lowerbound returned

[bob]

I don't see how you can go to the next depth before you get some idea of what the best value is at the current depth.

Some idea is defined as highest- lowest<error or no more than one lowerbound returned

However, that doesn't address my question. Each new iteration can and often will shift the score by a significant margin, sometimes up, sometimes down. You still have to find the best move to make this work, and if your estimate on lower bound is too high, you get no best move at all, if it is too low, you get a random best move which is just as bad. I don't see how you avoid refining the bounds before going to the next depth, otherwise you are shooting at a moving target, and missing has dire consequences.

[Michiel Koorn]

To me it seems that the gist of your remark is either
1) what is the value of error?
2) I doubt it will work for any level of error
With error=0 it defaults to mtd(f). This does not work due to too many iterations. Open question is error >0
Breaking it down

However, that doesn't address my question. Each new iteration can and often will shift the score by a significant margin, sometimes up, sometimes down.

Sure, 20% shift more than +-16

You still have to find the best move to make this work, and if your estimate on lower bound is too high, you get no best move at all, if it is too low, you get a random best move which is just as bad.

Worst case you perform the move that wast best at some lower depth but now is a maximum of error worse than the best one

I don't see how you avoid refining the bounds before going to the next depth, otherwise you are shooting at a moving target, and missing has dire consequences.

I am not suggesting not iterating at all at a given depth. I still have to verify if lowerbound and upperbound are less than error