Waste less time on Facebook — follow Brilliant.
×

Hunger Games - Moar data!

We've posted raw data for one of the games in the link below. This data will give you round by round info about the reputation and food for every player. Additionally we have posted the list of ranks. NOTE: player rank was calculated from multiple games, not just this one. Hence a player may very well have a different rank in this game vs. their overall rank.

Download HG_rundata.csv here: https://gist.github.com/brilliant-problems/6563538 *Note, this is a 25MB file, which you will have to download to view.

View your rank data here: https://gist.github.com/brilliant-problems/8d53f9c19a6304c0c7ca

These files identify users by userindex. Find your userindex as follows:

Go to https://brilliant.org/competitions/hunger-games/submit/ Click "Player File" Your userindex is the first three characters of your file name. For instance if your file is named "nsd8V2user123456.py", then your userindex is "nsd".

EDIT: If you believe your algorithm is missing from the list contact us at discussions@brilliant.org with your full user index.

We will post algorithms of the top players.

Note by David Mattingly
3 years, 11 months ago

No vote yet
17 votes

Comments

Sort by:

Top Newest

When is the next programming challenge? I am not so much interested in hard math problems. Max Tower · 3 years, 11 months ago

Log in to reply

@Max Tower What kinds of programming challenges would you all like to see here in the future?

Personally, I'd like to see something where we could get more immediate feedback. Maybe something where we submit solutions instead of algorithms.

The late Netflix Prize is one example of this. In that competition, you were given a bunch of users' movie ratings and tasked with predicting those users' ratings for other movies. It was largely an exercise in matrix arithmetic, along with some calculus. Note that I'm not suggesting exactly that kind of problem (i.e., collaborative filtering), just something along those lines--a statistical guessing game of sorts, but against a fixed target rather than against other competitors.

The late Eternity puzzles are another example. In those, participants were given a difficult puzzle to assemble. It was an exercise in combinatorics. I'd like to see something more in this direction, personally--something with a definite solution, but a very difficult one to find, but still with partial solutions possible (X out of Y pieces fit the constraints, e.g.).

I'm sure you all can come up with more creative things; those are just a couple of high-profile examples I happen to be familiar with. Christopher Johnson · 3 years, 11 months ago

Log in to reply

@Christopher Johnson There are already many programming competitions that have definite solutions or that ask to solve machine learning tasks. I enjoy this more game theoretic flavor: cooperation, competition, signaling. It would be interesting to repeat the same challenge just to see how player's strategies have evolved when they have seen top algorithms. My guess is that strategies would become more sophisticated.

Or one could try more complicated pay-off matrices, more than 2 choices or for 3 or more player decisions, or more complicated signaling than just reputation, or more complicated environment than random m each round. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

@Gatis Midrijanis I second the request for more "game-like" competitions. Alex Nastetsky · 3 years, 11 months ago

Log in to reply

@Gatis Midrijanis If they can automate the process and post results of intermediate runs say, once a day, I'd like to see more of the same. Blind, one-shot competitions like this, though, seem more an exercise of one's social intuition and luck than one's aptitude in STEM (which seems to be the focus of this site). It can be fun in moderation, but I can't agree that it's all I want to see here! Christopher Johnson · 3 years, 11 months ago

Log in to reply

@Christopher Johnson I second this question - we want to know what everyone likes! David Mattingly Staff · 3 years, 11 months ago

Log in to reply

@David Mattingly Can some one please get back to me about why my submission wasn't taken into account? Toms Bergmanis · 3 years, 11 months ago

Log in to reply

@David Mattingly just clear my doubt david , can i participate in these games coz i luv math , ive not yet enrolled myself or things like tat Sai Arvind · 3 years, 8 months ago

Log in to reply

In case anyone's interested, here's a brief summary of the trajectory my algorithm took and what it would have been doing. (I was AEM, who came in fourth in the tournament.)

Round 15: 102799 food (158th out of 349), 67.2% reputation (65th out of 349).

I initially have two goals: doing "my share" in helping to kill off non-cooperators, and stockpiling reputation. (I figure that once the non-cooperators die off and the cooperators take over, it will be better to be near the high end of reputations rather than at the low end.) It turns out that doing my share in helping to kill off non-cooperators causes my reputation to drop gradually over time.

Round 287: 26776 food (31st out of 233), 46.9% reputation (44th out of 233).

My reputation reaches its nadir on Round 287. At this point many of the worst non-cooperators have died off, so I'm no longer having to slack against them; even though my basic strategy hasn't changed, my reputation will now start rising gradually.

Round 613: 19500 food (15th out of 102), 55.0% reputation (24th out of 102).

My food supply reaches its nadir on Round 613. My behavior would have changed if my food had gotten so low or dropped so fast as to cause me to panic, but apparently the world food supply stabilized before that could occur. I continue to stockpile reputation.

Round 1025: 28616 food (20th out of 82), 60.9% reputation (15th out of 82).

My reputation reaches a local optimum on Round 1025. This was a hardcoded turning point in my algorithm; I stop stockpiling reputation "when the world food supply stabilizes, or after Round 1025, whichever comes second". (I didn't want to waste reputation slacking against players who weren't genuine rivals, but I figured that everyone who was still alive at this point was likely to be alive at the end of the game, so there was no reason not to go ahead and start converting stockpiled reputation back into extra food.)

Round 2335: 86711 food (1st out of 75), 54.0% reputation (in a 10-way tie for 37th out of 75).

My reputation reaches a local nadir on Round 2334. On Round 2335 my reputation converges with the reputations of the players who are doing "slack against players whose reputations are lower than mine, hunt with players whose reputations are at least as high as mine". (I've been keeping track of their reputation all game, because it's easy to simulate and because I expected there to be a lot of them.) I'm not willing to let my reputation sink below theirs, for obvious reasons, so I hide myself among them. At this point I'm done converting reputation into food, and am ready for the game to end as soon as possible.

Round 2556: 92421 food (3rd out of 75), 54.4% reputation (in a 10-way tie for 35th out of 75).

The game ends on Round 2556. Unfortunately I've sunk a bit in the ranks. I guess I would have done better by keeping a higher reputation, or at least cashing it in a little bit more slowly; the winner ended up at 97678 food and 57.0% reputation. In case anyone's interested, the nine algorithms which I presume to be doing "slack against players whose reputations are lower than mine" ended up with food ranging from 29829 to 35436. Evan Williams · 3 years, 11 months ago

Log in to reply

My submission ranked first overall and sixth in the game that was posted. My documentation wasn't very organized, so I put a short summary of my strategy below.

My strategy was to come as close as possible to playing the "direct" Tit-for-tat strategy that is so successful in normal prisoner's dilemma games. I played TFT against an opponent only when I could definitively determine what decision that opponent made against me last round via player tracking. Although this is impossible to do early in the game, it is possible in the vast majority of cases late in the game. When I could not determine this information, I would hunt with a player of reputation x only if my reputation was in the top (100x)%. I also included a couple of other features, such as a way to break viscious circles, but I think these ended up having a very minor affect.

I was told that I won only one game, but many of the algorithms that beat me in some games performed dismally in others. I am not sure why this happened - perhaps those algorithms took risks, such as basing their strategy on an estimate of when the game would end, or something similar? I am tempted to say that the optimal strategy is to come as close as possible to playing direct TFT, just as in prisoner's dilemma, but perhaps an algorithm that is very good at taking risks could fare better. Timur Vural · 3 years, 11 months ago

Log in to reply

It is bittersweet to see my algorithm ranking 2nd. Especially, when in the game given above, it has the most food at the end. I wonder whether it performs generally better in longer games as it seems to excel at the end of that game.

Anyway, for those who are interested, here is a code and a high level description of a strategy. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

@Gatis Midrijanis

I wonder whether it performs generally better in longer games as it seems to excel at the end of that game.

I looked at several of the top-performing algorithms, and they all showed a similar pattern of losing food during the first half of the game, only to start gaining food in the second half. Michael Dickens · 3 years, 11 months ago

Log in to reply

@Michael Dickens Yes, but it looks like my food starts to grow faster only after round ~2200. But perhaps it is just a fluctuation. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

@Gatis Midrijanis Your high level description does not explain how you choose your target reputation. Could you please elaborate? Avi Newman · 3 years, 11 months ago

Log in to reply

@Avi Newman Basically, it calculates its target reputation by adding or subtracting a fraction of a current reputation. At the beginning this fraction is 0.2, but it is decreased by half each time my algorithm changes a direction of its reputation change.

In a hindsight this was not probably not the best way to do it. At least I should have chosen a smaller fraction. As one can see in analysis I posted before, my reputation is oscillating at the beginning (my algorithm is 'sba'). I was not able to fine tune it because I had to implement it very fast and didn't want to make any mistakes.

However, I used this targeting only at the beginning of the game and as I argue in my analysis, a reputation at the beginning does not seem particularly important unless it is extreme (close to 0 or 1). It might have been important enough to cost me overall 1st ranking, perhaps, who knows. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

@Gatis Midrijanis It's bitter sweet to take a part in this competition and then realize that my algorithm is not rated (for unknown reason).

Apsveicu ar panākumiem! Toms Bergmanis · 3 years, 11 months ago

Log in to reply

@Toms Bergmanis Paldies!

I hope you'll get to know the reason at least. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

My team's algorithm was the one ranked third overall.

If anyone is interested, here's our strategy. As with many of the top-ranked strategies, we used a variant of Tit-for-Tat. More specifically, we were using Tit-for-Tat with forgiveness. So we would hunt with people who hunted with us the previous round, and for those who didn't hunt with us the previous round, we would "forgive" them (i.e. hunt with them) with a probability \(p\) between \(0.05\) to \(0.10\). The exact formula was \(p = 0.10 - 0.05r\), with \(r\) being our current reputation. The rationale behind this is that if we have a low reputation, then we would forgive with a higher probability to increase our reputation; if we have a high reputation, then we would forgive with a lower probability to preserve food. Other minor details of our strategy include: hunting with everyone on the first round, and not forgiving at all with two players left (this didn't happen though).

So how did my team do player tracking? We basically used the Hungarian Algorithm to do it for us. We can think of the tracking of players as an assignment problem; we need to assign players in round \(k\) to players in round \(k+1\), given only their reputations. It is possible to deduce (from the reputation list) the total number of hunts each player made in the whole game. So for any two consecutive rounds (say, rounds \(k\) and \(k+1\)), we compared the total number of hunts made - it must have increased by between \(0\) and \(P-1\) inclusive. In fact, we also know what each player did to us in round \(k\), so we know the increase in the total number of hunts made must be either: (i) from \(0\) to \(P-2\) if they slacked with us, or (ii) from \(1\) to \(P-1\) if they hunted with us. Of course, there's the possibility that the player died and is no longer in round \(k+1\), so we took that into account as well. So, we just need to input this information into the algorithm and it will output a possible matching between players in round \(k\) and players in round \(k+1\). It is not to say that this must be the correct matching, but there is really no simple way to tell which is the correct matching among all possible matchings (unless we use machine learning or other advanced algorithms).

So, I would say that my team's algorithm was really not complicated at all; in fact it was so simple that we were pretty surprised it came up third! Derek Khu · 3 years, 11 months ago

Log in to reply

My submission and write-up may be found here. I used a very simple algorithm that simply tries to keep its reputation at or above 0.6. It came in 6th place (much better than I expected!).

This strategy is much simpler than those used by the players who ranked 1st, 2nd, 4th, and 9th (these players have described their algorithms below). I wonder if any of the other top-scoring players had very simple algorithms? Michael Dickens · 3 years, 11 months ago

Log in to reply

I notice that there are some groups of players with the exact same reputation. For example, players 2rI, Z4r, and ni6 all end with the exact same reputation. I wonder if they were all using the same strategy. Michael Dickens · 3 years, 11 months ago

Log in to reply

@Michael Dickens Noticed it too. It looks like they have similar reputations in every round.

Even bigger clique is 5Re, AEM, 0is,xGb,E87,rPM,Ig1,c9Y,8WM,Df0 with the same reputation at the end. All of them, except AEM, gang up from the very start, but AEM joins at the end. Maybe they all are using the same simple strategy? Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

why my submission haven't been taken into account? My index is FJI Leonardo Daher · 3 years, 11 months ago

Log in to reply

Here's my first attempt at visualizing the raw CSV data

Please note that the CSV file takes a minute or so to dowload. You can filter /pan portions of the individual graphs to see how the game played out. Even though I didn't win, I had fun making this!

Screenshot 1 Screenshot 2 Nachiket Apte · 3 years, 11 months ago

Log in to reply

@Nachiket Apte In that screenshot, what does the vertical axis represent? Michael Dickens · 3 years, 11 months ago

Log in to reply

@Michael Dickens The Y-axis in all graphs represents the number of live players. Nachiket Apte · 3 years, 11 months ago

Log in to reply

I did a crude analysis of the given game, about performance of typical players and top players, with some graphs. You can find it here.

My conclusions: it seems that the most important thing is an asymptotics: how to play after mass extinctions when selfless gandhis and selfish scrooges mcducks have left the game. Also, the total number of rounds of a game seems to matter a lot, which is a pity because a probability distribution of it was not given. It well might be the case that some players do better in longer games, but others in the shorter ones. Gatis Midrijanis · 3 years, 11 months ago

Log in to reply

Really pleased to find out I was 9th! I was told in my interview that the top strategies seemed to maximise slacking yet maintain an accpetable reputation of around 0.5, which is luckily what I was going for!

If you're interested I'm userindex xxG. I gave an overview of my strategy in a comment here: https://brilliant.org/discussions/thread/hunger-games-strategy-week-free-for-all/?sort=top#comment-a3f516063e92 but for more detail here's my official documentation: https://brilliant.org/usermedia/hunger-games/GuKsDXjHZZ-user-132275.pdf

Thanks so much to the organisers for such a fascinating challenge. It's been great hearing all the different approaches, I've really enjoyed the discussion as well as the game itself. Looking forward to the next one!! Rosie Campbell · 3 years, 11 months ago

Log in to reply

I've noticed a pattern among the top strategies. Their food drops during the beginning of the game down to about 10,000 to 20,000, and then starts going up again and makes it back up to 80,000 or 90,000.

It seems as though the top strategies are those that do somewhat poorly at first but then do well once most others have died off. Of course, if strategy A drops to 10,000 and strategy B drops to 0, strategy A is better; so it's possible that the winning strategies lose food more slowly than others. (This question is answerable with the data we have, but it requires a more detailed analysis.) Michael Dickens · 3 years, 11 months ago

Log in to reply

@Michael Dickens I haven't looked that closely at the data overall, but I did track mine throughout the sample game. For reference, I was the 12th place entry running a simple Tit-For-Tat algorithm (outlined here).

One thing important to note is that in a sufficiently hostile environment (that is, one where many players are slacking), everyone will lose food. The best strategies will just lose food more slowly than the worse ones. My relative ranking seemed to reach the top 50 pretty quickly, and hovered around the 40s until food started increasing (at which point it slowly climbed in the rankings until ending at 14th) Chad Miller · 3 years, 11 months ago

Log in to reply

Hmm, I was checking the indexes of the top few players to see their data and I couldn't find any entries with the third-place user_index, 3nD. Where'd it go? Brian Chen · 3 years, 11 months ago

Log in to reply

@Brian Chen It was in our "slow" group, so got tagged with "slow" at the beginning...it may have gone into this list as slo then. David Mattingly Staff · 3 years, 11 months ago

Log in to reply

I may write something to spit out matplotlib graphs for this. In the meantime, if you want to see your own turns only:

import csv

me = raw_input('Enter your 3-character identifier: ')

with open('HG_rundata.csv') as infile:
    data = csv.DictReader(infile)
    for line in data:
        if line['user_index'] == me:
            print(line)
Chad Miller · 3 years, 11 months ago

Log in to reply

@Chad Miller Quick-and-dirty version for the command-line junkies (replace aaa with your own identifier, natch):

sed -n '/aaa/p' HG_rundata.csv

Plot your food (for reputation, replace $3 with $4):

awk -F ',' '/aaa/ { print $3 }' HG_rundata.csv | gnuplot -p -e "plot '-'"

(I don't think there are any identifiers that are all numbers or are part of the first line, so these should all work fine for this data file, even if not in general.) Brian Chen · 3 years, 11 months ago

Log in to reply

Are we ever going to learn what any of the top algorithms did, particularly the #1 ranked? I for one have been very curious from the start whether there even are any high-quality general solutions to this problem (like Tit-for-Tat in the original IPD), or whether success reduces to the luck of being stuck in a tribe that happens to flatter your strategy.

For instance, I'm guessing if this contest were run again tomorrow with just the information we have now, a vast swath of entries would always slack with everyone whose reputation was in the range \( [0.5, 0.6] \). Would any of the top 5 still come in top 5 then? How many of the current crop of survivors would still survive?

Not trying to take anything away from the contest or the winners, here. Well, not much, anyway. I am disappointed to learn that Brilliant didn't conduct any kind of N-fold cross-validation of sorts, where each submission was run against different subsets of the whole population. In my analysis and experiments, it didn't seem there was any algorithm that consistently performed well in every tribe. In fact, many strategies seemed to be very sensitive to the particular tribe they were in.

I guess what I'm asking for is some closure to the problem itself. Christopher Johnson · 3 years, 11 months ago

Log in to reply

@Christopher Johnson Why would slacking against reputations on [0.5, 0.6] be a winning strategy? Michael Dickens · 3 years, 11 months ago

Log in to reply

@Michael Dickens The idea is to slack against the people you believe will be in the lead while hunting with the losers to keep your reputation up (thus encouraging players to collude with you) Chad Miller · 3 years, 11 months ago

Log in to reply

David, my index, j43 is not on the list which would explain why I didn't receive an email. The question is - why my submission haven't been taken into account?

Thanks Tom Toms Bergmanis · 3 years, 11 months ago

Log in to reply

can you give us conversion factors ? Ramoj Tuazon · 3 years, 9 months ago

Log in to reply

Hi, my full user ID is oC2MWfwcUG-user-246.py and oC2 is not on the list. I sent an e-mail but didn't receive a reply. Can I please know what went wrong with it/why it wasn't taken into account. Thanks! Grace Li · 3 years, 11 months ago

Log in to reply

Have you determined the finalists yet? Are you going to announce them publicly? If so, where? Michael Dickens · 3 years, 11 months ago

Log in to reply

Beware in the CSV data, two players are named FIX and three players are named GRO. Just in case you'd want to parse the file but got weird results. Marc Dupont · 3 years, 11 months ago

Log in to reply

If my bot played correctly at the first round- but started to slack with everyone in the rounds after that, which should I assume- my code broke/froze, or ran correctly but gave output as "slack with everyone"? Btw, for the first round I used a different algorithm/code piece(with if/else), and my code ran correctly in the official tester and also Chad's checker. Nur Muhammad Shafiullah · 3 years, 11 months ago

Log in to reply

@Nur Muhammad Shafiullah And it worked quite well with the official tester too, it did what was supposed to do in the rounds after the first (did not give all slack). So why did it slack with everyone after round 1 only? Nur Muhammad Shafiullah · 3 years, 11 months ago

Log in to reply

@Nur Muhammad Shafiullah My simulation unfortunately didn't have code to check the length of the output. So if your algorithm was returning a list of length != (P-1), then that would explain this behavior. Chad Miller · 3 years, 11 months ago

Log in to reply

@Chad Miller Nah, I ran simulations with the official one too (and that had the part you mentioned), so I do not think it was that. It might be because I used a condition like if some_float in some_float_list: , is it a problem in python? Nur Muhammad Shafiullah · 3 years, 11 months ago

Log in to reply

@Nur Muhammad Shafiullah That condition will be true iff any object in somefloatlist is equal to the object some_float. Is that what you wanted? If you're dealing with player reputations, I'm guessing it's not what you wanted, since there are a lot of possible reputations, so it's unlikely that there will be an exact match unless you're looking for a 0 or a 1. Christopher Johnson · 3 years, 11 months ago

Log in to reply

@Christopher Johnson Yeah I did want that, because some_float was a float from reputations_list, ( takes as like the loop for some_float in reputations_list). It was too bad my code crashed,as I submitted some TFT not unlike Timur V. himself, and it'd have been nice to see how it did. Nur Muhammad Shafiullah · 3 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...