Please enable JavaScript.

Coggle requires JavaScript to display documents.

Adversarial Search - Coggle Diagram

- - - - Minimize the outcome
  - - - Players alternate turns
      - Compute each node's minimax value
      - Values are propagated to the root
  - - - time: O(b^m)
        space: O(bm)
  - - - Cannot search to leaves
        
        Depth-limited search
        
        We only search to a certain deepness in the game
        
        what we gain
        
        Search time is now better
        
        we have to encode a
        good evaluation function
        
        Scores non-terminal states
        
        weigh the features
        
        ideal function
        
        4 more items...
        
        determine what a "good" state looks like
        
        what we lose
        
        No optimal play
        
        Evaluation functions are not perfect
        
        The deeper, the better
        
        Exploring deeper gives us better results
        
        game-tree prunning
        
        We avoid exploring states which
        don't provide any better outcome than
        what we already now
        
        alpha-beta pruning
        
        we are computing the min-value at
        some node n
        
        we're looping over n children
        
        n's estimate of the childrens' min is dropping
        
        Who cares about n's value? MAX
        
        Let a be the best value that max
        can get at any choice point along
        the current path from the root
        
        If n becomes worse than a, MAX will avoid it,
        so we can stop considering the other children.
  - - - Good tie-breaking is needed
        
        account for the future
- - - - Montecarlo-deep learning
- - - - Deterministic
      - Zero sum
        
        Opposite utilities
        
        agents are oponents
        
        competition
        
        think of a single value that one maximizes and the other minimizes
      - Perfect information
    - - Recommends a move each state
    - - States
      - players
      - Actions
      - Transition function
      - terminal test
      - Terminal utilities