Hunger Games - Moar data!

When is the next programming challenge? I am not so much interested in hard math problems.

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.

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.

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.

why my submission haven't been taken into account? My index is FJI

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.

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?

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!

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

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.

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)

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?

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.)

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!!

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.

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

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.

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.

Have you determined the finalists yet? Are you going to announce them publicly? If so, where?

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!

can you give us conversion factors ?