Describe how the minimax and alpha–beta algorithms change for two-player, nonzero-sum games in which each player has a distinct utility function and both utility functions are known to both players.

Minimax will work as usual if it’s set up right. We’ll be backing up a vector of evaluations and at each level the player will choose what is best for him, even if it is also good for the other player. Thus if we assign increasingly positive values for states increasingly better for Max and increasingly negative values for states increasingly better for Min, then minimax will work unmodified. If both players have increasingly positive values, each player just picks the maximum value, so it’s a “maximax” algorithm.

Alpha-beta algorithm

However, alpha-beta pruning will not work because built into it is the idea that what’s good for max is bad for min – for example min won’t let max go down a path since min can force something worse, so max knowing this doesn’t have to explore that path. But without zero-sum assumption, the same state could be good for both min and max; you can’t assume that just because max likes it that min won’t, and vice versa.