Contest - Traveller's Dilemma

[pianorain]

Here's a very simple contest open to all skill levels.

Write a function that competes in a game that illustrates the Traveller's Dilemma.

*snip*

Before I start spouting off stuff about entries, is there any interest in this contest?

[edit] There seems to be interest. Scroll down for the details.

[whiteflags]

I'd like to play, but someone is probably going to enter with

int f() { return 2; }

and crush the tournament.

Please go into detail about how the contest works.

[dwks]

Here's my first entry.

int dwks_1(void) {
    return (rand() % 99) + 2;
}

Here's my second.

int dwks_2(void) {
    return 100;
}

And here's my third.

int dwks_3(void) {
    return 2;
}

The 2-100 range is inclusive, right?

Well, it actually sounds a bit simple -- why not pick a tougher problem? And you'll probably need some more rules. How long is the contest open for? When will the "tournament" be run? (I'm assuming that you'll run it.) What language(s) can the entries be written in? What sort of format will the entries be required to have? Do they just return an int and take no parameters?

[edit] citizen beat me to it. [/edit]

[pianorain]

Originally Posted by citizen

I'd like to play, but someone is probably going to enter with

int f() { return 2; }

and crush the tournament.

A guaranteed win in a single round, to be sure. Overall, it could do very poorly. Consider if the following functions were entered:

int f() { return 2; }

int f() { return 100; }

int f() { return 99; }

Overall, the constant 99 would win in this field with 1010, the constant 100 would net a respectable 970, while the constant 2 would earn a measly 80. Deviating from 2 does create some risk, but it offers the potential to pay off considerably.

Originally Posted by dwks

The 2-100 range is inclusive, right?

Yes, it's inclusive.

I haven't quite finished with the details, but my intent was to require submissions in C++ so that the programmer could inherit from a base class. It makes it easier to integrate all the entries into the competition program. Have a better idea?

[pianorain]

Traveller's Dilemma Contest

Schedule / Deadline
Start Date: June 15th, 2007
End Date: June 30th, 2007

Submissions
If you choose to enter, please reply stating that you have entered the contest. Before midnight on the Contest deadline you must complete a submission that meets the stated requirements and send it to the submission officer via email or private message. E-mail is preferred. The contest website can be found at http://fluff.thejefffiles.com/coding/travellersdilemma.

E-mail: pianorain@bellsouth.net
PM: pianorain

Introduction
Write a function that competes in a game that illustrates the Traveller's Dilemma. Here are the rules:

• The object is to maximize the number of points that you earn.
• A game will be arranged in a round-robin tournament in which your function will compete with each other function. Each round will consist of some number of turns.
• During each turn, both you and your opponent pick a number between a lower bound and an upper bound. The one that picks the lowest number will gain points equal to the lowest number + the bonus. The one that picks the highest number will gain points equal to the lowest number - the bonus. If the numbers are the same, both players get that many points.
• Five games will be run per simulation with different lower bounds, upper bounds, and bonuses, one of which will be the traditional Traveller's Dilemma (lower bound=2, upper bound=100, bonus=2). The winner is the writer of the function that accumulates the most total points over all five games.
• A number of different simulations have been suggested. The following will be run:
  • The primary entry per programmer and 10 turns per round.
  • Multiple entries per programmer allowed and 10 turns per round.
  • The primary entry per programmer with a random amount of turns per round.
  • Multiple entries per programmer allowed with a random amount of turns per round.

Details
Entries will be accepted in C++. Write a class that inherits from the following abstract class:

class TravellersDilemma
{
public:
	virtual int ChooseNumber(int previousEarning, int lowerBound,
		int upperBound, int bonus) = 0;
	virtual ~TravellersDilemma(){};
};

previousEarning will be the amount of points earned in the last turn or NEW_ROUND if starting a new round. lowerBound will be the lower bound of the range of values. upperBound will be the upper bound of the range of values. bonus will be the amount of points gained if the chosen number is the smaller of the two or lost if the chosen number is the larger of the two. ChooseNumber should return a number between lowerBound and upperBound. For organizational purposes, please name the class as close as possible to your CBoard username. Use the following header file: travellers_dilemma.h

Contest Rules
Below are the current contest rules and regulations.

I. Official Rules
I.I You may submit up to four entries, and they must have been submitted between the contest start and end dates. The programmer must designate one of their entries to be the primary entry.

I.II Entries submitted should be:

• Substantially the developer's original design
• Substantially the developer's original programming
• In C++

I.III In simulations that allow multiple entries, objects of the same class may be used. In other words, each entry does not need to be its own class; the same class may be used multiple times if desired.

II. Code Judging
II.I Submitted code will be judged solely on the number of points earned during the game. Code that does not compile will be disqualified. Code that generates invalid numbers in ChooseNumber during any part of a simulation will be disqualified from that simulation.

II.II In each simulation, five games will be run with different lower bounds, upper bounds, and bonuses, one of which will be the traditional Traveller's Dilemma (lower bound=2, upper bound=100, bonus=2). The winner is the writer of the function that accumulates the most total points over all five games.

II.III The following simulations will be run:

• The primary entry per programmer and 10 turns per round.
• Multiple entries per programmer allowed and 10 turns per round.
• The primary entry per programmer with a random amount of turns per round.
• Multiple entries per programmer allowed with a random amount of turns per round.

[dwks]

I think you should make the end date June 31st.

Each round will consist of 10 turns.
...
The winner is the writer of the function that accumulates the most total points over all five games.

So the ten turns is actually five games?

Okay, could be interesting. Can we submit more than one entry?

[pianorain]

Originally Posted by dwks

So the ten turns is actually five games?

Each game consists of enough rounds for your function to compete against each other function. Each round consists of ten turns. Five games will be played with varying upper bounds, lower bounds, and bonuses. So, assuming four entries, your function will play in five games, each with three rounds that are ten turns long.

Originally Posted by dwks

Can we submit more than one entry?

Multiple entries poses an interesting twist: the possibility of collusion. You can submit up to four entries, but make sure to designate one of them to be your primary entry. In the main competition, only the primary entry from each programmer will be allowed. If there is enough interest, I'll run a second simulation that includes all the entries.

[MacGyver]

Hmm, I think I might have to try this....

Originally Posted by pianorain

Each game consists of enough rounds for your function to compete against each other function. Each round consists of ten turns. Five games will be played with varying upper bounds, lower bounds, and bonuses. So, assuming four entries, your function will play in five games, each with three rounds that are ten turns long.

Edit:

To clarify:

Our function will be tried 10 times with each function and that constitues a round.

Our function will be put through as many rounds as there are "enemy functions", and that constitutes a game.

Our function will be put through 5 games in total.

Is this correct? Are those numbers set for sure or are they subject to change?

[pianorain]

Originally Posted by MacGyver

To clarify:

Our function will be tried 10 times with each function and that constitues a round.

Our function will be put through as many rounds as there are "enemy functions", and that constitutes a game.

Our function will be put through 5 games in total.

Is this correct? Are those numbers set for sure or are they subject to change?

Aye, that's pretty much it, except for the first line, I'd say "Our function will compete against one "enemy function" 10 times and that constitues a round".

Those numbers are "the numbers" unless someone can offer a compelling reason to change them. 10 times against a competitor in a round should be enough to allow for a myriad of strategies, and 5 games should provide a good cross sample of the possible interesting games one can derive from varying the parameters of the Traveller's Dilemma.

[Daved]

Consider randomizing the number of turns in a round. There are different (and less fun IMO) strategies if you know how many rounds there will be.

Oh, and it looks like you edited in the rules above, in case others missed it.

>> previousEarning will be the amount of points earned in the last turn or NEW_ROUND if starting a new turn.

That turn should be "round", right?

Also, can you provide the opponent's proposal from the previous round as well, or is that part of the game to not know?

[pianorain]

Originally Posted by Daved

Consider randomizing the number of turns in a round. There are different (and less fun IMO) strategies if you know how many rounds there will be.

I like the idea as a separate simulation. Should the number of turns be random per game or per round? What would be an acceptable lower bound? I'm leaning towards random per round with a lower bound of 2; I don't find single-shot rounds to be especially interesting.

Originally Posted by Daved

>> previousEarning will be the amount of points earned in the last turn or NEW_ROUND if starting a new turn.

That turn should be "round", right?

Yes, good catch.

Originally Posted by Daved

Also, can you provide the opponent's proposal from the previous round as well, or is that part of the game to not know?

That's part of the game.

[Daved]

I agree that single shot rounds wouldn't be interesting unless you did it on purpose. I'm not even sure that two turn rounds would be all that interesting. My preference would be to have the bounds be higher (5-15?, 10-100?), and randomize each round rather than each game. I also think it would be best if you were to have a random turn simulation to have the number of turns not be known to the contestants' code, even during the competition. So at one point the game just stops.

[pianorain]

Originally Posted by Daved

My preference would be to have the bounds be higher (5-15?, 10-100?)...

Higher bounds works.

Originally Posted by Daved

I also think it would be best if you were to have a random turn simulation to have the number of turns not be known to the contestants' code, even during the competition. So at one point the game just stops.

Yes, that's pretty much how it'd have to be since there's no parameter to pass in the number of turns to the function.

[Daved]

You could always change the interface if you wanted, but I'm obviously fine with that answer.

When you have the code setup to run the simulations, could you post that so we can test on it? You don't necessarily have to publish the actual data you will be passing if you'd like it to remain secret.

If I have time I think I'll write one that assumes a random number of turns, even though that's not the official rule. If that causes it to lose so be it.

[pianorain]

Originally Posted by Daved

When you have the code setup to run the simulations, could you post that so we can test on it? You don't necessarily have to publish the actual data you will be passing if you'd like it to remain secret.

Aye, I plan to once I finish this next version of it.