xkcd 2385 KoTH (Final Exam)

Question

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.

(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

Answer 1

Golden

This bot was inspired by Self Aware Maximizer, but also takes into account how its own score affects the scores of other players.

Golden uses a golden section search to find which cybersecurity score would have maximized the previous round's score for itself minus the previous round's next best score. It then chooses the average of the optimal cybersecurity scores it has found.

The first cybersecurity score returned was determined by determining the best cybersecurity score for the first round 1000 times in a row, then taking the average.

{
    name: 'Golden',
    previousChoice: 0,
    first: true,
    goldenRatio: (Math.sqrt(5) + 1) / 2,
    weightedBest: 75.28679012885513,
    round: 0,
    goldenSectionSearch(f, min, max, tolerance = 1e-5) {
        while (max - min > tolerance) {
            let leftInterior = max - (max - min) / this.goldenRatio
            let rightInterior = min + (max - min) / this.goldenRatio

            if (f(leftInterior) < f(rightInterior)) {
                max = rightInterior
            } else {
                min = leftInterior
            }
        }
        return (min + max) / 2
    },
    run(choices) {
        if (this.first) {
            this.previousChoice = this.weightedBest
            this.first = false
            return this.weightedBest
        }
        const n = choices.length
        const i = choices.indexOf(this.previousChoice)
        const otherChoices = [...choices.slice(0, i), ...choices.slice(i + 1)]
        const sum = otherChoices.reduce((a, b) => a + b)

        function score(candidate) {
            const average = (sum + candidate) / n
            const gameTheory = 100 - Math.abs(average * 0.8 - candidate)
            const score = Math.sqrt(candidate * gameTheory)
            const otherScores = otherChoices.map(c => {
                const gameTheory = 100 - Math.abs(average * 0.8 - c)
                return Math.sqrt(c * gameTheory)
            })
            const best = Math.max(...otherScores)
            return best - score
        }

        const best = this.goldenSectionSearch(score, 1, 100)
        this.weightedBest = (this.weightedBest * this.round + best) / (this.round + 1)
        this.round++
        this.previousChoice = this.weightedBest
        return this.weightedBest
    }
}
```

Answer 2

The Skinny

Basically the same as fat, just trying to use less lines of code, by using an approximate constant for average velocity and not using numerical solver.

Fat                             78684.97459611233
Skinny                          78684.90970216368 
Overshoot (slightly)            78684.59923852411 
Histogrammer                    78684.24574125063 
ExponentialMovingAverage        78680.78518171726 
Optimise Mean                   78679.65559244195 
Near-stable                     78679.65559244195 
Calculus                        78679.47519324803 
Squidward                       78679.11475381341 
FollowTheLeader                 78677.6890436919 
Smartleton                      78673.66796955772 
Simpleton                       78673.62925366624 

  {
    name: "The Skinny",
    l_a:71.5,
    l_v:2.5,    
    n:0,
    run(s){      
      let a = sum(s)/s.length;
      let va =Math.sqrt(sum(s.map(function(x){return Math.abs(x - a)})));
      let p = 0.3*(((va - this.l_v)>0?1:-1)*4.8 - (a - this.l_a));
      this.l_a = a;this.l_v = va;this.n++;
      return this.n <2 ? 77 : 50+(a+p)*2/5;
    }
},
```

Answer 3

78

Turns out 78 is much better than 77

{
    name: "78",
    run(s){
      return 78;
    }
},