Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial Search
:memo: Adversarial search is search when there is an…
Adversarial Search
:memo: Adversarial search is search when there is an "enemy" or "opponent" changing the state of the problem every step in a direction you do not want
-
-
Applications in
Games
:heavy_check_mark: Firstly, it should be a 2-player game
:heavy_check_mark: Players alternate the moves
:heavy_check_mark: Both should have perfect information
:heavy_check_mark: Using dice is not involved
:heavy_check_mark: Clear rules for legal moves
:heavy_check_mark: Well defined outcomes
-
-
Game search
problem
:green_cross: In tic tac toe, the outcome is win,
loss or draw with values +1, -1 or 0
-
:black_circle_for_record: Successor function– Returns
a list of (action, state)
pairs, indicating a
legal move and Resulting state
:black_circle_for_record: Utility function– Numeric value
for a terminal state representing its
utility for a given player
-
MIN-MAX Algorithm
:memo: The Minimax algorithm
tries to predict the opponent's behaviour.
It predicts the opponent will take the worst action from our viewpoint
-
:red_circle: Assuming that the opponent is rational
and always optimizes its
behaviour (opposite to us)
-
-
:large_blue_circle: Possible payoff, assuming
optimal play on MIN's part
-
-
:red_circle: The Game of Nim: At each move the player must divide a pile of tokens into 2 piles of different sizes. The first player who is unable to make a move loses the game.
Drawbacks of
Minimax Algorithm
:memo: The main drawback of the minimax algorithm is that it gets really slow for complex games such as Chess, go, etc. This type of games has a huge branching factor, and the player has lots of choices to decide. This limitation of the minimax algorithm can be improved from alpha-beta pruning
Alpha-Beta Pruning
:memo: Alpha-beta pruning is a
modified version of the minimax
algorithm. It is an optimization
technique for the minimax algorithm
α-β Values
Computing
α-β Values
α: The best (highest-value) choice we
have found so far at any point along the path of Maximizer, maximum across
seen children
β: The best (lowest-value) choice we have found so far at any point along the path of Minimizer, minimum across
seen children
Propagation
Update α, β values by propagating
upwards values of terminal nodes
Update α, β values down to allow pruning
-
Analysis of α-β
:ballot_box_with_check: Pruning does not affect final result
:ballot_box_with_check: The effectiveness of alpha-beta pruning is highly dependent on the order of successors
:ballot_box_with_check: It might be worthwhile to try to examine first the successors that are
likely to be best
Ideal Ordering
The ideal ordering for alpha-beta pruning occurs when lots of pruning happens in the tree, and best moves occur at the left side of the tree. We apply DFS hence it first search left of the tree and go deep twice as minimax algorithm in the same amount of time. Complexity in ideal ordering is
Rules to find good ordering
- Occur the best move from the shallowest node
- Order the nodes in the tree such that the best nodes are checked first
- Use domain knowledge while finding the best move. Ex: for Chess, try order: captures first, then threats, then forward moves, backward moves
- We can track the states, as there is a possibility that states may repeat