Alpha-Beta Pruning: Algorithm and Analysis

Tsan-sheng Hsu

tshsu@[Link]

[Link]

1
 Introduction
Alpha-beta pruning is the standard searching procedure used for
solving 2-person perfect-information zero sum games exactly.
Definitions:
• A position p.
• The value of a position p, f (p), is a numerical value computed from
evaluating p.
. Value is computed from the root player’s point of view.
. Positive values mean in favor of the root player.
. Negative values mean in favor of the opponent.
. Since it is a zero sum game, thus from the opponent’s point of view,
the value can be assigned −f (p).
• A terminal position: a position whose value can be decided.
. A position where win/loss/draw can be concluded.
. A position where some constraints, e.g., time limit and depth limit, are
met.
• A position p has b legal moves p1, p2, . . . , pb.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 2

 Tree node numbering

1 2 3

1.1 1.2 1.3 2.1 2.2 3.1 3.2

3.1.1 3.1.2

From the root, number a node in a search tree by a sequence

of integers a1.a2.a3.a4 · · ·
• Meaning from the root, you first take the a1th branch, then the a2th
branch, and then the a3th branch, and then the a4th branch · · ·
• The root is specified as an empty sequence.
• The depth of a node is the length of the sequence of integers specifying
it.
This is called “Dewey decimal system.”

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 3

 Mini-max formulation
max

min

max
1 5 6 7 2 7

min
1 8

Mini-max formulation:
• 
f (p) if b = 0
F 0(p) = 0 0
max{G (p1), . . . , G (pb)} if b > 0
• 
f (p) if b = 0
G0(p) =
min{F 0(p1), . . . , F 0(pb)} if b > 0
• An indirect recursive formula with a bottom-up evaluation!
• Equivalent to AND-OR logic.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 4

 Mini-max formulation
max

min
1
2

max
1 5 6 7 2 8 7

min
1 8

Mini-max formulation:
• 
f (p) if b = 0
F 0(p) = 0 0
max{G (p1), . . . , G (pb)} if b > 0
• 
f (p) if b = 0
G0(p) =
min{F 0(p1), . . . , F 0(pb)} if b > 0
• An indirect recursive formula with a bottom-up evaluation!
• Equivalent to AND-OR logic.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 5

 Mini-max formulation
max

min
1
2 7

max
1 5 6 7 2 8 7

min
1 8

Mini-max formulation:
• 
f (p) if b = 0
F 0(p) = 0 0
max{G (p1), . . . , G (pb)} if b > 0
• 
f (p) if b = 0
G0(p) =
min{F 0(p1), . . . , F 0(pb)} if b > 0
• An indirect recursive formula with a bottom-up evaluation!
• Equivalent to AND-OR logic.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 6

 Mini-max formulation
max
7

min
1
2 7

max
1 5 6 7 2 8 7

min
1 8

Mini-max formulation:
• 
f (p) if b = 0
F 0(p) = 0 0
max{G (p1), . . . , G (pb)} if b > 0
• 
f (p) if b = 0
G0(p) =
min{F 0(p1), . . . , F 0(pb)} if b > 0
• An indirect recursive formula with a bottom-up evaluation!
• Equivalent to AND-OR logic.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 7

 Algorithm: Mini-max
Algorithm F 0(position p) // max node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := −∞
. for i := 1 to b do
. t := G0(pi)
. if t > m then m := t // find max value
• end;
• return m
Algorithm G0(position p) // min node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := ∞
. for i := 1 to b do
. t := F 0(pi)
. if t < m then m := t // find min value
• end;
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 8

 Mini-max: comments
A brute-force method to try all possibilities!
• May visit a position many times.
Depth-first search
• Move ordering is according to order the successor positions are gener-
ated.
• Bottom-up evaluation.
• Post-ordering traversal.
Q:
• Iterative deepening?
• BFS?
• Other types of searching?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 9

 Mini-max: revised (1/2)
Search a max-node position p with a depth of depth.
Algorithm F 0(position p, integer depth) // max node
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
then return f (p)// current board value
else begin
. m := −∞ // initial value
. for i := 1 to b do // try each child
. begin
. t := G0(pi, depth − 1)
. if t > m then m := t // find max value
. end
end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 10

 Mini-max: revised (2/2)
Search a min-node position p with a depth of depth.
Algorithm G0(position p, integer depth) // min node
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
then return f (p)// current board value
else begin
. m := ∞ // initial value
. for i := 1 to b do // try each child
. begin
. t := F 0(pi, depth − 1)
. if t < m then m := t // find min value
. end
end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 11

 Nega-max formulation
max

min

max
1 5 6 7 2 7

min
−1 −8

Nega-max formulation:
Let F (p) be the greatest possible value achievable from position
p against the optimal defensive strategy.
• 
h(p) if b = 0
F (p) =
max{−F (p1), . . . , −F (pb)} if b > 0
. 
f (p) if depth of p is 0 or even
h(p) =
−f (p) if depth of p is odd
. h(p) is the position’s value from the point of view of the player of p.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 12

 Nega-max formulation
max

min
−1
neg neg −2
neg neg neg
max
1 5 6 7 2 neg 8 neg 7

min
−1 −8

Nega-max formulation:
Let F (p) be the greatest possible value achievable from position
p against the optimal defensive strategy.
• 
h(p) if b = 0
F (p) =
max{−F (p1), . . . , −F (pb)} if b > 0
. 
f (p) if depth of p is 0 or even
h(p) =
−f (p) if depth of p is odd
. h(p) is the position’s value from the point of view of the player of p.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 13

 Nega-max formulation
max

min
−1
neg −2
neg neg neg neg neg −7 neg
max
1 5 6 7 2 neg 8 neg 7

min
−1 −8

Nega-max formulation:
Let F (p) be the greatest possible value achievable from position
p against the optimal defensive strategy.
• 
h(p) if b = 0
F (p) =
max{−F (p1), . . . , −F (pb)} if b > 0
. 
f (p) if depth of p is 0 or even
h(p) =
−f (p) if depth of p is odd
. h(p) is the position’s value from the point of view of the player of p.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 14

 Nega-max formulation
max
neg 7 neg neg

min
−1
neg −2
neg neg neg neg neg −7 neg
max
1 5 6 7 2 neg 8 neg 7

min
−1 −8

Nega-max formulation:
Let F (p) be the greatest possible value achievable from position
p against the optimal defensive strategy.
• 
h(p) if b = 0
F (p) =
max{−F (p1), . . . , −F (pb)} if b > 0
. 
f (p) if depth of p is 0 or even
h(p) =
−f (p) if depth of p is odd
. h(p) is the position’s value from the point of view of the player of p.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 15

 Algorithm: Nega-max
Algorithm F (position p, integer depth)
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
• then return h(p) else
• begin
. m := −∞
. for i := 1 to b do
. begin
. t := −F (pi, depth−1) // recursive call, the returned value is negated
. if t > m then m := t // always find a max value
. end
• end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 16

 Nega-max: comments
Another brute-force method to try all possibilities.
• Use h(p) instead of f (p).
. Zero-sum game: if one player thinks a position p has a value of w, then
the other player thinks it is −w.
. min{x, y, z} = −max{−x, −y, −z}.
. max{x, y, z} = −min{−x, −y, −z}.
• Watch out the code in dealing with search termination conditions.
. Reach a given searching depth.
. Timing control.
. Other constraints such as the score is good or bad enough.

Notations:
• F 0 means the Mini-max version.
. Need a G0 companion.
. Easy to explain.
• F means the Negamax version.
. Simpler code.
. Maybe difficult to explain.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 17

 Intuition for improvements
Branch-and-bound: using information you have so far to cut or
prune branches.
• A branch is cut means we do not need to search it anymore.
• If you know for sure or almost sure the value of your result is more
than x
and the current search result for this branch so far can give you no
more than x,
. then there is no need to search this branch any further.

Two types of approaches

• Exact algorithms: through mathematical proof, it is guaranteed that
the branches pruned won’t contain the solution.
. Alpha-beta pruning: reinvented by several researchers in the 1950’s
and 1960’s.
. Scout.
. ···
• Approximated heuristics: with a high probability that the solution won’t
be contained in the branches pruned.
. Obtain a good estimation on the remaining cost.
. Cut a branch when it is in a very bad position and there is little hope
to gain back the advantage.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 18

 Alpha cut-off
V>=15

1 2
V <= 10
V=15
2.1 2.2 cut
V=10

• On the max node which is the root:

. Assume you have finished exploring the branch at 1 and obtained the
best value from it as bound.
. You now search the branch at 2 by first searching the branch at 2.1.
. Assume branch at 2.1 returns a value that is ≤ bound.
. Then no need to evaluate the branch at 2.2 and all later branches of 2,
if any, at all.
. The best possible value for the branch at 2 must be ≤ bound.
. Hence we should take value returned from the branch at 1 as the best
possible solution.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 19

 Beta cut-off

1 2
V<=8
1.1 1.2 V >= 13
V=8
cut
1.2.1 1.2.2
V=13

• On the min node 1:

. Assume you have finished exploring the branch at 1.1 and obtained the
best value from it as bound.
. You now search the branch at 1.2 by first exploring the branch at 1.2.1.
. Assume the branch at 1.2.1 returns a value that is ≥ bound.
. Then no need to evaluate the branch at 1.2.2 and all later branches of
1.2, if any, at all.
. The best possible value for the branch at 1.2 is ≥ bound.
. Hence we should take value returned from the branch at 1.1 as the best
possible solution.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 20

 Deep alpha cut-off
For alpha cut-off:
. For a min node u, a branch of its ancestor (e.g., an elder brother of its parent)
produces a lower bound Vl .
. The first branch of u produces an upper bound Vu for v .
. If Vl ≥ Vu, then there is no need to evaluate the second branch and all later
branches, of u.

Deep alpha cut-off:

. Def: For a node u in a tree and a positive integer g , Ancestor(g , u) is the
direct ancestor of u by tracing the parent’s link g times.
. When the lower bound Vl is produced at and propagated from u’s great grand
parent, i.e., Ancestor(3,u), or any Ancestor(2i + 1,u), i ≥ 1.
. When an upper bound Vu is returned from the a branch of u and Vl ≥ Vu,
then there is no need to evaluate all later branches of u.

We can find similar properties for deep beta cut-off.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 21

 Illustration — Deep alpha cut-off
V>=15

1 2
V=15
2.1 2.2
V>=15
2.1.1
V <= 7

[Link] [Link] cut

V=7

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 22

 Ideas for refinements
During searching, maintain two values alpha and beta so that
• alpha is the current lower bound of the possible returned value;
. This means to say you know a way to achieve the value alpha.
• beta is the current upper bound of the possible returned value.
. This means to say your opponent knows a way to achieve a value of
beta.
• If alpha = beta, then we have found the solution.
If during searching, we know for sure alpha > beta, then there
is no need to search any more in this branch.
• The returned value cannot be in this branch.
• Backtrack until it is the case alpha ≤ beta.
The two values alpha and beta are called the ranges of the
current search window.
• These values are dynamic.
• Initially, alpha is −∞ and beta is ∞.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 23

 Alpha-beta pruning algorithm: Mini-Max
Algorithm F 10(position p, value alpha, value beta) // max node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := alpha
. for i := 1 to b do
. t := G10(pi, m, beta)
. if t > m then m := t // improve the current best value
. if m ≥ beta then return(beta) // beta cut off
• end; return m
0
Algorithm G1 (position p, value alpha, value beta) // min node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := beta
. for i := 1 to b do
. t := F 10(pi, alpha, m)
. if t < m then m := t
. if m ≤ alpha then return(alpha) // alpha cut off
• end; return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 24

 Example
Initial call: F 10(root,−∞,∞)
• m = −∞

• call G10(node 1,−∞,∞)

. it is a terminal node
. return value 15

• t = 15; V>=15
. since t > m, m is now 15
1 2
V <= 10
V=15
0
• call G1 (node 2,15,∞) 2.1 2.2 cut
. call F 10(node 2.1,15,∞) V=10

. it is a terminal node; return 10

. t = 10; since t < ∞, m is now 10
. alpha is 15, m is 10, so we have
an alpha cut off,
. no need to call
F 10(node 2.2,15,10)
. return 15
. ···

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 25

 A complete example
max

min

max
7 2 7 1 5 6
min

8 1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 26

 A complete example
max

min

max
7 2 7 1 5 6
min

8 1

The solution is the same with or without the cut.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 27

 Alpha-beta pruning algorithm: Nega-max
Algorithm F 1(position p, value alpha, value beta, integer depth)
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
• then return h(p) else
• begin
. m := alpha
. for i := 1 to b do
. begin
. t := −F 1(pi, −beta, −m, depth − 1)
. if t > m then m := t
. if m ≥ beta then return(beta) // cut off
. end
• end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 28

 Examples (1/4)
max

min

max
7 2 7 1 5 6
min

8 1

max

min

max
1 5 6 7 2 7

min
1 8

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 29

 Examples (2/4)
max
7
min
7 2 1

max
7 8 2 7 1 5 6
min

8 1

max
7

min
1
2 7

max
1 5 6 7 2 8 7

min
1 8

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 30

 Examples (3/4)
max

min

max
7 2 7 1 5 6
min

8 1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 31

 Examples (3/4)
max

min

max
7 2 7 1 5 6
min

8 1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 32

 Examples (4/4)
max

min

max
7 2 7 1 5 6
min

8 1

max

min

max
1 5 6 7 2 7

min
1 8

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 33

 Lessons from the previous examples
It looks like for the same tree, different move orderings give
very different cut branches.
It looks like if a node can evaluate a child with the best possible
outcome earlier, then it has a chance to cut earlier.
• For a min node, this means to search the child branch that gives the
lowest value first.
• For a max node, this means to search the child branch that gives the
highest value first.
Comments:
• It is impossible to always know which best branch is; otherwise we do
not have to do a brute-force search.
• Q: In the best case scenario, how many nodes can be cut?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 34

 Analysis of a possible best case
Definitions:
• A path in a search tree is a sequence of numbers indicating the branches
selected in each level using the Dewey decimal system.
• A position is denoted as a path a1.a2. · · · .a` from the root.
• A position a1.a2. · · · .a` is critical if
. ai = 1 for all even values of i or
. ai = 1 for all odd values of i.
• Note: as a special case, the root is critical.
• Examples:
. [Link].2, [Link].1.2, [Link].[Link] and 1.1 are critical
. [Link].2 is not critical
• The number of 1’s in a path has little to do with whether it is critical
or not.
Q: Why does the root need to be critical?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 35

 Perfect-ordering tree
A perfect-ordering tree:

h(a1. · · · .a`) if a1. · · · .a` is a terminal
F (a1. · · · .a`) =
−F (a1. · · · .a`.1) otherwise

• The first successor of every non-terminal position gives the best possible
value.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 36

 Theorem 1
Theorem 1: F 1 examines precisely the critical positions of a
perfect-ordering tree.
Proof sketch:
• Classify the critical positions, a.k.a. nodes, into different types.
. You must evaluate the first branch from the root to the bottom.
. Alpha cut off happens at odd-depth nodes as soon as the first branch
of this node is evaluated.
. Beta cut off happens at even-depth nodes as soon as the first branch of
this node is evaluated.
• For nodes of the same type, associate them with pruning of same
characteristics occurred.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 37

 Types of nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index, if exists, such that aj 6= 1 and ` is the last
index.
• j will be the anchor in the analysis.
• Def: let IS1(ai) be a boolean function so that it is 0 if it is not the
value 1 and it is 1 if it is.
. We call this IS1 parity of a number.
• If j exists and ` > j, then
. aj+1 = 1 because this position is critical and thus the IS1 parities of aj
and aj+1 are different.
• Since this position is critical, if aj 6= 1, then ah = 1 for any h such that
h − j is odd.
We now classify critical nodes into three types.
• Nodes of the same type share some common properties.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 38

 Illustration — critical nodes
1 1 1 1 1 1 1 1 ... ?
* *
j l

1 1 1 :1

1 : not 1

* : any

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 39

 Type 1 nodes
type 1: the root, or a node with all the ai are 1;
• This means j does not exist.
• Nodes on the leftmost branch.
• The leftmost child of a type 1 node except the root.

type 1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 40

 Type 2 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
Type 2: ` − j is zero or even;
• type 2.1: ` − j = 0 which means ` = j.
. It is in the form of 1.1.1. · · · .1.1.1.a` and a` 6= 1.
. The non-leftmost children of a type 1 node.
• type 2.2: ` − j > 0 and is even.
. It is in the form of 1.1. · · · .[Link] .[Link]+2. · · · .a`−2.1.a`.
. Note, we have already defined 1.1. · · · .[Link] .[Link]+2. · · · .a`−2.1 to be a
type 3 node.
. All of the children of a type 3 node.

Q:
• Can a` be 1 or non-1 for a type 2 node?
• Can a` be 1 or non-1 for a type 2.1 node?
• Can a` be 1 or non-1 for a type 2.2 node?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 41

 Type 3 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
Type 3: ` − j is odd;
• aj 6= 1 and ` − j is odd
. Since this position is critical, the IS1 parities of aj and a` are different.
=⇒ a` = 1
=⇒ aj+1 = 1
• It is in the form of
. 1.1. · · · .[Link] .[Link]+2.1. · · · .1.a`−1.1.
• The leftmost child of a type 2 node.
• type 3.1: ` − j = 1.
. It is of the form 1.1. · · · .[Link] .1
. The leftmost child of a type 2.1 node.
• type 3.2: ` − j > 1.
. It is of the form 1.1. · · · .[Link] .[Link]+2.1. · · · .1.a`−1.1
. The leftmost child of a type 2.2 node.

Q: Can a` be 1 or non-1 for a type 3 node?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 42

 Comments
Nodes of the same type have common properties.
These properties can be used in solving other problems.
• Example: Efficient parallelization of alpha-beta based searching algo-
rithms.
Main techniques used:
• You cannot have two consecutive non-1 numbers in the ID of a critical
node.
• For each non-1 number, any number appeared later and is odd distance
away must be 1.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 43

 Type 2.1 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
type 2: ` − j is zero or even;
• type 2.1: ` − j = 0.
. Then ` = j .
. It is in the form of 1.1.1. · · · .1.1.1.a` and a` 6= 1.
. The non-leftmost children of a type 1 node.

type 1

type 2.1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 44

 Type 3.1 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
type 3: ` − j is odd;
• type 3.1: ` − j = 1.
. It is of the form 1.1. · · · .[Link] .1 and a` 6= 1.
. The leftmost child of a type 2.1 node.

type 1

type 2.1

type 3.1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 45

 Type 2.2 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
type 2: ` − j is zero or even;
• type 2.2: ` − j > 0 and is even.
. The IS1 parties of aj and aj+1 are different.
=⇒ Since aj 6= 1, aj+1 = 1.
. (` − 1) − j is odd:
=⇒ The IS1 parties of a`−1 and aj are different.
=⇒ Since aj 6= 1, a`−1 = 1.
. It is in the form of 1.1. · · · .[Link] .[Link]+2. · · · .a`−2.1.a`.
. Note, we will show 1.1. · · · .[Link] .[Link]+2. · · · .a`−2.1 is a type 3 node
later.
. All of the children of a type 3 node.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 46

 Illustration: Type 2.2 nodes
type 1

type 2.1

type 3.1

type 2.2

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 47

 Type 3.2 nodes
Classification of critical positions a1.a2. · · · .aj . · · · .a` where j is
the least index such that aj 6= 1 and ` is the last index.
type 3: ` − j is odd;
• type 3.2: ` − j > 1.
. It is of the form 1.1. · · · .[Link] .[Link]+2.1. · · · .1.a`−1.1
. The leftmost child of a type 2.2 node.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 48

 Illustration: Type 3.2 nodes
type 1

type 2.1

type 3.1

type 2.2

type 3.2

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 49

 Illustration of all nodes
type 1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 50

 Illustration of all nodes
type 1

type 2.1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 51

 Illustration of all nodes
type 1

type 2.1

type 3.1

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 52

 Illustration of all nodes
type 1

type 2.1

type 3.1

type 2.2

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 53

 Illustration of all nodes
type 1

type 2.1

type 3.1

type 2.2

type 3.2

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 54

 Illustration of all nodes
type 1

type 2.1

type 3.1

type 2.2

type 3.2

type 2.2

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 55

 Theorem 1: Proof sketch
Properties (invariants)
• A type 1 position p is examined by calling F 1(p, −∞, ∞, depth)
. p’s first successor p1 is of type 1
. F (p) = −F (p1) 6= ±∞
. p’s other successors p2, . . . , pb are of type 2
. pi, i > 1, are examined by calling F 1(pi, −∞, F (p1), depth)
• A type 2 position p is examined by calling F 1(p, −∞, beta, depth) where
−∞ < beta ≤ F (p)
. p’s first successor p1 is of type 3
. F (p) = −F (p1)
. p’s other successors p2, . . . , pb are not examined
• A type 3 position p is examined by calling F 1(p, alpha, ∞, depth) where
∞ > alpha ≥ F (p)
. p’s successors p1, . . . , pb are of type 2
. they are examined by calling F 1(p1, −∞, −alpha, depth),
F 1(p2, −∞, − max{m1, alpha}, depth), . . . ,
F 1(pi, −∞, − max{mi−1, alpha}, depth)
where mi = F 1(pi, −∞, − max{mi−1, alpha}, depth)
Using an inductive argument to prove.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 56

 Analysis: best case
Corollary 1: Assume each position has exactly b successors
• The number of positions examined by the alpha-beta procedure on
level i is exactly
bdi/2e + bbi/2c − 1.
Proof:
• There are bbi/2c sequences of the form a1. · · · .ai with 1 ≤ ai ≤ b for all
i such that ai = 1 for all odd values of i.
• There are bdi/2e sequences of the form a1. · · · .ai with 1 ≤ ai ≤ b for all
i such that ai = 1 for all even values of i.
• We subtract 1 for the sequence 1.1. · · · .1.1 which are counted twice.
Total number of nodes visited is
`
X
bdi/2e + bbi/2c − 1.
i=0

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 57

 Analysis: average case
Assumptions: Let a random game tree be generated in such a
way that each position on level j has
• a probability qj of being nonterminal and
• an average of bj successors.
Properties of the above random game tree
• Expected number of positions on level ` is b0 × b1 × · · · × b`−1
• Expected number of positions on level ` examined by an alpha-beta
procedure assumed the random game tree is perfectly ordered is

b0q1b2q3 · · · b`−2q`−1 + q0b1q2b3 · · · q`−2b`−1 − q0q1 · · · q`−1if ` is even;

b0q1b2q3 · · · q`−2b`−1 + q0b1q2b3 · · · b`−2q`−1 − q0q1 · · · q`−1if ` is odd

Proof sketch:
• If x is the expected number of positions of a certain type on level j,
then x × bj is the expected number of successors of these positions,
and x × qj is the expected number of “numbered 1” successors.
• The above numbers equal to those of Corollary 1 when qj = 1 and
bj = b for 0 ≤ j < `.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 58

 Perfect ordering is not always the best
Intuitively, we may “think” alpha-beta pruning would be most
effective when a game tree is perfectly ordered.
• That is, when the first successor of every position is the best possible
move.
• This is not always the case!

>=4 >=4

<=3
<=2 4

2 3 3

2 1
2 1

Truly optimum order of game trees traversal is not obvious.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 59

 When is a branch pruned?
Assume a node r has two children u and v with u being visited
before v using some move ordering.
• Further assume u produced a new bound bound.
Assume node v has a child w.
• If the value new returned from w can cause a range conflict with bound,
then branches of v later than w are cut.
This means as long as the “relative” ordering of u and v are
good enough, then we can have some cut-off.
• There is no need for r to have the best move ordering.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 60

 Theorem 2
Theorem 2: Alpha-beta pruning is optimum in the following
sense:
• Given any game tree and any algorithm which computes the value of
the root position, there is a way to permute the tree
. by reordering successor positions if necessary;
• so that every terminal position examined by the alpha-beta method
under this permutation is examined by the given algorithm.
• Furthermore if the value of the root is not ∞ or −∞, the alpha-beta
procedure examines precisely the positions which are critical under this
permutation.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 61

 Variations of alpha-beta search
Initially, to search a tree with the root r by calling
F 1(r,−∞,+∞,depth).
• What does it mean to search a tree with the root r by calling
F 1(r,alpha,beta,depth)?
. To search the tree rooted at r requiring that the returned value to be
within alpha and beta.

In an alpha-beta search with a pre-assigned window [alpha, beta]:

• Failed-high means it returns a value that is larger than or equal to its
upper bound beta.
• Failed-low means it returns a value that is smaller than or equal to its
lower bound alpha.
Variations:
• Brute force Nega-Max version: F
. Always finds the correct answer according to the Nega-Max formula.
• Original alpha-beta cut (Nega-Max) version: F 1
• Fail hard alpha-beta cut (Nega-Max) version: F 2
• Fail soft alpha-beta cut (Nega-Max) version: F 3

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 62

 Original version
Requiring alpha ≤ beta
Algorithm F 1(position p, value alpha, value beta, integer depth)
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
• then return h(p) else
• begin
. m := alpha // hard initial value
. for i := 1 to b do
. begin
. t := −F 1(pi, −beta, −m, depth − 1)
. if t > m then m := t // the returned value is “used”
. if m ≥ beta then return(beta) // cut off and return the hard bound
. end
• end
• return m // if nothing over alpha, then alpha is returned

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 63

 Properties and comments
Properties:
• Assumptions: (1) alpha < beta and (2) p is not a leaf.
• F 1(p, alpha, beta, depth) = alpha if F (p) ≤ alpha
• F 1(p, alpha, beta, depth) = F (p) if alpha < F (p) < beta
• F 1(p, alpha, beta, depth) = beta if F (p) ≥ beta
• F 1(p, −∞, +∞, depth) = F (p)
Comments:
• F 1(p, alpha, beta, depth): find the best possible value according to a
nega-max formula for the position p with the constraints that
. If F (p) ≤ alpha, then F 1(p, alpha, beta, depth) returns with the value
alpha from a terminal position whose value is ≤ alpha.
. If F (p) ≥ beta, then F 1(p, alpha, beta, depth) returns the value beta
from a terminal position whose value is ≥ beta.
• The meanings of alpha and beta during searching:
. For a max node: the current best value is at least alpha.
. For a min node: the current best value is at most beta.
• F 1 always finds a value that is within alpha and beta.
. The bounds are hard, i.e., cannot be violated.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 64

 Original version: Example

bound return max{ 4000 ,200,v}

[4000,5000]

A
F1(W,−5000,−4000,d) return(−v)

return(−200)
W Q
F1(Q,−5000,−4000,d) −v
−200

As long as the value of the leaf node W is less than the current
alpha value, the returned value of A will be alpha.
If the value of the leaf node W is greater than the current beta
value, the returned value of A will be beta.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 65

 Alpha-beta pruning algorithm: Fail hard
Algorithm F 20(position p, value alpha, value beta) // max node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := alpha
. for i := 1 to b do
. t := G20(pi, m, beta)
. if t > m then m := t
. if m ≥ beta then return(m) // beta cut off, return m
• end; return m
0
Algorithm G2 (position p, value alpha, value beta) // min node
• determine the successor positions p1, . . . , pb
• if b = 0, then return f (p) else begin
. m := beta
. for i := 1 to b do
. t := F 20(pi, alpha, m)
. if t < m then m := t
. if m ≤ alpha then return(m) // alpha cut off, return m
• end; return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 66

 Alpha-beta pruning algorithm: Fail hard
Algorithm F 2(position p, value alpha, value beta, integer depth)
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
• then return h(p) else
• begin
. m := alpha
. for i := 1 to b do
. begin
. t := −F 2(pi, −beta, −m, depth − 1)
. if t > m then m := t
. if m ≥ beta then return(m) // cut off, return m that is ≥ beta
. end
• end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 67

 Properties and comments
Properties:
• Assumptions: (1) alpha < beta and (2) p is not a leaf.
• F 2(p, alpha, beta) = alpha if F (p) ≤ alpha
• F 2(p, alpha, beta) = F (p) if alpha < F (p) < beta
• F 2(p, alpha, beta) ≥ beta and F (p) ≥ F 2(p, alpha, beta) if F (p) ≥ beta
• F 2(p, −∞, +∞) = F (p)
Comments:
• F 2(p, alpha, beta): find the best possible value according to a nega-max
formula for the position p with the constraints that
. If F (p) ≤ alpha, then F 2(p, alpha, beta) returns with the value alpha
from a terminal position whose value is ≤ alpha.
. If F (p) ≥ beta, then F 2(p, alpha, beta) returns a value ≥ beta from a
terminal position whose value is ≥ beta.
• An intermediate version.
. The lower bound is hard, cannot be violated.
. Easier to find the branch where the returned value is coming from.
. Always return something better than expected, but never something
worse!!
• For historical reason [Fishburn 1983][Knuth & Moore 1975], this is
called fail hard.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 68

 Example
Initial call: F 20(root,−∞,∞)
• m = −∞

• call G20(node 1,−∞,∞)

. it is a terminal node
. return value 15

• t = 15; V>=15
. since t > m, m is now 15
1 2
V <= 10
V=15
0
• call G2 (node 2,15,∞) 2.1 2.2 cut
. call F 20(node 2.1,15,∞) V=10

. it is a terminal node; return 10

. t = 10; since t < ∞, m is now 10
. alpha is 15, m is 10, so we have
an alpha cut off,
. no need to call
F 20(node 2.2,15,10)
. return 10
. ···

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 69

 Fail soft version
Algorithm F 3(position p, value alpha, value beta, integer depth)
• determine the successor positions p1, . . . , pb
• if b = 0 // a terminal node
or depth = 0 // remaining depth to search
or time is running up // from timing control
or some other constraints are met // add knowledge here
• then return h(p) else
• begin
. m := −∞ // soft initial value
. for i := 1 to b do
. begin
. t := −F 3(pi, −beta, − max{m, alpha}, depth − 1)
. if t > m then m := t // the returned value is “used”
. if m ≥ beta then return(m) // cut off
. end
• end
• return m

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 70

 Properties and comments
Properties:
• Assumptions (1) alpha < beta and (2) p is not a leaf
• F 3(p, alpha, beta, depth) ≤ alpha and F (p) ≤ F 3(p, alpha, beta, depth) if
F (p) ≤ alpha
• F 3(p, alpha, beta, depth) = F (p) if alpha < F (p) < beta
• F 3(p, alpha, beta, depth) ≥ beta and F (p) ≥ F 3(p, alpha, beta, depth) if
F (p) ≥ beta
• F 3(p, −∞, +∞, depth) = F (p)
F 3 finds a “better” value when the value is out of the search
window.
• Better means a tighter bound.
. The bounds are soft, i.e., can be violated.
• When it is failed-high, F 3 normally returns a value that is higher than
that of F 1 or F 2.
. Never higher than that of F !
• When it is failed-low, F 3 normally returns a value that is lower than
that of F 1 or F 2.
. Never lower than that of F !

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 71

 Fail soft version: Example

bound return max{200,v}

[4000,5000]

A
F3(W,−5000,−4000,d) return(−v)

return(−200)
W Q
F3(Q,−5000,−4000,d)
−v
−200

Let the value of the leaf node W be u.

If u < alpha, then the returned value of A will be at least u.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 72

 Comparisons between F 2 and F 3
Both versions find the corrected value v if v is within the
window [alpha, beta].
Both versions scan the same set of nodes during searching.
. If the returned value of a subtree is decided by a cut, then F 2 and F 3 return
the same value.

F 3 provides more information when the true value is out of the

pre-assigned search window.
• Can provide a feeling on how bad or good the game tree is.
• Use this “better” value to guide searching later on.
F 3 saves about 7% of time than that of F 2 when a transposition
table is used to save and re-use searched results [Fishburn
1983].
• A transposition table is a data structure to record the results of previous
searched results.
• The entries of a transposition table can be efficiently accessed, i.e.,
read and write, during searching.
• Need an efficient addressing scheme, e.g., hash, to translate between
a position and its address.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 73

 F 2 and F 3: Example (1/2)
P1 P2
bound
bound [390,600]
[4000,5000]

W
Q
−200

Assume the node A can be reached from the starting position

using path P1 and path P2.
• If W is visited first along P1 with a bound of [4000, 5000], and returns
a value of 200, then
. the returned value of W , 200, is stored into the transposition table.
• If A is visited again along P2 with a bound of [390, 600], then a better
value of previously stored value of W helps to decide whether the
subtree rooted at W needs to be searched again.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 74

 F 2 and F 3: Example (2/2)
P1 P2
bound
bound [390,600]
[4000,5000]

W
Q
−200

Fail soft version has a chance to record a better value to be

used later when this position is revisited.
• If A is visited again along P2 with a bound of [390, 600], then
. it does not need to be searched again, since the previous stored value
of W is −200.
• However, if the value of W is 450, then it needs to be searched again.
The fail hard version does not store the returned value of W
after its first visit since this value is less than alpha.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 75

 Comments
For historical reason, comparisons are made between F 2 and
F 3, while we should compare F 1 and F 3.
• To me, F 1 fails really hard. F 2 is only an intermediate version!
What move ordering is good?
• It may not be good to search the best possible move first.
• It may be better to cut off a branch with more nodes first.
How about the case when the tree is not uniform?
What is the effect of using iterative-deepening alpha-beta cut
off?
How about the case for searching a game graph instead of a
game tree?
• Can some nodes be visited more than once?

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 76

 References and further readings
* D. E. Knuth and R. W. Moore. An analysis of alpha-beta
pruning. Artificial Intelligence, 6:293–326, 1975.
* John P. Fishburn. Another optimization of alpha-beta search.
SIGART Bull., (84):37–38, 1983.
J. Pearl. The solution for the branching factor of the alpha-beta
pruning algorithm and its optimality. Communications of
ACM, 25(8):559–564, 1982.

TCG: α-β Pruning, 20191107, Tsan-sheng Hsu c 77