2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jan 18 at 9:02
  • $\begingroup$ @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). $\endgroup$
    – Druudik
    Jan 18 at 16:06
  • $\begingroup$ 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? $\endgroup$ Jan 18 at 18:39
  • $\begingroup$ 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. $\endgroup$
    – Druudik
    Jan 18 at 19:01

0

You must log in to answer this question.

Browse other questions tagged .