King of the Hill: Nose Poker - An ogre game for ogres

Question

Links

• Chat room
• The official game report
• Github repo - In case of bugs to report

Here's the official score table:

<script src="https://ajfaraday.github.io/nose_poker/ogres.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script><table> <thead> <tr> <th>Ogre</th> <th>Hand</th><th>NP</th> <th>Reason</th> </tr></thead> <tbody id="clients"> </tbody></table><script type='text/javascript'>  
ogres.forEach( function(data_row){var row=$('<tr>'); var cell=$('<td>'); cell.html(data_row.name); row.append(cell); cell=$('<td>'); cell.html(data_row.hand); row.append(cell); cell=$('<td>'); cell.html(data_row.np); row.append(cell);row.append(cell);cell=$('<td>'); cell.html(data_row.reason); row.append(cell); $('tbody#clients').append(row);});</script>

Nose Poker is an ogre game played by a group of ogres. Each ogre brings a large nose and a small club.

On each hand, all the ogres will declare how many times they will poke their nose with the club.

Each time, the lowest bid(s) will be knocked out of the game, then the remaining ogres will poke their nose with the club their declared number of times.

Any ogre who has run out of nose will also be knocked out of the game.

The Challenge

Write the JavaScript code to play Nose Poker. You'll write a client class which plays the role of an ogre and makes the decision how to bid on each hand.

Your ogre starts the game with 500 nose points (np), and there is no way to recover np during the game. Each turn you will call controller.declare(pokes) and either fall out of the competition if you declare the lowest number of pokes, or your troll will lose the declared amount of np.

The goal is to stay in the game as long as you can.

There are three ways to be knocked out of the game:

• Failed to bid If something goes wrong and you don't make a bit, or bid zero or less, you're out.
• Cowardice! Your ogre chickened out and bid lower than everyone else.
• Has no nose Your ogre ran out of np and therefore has no nose. How does it smell? Like it's out of the game.

The Controller

Your client class will be passed a controller object which acts as it's interface to the game.

Here are the four functions it provides:

np(): The current amount of nose points that your ogre has.

this.controller.np();
// 450

hand_number() The number of the current hand the game is on.

this.controller.hand_number();
// 2

scores() An array of the amount of np each currently active ogre has.

this.controller.scores();
// [450, 250, 20]

Note: This is intentionally sorted in descending order of np so it is not possible to see how other ogres have been bidding.

declare(pokes) Here's the important one. Declare how many times your ogre will poke itself in the nose with a club.

this.controller.declare(10);

Getting the app

You're going to need node and npm, sorry.

• git clone https://github.com/AJFaraday/nose_poker.git
• cd nose_poker
• npm install

Writing a Client

Here's the template for your client class, add it to a js file in src/clients/working

module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
  }

};

You can then modify the play_hand() function, remember it must call this.controller.declare(pokes). (You can also be knocked out of the game for failing to do this).

When you're happy with it, run ./get_answers.sh from the nose_poker root directory. This will add your client to /src/clients.js (and also get the current set of clients from the Stack Exchange question). You only need to do this once.

After the first time you can run games to see the result of modifying your code by calling node script/play_game.js.

Submitting your Client

To add your client to the competition, answer this question.

• Name your ogre by including a title (h1, by starting the line with '#' or underlining it with '=' symbols)
  • The name should only contain alpha characters and underscores, no spaces please.
• Put the code in a code block.
• Please include a brief description of your ogre's strategy, and any other information you'd like to include.

The app will then periodically pick up answers, run the game, and update the score table in this question.

Forbidden stuff

In order to be accepted into the competition, your code must export a valid class which accepts a controller, has a play_hand() function, and will call this.controller.declare(pokes) at some point in that function. If it does not, the official instance will not import it.

The importer will also ignore any answers which use these terms:

• game - Please do not try to interact with the game directly
• Math.random - Let's keep this deterministic, so the result is definitive.
• setTimeout, setInterval - These lead to runtime oddities.
• eval, import - Just don't!

Default bots

Default Bot	Behaviour
go_home	Always bid 1
go_big	Bids 90% of np
half_way	Bids 50% of np

Answer 1

Sinus-oidal

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        var turn = this.controller.hand_number();
        var multiply = Math.sin(turn * Math.PI / 4);

        this.controller.declare(Math.floor(2 ** (multiply + 1)));
    }
};

Get it?

Answer 2

super_smart_bot

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    try_certain_win()
    {
        //we need to have more points than everyone else combined, plus 1 per player (though this bound is probably too weak)
        //bid as many points as the lowest-NP player has, plus 1
        let tcost = 0;
        let mcost = 999;
        let skipped = false;
        let other_scores = this.controller.scores().filter(a => skipped ? true : (a == this.controller.np() ? (skipped = true)*0 : true));
        for(let c of other_scores)
        {
            tcost += c + 1;
            if(c + 1 < mcost) mcost = c + 1;
        }
        if(this.controller.np() <= tcost)
            return false;
        this.controller.declare(mcost);
        return true;
    }
    min_safe_bid()
    {
        let skipped = false;
        let other_scores = this.controller.scores().filter(a => skipped ? true : (a == this.controller.np() ? (skipped = true)*0 : true));
        let res = Math.min(...other_scores) + 1;
        return res;
    }
    play_hand() {
        if(this.controller.hand_number() == 1)
        {
            this.controller.declare(2);
            return;
        }
        let scores = this.controller.scores();
        if(scores.length == 2) //optimal because this is the last round
        {
            this.controller.declare(this.controller.np() - 1);
            return;
        }
        if(this.try_certain_win()) return;
        let bid = this.controller.np() / this.controller.scores().length;
        bid = Math.min(bid, this.min_safe_bid());
        this.controller.declare(bid);
    }
};

Answer 3

Smart Median

module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

    play_hand() {
    // Beat the simple bots
    if(this.controller.hand_number() <= 5) {
        this.bid(this.controller.hand_number() + 1);
        return;
    }
    var scores = this.other_scores();
    var bid = Math.floor(this.median(scores) / scores.length) + 1; // Add 1 to win once there's only 1 opponent left
    this.bid(bid);
    }
  
  other_scores() {
    var scores = this.controller.scores();
    var myIndex = scores.indexOf(this.controller.np());
    scores.splice(myIndex, 1);
    return scores;
  }
  
  median(scores) {
    var half = Math.floor(scores.length / 2);
    return scores[half];
  }
    
    bid(value) {
        // Never bid more than the weakest player has
        var weak = Math.min(...this.controller.scores());
        // Never bid more than I have
    var me = this.controller.np();
    var final_bid = Math.min(value, weak + 1, me);
    this.controller.declare(final_bid);
    }

};

Chooses a bid based on the median score divided by the number of opponents remaining. The idea is that the more opponents there are, the more likely one is to bid low, so I am safer to bid lower as well. I also threw in some smart bidding features, like not bidding more than a guaranteed pass, to not lose too many points. I imagine this strategy will burn through too many points in the midgame to win, but I do think it'll place near the top.

Answer 4

Half-life

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        var np = this.controller.np()
        var bid = np < 10 ? np - 1 : Math.floor(np / 2);
        this.controller.declare(bid);
    }
};

Takes the number of nose points it has and bids half each time. However, if it has less than 10 np left, it goes all in. This is to hopefully defeat half_way.

Answer 5

Dumb Ogre

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        this.controller.declare(2);
    }
};

To be fair, ogres aren't known to be particularly smart.

A trivial bot to get the ball rolling :p

Answer 6

Exponential Ogre

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }

    play_hand() {
        let bid = 1 << this.controller.hand_number();
        this.controller.declare(bid);
    }
};

Starting at 2, the ogre doubles its bid every round. Quite similar to Reverse Pinocchio, but I got the idea independently.

Answer 7

Adaptive Bot

module.exports = class {


    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand()
    {
        if (this.controller.hand_number() == 1) {
            this.lastScores = this.controller.scores();
            this.controller.declare(2);            
            return;
        }

        var scores = this.controller.scores();
        var finalBid = 100;
        for (var i = 0; i < scores.Length; i++) {
            for (var j = 0; j < this.lastScores.Length; j++) {
                if (this.lastScores[j] - scores[i] < finalBid) {
                    finalBid = this.lastScores[j] - scores[i];
                }
            }
        }

        this.lastScores = scores;    

        this.controller.declare(finalBid + 1);
    }
};

Starts in the first round by bidding 2, to not get kicked out immediately (due to Go_Home bot).

Then, assuming the bots stay in the same order, find out what everyone bid by finding the smallest difference between the previous turn and the current one.

As all bots I have seen so far reduce their bid monotonically, finding the lowest bid that survived and adding 1 will ensure that you survive next round.

EDIT: I dont have access to real coding tools right now, so I cant upload it/fix bugs. But I hope I made the strategy clear, so if anyone wants to copy this into a working bot, feel free to do so :)

EDIT2: The bots was completely busted and only bid 101 each turn :O Now it should work properly, so please update it again :D

Answer 8

Oldgre

Oldgre has perfected his strategy over many years.

Whippersnappgres!

module.exports = class {
  
  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
    const x = this.controller.hand_number();
    this.controller.declare(
      -     0.000006858186 * x ** 11
      -     0.000199732658 * x ** 10
      +     0.024797517263 * x ** 9
      -     0.737278798843 * x ** 8
      +    11.416562524617 * x ** 7
      -   107.788528491826 * x ** 6
      +   656.517974108233 * x ** 5
      -  2615.799102867764 * x ** 4
      +  6707.381768918599 * x ** 3
      - 10515.725107130049 * x ** 2
      +  8997.738815265786 * x ** 1
      -  3130.528128281523 * x ** 0
    );
  }

};

^{This is largely a proof of concept and, for the sake of the competition, I won't keep updating it.}

Answer 9

Simple Optimization Thing

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        var count = this.controller.scores().length;
        var min = Math.min(...this.controller.scores());

        this.controller.declare(min / count);
    }
};

Not sure if this strategy will work at all :p

Answer 10

Quicksort Ogre

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        var turns = this.controller.hand_number();

        this.controller.declare(Math.round(turns * Math.log(turns)) + 4);
    }
};

Ogres don't understand time complexity, but they do understand being poked on the nose \$n\log n\$ times. Small constant offset to prevent being immediately eliminated.

Probably my last somewhat trivial bot, I just want to see how something between the linear and exponential strategies would do (and quadratic was a bit too boring :p).

Answer 11

Troll Adaptive

Exactly the same as Adaptive by @Nurator, except increases it's bid the second round to eliminate the original Adaptive:

module.exports = class {

    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand()
    {
        if (this.controller.hand_number() == 1) {
            this.lastScores = this.controller.scores();
            this.controller.declare(2);            
            return;
        }
        else if (this.controller.hand_number() == 2) {
            this.lastScores = this.controller.scores();
            /* Adaptive will bid 3 since 2 is the lowest number. Thus, bidding 4 will eliminate Adaptive */
            this.controller.declare(4);            
            return;
        }

        var scores = this.controller.scores();
        var finalBid = 75;
        for (var i = 0; i < scores.Length; i++) {
            for (var j = 0; j < this.lastScores.Length; j++) {
                if (this.lastScores[j] - this.scores[i] < finalBid) {
                    finalBid = this.lastScores[j] - this.scores[i];
                }
            }
        }

        this.lastScores = scores;    

        this.controller.declare(finalBid + 1);
    }
};

Can easily be defeated by increasing your bid in the third round instead, and the bot after can be easily defeated in the fourth round etc.

Answer 12

Super dumb bot

According to the instructions as I understand them, my own bot's score is returned somewhere in scores(); if this is not the case, comment out the lines starting with the line if (score == sscore) and continuing to the else.

module.exports = class {
    constructor(controller) {
        this.controller = controller;
    }
    
    play_hand() {
        if(this.controller.hand_number() == 1)
        {
            // Go Home Bot makes everybody else need to do this nonsense on the first turn rather than really try.
            this.controller.declare(2);
            return;
        }
        if(this.controller.hand_number() == 2)
        {
            // Get rid of the other not-really-competing bot.
            this.controller.declare(3);
            return;
        }
        var myscore = this.controller.np();
        var sscore = myscore;
        var scores = this.controller.scores();
        var ctr = 0;
        for (var i = 0; i < scores.length; i++) {
            var score = scores[i];
            if (score != 0)
                if (score == sscore)
                    sscore = 0;
                else
                    ctr+=1;
        }
        var value = (ctr < 2) ? 0
             : Math.floor(myscore / ctr);
        this.controller.declare(value);
    }
};

Either I know the optimal strategy off the top of my head or I don't. I put no effort into finding out whether or not I am right. The long loop just determines how many other bots are in the game. If the specifications had been written tighter it could be replaced by var ctr = scores.length - 1;

Answer 13

Knockout

module.exports = class {

    constructor(controller) {
      this.controller = controller;
    }
  
    play_hand() {
      let hand = this.controller.hand_number()
      if(hand == 12){
           this.controller.declare(2);
           return;
      }
      if(this.controller.scores.length == 2){
        this.controller.declare(this.controller.np() - 1)
        return;
      }
      this.controller.declare(500 / (this.controller.scores().length + hand + 2) + 20 * (hand > 7) + 5 * (hand > 9) + 5 * (hand > 9))
    }
  
  };

A very simple strategy with some small tweaks that allow it to win! Has been complicated a bit.

Basically tries to spend roughly the same amount each turn by going 500 / original number of bots. Of course, it's impossible to calculate the original number of bots, so it counts the current amount + the hand number.

Has several tricks, including going all-in at the end, and playing 2 on round 12 because oldgre will always play 1.

I'm not sure what's up with the snippet, but it is winning locally:

Answer 14

Incremental ogre

module.exports = class {

  constructor(controller) {
    this.controller = controller;
  }

  play_hand() {
    var bid = this.controller.hand_number() * 10
    this.controller.declare(bid);
  }

};

Bids 10 more each round.