tags:

• 🌱
• AI
• ComputerScience
• Search date: 17--Apr--2023

• Recurse down to leaf node of search tree and compute utility of leaf nodes
• Values are recursively returned and tree is populated at each state based on the player

• Opponent is optimal and acts the same

• Time
  • Depth first search manner of populating tree
  • For branching factor of b and depth of d
  • $O(b^d)$
• Memory
  • Each node has b possible action which is equal to the branching factor
  • Actions for each level is kept in memory
  • $O(bd)$

When there is no time bound

• Complete tree generation is possible
• Search is complete and optimal action can be guaranteed

When there is time bound or insufficient memory space

• Partial tree generation
  • Complete tree generation may not be possible
• Evaluation function as heuristic used
  • Used to estimate utility of node
  • Performed on Quiescent nodes
  • Suffers from Horizon effect

• The MAX will do at least as well against an optimal MIN, or possibly better
  • Minimax computes the tree and assumes that the opponent always picks the optimal action that minimises MAX utility
  • Suppose MIN is sub-optimal, then the action taken may not be the min utility for MAX
  • MAX would be able to achieve the same or higher utility in the game

def minimax_search(game, state) -> action:
    value, action = max_value(game, state)
    return action
def max_value(game, state) -> action:
    if game.terminate(state):
        return (game.utility(state), None)
    v = int.max() * -1
    a = None
    for action in game.actions(state):
        v_opp, action_opp = min_value(game, game.nextstate(state,action))
        if v_opp > v:
            v,a = v_opp, action_opp
    return (v,a)
def min_value(game, state) -> (value, action):
    if game.terminate(state):
        return (game.utility(state), None)
    v = int.max()
    a = None
    for action in game.actions(state):
        v_opp, action_opp = max_value(game, game.nextstate(state,action))
        if v_opp < v:
            v,a = v_opp,action
    return (v,a)

Links: