Body: <p>I am trying to create <strong>minimax evaluation</strong> function for the <strong>Ms Pacman</strong> game. The goal of the player is to maximize score.</p>
  <p>I have some idea about the <strong>features</strong> that I would like to use in my evaluation function (which is weighted sum of all features):</p>
  <ul>
  <li>avg distance to the ghosts</li>
  <li>score</li>
  <li>is pacman close to pacdots</li>
  <li>etc.</li>
  </ul>
  <p>This can work in some way if AlphaBeta search considers only <em>non-terminal</em> nodes. However evaluation for the <em>terminal</em> nodes will be substantially different from evaluation of <em>non-terminal</em> nodes because we are returning true evaluation which is weighted score in this case. Hence once search reaches some terminal nodes, it may discard them completely or focus too much on them (depending on how our evaluation changes).</p>
  <p>In games with decisive result we can directly evaluate loss/draw/win with some very small/big value to overwrite the effect of evaluation function during search and properly backpropagate evaluations.</p>
  <p>However what is the correct approach for the games with score?</p>
  <p>I was thinking about adding another feature such as <em>is game finished</em> and using it in evaluation but this does not seem like an optimal solution.</p>
  <p>I will be thankful for any tips or references.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T09:02:58.433Z
Comments.Text: Is the Ms Pacman game a 2-player game, or are you training both the main character and the enemies in your version? I'm not sure that I see the relevance of minimax if not?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T16:06:18.163Z
Comments.Text: @NeilSlater It is turn based 2-player zero sum game. I am using same state evaluation for pacman and ghosts. Also all ghosts are moved in single turn (same for pacman).
Comments.UserDisplayName: Druudik
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T18:39:45.630Z
Comments.Text: So, just to be clear, the ghosts will be AI-controlled too? You said zero-sum game, so the score of the Ms Pacman, and score of the ghosts are equal and opposite? Or are the scores a separate quantity (not zero-sum) and highest score wins the game?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T19:01:21.413Z
Comments.Text: Yes, ghosts and pacman are controlled by the same minimax algorithm. There is no winner or looser in this game (which is the reason for my post; if there would be winner I would just return +infinity or -infinity from terminal nodes based on the fact whether pacman or ghosts won). The goal of the pacman is to gain as much score as possible. Goal of the ghosts is to minimize the pacman's score. So yes, I consider this game as a zero-sum game.
Comments.UserDisplayName: Druudik
Tags: <game-ai><minimax><alpha-beta-pruning><atari-games><evaluation-functions>
Title: Minimax evaluation function for games with score instead of loss/draw/win result
UserDisplayName: Druudik
ThreadText: # Minimax evaluation function for games with score instead of loss/draw/win result
  
  (Asked by: username_0 on 2022-01-17)
  
  I am trying to create **minimax evaluation** function for the **Ms Pacman** game. The goal of the player is to maximize score.
  
  I have some idea about the **features** that I would like to use in my evaluation function (which is weighted sum of all features):
  
  * avg distance to the ghosts
  * score
  * is pacman close to pacdots
  * etc.
  
  This can work in some way if AlphaBeta search considers only *non-terminal* nodes. However evaluation for the *terminal* nodes will be substantially different from evaluation of *non-terminal* nodes because we are returning true evaluation which is weighted score in this case. Hence once search reaches some terminal nodes, it may discard them completely or focus too much on them (depending on how our evaluation changes).
  
  In games with decisive result we can directly evaluate loss/draw/win with some very small/big value to overwrite the effect of evaluation function during search and properly backpropagate evaluations.
  
  However what is the correct approach for the games with score?
  
  I was thinking about adding another feature such as *is game finished* and using it in evaluation but this does not seem like an optimal solution.
  
  I will be thankful for any tips or references.
  
  **Tags:** game-ai, minimax, alpha-beta-pruning, atari-games, evaluation-functions
  > **Comments:**
  > **username_1**: Is the Ms Pacman game a 2-player game, or are you training both the main character and the enemies in your version? I'm not sure that I see the relevance of minimax if not?  
  > **username_0**: @NeilSlater It is turn based 2-player zero sum game. I am using same state evaluation for pacman and ghosts. Also all ghosts are moved in single turn (same for pacman).  
  > **username_1**: So, just to be clear, the ghosts will be AI-controlled too? You said zero-sum game, so the score of the Ms Pacman, and score of the ghosts are equal and opposite? Or are the scores a separate quantity (not zero-sum) and highest score wins the game?  
  > **username_0**: Yes, ghosts and pacman are controlled by the same minimax algorithm. There is no winner or looser in this game (which is the reason for my post; if there would be winner I would just return +infinity or -infinity from terminal nodes based on the fact whether pacman or ghosts won). The goal of the pacman is to gain as much score as possible. Goal of the ghosts is to minimize the pacman's score. So yes, I consider this game as a zero-sum game.  
  
  ---
  
  ## 0 answers
  
  