General Game Playing
General
Artificial
Intelligence

Lessons Readings Resources Gamemaster Forum

Week 10

This week, we will run the final competition of the course. (1) We will start with a qualifying round in which your players are tested on single player games and multiple player games against standard opponents. Stop by the open space outside Gates 308 sometime between 12:30 and 4:00 pm on Wednesday for the 10 minute evaluation. (2) The preliminary round will take place in class starting shortly after 4:00 pm. (3) Once that is done, we will move on to the semifinals and the final round. Be sure to get to class on time, and expect to stay longer than usual (until 7:00 pm or so). There will be pizza around 5:30 for those of you in need of sustenance, but you must bring your own beverages (other than water).


Week 9

We are finally done with the material of the course. This week, you should spend your time finalizing your player. Decide which techniques you want your player to use. Check the implementation and then check it again to make sure that it plays correctly.

On Wednesday of this week, I will talk a bit about he future of General Game Playing, and I will offer some advice for the final competition. We will also have a "dress rehearsal" for the final competition, so bring your computers and have your players ready for testing.


Week 8

This week, we look at some techniques to improve performance in playing games that cannot be grounded. Examples include reordering subgoals within rules, eliminating redundant subgoals, and eliminating redundant rules. We will also talk about materializing and reformulating the relations used in game descriptions. And we will mention some opportunities for automatic theorem proving.

Note that these are all advanced techniques. They are powerful but more complicated than the techniques we have seen thus far. The upshot is that we do not require that you implement them. All of the tasks on the assignment are optional. You may implement if you like; but, if you want to spend time grounding or pruning or simplifying or symbolizing game descriptions, that is perfectly fine.


Week 7

This week, we look at some techniques to restructure game trees, e.g. by pruning subtrees or splitting complex games into independent subgames. These techniques are relatively simple, but they are very powerful when they apply. If you use them, your player will play better, and you will get a sense of the sorts of things that human programmers consider in producing highly efficient game-playing programs.


Week 6

All of the general game playing methods we have seen thus far are designed to operate at runtime, i.e. while the play clock is running. This week, we begin our look at metagaming, i.e. general game playing activity that takes place offline, usually during the start clock period.

We begin our discussion of metagaming with a look at techniques for "grounding" and "symbolizing" game descriptions and playing games with the resulting descriptions. These techniques are straightforward, yet in many cases they allow players to process game trees more efficiently.

Next week, we look at techniques for "factoring" games into independent subgames, which in certain cases can dramatically decrease the size of the game trees we need to search. And, after that, we look at symbolic reasoning techniques, which can be used on games where grounding and symbolizing is impossible or impractical.

The essence of metagaming is to spend time before games begin to save time once games are underway. In general, metagaming can take a lot of time. However, as we shall see, there are techniques that more than pay for themselves. Most of the techniques we shall see operate in time polynomial in the size of game descriptions and yet yield benefits that are proportional to the size of the corresponding game trees.


Week 5

Hopefully, by this time, you have experimented with various heuristics for evaluating intermediate game states, and hopefully you have used them in time-limited search on various large games. If you are like me, you are probably not impressed with the results. Heuristics like mobility and goal proximity are sometimes good, but they are not good enough to constitute the basis for a good general game player. The intermediate state value heuristic is better. It works particularly well in monotonic / accumulation games, where the player's utility increases as the game proceeds. However, it is not effective in games where intermediate state values are not correlated with final success.

The good news is that statistical methods often work when these simpler heuristics fail. This week we start our look at two of these, viz. Monte Carlo Search (MCS) and its more powerful cousin, viz. Monte Carlo Tree Search (MCTS). These techniques have proven highly successful in General Game Playing, and virtually every General Game Playing program today uses one or the other.


Week 4

This week, we begin our look at techniques for playing large games. The main challenge of the week is to restructure your player so that it can select moves without searching the entire game tree. We will look at both depth-limited and time-limited search with a variety of techniques for evaluating intermediate game states (e.g. mobility, focus, and intermediate goal values).

A key lesson of the week is time management - allocating time among different tasks and making sure that players get their moves in before the play clock runs out. Time management is one of the main themes of the course. Devote enough effort to this now, and you won't stumble over it later when you have other things to worry about.


Week 3

Two weeks down, eight to go. By now, you should a sense of what General Game Playing is all about; you should be able to read and write game descriptions in GDL. You should also be comfortable using some of the resources we have provided, e.g. Sierra, Stylechecker, Gamechecker, and Standalone.

This week, we focus on game management and the rudiments of game playing. Your job this week is to create your first automated game player and put it to work playing small games effectively. Things are still simple in that you do not need to worry about time limits. Although all of our matches have start clocks and play clocks, the games are small enough that your players should be able to search the corresponding game trees in the time available. This is an unrealistic assumption in general, but the methods for dealing with large games are variations on the methods used for small games. So, it is a good idea to master those methods before moving on. In the weeks to follow, you will extend your player to larger and more realistic games.


Week 2

One week down, nine to go. By now, you should have teams and decided on a platform to use in building your game players. You should have a sense of what General Game Playing is about. And you should have played a few games from the Gamemaster library.

Your goals this week are (1) to learn to read and write game descriptions in GDL and (2) to get comfortable with some of the resources we have provided, e.g. Sierra, the style checker, the game checker, and the standalone tool for running standalone games. We realize that you are probably eager to get started building your game players. However, if you spend a little time on these basics, it will help you later in the quarter.

Note for those of you on the waiting list: Our admins tell us that they have sent you all permission codes to enroll in the course. If you are on the waiting list and you want to enroll and you have not received a permission code please let us know by leaving a private note on Ed.


Week 1

Okay. We are on our way! First week of class begins now.

To get started, click the Lessons tab at the top of this page. The Lessons page provides links to slides and readings and resources. And it contains links to the weekly assignments, including details of how to submit your work. The Lessons page is your friend. Use it.

The Readings page provides links to relevant articles on General Game Playing. You are not required to read these articles, but you may find the subject matter helpful as you design and build your game players.

The Resources page provides links to useful tools and related websites.

The Gamemaster tab leads to the Gamemaster competition management system. Gamemaster includes descriptions of games and links to tools to play those games yourselves or to manage matches between automated players. Also, by signing in on this website, you can register your player to compete against other players.

The Forum is a great way to communicate with your fellow students - to ask questions, to offer answers, and to discuss the course material. It is also the best way to communicate with the course staff. You should use the Forum rather than emailing us individually, as this will allow us all to see your questions and/or comments and you will get quicker responses that way.

The lesson this week is mostly introduction, and the assignment is not onerous. We would like you form teams, invent a name for your team / player, agree on technology to use, and create an account for your player in the Gamemaster system. We would also like you to use the Gamemaster site to play a few games amongst yourselves - to become familiar with the practice of learning and playing new games.. See Assignment 1 for details (link on the Lessons page).


Welcome

General game players are computer systems able to play strategy games based solely on formal game descriptions supplied at "runtime". (In other words, they don't know the rules until the games start.) General Game Playing (GGP) is an interesting application in its own right. It is intellectually engaging and more than a little fun. But it is much more than that. It provides a theoretical framework for modeling discrete dynamic systems and for defining rationality in a way that takes into account problem representation and complexities like incompleteness of information and resource bounds. It has practical applications in areas where these features are important, e.g. in business and law. More fundamentally, it raises questions about the nature of intelligence and serves as a laboratory in which to evaluate competing approaches to artificial intelligence.

This course is a hands-on introduction to GGP. Theoretical background is provided through lectures and readings, but the main pedagogical value of the course derives from the use of this theory to create general game playing programs able to perform effectively.

All of the course materials are online here. There are links to lessons, background readings, resources, the Gamemaster competition system, and the course forum. Note that, as you proceed through the online materials, you may occasionally encounter problems. Apologies in advance for this. We are in the midst of revamping the course. You may get extra credit for reporting such problems (especially if your reports are not especially irate).

There will be ten in-person class sessions. See the table below for a summary of the topics of these sessions and locations. Note that two of the sessions will take place in a different location from the other eight.

DateTopicLocation
March 30 Introduction Bishop Auditorium

April 6 Game Description Gates 403
April 13 Game Playing Gates 403
April 20 Incomplete Search Gates 403
April 27 Probabilistic Methods Bidhop Auditorium

May 4 Logical Optimization Gates 403
May 11 Reformulation Gates 403
May 18 Game Tree Restructuring Gates 403
May 25 Really General Game Playing Gates 403

June 1 Final Competition Gates 403

All work in the course must be done in teams; and, except in extreme circumstances, all team members will receive the same grade. Grades for the course will be based on (1) weekly assignments, (2) performance in competitions, and (3) a final report. The majority of the assignments concern the development of a functioning general game playing program. Your program does not need to win competitions to receive a perfect grade; however, it must function correctly and illustrate the lessons of the course. That said, there will be extra credit for especially noteworthy performance in competitions. People who take CS227B tend to immerse themselves in the course and do good work; and, with occasional exceptions, most students receive high grades.

Important note: we use elementary JavaScript in all our examples and software libraries. You are not required to use JavaScript in building your players; but if you use other languages you will need to reproduce the functionality provided by the course subroutine libraries for yourself. JavaScript is quite easy to learn and has the merit of running natively in most World Wide Web browsers. If you are unfamiliar with the language, you can learn more by clicking here or here.

Mike Genesereth
Email: genesereth@stanford.edu
Office: Gates 308
Office Hours: Wed 2:00 pm - 3:00 pm
Dylan Cunningham
Email: dcunningham@stanford.edu
Office: First Floor Old Union
Office Hours: Tue 10:00 - 12:00
Jacob Wagner
Email: jtwagner@stanford.edu
Office: Huang Basement or Zoom
Office Hours: MTh 3:30 - 4:30

Questions and Comments