Pathology on Game trees

[Michiel Koorn]

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

I understand the Beal effect. I can see it. I understand thing if I see them. I mean that quite literally.
Beal is caused because:
1) minimax understands a two player zero sum game
2) minimax converges noise to a constant for sufficient depth
3) only legal moves are allowed.
4) based on legal moves the game state is updated correctly
5) typically game problems end in 0 degrees of freedom for the loosing side. Inversely more degrees of freedom is typically better.
6) search depth allows for inheritance. N+1 search depth knows what the implications of N search depth knowledgeare for the opponent.

I do not see pathology, I don't understand the concept as emanating from the paper. I think it means that deeper search depth inevitably results in worse play for pathological games or trees or positions, independent of evaluation accuracy (since all evaluations are said to converge to random). For me this is in conflict with inheritance, so somehow inheritance does not apply during pathology. I do not see how this would come about.

Do you deny pathology in game trees at all or only the practical relevance in chess and similar game trees?

I think the convergence for larger search depth is misinterpreted to mean that play becomes more random. Beal shows this is not (always) so.
My working theory (still to be verified) is that in addition to above statement selecting the right move and getting the pv right are confounded in the paper. For one ply they are the same but after that no more.

I mean all the theoretical stuff researched by very smart people like Don Beal, Dana Nau, Judea Pearl, Bruce Abramson and others?

I am not a researcher so don't know the literature but the papers posted in this thread seem to imply that Nau is into pathology, and Beal mentions it and ignores it happily to hop along on his own research.

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.

As said I understand Beal, or I think I do, until someone corrects me. And yes this contradicts pathology. The boundary conditions I mentioned above are quite generic, and I don't see where they contradict the pathology assumptions.

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.

This is the horizon effect and it results from too shallow searches, postponing inevitable effects beyond its foresight (search depth). I think this is an example of the inverse of pathology.

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?

Again horizon

[Gerd Isenberg]

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.

This is the horizon effect and it results from too shallow searches, postponing inevitable effects beyond its foresight (search depth). I think this is an example of the inverse of pathology.

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?

Again horizon

Pathology might be related to the horizon effect, but pathology implies deeper search finds worse moves, while deeper search helps to avoid horizon effect most often, i.e. non pathological horizon effect. Horizon effect usually refers to some negative event which is inevitable but postponable, i.e. giving some pawns to postpone the loss of a rook. When the loss of the rook is determined at the root the first time after trying previous PV, an alternative delaying move improves alpha in the same iteration. But a deeper search helps to become aware of that later, to finally give the rook directly without postponing pawn losses, and may be to even get some counter play. There is no pathology where a deeper search would find a worse move.

Here I mean a quiet position where the program already feels that good at the root and may only improve by some centipawns in one or three plies, but not further for many moves even far behind the maximum search horizon of this root position. There are no tactical threats for both sides along the PV - it is about strategy and to put the pieces on the "right squares" - or to shuffle around to wait for the opponent to blunder. I guess despite the KBNK-sample, this are the situations in chess, where pathology may arise - a shallow search would be sufficient, but a deeper search stumbles to delay a reasonable good move, to push that positional maximum of a shallower search to the now farther horizon, but to amplify small evaluation errors and noise from the leaves to the root, suddenly playing a sub-optimal move - pathology.