Hopefully, this past week, you have managed to get comfortable with the idea of 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.
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.
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, use the time to improve your player. If not, get to work. Your MCTS will undoubtedly be a key part of your final player.
Hopefully, by this time, you have built a 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. Monte Carlo Search 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.
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.
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 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. Arena and 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.
Okay. We are on our way! First week of class begins now.
Your first assignment 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, Camembert, 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, camembert, 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. 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 notes, videos, background readings, software resources, assignments, 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.
The Piazza link is possibly the second most important link. 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 response that way.
Comments and complaints to firstname.lastname@example.org.