Transcript
Games as Search Problems
2D1350 Programmeringsparadigm n n n n n
Pointers Arrays Structures Artificial intelligence and game playing Lab assignment
n
n
n n
n
Types of Game deterministic
Min-Max-Search n
Stochastic
n
Perfect information
Imperfect information
Chess, checkers, connect-4, go, othello
The behavior / actions of the opponent are unpredictable, therefore search for a “worst-case”plan. Time limit, therefore complete search is not feasible and an approximation is needed Algorithm for perfect play (van Neumann 1944) Finite horizon, approximate evaluation (Zuse 1945, Shannon 1950, Samuel 1952) Pruning search tree (McCarthy 1956)
Backgammon, monopoly
Bridge, poker, scrabble
Optimal strategy for deterministic, perfect-information game Idea: Choose move that results in position with highest min-max-value = best achievable payoff against best opponents play 5
Max: Min: A11 3
A1 3 A12 12
A3
A2 5
A13
A21
8
5
A22 7
2 A23
A31
9
4
A33
A32 2
7
1
Min-Max-Search
Min-Max Properties
Function MINMAX-DECISION(game state) returns a move for each move in PossibleMoves(game state) do value[move] < - MINIMAX-VALUE(apply(move, game state)) end return the move with the highest value[move]
n n n n n
Function MINMAX-VALUE(game state) returns a utility value if TERMINAL-TEST(game state) then return UTILITY(game state) else if MAX is to move in game state return the highest MINMAX-VALUE of SUCCESSORS(game state) else return the lowest MINMAX-VALUE of SUCCESSORS(game state)
n
Evaluation Scheme n
n
For chess for example typically linear weighted sum of features Utility(s) = w1 f1(s) + w2 f 2(s) + …wn f n(s) w1=9 f1(s)= #white queens - #black queens w2=5 f2(s) = #white rooks - #black rooks etc.
Complete: yes, if search tree is finite Optimal : yes, if opponent plays optimal Time complexity : O(b m) Space complexity : O(bm) depth first search Chess b~35 possible moves in each state, m~100 moves per game -> exact solution infeasible Standard solution n cutoff test for search (e.g. depth limit) n evaluation function : approximates utility of board position
Cutting of Search n
n n
Min-Max-Search with Cut-Off requires n 1. CUTOFF criterion, usually based on search depth n 2. UTILITY function needs an evaluation scheme for non-terminal game states Ply = one half-move (move by one player) Chess: n 4-ply = novice n 8-ply = PC, human master n 12-ply = Deep Blue, Kasparov
2
Min-Max-Search with Cut-Off Function MINMAX-DECISION(game) returns a move for each move in PossibleMoves(game state) do value[move] < - MINIMAX-VALUE(apply(move, game state)) end return the move with the highest value[move] Function MINMAX-VALUE(game state, depth) returns a utility value if CUTOFF-TEST(depth) or TERMINAL-TEST(game state) return UTILITY(game state) else if MAX is to move in game state return the highest MINMAX-VALUE(SUCCESSOR(game state),depth+1) else return the lowest MINMAX-VALUE(SUCCESSOR(game state), depth+1)
Connect-4
n n n n
n
n
two player game 7x6 rectangular board placed vertically 21 red, 21 yellow tokens players alternate by dropping a token into one of the seven columns, the token falls down to the lowest unoccupied square a player wins if she connects four token vertically, horizontally or diagonally if the board is filled (42 tokens played) and no player has aligned four tokens the game ends in a draw
Pruning Example Max:
≥3
A1 Min: A11 3
≤2
3 A12 12
A3
A2
A13
A21
8
2
≥5 2 A23
A22 ?
?
A21 5
A23
A22 7
2
Connect-4
win for red
win for yellow
draw
3
Connect-4 Utility Function n n n
n n n
n
n
Odd square: is a square belonging to an odd row (1,3,5) Even square: is a square belonging to an even row (2,4,6) Threats: A threat is a group of three tokens of the same color which has the fourth square empty and also the square below the empty square is empty Odd threat: is a threat in which the empty square is odd Even threat: is a threat in which the empty square is even If red (moves first) has an odd threat and black cannot connect four tokens anywhere else red will win. If black (moves second) has an even threat and black cannot connect four tokens anywhere else black will win. At the beginning of the game it is advantageous to place tokens in the central columns.
Lab Assignment n
n
n n n
Design and implement a game playing program for the deterministic two player game Connect-4 Features n The program should be able to play against itself or a human opponent. n The program should visualize the evolution of the game and print out its own estimate of the utility of the current game state. n The program should determine who won or if the game ended in a draw Implement the min-max-search algorithm Implement a proper utility function for Connect-4 Test the program by letting it play against itself and against a human opponent
Lab Assignment n n
n
n
Code for connect-4 available in game.h and game.c Copy files game.h, game.c, Makefile into your local directory To add gcc to your list of modules type module add gcc/3.1 or add this line to .modules To compile game.c into executable type make
Connect-4 Game State #define ROWS 6 /* number of rows in connect-4 */ #define COLS 7 /* number of columns in connect-4 */ #define RED -1 /* value for red tokens and red player */ #define BLACK 1 /* value for black tokens and black player */ struct Game { int board[ROWS][COLS]; /* -1 token red player, 1 token black player, 0 empty square */ int currentplayer ; /* -1 red player, 1 black player */ int tokensonboard; /* counts the number of tokens on the board */ };
4
Connect-4 Move struct Move { int row; /* row coordinate of square */ int col ; /* column coordinate of square */ int token; /* -1 red token, 1 black token */ };
void MakeMove() void MakeMove(struct Game *game, struct Move move) { #if DEBUG assert((*game).board[move.row][move.col ]==0); /* assert square is empty */ if (move.row>0) assert((*game).board[move.row -1][move.col]!=0); /* assert square below is occupied */ assert((*game).currentplayer ==move.token); /* assert correct player moves */ #endif (*game).board[move.row][move. col]=move.token; /* place token at square */ (*game).currentplayer *=-1; /* switch player */ (*game).tokensonboard++; /* increment number of tokens on board */ }
void InitGame() void InitGame(struct Game *game) /* pointer reference to game state */ { int i; int j; for (i=0; i < ROWS; i++) for (j=0; j < COLS; j++) (*game).board[i][j]=0; /* empty board */ (*game).currentplayer =RED; /* red player to start game */ (*game).tokensonboard=0; };
void UndoMove() void UndoMove(struct Game *game, struct Move move) { #if DEBUG assert((*game).board[move.row][move.col ]!=0); /* assert square is occupied */ if (move.row
