General Game Playing
Homepage
Sign In

Assignments Notes Videos Readings Resources Arena Piazza

Week 10

Final competition is finally over. Congratulations to the winners for trouncing the competition and condolences to everyone else. Once you have done celebrating and/or crying, don't forget that you have one more responsibility - a final report on your player due this Sunday. See Assignment 10 for details.


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. And head on over to Arena to compete against other players.

Next week, during class, we will run the final competition of the course. Be sure to get there on time, and expect to stay longer than usual (until 7:00 pm - 7:30 pm). There will be pizza for those of you in need of sustenance, but you must bring your own beverages.


Week 8

By this point, you have hopefully found that propnets can be used to searching game trees very efficiently at runtime. The good news is that they also have value in offline analysis.

This week, we look at the use of propnets in game reformulation. Using propnets rather than GDL, it is often easy to discover independent "factors" of games. Identifying and using such factors can allow your player to operate more efficiently, since it can search the various factors independently of each other. You should implement a factoring capability for in the case of the types of single player games described in the assignment.

Note that these factoring techniques are relatively simple, but they are very powerful. 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 7

Hopefully, in the last week, you managed to get comfortable with the idea of propositional nets; and, hopefully, you managed to coax your players to use propositional nets as an alternative to general deductive machinery.

Your goal this week is to fine tune your propositional net interpreters. There are many optimizations that can lead to dramatically superior performance, in some cases leading to orders of magnitude more depth charges. Among other things, you should try experimenting with forward propagation versus backward propagation and you should consider differential update rather in processing successor states.


Week 6

This week, we begin our look at the representation of games in the form of propositional nets. As we shall see, it is possible to transform any GDL game description into a propositional net and vice versa.

Given a propositional net representation for a game, it is often possible to search game trees very efficiently. Your non-statistical players should be able to search more deeply, and your statistical game players should be able to perform more depth charges. Propositional net representation also lends itself easily to compilation and even implementation in technologies like field-programmable gate arrays (FPGAs).

Moreover, as we will see in a couple of weeks, propositional net representation facilitates game reformulation and analysis. Using this representation rather than GDL, it is often easier to discover useful structure in games and find game-specific heuristics.


Week 5

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.

This week, we look at one particular class of metagaming techniques, i.e. optimizing game descriptions, e.g. reordering subgoals within rules, eliminating redundant subgoals, and eliminating redundant rules. See chapters x and y.

In the weeks to come, we will look at various other techniques, e.g. translation of game descriptions from logic to "propositional nets", "factoring" games into independent subgames, and "compiling" general game playing descriptions into specialized game players.

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 4

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 good news is that there are some methods that are much more powerful. This week we look at two of these, viz. Monte Carlo Search and Mote Carlo Tree Search. These techniques have proven highly successful in General Game Playing, and virtually every General Game Playing program today uses one or the other.

This week, your primary goal is to implement an MCS player and an MCTS player. If you have already started on this, use the time to improve your players. If not, get to work. Your implementation will likely be part of your final player.


Week 3

This week, we begin our look at techniques for playing large games, i.e. those for which there is too little time to search the entire game tree. We will look at both depth-limited and time-limited search with a variety of heuristics for evaluating intermediate game states (e.g. mobility, focus, and goal proximity). The 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 2

One week down, nine 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. Gameplayer.

Week 2 focusses on game management and the rudiments of game playing. Your job this week is to create your first automated game player, put it to work playing some games, and then extend it to play 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 1

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

Your primary responsibility this week is to form a team to take the course. Teams of three people are strongly preferred, but teams with two or four people are okay, provided that there are exceptionally good reasons. Invent a name for your team. Be creative. Some team names from the past: "Red Hot Chili Peppers", "Men Who Stare at Goats", and my personal favorite "Michael Genesereth". Create a suitable identifier for your team to use online - lower case letters, digits, and underscores only, e.g. red_hot_chili_peppers, men_who_stare_at_goats, and michael_genesereth.

Once you have a team, you need to create an account for your team. Unless you have already signed in, there should be a Sign In link at the top of this page. Clicking this link will take you to a sign in page. If you already have an account, you can use this page to sign in. Otherwise, click the Sign Up link to go to a sign up page. Enter your team name, your team identifier, and the email addresses of your team members and press the Sign Up button. (Please use your Stanford email addresses. Please use your Stanford email addresses. Please use your Stanford email addresses.) Your account will be created, and the team's password will be emailed to all team members. You can then use your team identifier and this password to sign in.

After you have created your account and signed in, you can access all of the course materials via links at the top of the course pages. There are links to assignments, notes, videos, background readings, software resources, the Arena competition management system, and a Piazza course forum.

From a practical point of view, the Assignments page is the most important. It tells you what you are expected to do each week - what you should read and what online tasks you are expected to perform. In addition to forming a team and creating an account, you need to do the tasks of assignment 1 this week.

And please use Piazza. It 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 Piazza rather than emailing us individually, as this allows us all to see your questions and/or comments and you will get quicker responses that way.


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 players able to perform effectively.

All of the course materials are online here. There are links to assignments, notes, videos, background readings, software resources, the Arena competition management system, and a Piazza course forum. Note that, as you proceed through the online materials, you may occasionally encounter technical problems. Apologies in advance for this. We are still working on the course. You may get extra credit for reporting such problems (especially if your reports are not especially irate).

The course is taught in "flipped classroom" mode. Students are expected to master most of the material using the online resources. There will be short lectures in class, but most of our classroom time will be devoted to discussion and demonstrations and competitions. Although the bulk of the material is available online, attendance in class sessions is mandatory. Classes will be held in Room 200-002 Wednesdays from 4:30 pm to 6:20 or so.

All work in the course must be done in teams; and, except in extreme circumstances, all team members receive the same grade. Grades for the course are based on (1) weekly assignments, (2) weekly competitions, (3) a midterm report, and (4) 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 notable performance in competitions and in Arena. People who take CS227B immerse themselves in the course and do good work; and, with occasional exceptions, most receive high grades.

Mike Genesereth*
Email: genesereth@stanford.edu
Office: Gates 220
Office Hours: Wed 3:00-4:00 pm

Jeffrey Barratt
Email: jbarratt@stanford.edu
Office: Gates 219
Office Hours: Fri 3:00 - 5:00 pm

Robert Chuchro
Email: chuchro3@stanford.edu
Office: Gates 226
Office Hours:
Matthew Mistele
Email: mmistele@stanford.edu
Office: Lathrop Learning Hub
Office hours: Tue 7:00 - 9:00 pm

Scott Ray
Email: nsray@stanford.edu
Office: Lathrop Learning Hub
Office Hours: Thu 2:00 - 4:00 pm

Vishal Subbiah
Email: svishal@stanford.edu
Office: Lathrop Learning Hub
Office hours: Mon 4:00 - 6:00 pm

Brian Zhang
Email: bhz@stanford.edu
Office: Lathrop Learning Hub
Office Hours: Mon 2:00 - 4:00 pm

* Genesereth wrote the original code base, first in Lisp and then in Javascript. However, he hates Java and Eclipse and obstinately refuses to become familiar with the details of the Java code base. He is happy to answer questions about General Game Playing and Computer Science, but he is unable to answer questions about Java code.


Comments and complaints to genesereth@stanford.edu.