Upper and Lowerbound

[DaOnlyOwner]

Hey guys,
I have another question that came up when I implemented transposition tables.

So quoting chessprogramming.org "A Lower Bound is returned from an Alpha-Beta like search, if it fails high. The node searched was a confirmed Cut-Node." Why is this the case. Wouldn't it make more sense if it were a Upper Bound?

Thanks

[emadsen]

A Lower Bound is returned from an Alpha-Beta like search, if it fails high... Why is this the case. Wouldn't it make more sense if it were a Upper Bound?

A fail-high creates a lower bound, that's correct. In a fail-hard alpha / beta search, a move that fails high is a strong move. Problem is, you don't know how strong. If beta is 100, the move is scored as 100 and causes a beta cutoff (hence the phrase "cut node"). You know the true evaluation lies between 100 and +infinity. So the "lower bound" of the true eval is 100.

[DaOnlyOwner]

Ahh now I understand. Thank you, the site doesn't make this clear, but through this explanation I understand it now.

[mvanthoor]

Ahh now I understand. Thank you, the site doesn't make this clear, but through this explanation I understand it now.

That a fail high causes a lower bound, and a fail low causes a higher bound took me some time to wrap my head around as well. In the end, if, you have the metal picture complete, you get this:


minus-inf ====bad for you=========||alpha||=======PV-moves=========||beta||=========good for opponent===========plus-inf

When searching for a side, you start at minus infinity, assuming the worst ever. When you search, you find better and better mvoes, and alpha gets higher and higher These are moves that are better and better candidates to play. Alpha-beta switches back and forth between your opponent; so HE comes in from the other side of the above line, but he reasons about it in the same way as you do, because the function reverses all the signs on each call.

So you start at minus infinity, and the moves become better and better and better (alpha is increasing),but at some point, your score exceeds bèta. This means the move is not good for you anymore (it is in the "opponent's side of the line"), and thus you cut off your search there: the so-called bèta cutoff. You don't want to search further in that branch. You don't need to know "how much bad" the move is; you know it's better for your opponent than it is for you, so you cut.

The point where you want to be is between alpha and bèta: those moves make up the principal variation. They are the best moves for you (and, from the other side, the best moves for the opponent). The faster your engine is, the deeper it can search, and the better the evaluation is, the narrower and more precise the engine can determine where "alpha" and "beta" are, making the gap as narrow as possible, and picking the best move within that gap.

The more precise you can determine alpha and bèta and pick a move in there (in perfect play, there should only be one move between alpha and bèta, and both bounds should be perfectly placed), the stronger your engine will be.