Teaching Kids Programming – Alpha-Beta Pruning Algorithm (Game Theory)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the following Two MinMax Game Trees:

alpha-beta-pruning-example

We can discard the subtree x as we know the result doesn’t matter.

For example, the left minmax tree. The node value of ? is less or equal to 6, which is worse than 5, thus there is no need to explore the subtree x since it won’t change the root node (min).

And the right minmax tree, the node value of ? is at least 4, which is worse than 5, thus there is no need to search the x subtree because it won’t impact the overall result of the root value (max) which is 5.

These two situations (Alpha and Beta), we can cut off (prune) the subtree to accelerate the searching. We can add the pruning on the basis of MinMax Algorithms with two extra paramters alpha and beta namely and to define the boundary/range.

When the value (current score of the game node) falls outside the valid range [alpha, beta] we can terminate the loop (cut-off, branches pruning).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def alphabeta(self, depth, maximizing, state, alpha, beta):
    player, s = state
    t = self.check(s)
    if t != None:
        return player * math.inf
 
    bestAction = None
    actions = self.actions(state)
    if maximizing:
        score = -math.inf
        for action in actions:
            newState = self.succ(state, action)
            _, curScore = self.alphabeta(depth + 1, False, newState, alpha, beta)
            if curScore > score:
                score = curScore
                bestAction = action
            if curScore >= beta:
                break  # β cutoff
            alpha = max(alpha, curScore)   
        return bestAction, score
    else:
        score = math.inf
        for action in actions:
            newState = self.succ(state, action)
            _, curScore = self.alphabeta(depth + 1, True, newState, alpha, beta)
            if curScore < score:
                score = curScore
                bestAction = action
            if curScore <= alpha:
                break  # α cutoff
            beta = min(beta, curScore)
        return bestAction, score

def alphabeta(self, depth, maximizing, state, alpha, beta):
	player, s = state
	t = self.check(s)
	if t != None:
		return player * math.inf

	bestAction = None
	actions = self.actions(state)
	if maximizing:
		score = -math.inf
		for action in actions:
			newState = self.succ(state, action)
			_, curScore = self.alphabeta(depth + 1, False, newState, alpha, beta)
			if curScore > score:
				score = curScore
				bestAction = action
			if curScore >= beta:
				break  # β cutoff
			alpha = max(alpha, curScore)   
		return bestAction, score
	else:
		score = math.inf
		for action in actions:
			newState = self.succ(state, action)
			_, curScore = self.alphabeta(depth + 1, True, newState, alpha, beta)
			if curScore < score:
				score = curScore
				bestAction = action
			if curScore <= alpha:
				break  # α cutoff
			beta = min(beta, curScore)
		return bestAction, score

Alpha-beta pruning algorithm is a simple optimisation technique to shorten the runtime of a minmax algorithm as the search space often are too huge. With branches pruning, we don’t spend/waste time on exploring subtrees that don’t matter.

Game Theory – Game Algorithms

• Teaching Kids Programming – Alpha Beta Pruning Algorithm on NegaMax (Game Theory)
• Teaching Kids Programming – NegaMax Algorithm (Game Theory)
• Teaching Kids Programming – Alpha-Beta Pruning Algorithm (Game Theory)
• Teaching Kids Programming – Define Tic Tac Toe using Game Theory Terminologies
• Teaching Kids Programming – Introduction to Two Players Zero-Sum Game (Number Halving)
• Teaching Kids Programming – MinMax Algorithm in Game Tree (Game Theory, Tic Tac Toe)

–EOF (The Ultimate Computing & Technology Blog) —