Answers.Body: <p>You can take any two player zero-sum game and change its rules, so that they become:</p>
  <ul>
  <li>Start from the game state being evaluated.</li>
  <li>Play for up to N turns.</li>
  <li>If no winner is found after N turns, the winner is the one with the highest heuristic score (calculated in the same way as your minimax algorithm).</li>
  </ul>
  <p>This is still a valid game, based on the original. A minimax using the same non-terminal heuristic will solve that derived/limited game optimally.</p>
  <p>The solution may be unrelated to solutions to the original game. As a worst case, choose as your heuristic a random oracle (that assigns a random number to each state, in practice this could be done using a cryptographic hashing function). In the extreme case of N=1, then a random oracle heuristic will perform - on the original game - much the same as a random player, until either player is 1 turn away from winning. As N increases to include more possible game ends, the effect of the poor heuristic is reduced, as forced wins/losses are discovered (and usually those parts of the search tree removed because one of the players would reject them).</p>
  <p>If you have a perfect heuristic, then the game is solved, and searching with N=1 against that heuristic will result in optimal play for the original game. <a href="https://xkcd.com/832/" rel="nofollow noreferrer">Here's an example for tic-tac-toe where the choice for search depth 1 is encoded into the grid</a></p>
  <p><em>After</em> you take the move identified by the heuristic, then the horizon N moves forward. Using the &quot;similar game&quot; idea above, the derived game has changed. It is feasible that a different choice would have been better according to the heuristic evaluated on N+1 turns, or that the search will now find a forced win, tie or loss which was previously beyond its horizon.</p>
  <blockquote>
  <p>Do considerations in the quote (<strong>do even better</strong> against a suboptimal opponent) still <strong>hold</strong>?</p>
  </blockquote>
  <p>Yes, but only in terms of potentially being able to score more highly on the heuristic by turn N. The search will identify a next move where the <em>worst case</em> scenario (assuming the other player chooses a response which minimises your possible score by turn N) is a certain heuristic score on turn N. If you are not in that worst case due to the other player's choice, it may be possible to do better and reach a higher score <em>by turn N</em>.</p>
  <p>However, because the horizon will move forward following a turn, you now have further information from searching deeper into the game, and that could mean that the other player's move was in fact worse for you. You can still guarantee a heuristic score by turn N at least as good as the one found before, but now you can see turn up to N+2, and a new search may find important differences.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-12T10:03:29.190Z
Answers.LastActivityDate: 2022-06-12T14:13:14.130Z
Answers.LastEditDate: 2022-06-12T14:13:14.130Z
Answers.UserDisplayName: Neil Slater
Body: <p>The following quote (from AIMA) refers to the situation in which the minimax algorithm computes its values directly from the <strong>terminal states</strong>.</p>
  <blockquote>
  <p>(The) definition of optimal play for MAX assumes that MIN also plays optimally—it maximizes the worst-case outcome for MAX. What if MIN does not play optimally? Then it is
  easy to show (...) that MAX will <strong>do even better</strong>. Other strategies against suboptimal opponents may do better than the minimax strategy, but these strategies necessarily do worse against optimal opponents.</p>
  </blockquote>
  <p>But what about minimax using an evaluation function for nodes at a certain depth? Can we achieve optimality? If we do not have a <strong>perfect evaluation function</strong>, is the best we can do to achieve optimality <strong>with respect to the specific evaluation function</strong>?</p>
  <p>Do considerations in the quote (<strong>do even better</strong> against a suboptimal opponent) still <strong>hold</strong>?</p>
  
Tags: <minimax><norvig-russell><evaluation-functions><optimality>
Title: Can we achieve optimality with minimax using an evaluation function?
UserDisplayName: Kestina
ThreadText: # Can we achieve optimality with minimax using an evaluation function?
  
  (Asked by: username_0 on 2022-06-11)
  
  The following quote (from AIMA) refers to the situation in which the minimax algorithm computes its values directly from the **terminal states**.
  
  > (The) definition of optimal play for MAX assumes that MIN also plays optimally—it maximizes the worst-case outcome for MAX. What if MIN does not play optimally? Then it is
  > easy to show (...) that MAX will **do even better**. Other strategies against suboptimal opponents may do better than the minimax strategy, but these strategies necessarily do worse against optimal opponents.
  
  But what about minimax using an evaluation function for nodes at a certain depth? Can we achieve optimality? If we do not have a **perfect evaluation function**, is the best we can do to achieve optimality **with respect to the specific evaluation function**?
  
  Do considerations in the quote (**do even better** against a suboptimal opponent) still **hold**?
  
  **Tags:** minimax, norvig-russell, evaluation-functions, optimality
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-06-12. Score: 1
  
  You can take any two player zero-sum game and change its rules, so that they become:
  
  * Start from the game state being evaluated.
  * Play for up to N turns.
  * If no winner is found after N turns, the winner is the one with the highest heuristic score (calculated in the same way as your minimax algorithm).
  
  This is still a valid game, based on the original. A minimax using the same non-terminal heuristic will solve that derived/limited game optimally.
  
  The solution may be unrelated to solutions to the original game. As a worst case, choose as your heuristic a random oracle (that assigns a random number to each state, in practice this could be done using a cryptographic hashing function). In the extreme case of N=1, then a random oracle heuristic will perform - on the original game - much the same as a random player, until either player is 1 turn away from winning. As N increases to include more possible game ends, the effect of the poor heuristic is reduced, as forced wins/losses are discovered (and usually those parts of the search tree removed because one of the players would reject them).
  
  If you have a perfect heuristic, then the game is solved, and searching with N=1 against that heuristic will result in optimal play for the original game. [Here's an example for tic-tac-toe where the choice for search depth 1 is encoded into the grid](https://xkcd.com/832/)
  
  *After* you take the move identified by the heuristic, then the horizon N moves forward. Using the "similar game" idea above, the derived game has changed. It is feasible that a different choice would have been better according to the heuristic evaluated on N+1 turns, or that the search will now find a forced win, tie or loss which was previously beyond its horizon.
  
  > Do considerations in the quote (**do even better** against a suboptimal opponent) still **hold**?
  
  Yes, but only in terms of potentially being able to score more highly on the heuristic by turn N. The search will identify a next move where the *worst case* scenario (assuming the other player chooses a response which minimises your possible score by turn N) is a certain heuristic score on turn N. If you are not in that worst case due to the other player's choice, it may be possible to do better and reach a higher score *by turn N*.
  
  However, because the horizon will move forward following a turn, you now have further information from searching deeper into the game, and that could mean that the other player's move was in fact worse for you. You can still guarantee a heuristic score by turn N at least as good as the one found before, but now you can see turn up to N+2, and a new search may find important differences.
  
  
  ---
  
  