Expectimax Search

Description:

• A single agent game trying to maximize utilities
  • Due to malfunction, chance, imperfect information,… controlled by chance
  • 2 agents game is called Expectiminimax Search
  • ex: 2048
• Values should now reflect the average case outcome, not worst or best
• Compute the average score under optimal play
  • Expected value
  • 

Expectimax Pruning:

• No pruning can be done

Depth-limit expectimax:

• Limit to certain depth
• But estiamte of true expectimax value requires a lot of work to compute

Danger of optimism vs Pessimism:

• Too optimism: underestimate the chances of enemies’ picking nodes that is good for him
• Too pessimism: overestimate

Overcome resource limits with randomness:

• Monte Carlo Tree Search

Formalize the underlying uncertain result :

• with Markov Decision Process