General Game Playing - Winter Term 2005/06

Course Description

Lecturer:   Prof. Michael Thielscher, Stephan Schiffel

See the official Course Summary page for more details.

Time Table

• Thursdays:
  • 4. DS Lecture (GRU 350)

Consultations

During the Open House.

Details about the Examination

oral examination

Handouts and Slides

• Lecture 1 (Thu, 13 Oct 2005)
• Lecture 2 (Thu, 20 Oct 2005)
• Lecture 3 (Thu, 27 Oct 2005)
• Lecture 4 (Thu, 03 Nov 2005)
• Lecture 5 (Thu, 10 Nov 2005)
• Lecture 6 (Thu, 17 Nov 2005)
• Lecture 7 (Thu, 24 Nov 2005)

Tasks

1. Form teams consisting of 2 to 4 people and send me an email with the names and email adresses of all team members.
2. Write a program that reads in the game description in prefix kif format (for examples see http://games.stanford.edu/language.html). The program should be able to compute:
   • a list of legal moves for all players given a particular state
   • whether a given state is terminal, and what the value of the state is for any role
   • the next state given a state and the move of each player
3. Implement state space search as described in the lecture. Now your program should be able to play small games like the Maze World, Blocks World and TicTacToe, given enough time.
4. Modify your program to return a best move even if it is not able to expand the entire game tree in a given time frame.
5. Implement the communication with the game manager (see below for details), such that your program is able to play against others.
6. Make your program play better than with a simple minimax search and possibly better than the others. Some possibilities to do this:
   • Find a good heuristic function for values of intermediate (i.e. non-terminal) states and use it to guide the state space search.
   • Try to detect the strategy of your opponent(s) and exploit it.
   • Use faster/better search algorithms, e.g. better planning algorithms for single player games.
   • Use the time between the START and the first PLAY message for learning a strategy or heuristic functions.
   • ...

Details about the Implementation

The infrastructure and communication protocol used between the game manager and the players is described here: http://games.stanford.edu/gdl_spec.pdf. The protocol used for communication between the game manager and the players is a kind of http protocol. So basically every player is an http server, that answers request from the game manager. There are three kinds of requests:

• START is sent when a new match is started and your player should reply with "READY", when he is ready.
  With this request the game description is communicated to your player.
• PLAY is sent for every move. Your player has to send a reply with the move he wants to play.
  With this request the previous moves of all players are communicated to your player.
• STOP is sent when the match is over and your player should reply with "DONE".

Here is an example of the messages exchanged during a match.

We provide some Java classes for implementing the player. So if you want to implement your player in Java you can use the classes in this archive. But feel free to use any other language you like.

You can test your player by creating matches on http://games.stanford.edu:4000/.

For further questions regarding the implementation, send me an email.

Details about the Competition

• Date: Tue, 07. Feb 2006
• Time: 9.00
• Room: GRU 106 (computer lab)

You have three options how to take part in the competition:

• You can use one of the computers from the computer lab. You can find details of the software that is available on these computers here and here. Ask me if you have questions about the availability of specific software you need.
• You can bring your own computer/laptop and connect it to the internet.
• You can use your computer at home, but you need to have a permanent internet connection.

Regardless of which option you choose you have to be present in room GRU 106 during the competition. That means, if you choose to use your computer at home, you might have only remote access to your computer.

The competition will start at 10.30, but at least one from every team has to be there at 9.00 in order to setup your computer and your player. We will test if the communication works, your player is able generate legal moves and responds in time.

During the competition each team will be asked to present the approach used for their player. So, prepare a short presentation of about 5 to 10 minutes telling us and the other teams what is special about your player. There will be a video projector and an overhead projector available for showing some slides. Here are some questions you might want to think about when preparing the presentation:

• How do you find the best move? Which search method did you use?
• How do you evaluate non-terminal states?
• How did you model your opponents?
• What do you use the startclock for?
• Did you use learning techniques? How?
• Which kind of games do you think your player is especially good/bad at? Why?
• ...

We will not use any of the games that are available on games.stanford.edu for the competition. Instead there will be new ones, including games you probably haven't seen before. The axioms for the games used in the competition will probably have all words except for role, init, true, does, next, legal, goal and terminal replaced by new, meaningless words, to make human intervention during play very difficult. That means your player shouldn't depend on the names of atoms, functions or relations in the game description other than the reserved words of the game description language.

Results of the Competition

The results of the competition as well as the games that were played are presented on this page.

Additional References

GGP website of Stanford University