Brilliant Hunger Games Programming Competition

I think I may have found a bug:

self.attempts += self.P-1
reputation_list = tuple(p[2]/self.attempts for p in self.players)

The rules say that: Each player has a reputation $R$, which is defined as $R=\frac{H}{H+S}$, where $H$ is the number of times you chose to hunt and $S$ is the number of times you chose to slack (not hunt).

Although players start with 0 reputation, I think that's only for the first round. Afterwards, the reputation is not $R=\frac{H}{H+S+(P-1)}$, but $R=\frac{H}{H+S}$.

Chad, thank you so much for your testing environment and the ready-to-submit Player class. Made it very comfortable to participate.

Hey Chad, I forked your repo, and my partner Tim and I have re-factored some stuff. It makes the code more modular, and re-writes Game.py. It's probably less efficient, but I think it's more readable.

https://github.com/jknielse/hungergames-1

If you modify the script to give a comma-separated output, it will be easier to read the results in a table and plot/analyze them.

You noted that your class fails the test script. Wouldn't that imply that it will also fail in the actual competition, or am I missing something?

By the way, you can have negative food during the round. See this comment.

"If after any round you have zero food, you will die and no longer be allowed to compete." I guess according to the rules, you're fine just as long as you have more than zero food by the time the round ends. Unless there's some sort of thing in the hunting function that doesn't let you hunt if you have zero or less food. I doubt it though, I think they'd be explicit about that sort of thing.

Whenever my algo returns huntdecisions in which the number of elements are greater than the input-ed number of playerreputations your engine seems to make it unbeatable.

Yeah I have no clue how this is supposed to work either I think you're right. Wait I'll go check the FAQ.

We are currently evaluating the feasibility of allowing java as well. We'll be able to firmly answer this question shortly. Other languages are not planned at the moment.

It's incredibly easy to learn too, so considering you're in Data Structures 4, you should have no problem completely understanding the constructs of Python.

Right now we have a test script that you can use to verify your code is functional.

I created one and it's hosted on Github at https://github.com/CaptSullivan/HungerGames

Another question about the word "average": Why would that be an average of 2? If the threshold is reached, then everyone gets exactly 2 per hunt, otherwise everyone gets exactly 0. Also there is no possibility to gain more than 2 extra food, so the actual average over the whole game is some number between 0 and 2. Am I missing something?

Correct. The bold portion means "sum of the number of times players chose to hunt in that round". We'll adjust the language to make it clearer.

As for number_cooperators: cooperator means you hunted. So this number is precisely the sum of the number of times players chose to hunt in the round. We'll modify the language here as well to streamline terminology.

Your friends can definitely team up and play with you! Anyone with a Brilliant account can participate, and anyone who can beg, borrow, or steal time on a computer can create a Brilliant account. Please have them create accounts on Brilliant. They can do so directly on the Hunger Games page: https://brilliant.org/competitions/hunger-games/

If you are logged out or do not have an account when you see that page, hitting the "start playing" button prompts you to a sign up page. Just send your friends the link.

We want teammates to all have accounts on Brilliant, as it provides a layer of verification that the people who submit code, or supposedly submit code, are in fact who they say they are and not impostors, bots, cylons etc... With money prizes on the line this is important. It also provides us a way of informing all members of a team of the status of their algorithm in the competition, as opposed to just you.

Have fun and may fortune smile upon your strategy :)

Food is only counted at the end of the round.

Python version would be nice to have indeed. I assume it's 3.x since test code uses print as a functions (can be done in 2.x too, but is necessary for 3.x).

Python version is 2.7, processing power is "enough", i.e. worrying about our specifications should not be a concern

I'll probably be writing one before too long. I can post it on github and put a link here if you'd like.

I wrote one last night. It's fairly simple and straight forward. Should also be easy to read if you want to tinker with it. https://github.com/CaptSullivan/HungerGames

good points. Also:

• My biggest gripe is the public goods part of the rules. First of all, you only have a very small influence on this until late game. And second, since it benefits everyone equally, there is almost never a reason to change your hunting choice to participate.

I suggest a change: Give the extra 2 per hunt only to the actual hunters. This would make it in 50% (in case m follows a linear distribution) of cases worth the "investment", which means maximum unpredictability for dumb programs. This also opens up a whole new layer of depth: you would have to estimate the propability of number of hunts reaching the threshold. Also this would improve the next issue:

• The food costs/bonuses are very skewed towards stackers. I get that a better player would win vs pure stacker, but only marginally so, which flattens the skill curve. Because of this, chance will play an unnecessary big part of the deciding factor.

I would suggest a slight change of numbers. maybe make cooperating more beneficial, and/or consider the change to the public goods rule as stated above

• I, again, strongly argument for imposing runtime and memory limitations.

This needs to be clarified on the rule page. I am confused as well. I would assume so.

From the FAQ.

If the last N players all die in the same round or N players have the same food at the end of the game, then reputation will be used as the tiebreaker, with the highest reputation winning. If there is still a tie, then the winning prize will be split.

So if N players die at the end and they are all left with -1 food, then reputation will be used to break the tie. Those with the same reputation will split the grand prize.

What about a .zip or .rar file?

And may the odds be ever in your favor. Just had to say it :D

1. Yes, $m$ can be higher than $P$, but the bonus applies when the total number of hunts is at least $m$, not the total number of hunters. The maximal total number of hunts is $P(P-1)$, as everyone $(P)$ gets $P-1$ chances to hunt.

2. If everyone gets $2(P-1)$ units, then that is $2$ units per (potential) hunt, as everyone has $P-1$ chances to hunt.

It should also be noted that you get the bonus food regardless of whether or not you hunted.

I'm bumping this. It's really, really, really important to know what the limits are regarding computation time and memory limits. They will have limits to these to keep people from sending them things like:

while true: pass

or

i = 0 while true: k[i] = "stuff" i++

• I have no idea to be honest. However I can't imagine there would be any exessive calculating in algorithms' logic if done in a smart manner(?)
• huntoutcomes list is in same order as the given rep list in huntchoices (See "Sample Code")
• No idea. However one could assume there will be not since there hasn't been any info about that. However things may change. You could always write your own Hunger Games code and run your algorithm on that, if that's allowed.
• Yes. I'd say it's impossible to track people in this game in any reliable way. Best you can do is to compare reps of last round, hunters of last round and new reps together and even then there's high possibility your code chooses wrong rep <-> player.

You can test your program for common mistakes using a script, see the Sample Code section.

I just put up a timer, basically, the form will be disabled when the next set of problems is released on midnight sunday (UTC).

The players are shuffled every round, so your OPTION 1 as described requires information you don't have.

OPTION 2 is already implemented in my GitHub project as FairHunter if you want to see what the source code looks like (it's in bots.py, inheriting from a base class in Player.py). And you're right, it's a 1-line comprehension not counting imports.

Very, VERY nice comment/post. The best alongside Chad's hunger games simulator post. I am sure this is what Brilliant staff was after when one of them said they even encourage to discuss about the best tactic. Like Chad side, first option requires one to connect players from last round with current round. It's not impossible especially after many rounds (50 or so, depends on how many players), but it can still be unreliable. Altho I am sure somebody implemented this kind of tactic already considering there is like 120 algorithms already participated (!!!), From what I have learned during force-test simulations (10 games of 50 players in ~7sec), from all simpler bots like one you described it performs a lot better. Could be just the fact I am using clones of same algorithms in one game and there's lack of proper algorithms, but it still wins other algorithms by a long shot.

There will be "what happens next" post/email tomorrow with all this information.

Looks right. Basically what these equations are saying is this: Your opponent's hunting with you is worth +3 to you, and their slacking with you is worth 0 to you. Your hunting with them is worth -1 to you, and your slacking with them is worth 0 to you. There's a -2 base payout (or 0 if a hunt bonus is awarded).

So, unless you can track individuals, what you're really looking at is trading your own hunts to the tribe in return for hunts from the tribe. It's worth trading three of your own hunts to get one hunt from the tribe. And, unless individuals can track you (and most probably can't), it doesn't matter who you give food to.

(Being able to track individuals' food would be interesting. Then, you'd want to copy the #1 guy's reputation, while at the same time starving as many top guys as possible so you could decrease their ranking relative to yourself. I wonder what kind of population dynamic this would lead to? Everyone with the same score? A constant churning of the leaderboard?)

I ran some simulations using a bot that followed approximately this algorithm and it did surprisingly well. Your analysis here takes some of the surprise out of the result.

Another odd thing I found is that there were really two end-game equilibria: one where everyone starves, and one where everyone has more food than they know what to do with. The break-even point seems to be around a 50:50 hunt:slack ratio, where if the average among everyone is below that, everyone will eventually starve, and above, there is ridiculous amounts of food for everyone. Different bots flourish in each environment, so it will be interesting to see whether the starting conditions are primarily cooperative or hostile.

You mean your reputation does not depend who you hunt with, just how many times you hunted? Your earnings of course depend on who you hunt with. If you chose to hunt 3 times in a round and your opponents slacked you are -9, if all of them hunted you are at 0 (did not gain anything, but did not loose anything either). But you are right that decisions how many times to hunt in a round and who to hunt with are two different decisions. Whether or not you get a bonus depends on how many times you hunted and of course how many times others hunted, not who you hunted with; whether you loose -3 per hunt or not depends on who you choose to hunt with.

We believe it to be fine under fair use laws. A community of math and science enthusiasts, throwing a competition where algorithms compete for "food" is not going to be confused with the best-selling books and movie.

Write in English. Add parentheses and colons. Now you have python.

I'd recommend this.

I recommend the book "Dive Into Python," which the author has made available for free online. It is targeted towards "experienced programmers," and will help you build a solid understanding quickly.

It's incredibly easy to learn. You're in Data Structures 2, and it will probably take you around 3 weeks if you sit down and learn Python to master the language. In fact, if you're familiar with some other language, grasping the basics of Python should only take you a day at a maximum.

Yes.

P is always the current number of players (see: section II, "Hunts")

Actually, it asks what should A be so that every strategy involving Chuck cooperating in the first round, is better or equal than every strategy involving Chuck deflecting in the first round

I was wondering this too myself, and just thought I misunderstood some of the English wrong in my head. Indeed if Chuck first chooses to cooperate (0) and then defect (8) he gains 8. I am now even more confused after I checked my answer which was 'right'.

we're adjusting this problem. It's not phrased in the way we wanted it to be.

Slacking is surely the best thing to do in a certain round, but for the long run, you might want to hunt, because that boosts your reputation. You want a high reputation because (hopefully) others are more likely to hunt with you if your reputation is high.

In 2 players, always slacking is unbeatable. It's not with more. A strategy of "slack unless paired with someone tied for the highest reputation" will beat any number of slackers as long as at least two players are doing it.

Yes and yes.

It seems like you should just name your class Player upon submission. Whatever you name it during testing shouldn't matter.

It's confirmed in the FAQ that the class should be named Player. This is the primary reason I adopted that convention in my github repo.

yes

Wow, I was skateboarding and surfing when I was 12 haha... I'm impressed... Do you have any specific questions? Do you know how to program?

1) described in the sample code 2) described in the sample code 3) the probability of any round ending is "small". It's very intentional that you never know if the game is about to end or not 4) If one goes and one stays, the one that goes spends 6 while the slacker only spends 2, but they both get 3 back. So the hunter gets -3 while the slacker gets +1. The goal is to try to get other people to hunt with you.

In simple game theory terms, the dominant strategy is to always hunt, but the equilibrium for the game (in the simplest case of two players) is to always slack.

The first round number we send to hunt_choices is 1.

That should work though I haven't extensively tested it. I believe python is pretty good about figuring out what information different objects should have (and preventing unintended access (for instance, if someone had def sum(x, y): in their code, it wouldn't override python's default sum function for other people).

If I understood well, you could choose to hunt or not hunt a player according to his reputation. If a player has a reputation of 1 he has always hunted, while if it's 0 he never did it!

Yep, that was us! :)

If you know Java well, learning enough Python for this project should be very easy.

In your algorithm, you can use the number of opponents, e.g. by taking the length of the list of reputations.

I just saw that someone posted an answer to another similar question. This was already posted. If anyone has anything else that would be great.

Isn't that irrelevant? All you know about others in the same tribe/game is their reps and number.

I think that everyone is in the same tribe.

I personally started from here

Everyone gets $300 \times (P-1)$ units of food, not $300 / (P-1)$.

Everyone will get 300(P-1) food. Since you can lose a maximum of 3 food per hunt, and have P-1 hunts per round, no player should die before round 100. Especially since the bonus foods come into play

I'd like to have some clarification to this too. From what I understood with my high school mathematics "300(P-1)" means "300 * (number of players - 1)". So if there were 61 players, each of them would gain 300 * (61-1) = 18000 units of food. This sounds ridiculously high amount for food per player altho number of hunt choices and change in food per round rises too. I just assume I understood something wrong.

Rebecca: I would say it's not impossible in principle. Your best bet is probably to find a beginner's Python 2 tutorial (Learn Python the Hard Way is my favorite) and run through that until you understand all the sample code posted here. I'd say the math is harder than the programming.

• Python isn't a shortcut to programming but it's one of the easiest ways to start.
• Results of hunt rounds and public good awards are seperated. Every player gets the coop award if total sum of hunts >= m, no matter what they chose.
• You don't enter any extra variables / code mid game. Your code has to survive on its own without outside help.

Most of this competition is primarily math, as Chad said. You can even just construct simple flowcharts which are purely logical thinking diagrams. Find someone in school who's a computer whiz, pair up with him/her for the competition and get him/her to put your logic into code.

It is not allowed, but even if you'd try, you wouldn't succeed: you don't know with who you are hunting, just their reputation.

They shuffle the player array every round, and you don't get any information about any given partner except their reputation. This makes it very difficult if not impossible to keep track of any individual player between rounds.

The list of hunt_decisions you return will be matched up to the order of player_reputations the host sent you, so if you re-sort it you should keep track of which is which so you can match opponents up correctly before returning.

Also regarding Chad's comment: everyone's reputation_list is unique to them (since they aren't in it) so it is mutable and doesn't hurt anything if they change it (except it may cause their own results to be different than they intended, though I guess it may be a useful tactic to do some in place modification of the reputation_list).

All arguments sent to Players are either ints (passed by value), floats (passed by value) or not used at all in the host (outcomes and player_reputations (both are created using a list comprehension in the function arguments to make it clear that it shouldn't be used internally))

You're only returning your strategy, so the game will almost certainly assume you meant your answers to correspond with the original.

As an aside, I would hope reputation_list is something immutable and not an actual list lest someone break it. ;)

Never mind, I just reread the rules. It's round #1.

In game rules it's mentioned you have a chance to hunt every other remaining player, so your rep will not be in the list.

You have to write a code to play the game for you. The code will decide wether or not you will hunt or slack. (I'm pretty sure)

No no no. Every round, random value m is selected in between 1 and players * (players-1). If total number of hunts (eg. sum of "h"s of every player) is equal or higher than m, every player no matter what they chose gets 2 * (players-1) food. If there were 11 players in total, each of them would get 20 food as an award.

Yes. Also remember public goods if sum of all hunt choices is above m.

Yes, we'll explain that better in instructions on the form tomorrow, but yeah, the form can be updated until the submission deadline (I will make a countdown timer on that page at some point for the deadline).

As I understand, it says in the long run player one will play c 25% of the time and d 75% of the time.

All objects and function exposed back to our host need to have the given names. Internal to your own code you are free to use whatever you want.

From the FAQ:

The standard library is available for use for the most part, but using things like open and inspect to try to gain access to information you shouldn't already have access to in memory or on the disk etc, will not be allowed. Numpy and scipy will be available.

As of now, we are all in the same tribe. This could change later if there are incredibly too many players, in which case (from what I understand) we will only compete within our tribe, and then the winners/survivors from each tribe go on to a second round. (I could be mistaken, since I'm working from memory and too lazy to click over to the FAQ's or further down in the discussions...)

It has been answered by the staff, in the FAQ.

It will be announced in the first round itself as everyone plays together in every round (with the exception of the algorithms that have been eliminated). Behind that deadline I have no clue.

No. The "cooperation reward" (or "public good") is an additional lump sum that is 2(P-1), where P is the total number of players. It is not conditional on hunting or not. It is simply a lump sum given to everyone if the threshold (total number of hunts > m) is achieved.

Yes, it's possible yet not worth the risk IMO. Even after high number of rounds reps of players could "overlap" and you can't reliably connect player <-> rep. However, whole tracking thing opens up new options.

living players at the start of the round

I don't think it's possible to know each players choices. Instead it might be possible to estimate the numbers of hunts and slacks by comparing the reputation between adjacent rounds. This has been discussed below. E.g. consider three players at start of round $t$, with reputations (unsorted) $R_t = [0.20~ 0.55~ 0.21]$. At round $t+1$ you are given (randomized order) $R_{t+1}=[0.53~ 0.21~ 0.22]$. You can guess that element/position two in $R_t$ and element one in $R_{t+1}$ belong to the same player, i.e. $0.55 \to 0.53$. For this to work the changes in reputation between two rounds must be small and overlaps shouldn't exist which would make it difficult for you to distinguish players, i.e. is it $0.20 \to 0.21$ or is it $0.20 \to 0.22$?

The formula for calculating reputation is given in the rules and might be used to estimate the number of hunts/slacks when you, more or less successfully, have tracked a player.

Before we run the full competition we will do a brief burn in and algorithm inspection to weed out algorithms that are completely broken, try to hack the game, or are totally error filled. "Bad strategy" will not be weeded out of course. If you pass this initial inspection, but your algorithm hangs or has a problem later in the game, you will not be kicked out. However, if there is a time out or error that prevents your algorithm from returning a properly defined set of choices in a round, then for that round you will be treated as an 'always slacker' by the host but remain in game.

You know the reputation of any player before you choose to hunt/slack with them. You get a list of reputations, and you return a hunt/slack decision for each of those players, in the same order.

see the faq for the rules in case of a tie

Yes, that is perfectly fine, we decided to allow that because we didn't want to disadvantage people who submit early (which we would like people to do so that can do more performance testing of the host and stuff like that).

From what I understood you can submit more than once, 'overwriting' the last submission.

Never mind, I understand the reasoning behind the number. But does P change as players die? I assume it must, because the hunts would have to change number.

Everyone else's.

hunt_outcomes comes first, then round_end

You could save that list as a global list, which you can access the upcoming round. I believe the sample code shows how to do that. Does that answer your question?

The game will assume your responses come in the same order as the reputation. So if you sort the reputations list for some reason, you need to keep track of the original order so you can return the answer properly.

Yes! Encouraged even, since it's often the fastest way to do things.

All your code needs to be compatible with Python 2.7, as that's what the actual engine runs.

It may be that it is not a global variable. Make sure to call "global thetotalnumber" before using it, otherwise it will be considered a local variable, and it will be destroyed at the end of each turn, to be created anew the next one... At least that's what I think the problem is...

If you're using a class, you want self.the_total_number. if not, you need a global declaration as Esteban pointed out.

Should work just fine.

It's true slacking is the best option always in short term, however this is why they added reputation to game: Others can 'starve' slackers while hunting with eachother => slackers die first. However this depends on how many (hopefully 99%) of the algorithms do this to slackers. Also award is 2 * (amountofplayers - 1), not just 2. And yes, everybody gets the award no matter what they chose.

Justin, my email address is on my github repo if you would like me to elaborate on the instructions that are already there.

I am not sure what you mean with that first question... players' reputations update after every round (see game rules for more info on that), and during next hunting round shuffled lists of these reputations are sent to players. Player reputations list is always in randomized order so you can't directly connect certain rep and/or certain decision from last round to certain player. Best you can is to compared reputations from last round with new ones and 'connect' them.

Only python is allowed. See FAQ

otherwise the best choice would be slack

There's a counter on "submit code" page.

0

I would be pretty surprised. I think one of the first things that people would consider is to exploit the pushovers.

I don't think I've ever seen Pushover win in any of the dozens of simulations I've done. The only way I could see it happening is if everyone (or at least, a majority?) submitted strategies that only hunt with individuals who have a reputation of 1, and slack with everyone else.

Plus, I'm assuming the organizers won't accept Pushover, Freeloader, or Alternator, since they gave those away in their test kit. In fact, I've been assuming the organizers will include those three strategies as part of the tribe, and simply disqualify them in the (exceptionally unlikely) event that any of them get first place. That's just my guess though; I could be (and probably am) wrong!

Nope,Python only

Totally depends on the country you're in, I'd say.

They have always answered "No." to this question, but you have a good point. I remember how I was afraid of Python 'corrupting' my programming skills with Java (no need to define data types etc).

Learning two languages at once shouldn't be a real detriment. If anything, concepts from one language can help inform the other.

Dhanin: I first learned to program on C and I don't think Python would be that hard to pick up. There's a definite learning curve if you want to use more advanced stuff, but you can write Python code that basically looks like garbage-collected C if you want.

I don't think it is a matter of advanced functions/perks. I believe its a matter of being able to run everyone's submissions together. If it's not in the same language, the program they are using to run the competition won't be able to recognize your code. I could be mistaken on this, but either way, if they allow C++, then why not Java, or Fortran, or any other of the hundreds of languages out there that other people are more comfortable in.

You cooperate by hunting. What variable names are you talking about?

The game is trivial if everyone can track everyone's food.

Are you sure this is true? :)

That would end quickly. Everybody hunting every turn, however, would make sure everybody survives.