Dumb question about alpha-beta

[daylen]

Apologies if this is a really dumb question that has been asked and answered elsewhere, but I've searched for a while and couldn't find an answer.

Assume it's your turn to move and you are using alpha-beta pruning with minimax. The first move you consider is to take a bishop, so your lower bound is +3. The second move you consider is one in which you leave a rook unprotected. So at depth 2, the other side takes your rook and the upper bound is -5. Therefore, you cut off that node. But if you had searched to depth 3 without cutting any nodes, you could have realized that after their side takes your rook, you take their queen.

Obviously this doesn't happen with chess engines, so I must be missing something. How does alpha-beta pruning not cut off good nodes?

[Dirt]

One point is this is a horizon effect. If you go to depth 3 you will find it.

Also, though, a program usually has a quiescence search. This means that even at depth 2 it will look for captures hanging at the end and find the queen loss.

[daylen]

I see. Then quiescence search must be basically required for any chess engine, right? If you didn't have quiescence search, even if you did go to depth 3, you still wouldn't find the correct move (i.e. sac rook for queen) since you cut the branch at depth 2 (i.e. rook gets taken, oh no!).

So the modified logic goes something like this:
- if the score of a position is worse than the guaranteed lower bound, cut the node
- EXCEPT if the move was a capture (or maybe some other criteria for a risky position), then perform an additional depth of search and use that score?

[hgm]

..., even if you did go to depth 3, you still wouldn't find the correct move (i.e. sac rook for queen) since you cut the branch at depth 2 (i.e. rook gets taken, oh no!).

No, that is not true. You don't cut off based on the value of the victim of a single move. You cut off based on the score returned by a search of thet move. 'Score' is not what the static evaluation returns, but what the search returns. At 3 ply the counter-strike against the Queen will be within the horizon, so the move that captures the Rook will not get a +5 score (for the one that makes it), but a -4 score. This will be worse than the loss of the Bishop in the other branch.

The problem you mention at 1 ply has nothing to do with alpha-beta. Alpha-beta is a 100% guaranteed way to get exactly the same score and move as a complete minimax search of the same tree, with far less effort. The problem is that a fixed-depth minimax tree sucks. Or rather, that the conventional evaluation of counting material sucks in positions that are not 'quiet'. To repair that, you would either have to switch to an evaluation that can handle non-quiet positions, or extend the search in order to reach a position that is quiet enough for the evaluation to produce a meaningful result.

[daylen]

You cut off based on the score returned by a search of thet move.

In that case, you would never return since you can't search to the end of the game, right? Then you must choose an arbitrary depth to which you want to search to, and take the result of that evaluation. What arbitrary depth do you choose?

I *think* I understand what happens in the case you *can* search to the end:

Code: Select all

evaluate:
	if game over:
		return game status (win/loss/draw)
	for each move:
		evaluate that move (recursive)
		do pruning
	return best move

Because in this case, you are guaranteed that the score you get is "correct." What I don't get is the case in which your evaluation could fluctuate depending on what depth you search to.

[hgm]

In that case, you would never return since you can't search to the end of the game, right? Then you must choose an arbitrary depth to which you want to search to, and take the result of that evaluation. What arbitrary depth do you choose?

The answer is 'the larger the better'. When you cannot afford to search all the way upto mate, you seach as deep as you can (by increasing the depth in steps, and doing a new iteration if there still is time), and doing a heuristic static evaluation in the artificial leaves (based on material, mobility, etc.).

This has nothing to do with alpha-beta pruning. Even with plain minimax you would have a search horizon, beyond which you cannot afford to look.

The art of Chess programming is to shape the horizon (by reductions and extensions) in such a way that it captures the important stuff at the expense of missing the less important stuff, and making a good heuristic evaluation.

It is quite difficult to statically evaluate positions where tactics is in progress. In absence of an accurate evaluation of such tactics, it becomes very important where you terminate the branches of the search tree. Extending all captures indefinitely at the horizon (the classical capture search) is feasible in Chess, because sooner or later you will run out of captures, and allows the use of a 'tactically naive' evaluation. Alternatives would be to only extend captures of the piece that last moved, or only of insufficently protected or more-valuable pieces.

Basically the branch-termination scheme is a convergence-accelerating method, which makes the search score converge faster with depth to the true value. Less accurate QS can be compensated by more depth.

[PK]

In my first chess program, which has been very weak, I side-stepped the quiescence search completely. Instead if the terminal node was a capture, its material value has been substracted from eval. It was enough to weed out nonsensical scores, so the engine named Hopeless 0.10 played something that resembled chess. Of course version with quiescence search has beaten it soundly.

[bob]

Apologies if this is a really dumb question that has been asked and answered elsewhere, but I've searched for a while and couldn't find an answer.

Assume it's your turn to move and you are using alpha-beta pruning with minimax. The first move you consider is to take a bishop, so your lower bound is +3. The second move you consider is one in which you leave a rook unprotected. So at depth 2, the other side takes your rook and the upper bound is -5. Therefore, you cut off that node. But if you had searched to depth 3 without cutting any nodes, you could have realized that after their side takes your rook, you take their queen.

Obviously this doesn't happen with chess engines, so I must be missing something. How does alpha-beta pruning not cut off good nodes?

You are missing the "depth-first" part of the equation. You search to the endpoints of the tree, then back the scores up. Now when you get back to ply=2 you will know whether you win material or lose material by taking the rook. If you win material, you don't look at the rest of the moves at that ply, which is the savings alpha/beta provides.

[daylen]

You are missing the "depth-first" part of the equation. You search to the endpoints of the tree, then back the scores up.

I read http://www.cs.berkeley.edu/~jrs/61b/lec/17.pdf and what you said about alpha-beta search makes sense to me for the simple case of tic-tac-toe, since the depth-first search will terminate at a win/loss/draw and so accurate alpha/beta values are passed up. In the example given, you stop searching on move B since move A guarantees a draw, and move B also guarantees a draw or worse. So you start searching on move C.

Here's a tree of the scenario I described above: http://cl.ly/image/1m0k111V031u

If we do a minimax search with no pruning to depth 3, then we'll choose to do "Leave rook not protected" since that is a +4 and the other move is a +3. Where does pruning come into play?

[AlvaroBegue]

The numbers you are quoting aren't right or aren't relevant. The static evaluations of the non-leaves are irrelevant. Only the leaves get to be scored, and then their scores are backed up the tree using the minimax rule.

I suggest you start by implementing minimax search without pruning. Then you can make a few modifications to your code to enable alpha-beta pruning, which makes the search much more efficient, but should in principle return the same answer as minimax.