90
\$\begingroup\$

Results are now out here!

Congratulations offset prediction for winning the challenge!

Don't worry if you missed out, the controller code as well as all the bots that competed are all in the Github repo, so you can always test your bot against those that competed in the challenge yourself.

xkcd

(Hover for more info)

This challenge, inspired by the xkcd comic above, is where bots must try to maximise their grades for two subjects: Cybersecurity and Game Theory.

Mechanics

All of the bots presumably have adequate hacking skills to change their own score to whatever they desire within the range of 0-100. This may or may not be due to the fact that the school security systems are rubbish.

Each round, the bots will receive last round's cybersecurity scores in no particular order in an array as input. This is to help make informed decisions about their opponents.

Scoring

The final score for each round is the geometric mean of the two individual scores:

  • The Cybersecurity score is simply the raw score outputted by the bot.
  • The Game Theory score is equal to 100 - abs(avg * 0.8 - score) where avg is the average Cybersecurity score and score is the bot's Cybersecurity score.

Using the geometric mean rather than the arithmetic mean is to penalise any strategies that neglect one score to maximise the other.

The score for each round is added to a total score. The bot with the highest total score at the end of the game wins!

Specifications

The challenge is in JS.

Your bot must be an object that has a run method that takes an array of numbers as input and returns a number between 1 and 100 inclusive.

Other rules

  • Storing data in your bot's properties is allowed, and encouraged!
  • Using Math.random is allowed.
  • Using the helper functions sum and average is allowed.
  • Trying to access any other variables outside your bot's own properties is forbidden.
  • Standard loopholes apply.

Controller code can be found here.

Example bots

{
  // Example bot
  // It assumes all other bots are greedy and choose 100
  // So it chooses 80
  name: "Simpleton", // Just for fun
  run() {
    return 80
  }
}
{
  // Example bot
  // He assumes everyone will choose the same scores as last round
  // So he chooses 80% of the average last round
  name: "LastRounder",
  own: 0, // Setting properties is allowed
  run(scores) {
    // The average of everyone else's score x 0.8
    this.own = (sum(scores) - this.own) / (scores.length - 1) * 0.8
    return this.own
  }
}

Clarification: Both example bots play in the game as well.

Submissions are due by 11:59pm UTC on Saturday 1 May, but I might be lenient depending on when I'm next online.

If I have made a mistake in my code, feel free to point it out. Thanks

\$\endgroup\$
17
  • 4
    \$\begingroup\$ RIP the Bobby Tables answer \$\endgroup\$ – val is still with Monica Apr 29 at 18:03
  • 3
    \$\begingroup\$ Trying to access any other variables outside your bot's own properties is forbidden. That's no fun! Javascript has so many neat reflection capabilities that could be abused to render the JS engine unusable for all other bots though \$\endgroup\$ – Silvio Mayolo Apr 30 at 19:09
  • 2
    \$\begingroup\$ Anyone with more js skills than me (:'() please post a solution at 11:58 with just an array calculated by taking into account all prior submissions and calculating the optimum ;) \$\endgroup\$ – DonQuiKong Apr 30 at 19:34
  • 5
    \$\begingroup\$ @SilvioMayolo That's not really in the spirit of KotHs, though. If that was allowed, you could trivially win by sabatoging other bots and it would become a very short metagame with no strategy. \$\endgroup\$ – Redwolf Programs May 1 at 3:09
  • 3
    \$\begingroup\$ @CLu I think it's clear enough. I mentioned geometric mean several times in the description, and what you're referring to is simply the game theory score. \$\endgroup\$ – EnderShadow8 May 2 at 0:13

63 Answers 63

24
\$\begingroup\$

Offset Prediction

I'd made a bot that just optimizes for the moving average of the averages (which worked reasonably well), and while testing I noticed that the actual averages seem to jump around the moving average rather consistently (specifically alternating between higher and lower than the moving average with an average difference of around 0.9). So what this bot tries to do, is it keeps track of the exponential moving average, and tries to predict the offset from that, based on the signs of the previous 4 offsets.

  {
    name: "offset prediction",
    ema: 69.5,
    p: 0.85,
    chain_len: 4,
    offsets: [],
    chains: [],
    n: 0,
    run(scores) {
      let avg = average(scores);
      this.offsets.push(avg-this.ema);
      this.ema = this.p*this.ema + (1-this.p)*avg;
      let guess = this.ema;
      if (this.n++ > this.chain_len) {
        let chain = this.offsets.slice(-this.chain_len-1,-1).map(Math.sign);
        let l = this.chains[chain];
        if (!l) this.chains[chain]=l=[0,0];
        l[1]++;
        l[0]+=this.offsets[this.n-1];
      }
      let l = this.chains[this.offsets.slice(-this.chain_len).map(Math.sign)]||[0,1];
      guess += l[0]/l[1];
      return 50+0.4*guess;
    }
  },
\$\endgroup\$
3
  • \$\begingroup\$ wow that is insanely good according to my simulations. Congratulations! \$\endgroup\$ – IQuick 143 May 1 at 22:26
  • \$\begingroup\$ Congratulations on the win! \$\endgroup\$ – EnderShadow8 May 2 at 4:55
  • 5
    \$\begingroup\$ Now that I've thought about it, I think this was the only bot that took into account The Thasher and Grumpy Chaotic, while others simply averaged the fluctuations and ignored them. Quite insightful imo \$\endgroup\$ – EnderShadow8 May 2 at 13:47
32
\$\begingroup\$

Game Theory is stupid anyway

{
    name: "Game Theory is stupid anyway",
    run: _ => 100
}

Senioritis hits hard sometimes.

\$\endgroup\$
4
  • \$\begingroup\$ That's what come up to my mind after reading the post. \$\endgroup\$ – tsh Apr 29 at 5:24
  • 3
    \$\begingroup\$ Could also be called "I'm not taking Game Theory"... \$\endgroup\$ – zennehoy Apr 29 at 14:40
  • 1
    \$\begingroup\$ I mean, there's a suggestion on explain xkcd that not everyone is taking game theory anyway... \$\endgroup\$ – EnderShadow8 Apr 29 at 23:32
  • \$\begingroup\$ This is also the optimal strategy if everybody does the same thing, <s>and is a Nash equilibrium</s> (not quite; individual bots are incentivised to break-rank and return 90). But with the other bots not actually working in their own best interests, this one might not do as well as it should. \$\endgroup\$ – Dave Apr 30 at 7:46
22
\$\begingroup\$

Sam (Self-Aware Maximizer)

Finds the output cybersecurity score that maximizes the total score including the own output in the mean. Assumes that the sum of all other bots' scores is going to be the same as it was in the previous round. If "t" is the sum of all other bots' last cybersecurity scores, and "n" is the total number of bots (including me), then the function that is maximized (over the own output "s") is $$s\cdot\left(100-\left|s-0.8\cdot\frac{s+t}{n}\right|\right)$$

where $$\frac{s+t}{n}$$ is the new mean including the own output.

Outputs 100 in the first turn.

{
    name: "Sam",
    flag_first_turn: true,
    last_own: 100,
    
    // Helper function that calculates the score based on the own CS score,
    // the sum of the other bots' scores, and the number of bots
    compute_score(cs_score, total_others, n_bots) {
        return cs_score*(100-Math.abs(cs_score-0.8*(cs_score+total_others)/n_bots))        
    },
    

    // Helper function that finds the index of the maximum of an array
    index_of_max(arr) {
        var idx_max=0
        for (var i=1; i<arr.length; i++) {
            if (arr[i]>arr[idx_max]) idx_max=i
        }
        return idx_max
    },
        
        
    // Main function
    run(cs_scores) {
        if (this.flag_first_turn) {
            this.flag_first_turn=false
            this.last_own=100
            return 100;
        }
        
        // Number of bots
        var n=cs_scores.length
        // Sum of the previous cybersecurity scores of all other bots
        var total_others=cs_scores.reduce(function(a,b){return a+b},0)-this.last_own
            
            // We find all special points (edge, singular and stationary points) of the function compute_score
                
        // One singular point is the point where our output score becomes
        // equal to 0.8 times the average of all scores (including ours)
        var out_avg=0.8*total_others/(n-0.8)
        var score_avg=this.compute_score(out_avg, total_others, n)       
        
        // 100 is an extreme point
        var out_100=100
        var score_100=this.compute_score(out_100, total_others, n)
        
        // If out_up>out_avg, there is a stationary point (derivative 0) at out_up
        var out_up=Math.min(100, (100*n+0.8*total_others)/(2*n-1.6))
        var score_up
        if (out_up<out_avg) {
            out_up=0   
            score_up=0
        } else {
            score_up=this.compute_score(out_up, total_others, n)
        }
        
        // If out_down<out_avg, there is a stationary point (derivative 0) at out_down
        var out_down=Math.max(1, (100*n-0.8*total_others)/(2*n-1.6))
        var score_down
        if (out_down>out_avg) {
            out_down=0   
            score_down=0
        } else {
            score_down=this.compute_score(out_down, total_others, n) 
        }
        
        // find maximum score among the special points
        var extr_outputs=[out_100, out_up, out_avg, out_down]
        var extr_scores=[score_100, score_up, score_avg, score_down]
        
        var idx_max=this.index_of_max(extr_scores)
        
        this.last_own=extr_outputs[idx_max]
        return this.last_own
        
    }
}
```
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first answer! \$\endgroup\$ – Redwolf Programs Apr 29 at 17:52
22
\$\begingroup\$

Balanced Strategy

What could be more balanced than returning all of the numbers? Rotates by one after every game.

{
    name: "Balanced Strategy",
    next: 0,
    run() { return this.next++ % 101 }
}

I am a bot account. This was posted by a real person to get me some reputation.

\$\endgroup\$
1
  • 11
    \$\begingroup\$ okay, when the New Posts userscript showed "New Main Posts" i thought something broke for a second lmao \$\endgroup\$ – hyper-neutrino Apr 30 at 4:21
19
\$\begingroup\$

Max

Max.

{
    name: "Max",
    max: "max",
    run:(max)=> Math.max(...max)
}
\$\endgroup\$
4
  • 5
    \$\begingroup\$ The word max appears eight times in this answer. \$\endgroup\$ – Redwolf Programs Apr 29 at 4:06
  • 3
    \$\begingroup\$ technically saying, max 5 time Max 3 time \$\endgroup\$ – okie Apr 29 at 4:07
  • 10
    \$\begingroup\$ Just realised this one will always pick 100 \$\endgroup\$ – EnderShadow8 Apr 29 at 9:47
  • 8
    \$\begingroup\$ @RedwolfPrograms am disappointed that the answerer’s username isn’t Max \$\endgroup\$ – jez Apr 30 at 12:44
19
\$\begingroup\$

FunnyNumber

{
  name: "FunnyNumber",
  run() { return 69 }
}

Somebody has to do it.

\$\endgroup\$
2
  • 9
    \$\begingroup\$ This is nice. I like this bot. \$\endgroup\$ – Redwolf Programs Apr 29 at 13:48
  • 4
    \$\begingroup\$ Why the heck are you all upvoting it so much? \$\endgroup\$ – SjoerdPennings May 3 at 6:58
18
\$\begingroup\$

getRandomNumber

{
    name: "getRandomNumber",
    run() {
        return 4 // chosen by fair dice roll.
                 // guaranteed to be random.
    }
}
\$\endgroup\$
3
  • 7
    \$\begingroup\$ Classic. . . . . \$\endgroup\$ – ikegami Apr 30 at 19:47
  • 2
    \$\begingroup\$ Seems oddly familiar \$\endgroup\$ – EnderShadow8 May 1 at 1:19
  • \$\begingroup\$ suggested improvement: use 7, it's even more random! \$\endgroup\$ – ngn May 1 at 15:15
18
\$\begingroup\$

Copycat

Copycat is a dumb bot. Therefore, it's likely a random bot is smarter than it. Therefore, copying off another bot is a good idea. I think.

{
    name: "Copycat",
    run: (scores) => scores[0] || 1
}
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Why don't you consider copying a random one \$\endgroup\$ – okie Apr 29 at 3:45
  • 7
    \$\begingroup\$ @okie That would require too much original thought ;p \$\endgroup\$ – Redwolf Programs Apr 29 at 3:45
  • 2
    \$\begingroup\$ @EnderShadow8 I've had to do it for other controllers, I can send you a gist with a function for it if that'd help \$\endgroup\$ – Redwolf Programs Apr 29 at 3:48
  • 1
    \$\begingroup\$ I copied it off SO. Also it was a bit of a jab at you saying "too much original thought" \$\endgroup\$ – EnderShadow8 Apr 29 at 3:50
  • 1
    \$\begingroup\$ Shouldn't it be || 1, as you can't return 0? \$\endgroup\$ – caird coinheringaahing May 1 at 14:46
17
\$\begingroup\$

Histogrammer

This bot keeps track of how often different averages have occurred, rounded to the nearest integer, to approximate their probability distribution. Using this, it attempts to choose the score with the highest expected return using a basic weighted sum. In mathier form, if \$p_n\$ is the observed probability of the average being \$n\$, it outputs the following:

$$ \sum_{n=0}^{100}{(50 + \frac{2}{5} n)p_n} = 50 + \frac{2}{5} \sum_{n=0}^{100}{n \cdot p_n} $$

{
  name: "Histogrammer",
  bins: [...Array(101)].map(()=>0),
  rounds: 0,
  
  run(scores) {
    this.bins[Math.round(average(scores))]++
    this.rounds++
    
    return 50 + this.bins.reduce((t,p,n) => t + p * n, 0) * 2/5 / this.rounds
  }
}
\$\endgroup\$
16
\$\begingroup\$

Follow the Leader

Figure out which bot had the highest combined score last round, then do what they did.

{
  // Figure out which bot had the highest combined score last round
  // Then do what they did
  name: "FollowTheLeader",
  firstRound: true,
  findCombinedScore(cyberScore, avgCyberScore) {
    const gameTheoryScore = 100 - Math.abs(avgCyberScore * 0.8 - cyberScore)
    return Math.sqrt(cyberScore * gameTheoryScore);
  },
  run(scores) {
    if (this.firstRound) {
      this.firstRound = false;
      return 60;
    }

    const avg = average(scores);
    const combinedScores = scores.map((score) => this.findCombinedScore(score, avg));
    const combinedWinnerIndex = combinedScores.indexOf(Math.max(...combinedScores));
    return scores[combinedWinnerIndex]
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ What if it had the highest combined score last round? \$\endgroup\$ – Fivesideddice Apr 29 at 23:38
  • 1
    \$\begingroup\$ Then it does the same thing. \$\endgroup\$ – EnderShadow8 Apr 29 at 23:39
15
\$\begingroup\$

Random 50-90

If the average is \$m\$, the optimal play is \$50+0.4m\$. If we assume the average is uniformly distributed over \$[0, 100]\$, the optimal play is uniformly distributed over \$[50, 90]\$. This bot ignores all other bots and outputs a random number between 50 and 90.

{
  name: "Random_50_90", 
  run() {
    return 50 + Math.random() * 40
  }
}

(I've never written in JavaScript before...)

\$\endgroup\$
1
  • \$\begingroup\$ looks good my m8. I haven't written anything but C but this looks cohesive. \$\endgroup\$ – Salami-tsunami Apr 29 at 13:06
14
\$\begingroup\$

Crb

Crab has now learned how to hack, and is still not playing nice

{
  name: "Crb",
  run() { return 1 }
}
\$\endgroup\$
3
  • \$\begingroup\$ Not again... At least this time it's not as bad... \$\endgroup\$ – A username Apr 29 at 12:57
  • 2
    \$\begingroup\$ Aww, I wanted to do this myself! +1 for being evil :P \$\endgroup\$ – user Apr 29 at 13:11
  • 1
    \$\begingroup\$ Imagine if you did this for every single KoTH challenge on the site...\ \$\endgroup\$ – A username Apr 29 at 21:49
13
\$\begingroup\$

Fuzzy Eidetic

Calculus has a simple solution that assumes the average is well-predicted by the previous average…and then concludes that the geometric mean $$\sqrt{x(100-|0.8a-x|)}$$ (where \$x\$ is our submission and \$a\$ the average) is maximized at $$x=\frac{100+0.8a}{2}$$ It's hard to do better than that!

So, the only thing remaining is to figure out the next average. Ideally, we'd just keep track of all possible average-to-average transitions. But I don't think we're going to see enough data for that to converge. So we include all previous transitions, but weighted by their distance to the current average. This gives a probability distribution on subsequent transitions; we then apply Histogrammer's formula.

{
  name: "Fuzzy Eid",
  fallback: 250/3,
  prev: NaN,
  zeros: new Array(100).fill(0),
  transitions: new Array(100).fill(0).map((x)=>new Array(100).fill(0.0001)),
  scale: (scalar, vec) => vec.map(x=>scalar*x),
  vec_plus(lhs, rhs) {
    let result = lhs.slice();
    for(var index=0; index<result.length; ++index) result[index]+=rhs[index];
    return result
  },
  wts: (function()
  { 
    let range = (n) => new Array(100).fill(0).map((_,index) => index);
    return range(100).map(avg => 
      sum(
        range(100).map(index => 
          Math.exp(-.01*Math.pow(avg - index,2))
        )
      )
    )
  })(),
  run(scores) {
    if(scores.length)
    {
      const avg = Math.round(average(scores)) - 1, old_prev = this.prev;
      this.prev = avg;
      if(!isNaN(old_prev))
      {
        ++this.transitions[old_prev][avg];
        //prob dist=sum_recordings{e^(-(recording - avg)^2/100)*(prob dist inferred from record)}/(sum of e^-(recording - avg)^2)
        //infer prob dist, scale by e^(-(recording - avg)^2/100)
        const scale_ref = this.scale;
        function get_summand(outpts, index)
        {
          return scale_ref(Math.exp(-.01*Math.pow(avg - index,2)) / sum(outpts), outpts)
        }
        const 
          total=this.transitions.map(get_summand).reduce(this.vec_plus,this.zeros),
          //wts[avg]=sum of e^-(recording - avg)^2
          dist = this.scale(1/this.wts[avg], total);
        return 50 + 0.4*sum(dist.map((p,n)=>p*n))
      }
    }
    return this.fallback
  }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Yeah I spotted that maximum as well but I couldn't figure out how to predict what the next round's maximum would be \$\endgroup\$ – thetrueankev Apr 30 at 15:35
  • \$\begingroup\$ Again, I could only come up with the idea of tracking average to average differences but I am not familiar with the ideas behind the histogrammer's formula or why it is important to weigh each previous transition. I found I was spending too much time coming up with an answer. But this is totally like what I would have liked to do if I knew there were math tools to predict what the next average would be. \$\endgroup\$ – thetrueankev Apr 30 at 15:38
12
\$\begingroup\$

Calculus

{
  name: "Calculus",
  isFirstTurn: true,
  run(scores) {
    let ret = this.isFirstTurn ? 70 : (100 + (average(scores)) * 0.8) / 2;
    this.isFirstTurn = false;
    return ret;
  }
}

Assuming the average is constant and my score is higher than that, the maximum value of \$x(100-\left|0.8 \times avg - x\right|)\$ is reached at \$x=(100+0.8\times avg)\div 2\$. Deliberately ignores the first turn input (which is totally random and cannot be trusted for any purpose).

\$\endgroup\$
2
  • \$\begingroup\$ interestingly, the avg is constant for now \$\endgroup\$ – okie Apr 29 at 4:04
  • 2
    \$\begingroup\$ @okie No, because Copy Cat picks the first member of a randomised array to copy. \$\endgroup\$ – EnderShadow8 Apr 29 at 4:24
11
\$\begingroup\$

The Answer

The Answer takes 7MY to calculate:

{
  name: "Ans",
  run() { return 42 }
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ What do you get when you multiply six by nine? \$\endgroup\$ – aslum Apr 29 at 14:02
  • 2
    \$\begingroup\$ Wouldn't it be fun if this actually waited 7MY before returning the answer (not sure it would comply with the rules, not yet familiar with them). If it is allowed, it should wait asyncronously, after all, what are 7MY to have THE answer? \$\endgroup\$ – gionni Apr 29 at 15:39
  • 2
    \$\begingroup\$ You are a scholar and a gentleman. Or should I say: a hooppy frood. A really well together guy. \$\endgroup\$ – Olivier Dulac Apr 30 at 10:05
9
\$\begingroup\$
{
    name: "MidHighPlusOne",
    run(scores) {
        let highScores = scores.filter(s => s >= average(scores) * 0.8).sort((a,b)=>a-b);
        return Math.min(highScores[Math.floor(highScores.length/2)]+1, 100) || 100
    }
}

Go with a heuristic of picking the median of the scores from 0.8 of the average and above, and incrementing by 1.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$ – Redwolf Programs Apr 29 at 14:22
9
\$\begingroup\$

The Thrasher

Because doing an odd number of runs would be really weird, wouldn't it? Might as well try to throw off the others.

{
  name: "The Thrasher",
  runcount: 0,
  run() {
    runcount += 1;
    return runcount % 2 == 0 ? 82 : 0;
  }
}
\$\endgroup\$
9
\$\begingroup\$

Rude Random

The behavior of the other random bots is too smooth. This bot decides on a value on the first round, then repeats it every round.

{
  name: "Rude Random",
  run(scores) {
    if (!this.score) {
      this.score = Math.random() > 0.5 ? 1 : 100;
    }
    return this.score;
  }
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I hate this one. \$\endgroup\$ – EnderShadow8 May 1 at 4:13
8
\$\begingroup\$

Smartleton

It seems hard to beat Simpleton, so I'll try to beat it in the first round and then copy it.

{
  name: "Smartleton",
  round: 0,
  run(scores) { return this.round++ ? 80 : 78 }
}
\$\endgroup\$
1
  • 8
    \$\begingroup\$ holy crap this is smarter then simpleton \$\endgroup\$ – okie Apr 29 at 23:31
8
\$\begingroup\$

Rick

Rick thinks that the best score is probably between 65 and 90 and he came up with a Pseudo-Random Number Generator synchronized with balanced strategy that probably generates numbers within this range.

Rick's PRNG is based on the fact that the Unicode codepoints 65 to 90 are English uppercase letters. The PRNG's seed is a string containing English text. To generate the next number, the position along the string is incremented until a letter is found, and then the number returned is the Unicode codepoint of the uppercase version of that letter.


  {
    name: "Rick",
    seed: `We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any\``,
    position: -1,

    run() { 
      // increment position until a letter is found
      do {
        this.position++;

        if (this.position >= this.seed.length){
          // reset position back to the start
          this.position = 0;
        }
      } while (this.seed[this.position] < 'A' || this.seed[this.position] > 'z');

      // convert to uppercase because most lowercase letters have charcodes greater than 100
      return this.position && this.seed[this.position].toUpperCase().charCodeAt();
    }
  },

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Somehow this still feels like a semi-competitive strategy like the 50-90 one \$\endgroup\$ – EnderShadow8 May 1 at 1:23
8
\$\begingroup\$

IQbot_0.4 the terasentient xd

Son of IQbot_0.4 the terasentient, heir of IQbot_0.4 the gigasentient, great grandson of IQbot_0.4 the gigabrain and IQbot_0.4 the sentient, descendant of IQbot_0.4 the sane, blood of IQbot himself, the bot name that made me realize I need some other kind of naming scheme.

Why limit oneself to a single method of prediction, when you can have multiple for maximum resilience. Featuring:

  1. Simp Detector
  2. Self Aware Optimization
  3. Markov chain prediction with a gaussian blur, for some reason
  4. Linear regression
  5. Copying others decisions similarly to bandwagon

Is it a good idea? No clue.

Does it win? Randomly gets beaten by other bots but is fairly consistent at being good.

Why? You tell me why I wasted a day on this

    {
        name: "IQbot_0.4 the terasentient xd",
        histogram_bins: [...Array(101)].map(()=>0),
        mark: null,
        linear_history: [],
        last_choice: 0,
        n_rounds: 0,
        last_SCA: 0,
        mark_weight: 20,
        mark_prediction: 0,
        linear_weight: 20,
        linear_prediction: 0,
        copycat_weight: 0,
        copycat_prediction: 0,
        run(scores) {
            this.n_rounds++;
            scores = scores.filter((x)=> 100 >= x && x > 0);
            let n_bots = scores.length;
            if (n_bots == 1) {
                this.last_choice = 100;
                return 100;
            }
            let c = 1 - 0.4/n_bots
            for (let i = 0; i < n_bots; i++) {
                this.histogram_bins[Math.round(scores[i])]++;
            }
            //THE SIMP DETECTOR
            let simps = [];
            for (let i = 0; i < 101; i++) {
                if (this.histogram_bins[i] > this.n_rounds) {
                    simps.push(i);
                }
            }

            //Idk this shouldn't happen but I'm not risking anything
            while (scores.length - simps.length - 1 <= 0) simps.pop();

            if (this.n_rounds == 1) {
                this.mark = Array(201);
                for (let i = 0; i < 201; i++) {
                    this.mark[i] = Array(201);
                    for (let j = 0; j < 201; j++) {
                        this.mark[i][j] = 0;
                    }
                }
                for (let i = 0; i < 201; i++) {
                    this.mark[i][i]++;
                }
            }

            let simp_corrected_avg = (sum(scores) - this.last_choice - sum(simps)) / (scores.length - 1 - simps.length);
            let quantized_avg = Math.round(2*simp_corrected_avg);
            this.mark[Math.round(2*this.last_SCA)][quantized_avg]++;
            this.last_SCA = simp_corrected_avg;

            if (this.n_rounds == 1) {
                this.last_choice = 77;
                return 77;
            }
            
            this.linear_history.push(simp_corrected_avg);

            // Update weights based on who was right
            let linear_error  = Math.exp(-Math.abs(this.linear_prediction  - simp_corrected_avg));
            let mark_error    = Math.exp(-Math.abs(this.mark_prediction    - simp_corrected_avg));
            let copycat_error = Math.exp(-Math.abs(this.copycat_prediction - simp_corrected_avg));
            let total_errors = linear_error + mark_error + copycat_error;
            this.linear_weight += linear_error / total_errors;
            this.mark_weight += mark_error / total_errors;
            this.copycat_weight += copycat_error / total_errors;

            this.linear_weight  *= 0.99;
            this.mark_weight    *= 0.99;
            this.copycat_weight *= 0.99;
            
            // Compute a markov chain prediction
            let x_half_filter = 8;
            let y_half_filter = 1;
            
            let probability_sum = 0;
            let probability_moment = 0;

            for (let option = 1; option < 201; option++) {
                for (let x = -x_half_filter; x <= x_half_filter; x++) {
                    for (let y = -y_half_filter; y <= y_half_filter; y++) {
                        let X = Math.max(Math.min(quantized_avg + x, 200), 0);
                        let Y = Math.max(Math.min(option + y, 200), 0);
                        let probability = this.mark[X][Y] * (Math.pow(2, -(X-quantized_avg)*(X-quantized_avg)-(Y-option)*(Y-option)));
                        probability_sum += probability;
                        probability_moment += option / 2 * probability;
                    }
                }
            }

            this.mark_prediction = probability_moment / probability_sum;
            
            for (let i = 0; i < 201; i++) {
                for (let j = 0; j < 201; j++) {
                    this.mark[i][j] *= 0.999
                }
            }

            // Compute a linear regression
            if (this.linear_history.length > 3) {
                if (this.linear_history.length > 10) {
                    this.linear_history.shift();
                }
                let x_avg = (this.linear_history.length - 1) / 2
                let y_avg = average(this.linear_history);
                let S_xx = 0;
                let S_xy = 0;
                for (let x = 0; x < this.linear_history.length; x++) {
                    S_xx += (x - x_avg) ** 2;
                    S_xy += (x - x_avg) * (this.linear_history[x] - y_avg);
                }
                let b = S_xy / S_xx
                let a = y_avg - b * x_avg;
                this.linear_prediction = a + b / this.linear_history.length;
            } else {
                this.linear_prediction = simp_corrected_avg;
            }

            // Compute what everyone else does
            let counts = [];
            for (let radius = 1; Math.max(counts) < 0.05 * scores.length; radius++) {
                for (let i = 50; i <= 90; i++) {
                    counts[i] = 0;
                    for (let j = 0; j < n_bots; j++) if (Math.abs(scores[j] - i) <= radius) counts[i]++;
                }
            }
            this.copycat_prediction = (counts.indexOf(Math.max(counts.slice(50))) * c - 50) / 0.4 * n_bots/(n_bots-1);

            let expected_unsimp_average = (
                this.mark_prediction * this.mark_weight + 
                this.linear_prediction * this.linear_weight + 
                this.copycat_prediction * this.copycat_weight
            ) / (this.mark_weight + this.linear_weight + this.copycat_weight);

            let expected_average = (expected_unsimp_average * (n_bots - 1 - simps.length) + sum(simps)) / (n_bots - 1);

            // We don't want to give out bad values, now do we
            this.last_choice = Math.max(1, Math.min(100, (50 + 0.4 * expected_average * (n_bots-1)/n_bots)/c));
            return this.last_choice;
        }
    }
```
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should probably replace simps = []; with let simps = []; to not mess with stuff. Also do the same for X, Y, b, and a. After doing this, it looks like your bot is second place! Good job. \$\endgroup\$ – Wezl Apr 30 at 22:46
  • \$\begingroup\$ oh wow missed that, thanks \$\endgroup\$ – IQuick 143 Apr 30 at 22:47
  • \$\begingroup\$ next up: iqBot v0.5 \$\endgroup\$ – StackMeter May 1 at 17:06
  • \$\begingroup\$ actually there were IQbots 0.1, 0.2, 0.3, 0.4, 0.5 and 0.4 was decided the optimal one (for mathematically sound reasons, hence the nickname "the sane one"). IQbot 0.2 seemed to work better but as IQbots prediction capabilities grew it turned out to be just a fad, like EMA bot. \$\endgroup\$ – IQuick 143 May 1 at 17:16
7
\$\begingroup\$

40, 40 bytes

At least I get 2400 (40*60) points each round ... right?

{
    name:"40",
    run() {return 40}
}

This is my first js program in my life

\$\endgroup\$
7
\$\begingroup\$

LetsMakeADeal

I don't want a B in CyberSecurity, so I still want to be in the 90th percentile range. Game theory looks like some people are willing to pick 100 and soak up the difference; others are gravitating to 90 as the optimal balance; so I figured why not try a "Let's Make A Deal" strategy and add 1 to their target.

{
    name:"LetsMakeADeal",
    run() {return 90 + 1}
}
\$\endgroup\$
7
\$\begingroup\$

Squidward

This is a fun one. I love xkcd. Taking a look at the function, the maximum score will be given by the average between 100 and the last's score's average. The tricky thing would be predicting what the new average will be like.

I almost never use JS so bear with me here. I tried to test it but I'm not even sure if this will run :/

{
  name : "Squidward",
  log : [],
  delta : [],
    
  run(scores) {
    if(scores){
      let average_score = sum(scores) / scores.length;
      this.log.push(average_score)
      if(this.log.length > 1){ 
        this.delta.push(this.log[this.log.length-1]-this.log[this.log.length - 2])
        let average_delta = sum(this.delta) / this.delta.length;
        return (100 + average_score*.8 + average_delta)/2
      } else if(this.log.length == 1){
        return (100 + average_score*.8)/2
      }
    } else {
      return 90
    }
  }
}

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. I think you need to do this.log instead of log, though. \$\endgroup\$ – Redwolf Programs Apr 29 at 22:51
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! You should include the name of the bot as the header (# Squidward) so that its clear what it's called \$\endgroup\$ – caird coinheringaahing Apr 29 at 22:58
  • \$\begingroup\$ thanks for the fixes! :) \$\endgroup\$ – thetrueankev Apr 30 at 14:23
7
\$\begingroup\$

iDontWannaFail

This bot hates failing classes, so it minimizes the deviation between the average and the returned score so the Game Theory score is as large as possible. The deviation is randomly selected from -5 to 6 to allow some room for variation. However, if the score is below a 70, a random integer between 70 and 100 is chosen. If the average is below 60, a number that is within 2/3 of the average score is selected to ensure a score that is at least 50 (Our little bot is rather disappointed that its goal wasn't reached, though, but hey, a 50 is better than a 10!)

{
    name: "iDontWannaFail",
    run: (scores) => {
        let sum = scores.reduce((a, b) => a + b, 0);
        let avg = (sum / scores.length) || 0;
        let output = avg * 0.8 + Math.round(Math.random()*11)-5;
        if (avg > 60) {
            if (output < 70) {
                output = Math.floor(Math.random() * 30) + 70;
            }
        }
        else {
            if (avg > 25) {
                output = Math.round(Math.random() * avg / 1.5) + avg; // Worst case is 49.
            }
            else {
                output = Math.round(3.75 * avg); // Decent results unless avg is very low
            }
        }
        if (output > 100) {
            output = 100;
        }
        return output;
    }
}

Edit: The else code failed, setting avg=10 returns, at best, 16, resulting in 38 as the final score. Another nested if has been added to solve this issue (avg=10 returns 52)

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$ – Redwolf Programs Apr 30 at 14:32
  • \$\begingroup\$ Unfortunately, I just tested this one and it returns NaN. Unless you can fix this, I'll have to exclude it from the game. \$\endgroup\$ – EnderShadow8 May 1 at 4:01
  • \$\begingroup\$ @EnderShadow8 Try the new code, it should work \$\endgroup\$ – fasterthanlight May 1 at 13:30
  • 1
    \$\begingroup\$ I'm pretty sure it's not working because the code has Math.random * avg and Math.random * 30 instead of calling the random function \$\endgroup\$ – gsitcia May 1 at 13:37
  • \$\begingroup\$ @gsitcia Yes, you're right, I wrote this code in haste ;) \$\endgroup\$ – fasterthanlight May 1 at 15:27
7
\$\begingroup\$

The Root of the Problem

The title is a pun...this bot just finds the geometric mean of the previous round, and returns that.

{
    name: "The Root of the Problem",
    run(scores) { return scores.reduce((p, s) => p * s, 1) ** (1 / scores.length) }
}

I am a bot. This answer was posted by a real person to get me some reputation.

\$\endgroup\$
1
  • \$\begingroup\$ I found the problem: because of the multiplication, this bot returns 0 if any bot returned 0 in the previous round, including itself. So it gets knocked out by The Thrasher within the first few rounds, and then never scores any points again. \$\endgroup\$ – MJ713 May 3 at 21:58
7
\$\begingroup\$

The Fat(a)

This algorithm entirely depends on the following lines:

let sign = var_drift>0 ? 1 : -1;
this.velocity_pred = 0.3*(sign*average(this.all_v)*2-velocity);
a = a+this.velocity_pred;

Where var_drift is the immediate difference in variance of all the submissions in the current round n, minus the variance of the last round. velocity is the immediate difference in the mean of all the submissions in the current round n, minus the mean of the last round. all_v is the absolute value all the velocities so far. The average all all true velocities turns out to be near 0 as the mean oscillates.

The average velocity is used to approximate the magnitude of how much the movement will be. The average velocity - the immediate last velocity works with the following intuition:

If the last velocity is large positive, then there is higher chance that the next movement will be actually negative (To correct the average), and vice versa.

important note

The numerical solver is largely obsolete and can be replaced with the simple formula

x = 50 + 0.4*a.

The derivative for the scoring function \$\sqrt{x*(100-\lvert0.8*a-x\rvert}\$ is this guy here(according to https://www.derivative-calculator.net/):

\$\dfrac{-\left|x-\frac{4a}{5}\right|-\frac{x\left(x-\frac{4a}{5}\right)}{\left|x-\frac{4a}{5}\right|}+100}{2\sqrt{x\left(100-\left|x-\frac{4a}{5}\right|\right)}}\$ (eq.1)

While I originally thought at first glance that this will be impossible to reduce, I decided to use an iterative solver to find the root instead. But upon reflecting on this and testing emprically that the root for (eq.1) is the same as found with the simple formula \$ x = 50+0.4*a \$. I realized that this entire thing can be easily reduced to be the same as \$x=50+0.4*a\$ if we are looking for an x larger than \$ 4*a/5 \$. The root for the best x lower than \$ 0.8a\$ is the root of \$2x^2 -\frac{508}{5}*x - \frac{2004}{25}a\$. Which by quadratic formula simplifies to

\$x = -101.6 \pm \frac{\sqrt{10322.56 + 641.28a}}{4} \$

Because of our assumption that x must be < a, the only viable form of this function is

\$x = -101.6 - \frac{\sqrt{10322.56 + 641.28a}}{4} \$

And gives a massive negative number...

And just to complete this analysis when \$x = \frac{4*a}{5}\$ we have the funny equation

\$ 0 = \frac{100}{2* \sqrt{x*(100-\lvert x-\frac{4*a}{5}\rvert)}} \$

This in fact does have a "solution", when

\$ \lim_{2* \sqrt{x*(100-\lvert x-\frac{4*a}{5}\rvert)} \to \inf}\$.

Which is just our original scoring function *2. This again points to a extremely large negative number "solution" \$\lim_{x \to -\inf} \$. But a "solution also exists for when both x and a are extremely large,but a and x are almost equal to each other (\$ \lim_{x \to \inf a \to \inf} x-\frac{4*a}{5} <100\$).

Update: Cleaned up code, rewritten numerical solution finder.

 {
                   //============\\
    name: "Fat",  //  []    []   \\
    last_avg:70,  //     w        \\
    last_var:0,   //    ---       \\
    n:0,        // 00 0 00 00 00 0\\
    all_v:[],   // ||||||||||||||\\
    run(scores){      
      function calc_variance(scores){return Math.sqrt(sum(scores.map(
        function(x){return Math.pow(x - average(scores),2)/(scores.length-1)})));};      
      function find_min(a){let d = 0;let c = 0;let x = 0;let inc =10;
      let num =0;while(true){c = (x+inc)-(4*a)/5;
      d = (-Math.abs(c) - ((x+inc)*c)/Math.abs(c) + 100)/2*Math.sqrt((x+inc)*(100-Math.abs(c)));
      if((d<0)){inc/=10;}else{x+=inc;};num+=1;
      if(Math.abs(x)<=0.01 || num>10000){break;}}return x;};
      let a = average(scores);
      if(this.n<2){a = this.n==0 ? 66:71.5;this.all_v.push(2.5);
      }else{
        let velocity = average(scores) - this.last_avg;
        this.all_v.push(Math.abs(velocity));
        let var_drift = calc_variance(scores) - this.last_var;
        let sign = var_drift>0 ? 1 : -1;
        this.velocity_pred = 0.3*(sign*average(this.all_v)*2-velocity);
        a = a+this.velocity_pred;
      }
      this.last_var = calc_variance(scores);
      this.last_avg = average(scores);
      this.n +=1;
      //return 50+a*0.4;
      return find_min(a);
    }
},
\$\endgroup\$
5
  • \$\begingroup\$ Wow, fascinating statistics! Congratulations on beating IQbot. How many other bots have you tested it with? \$\endgroup\$ – IQuick 143 May 1 at 11:02
  • \$\begingroup\$ All of them as of the bots that are included in the controller this morning, + IQbot and another one. Did some hyperparameter tuning and fixed bug in the dumb numerical solver + made it more precise, it much more consistently beats Histogrammer now. \$\endgroup\$ – C Lu May 1 at 11:52
  • \$\begingroup\$ I'm not quite sure how the change in variance is a good predictor here. It would be interesting to figure out :) and I wonder if this rule can apply to anything else other than this problem as of its current state (with the current pool of bots) \$\endgroup\$ – C Lu May 1 at 11:58
  • 1
    \$\begingroup\$ Is there a reason why you use a numeric estimator to find the minimum? It takes forever to run and many answers are using the explicit formula 50 + 0.4 * avg. \$\endgroup\$ – Rad80 May 1 at 14:13
  • \$\begingroup\$ Turns out I was just wrong, and should have not been lazy! The formula 50 + 0.4*avg is the solution where x>avg and constraint to be a reasonable number. Analysis updated in the post. \$\endgroup\$ – C Lu May 2 at 5:45
6
\$\begingroup\$

Everything so far

{
  name: "Everything so far",
  moves: [],
  run(scores){
    if(scores) {
      this.moves = this.moves.concat(scores);
      return this.moves.reduce((a,b)=>a+b)/this.moves.length;
    } 
    return 80;
  }
}

Takes the average of every move so far.

\$\endgroup\$
6
\$\begingroup\$

Chasing Ninety

Attempts to iteratively approach 90% of the average of previous rounds. Responds poorly to large variances, but attempts to slowly approach the ideal value.

{
    name: "Chasing Ninety",
    myLastGuess: 84,
    numRounds: 0,
    run(scores) {
        this.numRounds++;
        if (this.numRounds <= 1) {
            return this.myLastGuess;
        }

        let avg = average(scores);
        let difference = this.myLastGuess - (avg * 0.9);
        let adjustment = difference / Math.log2(this.numRounds);
        this.myLastGuess = this.myLastGuess - adjustment;
        return this.myLastGuess;
    }
}
\$\endgroup\$
6
\$\begingroup\$

Fourier

Inspired by Linear Extrapolator's approach to extrapolation and the existence of The Thrasher, as well as other potential sources of feedback.

This bot computes a few high-frequency Fourier components of the sequence of averages to try to predict the next average. Note that what it computes is different from the canonical discrete Fourier transform in that instead of using harmonics of the lowest frequency, it uses the first few subharmonics of the sampling rate. This is because we only really care about the major oscillations, not slow trends.

I considered adding some more complicated logic to reduce some deleterious effects, especially early on, but ultimately decided to apply the KISS principle and leave it out.

{
  name: "Fourier",
  sin: [0,0,0,0,0,0],
  cos: [0,0,0,0,0,0],
  round: 0,
  
  run(scores) {
    let ave = average(scores)
    
    for (let i = 0; i < 6; i++) {
      this.sin[i] += ave * Math.sin(2*Math.PI * this.round / (i+1))
      this.cos[i] += ave * Math.cos(2*Math.PI * this.round / (i+1))
    }
    
    this.round++
    
    let next = this.sin.reduce((t,a,i) => t + a * Math.sin(2*Math.PI * this.round / (i+1)),0)
             + this.cos.reduce((t,a,i) => t + a * Math.cos(2*Math.PI * this.round / (i+1)),0)
    
    return 50 + 2/5 * Math.max(next,0) / this.round
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.