Project #1 - CS 489 - Computers and Games

Loyola College in Maryland
CS 489 - Computers and Games Spring 2009

Loyola College > Department of Computer Science > Dr. James Glenn > CS 489 > Projects > Project #1

Due:

Part 1: Monday, February 9th at 11:59pm
Part 2: Friday, Februaru 27th at 11:59pm

Introduction

A slot machine (or one-armed bandit) can be modelled mathematically as a device with a payout table that lists the possible payouts and the chance of those payouts occurring. For example, a $1 per play machine may be programmed to pay $1 1/4 of the time, $2 1/8 of the time, $10 1/100 of the time, and nothing the rest of the time. A multi-armed bandit is a machine that has more than one arm. On each play, the player chooses which of the arms to pull. Each arm has its own, fixed payout table. It is to the player's advantage to play the arm with the largest expected payout, but which arm that is may be difficult to determine if the payouts are not posted.

Assignment

Part 1

Write a program that attempts to play a multi-armed bandit as well as possible. Your code will be a subclass of MultiArmedBanditPlayer, which specifies two methods:

int chooseArm(), which determines which arm to play; and
void update(int arm, double payout), which tells the player the result of that play so the player can remember the result and use that information during later invocations of chooseArm.

MultiArmedBanditSimulation contains a main method that will test your player. Your player should not assume that the payouts will always be as given in the supplied test driver. You can create different test machines by creating instances of BinomialBandit and CompositeBandit. A BinomialBandit has a payout table that is determined by the outcome of flipping any number of possibly unfair coins all of the same value. For example, new BinomialBandit(2, 0.25, 0.5) creates a one-armed bandit that flips two fair (probability 0.5 of coming up heads) quarters (value 0.25) and pays the player the ones that came up heads. So 1/4 of the time the payout is nothing, 1/2 of the time the payout is 25 cents, and 1/4 of the time the payout is 50 cents. CompositeBandit allows you to combine multiple one-armed bandits into a single one-armed bandit. The payout of the composite machines is the average of the payouts of the component machines. For example, new CompositeBandit(new BinomialBandit(1, 1.00, 0.25), new BinomialBandit(1, 10.00, 0.05)) creates a machine that pays $1 19/80 of the time (when the 1st coin is heads and the second one us tails), $10 3/80 of the time (tails/heads), $11 1/80 of the time (heads/heads), and nothing the rest of the time (tails/tails).

Your player should outperform the random player defined by the RandomPlayer class. There will be a small prize for the player that consistently performs the best over many different multi-armed bandits.

Part 2

Implement the UCB2 algorithm as a class that implements MultiArmedBanditPlayer.

Files

The archive ucb.jar contains

Submissions

Name your subclass MultiArmedBandit[your-last-name] (omit characters from your last name that are illegal in Java identifiers) and submit as an attachment to e-mail sent to your instructor at [first-initial][last-name]@cs.loyola.edu.