Teaching Kids Programming – NegaMax Algorithm (Game Theory)


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a MinMax implementation, one problem is that there are two situations that we need to handle separately: maximizing and minimizing. We can implement both scenarios in a same recursive function, or two separate function where max calls the min and min calls the max.

The NegaMax is a simplified implementation of the MinMax, based on the following observation:

tex_5dec7295c0dfd1369f905c8c4df7aede Teaching Kids Programming - NegaMax Algorithm (Game Theory) algorithms games python teaching kids programming youtube video

Thus, we can set to always find maximum value in the NegaMax algorithm but we have to negate the sign when passing to next round.

1
2
3
4
5
6
7
def negamax(self, state, depth, player):
    if depth == 0 or self.isEnd(state):
        return evalState(state)
    score = -math.inf
    for act in self.actions(state):
        score = max(score, self.negamax(self.succ(state, act), depth - 1, -player)
    return score
def negamax(self, state, depth, player):
    if depth == 0 or self.isEnd(state):
        return evalState(state)
    score = -math.inf
    for act in self.actions(state):
        score = max(score, self.negamax(self.succ(state, act), depth - 1, -player)
    return score

The negamax simplifies the implementation of minmax by combining two scenarios. Both players can be treated as finding the maximal value of the nodes – as we negate the value into next recursive call. The above is the Negamax Base Algorithm which can be used to implement the Alpha Beta Pruning.

Game Theory – Game Algorithms

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
528 words
Last Post: Teaching Kids Programming - Alpha-Beta Pruning Algorithm (Game Theory)
Next Post: Teaching Kids Programming - Alpha Beta Pruning Algorithm on NegaMax (Game Theory)

The Permanent URL is: Teaching Kids Programming – NegaMax Algorithm (Game Theory)

Leave a Reply