CODEWITHSUNDEEP
artificial-intelligenceminimaxalpha-beta-pruning
ido kahana
ido kahana

Reputation: 165

Is it possible to apply alpha-beta pruning for non0zero sum games with 2 players?

I understand why it is possible for zero-sum game, but I cannot understand whether it is possible for non-zero sum games with 2 players. Is it because both players do not necessarily have a conflict in their interests?

Upvotes: 0

Views: 354

Answers (1)

Nathan S.
Nathan S.

Reputation: 5388

If the scores for two players are completely arbitrary, then you can't do any pruning. Suppose that the scores were {-10, 10} for P1 and P2 on one branch. P1 might be tempted to prune this branch because, perhaps, at the root P1 could get >= 5. But, perhaps the second branch is {100, 100} which would be a much better outcome. In general there is no guarantee that we won't find another branch with an arbitrarily large score for both players, so we can never prune.

If you make stronger assumptions, more can be done.

For instance, look at the M* algorithm which handles opponent models. There they handled the cases of bounded sum. An extended tech report is available online.

This is related to multi-player (meaning >=3) constant-sum games, which can use a different set of pruning techniques.

Upvotes: 1

Related Questions