Printable View
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.
I'd like to play, but someone is probably going to enter withand crush the tournament.Code:int f() { return 2; }
Please go into detail about how the contest works.
Here's my first entry.
Here's my second.Code:int dwks_1(void) {
return (rand() % 99) + 2;
}
And here's my third. :)Code:int dwks_2(void) {
return 100;
}
The 2-100 range is inclusive, right?Code:int dwks_3(void) {
return 2;
}
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]
A guaranteed win in a single round, to be sure. Overall, it could do very poorly. Consider if the following functions were entered:Quote:
Originally Posted by citizen
Code:int f() { return 2; }
Code:int f() { return 100; }
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.Code:int f() { return 99; }
Yes, it's inclusive.Quote:
Originally Posted by dwks
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?
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: [email protected]
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: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.hCode:class TravellersDilemma
{
public:
virtual int ChooseNumber(int previousEarning, int lowerBound,
int upperBound, int bonus) = 0;
virtual ~TravellersDilemma(){};
};
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.
I think you should make the end date June 31st. ;)
So the ten turns is actually five games?Quote:
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.
Okay, could be interesting. Can we submit more than one entry? ;)
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.Quote:
Originally Posted by dwks
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.Quote:
Originally Posted by dwks
Hmm, I think I might have to try this.... :)
Edit:Quote:
Originally Posted by pianorain
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".Quote:
Originally Posted by MacGyver
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.
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?
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.Quote:
Originally Posted by Daved
Yes, good catch.Quote:
Originally Posted by Daved
That's part of the game. ;)Quote:
Originally Posted by 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.
Higher bounds works.Quote:
Originally Posted by Daved
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.Quote:
Originally Posted by 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.
Aye, I plan to once I finish this next version of it.Quote:
Originally Posted by Daved
Cool, thanks. I got working on this and it's really amazing how who wins really depends on the other entries.
I am going to enter, but I want to wait to submit my entry based on how many other people enter. I've got three different strategies that win at different times based on which other strategies I enter in my test tournament.
The more people that enter the better, because it is funner and more interesting. And as far as I can tell a complicated solution might not have a better chance than a simple one depending on the other entries.
Heh, it really is. At first it seems like such a simple thing, and yet the more you play with it, the more stuff seems to emerge. Simple programming dealing with challenging concepts.Quote:
Originally Posted by Daved
Here's the code I'll be using to simulate. Please look it over; I'd rather not skew the contest in any way with a bug on my part. ;)
I'm in. Good luck to the rest of you!
I don't really understand this problem...
What's the advantage of picking 2?
How does picking 100 put you in a disadvantageous position? if you did, wouldn't you get a minimum of 98?
The winner gets their pick plus a bonus in points, and the loser gets the other's pick minus the bonus value (as a penalty) in points. Therefore, picking the bottom number ensures points for yourself and your opponent will score low, and picking the top number is only safe while the opponent's guess is significantly large.Quote:
Originally Posted by h_howee
>> How does picking 100 put you in a disadvantageous position? if you did, wouldn't you get a minimum of 98?
You get a minimum of 2 less than the winning number, which is the smaller of the two numbers, so by picking 100, you will either get 100 (if the other person picked 100) or you'll get two less than the other numbers, whatever that is.
If you pick 100, it's impossible to get 98.
I will enter, but I have a request also.
Can also add a void init(int number_of_players) function to the class?
I'm less inclined to change the interface since entries have already been submitted. Which reminds me of something I forgot to specify...please make sure your class implements a parameterless constructor, as that will be the one I call to populate the player vector. I'll add that to the rules also.Quote:
Originally Posted by Darryl
While you're adding to the rules you might consider disallowing the use of srand and just promise anybody who wants to use random numbers that srand will be seeded prior to the construction of their class.
Ha...that'd be wonderfully devious. ;) Good call. Since I can't edit the post with the rules any more, be sure to check http://fluff.thejefffiles.com/coding/travellersdilemma/ for the most recent version. I'll put a link in my sig also.Quote:
Originally Posted by Daved
In addition to the above changes, I've prohibited the use of file I/O to persist data between simulations.
When you submit an entry, be sure to specify whether you'd like to have multiple copies of your entry in simulations that allow multiple entries or not. If you submit multiple entries, be sure to designate one as your primary entry.
[edit] The judging code contained a one-off bug resulting in incorrect round-robin schedules. The updated code can be found on the contest site.
[edit2] After running some testing with random number of turns per round, I tend to think we might want to use random number of turns per game instead.
Consider the case with three players: your code, a really challenging piece of code, and a fairly dumb piece of code (fortunately, nothing like that's been submitted yet). If your code plays the challenging code for an extended time, you and the challenging code may be tied. Then suppose that you play the dumb code for a short amount of time, while the challenging code plays the dumb code for a long amount of time. The challenging code would be able to pump more points out of the dumb code than you would.
Making it random per game eliminates any random bias.
Less than a week left. Anyone else finished an entry?
Guess I should get around to submitting the one I wrote awhile ago when this was new. :p
does the upperbound, lowerbound, and bonus change each turn or each round?
**edit** nevermind - figured it out...submitting my entry now
I'll submit before the 30th.
For those of you that have submitted an entry, you might want to check yourself against the judging code. It's sad to see promising entries fail to stay within the bounds. Make sure that your code accounts for variances in the bounds and bonus. I played with the idea of introducing negative integers in some of those arguments, but I figured I'd stick with non-negative integers since it made more sense with the storyline. In short, don't worry about negative integers for the bounds or the bonus; it's all non-negative integers only.
Need some extra players? I used the following class:To aid in using the judging code, here's a snippet:Code:template <int constant>
class Constant : public Contest::TravellersDilemma
{
int ChooseNumber(int previousEarning, int lowerBound,
int upperBound, int bonus)
{
return constant;
}
};
Code://Seed up the rng
std::srand(std::time(0));
std::vector<std::pair<Contest::TravellersDilemma*, int> > players;
//push_back all the players with a 0
//i.e. players.push_back(std::make_pair(new Constant<2>(), 0));
std::vector<std::ostream*> streams;
//If you want some output to the console.
streams.push_back(&std::cout);
//Personally, I find this much more useful.
streams.push_back(new std::ofstream("simulation.txt"));
//Make sure you can at least play the standard game
Contest::TravellersDilemmaJudge judge(players, 2, 100, 2, 10, streams);
judge.Go();
I updated the judging code today. There were no significant changes; just some code reorganization and the change from random number of turns per round to random number of turns per game.
After running some preliminary runs, I can say that it looks very interesting! C'mon and get those entries in.
I need a bit of clarification from those that have already submitted one or more entries. Do you want any of your entries entered more than once in the simulations that allow multiple entries per contestant?
Could you post a list of the people who have submitted entries?
> Do you want any of your entries entered more than once in the simulations
> that allow multiple entries per contestant?
I'm going to trust that the tournament style will allow me to face all of the entries by any person at least one time. Put me in once.
I'm going out of town this weekend, so this will be my last reminder to get those entries in. With any luck, I'll post the results on Monday.I'm struggling with whether or not to do so. Each extra piece of information can influence a strategy.Quote:
Originally Posted by Brad0407
Submitted mine just now. I would suggest it be entered only once.
Sent.
Now that the deadline has passed, let's open the floor for discussion.
I wish I could have had initiated my class with the number of players and the number of turns at the beginning of the round. Then I could have made the perfect entry instead of just the most perfect entry :-)
All I'm going to say is that when he looks at my source code, he's going to think something along the lines of, "Whaaaaaaaaaaaa?" :D
The entries and the results have been posted on the site. Thanks everyone for submitting an entry. I would post some commentary, but HTML composition via Notepad tends to be a mind-numbing experience.
So... everybody wins?!
I did better than I expected.
Heh, just about. If I had to assign winners, it'd probably go something like this:Quote:
Originally Posted by Daved
Total number of wins in Simulation 1:Total number of wins in Simulation 2:
- Daved - 3
- MacGyver - 3
- Brad0407 - 2
- Darryl - 1
Total number of wins in Simulation 3:
- Darryl - 4
- Daved - 2
- Brad0407 - 1
Total number of wins in Simulation 4:
- MacGyver - 3
- Brad0407 - 3
- Daved - 2
- Darryl - 1
Total number of wins overall:
- Darryl - 4
- Daved - 2
- Brad0407 - 1
- Darryl - 10
- Daved - 9
- Brad0407 - 7
- MacGyver - 6
Congratulations Darryl!
Seriously though, thank you everyone that participated. I had a ton of fun trying to put together an entry that made just enough sense to gather points, but not so much sense that I ended up playing the lower bound the whole time.
Hindsight.... I should have been way more aggressive with my main bot and I should have submitted multiple entries to assist.
Nice job, Darryl. :)
Thanks, pianorain, for starting this tournament. So...... when's the next one and what subject is it on? :D
Aw, that's really too bad. :( I'll have to do a lot better next time I decide to participate in something.
>> I'll have to do a lot better next time I decide to participate in something.
I disagree. Having lots of participants is what makes it fun, regardless of whether your entry ends up doing well or not. Please participate next time if you have any semblance of a working entry.
P.S. Well done, Darryl.
Macgyver, your bot was a beast. If you'd had supporting bots in multi-play, I'm sure it would have gone far.
Also, even though the contest might be 'over', I'll still take entries and run simulations. I really like how this problem tends to defy game theory in the single player version. If anyone figures out a clever solution, feel free to post about it.
I had another idea for a contest before I started this one, but I failed to write it down. I'll run back through my notes and see if I can pick it up again.
I was going to submit multiple entries, but all I needed to do better was compete against higher numbers. For that reason, I was going to submit one that just always submitted the upper bound, another to alternate between the upper bound and (upper bound - 1), and yet another one to do the exact same as the last one except start with (upper bound -1).
When you said that no one entered simple bots, I decided against submitting my cheap multiple entries. I should have chosen a more aggressive strategy in advancing from a loss, instead of by 1, but I was worried about jumping over the upper bound. I should have jumped a percentage of the difference imo.
Overall, lesson learned. Play aggressive and go for the jugular. :p
How about a round two?Quote:
Originally Posted by MacGyver
Some notes on my experimentation.
I would classify two categories of entries. Cooperative(Coop) and Competitive(Comp)
Coops tries to work with other to maximize overall points.
Comps tries to undercut others to minimize opponent points while maximizing their own.
Comps are highly dependent on the bonus award, the higher the bonus the better they do.
Coops tend to match others so are not dependent on bonus.
More turns per round help Coops overcome the bonus advantage. I figured coops needed about 4-6 turns to counter each bonus point
AS the ratio of Coop players to Competive players increase the better the Coops do. The ratio is less than 50% therefore fewer coops can beat more Comps.
My "Ultimate" entry tried to switch between the two styles of play, for instance since bonus helps Comps, it played that way for higher comps which looking at results, I won most (all?) of the high bonus rounds. Unfortunately I couldn't gauge number of players or numbers of turns, so therefore couldn't adjust to them. My Coop entry though did very well on the low bonus games as well as the many turns per round games