Answers.Body: <p>Here is one of many web pages devoted to the application of Minimax in Tic-Tac-Toe solving: <a href="http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/" rel="nofollow noreferrer">Minimax Algorithm in Game Theory | Set 3 (Tic-Tac-Toe AI – Finding optimal move)</a>  </p>
  
  <p>Google search will yield many such results. <em>(I will return to this answer when I have more time, and post more links with more context.)</em> </p>
  
  <p>Here's a high-level explanation on how minimax may be used in the non-chance, perfect information, sequential, partisan, zero-sum set of games <a href="http://www.fundamentalcombinatronics.com/rules-of-m/" rel="nofollow noreferrer">[M]</a>:</p>
  
  <ul>
  <li>A non minimax evaluation function would look to place integers on the gameboard in positions that grant maximum value (power &amp; influence)</li>
  <li>A minimax evaluation function would look to place integers on the gameboard in positions that maximize value while minimizing the max value of the opponents next placement</li>
  </ul>
  
  <p>This is partly due to the utilization of "resource stealing strategies" in [M] games. </p>
  
  <hr>
  
  <p>Note: I need to do some more thinking on the sub questions regarding application beyond zero-sum, perfect-information games, but I don't see any issue with it.   Minimax/maximin has wide and fundamental utility in an array of contexts, not strictly related to games except in the sense that every problem can be understood as a type of game or puzzle.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-13T21:44:17.673Z
Answers.LastActivityDate: 2017-09-13T21:44:17.673Z
Answers.UserDisplayName: DukeZhou
Body: <p>The Von Neumann's <a href="https://en.wikipedia.org/wiki/Minimax_theorem" rel="nofollow noreferrer">Minimax theorem</a> gives the conditions that make the <a href="https://en.wikipedia.org/wiki/Max%E2%80%93min_inequality" rel="nofollow noreferrer">max-min inequality</a> an equality.</p>
  <p>I understand the max-min inequality, basically <code>min(max(f))&gt;=max(min(f))</code>.</p>
  <p>The Von Neumann's theorem states that, for the inequality to become an equality <code>f(.,y)</code> should always be convex for given y and <code>f(x,.)</code> should always be concave for given x, which also makes sense.</p>
  <p><a href="https://www.youtube.com/watch?v=m-EewaiFhF0&amp;list=PLAwxTw4SYaPnidDwo9e2c7ixIsu_pdSNp&amp;index=61" rel="nofollow noreferrer">This video</a> says that for a zero-sum perfect information game, the Von Neumann's theorem always holds, so that minimax always equal to maximin, which I did not quite follow.</p>
  <p><strong>Questions</strong></p>
  <ul>
  <li><p>Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?</p>
  </li>
  <li><p>If we relax the rules to be non-zero-sum or non-perfect information, how would the conditions change?</p>
  </li>
  </ul>
  
Tags: <game-theory><search><minimax>
Title: Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?
UserDisplayName: dontloo
ThreadText: # Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?
  
  (Asked by: username_0 on 2016-08-07)
  
  The Von Neumann's [Minimax theorem](https://en.wikipedia.org/wiki/Minimax_theorem) gives the conditions that make the [max-min inequality](https://en.wikipedia.org/wiki/Max%E2%80%93min_inequality) an equality.
  
  I understand the max-min inequality, basically `min(max(f))>=max(min(f))`.
  
  The Von Neumann's theorem states that, for the inequality to become an equality `f(.,y)` should always be convex for given y and `f(x,.)` should always be concave for given x, which also makes sense.
  
  [This video](https://www.youtube.com/watch?v=m-EewaiFhF0&list=PLAwxTw4SYaPnidDwo9e2c7ixIsu_pdSNp&index=61) says that for a zero-sum perfect information game, the Von Neumann's theorem always holds, so that minimax always equal to maximin, which I did not quite follow.
  
  **Questions**
  
  * Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?
  * If we relax the rules to be non-zero-sum or non-perfect information, how would the conditions change?
  
  **Tags:** game-theory, search, minimax
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-09-13. Score: 1
  
  Here is one of many web pages devoted to the application of Minimax in Tic-Tac-Toe solving: [Minimax Algorithm in Game Theory | Set 3 (Tic-Tac-Toe AI – Finding optimal move)](http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/)
  
  Google search will yield many such results. *(I will return to this answer when I have more time, and post more links with more context.)*
  
  Here's a high-level explanation on how minimax may be used in the non-chance, perfect information, sequential, partisan, zero-sum set of games [[M]](http://www.fundamentalcombinatronics.com/rules-of-m/):
  
  * A non minimax evaluation function would look to place integers on the gameboard in positions that grant maximum value (power & influence)
  * A minimax evaluation function would look to place integers on the gameboard in positions that maximize value while minimizing the max value of the opponents next placement
  
  This is partly due to the utilization of "resource stealing strategies" in [M] games.
  
  ---
  
  Note: I need to do some more thinking on the sub questions regarding application beyond zero-sum, perfect-information games, but I don't see any issue with it. Minimax/maximin has wide and fundamental utility in an array of contexts, not strictly related to games except in the sense that every problem can be understood as a type of game or puzzle.
  
  
  ---
  
  