Adversarial Search

Adversarial Search

Introduction

1. Trying to win, when someone else is actively trying to beat us.

Involves techniques similar to searching, outright use of search techniques but the adversary is another variable to take care of.

Ex: games

2. Often considerably widens the search space.

Huge search space, visualized by a search tree.

Ex: chess game

• Average branching factor : 35
• Game running for ~50 moves
• 10154 nodes (1040 distinct ones)
• Impossible to search them all
• Have to act within a time limit

3. Player has only control on moves on alternative levels on the search tree, adversary moves in other cases.

4. We can’t predict how adversary play, but can consider all its moves and compute most favourable.

5. A common assumption is :- adversary will do the best move for them. It is a variable to take care of.

Min Max algorithm in Adversarial Search

• Two players, “Max vs Min” used in zero sum games of perfect information.

Zero sum games : one player’s gain (or lose) of utility, is balanced by the loses (or gains) of the utility of the other player.  Total gains - Total loses = zero. So, strictly competitive.

Perfect information : nothing to hide

• Search strategy id MinMax strategy.

MinMax strategy : choose best move assuming the opponent plays optimally.

• MinMax algorithm is a recursive algorithm to choose the next move (in position with highest minmax value) in an n-player game. (here we are talking about two-player game)

• A value is associated to find the optimal move.
• In a search tree, of a two-player game, two kinds of nodes :-
• Representing player moves :  max nodes

• Representing adversary’s moves : min nodes

• Max node’s goal

To MAXIMIZE the value of the sub-tree rooted at the node.

To do this, a MAX node chooses the child with the greatest value,

which becomes the value of the MAX node.

• Min node’s goal

To MINIMIZE the value of the sub-tree rooted at the node.

To do this, a MIN node chooses the child with the least value,

which becomes the value of the MIN node.

Minmax value

A game ends with a certain utility.

Utility : utility of a node is represented by minmax value.

+1 win

0 draw

-1 lose

Player who do the first move is MAX : will maximize the utility.

Adversary is MIN : will minimize the utility.

Minmax value is the utility for MAX of the final state we will end up in if both players play optimally.

It can be shown that if MIN plays sub-optimally, MAX will do even better,

Computing Minmax

Multi Player games

• Minmax can be extended to multiplayer games by making utility into a vector.
• However, multiplayer games can be much more complicated.
• Can be alliances between players, that disrupt the normal purely selfish maximum utility behaviour.

Pruning

• In general, we cannot explore the whole tree, so we will need to prune it.
• That means, we will not need to examine whole branches of the tree, to reduce its’ effective branching factor.
• For real games, pruning will require intelligent heuristics.
• But there are also some basic strategies that can cut down the number of visits in general.
• Pruning does not affect the final result. This means that, it gets the exact same result as does the full Minmax.

Alpha - Beta Pruning

This procedure can speed up a depth-first Minimax search and find an optimal minmax solution by avoiding unnecessary steps.

General principle of alpha-beta pruning

1. Consider a node “n”, somewhere in the tree, that Player has a choice of moving to that node or prune it.
2. If Player has a better choice “m” , either at the parent node of “n” or at any choice further up, then “n” will never be reached in actual play.
3. So, once we have found out enough about n (by examining some of its descendants) to reach this conclusion, we can prune it.

Value V : evaluation value of a node

Alpha α : highest value seen so far on MAX level

Beta  β : lowest value seen so far on MIN level

If α ≥ β  then prune

α-β pruning stops searching down a branch of a tree, when you can determine that it is a dead end/ reached to the leaf nodes of the tree.

Further explanation of α-β pruning

• When maximizing:

Do not expand any more sibling nodes once a node has been seen whose evaluation is smaller than α

• When minimizing:

Do not expand any more sibling nodes once a node has been seen whose evaluation is greater than β

Some examples

Example 1

Example 2

Example 3

Example 4

Example 5

Example 6

Example 7

Questions: Tic Tac Toe

Questions: pen and paper game

Sub tree 1

Sub tree 2

Sub tree 3

Sub tree 4

Questions: connect squares

ii) yes, it is possible to player 2 to win the game.

   There is a winning position , the utility value of +1 in at least one of the leaf nodes.

iii) the all three moves have utility 0, so any of the moves can be chosen for player 2 as the best  move, where player 2 will not lose.

iv) Alpha beta pruning

All nodes below the top node in the tree evaluate to the same value of 0. So, after one branch has evaluated, the subsequent branches can be pruned as soon as it is certain hat there is best value is no better than 0.

All branches below the leftmost branch are traversed, so it gets evaluated as 0 and the preliminary value of the topmost node is 0. From the middle branch, going left, we get an preliminary value of 0. Since this is a MIN level, it means that its’ final value can be no greater than 0, so that the middle is never better than the left. So, we can prune the right branch from the middle node on level one. Similarly, we can prune the right branch below the rightmost node on level one.  So, going in the order of the picture will allow some alpha beta pruning to be done.

Vocabulary