Body: <p>I am working on a controller that plays Ms. Pac-Man using a minimax algorithm. The controller has a <strong>limited time amount</strong> in which it can choose a move on each round, otherwise when the time runs out the system chooses a random action instead.</p>
  <p>My goal is to select a value for the <strong>depth</strong> that is <strong>large enough</strong> 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 <strong>intuitive</strong> thing: I increased the depth until I noticed a drop on the score values, but that drop could have occurred casually.</p>
  <p>Is there a more <strong>scientific/statistical way</strong> to do that (that ideally addresses both the score e the timeout issues)?</p>
  <p>(I fantasized about performing repeated hypothesis testing, but I quickly learned how silly that idea was when I heard about multiple testing problem).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-13T19:27:43.307Z
Comments.Text: Can you do a breadth first search using all available time (leaving just enough to collapse the tree and find the optional action)?
Comments.UserDisplayName: Lee Reeves
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-14T07:34:08.203Z
Comments.Text: 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.
Comments.UserDisplayName: InCrisis
Tags: <game-ai><minimax>
Title: How should I choose the depth for minimax if I have a strict time constraint?
UserDisplayName: InCrisis
ThreadText: # How should I choose the depth for minimax if I have a strict time constraint?
  
  (Asked by: username_0 on 2022-06-13)
  
  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).
  
  **Tags:** game-ai, minimax
  > **Comments:**
  > **username_1**: Can you do a breadth first search using all available time (leaving just enough to collapse the tree and find the optional action)?  
  > **username_0**: 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.  
  
  ---
  
  ## 0 answers
  
  