Hunger Games - Strategy week free for all

My player uses the following very simple (tit-for-tat-esque) strategy: on the first turn, hunt with everyone. Then, if k people hunted with me on turn n, hunt with k random people on turn n+1.

This has the nice property that after the initial investment of hunting with everyone on the first turn, we can't do any worse than slacking (the extra food it takes to hunt with k people on turn t is balanced by the k people that gave me food on turn t-1). On the other hand, if there's a clique of high-reputation players that hunt with each other, this player will naturally fall into this clique. Moreover, by distributing the hunts randomly, we remove some of the advantage the colluding players have (ideally, we would spend our hunts on the players with the least amount of food, but it's hard to keep track of these players, so hunting randomly seemed like a good secondary option).

Overall, it's kind of a "best-of-both-worlds" situation; we're guaranteed not to do much worse than any slackers, even when everyone is a slacker, but we can also sneak our way into groups of colluding players (while giving away all of their food). It's not perfect - ideally, there'd be some learning to know when we can undercut and reduce our reputation further (i.e. hunt with fewer than k people on turn n+1) - but hopefully it is good enough for a t-shirt.

I based my algorithm on the following premises:

1. No point hunting with players who are very unlikely to hunt
2. No point hunting with players who are very likely to hunt
3. Need to build up a reasonable reputation to encourage players to hunt with me
4. More likely to hunt when m is low (so there is a realistic chance of achieving the public good award)

To address the premises 1 and 2, I started with a Gaussian probability distribution. I would hunt 'randomly', but it would be weighted according to my opponents reputation. So at very low and very high reputations, I would be very unlikely to hunt. The greatest chance of me hunting would be around the middle. This is a achieved with the equation (the 0.5 shifts it to centre around 0.5 and the 4 squishes to be between 0 and 1):

$hunt\_probability = \frac{1}{e^{((rep-0.5) \times 4)^{2}}}$

However, I wanted to reward players that hunt and punish those that slack. I therefore altered my probability distribution by weighting it in favour of those with good reputations. I did this by adding the opponent's reputation to the above probability distribution and dividing by 2:

$hunt\_probability = (\frac{1}{e^{((rep-0.5) \times 4)^{2}}} + rep) / 2$

To address premise 3, I assumed most strategies are likely to punish slackers (i.e. players with a low reputation). To avoid this punishment, I aggressively ramp up my hunt_probability when my reputation falls below 0.5. this is achieved by adding the following to the previous equation:

$0.5 - current\_reputation$

This stops me getting starved out by players who will only hunt with those who have a high reputation.

I address premise 4 by keeping track of the proportion of hunts relative to interactions over the entire game, and increase hunt_probability by a small amount when m is lower than the average of this.

I made the strategy less forgiving by adding a hard cut off at each extreme: If a player has a reputation < 0.2 or greater than 0.9, I will certainly slack (hunt_probability = 0).

To have a look at my probability distributions, see http://fooplot.com/plot/fexxqzxw4f

The pink line represents a pure Gaussian, the dark blue represents my weighted version (that I used in my strategy) and the green shows the ramped up version used when my reputation falls below 0.5.

A lot of people have mentioned that slacking or 'freeloading' appears to do very well, according to the bots in Chad's testing framework (which was excellent, thank you Chad!). This is only true when it plays against very simple strategies that don't punish players for slacking. My strategy relies on the idea that slackers will be starved out by other players. So I'm hoping that the simplistic bots in the testing framework may have led people to believe that slacking is a good option, and I can take advantage of this!

With more time I'd have liked to implement some machine learning techniques (I'm sure my strategy will crumble compared to more sophisticated ones that use ML or ANN!). Ah well, it was fun to have a go!!

I'm quite surprised nobody is talking about sorting the players by reputation and then assigning to each one the same behaviour obtained by the player that occupies its position in the previous round (i.e. hunting with the i th player if the i th player of the last round hunted with you and slacking the j th player if the j th player of the last round slacked you).

For me this is the most straightforward way of implementing the Tit for Tat strategy under the constraints of this contest (I even call it Fuzzit-For-Tat!).

Has anybody walked this path? Any thoughts about it?

My algorithm first tries every possible reputation rounded to .01 in a certain range, to see which one has the highest gains. After it's gone through that range, it picks the reputation with the highest gains and hunts with the frequency to reach that 'ideal' reputation.

I've posted my documentation online: <http://chill-dream.com/TitForTat.html>

I had a far cleverer idea in mind but there was some fatal algebra or logic error somewhere that I still haven't found. So instead I just ended up with a boring unexploitable (but unexploitative) Tit For Tat algorithm.

I went through many iterations.

1. Boneheaded interpretation of Tit-for-Tat (called CjTitForTat). Basically, hunt with at least the top-reputationed 50% of players (be generally cooperative), and hunt with anyone else with a reputation > 0.5 (cooperate with those who seem to be cooperating). Ultimately decided this was a stupid interpretation of Tit-for-Tat, but in my throes of last minute helplessness and despair, I almost submitted a version that used 60% and 0.8, since that tended to do the best of the pack for reasons that are beyond my desire to analyze. (Indeed, it scored #1 overall with its pack to back it up.)

2. Super-simple algorithms. First there was Bro, who hunted with everyone whenever the average reputation of the tribe was > 0.5, and slacked with everyone otherwise. (Bro follows the crowd.) Even unto the end of this contest, this dumb algorithm that I came up with after reading half the rules and understanding half of what I'd read /still/ managed to win more than half the hostile-tribe (food tending towards 0) play-outs. I actually grew to hate Bro. Then there was Hipster, who did the opposite of what Bro did. (Hipster bucks the trend.) This guy was almost always the first to die off in hostile populations. Then there was GoWithTheFlow, which was Bro, but who recalculated average tribe reputation each round, based on foodearnings (Bro just averaged all playerreputations together, similar to AverageHunter). This was intended to respond more quickly to changes in the tribe dynamic than Bro. It tended to do about as well as Bro. Then there were many variants of these algorithms with different parameters (cut-off between hunting and slacking). For reasons I had neither the time nor ability to understand, 0.5 tended to be the best whenever any of these algorithms did well (which was only in hostile tribes).

3. Game theoretic algorithms. Okay, I was getting serious at this point. I actually looked at the payout tables and crunched some numbers. My idea was to maximize my reputation, but do so rationally--only buy reputation (i.e., hunt) when it would not cost food (i.e., when the average payout would be >= 0). There were four of these algorithms, based on two binary categories. The first category was whether to hunt/slack the whole tribe at once (Grp), or hunt/slack on a player-by-player basis (Ind). The second category was whether to average in hunt bonuses (Bna), or use m to try to predict them (Bnp). To predict a hunt bonus, I multiplied each players reputation by P-1. If the result was >= m, a bonus was predicted. Since a hunt bonus essentially adds 2 to each payoff in the table, it lets us rationally buy reputation for more low-reputationed people. RatRepGrpBna hunted with everyone if the average reputation (ravg) was >= 3/5. Else, it slacked with everyone. (In other words, it was basically Bro with a 0.6 parameter instead of 0.5.) RatRepGrpBnp: If no bonus, hunt with all if ravg >= 1 (yes, if everyone has a reputation of exactly 1--so, basically never); if bonus, hunt with all if ravg >= 1/3. Else, slack with everyone. RatRepIndBna hunts with any population member whose reputation is >= 1 - 2/3*ravg, and slacks with that member otherwise. Finally, RatRepIndBnp: If no bonus, hunt with each player with a reputation >= 1 (yes, only exactly 1); if bonus, hunt with each player with a reputation >= 1/3. Slack with everyone else. These algorithms did so-so. The problem, I think, is that they fail to factor in the worth of reputation. At the extreme, if no one cares about reputation, you shouldn't buy it even if you can do so at >= 0 food earnings. If everyone cares about reputation, you should buy reputation even if you have to do so at < 0 food earnings sometimes. Nonetheless, I was most proud of these algorithms and the time I'd put into researching them, and thought about entering RatRepIndBnp, the most complex one, out of spite (not for the competition, but out of reality, for not letting my beautiful algorithms work!).

4. Adaptive algorithms. This was a series of algorithms that attempted to adjust our reputation (or, in simpler cases, how many individuals we hunted with vs. slacked with) based on the payouts we were getting. The most successful of these, PushPull, typically managed an over 100,000 food lead over second place in a friendly, rep-caring population of around 90 members. Sadly, it took about 2000 rounds for it to do this, and by round 15000, it started slipping from first place and into the middle of the tribe. Also, PushPull typically died about half-way through any hostile-population run. Sadly, I didn't have the time (or probably, ability) to work out the kinks in PushPull, since it was probably the closest I came to an algorithm that could take first place.

5. What I actually submitted: Copycat. This is yet another Tit-for-Tat variant, this one truer to the original Tit-for-Tat than CjTitForTat was. It has three basic rules: 1) Hunt with everyone on round 1. (Like Tit-for-Tat's "cooperate on round 1.") 2) Else, if <= 50% of people hunted last round, slack with everyone. (A crude, group-level "defect against defection.") 3) Else, do what everyone else did last round. Literally, food_earnings is converted into a list of 'h's and 's's, trimmed to account for deaths, and fed right back into the population as our actions for this round. (A group-level, literal interpretation of "repeat what they did last round.") I have rule #2 instead of letting rule #3 absorb it because I found through testing (and Bro's aggravatingly good performance) that an average reputation <= 0.5 tends to be highly correlated with a population's being hostile, and in such populations, it's best to always slack. The implementation of rule #3 was mainly to be cute and get style points--the idea came from a one-liner someone entered into an old Rock-Paper-Scissors tournament. In retrospect, though, it turned out to be a very clever way of interpreting Tit-for-Tat's "I do what you just did" behavior.

I really, really wish I'd simulated my bot with others. I have no idea if the weights I put on the different sections of my algorithm are right, and reading the comments here I'm not sure I even analyzed the game correctly now.

This is something I thought about during the competition, and maybe could qualify as a "question #5":

In general, should an ideal/optimal strategy for this game implicitly collude with copies of itself?

On the surface, it seems the answer must be "yes." After all, if a strategy does not collude with copies of itself, then the more copies of that strategy there are in the population, the lower they'll all tend to score. The strategy becomes its own worst enemy! If it does collude with itself, then adding copies of itself to the population at the very least doesn't hurt it, and might even help.

Although strategies can't spawn copies of themselves in this particular competition*, clusters of people seem to have independently come up with very similar strategies. Such clusters of strategies that don't implicitly collude with each other may end up bringing everyone in the cluster down!

• Although, that'd be an interesting idea for a spin-off! There'd need to be some way of limiting the growth of the population, though. Maybe making it so that hunt bonuses don't scale up with population size might do it? Score = sum of food of all copies. Spawning would cost food. Etc.

My hypocritical strategy was to pretend to be a cooperator, and enjoy a good reputation, while secretly sabotaging my fellow cooperators. It's a strategy that works for politicians, so why not here? I start by calculating an ideal reputation. If I were to cooperate with other cooperators, what would my reputation be? I then make sure to maintain my reputation with the appropriate number of hunts. The hypocritical twist is that I do not actually cooperate with the other cooperators. I slack against them, while hunting with the slackers. Why would it be beneficial to do this? If I slack against a hunter I earn +1 food, and if I hunt against a slacker I lose -3 food. This equals out to -2 food. What if I had been honest and cooperated with the hunters and slacked against the slackers? I would earn 0 from the hunter, and -2 from the slacker. -2 = -2, so these two strategies are equal. However, I am benefiting by being a hypocrite in two ways: One is that I am hurting the other cooperators, moving me ahead. The second is that some of the slackers may actually hunt with me because of my reputation. In that scenario I would get +1 from the cooperating hunter that I slacked against, and then 0 from the slacker that decided to hunt with me. Part of my strategy is to pick out the slackers most likely to hunt with me on occasion, so I will hunt against the slackers with the best reputations. This competition really got me thinking. This was the fifth strategy that I developed, and I kept this one mainly because of the parallels with nature.

In the first place, I only heard about the competition last Thursday, and only started coding my actual strategy the day of the deadline, as the day before I had tried to come up with an overcomplicated plan for the length of time I had to develop it. :P The deadline extension would have been a lifesaver, had I actually finished debugging it and got it to work for more than one round, so you will not be seeing me in even preliminary rankings, I think.

The more complex strategy I had planned was a specialization in the game's domain of the general AI I am perpetually planning. I will not share details of this AI's design. I thank brilliant.org for turning me on to the superior development speed and high-quality libraries of Python. I had always disparaged it before, but the competition being in Python was the reason I was able to develop a relatively complex strategy so quickly. If I had heard about this competition when it started, or at least a week before the deadline, I might have made a better showing (i.e. any showing at all).

The less complicated strategy I developed [would have] used several calculations to get some most probably salient data streams from the information given. To list all the data I [would have] used:

• performance, or the derivative of food per round.
• The ratio of my food to the tribe's food, depicting the percentage of the total food I owned.
• Repute, the sequence of my reputation per round, of course
• Trust, or the percentage of people who cooperate with me each round
• A big one: Despite, or the difference between Repute and Trust. For example, a reputation of >0.95 would probably be exploited pretty quickly, which would inspire moving downwards.

These data streams would all be correlated with repute to give the weights each data stream's current value would have to make a calculation of the desired reputation, and thus the desired number of defections in the strategy.

As for deciding which people to cooperate/defect with...

scipy.stats.gaussiankde was my friend. There was no other tool to help me get an estimate of a continuous probability density function from the discrete data provided. For every round, I would add in the reputation distribution and the hunt outcome associated with each, if they cooperated or defected. It was sorted by time, and the amount of food I currently had affected how many samples I drew from the database, or the short-sightedness of the prediction, essentially. I would take a large amount of the most recent rounds, (should have been up to fifty or so, but the amount of food affecting the short-sightedness had a bad calculation, like antilogarithmic growth divided by a smaller antilogarithmic growth) draw up a distribution of the cooperation instances normalized by distribution of population, which gave the predicted probability density function for the current round. I would order the playerreputations by the given predicted likelihood, then defect against those least likely to cooperate, up to the optimal limit of defections given by my desired reputation. I wasn't able to implement betrayal of extremely likely cooperators in time.

To the given discussion questions:

Why does always slack not necessarily win?

Slacking is of course the Nash equilibrium. However, in a dwindling-resource game such as this, it is not a successful long-term strategy, as well as supremely ineffective if everyone always slacks, as in the tragedy of the commons. Everyone always hunting is the superrational equilibrium, and is the most sustainable strategy, a "success of the commons," as it were. Everyone gets a constant food growth from the m reward, and no one dies forever. A bot that always slacks would gain food equivalent to the number of their hunts, in other words, half of the reward. But this game has reputation in it as well, and a strong 1000USD incentive to win, which means that bots can be tracked, and there is a high likelihood that people will enter smart bots instead of 0th-level players. The reward complicates things in a smart-bot reputation game. Ultimately, the smarter thing to do is to cooperate as much as possible to increase the likelihood of the reward as well as the value of the reward, while defecting as much as possible on likely defectors to prevent unrecoverable losses, and on likely cooperators to get a leg up on other competitors. Then there's metagaming above that, player tracking, the applications of machine learning and other adaptive affectors, and so on.

How does one identify individual players and play tit-for-tat or other colluding strategies? Can one even?

Player tracking. This was going to have been part of my more complicated model, in cooperation with a strategy analyzer to predict likelihood of cooperation in a smarter way. I believe it is possible. As this comment states, a player can move their reputation only so far in one round. I used this in part of my desired repute routine, though not as effectively as I would have if I had more time. I was also originally planning to use this as an indicator/perceptor in the more complicated player. Each player_reputation given would be assigned a connection to other possible reputations in the last round, with weights, as in a graph formation. As reputation stabilized, it would become a very reliable indicator of past identity (not empirically tested, but it is my prediction), and would contribute as another heuristic to strategy guessing, probability of cooperation given reputation, optimal action, etc. It would get less accurate with more players, but it would still be useful in the endgame, as the number of players thinned out, and reputations stabilized even more.

Colluding would require the use of outside communication, obviously illegal, or Schelling points. An obvious Schelling point would be a reputation of 100%, but how to verify that it is due to plotting collusion instead of dumb luck or dumb strategy is not as clear. Still, for bots who can track one another, making yourself distinguishable by being on the high end of the distribution for a period of time suitable to stabilize your position/trackability is the true Schelling point in consideration. Working out a strictly numerical solution would not be best, it would not result in as many collusions (given that you have the exposure to other colludable bots), and the others would be better off for it as you would have less ability to influence game outcome.

Then it comes to betraying alliances. Metagaming to the $meta^{meta}th$ power. 9_9

What is the purpose of m? It adds to everyone, so what difference does it make?

The difference is in the weighting. From the rules, it is twice the amount of times you've hunted, I believe. This is strong enough to motivate a smart game theorist, I think, as it rewards cooperation, more than individual rewards for defection would influence the decision, all things being equal, and it would also be a motivator to trick others into not hunting as much while still getting them to add to m's likelihood of success. It wouldn't recoup losses at less than or equal to a 2/5 betrayal ratio, and that wouldn't be enough to recoup the losses from its mutual defections. M is still a big thing to take into consideration, though, as it pushes permaslackers further down the winning scale into no-fly territory. Given smart enough algorithms, of course.

Is it better to construct a really good fixed strategy via game theory, or try a bunch and evolve the strategy over time (machine learning)?

Given a month, wouldn't someone be able to construct a machine learning-principled bot that can analyze its opponents for use of game theory, near-perfect or flawed, and then exploit the resulting predictions? Also consider that the population of the tribe will not consist of a predictable group of strategies, so at least some method of perception must be utilized for even a fixed strategy bot.

That said, I really wished I had heard of this when the competition was announced. ;_; I hoped to leverage this particular contest into making me a small amount of money to buy a laptop of my own. I'm always using someone else's...

Lot of interesting stories here, accompanying the strategies. I, too, wish I had heard about this competition (or indeed, even this site) earlier, but since I was busy with summer classes/exams anyway, it likely wouldn't have mattered. I ended up implementing my solution on the 17th and 18th. Here's a quick summary for those interested:

My approach is based on machine learning, I suppose, though I didn't use that term in my README. (It didn't sound sophisticated enough for that label, haha.) Basically, it builds up data on past player behavior to aid in the choice to hunt or not. In particular, I implemented calculations for the probability of getting the award, as well as the probability of opponents as a whole to hunt, refined round by round. Award probability, since it is highly dependent on the random m integer, is used sparingly, only in the calculation of expected food returns from future rounds. Hunt probability was used to estimate the amount of hunts that could be expected from any one round. It was only used in my "Food Opportunist" algorithm (more on that below).

The solution has a few extra features. For example, I called my script "FourFaced", due to the four main algorithms I implemented, representing four complementary play styles/personalities (get it? It's like TwoFaced, but...more). The aforementioned "Food Opportunist" plays offensively, attempting to score the most hunting awards possible, slacking otherwise, but ignores food and reputation. The "Indifferent Observer" bides its time, attempting to keep these values stable, in order to better collect probability data. The "Social Climber" and "Frugal Survivalist" are emergency correction algorithms, designed to quickly accrue and/or stabilize low reputation and food, respectively. The former always hunts, while the latter relies on a safer but less paying version of the "Food Opportunist" algorithm.

(You'd be surprised how much thought I put into those names. I may get my butt handed to me in the competition, but at least I might win points for creativity :) )

There's some more logic in switching between these strategies as well as a few "safety measures", but I've chosen to keep the specifics out for now so as not to crowd up space. If anyone is interested in more, this would be as good a time as any for me to figure out where to post READMEs online...-_-

In any case, it was quite fun to come up with solutions for the challenge. Thanks for the opportunity, Brilliant, and good luck to everyone (even though that's not technically possible in a game like this)!

Hey everyone! My partner Justin L. and I created an algorithm that does not rely on any assumptions other than the rules of the game.

The algorithm features a few cool aspects:

1) Iterated linear regressions (partial correlation method) for maintaining the optimal reputation.

2) Recursive opponent tracking and collusion with individual players

3) Hunting with weak players, slacking with strong players.

4) "Wasting" our reputation by the end of the game to gain maximum benefit from it.

Feel free to take a look at our write-up here, and tell us what you think! If you want to take a look at the code (about 800 lines of it), we'd be happy to share that too.

I used simple mix of game theory, VERY simple machine learning (which may not be learning to the letter), weighting and tiny pinch of strategies. No idea how it will perform against other smart/unique algorithms but it was the winning one among dumber algorithms during my brute-force tests. Just curious here: Did anybody use ANNs? Would be interesting to see how those perform even tho they may need lots of training.

My program bases its strategy off the assumption that people will give hunts to people who have hunted the most previously. (which it seems like is true for most strats_

First, it determines how often people give out hunts, on average.

Then it determines how many times it would have to hunt to be in that top percent. (so if people hunt 30% of the time, it tries to get in the top 30% of the reputations) Lastly, it tries to get to that amount of hunts.

My answers to the starter questions:

1. Always-slack fails if more than 1/3 of the tribe refuses to hunt with it. Slack-slack gives a -2 payout, while slack-hunt gives a +1 payout. If s is the fraction of the population who slacks with us, we have an expected payout of s * -2 + (1-s) * 1, which simple algebra shows is < 0 when s > 1/3. (Hunt bonuses don't really change this fundamental weakness of always-slack--they just mean always-slack is less likely to die, but it'll still place lowly.)

2. To identify players across rounds, you'd have to wait for (and count on) each player's reputation to converge to a mostly fixed value, then try to map reputations to individual players. Since more than one player can have the same reputation, this is already an uncertain process. Further, not everyone will converge to a particular reputation. It was my belief from very early on that tracking player was too complicated, too error-prone, and, considering the utter simplicity of the strategy that won the original Prisoner's Dilemma tournament, probably a waste of time. Someone may well prove me wrong on this, though.

3. The purpose of m, and the hunt bonuses, seems to be to cancel the base -2 payout. That is, the expected payout of a play can be expressed as payout(rthem, rme) = 3*rthem - rme - 2, where rthem is their reputation and rme is mine (and assuming that we hunt or slack randomly). So, their hunting is worth +3 to us, and their slacking is worth 0 to us. Our hunting is worth -1 to us, and our slacking is worth 0 to us. The base payout is -2. When a hunt bonus is awarded, you get +2 food for everyone else in the tribe. This effectively cancels the -2 base payout, giving a second payout table. It makes a difference if you're trying to accumulate as much reputation as possible at as little cost to yourself. Whenever there's a hunt bonus, you can hunt with more people of lesser reputation and not take as much of a hit. Also, hunt bonuses allow the game to go on forever, a benefit to algorithms that take a long time to hit their stride.

4. Due to the very simple, fixed solution to the original Prisoner's Dilemma contest, and how it beat a bevy of more sophisticated, machine learning-based algorithms, my belief throughout most of this contest is that a good, simple, fixed strategy is best. I came to believe (too late) that a strategy with some form of machine learning will probably take first prize, though, since mapping personal reputation to actual payouts seems to be the secret to consistent success. However, I'm looking forward to being blown away and proven completely wrong on this. It certainly won't be the first time!

Our strategy assumes that more reputation --> more people will hunt with you.

It spends the first 5 rounds only hunting, and the rest of first 30 rounds hunting so that its reputation would remain in the top 10%. (because the first few rounds will have the longest impact on reputation)

Afterwards it's allowed to drift towards the median reputation, while every round making a calculation taking into account the gains from last 3 rounds, reputation change with respect to the median, and food gained from others with respect to the average food gained by everyone, and expected number of rounds left (based on average food gained by everyone and amount of food I have). (Basically taking a derivative of expected number of food gained due to reputation with respect to hunts spent) This calculation will show whether it is more worth it to increase reputation next round with respect to the median (by hunting more) or lower it (by slacking more).

When picking who to hunt with, it hunts with the people with the most reputation and the people with the least reputation, because both populations are considered most likely to die (so that the food given out can be wasted).

Since we only had a few hours to code this, some constants will need adjusting and we could not test it out adequately. In addition, we made 2 bad mistakes in the code that made the implementation different from what we expected: 1. We forgot to subtract out the gains from our own hunting decisions from the gains-from-other-people we used. This would have a net effect of us hunting more than we should. 2. We put the number of rounds remaining on the wrong side of our inequality, and we forgot to correct for when the number of rounds remaining would come out negative (meaning we would survive indefinitely). This means our entire effort in this calculation was pointless.

So, since the calculations are pointless, the features that did work would end up making this implement a similar concept to Chad M's mole strategy (in terms of giving hunts to people most likely to die) as well as someone else who mentioned that the first few round are most influencial in terms of reputation.

I would like to see someone provide a good answer to #3: What is the purpose of m? It adds to everyone, so what difference does it make?

For my strategy, it strongly influences the calculation in the number of rounds that are expected to remain. More remaining rounds would increase the value of raising reputation, as the higher reputation is expected to last longer. Less remaining rounds would decrease that value and make it favor slacking, as there is little gain in using up 1 food and giving out 3 food in hopes of potentially gaining 3 that it might otherwise already receive.

I chose to monitor hunt threshold, average opponent reputation, my accuracy, and the streaks of accuracy. By using streaks I could determine if I needed to reverse course or size of adjustment. This allowed me to dynamically change the amount of times I hunted or slacked to give myself maximum hunt reputation without losing consistent rounds (losing was defined by my accuracy). The idea was to make others believe you will hunt. The only way to do that was to have a better than average reputation.... I just want the shirt....

My group's first concern was making a simulator to emulate the game conditions as laid out in the rules. We were all most comfortable in C#, so we created a game simulator that would take any implementation of IPlayer and run it through the game, with modifiers for duplicates of a player instance, and a max number of rounds. Of course, there's a risk here of misinterpreting a rule, but we all gave it a quick code review and hopefully got somewhere close with the game implementation.

After we had that set up, we just started throwing player implementations at it. We had the few simple ones that were given as examples (random, always hunt, always slack) and started looking at how they compare against one another. Then as a team we just started throwing different ideas into player implementations and saw how they stacked up against all the other players.

We tried really complicated algorithms, we tried quick and dirty ideas. After it was all said and done, after simulating thousands of games we had 3 approaches that seemed to do well against an Always Slack player (what we considered our benchmark, since it won more often than not):

1) Hold a Grudge: quite simply, if you had a net loss of food last round (including possible bonus), slack.

2) Karlee (named after its author): (almost always) hunt until you have the highest reputation out of the group, and then slack the rest of the game. This was based on the idea that once you have more food than an AlwaysSlack player, you can just slack and outlast them because you have more food.

3) Hunt If Hungry: if we lost food last round, or if we go below our starting total of food, hunt

It's entirely possible that these three player implementations are only successful in our specific environment - with the other player implementations we've introduced, or with our (possibly wrong) interpretation of the rules, but they're the top ones we came up with :)

So far I have not seen anyone making use a reputation groupings system to determine the course of action against a specific group.

My algorithm's core idea is to group the public into 20 different reputation groups, the 0.00-0.05 group, 0.05-0.10 group, 0.10-0.15 group, and so on. Then I will proceed to calculate my cooperation probability depending on how people from that group did previously.

While there may be different algorithms within the same reputation range, I suppose this will separate cooperative people from non-cooperative ones, at the very least. Now that I am aware that tit-for-tat is the most tested algorithm for prisoner's dilemma, I suppose this groupings technique will help a lot in deciding which players slack against you?

As for question number 3, I would argue that m makes a difference for people struggling to survive; that is, to buy time to get a t-shirt. As mentioned by the rules, there is no maximum number of survivors, and there is a fixed rule for the number of rounds. Hence, when we realize that our strategy is failing, we can switch to a 'survival mode' and we should aim for m whenever it is feasible to be achieved. As for me, my survival mode will take the number of hunts from the previous round (hunts by myself excluded) times a factor (of 0.9, this was decided by trial and error), and compare it with the value of m. If it is greater than m, I feel that I do not need to make that extra hunt. If it is less than m and my extra hunts can contribute (and there are people who are likely to cooperate), I will go for the hunt. If the margin is too large, I will stick to my standard hunting system.

I also have an unfinished feature due to time constraint: Detecting when you are being ostracised by the society. This is when people hunts in general, but you are not getting the hunts. Likely to happen when rep is too low I suppose. A great ostracization detecting algorithm to prevent starvation would be great, but also risky. I would love to hear from anyone who have thought of this feature.

Lastly, Good Luck for the competition people!

it looks like the conversation venue has shifted:

http://brilliant.org/discussions/thread/hunger-games-the-story-so-far/

My algorithm formulates the expected hunting value for a round based on player reputations. It then does the required hunts (if any possible) to reach m. Based on how accurate its prediction was to the number_hunters at the end of the round, it refines an index that the expected hunting value is multiplied by in order to get the expected number of hunts.

I submitted an incredibly simple strategy, inspired somewhat by the success tit-for-tat has with the standard iterated prisoner's dilemma. It took me 22 lines of code, most of which is white space. The main (and only) logic is described by a single if statement:

for reputation in player_reputations:
    if reputation >= current_reputation:
        choice = 'h'
    else:
        choice = 's'

Put simply: my bot slacks against any bot that has slacked more than it. This deviates from tit-for-tat in that it punishes bots for every pre-emptive slack, instead of defections merely against itself. This makes my bot a reputable and maximally beneficial community member. That is, It punishes every hunter for every slack and never punishes bots that likewise punish every slacker. Another interesting effect is how severely lazy bots end up being punished by my strategy. Tit-for-tat is very forgiving in comparison, where a single defection is met with defection the next round, and co-operation thereof should the initially defecting bot behave as such. My bot, however, isn't as merciful. Given an example game of 10 players, a bot may defect against all 9 of its opponents in a single round, one of whom is my bot. In response, my bot with defect against this bot for 9 consecutive rounds of unanimous co-operation on its part before continuing to co-operate with it again, despite only being defected against by the offending bot once itself.

My bot can be described as tit-for-tat that treats any single defection against the honorable portion of the community as a personal defection against itself, while maintaining co-operation with any bot as or more co-operative than itself.

How do you guys think I'll do? Are there obvious ways to exploit my bot's strategy? I haven't thought of any, but I may be missing something. I'm hopeful for at least the surviver prize.

I (and my friend) use simple lazy learning (kNN) to identify which players are likely to be the prospective partners to hunt together. It uses last 30 rounds result for data training since some players might have died and I don't need their behaviour to be included in data training. At first, we want to identify each player behaviour, but we didn't have enough time for that.

After submitted and did some simulations with my friend's algorithm, I realized that I should betray the most prospective ones, add some tricky strategies, or consider m as a lower/upper-bound to the number of 'h'. Ah well, we are the deadliner, hope we still can get the survivor t-shirt!

The purpose of m? Some algorithms survive for a long run, some do not. Getting a bonus food is really make a difference to the game though everyone gets it.

My algorithm always hunts in the first round only to start off with a reputation of 1.0 to encourage hunting by other good and rational players.

In subsequent rounds the algorithm becomes:

• If other player's reputation is less than 0.95, then slack.
• Otherwise, hunt with a probability dependent on a value calculated from m (I call it mthreshold).

To calculate mthreshold I first convert m from absolute terms to a scale between 0.0 and 1.0 by dividing m by: the number of players in the current round times the number of players in the current round minus one. This is known as the mratio. If mratio is near 0.0, this means only a few hunts need to happen in the round in order for everyone to receive the reward. If mratio is near 1.0, this means that even if many hunts happen in the round, we will probably not get the reward. Therefore, it makes sense to hunt with a higher probability when mratio is in the middle range. This probability is the mthreshold, which I calculate by simply transforming mratio in a linear fashion, going from 0.0 to 1.0 linearly as mratio goes from 0.0 to 0.5, and going from 1.0 to 0.0 linearly as mratio goes from 0.5 to 0.0.

I used a machine learning model. My strategy mainly considers these points: 1. It costs to maintain a reputation. 2. A higher reputation is likely to return more hunts from others

I created a list of length ten which stores how many people hunt with me when my reputation is in the range (0 to 0.1), (0.1 to 0.2) ... (0.9 to 1.0). In the first many rounds I try to go through all reputations and build this table. Looking at the matrix, I gain 3 food every time the other person hunts; lose 1 food every time I hunt (compared to the default -2 when no one hunts). So when I am at rep. 0.5 and others are cooperating 0.3 times at this reputation, I will gain (-2 + 3*0.3 - 0.5 = -1.6) food per hunt per round. I can calculate this value (net gain in food) for all reputation ranges (assuming 0.15 represents (0.1 to 0.2) range and so on).

Then I try to maintain the reputation which is most optimum reputation. Try to do this by cooperating more with those who have a higher reputation.

Further in certain cases try for m. I made another list which stores no. of players who hunt when m in the range (0 to 0.1), (0.1 to 0.2) and so on. If the ratio of number of hunts to m for a particular range is between 0.9 and 1.2 then try for m.

What if you: 1) cooperate with every one till reputations stabilize to some extent (up to your choice) 2) then work for social welfare: estimate expected hunt events S and compare it to m. If you can't influence social reward to take place go for some strategy A which doesn't take m into account, else make m-S hunt events with top rated players. For others go for some strategy B (which might or might not be the same as A) 3) while your food continues to grow stick with 2), when it goes below 95% of max food switch to Slack. 4) if your food grows above the last local minimum for more than 5% of it, switch to 2)

I've written a blog post describing what my team's approach was here: http://www.chasestevens.com/blog/read_post.php?title=the+anonymized+prisoner%27s+dilemma+challenge+%96+exploiting+limited+knowledge&time=1376983736 . The basic gist is that we implement tit-for-tat using reputation sorting as a means of player identification, unless we have the opportunity to subvert other similar tit-for-tat bots by assuming another player's identity.

There seems to be no talk of algorithm-switching yet. Did anyone submit any code that was preset to switch algorithms under different conditions or time periods? Our team ended up submitting an algorithm that would switch algorithms after a certain time. As in, not merely modifying its own parameters (e.g. Machine learning like), but switching to an entirely different algorithm altogether. Anyone else did this? Our reason was that our later-deployed algorithm was not effecive enough until it observes enough data.

My player only hunts with players falling within top 30% reputations and that too with a probability of 1/3. I am very impressed by the performance of always slackers (using the engine introduced by Chad M.) and decided to be slacker while giving an extra edge to it by hunting with top rep players. I have made this strategy assuming the game would go as follows. Firstly all players who hunt excessively would be out. After a while excessively slackers would have really nice food with low reputations and some other clever players with balanced rep and food who wish to go father than slackers by making a small union who would help each other by fairly hunting and beat slackers in the long run. Eventually excessive slackers who have lots of food will start to lose food and others would start gaining slowly. (The process is so slow that's other reason I decided to be a slacker majorly). My algorithm made an attempt to hunt with those fair players though remaining majorly a slacker. That's it. Thanks for introducing this competition. I had a great time learning Python and designing this algorithm.

How long do you think it's going to take for someone to die? It's kind of important to the running of my code that the estimations are correct.

I hunt with those who have higher reputations for me with subtle adjustments based on the number of hunters in the recent rounds and massive adjustments when someone dies.

For Q2, there are actually a lot of ways to track players. I think that strategies which track players well are going to have an advantage and be the top placers in the competition (although as a caveat, they must also make good decisions based off the information the tracking provides).

I chose to implement tracking based off the idea that you can look at a player's reputation and discover how much it could change (go up or down). The next round, if only 1 player falls within that range then you most certainly are looking at the same player from the previous round.

Additionally, I extended this idea to clusters of players with similar reputations. That way, even if I can't track a particular individual I can track a group of players which appear to be playing in a similar way.

I believe I have developed a strong algorithm for this problem. I have called my game engine 'Kran'. My main idea is that by hunting early and slacking later you can maximize the sum of reputations. My algorithm dynamically define the best moment to stop hunting and start slacking. Kran also features an underdeveloped Image system which can identify some players with distinguishable reputations and tries to contact them. I am particularly interested in critiques on my main idea: hunt early and slack later. Please check my link for more details.

www.kelvinsantos.com/kran.html

It is great to read everyone's thoughts here. My solution uses a number of strategies but my favorite is called CommunityBackstab. It is chosen by the meta-strategy when the chance of hitting $m$ this round is likely. The probability of reaching $m$ in round $i$ is likely when $p_{m} < 1.0$:

$p_{m} = m_{i} / (r_{average} \times P \times (P - 1) )$

where $r_{average}$ is the average reputation of the remaining $P$ players.

If $p_{m} < 1.0$ then we only need to hunt with $p_{m} \times P$ colluding players to realistically reach $m$. So we hunt with those players and slack against the remaining randomly chosen $(1 - p_{m}) \times P$ players.

The advantage here is that we still get $m$ most of the times but during the mad dash for $m$ we occasionally back stab a random bunch of players that we are colluding with and they (hopefully) don't find out.

Of course, this assumes that colluding players will try to achieve $m$ together and hunt more frequently in these rounds as a result.

based on :

• I should hunt with people that hunt (to stay in the potential survival group that always hunt together)
• I should slack with people that slack

my strategy is to stay in the "hunters" groups. So everyturn I do a basic 2-clustering (hunters/slackers) based on people reputation. then I hunt with the higher reputation until I set my reputation to the mean of the hunters group.

I start with hunting with everyone on the first round.

Ok, I didn't actually enter the competition. A friend of mine showed me this website and I read over the materials, thought about them, and did some back-of-the-envelope calculations and came up with an algorithm. But I've never used Python before and didn't invest enough effort to figure its ins and outs and code my thoughts...

In any case, my big idea was to keep things simple and use Tit for Tat as a model of sorts (a while back I'd read about a similar tournament for Prisoner's Dilema, which the Hunger Game strongly resembles). More specifically I wanted to hunt on the first turn. And on subsequent terms use a random number generator and basically hunt with a probability p which equals the reputation of my hunting buddy.

So treat people as they treat others.

Did anyone else use this algorithm? I'm still kind of interested in seeing how it could have been coded and how it might have done in competition.