[part 2] 3 Solved and Unsolved Problems in AI for Games Steve Woodcock keeps his finger on the pulse of current AI evolution. You can usually get some good leads on all things comp.ai.games by visiting his excellent site at: http://www.gameai.com He has a page about "solved" *games*. That means that computer AI has evaluated enough combinations to know whether a win is possible by moving first. Or second, or whatever. Just like in O's and X's, you know that "it's always a draw" with optimum play, it has been shown that, for example, Connect 4 is always a Win for the first player, again, with optimum play. Chess hasn't been solved... 3.1 What game AI problems have been solved well enough that I can build them into my next game? 3.1A Finding the shortest path from point A to point B. The A* Algorithm This is the best known, and most widely implemented Shortest Path Algorithm. The algorithm forms a star, and this is the shape of the potential paths spread out from point 'A'. Point 'B' will, at some point, be under the star shape as it spreads out looking for all paths from point A. Weighting is given to each discrete area covered by the search to find the best path. There are lots of shortest path algorithms (SPAs) around. There are some animations present on the internet. An good page is Smart Unit Navigation: http://www.lis.pitt.edu/~john/shorpath.htm Another, academically focussed page is http://home1.stofanet.dk/breese/aaai99.html A complete 3D RTS (Real Time Strategy) game which is using A* has been written by Keith Mukai. It can be downloaded and is described at : http://www.princeton.edu/~kdmukai/Seed/ Finally, there is much information on A* and variants at Amit's Game Programming site : http://theory.stanford.edu/~amitp/GameProgramming/ James Matthews has written a demo app with source code which can be found at http://www.generation5.org/ 3.1B Traversing a maze. Traversing a maze is a variant of the above. For our purposes here, ``traversing a maze'' involves moving from position to position toward an unknown but specific goal, with only partial knowledge of the maze. The effort to move from one position to another is usually constant. A monte carlo algorithm, randomly choosing a direction at each intersection, will in principle eventually solve any maze. And an infinite number of monkeys typing randomly will eventually recreate the works of Shakespeare. A brute force algorithm, such as following the left wall until you find the exit, will solve most mazes, but can be defeated by special maze design. A more sophisticated algorithm will remember that part of the maze which has already been travelled or seen, and will avoid aimless retravel of known segments. The algorithm should attempt to fill in blank spaces by directed searching. 3.1C Exhaustive search of sequences of a limited set of moves. (gametrees) known as Minimax [eg, chess] [Note that the practicality of building this into your game depends on the power of your processor, amount of memory, time constraints, number of possible moves at each step, and number of moves you wish to search.] Such games are often represented as minimax trees---we assume the first player is trying to maximize some payoff for himself, and the second player is trying to minimize the payoff to the first player. At the end of each sequence of tried moves, we assign a number (the payoff) to the reached position using an "evaluation function". >>>> [example here to follow] Alpha-beta pruning is a method that (usually) allows minimax trees twice as deep (i.e., move sequences twice as long) to be searched in the same time. Alpha-beta is described in almost any introductory AI text book. It is basically an optimisation of the evaluation function so that redundant nodes can be eliminated as soon as it is known, rather than evaluating all nodes and leaves before inspecting minimax style. 3.1D Database knowledge of information to apply Larger game AI developments, in particular chess, and backgammon, have libaries of 'openings' which huge historic and stored analysis has already been done to help find the best next move. A good online version of how a database mimics human intelligence can be found in a "Twenty Questions" on the Web called http://come.to/20Q and it's great fun! 3.2 What game-applicable AI problems have not been solved yet? The current best backgammon player, TD-Gammon, by Gerald Tesauro, was trained using temporal difference learning on a neural net (ref: March 1995 CACM) 3.3 What games have been "solved" First off, the following games have been solved by analysis and exhaustive searches, not by "artificial intelligence". However, they are included here so you won't put a lot of time into writing an AI program to beat someone at these games. (This isn't to discourage you from writing the games, just to advise you that AI, per se, won't be needed.) The meaning of "solved" is subject to some debate. In some games (e.g., Hex) we know who will win if the game is played perfectly (the "game theoretic value"), but not how to play perfectly. The following are games for which computer opponents are available that do achieve the game theoretic value. [ If anyone has code snippets or entire programs for these, or pointers to such, please drop me a line. ] Connect 4. First player wins. Gomoku (5 in a row) on a 15x15 board. First player wins. The game is solved both with and without overlines (six or more in a row) being counted as a win. 3-D Tic-Tac-Toe (3x3x3). First player wins. Qubic (4x4x4 three-dimensional tic-tac-toe). First player wins. Nine Men's Morris (also called Mill). The game is a draw. Awari. The general name of "Awari" covers a huge number of variants. Some of these have been solved analytically and some have not. Sprouts, for some numbers of points, anyway. Sorry, I don't have the figures on hand, but they were given in the original Scientific American article back in the '70's. I haven't heard of any further investigation. --------------------------------------------------------------------------- 4 What are some promising areas of research in AI, as applied to games? Case-Based Reasoning (CBR), sometimes (not necessarily correctly) known as knowledge-based systems or expert systems. Neural Nets. Steve Woodcock's Round Table discussions at the Gamedev meet have sometimes touched on this. Many programmers quote it as the next great thing to implement, but few have actually succeeded. The problem is one of complexity and practicality. Fuzzy Logic. Monitoring and adapting to the opponent's style of play. A number of rules which can be adapted, graded, modified and measured are an excellent way of computer learning. --------------------------------------------------------------------------- 5 Fact Sheets and descriptions of Gaming AI projects Projects come and go, but some of the latest ones can be found at http://dir.yahoo.com/Recreation/Games/Computer_Games/Programming/Projects/ A subject much in discussion during the latter half of 1999 was the 'Rock, Scissors, Paper' or 'RoShamBo' competition, along with the whole of the rec.games.poker newsgroup. The competition has now completed, but the discussion goes on. Find out more about it at http://www.cs.ualberta.ca/~darse/rsbpc.html and play a bot at http://www.sportsrocket.com/cgi-bin/roshambo/roshambot.cgi --------------------------------------------------------------------------- 6 Summaries of useful c.a.g threads This note is here because we can refer to Steve's pages again. He has these threads archived, not summarized : http://www.gameai.com --------------------------------------------------------------------------- 7 Game AI in the larger world 7.1 Where can I find information on XXX game programming? This section lists game-specific links which serve as good starting points for those interested in resources and approaches for programming game AI in each specific game. Please email the maintainer with new links for other games, or better links if you can find them. 7.1.1 Chess A good, but not recently updated guide, is at http://www.xs4all.nl/~verhelst/chess/programming.html 7.1.2 GO A good opening for AI discussion of GO is at: http://www.usgo.org/computer/ 7.1.3 Backgammon A fine starting point for Backgammon, including a discussion of the various AI programs available and their capabilities : http://www.statslab.cam.ac.uk/~sret1/backgammon/ 7.1.4 Othello / Reversi There doesn't appear to be a specific programming page around, but a good starting point would be http://www.iioa.org 7.1.5 Checkers / Draughts Again, no specific programming AI page, but this is a good place to start : http://www.mcn.net/~jimloy/checkers.html 7.1.6 3D shootemups AI Bots, programming of both server and client, can be found at http://www.planetquake.com/botshop and many more at http://www.botepidemic.com/ 7.1.7 Other game AI links The list below will give you many hours AI surfing : http://www.gameai.com/ai.html http://www.gamedev.net http://www.gamasutra.com http://www.programmersheaven.com Grant Castillou has put together some downloads which cover Gomoku, Checkers and Othello. You can get them at: http://skyscraper.fortunecity.com/apple/230/ This section (7.1) needs additional resources for AI in card games, board games, driving games, fighting/arcade and AI for other computer hosted / simulated games. Let me know if you have any. 7.2 Who is sponsoring research into AI in games? Lots of people. Professional game developers can either just want to get the game out the door or can be dedicated to the AI. Whether they get their code included or not! University research projects are usually focused on the techniques used instead of the domain. 7.3 How can I get a job or an assistanceship writing games? Learn C or C++. Buy a book on games. Write a simple game. Write a more complicated game that's enjoyable to play. Send the demo to a company which wants talented, useful game programmers. You could offer to work for free, of course, if the bank balance allows, and you're confident enough. Further details of the game industry from the developer viewpoint can be found at http://www.godgames.com especially, check out 'The Oracle' where pretty much every aspect of the game developer's questions are asked (and answered). 7.4 What commercial games use AI? Pretty much all of them. You will see people complaining in the related games newsgroups about poor AI if it hasn't been implemented coherently. 7.5 What commercial games advertise AI but don't really use it? This is getting into the definition of AI. 7.6 Are there any AI competitions? The Loebner Prize, based on a fund of over $100,000 established by New York businessman Hugh G. Loebner, is awarded annually for the computer program that best emulates natural human behavior. During the contest, a panel of independent judges attempts to determine whether the responses on a computer terminal are being produced by a computer or a person, along the lines of the Turing Test. The designers of the best program each year win a cash award and a medal. If a program passes the test in all its particulars, then the entire fund will be paid to the program's designer and the fund abolished. For further information about the Loebner Prize, write Dr. Robert Epstein, Executive Director, Cambridge Center for Behavioral Studies, 11 Waterhouse Street, Cambridge, MA 02138, or call 617-491-9020. The International Computer Chess Association presents an annual prize for the best computer-generated annotation of a chess game. The output should be reminiscent of that appearing in newspaper chess columns, and will be judged on both the correctness and depth of the variations and also on the quality of the program's written output. The deadline is December 31, 1994. For more information, write to Tony Marsland, ICCA President, Computing Science Department, University of Alberta, Edmonton, Canada T6G 2H1, call 403-492-3971, or fax 403-492-1071. --------------------------------------------------------------------------- 8 Further information 8.1 What are some related news groups? The entire comp.ai.* hierarchy. Particular topics people seem interested in include comp.ai.fuzzy, comp.ai.genetic, and comp.ai.neural-net. The rec.games.* and alt.games.* hierarchies. The comp.ai FAQ in particular has an enormous fund of information. I plan to incorporate as much of it as I can without being accused of plagiarism, but for now, just look it over. This FAQ has a long list of reference books and articles covering topics of interest to AI gamers. http://www.cs.uu.nl/wais/html/na-dir/ai-faq/general/.html 8.2 Where can I go to FTP text and binaries? Some info can be found in x2ftp.oulu.fi:/pub/msdos/programming/ directory.. Please note that the "msdos" part in path does NOT mean everything is dos related x2ftp.oulu.fi:/pub/books/game/ 3d-books.320 3D graphics books reviewed by Brian Hook - 3.20 aaa_set.toc Action Arcade Adventure Set - Diana Gruber 1994 (FastGraph) cgames_1.txt Computer Games I - Levy 1988 cgames_2.txt Computer Games II - Levy 1988 explorer.toc PC Game Programming Explorer - Dave Roberts 1994 playgod.zip Playing God, Creating Virtual Worlds - Roehl 1994 (TOC/errata) tricks.rev Tricks of the Game Programming Gurus - LaMothe/Ratcliff 1994 tricks.toc Tricks of the Game Programming Gurus - LaMothe/Ratcliff 1994 x2ftp.oulu.fi:/pub/msdos/programming/ai/ x2ftp.oulu.fi:/pub/msdos/programming/theory/ Especially the latter directory has some excellent documents. BOLO : the 'official' archive seems to be down. I suggest starting at the home page, but the development seems to have died. http://www.lgm.com/bolo/ 8.3 What books and magazines are available on AI and gaming topics? _Neural Networks and Fuzzy Logic Applications in C/C++_, Stephen T. Welstead, Wiley Professional Computing, 1994. Discusses the topics and gives library and application source code for Borland C++. Another resource is Sunir Shah's "Programmers' Booklist," a list of, you got it, books (plus magazines, e-mags, web sites, and files) of interest to the programmer. This list is indexed hypertext. The web site is at http://www.intranet.ca/~sshah/booklist.html There is a "binary searchable" version at: http://www.intranet.ca/~sshah/booklist This list is a very comprehensive and inclusive one. --------------------------------------------------------------------------- 10 Glossary Case-based Reasoning: Technique whereby "cases" similar to the current problem are retrieved and their "solutions" modified to work on the current problem. Fuzzy Logic: In Fuzzy Logic, truth values are real values in the closed interval [0..1]. The definitions of the boolean operators are extended to fit this continuous domain. By avoiding discrete truth-values, Fuzzy Logic avoids some of the problems inherent in either-or judgments and yields natural interpretations of utterances like "very hot". Fuzzy Logic has applications in control theory. SPA: Shortest Path Algorithm. --------------------------------------------------------------------------- 11 Acknowledgements [Dave Burbage's] My thanks to: Sunir Shah - for handing me the FAQ. Bjorn Reese - for not bullying me too much in getting this version out at all! [Sunir Shah's] My thanks to: David Burbage for taking over the FAQ. Steve Furlong Doug Walker for conferring the copyrighted on me. Robert Uhl Lukas Bradley for HTMLizing the FAQ. Steven Woodcock for putting up http://www.gameai.com Everyone else for putting up with me. [Steve Furlong's] My thanks to: Dan Thies for the charter, and for creating this group Doug Walker, the original FAQ maintainer Mark Kantrowitz, maintainer of the comp.ai FAQ Jouni Miettunen Paul Colley Frits Daalmans Robert Uhl Mitchel Timin Jessie Montrose Will Uther Timothy Huang and everyone else that submitted questions or answers or pointers to answers [document ends]