Alpha Beta Pruning in Adversarial Search

Minimax Implementation

def max-value(state):
	initialize v = -∞
	for each successor of state:
		v = max(v, min-value(successor))
	return v

def min-value(state):
	initialize v = +∞
	for each successor of state:
		v = min(v, max-value(successor))
	return v

$V(s)=max(V(s^{\prime }))s^{\prime }\in successor(s)$

$V(s^{\prime })=min(V(s))s\in successor(s^{\prime })$

Alpha Beta Pruning

General configuration (MIN version)
  We’re computing the MIN-VALUE at some node n
  We’re looping over n’s children
  n’s estimate of the childrens’ min is dropping
  Who cares about n’s value? MAX
  Let $\alpha$ be the best value that MAX can get at any choice point along the current path from the root
  If n becomes worse than $\alpha$, MAX will avoid it, so we can stop considering n’s other children (it’s already bad enough that it won’t be played)

MAX version is symmetric

Examples

To start with, we know nothing about the bounds, so we set $\alpha =-\infty ,\beta =\infty$.

Then we passing along the bounds to the child, child’s child…

Now we reach at the level: depth of 4. We run our evaluation functions here.

An evaluation function is like:
Ideal function: returns the actual minimax value of the position
In practice: typically weighted linear sum of features: $Eval(s)=w_1{f}_1(s)+\cdot \cdot \cdot +w_n{f}_n(s)$.

We get value 3, since this is a min node, we now know the minmax value must be less than or equal to 3, thus, we set $\beta =3$.

Next child in depth 4 is value 17, while 17 > 3, we ignore this child.

All children handled, we return to depth 3. we have $\beta =3$ here, so we can set $\alpha =3$ at the depth 2 node.

We pass along the bounds of depth2 to next child of depth3.

At this moment, we get $\alpha =3and\beta =2,\alpha >\beta$.
If these values are to change, children values would be greater than 3 and less than 2, which is impossible. We can prune any children and return.

We do these steps recursively, we will reach this:

Some pictures and ideas comes from $https://www.cs.ucla.edu/$.

Two Quiz

notice: I do not have answers.