12/06/06 David Haley 1CS 157: Computational LogicFall 2006General Game PlayingDavid HaleyStanford UniversityLogic Group12/06/06 David Haley 2Games●One of the oldest human activities●Physical, intellectual activity●Outlet for ‘safe’ competition●More recently, games on the computer●Why not write programs to play games?●Artificial Intelligence.12/06/06 David Haley 3AI and Games●Most very domain-specific●E.g., Deep Blue–Amazingly good at Chess. Cannot play anything else, even variants of Chess (e.g. Knight-Chess).●These programs only play one game, or a set (not class) of predefined games●Are these intelligent programs or intelligent programmers?12/06/06 David Haley 4AI and Games●Learning structures specified by humans●Heuristic structures specified by humans●AI agent learns in framework for very precise games developed with careful thought and insight by humans●What structures or regularities do humans look for in a game to build this framework? Can the search for features be generalized?12/06/06 David Haley 5General Games●Instead of playing one kind of game, program should be able to play arbitrary games.–It would have to deduce (like humans) what the general physics and principles of the world are.●Most general form: should be able to interact with arbitrary environment, observe effects, deduce physics, ... like humans–For now: we focus on a formally specified, predefined class of games.●Emphasis less on learning one game; more on feature discovery and transfer learning.12/06/06 David Haley 6General Game Playing●Definition from games.stanford.edu:A General Game Playing System is one that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.12/06/06 David Haley 7General Game Playing●Rules sent to play at beginning of game●Player given time to cogitate●Only thing known about a game beforehand is the form the rules come in (i.e. the space of possible rules)12/06/06 David Haley 8Considered Games●Completely specified.–Players know all rules (physics) in advance.●Complete information.–Players know everything about the world's state.●Deterministic.–No probabilities. Next state is defined as function of current state and player moves.●Finite.–Finite number of possible game states.–One initial state, one or more terminal states.●Simultaneous move.12/06/06 David Haley 9Considered Games●Playable.–Every player has at least one legal move in every non-terminal state.●Winnable.–Single-player games strongly winnable.–Multi-player games at least weakly winnable.12/06/06 David Haley 10Game Description Language●Games are finite state machines.–But a finite state machine for games can be huge!●We need a more compact representation.●Formal logical language–Subset of KIF (Knowledge Interchange Format)●Uses (subset of) Relational Logic to define games and states.12/06/06 David Haley 11Logic Language●Constants: a, b, white, ...●Variables: ?x, ?y...●Functions (see caveat): (f a b c)●Relations: e.g. (true (f a))●Connectives: e.g. (and (true ?x) (true ?y))●No quantifiers! Variables are implicitly universal.●Domain:–HHHHHerbrand: the domain of discourse is the set of constants. (I.e., domain closure.)–Unique names. In particular, constant a and constant b refer to distinct objects in the domain.12/06/06 David Haley 12Language Vocabulary●Game-independent relation constants–(init x): x is true in initial state–(true x): x is true in current state–(next x): x will be true in the next state–(legal x y): player x may do y in current state–(does x y): player x performs y in current state–terminal: current state is terminal–(goal x y): player x has obtained score y.12/06/06 David Haley 13Language Vocabulary●Game-specific constants:–Player objects, e.g. white, black, wumpus...–Action objects, e.g. (mark 1 2)–State objects, e.g. (cell 1 2 x)●aka: transients, fluents, volatiles...–View relations, e.g. (row 1 x)–Type relations, e.g. (number 1)12/06/06 David Haley 14Function Caveat●Be careful about functions vs. relations●Consider the function: (cell 1 2 b)–This is not a relation–It maps the arguments to the state object saying that cell 1;2 has a blank●(true (cell 1 2 b))–The state object is in the true relation.●Functions not used otherwise, e.g. we do not define s(1) = 2.–Instead, relations: (successor 1 2)12/06/06 David Haley 15Playing the Game●Game fully described in logic.●To reason about the game, need a prover.●Two main knowledge bases:–Static information. Basically, the game description. Includes base relations, rules and so forth.–Volatile (state) information. What is true in the current state.12/06/06 David Haley 16Static Knowledge●Describes basic facts about game–(player white)–(init (cell 1 1 b))–(successor 1 2)●Gives rules of the game–(less-than ?x ?y) <= (and (successor ?z ?x) (less-than ?z ?y))–(next (true (cell 1 1 b))) <= (true (cell 1 1 b))–(legal ?x (mark ?y ?z)) <= (and (true (cell ?y ?z b)) (true (control ?x)) )–etc.12/06/06 David Haley 17Volatile Knowledge●List of things true in current state.–(true (cell 1 1 b))–(true (cell 1 2 x))–(true (cell 1 3 o))–(true (cell 2 1 b))–(true (cell 1 2 x))–(true (cell 1 3 b))–...12/06/06 David Haley 18No Lexical Assumptions●Except for built-in relations, vocabulary has no semantic meaning.●In particular “cell” is simply a string of characters and the player must make no assumptions that “cell” is actually talking about cells on a board.●During competition, names are scrambled before being sent to the player:–(next (welcoul ?m ?n himenoing)) <= (and (does poontron (dukepse(?m ?n))) (true (welcoul ?m ?n lorenchise)) )12/06/06 David Haley 19Example●Tic-Tac-Toe●Notes on size:–Naively, search tree has 9! = 362,880 states–Taking advantage of e.g. symmetry can bring it down considerably●Instead of having 9 choices for the first move, there are only three distinct moves modulo board rotation●Consider Chess with more than 1030!12/06/06 David Haley 20Putting it Together●How does one actually reason about the game?●Everything (can be) done with a logic prover.●Standard techniques used:–answer extraction–unification–backward-chaining12/06/06 David Haley 21Proving Things●Example proof: is player white in
View Full Document
Unlocking...