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

Teaching Kids Programming: Videos on Data Structures and Algorithms

The Alpha Beta Pruning Optimisation Algorithm can also be applied directly on NegaMax – so that we can combine both players/scenarios instead of writing similar code twice.

The alpha, beta boundary when negated becomes (-beta, -alpha) – that is turns to

The following is a Python code to implement the Alpha Beta Pruning Algorithm based on Negamax – with the Depth Limit Search aka the depth parameter is the max depth to search.

def alphabeta(state, depth, player, alpha, beta):
    if d == 0 or isEnd(state):
        return score(state)

    score = -math.inf
    for act in actions(state):
        newState = succ(state, act)
        score = max(score, -alphabeta(newState, depth - 1, -player, -beta, -alpha)
        alpha = max(alpha, score)
        if alpha >= beta:
            break
    return score

To have a higher chance of Alpha Beta pruning, we can order/sort the moves aka action from good moves to bad moves.

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) —