General Game Playing
CS227B Spring 2014-2015

Home Notes Assignments Resources Readings Coursera

Week 10

Okay. We have done our work, and you have done your work. Now it is time to see how well the players do in competition with each other. Get ready.


Week 9

We are finally done with the material for this offering 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 Tiltyard to register your player to compete against other players.


Week 8

We have now finished with our treatment of propnets. Hopefully, you have found that propnets can be used in searching game trees more efficiently as well as in factoring games to decrease the sizes of those game trees. There is more you can do with propnets; but, in the interest of getting on with the course, we will not delve further into those possibilities. Instead, we will move on to another topic.

This week, we look at some techniques for optimizing games, e.g. reordering subgoals within rules, eliminating redundant subgoals, and eliminating redundant rules. These techniques can be applied to game descriptions even before you consider converting to propnets. These techniques are quite simple but require some processing of the rules themselves. There are no videos for these chapters (as we have just finished writing them). However, there is written material (see Chapter x and Chapter y in the Notes) and a couple of exercises in those chapters and some Gamemaster games on which to apply the methods (e.g. Tic Tac Toe Bad and Skirmish Bad).

In addition to looking at this material, you should spend time this week polishing your players. Also, be sure to connect them to Tiltyard so that they can be tested against other players to see how well they perform.


Week 7

Hopefully, this past week, you have managed to get comfortable with propositional nets; and, hopefully, you have managed to coax your players to use propositional nets as an alternative to the use of the deductive machinery we were using early on. Some of you may even have gone further and figured out how to compile propnets into directly executable code (or even FPGAs). Done properly, this can lead to dramatic increases in efficiency and the consequential ability to do much more search in less time.

This week, we look at another use of propnets, viz. game reformulation and analysis. Using propnets rather than GDL, it is often possible to discover independent "factors" of games, which allows your player to operate more efficiently by searching the various factors independently of each other. The techniques here are relatively primitive but very powerful; and we highly recommend that you look into implementing at least the most basic of these techniques. Your player will play better, and you will get a sense of the sorts of thinking that human programmers use in in producing highly efficient game-playing programs.


Week 6

With our look at Monte Carlo methods behind us, we have now covered all of the basic techniques used in General Game Playing; and your players should now be able to play respectably and even competitively.

This week, we begin our look at a class of more advanced techniques. The unifying theme for this week and next is the representation of games in the form of propositional nets. 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 the game tree more efficiently. Your 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 next week, 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. Importantly, these computations can often be done in time proportional to the size of the propositional net rather than the size of the game tree, leading to a significant improvement in game playing with minimal cost.


Week 5

This week, your job is to continue your work on Statistical Search techniques. Your primary goal is to implement an MCTS player. If you have already started on this (and gotten extra credit for doing so), use the time to improve your player. If not, get to work. Your MCTS will undoubtedly be a key part of your final player.


Week 4

Hopefully, by this time, you have built or configured your player to do heuristic search, and hopefully you have experimented with it 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 often 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 the first of these, viz. Monte Carlo Search and its even more powerful cousin Monte Carlo Tree Search, sometimes called UCT. Monte Carlo and its variants have proven highly successful in general game playing, and virtually every general game playing program today uses some variant of Monte Carlo search. You will probably like it.


Week 3

This week, we begin our look at large games and the Heuristic Search approach to Game Playing. The specific heuristics we examine this week are not as strong as those we will be seeing in the weeks to come. (Translation: The heuristics are mostly "hacks" and not very good ones at that.) However, the basic architecture of Heuristic Search programs is good, and we will see how that architecture can be used with more sophisticated General Game Playing techniques in the weeks to come.

Most importantly, this week, your will confront the problems of time management - allocating time among different tasks and making sure that your players get their moves in before the time 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 the basic tools we have provided, such as Gameplayer and Gametester.

This week, we talk about game management, and we begin our look at 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

This course is a hands-on introduction to General Game Playing (GGP). Theoretical background is provided through lectures and readings, but the main pedagogical value of the course derives from your work in using this theory to create GGP systems to compete with each other and in external competitions against other GGP systems.

This year, we are continuing our experiment with a "flipped classroom" approach to teaching the course. We are providing all of the course material online, and you must review these materials on your own time. There will be no traditional lectures. Instead, we will use class time for discussion and demonstrations. Attendance in class sessions is mandatory. All classes will take place in the room 219A of the Gates Building (the 2A Open Space), not in Math Corner room 380Y as listed in the Stanford schedule.

All of the materials of the course are accessible via the tabs at the top of this page. There are links to Notes, Assignments, Software Resources, and Background Readings. There is also a link to a publicly accessible version of the course on Coursera.

You may find it useful to sign up for the Coursera. Just click on the link in the command bar above and proceed from there. In addition to the materials linked above, this will give you access to videos for all lessons and a public forum for you to use in discussing course material with other students. Registration in the public Coursera offering is recommended but is not required. You can still view the videos by going to the site and clicking Preview Videos on the course home page. The only downside of not registering is that you will not have access to the discussion forum. However, we will cover most of the same topics in class, so participation is not essential.

All work during the quarter will be done in teams; and, except in extreme circumstances, all team members will receive the same grade. Your grade for the course will be based entirely on your work on the assignments listed on the Assignments page. The majority of the assignments concern the development of a functioning general game playing program. We will evaluate your program through a combination of (1) private discussions, (2) the performance of your player during in-class games, and (3) one or more short papers describing your implementation. Note that your program does not need to win in-class matches to receive a perfect grade for each assignment; however, it must function correctly and illustrate the lessons of the week. People who take CS227B immerse themselves in the course and do good work; and, as a result, most students receive high grades.

Mike Genesereth
genesereth@stanford.edu
Gates 220
Office Hours: Wed 2-3
  Dustin Fink
dsfink@stanford.edu
Gates 219A
Office Hours: Mon 4-6
  Josh Grinberg
jgrinber@stanford.edu
Lathrop Tech Lounge
Office Hours: Thu 7-9



© Copyright 2006-2015 by Michael Genesereth. All rights reserved.