Pathology on Game trees

[Michel]

The conclusion he has is rather trivial. Its that finding the moves to the best position in tree is less probable with high search depth. This is simply because there are more positions in trees with high search depth and thus a higher chance to miss it.

I don't have the paper here but wasn't conclusion rather that if you have an evaluation
function which can correctly predict whether a position is won/lost with probably p then prediction power becomes progressively LESS if you search deeper using minimax?

Of course the paper makes some assumptions which do not literally hold for real games so this is why in real games deeper search really yields a benefit.

[hgm]

With a truly wrong eval (e.g. piece values that are totally off, say N > R) it is kind of understandable that deeper search does not help. In this case the gae is full of pitfalls (bad trades), and deep search only makes the chances higher that the program will get one with its horizon, and will be drawn to it like a magnet.

[Gerd Isenberg]

A recent related paper:

* Brandon Wilson, Austin Parker and Dana Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

On the topic of random eval:

* Mark Levene and Trevor Fenner (1995). A Partial Analysis of Minimaxing Game Trees with Random Leaf Values. ICCA Journal, Vol. 18, No. 1, pp. 20-33, zipped ps
* Mark Levene and Trevor Fenner (2001). The Effect of Mobility on Minimaxing of Game Trees with Random Leaf Values. Artificial Intelligence, Vol. 130, No. 1, pdf

[Mangar]

A recent related paper:

* Brandon Wilson, Austin Parker and Dana Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

Hi Gerd,

thanks for posting those papers. Sadly once again it is oversimplified and not helpful. The paper makes the following assumtion: If the error that an evaluation fuction returns a false result is "e" then the error that two calls are both false is e*e. It´s school math that this is only true, if both evaluation calls are independant. If both calls are siblings of the search tree (after one move of the same position) they are largely related (at least in chess). As the basic assumption is not true, all the rest is false either.
Another point to consider is that in chess it is highly probable for "normal" positions, that playing a move will not result in worse evaluation results.

Greetings Volker

[Gerd Isenberg]

A recent related paper:

* Brandon Wilson, Austin Parker and Dana Nau (2009). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. pdf

Hi Gerd,

thanks for posting those papers. Sadly once again it is oversimplified and not helpful. The paper makes the following assumtion: If the error that an evaluation fuction returns a false result is "e" then the error that two calls are both false is e*e. It´s school math that this is only true, if both evaluation calls are independant. If both calls are siblings of the search tree (after one move of the same position) they are largely related (at least in chess). As the basic assumption is not true, all the rest is false either.
Another point to consider is that in chess it is highly probable for "normal" positions, that playing a move will not result in worse evaluation results.

Greetings Volker

Hi Volker,

yes, the initial assumption that siblings are independent (and only win or loss values) is most often not true for chess, which is likely the reason pathology does usually not exists in our domain. Anyway, I found the topic worth a cpw page

Cheers,
Gerd

[Michiel Koorn]

I don't see the issue of pathology

A position is proposed where the outcome is either won or lost. However the outcome cannot occur within the depth of a search. Emphasis on cannot. It is not that they are pruned out in a search, they simply don´t exist. For a 2 ply depth search a mate in 3 position is permissible, but the same position is not allowed in a 17 ply search. This is comparing apples and pears. For an increasing search depth the potential problem space shrinks, as more and more positions are solved and are omitted as a problem.

Furthermore the convergence described does not necessarily mean evaluation gets worse, random eval could get better, and in fact it does. Basically an eval can thought to be modelled as the outcome of random evaluation+ searchdepth d. For x to infinite random + searchdepth (x) over eval +searchdepth(x) (=random +searchdepth (x+d)) will go to 1.

Of course a deeper search could produce a wrong move, where a shallower one produces the right one by accident. Wandering around the board during an end game happens, and deeper does not make it necessarily better. The missing observation is that the shallower search may have given the right move despite it's lack of understanding of the position but it will not play the right sequence of moves to end the game in a win.

[Gerd Isenberg]

I don't see the issue of pathology

A position is proposed where the outcome is either won or lost. However the outcome cannot occur within the depth of a search. Emphasis on cannot. It is not that they are pruned out in a search, they simply don´t exist. For a 2 ply depth search a mate in 3 position is permissible, but the same position is not allowed in a 17 ply search. This is comparing apples and pears. For an increasing search depth the potential problem space shrinks, as more and more positions are solved and are omitted as a problem.

Furthermore the convergence described does not necessarily mean evaluation gets worse, random eval could get better, and in fact it does. Basically an eval can thought to be modelled as the outcome of random evaluation+ searchdepth d. For x to infinite random + searchdepth (x) over eval +searchdepth(x) (=random +searchdepth (x+d)) will go to 1.

Of course a deeper search could produce a wrong move, where a shallower one produces the right one by accident. Wandering around the board during an end game happens, and deeper does not make it necessarily better. The missing observation is that the shallower search may have given the right move despite it's lack of understanding of the position but it will not play the right sequence of moves to end the game in a win.

I think HG gave a good example with knight versus rook value - if the "eval error" is inherently that huge, that a deeper search would found even worse moves. Same might be true due to eval noise, where too many wrong tuned eval terms may interact in a pathological way, let say in a non tactical, quiet "no progress" position. Eval-granulation is a related issue, deci-, centi- or millipawn fixed point versus float or double. Beal's simplified minimax model where the error at the root amplifies - as a thought experiment to understand minimax better - has following assumptions:

1. uniform branching factor b
2. node values are either win or loss
3. true values conform to the minimax relationship
4. values are distributed so that at each level, the proportion of wins of the player to move are the same
5. heuristic values are identical to true values, the proportion of erroneous values being small compared to 1/b
6. heuristic values have a probability of error p, independent of the distribution of true values.

With p' as probability of error in 1-ply backed-up values with ply-level k greater than p.

Clearly this model does not capture some essential property of minimax search in typical game trees. It is not so clear, however, why this is so.

[Michiel Koorn]

I think HG gave a good example with knight versus rook value - if the "eval error" is inherently that huge, that a deeper search would found even worse moves. Same might be true due to eval noise, where too many wrong tuned eval terms may interact in a pathological way, let say in a non tactical, quiet "no progress" position.

I disagree, I don't think this is a good example. According to the graph in the original paper, wrong evals (neg correlation with victory) start out below random eval and converge from below for larger search depth.
As said, I don't see the issue

[Mangar]

Hi,

one reason why deeper searches are better than shallow searches can be explained by the example of othello.

Consider an othello alpha-beta implementation where the last 25 moves are allways fully calculated. Thus only the first 35 moves are searched using evaluation.
Write an evaluation that only count black vs. white pieces (every white piece gives +1 points, every black piece gives -1 points). This is a very poor evaluation for midgame in othello. The evaluation will change much after each move. You´ll see, that deeper searches will not increase game play performance.
But once you add the a huge bonus for having a corner piece, searching deeper will result in much better play.

IMHO all depends on evaluation. If you have stable evaluation terms that keeps their value after most moves, deeper search will give better results than shallow search. If you have "alernating" terms giving large changes with little amount of moves, then deeper search will not help.

Chess has such stable terms as material, king pressure, pawn structure, development, ... Thats why chess profits from deeper search.

Greetings Volker

[Gerd Isenberg]

I think HG gave a good example with knight versus rook value - if the "eval error" is inherently that huge, that a deeper search would found even worse moves. Same might be true due to eval noise, where too many wrong tuned eval terms may interact in a pathological way, let say in a non tactical, quiet "no progress" position.

I disagree, I don't think this is a good example. According to the graph in the original paper, wrong evals (neg correlation with victory) start out below random eval and converge from below for larger search depth.
As said, I don't see the issue

Fine. I am not so confident and still in a mental confusion and phase trying to understand stuff

Do you deny pathology in game trees at all or only the practical relevance in chess and similar game trees? I mean all the theoretical stuff researched by very smart people like Don Beal, Dana Nau, Judea Pearl, Bruce Abramson and others?

The somehow contrary Beal-effect with random leaf values where deeper search improves playing strength seems to support the thesis of absence of pathology in chess. But I am not sure, and have to admit that I still have problems to understand all that stuff. We have perfect versus erroneous heuristic knowledge, eval-noise, non uniform depth, and phases where no progress can be made inside the horizon. If a shallow search finds some local positional maximum - since I stand already quite perfect according to my eval, deeper searches may have a hard time to hold that score and tend to find all kind of "tricks" to postpone that stuff.

For instance the KBNK endgame with a simple positional evaluation considering the distance of the losing king to the board corners of the bishop color, and may be some more usual king and center distance stuff. A shallow, say 10 ply search may do better than a 12 or 14 ply search, because the search need to pass a valley few plies deep. Isn't that pathological behavior?