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.
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.
This week, we look at some techniques 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 the types of 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.
This week, we 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 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.
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 some techniques that transform GDL game descriptions to alternate GDL game descriptions that allow out standard game players to search game trees more efficiently. Examples include reordering subgoals within rules, eliminating redundant subgoals, and eliminating redundant rules. See chapters x and y in the notes.
After that, we begin our look at transforming game descriptions to other data structures so that they can be processed more efficiently. This week, we concentrate on grounding and compiling game descriptions. Next week, we look at rewriting game descriptions in the form of "propositional nets".
The week after next, 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.
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.
This week, your primary goal is to implement an MCTS player. MCTS is similar to MCS in that it uses random probes to compare non-terminal states. It differs in the way the player selects which states to explore in this way - balancing exploitation (looking deeper into states that have already been explored) with exploration (investigating new states). In practice, MCTS tends to outperform MCS, and there is a good chance you will include some version of MCTS in your final player.
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 start our look at one of these, viz. Monte Carlo Search (MCS); and next week we look a 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.
This week, your primary goal is to implement an MCS player. If you have already started on this, use the time to improve your player. If not, get to work.
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.
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.
As discussed in class, we are moving our class sessions from Room 200-002 (in History Corner) to Gates 219A (the large open space on the second floor of the Gates Building).
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.
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) a midterm report, (3) a final report, and performance in weekly competitions, Arena, and a final competition. 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.
Comments and complaints to firstname.lastname@example.org.