Three Concepts: Probability | Projects
Eleusis is a card game that simulates scientific work. In Eleusis, one player takes the role of God (also known as The Supreme Being), and the others play scientists in a race to find the truth in the God's mind. The subject of this project is to produce a learning agent that plays the role of a scientist in a simplified version of the game, called Probabilistic Eleusis.
» Introduction and the rules of Eleusis
Programming an agent for the universal game of Eleusis would require considerable effort. Thus the task in this project is to program a "scientist" agent for a probabilistic, memoryless version of Eleusis. In this version of Eleusis at each step the "Supreme Being" selects randomly a card (with replacement), i.e., decides on a particular card from a regular deck according to a stationary distribution. Scientist's task is to guess the characteristics of the playing card (suit, number) in question. The Supreme Being has no memory, so each card is drawn from this distribution independently.
Also the scoring rules are very different from regular Eleusis:
In short:
The purpose of the game for the scientist is to learn/guess the distribution as fast as possible and, as a result of this, get rid of all the harma. The performance of a scientist is measured as the number of guesses needed to finish the game.
Your task is to write a scientist program that can play the probabilistic Eleusis game. You must also document the principles your solution and analyse its performance. You can implement the scientist either as a scientist program or a scientist class in Java.
A scientist program is a program that, in an endless loop:
The scientist program must write its guess to the standard output and read the results from the standard input. A guess is a line with two numbers separated by a space. The first number specifies the suit (0 = spades, 1 = hearts, 2 = diamonds, 3 = clubs) of the card and the second one specifies the number (1..13). For example, to guess a king of diamonds, the program must output "3 13\n". The Supreme Being answers by outputting two binary numbers, separated by a space. The first one tells if the suit of the card was correct, the second one tells if the number was correct. For example, "1 0\n" means that the scientist guessed the suit right but failed with the number. If the input stream ends, or the scientist reads anything else than a valid result line, it must exit. You can use any programming language to write the scientist agent, as long as
In the downloadable project template, there is a driver script (peleusis)that tests your scientist. It is written in Python, so you must be using a computer with a Python interpreter. All the CSL#2 Linuxes have one. You can also write your own evaluation script in another language if you wish. To help you start building your scientist, there are two simplistic example scientists included in the project template. One is written in Python and the other in C.
Since the stream-based agent approach explained above failed to cooperate with Java (for unknown reasons), there is an option to program the scientist as a Java class that conforms to the simple Scientist interface included in the project template. This interface defines two methods: guess and reveal that the scientist must provide. The project template comes with a driver program in Java that you can use to test the scientist. There is also an example scientist class called StupidoScientist to demonstrate creating a scientist.
The driver scripts have the possibility to define the Supreme Being's stationary distribution for the deck of cards in a file (see the sources for examples). Thus you can test the performance of your scientist with different distributions. A distribution file lists the frequencies of all cards. If there are fewer than 52 entries, all other cards are assumed to have frequency of 0.
Your scientist does not have to be based on Bayesian principles, it can use any method (neural network, rule-based system etc.) that can be used for discrete prediction tasks. However, since the learning task is probabilistic in nature, scientists that use probabilistic model families have certain advantages...
The complete project is a tar file that has the shape of the project template. So use this template to return your entry for each round. You should remove unnecessary files under 'programs' subdirectory to avoid misunderstanings. We need only the files for your entry. Mail the finished project to tommi.mononen@cs.helsinki.fi.
These instructions are rather brief. If you run into problems, email questions to Tommi.
Your scientist will be evaluated with an evaluation script not unlike the ones in the project template. The scientist is tested with a set of ten (10) different distributions, and the performance will be measured as the total number of steps needed to finish the game in all the distributions, i.e., to get rid of all harma. If testing against a distribution takes more than 1 CPU hour of computation, or it takes more than 1000000 steps, the scientist will get be treated as if it spent 1000000 steps to get rid of all harma. Scoring of your project will be relative to the performance of your program. We may change details of the evaluation program, such as the random number generator, so you better not try any dirty tricks!
In case you want to provide (at least an approximate) Bayesian
scientist (which of course is always a good idea :), you should use
two multinomial models, one for the suit and one for the number. More
information about the multinomial distribution can be found in
Gelman A., Carlin J., Stern H. and Rubin D.,
Bayesian Data Analysis.
Chapman & Hall, 1995.
or Minka's
derivation.
For example so called Naïve Bayes classifiers should work decently.
|
|
|
|
|
|
| Three Concepts: Probability | |