95
\$\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\$ Apr 29, 2021 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\$ Apr 30, 2021 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, 2021 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\$ May 1, 2021 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\$ May 2, 2021 at 0:13

63 Answers 63

6
\$\begingroup\$

Bandwagon

{
    name: "Bandwagon",
    run: (scores) => {
        let counts = [];
        for (let radius = 1; Math.max(...counts.slice(50)) * 20 < scores.length; radius++) {
            for (let i = 50; i <= 80; i++) {
                counts[i] = +scores.map((x) => Math.abs(x - i) <= radius).reduce((x,y) => x+y);
            }
        }
        return (counts.indexOf(Math.max(...counts.slice(50))) + 1 || 253 / 3) - 1;
    }
}

Since everyone else got around to extrapolating the entire game history well before I could figure out how to do it poorly, Bandwagon assumes--within reason--that enough of them know what they're doing, and hopes they won't change too much, by putting itself in the center of a region containing at least 5% of last round's grades.

\$\endgroup\$
1
  • \$\begingroup\$ I'm shocked by how well Bandwagon performed in the final results--guess enough of the other bots really do know what they're doing \$\endgroup\$ May 2, 2021 at 11:08
6
\$\begingroup\$

Rebel

{
    name: "Rebel",
    counts: Array(31).fill(0),
    run(scores) {
        scores.filter((x) => x <= 80 && x >= 50).forEach((x) => this.counts[x-50]++);
        return this.counts.lastIndexOf(Math.min(...this.counts)) + 50;
    }
}

Bandwagon and all of the other bots are dumb and bad, so clearly the best choice of grade is the one which has been chosen the least throughout the course of the game, between 50 and 80.

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

LumberJack

Kicking ass and taking logs, and it's all out of ass.

Look for the upper quartile of all the scores, and start logging that. Assume your fellow classmates are improving, and try and work out the slope of that graph, to predict the next highest scores.

Keep a moving average, so low initial scores don't hold you back,

{
    name: "LumberJack",
    scoresLog: [],
    upperQuartile(scores) {
      return scores.sort((a, b) => a - b)[Math.floor(scores.length*0.75)]
    },
    run(scores) {
        if(!scores)  {this.scoresLog.push(80);return 80;}
        const upperQScore = this.upperQuartile(scores);
        this.scoresLog.push(upperQScore);
        this.scoresLog = this.scoresLog.slice(-4)
        
        const avgScoresLog = average(this.scoresLog)
        const top = this.scoresLog.map((score, index) => (score-avgScoresLog)*0.5*index);
        const bottom = this.scoresLog.map((score, index) => (index-scores.length)**2)
        const intercept = this.scoresLog[0]-(sum(top)/sum(bottom));
        const predicted = this.scoresLog.length*(sum(top)/sum(bottom))+intercept;
        return Math.min(100, predicted);
    }
}

See the bot run below!

const sum = (array) => array.reduce((a,b) => a+b);
const average = (array) => sum(array)/array.length;
const bot = {
    name: "LumberJack",
    scoresLog: [],
    upperQuartile(scores) {
      return scores.sort((a, b) => a - b)[Math.floor(scores.length*0.75)]
    },
    run(scores) {
        if(!scores)  {this.scoresLog.push(80);return 80;}
        const upperQScore = this.upperQuartile(scores);
        this.scoresLog.push(upperQScore);
        this.scoresLog = this.scoresLog.slice(-4)
        
        const avgScoresLog = average(this.scoresLog)
        const top = this.scoresLog.map((score, index) => (score-avgScoresLog)*0.5*index);
        const bottom = this.scoresLog.map((score, index) => (index-scores.length)**2)
        const intercept = this.scoresLog[0]-(sum(top)/sum(bottom));
        const predicted = this.scoresLog.length*(sum(top)/sum(bottom))+intercept;
        return Math.min(100, predicted);
    }
}

console.log(bot.run([10,10,10,10,10,20,30,40,50,100]))
console.log(bot.run([10,10,80,90,70,20,30,40,50,100]))
console.log(bot.run([10,10,80,90,80,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))
console.log(bot.run([100,100,100,90,90,20,30,40,50,100]))

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

Chain estimator

Records the several latest averages, downsamples them, records the states, uses the history record to estimate the next average, and uses it to get the optimal score given the average.

{
  name: "Chain estimator",
  bin_n: 25,
  history_len: 2,
  avg_history: null,
  table: {},
  run(scores) {
    let weighted_mean = (values, weights) => {
      const result = values
        .map((value, i) => {
          const weight = weights[i]
          const sum = value * weight
          return [sum, weight]
        })
        .reduce((p, c) => [p[0] + c[0], p[1] + c[1]], [0, 0])
    
      return result[0] / result[1]
    };
    
    let avg = average(scores);
    let bin_n = this.bin_n;
    let bin_w = 100/bin_n;

    if(this.avg_history === null){
      this.avg_history = Array(this.history_len).fill();
    }

    if(this.avg_history[0] === null){
      let out = 50 + 0.4*avg;

      // updates history
      this.avg_history = this.avg_history.slice(1).concat([avg])

      return Math.min(Math.max(Math.round(out),1),100);
    }else{
      // gets the "bins"
      let bin = (v => Math.max(Math.ceil(v/bin_w)-1, 0));
      let bins = this.avg_history.map(bin);
      let bin_cur = bin(avg);

      // updates the table
      for (state in this.table) {
        this.table[state] = this.table[state].map((v,i)=>v*0.95);
      }
      if(!(bins in this.table)){
        this.table[bins] = Array(bin_n).fill(1);
      }
      this.table[bins][bin_cur] += 1;
      
      // estimates the avg
      let state = bins.slice(1).concat([bin_cur]);
      let mids = Array(bin_n).fill().map((_,i) => (i+.5)*bin_w);
      if(!(state in this.table)){
        this.table[state] = Array(bin_n).fill(.1);
      }
      let avg_est = weighted_mean(mids, this.table[state].map((v,i)=>Math.pow(v,5)));
      let out = 50 + 0.4*avg;

      // updates history
      this.avg_history = this.avg_history.slice(1).concat([avg])

      return Math.min(Math.max(Math.round(out),1),100);
    }
  }
}
```
\$\endgroup\$
6
\$\begingroup\$

SimpleWeighted

{
    name: "SimpleWeighted",
    weights: (E => {
        let csum = [...Array(101).keys()].map((s=>n=> s+=Math.sqrt(n*(100-Math.abs(4/5*E-n))))(0));
        return csum.map(x => 1 - x / csum[100])
    })(58.863975225),
    run() {
        let rand = Math.random();
        return 1+this.weights.findIndex(w => rand >= w)
    }
}

Weights each integer \$x\$ by its score \$w(x)=\sqrt{x\left(100-\left|\frac45E-x\right|\right)}\$, where \$E=\frac{\sum_{x=1}^{100}xw(x)}{\sum_{x=1}^{100}w(x)}\approx 58.863975225\$ is the mean of its own distribution.

For a continuous distribution, \$E\approx58.6219755033\$, but using its own mean doesn't seem like it makes for a very good strategy anyways.

\$\endgroup\$
2
  • 5
    \$\begingroup\$ You cannot use an arrow function and have access to the context of this. Changing run: _ => { to run() { fixes the issue. \$\endgroup\$ Apr 29, 2021 at 8:58
  • \$\begingroup\$ x is not defined \$\endgroup\$ May 2, 2021 at 1:23
5
\$\begingroup\$

Optimise Mean

{
  name: "Optimise Mean",
  run(scores) {
    const avg = scores ? scores.reduce((a,b)=>a+b) / scores.length : 80;
    return .4*avg+50;
  }
}

Maximises the geometric mean between game theory and cybersecurity score, assuming the average score will be the same as from the previous submissions. Maths ftw!

\$\endgroup\$
5
\$\begingroup\$

Linear Extrapolator

Extrapolates linearly based on the two previous averages to estimate the average of this round. Estimate is clamped to previous minimum and maximum averages. Then maximize points assuming that this estimate will be the average for this round.

{
    name: "Linear Extrapolator",
    iteration: 0,
    average1: 0,
    average2: 0,
    minAverage: 0,
    maxAverage: 0,
    run(scores) {
        this.iteration++;
        if (this.iteration == 1) {
            return 77;
        }
        if (this.iteration == 2) {
            this.average2 = average(scores);
            this.minAverage = this.average2;
            this.maxAverage = this.average2;
            return 50 + this.average2 * 0.4;
        }
        this.average1 = this.average2;
        this.average2 = average(scores);
        let extrapolatedAverage = this.average2 + this.average2 - this.average1;

        this.minAverage = Math.min(this.minAverage, this.average2);
        this.maxAverage = Math.max(this.maxAverage, this.average2);
        extrapolatedAverage = Math.max(extrapolatedAverage, this.minAverage);
        extrapolatedAverage = Math.min(extrapolatedAverage, this.maxAverage);

        return 50 + extrapolatedAverage * 0.4;
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf! Nice first answer! \$\endgroup\$ Apr 29, 2021 at 20:19
  • \$\begingroup\$ @RedwolfPrograms Thanks. It doesn't do that well when random answers cause oscillations, but if a consensus emerges when there are more bots it might do ok, I hope. \$\endgroup\$ Apr 29, 2021 at 20:31
  • 1
    \$\begingroup\$ I like this one, this is the sort of answer I had in mind when I decided to give the previous round's scores \$\endgroup\$ Apr 29, 2021 at 23:30
5
\$\begingroup\$

AverageAverage

Assumes the average score will be the average of the average of scores of all rounds before it (except the first round).

  {
    name: "AverageAverage",
    avgLog: [],
    isFirstRound: true,
    gmean(a, b) {
      return Math.sqrt(a * b);
    },
    scoreForAvg(avg) {
      let delta = 100;
      let score = 100;
      let newScore = 0;
      while (delta > 0.05) {
        newScore = this.gmean(score, 100 - Math.abs((avg * 0.8) - score));
        delta = Math.abs(score - newScore);
        score = newScore;
      }
      return score;
    },
    run(scores) {
      if (this.isFirstRound) {
        this.isFirstRound = false;
        return 73;
      }
      this.avgLog.push(average(scores));
      let avgavg = average(this.avgLog);
      return this.scoreForAvg(avgavg);
    }
  }
\$\endgroup\$
1
5
\$\begingroup\$

Lucky Dice Kid

The younger brother to Lucky Dice Bot, this kid is a big D&D fan and only trusts his d20s. Since rolling dice clearly solves all problems optimally, he ignores all of the previous round input, rolls 7 d20s, discards the lowest two, and takes the sum of the rest. This produces a value between 5 and 100, with average value roughly 65.

{
  name: "LuckyDiceKid",
  run(_scores) {
    let total = 0;
    let values = [];
    for (let i = 0; i < 7; i++) {
      let curr = Math.floor(Math.random() * 20) + 1;
      values.push(curr);
      total += curr;
    }
    values.sort((x, y) => (x - y));
    total -= (values[0] + values[1]);
    return total;
  }
}
\$\endgroup\$
5
\$\begingroup\$

Grumpy Chaotic

Mr. Grumpy has a beef with his classmates and thus he wants to worsen everyone's grades. However the next day he realised he still needs a good grade in CSEC.

...Lets just say he has frequent mood swings.

    {
        name: "Grumpy Chaotic",
        mood: true,
        run() {
            this.mood=!this.mood;
            return this.mood?100:1;
        }
    }
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Thrasher but more extreme \$\endgroup\$ May 1, 2021 at 13:31
5
\$\begingroup\$

xXx_Markov_143_xXx

Going from his immense experience of playing FPS games like BS:GO, young Markov realised he does not need to model the entire game in order to play well, he can just predict what the best 5% of players will do, and do it before them.

    {
        name: "xXx_Markov_143_xXx",
        mark: null,
        n_rounds: 0,
        old_average: 50,
        run(scores) {
            this.n_rounds++;
            let last_average = average(scores);
            scores = scores.filter((x)=> 100 >= x && x > 0);
            let evaluated_scores = scores.map((score) => [score, score * (100 - Math.abs(last_average * 0.8 - score))]);
            evaluated_scores.sort((a,b) => a[1] - b[1]);
            let smart_average = average(evaluated_scores.slice(Math.floor(evaluated_scores.length * 0.95)).map((a)=>a[0]));

            if (this.n_rounds == 1) {
                this.old_average = smart_average;
                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]++;
                }
                return 77;
            }

            let quantized_avg = Math.round(2*smart_average);
            this.mark[Math.round(2*this.old_average)][quantized_avg]++;
            this.old_average = smart_average;

            // Compute a markov chain prediction
            let x_half_filter = 5;
            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;
                    }
                }
            }

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

            return probability_moment / probability_sum;
        }
    }
\$\endgroup\$
5
\$\begingroup\$

Impatience

Impatience is the most rational bot, and wants all the other bots to just hurry up and be more rational already.

  1. All the bots will behave rationally, eventually.
  2. Some of the bots don't care about game theory, but all the others do.
  3. There is a single optimal solution.
  4. If a bot can change its answer and get a better score, the rational action is to change its answer.

Therefore, if there are n bots and m of them don't care about game theory, the exam results will converge to a Nash equilibrium, which is the rational solution.

Impatience outputs this answer to begin with, and never changes its answer unless evidence suggests it was (rationally) mistaken about the value of m. Impatience is the most rational bot.

{
    name: "Impatience",
    optimal: average => 0.4*average + 50,
    run(scores) {
        const n = scores.length;
        // rational actors who don't care about game theory
        // will output 100, to win the cybersecurity exam
        const m = scores.filter(v => v == 100).length;

        // other bots are slow, so simulate them
        do {
            const average = scores.reduce((a,b)=>a+b) / n;
            const optimal = this.optimal(average);
            // other bots take a while to get there
            scores = scores.map(v => v==100 ? 100 : 0.5*(v + optimal));
        } while ((new Set(scores)).size > ( 0?0 :3 ));

        scores = new Set(scores);
        scores.delete(100);
        if (scores.size > 0) {
            return Math.max.apply(Math, scores);
        } else {
            return 90;
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ This one outputs 0 consistently \$\endgroup\$ May 2, 2021 at 1:22
  • \$\begingroup\$ @EnderShadow8 It is the most rational bot! \$\endgroup\$
    – wizzwizz4
    May 2, 2021 at 10:40
  • \$\begingroup\$ Outputs 0 due to my tests so it's DQ unfortunately. \$\endgroup\$ May 2, 2021 at 12:29
4
\$\begingroup\$

NaiveMeta

Bot attempts to categorize other bots and analyze their strategies to weight its own score formula. Determines a stable score based on static bot scores, and then determines the number of bots optimizing(playing well) in the last round. Approximates that all optimizers will roughly lean toward the optimal score last round. Ignores other(assumed random) bots. Then calculates an a weighted average bet between the two optimal scores weighted based on the number of bots of each type.

{
    name: "NaiveMeta",
    persitentScores: [],
    otherScores: [],
    lastAvg: 0,
    round: 0,
    sWeight:.2,
    oWeight:1,
    run(scores) {
      this.round++;
      if (this.round === 1) {
        return 75;
      }
      if(this.round === 2){
        this.persitentScores = scores;
      }
      var optimizer = 0;
      var avg = average(scores);
      var optimalScoreLR = 50+ .4*avg;
      var newPScores = [];
      scores.forEach(s=>{
        let i = this.persitentScores.indexOf(s);
        if(i!==-1){
            this.persitentScores.splice(i,1);
            newPScores.push(s);
        }
        else if( Math.abs(s - optimalScoreLR) <=12){
            optimizer++;
        }
      });
      this.persitentScores = newPScores;
      var pOptimalScore =  50+.4*average(this.persitentScores);
      if (this.round === 2) {
        return optimalScoreLR;
      }
      return ((pOptimalScore*this.persitentScores.length*this.sWeight) + (optimalScoreLR  * optimizer*this.oWeight))/(this.persitentScores.length*this.sWeight+optimizer*this.oWeight);
    }
  }
\$\endgroup\$
1
4
\$\begingroup\$

Geothmetic Meandian

Not a serious entry, but seemed appropriate.

{
  name: "Goethmetic Meandian",
  run: scores => {
    let a = new Float64Array(scores.filter(x => x > 0));
    do {
      a.sort();
      a = [
        a.reduce((x, y) => x + y, 0) / a.length,
        Math.pow(a.reduce((x, y) => x * y, 1), 1 / a.length),
        a.length % 2 ? a[Math.floor(a.length / 2)] : (a[Math.floor(a.length / 2)] + a[Math.ceil(a.length / 2)]) / 2,
      ];
    } while (Math.abs(a[0] - a[1]) > 0.0001 || Math.abs(a[1] - a[2]) > 0.0001);
    return Math.min(100, Math.max(1, Math.round(a[0])));
  },
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Was waiting for someone to do this. Few problems though, not sure if my controller code is outdated, but you're missing a score.filter((x) => x > 0) to prevent a 0 score from slipping in (technically shouldn't happen, but always sanitize your inputs). If a 0 does slip in, it prevents the function from converging at all. Also instead of using !== you probably should use Math.abs(a[0] - a[1]) < 0.0001 or some other small value, to avoid other undending loop issues. Finally you should use || instead of && to actually stop the loop when both conditions are un-met. \$\endgroup\$
    – IQuick 143
    May 1, 2021 at 20:31
  • 1
    \$\begingroup\$ This one doesn't halt. I think it might be due to the issue stated above \$\endgroup\$ May 2, 2021 at 1:21
4
\$\begingroup\$

LastMinute HistoryAnalyzer

This bot records differences and takes advantage of that the averages periodically wobble, and tries to guess based on that. It doesn't expect to win, but it will do its best to reach a good ranking.

It's named "LastMinute" because I submitted just before the deadline, but its name also applies to its behaviour: it analyzes the last moments of history.

{
  name: 'LastMinute HistoryAnalyzer',
  avgs: new Array(6).fill(63),
  diffs: new Array(3).fill(1),
  run(prev){
    const prevAvg = average(prev)
    this.avgs.push(prevAvg)
    this.avgs.shift()
    this.diffs.push(this.avgs[this.avgs.length-1] - this.avgs[this.avgs.length-2])
    const diffs4 = this.diffs.shift()
    const diffs2 = this.diffs[1]
    const avg = average([diffs2, diffs4]) + prevAvg
    return (77.9 + (avg - 70) * 0.3) //Magic formula for converting a guessed average to the corresponding equilibrium point (inaccurate when average is far from 70, but that's what I came up with)
  }
},

PS: I'm completely new to programming challenges, KotH and codegolf.se, but I like programming in JavaScript and like challenges, so I decided to give it a try.


Actually, I wanted to make it like this (it doesn't make much difference, though), but I was tired and screwed it up:

{
  name: 'LastMinute HistoryAnalyzer',
  avgs: new Array(6).fill(63),
  diffs: new Array(3).fill(1),
  run(prev){
    const prevAvg = average(prev)
    this.avgs.push(prevAvg)
    this.avgs.shift()
    this.diffs.push(this.avgs[this.avgs.length-1] - this.avgs[this.avgs.length-2])
    const diffs4 = this.diffs.shift()
    const diffs2 = this.diffs[1]
    const avg = average([diffs2, diffs4]) + average(this.avgs)
    return (77.9 + (avg - 70) * 0.3) //Magic formula for converting a guessed average to the corresponding equilibrium point (inaccurate when average is far from 70, but that's what I came up with)
  }
},
\$\endgroup\$
3
\$\begingroup\$

90ies

{
  name: "90ies",
  run() {return 90}
}

After thinking very hard and not getting very far, this seems to be the one and only optimal solution.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Apr 29, 2021 at 13:57
3
\$\begingroup\$

Returns 50 + 0.4*avg(scores):

{
  name: "Near-stable",
  run: s => {
    return 50 + 0.4*s.reduce((a, b) => a + b, 0)/s.length;
  }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$ Apr 29, 2021 at 21:30
  • \$\begingroup\$ I feel like we already have at least four of these \$\endgroup\$ Apr 29, 2021 at 23:24
  • \$\begingroup\$ @EnderShadow8, I just found where the score function would have a 0 derivative, but looks like I'm not the first one. I didn't look at other submissions before submitting mine, but you'll have to take my word for it \$\endgroup\$
    – Arseny
    Apr 29, 2021 at 23:27
  • \$\begingroup\$ That's ok, just remember to check next time or you might be downvoted to hell in the future \$\endgroup\$ Apr 29, 2021 at 23:29
  • \$\begingroup\$ Yeah, i almost did another submission, 5/6*100, which is the fixed point, but I saw someone else had done it already \$\endgroup\$
    – Arseny
    Apr 29, 2021 at 23:31
3
\$\begingroup\$

USACO (Unofficial)

Uses binary search to maximize its score.

(() => {
    function *stateMachine() {
        let left = 1;
        let right = 100;
        
        yield 51;
        
        let counter = 0;
        
        while (true) {
            counter++;
        
            const middle = left + (right - left) / 2;
            
            if (counter % 10 === 0) {
                left = Math.max(1, Math.random() * 100);
                right = Math.max(1, Math.random() * 100);
                
                if (left > right) [left, right] = [right, left];
            }
            
            const scores = yield middle;
            scores.sort((a, b) => a - b);
            
            let countLower = 0;
            let countHigher = 0;
            
            for (const score of scores) if (score < middle) countLower++;
            for (const score of scores) if (score > middle) countHigher++;
            
            if (countLower > countHigher) {
                right = middle;
            } else {
                left = middle;
            }
        }
    };
    
    const iterator = stateMachine();
    let score = iterator.next().value;

    return {
        name: "USACO (Unofficial)",
        run: scores => {
            const oldScore = score;
            score = iterator.next(scores).value;
            return oldScore;
        }
    };
})()
\$\endgroup\$
2
  • 3
    \$\begingroup\$ This sign can't stop me because I can't read! Is it ok for me to add this bot to the game? (despite unofficial in the title) \$\endgroup\$ Apr 30, 2021 at 10:43
  • \$\begingroup\$ sure thing (padding padding padding annoying padding stack exchange is so nosy lol) \$\endgroup\$ Apr 30, 2021 at 11:04
3
\$\begingroup\$

Overshoot (slightly)

I started off with the idea that a CS mark below the target (80% of the average CS mark) is very penalizing. Better then to be too high than too low.

I started off taking the 80th percentile of past averages as my estimation for next round average CS mark, but soon realized that it was too much. Some tweaking of the parameters later I ended up with this result, which takes just slightly above the median.

{
    name: "Overshoot (slightly)",
    historyAvg: [],
    rounds: 0,

    run(scores) {
        this.rounds++
        if (this.rounds == 1) return 75.5;

        this.historyAvg.push(average(scores))
        this.historyAvg.sort((a,b) => a-b);
        let estimatedAvg = this.historyAvg[Math.ceil(this.historyAvg.length * 0.535)-1]
        let score = 50 + estimatedAvg * 2/5;

        return score
    }
},
\$\endgroup\$
3
\$\begingroup\$

Greedy

Assumes that all other bot keep their scores the same as last round, and chooses a score that maximizes own_point - max(other_bots_points).

{
  name: "Greedy",
  run(scores){
    let max_index = (arr => arr.indexOf(Math.max.apply(Math, arr)));
    let point = (avg) => {
      return (s) => Math.sqrt(s*(100-Math.abs(0.8*avg-s)))
    }
    let goal = (scores) => {
      return (mine) => {
        let avg = average(scores.concat([mine]));
        return point(avg)(mine) - Math.max(...scores.map((v,i)=>point(avg)(v)));
      }
    } 

    let avg = average(scores);
    let range = Array(101).fill().map((_,i)=>i);
    return range[max_index(range.map((v,i) => goal(scores)(v)))];
  }
}
\$\endgroup\$
2
\$\begingroup\$

SimpleCalculus

Just the result of plugging x = avg into @Bubbler's formula.

{
    name: "SimpleCalculus",
    run: _ => 250 / 3,
}
\$\endgroup\$
1
  • \$\begingroup\$ 33rd out of 60... for such a simple program, I'll take that. \$\endgroup\$
    – Neil
    May 2, 2021 at 8:43
2
\$\begingroup\$

Elevens

{
    name: "Elevens",
    run() { return (Math.floor(Math.random() * (10 - 1) ) + 1) * 11; }
}

Randomly returns 11, 22, 33, 44, 55, 66, 77, 88 or 99.

\$\endgroup\$
2
\$\begingroup\$

7-ELEVEn

{
  name: "7-ELEVEn",
  run() { return 77 }
}
\$\endgroup\$
2
\$\begingroup\$

ExponentialMovingAverage

{
    name: 'ExponentialMovingAverage',
    prev: 80,
    run(scores) { return (scores && scores.length ? average(scores) : 80) * 0.225 + this.prev * 0.775 },
}

Returns EMA of the average score. Of course, I forgot to update the previous value, so it does not calculate the EMA, but some mix of the initial and the average score, but it gives much better results than I expected.

\$\endgroup\$
2
\$\begingroup\$

Woulda-Shoulda

{
  name: "WouldaShoulda",
  ownLast: 0,
  isFirst: true,
  run(scores) {
    if (this.isFirst) {
      this.isFirst = false
      this.ownLast = 80
    } else {
      let count = scores.length
      let otherAvg = (sum(scores) - this.ownLast) / (count - 1)
      this.ownLast = (80 * count + otherAvg * count - otherAvg) / (2 * count - 1)
    }
    return this.ownLast
  }
}

Returns 80 the first round, then each subsequent round returns what would have been the best option the previous round.

\$\endgroup\$
2
\$\begingroup\$

AverageAverageAverage

{
    name: "AverageAverageAverage",
    run: _ => 77.22599053004494
}

Turns out AverageAverage is pretty damn good. So, AverageAverageAverage uses an average of its averages.

(Occasionally beats its dynamic namesake in test runs, but I suspect this won't last as more bots get added lmao)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Isn't this the reason 7eleven did so well in my test runs? \$\endgroup\$ May 1, 2021 at 9:27
  • 2
    \$\begingroup\$ @EnderShadow8 Didn't even see that one until now, but considering the difference in their constants is less than .226, ...probably \$\endgroup\$ May 1, 2021 at 9:35
  • 2
    \$\begingroup\$ Also the reason people were still trying to beat Simpleton in the early days of this challenge \$\endgroup\$ May 1, 2021 at 9:36
  • 1
    \$\begingroup\$ Awesome, love it! \$\endgroup\$
    – David
    May 2, 2021 at 9:59
2
\$\begingroup\$

Chessmaster

Game theory is a lot easier when you know what the other players are going to do.

(In lieu of constantly editing this answer, it is generated by a Stack Snippet based on the leaderboard. I hope this is okay. If not, I'll try to ninja-edit the final version in just before the deadline.)

/* Configuration */

var QUESTION_ID = 224621; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!)qM4PLHIEQza67lA3AlA";

/* App */

var answers = [], answer_page = 1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  let oreq = new XMLHttpRequest();
  oreq.addEventListener("load", function() {
    let data = JSON.parse(this.responseText);
    answers.push.apply(answers, data.items);
    if (data.has_more) getAnswers();
    else process();
  });
  oreq.open("GET", answersUrl(answer_page++));
  oreq.send();
}

getAnswers();

function process() {
  let codez = answers.map(a => {
    var body = a.body_markdown;
    
    let x = [];
    let stage = 0;
    body.split("\n").forEach(line => {
      if (line.startsWith("```")) {
        stage += 1;
      } else if (stage == 1) {
        x.push(line);
      }
    });
    if (stage > 0) {
        return x.join("\n");
    }

    x = body.split("\n").filter(
      l => l && l.startsWith("    ")
    );
    return x.join("\n");
  }).map(x => (new DOMParser()).parseFromString("<!DOCTYPE html><body>" + x, "text/html").body.textContent);
  
  document.getElementById("here").innerText = JSON.stringify(codez);
}
<code><pre>
{
    name: "Chessmaster",
    pieces: (
        codes => codes.map(
            code => { try {
                return (new Function('return ' + code + ';'))();
            } catch {
                console.log("could not parse", code);
                return undefined;
            }; }
        ).filter(p => p !== undefined)
    )(<span id="here"></span>),
    run(scores) {
        const prediction = this.pieces.map(
            piece => { try {
                return parseInt(piece.run(scores.slice()));
            } catch {
                console.log("could not run", piece.name);
                return NaN;
            }; }
        ).filter(s => 0 <= s && s <= 100);
        const average = prediction.reduce((a,b)=>a+b) / prediction.length;
        return 50 + 0.4*average;
    }
}
</pre></code>

\$\endgroup\$
1
  • \$\begingroup\$ This one doesn't work.. yet? \$\endgroup\$ May 2, 2021 at 1:22
2
\$\begingroup\$

Equilibrium

The optimal score is 50 + (0.4 * avg). There is an equilibrium point at approximately 83.333 where the average score is also the optimal score, e.g. avg = 50 + (0.4 * avg).

This bot assumes the average will move towards the equilibrium point, so it picks a point halfway between the equilibrium and the last average. It then chooses the optimal score for that halfway point.

{
  name: "Equilibrium",
  equil: 83.333,
  first_round: true,
  run(scores) {
    if (this.first_round) {
      this.first_round = false;
      return this.equil;
    } else {
      let midpoint = (average(scores) + this.equil) / 2;
      return (50 + 0.4*midpoint);
    }
  }
}
\$\endgroup\$
2
2
\$\begingroup\$

SettleDown

Starts off really unpredictably, but over time sets its result closer and closer to the average of the last round

(if this doesn't run, please let me know!)

{
    name: "SettleDown",
    rounds: 0,
    lastAverage: 0,
    run(scores) { 
        this.rounds++ 
        this.lastAverage = (sum(scores) - this.lastAverage) /(scores.length - 1)*0.8
        return (this.lastAverage + ( Math.floor( Math.random() * 100 - 50) / (this.rounds/5+1)))%101
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ It should have run(scores) { instead of run() { \$\endgroup\$
    – gsitcia
    May 2, 2021 at 2:14
  • \$\begingroup\$ ah, thanks! I knew I missed something... \$\endgroup\$
    – DPS2004
    May 2, 2021 at 2:49
1
\$\begingroup\$

That mean average Joe

{
  name: "That mean average Joe",
  Joe: [],
  run( scores ) {
    this.Joe.push(average(scores)); // like.no.one(ever(did));
    return average(this.Joe)*1.1111111111111111;
  }
}

This returns the mean of the averages of the scores of all the turns played so far, multiplied by 1.1111111111111111.

Why 1.111111111111111?

Suppose that the average of every turn is always the same constant and let's take it as the reference unit.

Now knowing that in the next turn the average of the scores will be 1, our smart move for the Game Theory exam would be to return 0.8.

However in this way we would score 100% in Game Theory (impossible to do better) and 80% in Cybersecurity (relative to the class average) and since the KOTH's final score would be the geometric mean of the two exams, we'd better find a compromise between the two rather than maximise one of them.

The perfect compromise would be scoring 88.88888...% in both, cause that's 11.11111...% less than 100% and more 80%.

To score 88.88888...% in Game Theory means being 11.11111...% away from the average of Cybersecurity scores, doesn't matter if it is 11% more or 11% less.

However if we move to 11.11111...% more than the average, rather than less, we would get a better score in Cybersecurity, while still scoring the optimal 88.88888...% in Game Theory.

So returning 11.11111...% more than the average of the scores is what we want.

In the KOTH challenge the average of the scores is unlikely to be the same every turn, so as a reference unit we take the mean of the averages of the scores of all the turns played so far.

NOTE: This wasn't the actual reasoning that brought me to the constant, my initial reasoning was quite similar but buggy and I tried to fix it till I came up with this. However I wouldn't say that this constant is the result of luck, but rather of intuition. After all it seems that the purpose of our reasoning has always been to support and explain our intuitions.

\$\endgroup\$
4
  • 5
    \$\begingroup\$ Why don't you just do *10/9 instead? \$\endgroup\$
    – leo3065
    Apr 30, 2021 at 18:40
  • 4
    \$\begingroup\$ 1.1111111111111111 is harder, better, faster, straighter. 10/9 could be rounded to 1.1111111111111112 which is less accurate. \$\endgroup\$
    – anotherOne
    Apr 30, 2021 at 19:24
  • 2
    \$\begingroup\$ Is "harder, better, faster, straighter" a reference to "harder, better, faster, stronger"? \$\endgroup\$
    – leo3065
    May 1, 2021 at 3:49
  • 1
    \$\begingroup\$ @leo3065 yes, where straighter is for "more accurate", harder and faster because it's hardcoded, and better as a consequence. \$\endgroup\$
    – anotherOne
    May 1, 2021 at 9:38

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.