Design and Analysis of Algorithms

Games

Common games attempted in Artificial Intelligence

Chess
Checkers
Go
Backgammon
Blackjack
Kalah
Bridge
Othello
Draw Poker

Not Puzzles ...why? Compare to CSCI 356 text.

Example of an old approach (still a puzzle)

UNIX Mastermind

List all possible codes

Randomly choose the first guess

Eliminate codes which could not be right (Based on opponent's reply).

Choose the first of the remaining codes for the next guess

If not done then go to 3.

Maximum of 8 colors, 5 positions

Why does this work?

What's wrong with it?

Game Trees

Games are conveniently represented as game trees

Given the initial state (e.g. Starting board position), the game rules describe how to generate alternative lines of play to a conclusion.

Example of (Part of) a game tree --

Tic-Tac-Toe (Aka naughts and crosses)
Ply of a game tree
has P levels (Including root)

Depth is D then P=D+1
     Branching factor
     Look ahead
             10 moves, 10 ply

Size of a game tree is determined by
     Average number choices from each position (Branching Factor)
     Length of Game (Depth)
         => # alternative lines of Play = B.F.^Depth.

Some Examples

B.F. Ave. Length Lines Of Play

Tic-Tac-Toe 4 6-7 10⁴

Checkers 6 60 10⁴⁰

Chess 30 80 10¹²⁰

Go 200

Backgammon 800

So it is impossible to search through interesting games to the end.

Note: even Tic-Tac-Toe Becomes impossibly large with minor changes (4x4, cubic, probabilistic)

Generate and Test

generate procedure that produce only valid (legal) moves.

test procedure to "recognize" best path static evaluation function (sef) (A* like)

Initial attempts

Start at a current position
Use plausible-move generator to generate set of possible successor positions (1 ply)
apply static evaluation function (sef)
choose best
(Assume that sef returns large values to indicate good situations ... want to maximize sef of board positions)
Look-ahead (since sef is only estimate)

... However many ply ... (time allowed)

depth-first / depth limited

MiniMax

The term comes from the Min-Max theorem of Von Neumann (~1925)

Intuitively

Minimize the damage your opponent can do
Find the worst thing your opponent can do to you along each line of play and choose the least obnoxious
Minimizing Maxima, Maximizing Minima

Minimax as an algorithm can be iterated up a game tree from terminal nodes.

Note - Minimax assumes rational play by the opponent. in complete game trees, irrational play by the opponent leads to better positions. With incomplete information this is not always true.

Alpha-Beta Procedure .. Prunes Game Tree

MiniMax

Plausible-move generator
static evaluation function

reduces # of trees branches that must be generated
reduces # of static evaluations

Pruning

Based on the following observations

Game trees are generated depth-first
if the best possible value below some node is worse than the best possible known so far, there is no need to explore further below the node

= Max, best known so far to us

= Min, best known so far to them

Here is some detail

Try pruning on this

results in the same backed up value at the root as pure minimax

if the best alternatives are considered first, the effective branching factor, b, is reduced to the square root of b.

No one seems to know who invented . The name is due to McCarthy.

Analysis of

Worst case: branch ordered so Alpha-beta does nothing
Best case: Suppose tree ordered with each best move being the leftmost alternative at each node

Need not consider all of the opponent's replies to alternatives - but DO deal with all options of moving player

Why? ... if an opponent has some responses that make a move bad no matter how the moving player continues, then the move must be bad.

In the Kasparov vs. Deep Blue match the basic techniques were A* and minimax. Consider A*.

Different levels of game (opening, etc). Also Samuels and signature tables signature tables and More on IBM and AI