From gherrity@io.nosc.mil Fri Jul 1 14:40:42 EDT 1994 Article: 22906 of comp.ai Xref: glinda.oz.cs.cmu.edu comp.ai:22906 Path: honeydew.srv.cs.cmu.edu!nntp.club.cc.cmu.edu!newsfeed.pitt.edu!gatech!swrinde!ihnp4.ucsd.edu!newshub.sdsu.edu!gherrity From: gherrity@io.nosc.mil (Mike Gherrity) Newsgroups: comp.ai Subject: Re: Game Learning Date: 1 Jul 1994 02:28:10 GMT Organization: NRaD, San Diego Lines: 140 Message-ID: <2uvuvq$bok@pandora.sdsu.edu> References: <1994Jun22.131623.1@otago.ac.nz> <1994Jun22.074127.19785@msuvx1.memphis.edu> <1994Jun28.035655.28183@Princeton.EDU> NNTP-Posting-Host: io.nosc.mil X-Newsreader: TIN [version 1.2 PL0] Devin Hosea (0428870@tucson.princeton.edu) wrote: : I am thinking about how to get a computer reasoner to play the game : Tic Tac Toe beginning with only the rules of the game and no pre-programmed : strategy. There are three ways to do this: : (1) A search algorithm -- TTT has a finite search space, which : can be represented by a 'tree'. The algorithm simply rejects : going down branches that might lead to a loss, and likes to go : down branches that lead to a win. Creating this 'tree' can be : done recursively, and after it's built, the computer can play : TTT with the best of them. (ha ha) : (2) A connectionist approach -- have the computer play an intelligent : opponent a million times, and use a neural net to 'learn' the best : move in a given situation. : (3) An explicit reasoning approach -- have the computer deduce : strategy, or even explicit moves (e.g. prove 'a move to space : 1 is the best possible move' from premises 'rules' and 'desire : to win'). : I am trying to take approach #3, as I believe the first two are brute : force attacks that do not resemble a human being's approach to the game : of Tic Tac Toe. I am using the reasoner OSCAR (developed by John Pollock : at the University of Arizona) as the 'inference-engine' for this game-playing : machine. : My question is: Is there any software out there, for any game, that uses : one of the three methods listed above? I know that some exists for chess : that roughly follows (1), and I am relatively uninterested in 1. I am also : aware of the myriad of software that has built-in strategy. I am looking : for examples of programs that give the computer ONLY the rules, and physical : constraints/environment, etc, but NO STRATEGY. Has anyone heard of stuff : like this? : Devin You might be interested in both Barney Pell's Ph.D. thesis, and my Ph.D. thesis. Here's the abstracts... Strategy Generation and Evaluation for Meta-Game Playing Barney Darryl Pell PhD Thesis, University Of Cambridge August, 1993 Abstract: Meta-Game Playing (METAGAME) is a new paradigm for research in game-playing in which we design programs to take in the rules of unknown games and play those games without human assistance. Strong performance in this new paradigm is evidence that the program, instead of its human designer, has performed the analysis of each specific game. SCL-METAGAME is a concrete METAGAME research problem based around the class of symmetric chess-like games. The class includes the games of chess, checkers, noughts and crosses, Chinese-chess, and Shogi. An implemented game generator produces new games in this class, some of which are objects of interest in their own right. METAGAMER is a program that plays SCL-METAGAME. The program takes as input the {\em rules} of a specific game and analyses those rules to construct for that game an efficient representation and an evaluation function, both for use with a generic search engine. The strategic analysis performed by the program relates a set of general knowledge sources to the details of the particular game. Among other properties, this analysis determines the relative value of the different pieces in a given game. Although METAGAMER does not learn from experience, the values resulting from its analysis are qualitatively similar to values used by experts on known games, and are sufficient to produce competitive performance the first time the program actually plays each game it is given. This appears to be the first program to have derived useful piece values directly from analysis of the rules of different games. Experiments show that the knowledge implemented in METAGAMER is useful on games unknown to its programmer in advance of the competition and make it seem likely that future programs which incorporate learning and more sophisticated active-analysis techniques will have a demonstrable competitive advantage on this new problem. When playing the known games of chess and checkers against humans and specialised programs, METAGAMER has derived from more general principles some strategies which are familiar to players of those games and which are hard-wired in many game-specific programs. Michael Gherrity University of California, San Diego November, 1993 ABSTRACT This dissertation describes a program which learns good strategies for a class of two-player board games. The program learns by simply playing the game against either a human or computer opponent. The results of the program learning the games of tic-tac-toe, connect-four, and chess are reported. Central to the performance of the program is the consistency search procedure. This is a game-independent generalization of the capture tree search used in most successful chess playing programs. It is based on the idea of using search to correct errors in evaluations of positions. This procedure is described, analyzed, tested using a monte carlo simulation, and implemented in the game-learning program. Both the monte carlo test results and the performance of the program confirm the results of the analysis which indicates that consistency search improves game playing performance for sufficiently accurate evaluation functions. The program uses a temporal difference procedure combined with a backpropagation neural network to learn good evaluation functions. The features used as inputs to the neural network are applicable to a wide class of two-player board games. The features represent the current board position, the move that led to the current board position, all the positions that could result after the opponent's next move, and all the positions that could result if the player who just moved could immediately move again. I think Barney's thesis is still available at ftp.cl.cam.ac.uk:users/bdp/thesis.ps.Z and mine is at io.nosc.mil/pub/gherrity/gherrity.thesis.ps.Z You can get code at these places too. mike --------------------------------------------------- Michael Gherrity | gherrity@nosc.mil NCCOSC RDTE DIV 4221 | (619) 553-4003 (office) 53140 Gatchell Road | 553-3939 (lab) San Diego, CA 92152-7463 |