How would the min max algorithm of a chess engine work in the case of 3 player chess?

Question

I understand that for 2 player chess if an engine is playing white, then the engine uses a min max algorithm, which assumes that black will always make the move that is best for black, or worst for white, and that white will always make moves that are best for white.

While in 2 player, with black to play, the move that is best for black is always the one that is worst for white, but in 3 player chess this is not always the case. As an example, let's say that there is a white rook that is undefended by any white pieces or pawns, but which is attacked by both the black queen and the red queen. Capturing the rook would not be the best move for black, and if black does take the rook the best move for red would be to take the black queen. However what would be worst for white would be if black took the white rook and red did not take the black queen as then white would just be down a rook, compared to both opponents, without compensation.

So my question is would a 3 player chess engine use a min max that assumes that the other two opponents make moves that are best for their individual positions, or would it use an algorithm that assumes that both players would make moves that are worst for the engines position regardless of how that affects their individual positions?

Answer 1

The problem is really not in chess, but in any naive 3-player version of any 2-player strategy game. In general, it is hard to make an interesting 3-player game where each player's performance is almost solely a matter of skill regardless of whether the other players cooperate.

Indeed, before you can even ask how to compute the best strategy, you would have to define what it means. That is, you must define precisely what each player's outcome is and what each player's objective is, in such a way that it 'feels fair enough'.

In the case of deterministic strategy games, you might define the optimal strategy for each player as the strategy that maximizes his/her worst possible outcome against all other players regardless of whether the other players cooperate, and you might call that outcome the minimum ensured outcome.

Unlike 2-player games, even if all the players' outcomes sum to zero, it is often the case that the sum of their minimum ensured outcomes is not zero. Unfortunately, there is no generic way to convert a 2-player game into a 3-player game with zero total minimum ensured outcome that retains the flavour of the original game. And that is the biggest problem you need to solve. Once you solve that, you can compute the optimal strategy using the same trivial recursion as for 2-player games. (By the way, minimax is not the right way to understand chess engines at all; learn negamax instead.)

Answer 2

I tried it once, chess with black, white and red pieces. We played for a while and left scratching our heads.

The problem is alliances. If A is in a stronger position than both B and C, these two will cooperate to weaken A. Just both exchanging pieces with A will weaken A, A will lose two pieces, B and C only one each.

C could be in the weakest position and not care about what A and B do. But if B is runner up then he can exchange pieces with A until C is not the weakest anymore, and then C sees his chance of winning, and B and C beat up A.

And there’s the possibility that A just dislikes B personally. In normal chess that is mostly irrelevant. In 3-player chance it makes a huge difference.

Answer 3

This really opens a can of worms. E.g. it could be that there is a forced win for either A or B, depending on what C does. But why would C still care what he does? He will randomly decide whether A or B wins. So even though the game is fully deterministic, you get some aspects of stochastic games in it. (Which requires 'expectomax' rather than minimax.) It also depends on whether it is a 'winner takes all' game, or whether there is some reward finishing second. In general the burden of engaging the player with strongest position is on the runner-up. It also depends on the nature of the game: does engaging someone weaken or strengthen you. In a game like chess your army erodes away. In a game like shogi/crazyhouse not necessarily. And would 'ganging up' on a player help? E.g. with fixed turn order in chess it would, as A and B could both capture a protected piece of C, but C could only recapture one. If the rules are such that after a capture the turn would go to the attacked player, attacking with 2 would not be any better than attacking with 1 army.

Opponent modelling will also be more important. You can see what is best for one of the opponents to do, but will he be able to see that as well, or would he do a sub-optimal (for him) move that happens to hurt you, rather than the third player, just because he was not smart enough?

Answer 4

Q: Would a 3 player chess engine use a min max that assumes that the other two opponents make moves that are best for their individual positions?

A: The Max^n algorithm, which is an attempt at strategy optimisation in n-player games, establishes outcome vectors rather than outcome values, and choses moves based on optimised such vectors; but indeed, it does so following your logic of assuming best play of the other players.

See: Luckhardt, Irani, An algorithmic solution to n-person games

Q: Would it use an algorithm that assumes that both players would make moves that are worst for the engines position regardless of how that affects their individual positions?

A: No. The sort of strategy optimising needed is based on the assumtion of strictly rational, read: selfish and non-colluding players. A sensible approach wants the respective other entities to follow a max-strategy, maximising their payoffs. The idea of others colluding may well be part of the (sub)tree, but primate must be given to the max-vector if you want the algo to rely on

Theorem: A finite n-person non-cooperative game with perfect information possesses am equilibrium point in pure strategies.

See: Jones, A.J. (1980), Game theory: Mathematical Models of Conflict.

Lastly, to quote @Prof.Chaos from StackOverflow:

Note that MiniMax, and thus Max^n is never used in practice due to the exponential increase of the search space, i.e., game tree. Instead, one always uses Alpha/Beta pruning, which is a rather intuitive extension to never visit/explore branches of the tree that would be pointless to search anyway. Alpha/Beta was also extended to work for n-player games (n>2) as well, described by Richard Korf in "Multi-player alpha-beta pruning" in Artificial Intelligence 48 (1991), p.99-111. The article is publicly available at: https://www.cc.gatech.edu/~thad/6601-gradAI-fall2015/Korf_Multi-player-Alpha-beta-Pruning.pdf

In this paper, you'll read about shallow pruning being an option to save on computational efforts. Hope this guides you further.