Please enable JavaScript.

Coggle requires JavaScript to display documents.

Adversarial search (AND-OR Search Tree (Use to find liable solution for…

- - - - 2 players - Max and Min
        
        Formal description of game:
        
        s = initial state
        
        Player(s) = whose move
        
        Actions(s) = legal moves
        
        Results (s, a) = transition model
        
        Terminal-Test(s) = is the game over? ie. Terminal state
        
        Utility(s, p) = pay-offUtility function describes value at terminal state for player p
    - - roblem with minimax - number of game states to search is exponential in depth of tree
        
        Alpha = value of best choice (highest) along Max’s path
        
        Beta = value of best choice (lowest) along Min’s path
    - - Examples:
        
        Tictactoe, chess, checkers, othello, go
        
        Perfect information
        
        Utility values equal and opposite - I win, you lose or we draw.
        
        Abstract
        
        Useful to study
        
        States easy to represent
        
        Agents restricted to limited actions and precise rules