Adversarial Search

We will set up a framework for formulating a multi-person game as a search problem.

We will consider games in which the players alternate making moves and try respectively

to maximize and minimize a scoring function (also called utility function). To simplify

things a bit, we will only consider games with the following two properties:

• Two player - we do not deal with coalitions, etc.

• Zero sum - one player's win is the other's loss; there are no cooperative victories

We also consider only perfect information games.

Game Trees

The above category of games can be represented as a tree where the nodes represent the

current state of the game and the arcs represent the moves.

The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. Each individual move by one player is called a "ply". The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff).

Each terminal position has a score. High scores are good for one

of the player, called the MAX player. The other player, called MIN player, tries to

minimize the score. For example, we may associate 1 with a win, 0 with a draw and -1

with a loss for MAX.

Example : Game of Tic-Tac-Toe

Optimal decision in games

N queens

Goal: Put n chess-game queens on an n x n board, with no two queens on the same row,

column, or diagonal.

Example:

Chess board reconfigurations

Here, goal state is initially unknown but is specified by constraints that it must satisfy

Hill climbing (or gradient ascent/descent)

Iteratively maximize “value” of current state, by replacing it by successor state that has

highest value, as long as possible.

Note: minimizing a “value” function v(n) is equivalent to maximizing –v(n),

thus both notions are used interchangeably.

Hill climbing – example

Complete state formulation for 8 queens

Successor function: move a single queen to another square in the same column

Cost: number of pairs that are attacking each other.

Minimization problem