Download Presentation
## Introduction

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**General Game Playing Lecture 1**Introduction Michael Genesereth Spring 2006**Game Playing**Human Game Playing • Intellectual Activity • Skill Comparison Computer Game Playing • Testbed for AI • Limitations**General Game Playing**General Game Players are systems able to accept descriptions of games at runtime able to use such descriptions to play the games**Technology**Unlike specialized game players (e.g. Deep Blue), they do not use algorithms designed in advance for specific games. Artificial Intelligence Technologies knowledge representation reasoning and learning rational behavior**X**O X Tic-Tac-Toe**a**b c Single Player “Games”**Activities**Testbed for General Game Playing Games Game Manager Reference Players Annual Competition AAAI 2005 - Winner: Jim Clune, UCLA AAAI 2006 - $10,000 prize to the winner Website - http://games.stanford.edu Research Papers Educational Materials Discussion groups Research Profiles**AAAI-05 Qualifying Teams**Jim Clune - UCLA and Parasoft Stephan Schiffel, Michael Thielscher - Dresden University David Kaiser - Florida International Univeristy Xinxin Sheng - North Carolina State Peter Stone, Greg Kuhlmann, Kurt Dresner - UT Austin Matt Grounds - University of York**Programme for Today**General Game Playing Game Description Language General Game Players General Game Playing Logistics**Finite Deterministic Games**Environment Game “world” with finitely many states One initial state and one or more terminal states Players Finite number of players Each with finitely many “percepts” and “actions” Each with one or more goal “states” Deterministic Operation Environment changes only in response to moves Synchronous and asynchronous actions**Single Player Game as a State Machine**a b s2 s5 s8 a a b a a b d b b s1 s3 s6 s9 s11 d a c a a c b b a s7 s4 s10**Composite Actions for Multiple Players**aa ab s2 s5 s8 aa bb ab aa aa ab bb ab ab s1 s3 s6 s9 s11 ba aa ba ba ab bb bb aa aa s4 s7 s10**Playability**A game is playable if and only if every player has at least one legal move in every non-terminal state. Note that in chess, if a player cannot move, it is a stalemate. Fortunately, this is a terminal state. In GGP, we guarantee that every game is playable.**Winnability**A game is strongly winnable if and only if, for some player, there is a sequence of individual moves of that player that leads to a terminating goal state for that player. A game is weakly winnable if and only if, for every player, there is a sequence of joint moves of the players that leads to a terminating goal state for that player. In GGP, every game is weakly winnable, and all single player games are strongly winnable.**Direct Description**Since all of the games that we are considering are finite, it is possible in principle to communicate game information in the form of transition graphs. Problem:Size of description. Even though everything is finite, the graphs can be large. Ideas: 1. Different Conceptualization 2. Compact Encoding**Relational Logic**Object Variables: X, Y, Z, … Object Constants: a, b, c, … Function Constants: f, g, h, … Relation Constants:p, q, r, … Logical Operators:=,#,~, :- Terms: X, Y, Z, a, b, c, f(a), g(a,b), h(a,b,c) Relational Sentences: p(a,b) Rules: r(X,Y):-p(X,Y) & ~q(Y) & X#b Safe rules with stratified negation. Herbrand semantics (with NAF)**Vocabulary**Game-specific names for: players, e.g. white, black actions, e.g. mark(row,col) fluents, e.g. cell(row,col, mark) views, e.g. row(row,mark) Game-independent relation constants: init(fluent) - fluent is true in the initial state true(fluent) - fluent is true in the current state next(fluent) - fluent will be true in the next state legal(player,action) - player may perform action in the current state does(player,action) - player performs action in the current state goal(player,score) - current state is worth score to player terminal - current state is terminal**Initial State**init(cell(1,1,b)) init(cell(1,2,b)) init(cell(1,3,b)) init(cell(2,1,b)) init(cell(2,2,b)) init(cell(2,3,b)) init(cell(3,1,b)) init(cell(3,2,b)) init(cell(3,3,b)) init(control(x))**Legality**legal(W,mark(X,Y)) :- true(cell(X,Y,b)) & true(control(W)) legal(white,noop) :- true(cell(X,Y,b)) & true(control(black)) legal(black,noop) :- true(cell(X,Y,b)) & true(control(white))**Physics**next(cell(M,N,x)) :- does(white,mark(M,N)) next(cell(M,N,o)) :- does(black,mark(M,N)) next(cell(M,N,Z)) :- does(W,mark(M,N)) & true(cell(M,N,Z)) & Z#b next(cell(M,N,b)) :- does(W,mark(J,K)) & true(cell(M,N,b)) & (M#J | N#K) next(control(white)) :- true(control(black)) next(control(black)) :- true(control(white))**Supporting Concepts**row(M,W) :- diagonal(W) :- true(cell(M,1,W)) & true(cell(1,1,W)) & true(cell(M,2,W)) & true(cell(2,2,W)) & true(cell(M,3,W)) true(cell(3,3,W)) column(N,W) :- diagonal(W) :- true(cell(1,N,W)) & true(cell(1,3,W)) & true(cell(2,N,W)) & true(cell(2,2,W)) & true(cell(3,N,W)) true(cell(3,1,W)) line(W) :- row(M,W) line(W) :- column(N,W) line(W) :- diagonal(W) open :-true(cell(M,N,b))**Goals and Termination**goal(white,100) :- line(x) goal(white,50) :- ~line(x) & ~line(o) & ~open goal(white,0) :- line(o) goal(black,100) :- line(o) goal(white,50) :- ~line(x) & ~line(o) & ~open goal(white,0) :- line(x) terminal:- line(W) terminal:- ~open**No Built-in Assumptions**• What we see: • next(cell(M,N,x)) :- • does(white,mark(M,N)) & • true(cell(M,N,b)) • What the player sees: • next(welcoul(M,N,himenoing)) :- • does(himenoing,dukepse(M,N)) & • true(welcoul(M,N,lorenchise))**Logic**Possible to use logical reasoning for everything Computing legality of moves Computing consequences of actions Computing goal achievement Computing termination Easy to convert to other representations Simplicity of logical formulation Simple, widely published algorithms**X**O X State Representation cell(1,1,x) cell(1,2,b) cell(1,3,b) cell(2,1,b) cell(2,2,o) cell(2,3,b) cell(3,1,b) cell(3,2,b) cell(3,3,x) control(black)**Legality Computation**legal(W,mark(X,Y)) :- cell(1,1,x) true(cell(X,Y,b)) cell(1,2,b) true(control(W)) cell(1,3,b) cell(2,1,b) legal(white,noop) :- cell(2,2,o) true(cell(X,Y,b)) cell(2,3,b) true(control(black)) cell(3,1,b) cell(3,2,b) legal(black,noop) :- cell(3,3,x) true(cell(X,Y,b)) control(black) true(control(white)) Conclusions: legal(white,noop) legal(black,mark(1,2)) … legal(black,mark(3,2))**Update Computation**cell(1,1,x) cell(1,1,x) cell(1,2,b) cell(1,2,b) cell(1,3,b) cell(1,3,o) cell(2,1,b) black cell(2,1,b) cell(2,2,o) cell(2,2,o) cell(2,3,b) mark(1,3) cell(2,3,b) cell(3,1,b) cell(3,1,b) cell(3,2,b) cell(3,2,b) cell(3,3,x) cell(3,3,x) control(black) control(white) next(cell(M,N,o)) :- does(black,mark(M,N)) & true(cell(M,N,b))**X**O X O O X X X X O X O X O X X X O O O O X O X O X X Game Tree Expansion**X**O X O X X X X O X O X O O X X X X X O O O O X X O X O O X X X X O X O X O X X X O O O O X O X O X X Game Tree Search 100 X O X 100 O X 100 100 100 100 100 100**Resource Limitations**Large state spaces ~5000 states in Tic-Tac-Toe ~1030 states in Chess Limited Resources Memory Time (start clock, move clock)**Partial Search**Incremental Search Expand Game Graph incrementally As much as time allows Use Minimax evaluation on non-terminal states Evaluation function for non-terminal states? Clune: maximize number of options Novelty and reversibility Other possibilities? Opportunity for research.**Game Graph Analysis**Graph Analysis Bottlenecks Independence, e.g. Hodgepodge Reformulation Abstract graph solve abstract problem refine abstract solution to complete solution e.g. symmetry in Tic-Tac-Toe**Modeling Other Players**Modeling other players Intra-game modeling useful only for long games Inter-game modeling possible but Unfortunately, identity information not available Must recognize style of play Assumptions Rationality?**Compilation**Partial Evaluation Fold game description into logical reasoning Recompile Specialized Data Structures Make propositional net explicit 1 bit per proposition Convert rules to bit operations**Performance Improvement**Performance Improvement over multiple matches Unfortunately, game identity not supplied Must recognize that it is the same game May be able to play matches during start clock Performance improvement over multiple games Algorithms (alpha-beta and so forth) Useful Concepts (e.g. “pinned pieces”, “forks”)**Gamemaster**Parameterized Collection of Games Complete or incomplete information One player or n players Competition and Cooperation Services Sample Players (including human interface) Game Definition Support Game Manager Records Players Performance Data