@user21820 Thanks! I'm having trouble understanding the second paragraph. The iteration is not very clear to me. For instance, if we are setting $m$ to be $\alpha$ first (if I understood correctly, $\alpha,\beta=-\infty,+\infty$ at the beginning), then we would evaluate the first position and set $t=-eval(d',-\beta,\infty)$ and then $m:=\max(m,t)$ will be $\infty$. What would happen next, and did I miss something?

@AloizioMacedo eval(d,−∞,∞) indeed sets m := −∞ then t := −eval(d',−∞,−m), which for the first move would be −eval(d',−∞,∞). But why would m := max(m,t) be ∞?

@user21820 You are right, got my $\pm \infty$ mixed up... But how does the program proceed? (Sorry for the triple ping)

After testing the first move m would be the t from the first move.

So the next move tested would be called with a smaller window.

In my post I wrote"t := −eval(d',−β,−m)", and gave a brief explanation of why the truncation to [−β,−m] does not affect the results of the procedure.

Do you prefer code?

But in the next iteration, who is $\alpha,\beta$?

Can I assume that you are familiar with plain negamax?

No, sorry.

But I am familiar with programming in general, if that helps.

Ah no wonder; I wrote my post with that intended audience. Then let me explain negamax first.

Sure, if you're willing!

Negamax is just a recursive function eval(d) that returns the value of the current position based on a search to 'depth' d. This is applicable for any 2-player zero-sum game including chess (outcomes sum to zero). For simplicity let's have the depth decrease by 1 per move. To compute eval(d), if d=0 then return its value, otherwise set m := −∞, and for each possible move X from the current position, perform X then set t:= −eval(d−1) and m := max(m,t) and undo X, and finally return m.

The name "negamax" comes from the negation in "−eval(d−1)" and the "max".

Negation because it is zero-sum. My best move is the one with the worst opponent value.

Got it?

Ok, I think I got it. (Here, eval is some blackbox-esque evaluation right?)

Which will depend on the game, but the procedure doesn't.

Only eval(0) is a black-box. The rest is all there.

Ah yes, the move making is all based on the game, yes.

(By the way I described negamax as a recursion with side effects, where it keeps altering the same board, because in many games it is more efficient than passing the entire board state in as a parameter, since only a small part of the board changes on each move. If this comment doesn't mean much to you, you can ignore it.)

Okay now the idea behind alpha-beta negamax is to compute exactly the same answer as plain negamax but without any unnecessary work!

So, let me see if I understand... at the end of this process, then -m is what is showed as the current evaluation of a given position?

@AloizioMacedo Not quite. m is the current evaluation. Remember that it is the best (max) negation of opponent value after I make a move.

So it is the value I have given the current position.

Oh okay, we keep with the perspective of opponent value.

When Stockfish says a position is +9, it means the best move has value +9 because it leads to opponent value of −9.

Bigger is more winning.

Ok, great. Please continue.

So the invariant behind alpha-beta negamax is that eval(d,α,β) is eval(d) truncated to the interval [α,β], meaning if it lies outside then it is snapped to the nearest endpoint.

And that paragraph in my post describes what eval(d,α,β) returns.

You can see that it is similar to plain negamax except that it sometimes returns earlier (knowing that further testing does not change the answer).

Let me quote what eval(d,α,β) does:

> We first set m := α before testing any move. When testing each subsequent move we would call t := −eval(d',−β,−m) and then set m := max(m,t). If m≥β then we can immediately return β. At the end we return m. The reason for calling "eval(d',−β,−m)" is that if the resulting position has true value u outside [−β,−m] then it would have equivalent effect on the true value v of the current position as the truncated value.

> (If u<−β, then −eval(d',−β,−m) yields β so we return β, which is correct since v>β. If u>−m, then −eval(d',−β,−m) yields m so it does not affect m, which is correct since that move led to true value of −u<m.) Here d' is set by a heuristic (e.g. quiescence search may set d' := d−1 for normal moves but d' := d−1/2 for check and d' := d for captures).

The "early return" is "If m≥β then we can immediately return β.". Indeed, once m≥β it can only increase further but we truncate to β anyway... so return β.

This relies on the call to "eval(d',−β,−m)" not affecting the result.

Well I suppose I should not try to simplify too much; it's better to just work through the cases carefully. =)

Read "true value" in the above as "plain negamax value".

I'll just give a sample expansion of the first case: "If u<−β, then −eval(d',−β,−m) yields β so we return β, which is correct since v>β."

Let eval[P](d) be the output of eval(d) when current position is P. Let P+X denote the position after performing move X from P. Take any position P and move X from P. Let u = eval[P+X](d'). If u<−β, then −eval[P+X](d',−β,−m) = β (by the claimed invariant), so eval[P](d,α,β) returns β immediately, which is correct since eval[P](d) > β (by definition of negamax).

To be technically precise, note that throughout we are using the invariant under structural recursion on the finite search tree comprising all the calls to eval. Namely, if eval[P+X](d',α',β') is eval[P+X](d') truncated to [α',β'] for every call of the form "eval(d',α',β')" that eval[P](d,α,β) makes, then eval[P](d,α,β) is also eval[P](d) truncated to [α,β].

What I mean is that we are merely proving the above implication, and then applying structural recursion to obtain the desired theorem.

Supposing that for a certain move X, $-eval[P+X](d',-\beta,-m)$ outputs some number $k$ which is not $\beta$, then what is $\beta$ for our calculation of $-eval[P+X'](d',-\beta,-m)$, where $X'$ is the next move that we are interested?

I think you missed the point that α,β are simply the 2nd and 3rd parameters to the recursive function. So doing "t := −eval(d',−β,−m)" calls that function with 2nd,3rd parameters being the (current) values of −β,−m respectively.

As we test more and more moves, m is increasing, so −m is decreasing, so the alpha-beta window that we pass to the function for evaluating each move is shrinking.

Hmm, but how do the values of $\beta$ change in the iterations? $m$ is being set to $\max(m,t)$ at each iteration, but I don't see how $\beta$ is changing.

Do you know what a recursive function is in programming?

Yes

Then I don't understand your question. eval(d,α,β) is literally passing −m as the "beta" to all the calls "−eval(d',−β,−m)".

Oh, of course.

So does it make sense now?

Yes

Formally, it is clear.

The intuitive reasoning for the truncation is still not so clear to me.

The intuition is just that when computing eval(d), instead of computing plain negamax eval(d'), we pass some additional information so that we can stop the computation if the result from that eval(d') will not affect the final result of this eval(d).

What can we pass? Well, we have the 'current best value' m, and we also have the extra information from above.

The better the current best, the more 'demanding' we should be of how bad the opponent value is for the next move we test. That's why the window we pass in [−β,−m] is shrinking from the top. If the opponent's value is better than −m, then this move is lousy compared to the move that got us value m.

@AloizioMacedo: Well we can use concrete example. Suppose you put your queen up for my pawn to capture it. I evaluate that move first, which is very yummy. I then look for other moves but I demand that they are at least as yummy, so while I am evaluating other moves I am always looking for how they can possibly get me as good as a queen up.

I don't know. Alpha-beta can seem mysterious the first time you meet it. It was mysterious to me too when I first learnt about it.

(Partly because at that time I didn't have the mathematical capability to formalize my intuition!)

@user21820 Okay, let's try to run through that specific example, because upon reflection I think I actually did not understand. So, assuming that we are the player that has the possibility of capturing the queen, if that move (capturing the queen) is the first move under scrutiny, then we will run t=-eval(d', -\infty, \infty) which will be something like, t=-(-9)=9. Then, m will become 9 (as it is max(-\infty,9)).

Yup.

So for every subsequent move X, we will perform X then do t := −eval(d',−∞,−9). This is efficient because whenever eval(d',−∞,−9) tests a move and finds its value exceeds −9 it immediately quits and returns −9.

OK, but I think what is confusing me is that I don't see how that lower bound of $-\infty$ in the interval would change. Can it change?

Oh wait

The −9 is the 'beta' in eval(d',−∞,−9), right? The β is passed in via −eval(d',−β,−m), so it becomes the 'alpha'..

It's a really nice cascade of information roughly every two moves down the tree.

The α is also pushing up the initial starting point of m, so it does limit the 'beta' in the recursive calls.

For example, if the next move were to be worse for the opposing player, say $eval=-12$, then $t=12$ and $max(m,t)=12$, thus $m$ becomes $12$. At this point we are still considering $\beta=\infty$, so the algorithm runs on, and now I'm certainly missing something because it looks like the next evaluation would be $eval(d',9,-12)$, which doesn't make sense.

Could you write the iteration in a pseudocode fashion together with the attributions of $\alpha,\beta$ and $m$? If possible, I think that could help me.

@AloizioMacedo I think you're getting confused because you're passing the wrong parameters in. Maybe you should just draw out the tree.

def eval(depth,alpha,beta):
	if depth=0: return ...;
	m:=alpha;
	for move in moves():
		perform(move);
		d:=...;
		t:=-eval(d,-beta,-m);
		undo(move);
		m:=max(m,t);
		if m>=beta: return beta;
	return m;

@user21820 That's great!

So, for example, if depth=1 and say that $d=depth-1$ regardless, then all the evaluations will have as lower bound -$\infty$, correct?

If depth=2, then in some tree, what would happen in that example we were considering is that we could have a sequence of "local" evaluations eval(d,-9,-6), eval(d,-9,-7), eval(d,-9,-7.5)...

The answer to your first question taken literally is no. But eval(1,−∞,∞) results in only calls to eval(0,−∞,?), yes.

And to your second inquiry, indeed.

So considering the procedure fixed, the things that the engines have latitude over are the choices of the depth, how we choose each $d$ which can depend on the move being analyzed on a tree and the evaluation itself. Mostly, then, it is how to choose each $d(move)$ and the evaluation, right? That choice of $d(move)$ is what is intuitively the pruning?

@AloizioMacedo Yes d depends on the move and depth, as in quiescence search. The base-case evaluation is also called static evaluation. But no, the depth control is not really considered pruning at all.

Some people call alpha-beta "alpha-beta pruning". I prefer not to think of it as part of 'real' pruning.

Quiescence search, too, is a mechanism that has nothing to do with pruning in my (subjective) opinion.

How does pruning enter the picture?

In the algorithm, I mean.

@AloizioMacedo Heuristic pruning as described in my answer mean that moves() does not return all the possible moves from the current position, or you add some extra early returns that may not be sound.

The example I gave in my post can be incorporated as follows:

def eval(depth,alpha,beta):
	if depth=0: return ...;
	m:=alpha;
	for move in moves():
		perform(move);
		d:=...;
		if d>4:
			u:=-eval(4,-beta,-m);
			if u+3<=m:
				undo(move);
				continue;
		t:=-eval(d,-beta,-m);
		undo(move);
		m:=max(m,t);
		if m>=beta: return beta;
	return m;

This is slightly different from the one in my post, being slightly superior, but it's the same idea. The one in my post was a simpler version that I thought of when writing it.

@Skaldebane You can ask @AlessandroCodenotti for the intended scope of the room (he is the room owner), but for what it's worth, the room is named after a joke-opening of chess, so it is safe to assume that the room is intended for chess discussions of some kind.

Anyway, you can see that we skip some moves based on a search to a much shallower depth (here 4) than we would normally (i.e. d). It would fail to get the negamax answer if there is a tactic of 'depth' more than 4. Quiescence search helps to prevent such issues.

@user21820 OK, got it. It is very comprehensive.

Thank you! Anyway, I need to go soon. =)

@AloizioMacedo: So see you next time!

@user21820 See you! Thanks for taking your time, and sorry if it took a while for me to get some aspects of it.

No problem. I always enjoy explaining the mathematical side of anything. =)

There were some vague ideas of making a chess study group, but since that is not happening any kind of chess related discussion is appreciated here