Answers.Body: <p>The problem is really not in chess, but in <em>any naive 3-player version</em> 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 <em>regardless of whether the other players cooperate</em>.</p>
  <p>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 <strong>precisely</strong> what each player's <strong>outcome</strong> is and what each player's <strong>objective</strong> is, in such a way that it 'feels fair enough'.</p>
  <p>In the case of deterministic strategy games, you might define the <strong>optimal strategy</strong> 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 <strong>minimum ensured outcome</strong>.</p>
  <p>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 <strong>not zero</strong>. 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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-03T14:15:19.450Z
Answers.Text: Texas hold'em poker is good example to see the effects of moving from a 2-player game to a 3- or more player game. For 2 players one can apply a lot of game theory for optimal strategies and such. Most of that doesn't work anymore for 3 players if 2 of them are allowed to cooperate.
Answers.UserDisplayName: quarague
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-02T18:30:33.153Z
Answers.LastActivityDate: 2022-07-02T18:30:33.153Z
Answers.UserDisplayName: user21820
Answers.Body: <p>I tried it once, chess with black, white and red pieces. We played for a while and left scratching our heads.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-02T15:30:40.017Z
Answers.LastActivityDate: 2022-07-02T15:30:40.017Z
Answers.UserDisplayName: gnasher729
Answers.Body: <p>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.</p>
  <p>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?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-02T11:57:12.367Z
Answers.LastActivityDate: 2022-07-02T11:57:12.367Z
Answers.UserDisplayName: H.G.Muller
Answers.Body: <p>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?</p>
  <p>A: The <code>Max^n</code> algorithm, which is an attempt at strategy optimisation in n-player games, establishes <em>outcome vectors</em> rather than <em>outcome values</em>, and choses moves based on optimised such vectors; but indeed, it does so following your logic of assuming <strong>best play</strong> of the other players.</p>
  <p>See: <a href="https://www.aaai.org/Papers/AAAI/1986/AAAI86-025.pdf" rel="nofollow noreferrer">Luckhardt, Irani, An algorithmic solution to n-person games</a></p>
  <p>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?</p>
  <p>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 <em>other</em> entities to follow a max-strategy, maximising their payoffs. The idea of <em>others</em> 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</p>
  <p>Theorem: A finite n-person non-cooperative game with perfect information possesses am equilibrium point in pure strategies.</p>
  <p>See: Jones, A.J. (1980), Game theory: Mathematical Models of Conflict.</p>
  <p>Lastly, to quote @Prof.Chaos from StackOverflow:</p>
  <blockquote>
  <p>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&gt;2) as well, described by Richard Korf in &quot;Multi-player alpha-beta pruning&quot; in Artificial Intelligence 48 (1991), p.99-111. The article is publicly available at: <a href="https://www.cc.gatech.edu/%7Ethad/6601-gradAI-fall2015/Korf_Multi-player-Alpha-beta-Pruning.pdf" rel="nofollow noreferrer">https://www.cc.gatech.edu/~thad/6601-gradAI-fall2015/Korf_Multi-player-Alpha-beta-Pruning.pdf</a></p>
  </blockquote>
  <p>In this paper, you'll read about <em>shallow pruning</em> being an option to save on computational efforts. Hope this guides you further.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-02T19:16:20.600Z
Answers.LastActivityDate: 2022-07-02T19:16:20.600Z
Answers.UserDisplayName: Peter Fischer
Body: <p>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.</p>
  <p>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.</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-03T23:13:55.757Z
Comments.Text: So, what is the winning condition of your three player game? Do you win if you checkmate either opponent? Or do both players need to be eliminated?
Comments.UserDisplayName: Abigail
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-04T00:28:37.127Z
Comments.Text: @Abigail it varies from variant to variant.  In some variants you win if you checkmate either opponent and in some both players have to be eliminated.  In some of the variants if a checkmate happens both of the players that didn't checkmate lose while in others the one to neither checkmate nor get checkmated neither wins nor loses.
Comments.UserDisplayName: Anders Gustafson
Tags: <engines><analysis><chess-variants><programming><evaluation>
Title: How would the min max algorithm of a chess engine work in the case of 3 player chess?
ThreadText: # How would the min max algorithm of a chess engine work in the case of 3 player chess?
  
  (Asked by: username_0 on 2022-07-02)
  
  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?
  
  **Tags:** engines, analysis, chess-variants, programming, evaluation
  
  > **Comments:**
  > **username_1**: So, what is the winning condition of your three player game? Do you win if you checkmate either opponent? Or do both players need to be eliminated?  
  > **username_0**: @username_1 it varies from variant to variant.  In some variants you win if you checkmate either opponent and in some both players have to be eliminated.  In some of the variants if a checkmate happens both of the players that didn't checkmate lose while in others the one to neither checkmate nor get checkmated neither wins nor loses.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_2 on 2022-07-02. Score: 15
  
  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.)
  
  > **Comments:**
  > **username_3**: Texas hold'em poker is good example to see the effects of moving from a 2-player game to a 3- or more player game. For 2 players one can apply a lot of game theory for optimal strategies and such. Most of that doesn't work anymore for 3 players if 2 of them are allowed to cooperate.  
  
  ---
  
  ### Answer by username_4 on 2022-07-02. Score: 8
  
  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 by username_5 on 2022-07-02. Score: 2
  
  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 by username_6 on 2022-07-02. Score: 2
  
  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](https://www.aaai.org/Papers/AAAI/1986/AAAI86-025.pdf)
  
  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](https://www.cc.gatech.edu/%7Ethad/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.
  
  
  ---
  
  