Table of Contents
EGGG: The Extensible Graphical Game Generator
Thesis Committee
Table of Contents
Preface
About This Dissertation
Acknowledgments
Chapter 1: Introduction
What's In A Computer Game?
Decoupling Hard from Soft
The Tradeoff
Circumventing the Tradeoff: Patching and Burrowing
Games As A Domain For Automated Program Generation
Design Principles: Languages, Overengineering, and Brevity
What This Dissertation Is And Is Not
Related Systems
The Programmer's Apprentice
METAGAME
Commercial Products
GURPS
Klik & Play
Related Fields
Game Theory
Complexity Theory and Game Automata
Condon's Probabilistic Game Automaton
The Eight Games
Chapter 2: Anatomy of a Game
A Structural Categorization Of Video Games
A Designer's Taxonomy of Games
Frenetics
History
The Six Types Of Synchrony
Movement
The Move
The Phase
The Turn
The Round
The Step
Tangibles
The Board
The Grid
The Graph
The Canvas
Topology
Board Summary
The Piece
More About Color
Compartments
The Hand
The Bag
Abstract Facets of Play
The Genre
Information
Referees
Endings
Chapter 3: The Physiology of EGGG
Game Descriptions
How Does EGGG Know That Poker Is A Game Of Rounds?
How Can EGGG Assume That The Cards Are In Descending Order?
How Did EGGG Know To Generate All Those Buttons?
A New Game: Deducto
Board Initialization
Functions
Assertions
Variations
A Sample Variation: Color Deducto
Software Architecture
Why Perl?
Running EGGG
The Parser
Ambiguity in the EGGG language
Interactive Parsing
The Engine
The Game
The State
Modules
Sorting
Timing
Documentation
Documenting The Program
Documenting The Game
Naming
Abbreviations
Error Recovery
Chapter 4: Enemy of the Game State (Computer Opponents)
A Generic Minimax Procedure
A Generic Static Evaluator
Estimating Piece Power
Estimating Piece Motility
Estimating Piece Rank
Estimating Piece Rarity
Estimating Piece Expected Value
Competition versus Cooperation
Common Strategies
Analyzing Strategies With Hidden Markov Models
Rock Paper Scissors
Nothing Beats Rock
Randomness
Switcheroo
Generalized Tit For Tat: The Vendetta
Sacrifice
Synthesizing Strategies
Freedom As A Universal Strategy
You Cut, I'll Choose
Hypotheses
Estimating Player Ability
Bluffing
Making Interesting Moves
Probabilistic Bluffing
Garnering Trust
Chapter 5: Beauty on the Inside (Graphic Layout)
The Frame
The Window
The Menu Bar
The File Menu
The Preferences Menu
The Help Menu
The Status Line
The Message Field
Play Again
The Score Field
The Board
The Geometry Manager: Packing, Placing, and Gridding
Board Shape
Squares
Checkerings
The Pieces
Color
Get Your Game Face On
Chapter 6: Connect the Bots (Networking)
The Henhouse, And Stateless Connections
Mail Generation
Global History and Adaptive Learning
Multiplayer Networked Games, And Stateful Connections
A Sample Networked Game: Mammon
Chapter 7: Conclusion
What We've Learned
Abstraction Revisited
Similarities Revisited
Similarities of Structure
Similarities of Strategy
Similarities of Appearance
Complexity
Tips for Game Designers
Computer Opponents Should Act Smarter Than They Are
Make Mistakes
Include Easter EGGGs
Measuring Playability
Empirical Evidence Of Playability
Why There Can Be No Good Measure Of Playability
Making Work Into Play
Lessons Learned
What To Do Next
Text Adventures
Speed
How About Some Real Graphics?
What About Sound?
Other Domains
Scriptability and Glass Boxes
Open Source Games
Bibliography
Appendix A: EGGG Installation Instructions
Appendix B: Sample EGGG Games
Rock Paper Scissors
Tic Tac Toe
Poker
Crossword
Deducto
Tetris
Chess
Appendix C: The EGGG Grammar
Colophon
Biographical Note
Preface
About This Dissertation
This dissertation is part of an ongoing project called EGGG, the Extensible Graphical Game Generator. As its name suggests, EGGG is a system that creates computer games, and the thesis behind the dissertation is that there exist sufficient commonalities between games that such a software system can be constructed.In plain English, the thesis is that games are really a lot more alike than most people imagine, and that these similarities can be used to create a generic game engine: you tell it the rules of your game, and the engine renders it into an actual computer game that everyone can play. You can play with EGGG if you want; details are given in Appendices A and B.
In the Introduction, I talk about what drove me to create EGGG, and how my work differs from what others have done.
Anatomy of a Game discusses the common components of games that made this dissertation possible.
In the Physiology of EGGG, I explain the design of the EGGG parser and engine. I also describe the user experience of creating EGGG games: what novices have to know about programming, and what they don't.
Enemy of the Game State explores how EGGG builds computer opponents that can play games designed by users -- including how they can bet and bluff.
Beauty on the Inside: Graphic Layout explains how EGGG generates the graphical elements of computer games.
Connect the Bots: Networking examines the networking components that EGGG uses to link computer games together.
Conclusion and Analysis concludes the dissertation and suggests future research directions.
The Bibliography lists relevant sources for games, computer gaming, game variations, and game creation.
Appendix A: EGGG Installation Instructions describes how to install and use EGGG.
Appendix B: Sample EGGG Games contains some EGGG files for some popular games to demonstrate EGGG rulesets.
Appendix C: The EGGG Grammar contains a Backus-Naur specification of the EGGG language.
Acknowledgments
I've spent a substantial portion of my life at the MIT Media Laboratory, and above all, I would like to thank Walter Bender for the environment he's somehow managed to maintain during all of that time. I defected from the MIT AI Lab in 1988 because Walter gave me the chance to hack image processing on the Connection Machine, and soon became enthralled by the freedom and intellectual camaraderie of the Terminal Garden and now the Cube. Since then, I've worked on news, user modeling, a multitude of other projects, and finally games, the subject of this dissertation. Walter combines a love of ambitious ideas with a laid-back attitude -- an unusual combination, and I cannot imagine a better advisor.Thanks to the other members of my thesis committee, Mitchel Resnick and Murray Campbell, for their helpful insights and suggestions.
Thanks to my friends who contributed, knowingly or not, to some of the ideas in this dissertation: Sandy Aronson, Alan Blount, Amy Bruckman, Richard Christie, Diego Garcia, Carolyn Grantham, Kyle Pope, Kimberly Scearce, and Sekhar Tatikonda.
I'd like to thank the many members of the Perl community that have provided me with innumerable distractions during my Ph.D.: David Blank-Edelman, Tom Christiansen, Mark-Jason Dominus, Jarkko Hietaniemi, Tuomas J. Lukka, John Macdonald, Linda Mui, Chris Nandor, Andy Oram, Tim O'Reilly, Madeline Schnapp, Mike Stok, Nathan Torkington, and Larry Wall. In particular, Nathan Torkington and Tom Christiansen were a continual source of intellectual amusement. Thanks to the officemates who've put up with my folding bike and my ten pounds of silly putty: Judith Donath, Doug Koen, and Marko Turpeinen. Other members of the Media Lab provided camaraderie, inspiration, and help: Nathan Abramson, Bill Butera, Pascal Chesnais, Klee Dienes, Scott Fullam, Dan Gruhl, Roger Kermode, Jill Kliger, Hakon Lie, Michelle McDonald, Chris Metcalfe, Warren Sack, Laura Teodosio, Sunil Vemuri, and Chris Verplaetse. Thanks to Nicholas Negroponte for creating the Media Lab, and to Felice Gardner and Linda Peterson for making it function so smoothly.
Finally, thanks to Robin Lucas, and to my parents, Jack and Carol.
Chapter 1: Introduction
I think the thing I take the most pride in about Spacewar is that it got so many people hooked on computer programming. It caught a lot of eyes and got a lot of interesting people asking, "How do you do that?"
Steve Russell, author of Spacewar, the first video game.
There are obviously similarities between games. Are those similarities sufficiently numerous and deep that a system can be constructed which turns a written description of a game into a playable program? This dissertation is an attempt to answer that question in the affirmative. In support of this thesis, a system that translates the rules of a game into a program was built: EGGG, the Extensible Graphical Game Generator.
In this chapter, I'll describe what motivated me to create such a system, and survey related work. First, we'll look at the breadth of computer games that exist today.
What's In A Computer Game?
Frenetic shoot-em-up games like Doom and Quake sell millions of copies and tax the abilities of today's most powerful personal computers. Considerably less demanding games like the ubiquitous Windows Solitaire occupy thousands of hours of idle (and not-so-idle) time; Napoleon played the old-fashion version while in exile on Elba. Supercomputers like IBM's Deep Blue defeat the world's greatest human chess player. Internet users circumvent U.S. gambling laws by wagering in Antigua.Each of these four experiences is considered "computer gaming", even though they differ in who plays them, and why, and how. Games like Doom are graphic-intensive, often violent, and players move from location to location in a virtual world. (In spite of what some detractors say, some of these games have challenging puzzles and intricate narratives.) The various Windows Solitaire games are played with picture-for-picture identical 52-card decks. The heart of Deep Blue is the same as every other chess-playing program: a minimax engine coupled with a static evaluator and a library of opening moves. Gambling games, whether online or off, involve unpredictable outcomes.
In an attempting to categorize computer games, we could treat each of these four scenarios as representative of an entire genre of games:
Is this a good categorization? No; many games are missing. Where's tic tac toe, or Tetris? Here's another categorization:
This is still not up to snuff. Some of these categories overlap: is poker a card game or a gambling game? And who cares about a taxonomy of games, anyway?
- Games requiring hand-eye coordination
- Card games
- Games played on a grid
- Gambling games
Programmers do. Once you arrive at a comprehensive categorization of games, you can begin to make the leap from merely categorizing games to drawing inferences about them -- and ultimately, to helping people create them. Here's an elaboration of those categories:
Now we're getting somewhere. This categorization is still quite unclean -- the first category has to do with process, the middle two with structure, and the final category with function -- but it serves to illustrate what I'm talking about when I say that there are similarities between games. These similarities are all obvious, but in Anatomy of a Game (Chapter 2) we'll develop a more comprehensive taxonomy of games, arriving at some far less obvious (but just as useful) observations. For the remainder of this chapter, let's just assume that such a taxonomy exists.
- Games requiring hand-eye coordination ...have a main loop and need callbacks
- Card games ...use the same images and share some actions, like shuffling.
- Games played on a grid ...need a two-dimensional array to contain the game state.
- Gambling games ...require security and a "Money" abstraction.
Decoupling Hard from Soft
Before the Atari 2600 debuted in 1978 (and its obscure predecessor, the Fairchild Channel F in 1976), videogames were embedded in chips inside chunks of wires and plastic called game consoles. When you tired of whatever games were burned onto the chip, you stopped using the system entirely.The 2600 (also called the "Atari VCS") revolutionized the game industry because of cartridges -- no longer were chunks of plastic and wires only able to play a fixed set of games. When you got tired of a cartridge, you'd just buy a new one, for a fraction of the console price.
This decoupling of hardware and software was made possible by simpler and more flexible hardware components. The decoupling is what made home video game systems a commercial success, because someone plunking down two hundred dollars wouldn't be restricted to a small fixed number of games. He knew that as long as tens of thousands of fellow gamers had consoles just like his, that new games would be developed for it.
So what's the next step? We can take the decoupling further, thanks to simpler and more flexible software components. Instead of decoupling hardware from software, what we can do is decouple a game's implementation (the "hard software") from the rules of play (the "soft software"). This is what EGGG does, and it does it by incorporating assumptions about game play into a program that translates the rules of play into a fully-functioning game.
The Tradeoff
Programming is hard. But programming for a particular domain needn't be -- when you can build assumptions about the domain into the language. And more to the point, those assumptions can be built into whatever system (compiler, translator, interpreter, or combination of all three) that ultimately turns the program into something you can run.Let's say your domain is widgets. If you know your clientele will be designing widgets, you could create a software package called a Widget Designer that lets them specify a recipe for building their widget. The recipe can be viewed as a program, and the Widget Designer is a translator that transforms the program into something more complex.
Designing a widget might not seem like programming for two reasons. First, the Widget Designer might be easy to use, and people are unfortunately conditioned to think that programming has to be difficult. Second, the range of behaviors permitted by the Widget Designer will be severely limited: you won't be running spreadsheets or calculating differential equations with it. You just design widgets. There's a tradeoff between expressivity and convenience; the Widget Designer chooses convenience.
Another example: drawing pictures on a screen used to be hard. In the old days, graphics libraries gave you ways of drawing points and lines and circles, and not much more. Creating usable applications with buttons and pictures and scrollbars was tough -- but you had enough low-level control over what the electron gun shot to the CRT that you could do anything. You could be expressive, but it wasn't very convenient. Later, graphics toolkits took away the drudgery, but they also took away some of the low-level control. Applications were developed faster, but they all had a certain similarities of appearance. In Xlib, you could do anything. In Motif, you can do almost anything, and people would look at the result and say, "Oh, you must have used Motif." The same is true of other visual programming environments, like Visual Basic and NeXTSTEP's Interface Builder.
You can see the same phenomenon with HTML. People used to speak about "HTML programming", but that phrase is becoming more and more rare as programs like ColdFusion are used to generate HTML automatically. You don't hear people saying "Oh, you must have used ColdFusion" when they see those web pages, but that's only because web browsers affect how web pages appear.
Every system that helps you build things has to make a tradeoff between the variety of things it lets you build, and the ease with which you can build them. EGGG is an attempt to help people create programs, but it is not a generic programming assistant like the Programmer's Apprentice, described later. Nor is it a visual development environment that lets people drag and drop elements into place, which would permit only a small variety of games.
Circumventing the Tradeoff: Patching and Burrowing
NeXTSTEP's Interface Builder lets you construct applications by dragging and dropping components (buttons, frames, text boxes, and the like), and by establishing links between them. As you would expect, the applications you construct all have the same look and feel; there's only so much customization you can do. But under the hood, what the Interface Builder does is generate Objective C code. Programmers who want to specify the behavior of the component do so in code. The look and feel is still constrained, but the system lets you patch the generic output by writing your own code.Other systems let you burrow down into internals. For instance, languages like Perl and some versions of LISP let you implement chunks of code in another lower-level language when speed is paramount. Browsers like Netscape, web servers like Apache, and paint programs like the GIMP and PhotoShop provide hooks so that developers can write code for features not provided by the prepackaged application.
EGGG lets you both patch and burrow. Details are provided in Chapter 3, the Physiology of EGGG.
Games As A Domain For Automated Program Generation
What is the right size domain for creating an automated program generator? If the domain is too broad, the assistant won't be able to help much, because it won't be able to infer the intentions of the would-be programmers. If the domain is too narrow, the assistant won't be necessary. No one needs help creating calculator programs, because there aren't that many different programs to create.Games have several advantages as a domain:
So how can users communicate their intentions to EGGG? They do so by codifying the rules of their game in a pseudo-English language. We call this the EGGG language, and turn to it in the next section.
- Games have the right amount of diversity. The similarities between games like chess and tic tac toe are obvious; the similarities between poker and chess and Tetris, less so. By building a system that can create all of those games, we support to our thesis that the similarities between games are broadly applicable and useful to an automated program generator.
- There are many game programs. This allows us to identify common techniques in their design, and exploit those techniques in the design of EGGG.
- Many games can be easily represented with a small set of rules. It is possible to create systems that generate stories, or financial applications, or music -- but the systems would require much more input from the user.
- A game generator needn't be perfect. Because games are so popular, they'll still be used even if they lack the polish and speed that only dedicated programmers can provide.
- Games benefit from large populations of users. One way to improve a system as large and sprawling as EGGG is to release it and see whether (or how) people use it. Furthermore, games appeal to novices and experts alike, so a system that solicits feedback from users will benefit. Novice programmers will have different comments and suggestions about the system than experts, and EGGG can use feedback from both camps. This feedback won't be evidence for or against the thesis, but it will help make EGGG more useful and fun for everyone.
Design Principles: Languages, Overengineering, and Brevity
It's an uncertain world out there, and classically trained programmers know this. They know to design for scalability: if your program operates on a thousand pieces of data today, it might be called upon to manipulate a million pieces of data next year. And designers decide that since they can't know what protocols or standards or data formats will be around in a year, they create abstractions for those protocols and standards and data formats.The unfortunate result is that many designers overdesign, abstracting out components too much, and in so doing slow down their programs (that's bad) and make them harder for others to understand (that's worse). The abstractions that seem so clear to a designer are opaque to the next person who has to use the program. When designers assume that their users share their tenacity and attention to detail, the result is bad software.
But this is the wrong approach. The right approach is to be able to program quickly, so when that new protocol arrives, you can throw away your old code and begin anew. The right approach is to create lots of tiny tools that do one thing well, so you can combine them in whatever pipeline you need.
Consider the Berkeley socket library used for networking computers together. The library doesn't do very much: it just creates a connection between two computers on the Internet, or between two processes on the same Unix system. Yet because the designers wanted a uniform interface to both, they ended up with a system that requires you to specify which connection you want. Some of the arguments you have to provide make no sense if you're connecting two computers, and others make no sense if you're connecting two processes. Nowadays Berkeley sockets are used almost exclusively for Internet connections, because there are better ways to communicate between processes on the same computer, like SysV IPC and threads.
What is the right level of abstraction for games? As with the Berkeley socket library, there's a danger here. Abstractions are all well and good, but designers shouldn't force users to cope with their particular organization of the world unless it's intuitive. EGGG disguises its abstractions behind terms with common usages, providing a simple language through which game designers can communicate their intentions to the system.
So "EGGG the engine" and "EGGG the dissertation" include "EGGG the language": a high level language that lets users describe games in as few words as possible while still retaining the precision that the EGGG engine needs to render the language. The language is expressive (you can create nearly any kind of graphical two-dimensional game) and and concise (statements are short and powerful, so that debugging is easy).
The importance of brevity shouldn't be underestimated. It's good to be able to see all of the game on a single page -- you never have to visit different files, or even scroll up and down. For instance, here's how one tells EGGG that players alternate turns in chess:
turns alternateHere's how one stipulates that the deal moves clockwise in poker:
deal moves clockwiseEvery attempt was made to mimic language that people would normally use to describe games. That's not always possible, of course, and there is a particular danger involved with systems that accept natural language as input: users tend to assume that the parser is much more sophisticated than it actually is [Brennan 90]. Here's the description of a stalemate in chess:
Stalemate means turn(P) and no moves(P) => tieThis can be read as "A stalemate is a situation where it's P's turn and he doesn't have any moves. If that happens, the result is a tie." This single statement triggers EGGG to do a number of tasks:
These game descriptions are stored in single files. The description is very concise: the rules of poker require 19 lines, and even chess requires only 81 lines. The ordering of the lines within the file is immaterial.
- Create a subroutine called Stalemate. When EGGG encounters
Stalemate means, it sees thatStalemateis capitalized. Lowercased words have special meaning to EGGG; uppercased words are terms that have a per-game or per-rule meaning.
- Execute the subroutine at appropriate times. Because the subroutine mentions a turn, it will be executed at the beginning of each turn. Checkmate is checked for at the end of each turn; that's why the Stalemate definition needn't verify that the player isn't in check. If the game designer preferred precision to brevity, the rule could have been written this way:
Stalemate means turn(P) and no moves(P) and not Attacking(Q, King) => tie
- Have the subroutine set a variable, P, to whoever's move it is. Different single letters mean different things.
Palways means a player, and because it's capitalized, it means a particular player. Had it beenpinstead, EGGG would have generated a loop that cycled through all players. Of course, in chess there are only two players, but in a game like poker, the rule we saw earlier,deal moves clockwisewould indicate how the loop would proceed.
- Have the subroutine check to see if P has any available moves. EGGG will already have generated a subroutine that enumerates all of the moves available for each player.
no moves(P)causes that subroutine to be invoked, and immediately returns zero if any moves are found.
- If there are no available moves, invoke the tie() subroutine. EGGG will already have created a
tie()subroutine on a previous pass through the game description; any mention of "tie" triggers that behavior. If the subroutine gets to this point, it must be playerP's turn, he must have no available moves, and he must not be in check, so a stalemate occurs and the game is tied.
There is plenty more to the EGGG language than what is shown here, and we'll see more examples throughout this document. The EGGG language strives to approach the brevity and simplicity of human writing.
When there is ambiguity in the language (in poker, "draw" means to receive cards and "rank" means the strength of a hand, while in chess, "draw" means to tie the game and "rank" means the y-coordinate) EGGG makes its best guess. If it's really stumped, it queries the user.
It is assumed that most users will create their own games by copying game description files from EGGG's central repository and modifying them. As one would expect, variations on traditional games are easier to create than entirely new games.
The design criteria for the EGGG language and engine are the following, in approximately decreasing order of importance:
- Game descriptions should be brief.
- Easy games should be easy to generate, and hard games should be possible to generate.
- The EGGG engine should contain as little a priori information about particular games as possible.
- It should be easy to create variations.
- The EGGG engine and the games that it generates should be maximally portable.
- The games generated by EGGG should be easy to modify.
- EGGG shouldn't take a long time to generate games, and the games that it does generate shouldn't run so slowly that playability is affected.
What This Dissertation Is And Is Not
EGGG is not about the "who" or the "why" of games, only about the "what" and "how". It is an exploration of the similarities between traditional games like board games and card games, and how those games are realized in computer programs. The thesis underlying the dissertation is that those similarities are sweeping enough that it is possible to construct a system that generates a computer game from its distilled essence: the rules of play.This dissertation is not about children, society, gender, culture, education, or any particular community of game players. While there are many interesting research topics in these areas, EGGG's focus is on the similarities between games and the resulting implications for the mechanics of computer game creation. This dissertation offers no opinion about what sort of games should be created, nor about the effects of any game -- good or bad -- on the people who play them. However, we do note that Monopoly sends a rather brutal message to would-be industrialists, and no game generated by EGGG can be as dangerous as the fluoroscopes found in the earliest penny arcades, where medically uninformed amusement seekers paid for the ability to X-ray the bones in their hand.
The games that EGGG creates are those that lend themselves to concise descriptions: the simpler the game, the better. It is best-suited for creating games involving pieces and boards and cards and icons, and not well-suited at all for games like Mortal Kombat, or Doom, or sports simulations. The graphical sheen of games like Mortal Kombat and Doom is intrinsic to their appeal, and EGGG can't supply artistry. Sports simulations might not require so much polish (although the successful ones certainly do), but the sheer number of rules involved in any sport makes it difficult to write the description in such a way that EGGG could know how to render it. If you're creating a baseball game, you can't just tell EGGG to create bases. You have to tell it how far apart to make the bases, and the pitcher's mound, and the outfield wall. You'd have to describe -- algorithmically -- the paths of the different types of pitches. You'd have to express the speeds of the pitches, and maybe even of the runners and the bat. And so on. It is impossible to describe baseball concisely to EGGG, because it is impossible to describe baseball concisely.
Theoretically, EGGG could create any game, since you can always burrow down into the underlying Perl programming language. However, in this dissertation we will restrict ourselves to games that are graphical, but not graphics-intensive or overly complex.
One could argue that these are the best games to study because they are the most timeless: card and dice and board games have been around for centuries, so they best epitomize gameness. I don't agree with this; while arcade games have eclipsed "classic" games, it's unclear whether this is because of changing tastes of youth exposed to incessant marketing or because those games really are more fun to play. It's quite possible that if the ancient Romans had had Nintendo, the empire would have collapsed a lot sooner. I make no claims about the superiority of some games over others, nor do I claim that game play is an intrinsic part of intellectual life. Gaming is less universal than many suspect; despite the best efforts of anthropologists, no one has been able to stake a claim for the universality of games across cultures [Avedon 71].
However, game play is nearly universal among computer scientists, and in the next section we turn to other systems pertaining to computer game creation and automated programming assistance.
Related Systems
The Programmer's Apprentice
Before I came to the MIT Media Laboratory, I worked at the MIT Artificial Intelligence Laboratory on the Programmer's Apprentice, an automated programming effort headed by Charles Rich and Richard Waters. The Programmer's Apprentice project yielded a series of intelligent assistants for software engineers: programs that helped programmers formalize requirements, create and edit programs, and analyze the programs they created.EGGG differs from the Programmer's Apprentice in that its goal is simultaneously both more and less ambitious. EGGG is more ambitious in the sense that it is an attempt to create something that people with a minimum of programming skill can use: its target audience is not programmers, but people who want to create computer games -- people who may not have much (or any) programming experience. EGGG is less ambitious in that it drastically constrains what type of systems you can create. EGGG does not do requirements analysis or program verification; it simply generates games.
METAGAME
METAGAME [Pell 92] is similar in spirit to EGGG, but arose from a different premise. For a long time, chess was considered a formidable problem for AI. The reasoning was that any program that could beat an expert player, or even a competent one, would surely possess some of the intellectual capacity of a human. Yet Deep Blue and other successful chess programs demonstrate that this is not necessarily the case: chess programs have gotten better largely through improvements in computer power and in hardwiring knowledge of chess into the architecture. Put another way, chess is not AI-complete: just because a program is an intelligent chess player doesn't mean that it's intelligent.Barney Pell's METAGAME strives to bring the AI back to computer game playing. He suggests that the test of a computer's game-playing prowess shouldn't be chess, or even Go, but the ability to play a game with no a priori knowledge. To this end, Pell develops a formalism for representing "Symmetric Chess-Like" (SCL) games, including a proof that all finite two-player games of perfect information (that is, games that can be represented as game trees) can be represented using his formalism. A computer program that can play aribtrary SCL games is called a metagame player.
Pell goes on to develop an evaluation mechanism for metagame players and a program that generates games that are similar to chess, but with random rules. He then tests his METAGAMER program against several such games and reports the results.
METAGAME is a mathematical framework for developing programs that can play games well, in contrast to EGGG, which is a system for developing games. Nevertheless, METAGAME has influenced the design of EGGG in a few ways. In particular, EGGG uses logical predicates that represent changes in the state of game play, cf. [Pell 1993], p. 104:
In addition, these predicates are all logical, in that state is represented as a relation between two variables,
StateInandStateOut, instead of a global structure which is changed by side-effects (as in a current board array used in many traditional playing programs). This enables a program to use the predicates in the domain theory in both directions. For example, by constrainingSOutin Figure 12.2 instead ofSIn, a program can determine possible predecessor states, thus using the rules "in reverse" to find all the positions which would have been legal before a given move.
EGGG has global structures that are changed by side effects, but it also has "actions" that are passed around, composed, concatenated, and hypothesized about, just like METAGAME.
Commercial Products
There have been several commercial "game construction kits", but they are typically not very expressive: the range of the games you can generate is quite limited. Bally's Pinball Construction Kit, for instance, let you adjust the number and placement of flippers, and it let you change gravity, but at the end of the day all you could create were slightly different variations on the same pinball game. Many game constructions kits are like this.In this section, we will briefly discuss two commercial products that have broader approaches to game construction: GURPS and Klik & Play.
GURPS
Steve Jackson's GURPS (Generalized Universal Role Playing System) is an ambitious attempt to generalize role-playing games into a single set of all-encompassing rules. It focuses on dice-and-paper simulations and therefore is only tangentially related to computer games, but faces the same problem EGGG does: how do you partition the universe of games, and what are the proper levels of abstraction? For instance, GURPS has a single unifying architecture for all combat, but overrides that architecture when certain conditions occur (for instance, when the combatants are in water). Parallels exist for EGGG: it makes guesses about games and then overrides those guesses as more specific rules are found.GURPS is a reference manual; it is essentially a compendium of information to help you create your own simulation. It does not create the simulation for you, nor can it supply the creativity that every successful role-playing game requires. (EGGG can't supply the creativity either, of course.)
Nevertheless, GURPS is an ambitious work, and it is a philosophical ancestor of EGGG. Reading it, you can sense Steve Jackson's frustration as an avid scenario designer who recognized the similarities between the different milieus: protecting your body with chain mail against an arrow is not unlike protecting your body with a Kevlar vest against a bullet. In each case you have to establish probabilities that the target will be able to dodge the projectile (the bulkier the protection, the slower the target can react), the probability that the projectile will penetrate the target (which depends on the speed and force of the projectile), and the probability that the wounds caused will be fatal. That, in turn, depends on the health of the target, and so on. Nor is GURPS entirely about combat; it provides guidelines for a scenarios as obscure as loading cargo onto an aircraft without the aircraft having to land.
Implicit in GURPS's design are decisions about when to generalize (social traits that are universal, and combat rules that apply to all milieus) and when not to (a character's skill at xenology -- the knowledge of alien races -- which is unique to space-age milieus). However, GURPS' generalizations are all obvious: you can fight in any game, but laser weapons have no place in Westerns.
Klik & Play
Klik & Play, originally created by Europress Software and distributed in the U.S. by Maxis, is a game construction kit that has met with some commercial success. In contrast to GURPS, Klik & Play is more than a reference guide: like EGGG, it creates computer games.Klik & Play is aimed at children. It's a visual application builder that provides you with predefined objects -- a running man, walls, monsters, and the like -- and lets kids assemble them into video games. There is an "event editor" that lets you define complex actions -- but these actions are all essentially simple conditionals that depend on the other objects. Klik & Play games aren't Turing complete.
The video games all look pretty much the same: in J.C. Herz's categorization of games (see The Game Space in Chapter 2), they are all "shooters", a subgenre of action games. Herz's genres, in turn, are all subgenres of video games. You can't make crosswords, or poker, or chess, with Klik & Play.
The system touts its object orientation, which only means that its monsters and walls and objects have independent picture, animation, and movement properties. Klik & Play is good, but it is not a universal game generation engine. In the tradeoff between expressivity and ease, it favors ease to a much higher degree than EGGG.
Related Fields
Game Theory
EGGG is about games, and EGGG is about theory, but EGGG is only tangentially about game theory. Game theory is a branch of mathematics (some would say economics) that deals with human interactions where the outcomes depend on the interactive strategies of two or more people with opposing motives. Game theory began with a simple betting card game called le Her, in which two players each drew a card and could optionally exchange the card for another based on simple rules. An optimal strategy for playing le Her was discovered in 1713, and that optimal strategy was applied to all two-player deterministic games with the Generalized Minimax Theorem by John von Neumann in 1928.One well-studied game in game theory is the Prisoner's Dilemma, which has this scenario: Two criminals, in cahoots, are arrested for the same crime. They are placed in separate interrogation booths where they can't communicate with one another, and each is encouraged to confess to the crime. If one criminal confesses and indicts the other, the confessor gets a light sentence while the holdout does heavy time. If both confess, they both get a heavy sentence, but not as heavy as a single holdout. If both hold out, they both get a light sentence -- but not as light as a single confessor.
What should a criminal do if he wants to minimize his jail time? Tough question, and this is the bread and butter of game theory. Active research topics include variants of this scenario. What if there are repeated trials? What if they are able to communicate? What if they aren't rational? What if there are three criminals instead of two? What if the criminals aren't sure of the penalties? What if one criminal is less averse to jail than the other? And so on, applied to many other scenarios: arms control, marriage, patents, college applications.
Game theory has nothing to do with actual computer game creation; it is only about strategies for making the best decision, in games where it's possible to reason about what a best decision is (as opposed to arcade games or crossword puzzles). EGGG uses the results of game theory when it generates computer opponents for a game, but the strategies it uses are not the cutting-edge game theory research. The strategies are discussed in Chapter 4, Enemy Of The Game State.
Complexity Theory and Game Automata
It's possible to view games as problems to be solved. Can the first player guarantee a win in tic tac toe? No. Can the first player guarantee a win in chess? No one knows; it's a problem yet to be solved. You can try to solve this problem with brute force, but you'll fail. There are thought to be 10120 chess games, and there are thought to be about 1070 protons in the universe. If every proton in the universe were evaluating a trillion chess boards per second, you still wouldn't be able to answer the problem before the universe ended.Complexity theory is the branch of computer science that analyzes how hard problems are to solve. If a problem can be solved in polynomial time, it is said to belong to P. (More precisely, P is the class of languages that are decidable by some Turing machine in a number of steps that is bounded by a polynomial.) If a problem can be solved by a nondeterministic Turing machine in polynomial time, it belongs to NP. Every problem in P is obviously in NP as well. It has not yet been proven that there are problems in NP that aren't in P as well, although it's a good bet. Much of complexity theory involves proving that a given problem can be "reduced" to a known problem in P or NP, where "reduced" means, roughly, "translated into, if you change how you represent the problem in a nonintrusive way."
Garey and Johnson [Gar 79] list the known complexities of hundreds of problems, including crossword puzzle construction (which is NP-complete), checkers (PSPACE-hard), and Go (PSPACE-hard). This translates roughly into:
- Given a set of words, finding a crossword grid that contains those words will take too long if you have enough words.
- Given checkers on an NxN grid, determining whether a player can always win will take too much memory if N is high enough.
- Given Go on an NxN grid, determining whether a player can always win will take too much memory if N is high enough.
These results may seem far removed from the practical concerns involved in determining a game designer's intentions and converting them into working programs, and for the most part they are. When a typical game opponent is created, its designer has a rough idea of how complex the problem is. Perhaps he can't determine it to the satisfaction of a theoretical computer scientist, but he knows whether a brute-force approach is feasible or not, and he can choose an appropriate strategy accordingly. EGGG doesn't have that luxury.
Condon's Probabilistic Game Automaton
Condon's Computational Models of Games [Con 89] notes that "Traditional models of computation, such as Turing machines, do not reflect the game-like properties of many problems of interest to computer scientists. On the other hand, the traditional approach of mathematicians to game theory did not focus on questions regarding the computational complexity of the game."To rectify this, Condon defines a theoretical construct called a probabilistic game automaton that combines elements of several game-theoretic models. The probabilistic game automaton is able to model features of games that traditional game theory can't accommodate: randomness, secrecy, and limited resources of the players.
The different types of probabilistic game automatons can be classified along three dimensions:
Universal steps Coin-tossing steps Degree of information B (bounded) Z (zero) U (unbounded) P (partial) C (complete) In Condon's analysis, every probabilistic game automaton has at most one symbol from each of the left and center columns, and exactly one symbol from the right column. The left column, Universal steps, has only a single symbol, the "for all" operator. Universal steps are situations where a player has a move available to him without any randomization involved. The middle column, Coin-tossing steps, are situations where what a player does is determined randomly. B or U are chosen depending on whether the automaton needed to model the game is finite or infinite. The right column, Degree of information, indicate how much information a player reveals. A completely secretive game reveals zero information, Z; a game in which the player reveal some information is P, and a game where no information is concealed is C.
These games are all between two players. Multiplayer games like poker, or single-person games like crosswords, cannot be modeled by probabilistic game automatons. And games that depend on hand-eye coordination can't be easily modeled by any automaton at all.
The Eight Games
Computer science has a narrower view of games than the broader population, and so for exploring the similarities between games and describing EGGG's capabilities, we'll focus on a representative core of eight games that, taken together, portray the versatility of EGGG:
EGGG can generate an infinite number of games, and it can generate games that are substantially different from these eight, but in the interests of having concrete examples that can be continued throughout the discussion of EGGG, we will restrict ourselves to these.
- Tic Tac Toe A two person game of complete information, with no randomness and simple rules.
- Chess A two person game of complete information, with no randomness and complex rules.
- Poker A two to six person game of partial information, with randomness and complex rules.
- Crosswords A one person game of complete information, with no randomness and simple rules.
- Tetris A one person game of partial information, with randomness and simple rules.
- Rock Paper Scissors A two person game of zero information, with no randomness and simple rules.
- Deducto A one person game of partial information, with randomness and complex rules. Deducto is the author's creation, and will be discussed in Chapter 3, The Physiology of EGGG.
- Mammon A multiple-person game of partial information, with no randomness and complex rules. Mammon is the author's creation, and will be discussed in Chapter 6, Connect the Bots: Networking.
In the next chapter, we'll take a deeper look at the similarities between games that made EGGG possible.
Chapter 2: Anatomy of a Game
[Game] genres do seem to hold together in the middle, weathering revolutions in chip speed and licensing. It's like the proverbial fourteen novels that have been endlessly rewritten throughout history. The costumes change, but the basic matrices remain. There are certain things that people want to see on a video screen. There are certain strategies that are inherently satisfying. There are certain ways of organizing obstacles that are hard to improve upon.
J.C. Herz, in Joystick Nation (page 25).
In this chapter, we will develop a taxonomy of games, laying the foundation for Chapter 3, The Physiology of EGGG, where we discuss the actual mechanics of game generation.
How are games organized? Is there some Platonic essence of gameness, an ur-game from which all other games have evolved over millennia? A romantic thought, but the answer is no: even if Australopithecus took turns seeing how far they could throw a rock, plotting a gradual evolution from that to Myst would require shoehorning cricket, logic puzzles, Pac-man, card tricks, and professional wrestling all into the same family tree. With games, as with most other collectible things, categorizing is messier than it would first appear.
If we're going to make sweeping conclusions, we first need to identify what it is that we're making conclusions about. Is baseball a game? What about hide and go seek? Anthropological literature typically divides leisure activity into game, play, and sport. Play has no explicit goal, sport involves a test of physical ability, and everything else falls under the catchall category: games. This has the curious corollary that a baseball game played on a field is a sport, while a baseball game played on a computer is a game, even though the two differ only in which muscles are being strained. Nevertheless, it is this definition that we will use when we categorize games and game elements. Game strategies are deferred until Chapter 4, Enemy of the Game State.
A Structural Categorization Of Video Games
We showed some overly simplistic categorizations in the Introduction. For another, deeper categorization, we can examine a particular genre of computer games: the arcade game. J.C. Herz, in Joystick Nation, divides up the space of arcade games as follows:
Herz is only attempting to categorize video games here, but note how she does it: she categorizes them by the player's experience. That makes sense, because her audience is players.
- Action games. These are also known as "twitch" games, and are the most popular subgenre of arcade game. They also have commercial opportunities that few other subgenres do, because they can have character development, and are therefore ripe for cross-licensing deals with other entertainment industries. Sometimes the games lead to television shows (Pac-Man) or movies (e.g. Mortal Kombat), and sometimes television shows (The Simpsons) or movies (Star Wars) lead to games. In Herz's words, these relationships are good for "hatching a slew of games based on movies that are mostly special effects anyway." Herz continues, "These include some of the worst cartridges and arcade cabinets ever produced."
Herz divides up action games into what she calls "structural subcategories":
- Horizontal scrolling games In these games, ships move horizontally across dangerous terrain. Examples: Scramble, Defender.
- Maze chase games The player navigates around the screen, eluding opponents. Examples Pac Man, Rally X.
- Platform climbing games The player tries to navigate obstacles by moving between areas of the screen. Examples: Donkey Kong, Lode Runner.
- Shooters Enemies are attacking you; shoot them all. Examples: Doom, Robotron.
- Raining games Missiles are falling down at you; avoid them (or prevent them from hitting the innocents below you). Examples: Missile Command, Kaboom.
- Breakout Break down a wall with many repeated attacks. Examples: Breakout, Arkanoid.
- Adventure games Adventure games include some of the earliest computer games: Zork and Adventure, which were text-based; and the graphics- and sound-intensive commercial success Myst. Common to all of them is that you wander about accumulating items which are used to solve puzzles.
- Fighting games In Herz's words, "comic books that move." An enemy is attacking you; use the right combination of moves to defeat him. Examples: Mortal Kombat, Tekken.
- Puzzle games Adventure games have an ultimate goal, a Holy Grail; these don't. For instance, Tetris has no ending. The play just gets harder and harder.
- Role-playing games In these games, the player chooses or invents a character and behaves accordingly: you can't just hack and slash everything in sight. Examples: Wizardry, Ultima.
- Simulations Simulations strive for realism over frenetic button pushing; frequently, there is military funding somewhere in the development pipeline. In some simulations, the player needs to manipulate a complex vehicle; in others, he needs to manage limited resources to develop something. Examples: Lunar Lander, SimEarth, and all flight simulators.
- Sports Sports games are a combination of action games and simulations, and try to be as realistic as possible so that they can cater to real-life sports aficionados. Examples: NBA Jam, NFL Quarterback Club 99.
- Strategy These are games where you have to plan long-term strategies, or foster temporary alliances with enemies. Frequently, the theme is consolidation of power, and the games are often multiplayer -- either between humans or between a human and "intelligent" computer opponents. Examples: Civilization, Populous.
Burns categorizes non-video games into the following categories [Burns 98]:
However, if we try to categorize games from the developer's perspective, we need different criteria. When you're programming, the difference between a shooter and a raining game is far less than the difference between either of those games and a card game. Likewise, the difference between the software architecture of a Go game and a rendition of Capture The Flag is tremendous, even though Burns would classify them both a territorial games.
A taxonomy of games from the player's perspective focuses on structure. A taxonomy from a mathematician's perspective focuses on information and probability, as Condon's probabilistic game automata suggest. A taxonomy of games from the designer's perspective focuses on process.
A Designer's Taxonomy of Games
In the rest of this chapter, we will explore the similarities of games by creating a game taxonomy: an organization of games. Each game will be described by a categorization string that describes the process of game play. The categorization strings don't contain the rules of the game, and knowing the categorization doesn't enable one to reconstruct the game, or even visualize it. But if you know the categorization string for a game, you can generate the entire software infrastructure of the game. Everything else is just frosting.In our taxonomy, we attempt to use familiar English words wherever possible. While the taxonomy would sound loftier if we used precise terms (
OccludingBarrier,PlayingSurface,IntrinsicAttribute) we have chosen to use imprecise terms instead (Hand, Board, Color) in the interest of making our study of games a little more accessible.
Frenetics
The first criterion of how a game is to be programmed is whether it is frenetic -- whether it requires "quick" action. We can divide those games into "twitch" games that require near-continuous quick action (most arcade games) and those that are simply time-based, like chess when it is played with a chess clock.Any game that requires moves in a fixed period of time requires a program that can record how much time has elapsed, which in turn requires that any sort of pause feature not provide a player with an undue advantage.
This provides us with the first category of our taxonomy, which we will depict with a table:
Frenetic Frenetic and fast ff Frenetic, but merely timed ft If an
ffis present in the categorization string for a game, it means that the game is frenetic and fast; if anftis present, it means that game is merely timed. If there's nothing at all, the game isn't time-critical at all. These categorization strings were part of the design of EGGG, but are not part of its implementation; they serve only to help us identify the similarities between games.Some Tetris implementations blank out the screen when you pause, so that you can't analyze where a piece would best fit, unpause, and play the perfect game. There are right ways to pause and wrong ways to pause; that's a right way to pause. However, any pause feature would defeat the purpose of timed chess; since chess has relatively little state (any reasonably good chess player will be able to reconstruct the board from memory), blanking out the screen isn't sufficient.
Thus, a universal game generator that renders games from descriptions first needs to determine whether the game is time-based, and then needs to determine what to do when pausing: the more frenetic the game is, the more sufficient it will be to simply blank out the screen.
This provides the second category of our taxonomy:
Frenetic? History-critical? f h Let's classify the eight games described in the Introduction according to these three bits:
Frenetic History Tic tac toe Chess (with chess clock) ft h Poker h Crosswords (untimed) Tetris ff Rock Paper Scissors ft h Deducto h Mammon ft Throughout this chapter, we'll add new categories to our classification scheme as we define the other components of our taxonomy. Before we add more bits to our classification scheme, we'll examine history in greater depth.
History
In this section, we turn to the notion of a game's history. This has nothing to do with how or when the game itself was developed; instead, it refers to the succession of moves made in a game, and their importance to deciding how future moves should be played.In particular, we turn to what we call local history, which is what Condon calls simply "history": the sequence of moves in a particular game between particular players.
Condon [Condon 89] defines Markov games as games where history is irrelevant. If you look at a tic tac toe game in progress, you know everything you need to know just from looking at the board and identifying whose turn it is. Tic tac toe is a Markov game; so are crosswords. To say that something is a Markov game is the same as saying that you can choose your move without remembering earlier moves.
Text adventure games are not Markov games, because what happens to the player at a given point depends on actions he took earlier.
Chess, to the surprise of some, is not a Markov game. You cannot capture a pawn en passant unless the opponent moved that pawn forward two squares in his last turn -- so you need to remember the last turn: a history of one move. Furthermore, you cannot castle unless you have never moved your king. Therefore, a chess program has to remember all of the moves back to move 2, which is the earliest that a king could be moved. You need to remember almost the entire history. Go also requires history: even though Go books teach readers by depicting boards and asking what the player should do, which suggests that the board contents are all you need to know to render a decision, Go is not a Markov game due to the rule of ko, which prevents a board from having the exact same arrangement of stones on successive turns.
When you peer closer at what it means to be a Markov game, the distinction between Markov games and non-Markov games gets even more slippery. For instance, consider Rock Paper Scissors. Is it a Markov game? It might seem so, because the previous rounds don't affect the play of the current round: the rules are all still the same. Yet the strategy of the game involves analyzing the history of your opponent.
When the history is itself part of the board, the distinction blurs even more. Consider Mastermind, where a player inserts pegs into the lowest level of the board on turn 1, level 2 on turn 2, and so on up to the top of the board. On turn N, the pegs in levels 1 to N-1 are there only to provide a record of the game history. Yet you can look at the board and immediately have all the information you need to decide the perfect move -- clearly a Markov game. The play of Mastermind would be exactly the same if the player had only one level available to him, which he would fill with pegs and then remove when his next turn began. He'd just have to remember all of his previous moves -- clearly a non-Markov game.
Classifying games into Markov games and non-Markov games seems clear-cut when you consider the idealized games of theoretical computer science, but it falls down upon closer scrutiny.
Condon's probabilistic game automata view history as something that a particular game possesses. But EGGG takes a broader view with a global history, defined in Chapter 6, Connect the Bots: Networking.
The Six Types Of Synchrony
In this section, we continue our emphasis on the process of the game, rather than its structure. Once we know whether the game is time critical, whether it is frenetic, and whether it has to remember everything it's done, we can turn to the actual game construction.In a game like bridge or chess or tic tac toe, the turns alternate. If you assume that the game is not networked (networked games will be explored in Chapter 6), you could envision players taking turns playing the game on a single computer, with one player using the keyboard and then handing it off to the next player; the game program then has to rotate the board so that it is presented from the appropriate viewpoint for each player.
But there are some games for which this doesn't make sense. Consider Diplomacy, in which everyone decides where to move their armies and navies, and submit their moves simultaneously. Or consider Spit, a card game where two players are racing to place their cards on top of a central pile. Even one-person games like Doom, which have no discrete moves at all, aren't without synchrony: the monsters move at the same time you do.
We classify the synchrony of a game as follows: If all players move simultaneously, we call that complete synchronization. If only a subset of the players (which we'll call a team) move simultaneously, that is partial synchronization. And if the game is sequential, we call that zero synchronization.
If only one thing happens at a time, we call that a sequential game. Poker is sequential, because only one person at a time can move. In sequential games, the turns might alternate between two players, as they do in chess, or they might circulate in a particular order, as in the clockwise betting rotation of poker. They might be arbitrary but fixed, as they are in Monopoly. They might have no order at all, as in quiz shows or Charades: you "move" whenever you like.
Here, then, are the different types of synchrony. We have no categorization for simple alternation, since alternation between two players can be viewed as a degenerate form of clockwise or counterclockwise rotation. (Below, we refer to counterclockwise rotation by its more esoteric and evocative name, "widdershins", so that we can have a unique one-letter descriptor for the six types of synchrony.
Synchronization Total synchronization st Partial synchronization sp Sequential movement (rotation clockwise) sc Sequential movement (rotation widdershins) sw Sequential movement (other ordering) so Sequential movement (random) sr Games that are not sequential usually require multiple strands of execution: either the threads provided by many operating systems, or distributed computing, or a fork/exec computation model. At the very least, they will require emulating multiple threads of execution.
Games that are sequential can use the ordering to loop through the players in the appropriate order.
Now we can classify the eight games of our dissertation according to their synchrony as well as the previous time and history criteria.
Frenetic History Synchrony Tic tac toe sc Chess ft h sc Poker h sc Crosswords sr Tetris ff sr Rock Paper Scissors ft h st Deducto h sr Mammon ft sp
Movement
Now that we've classified the sequence of play in the game, we can turn to what is being synchronized: the moves. Our taxonomy defines several components to movement: the move, the phase, the turn, the round, and the step. Few games have all five components. (Magic: The Gathering is one such game.) Each of these components is denoted with a single letter followingm: A game with moves is denotedmm. A game with moves and phases is denotedmmp.To a first approxmation, these components form a hierarchy: a round can consist of multiple turns; a turn can consist of several moves; a move can consist of multiple phases; and a phase can consist of multiple steps. However, there is not strictly adhered to: in Nine-Men's Morris, phases consist of multiple moves, and is denoted
mpmto indicate that moves constitute a phase instead of the other way around.We now discuss each of the five components of movement.
The Move
In games like tic tac toe and chess, the notion of a move is intuitive, and we hear it in "X should move here", or "Black moved his king's pawn forward two squares." Yet even these moves are slightly different. In tic tac toe, the movement is really placement: a player chooses which square to occupy, and by so doing occupies it. In chess, choosing a square is not enough. You have to choose two squares: a source and a destination. In Diplomacy, even the source and destination of a move aren't enough.In a crossword, a move is writing a letter in a square. But a crossword move can also be erasing a letter in a square. Thus, moves aren't always steps toward a goal, and they don't always add information to the game state.
At this point, the astute reader will note that we've corrupted the intuitive definition of move -- casual users would never call filling in a crossword grid as a series of moves. That's okay, because here we are only talking about the abstractions inside EGGG. The casual user never sees these abstractions, because they can use the more familiar terminology when describing games. EGGG maps the familiar terms to the internal abstractions described in this chapter. Multiple words in the EGGG vocabulary trigger the same abstraction; the choice of abstraction depends on their context.
The Phase
The picture becomes further complicated when we consider the moves of other games. People don't speak of making "moves" in poker, but it's not difficult to broaden the concept of moves to include what it is that players do in poker: ante, bet, call, raise, fold, and discard. Now we have several different types of moves, and each is valid only at particular times during the game. Likewise, deciding who goes first in Monopoly or backgammon or billiards implies a sequence of actions entirely different from the regular play of the game.We call these distinct times phases, and if a game has phases, it is represented as
mp. The movement letters can be concatenated; a game with both moves and phases is denotedmmpif the phases are part of the move (as in poker) ormpmif the moves are part of the phase (as in backgammon).
The Turn
Where does a game like Progressive Chess fit into this categorization? In Progressive Chess, the first player takes one move; the second player takes two moves; the first player take three moves, and so on. Games typically last about seven or eight turns [Burns 98].When a sequence of moves are made at a time, we call that a turn, and designate it
mt. In Progressive Chess, EGGG needs to know not just that moves are combined into turns; it also needs to know how. Unfortunately, this requires that you burrow down into the underlying representation and specify how: with code. When a component of the taxonomy requires writing code, we designate it with an additional opening curly brace,{.In games like that have tricks, like bridge and pinochle, the moves are individuals playing cards, and the turns are the tricks.
The Round
When a game consists of a series of short, independent games, each with its own winner, it is said to consist of rounds. Poker has rounds, as does Rock Paper Scissors. In both of these games, there is no state kept between independent rounds. You can play one round of poker, but in practice many rounds are played at a sitting. A game with rounds consisting of turns would be representedmrt.
The Step
Some games have complicated moves that require compound actions. If the actions are integral to the play of the game, they are the moves and phases that we discussed earlier. If they are merely customary or superficial, they are called steps. Rapping your knuckle on the table to signify the end of a phase in Magic, or sorting the cards in your hand, or saying "Check" in chess: these are all inconsequential actions that are nevertheless important for any faithful rendition of the game by a computer.Here is a summary of the five components of movement:
Movement Move mm Phase mp Turn mt Round mr Step ms And here are the categorization strings for our eight games:
Frenetic History Synchrony Movement Tic tac toe sc mm Chess ft h sc mms Poker h sc mrmp Crosswords sr mm Tetris ff sr mtm Rock Paper Scissors ft h st mrm Deducto h sr mrpms Mammon ft sp mmp We've now classified when players act, and the sequence of actions. But we haven't talked about what it is the players are acting upon. We turn to that in the next section, Tangibles.
Tangibles
Descriptions of games from the player's perspective typically begin with the look and feel of the tangible objects: board, pieces, cards, and so on. Or they begin with what the user first sees in the game. "You have a sideline view of a basketball court, and you control one character at a time in a game of two-on-two."This is precisely the way you want to describe a game to a person, because it helps them visualize the game. Pictures first, rules and buttons and controls later. However, we have delayed introducing tangible objects into our taxonomy for a reason: they actually aren't that important to the design of a game. You can play chess with cards instea
