Is it possible to use alpha-beta pruning for non-zero-sum games with more than two players?

Question

I have read somewhere that the minimax algorithm can be generalized for more than two players. Imagine that we have 3 players that each of them want to maximize its own answer. Is it possible to use alpha-beta pruning in this case? or it is useless? why?

Note: Games are non-zero-sum.

Answer 1

Yes, but you have to be clear on the game mechanics. Your given tree shows the blue moves first, then green, and red has final choice.

There are two approaches here, depending on the game mechanics. If the sole purpose for each player is to maximize their own result, then you need to solve each level for the active player, considering only the associated reward.

In the given example, assuming the the rewards are listed in the order (blue, green, red), then red's four choices among the pairs (2-4),(9-4),(0-6),(0-2) will be R,L,R,R; presenting green with values (8-5),(9-3). From these, green will choose L,L; blue gets the choice (6-8) and will make the R choice, settling on (8, 9, 6) for the game value.

---

However, if there are any other motives for the players, such as maximizing the overall gain (which we happened to achieve above) or giving value to the net differences, then you'll need to use a somewhat more complex decision algorithm; the same logic applies.

With a sufficiently complex game, one in which the players are antagonistic, and moves are made in secret and simultaneously, you may have to switch to the "one-versus-all" model, in which each player assumes that the others will make the choices that minimize the choosing player's reward. This worst-case planning takes you back to a simple minimax process, in which the two opponents are combined into one player, pretending that the game is actually a zero-sum problem.