I am working on a controller that plays Ms. Pac-Man using a minimax algorithm. The controller has a limited time amount in which it can choose a move on each round, otherwise when the time runs out the system chooses a random action instead.

My goal is to select a value for the depth that is large enough to consent Ms.Pac-Man to achieve a decent score, but not so large to cause a lot of timeouts. Leaving the number of timeouts aside, basically I did the most intuitive thing: I increased the depth until I noticed a drop on the score values, but that drop could have occurred casually.

Is there a more scientific/statistical way to do that (that ideally addresses both the score e the timeout issues)?

(I fantasized about performing repeated hypothesis testing, but I quickly learned how silly that idea was when I heard about multiple testing problem).

  • $\begingroup$ Can you do a breadth first search using all available time (leaving just enough to collapse the tree and find the optional action)? $\endgroup$
    – Lee Reeves
    Jun 13, 2022 at 19:27
  • $\begingroup$ I don't think that I can do that. Every round lasts only a few milliseconds, and the agent chooses its moves on each round. $\endgroup$
    – InCrisis
    Jun 14, 2022 at 7:34


You must log in to answer this question.

Browse other questions tagged .