title: Snowball Fight KoTH!

text:
# Question
Title: Snowball Fight KoTH!
# Results (May 22 2017 21:40:37 UTC)

`Master` won 18 rounds, lost 2 rounds, and tied 0 rounds
`Save One` won 15 rounds, lost 3 rounds, and tied 2 rounds
`Machine Gun` won 14 rounds, lost 3 rounds, and tied 3 rounds
`Monte Bot` won 14 rounds, lost 3 rounds, and tied 3 rounds
`Amb Bot` won 12 rounds, lost 8 rounds, and tied 0 rounds
`Coward` won 11 rounds, lost 3 rounds, and tied 6 rounds
`Pain in the Nash` won 11 rounds, lost 9 rounds, and tied 0 rounds
`Nece Bot` won 10 rounds, lost 7 rounds, and tied 3 rounds
`Naming Things is Hard` won 10 rounds, lost 7 rounds, and tied 3 rounds
`The Procrastinator` won 10 rounds, lost 8 rounds, and tied 2 rounds
`Yggdrasil` won 10 rounds, lost 10 rounds, and tied 0 rounds
`Simple Bot` won 9 rounds, lost 4 rounds, and tied 7 rounds
`Table Bot` won 9 rounds, lost 6 rounds, and tied 5 rounds
`Prioritized Random Bot` won 8 rounds, lost 7 rounds, and tied 5 rounds
`Upper Hand Bot` won 7 rounds, lost 13 rounds, and tied 0 rounds
`Aggressor` won 6 rounds, lost 10 rounds, and tied 4 rounds
`Insane` won 5 rounds, lost 15 rounds, and tied 0 rounds
`The Ugly Duckling` won 4 rounds, lost 16 rounds, and tied 0 rounds
`Know Bot` won 3 rounds, lost 14 rounds, and tied 3 rounds
`Paranoid Bot` won 0 rounds, lost 19 rounds, and tied 1 round
`Panic Bot` won 0 rounds, lost 19 rounds, and tied 1 round

Unfortunately I could not test The Crazy X-Code Randomess because I can't get it to run from bash on Linux. I will include it if I can get it to work.

Full Controller Output

---

# The Game

This is a very simple KoTH game. It's a one-on-one snowball fight. You have an initially-empty container that can hold up to `k` snowballs. You can duck up to `j` times. Each turn, both players are asked to simultaneously give a choice for what move to make. There are three moves:

* reload: gives you another snowball (up to `k`)
* throw: throws a snowball, which will kill the other player if they decide to reload. If both players throw a snowball, nobody dies (they have such good aim that they will hit each other's snowballs)
* duck: does nothing, and avoids getting hit if the other player throws a snowball. If you have no more ducks left, then nothing happens and if the other player throws a snowball you die.

# Objective

Don't die.

# Challlenge Specifications

Your program can be written in any language. You are to take each of these variables as an argument on each execution:

```
[turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs]

```

`turn` \- how many turns have elapsed (`0` on the first iteration)
`snowballs` \- how many snowballs you have
`opponent_snowballs` \- how many snowballs the opponent has
`ducks` \- how many more times you can duck
`opponent_ducks` \- how many more times the opponent can duck
`max_snowballs` \- the maximum number of snowballs you can store (`k`)

The key function's output should be `0` for reload, `1` for throw, and `2` for duck. You must output your move, newline terminated. Please don't output invalid moves, but the controller is very resilient and will not break if you output invalid moves (even if your move isn't even an integer). It **must** be newline-terminated though. If the move isn't in `[0, 1, 2]`, it will default your move to `0`. The winner will be decided as the player with the most wins from a full round-robin tournament.

# Rules

You can read/write from/to one file for memory storage between iterations. Your bot will be placed in its own directory so filename conflicts will not occur. You cannot change built-in functions (such as the random generator). It was quite funny the first time it was done, but it won't be anymore. Your program is not allowed to do things that are just blatant execution stalling. Standard Loopholes Apply.

# Testing

The source code for the controller can be found here. Example of running it: `java Controller "python program1/test1.py" "python program2/test2.py" 10 5` for 10 snowballs and 5 ducks.

# Judging

The winner will be decided by selecting the person with the most wins after a full round-robin. While this is a tie, remove all people who do not have the most wins. Then, repeat until one person wins. The judging standard will be 50 snowballs and 25 ducks.

Happy KoTHing!

**EDIT**: The game will be declared a tie if 1000 rounds pass. Your bot may assume that `turn < 1000`.

# Answer
# Master, C#

I trained a small neural network (using Sharpneat). It seems to like picking up snowballs and ducking...

In a previous version of the controller, it even found a bug. It went from 0% winning to 100% when it discovered how to win by cheating.

**Edit:** I forgot to reset the networks interal state and trained the network wrong. The newly trained network is much smaller.

```
using System;
using System.Collections.Generic;

public class Master
{
    public CyclicNetwork _network;

    public static void Main(string[] args)
    {
        int s = int.Parse(args[1]);
        int os = int.Parse(args[2]);
        int d = int.Parse(args[3]);
        int od = int.Parse(args[4]);
        int ms = int.Parse(args[5]);

        var move = new Master().GetMove(s, os, d, od, ms);
        Console.WriteLine(move);
    }

    public Master()
    {
        var nodes = new List<Neuron>
        {
            new Neuron(0, NodeType.Bias),
            new Neuron(1, NodeType.Input),
            new Neuron(2, NodeType.Input),
            new Neuron(3, NodeType.Input),
            new Neuron(4, NodeType.Input),
            new Neuron(5, NodeType.Input),
            new Neuron(6, NodeType.Output),
            new Neuron(7, NodeType.Output),
            new Neuron(8, NodeType.Output),
            new Neuron(9, NodeType.Hidden)
        };
        var connections = new List<Connection>
        {
            new Connection(nodes[1], nodes[6], -1.3921811701131295),
            new Connection(nodes[6], nodes[6], 0.04683387519679514),
            new Connection(nodes[3], nodes[7], -4.746164930591382),
            new Connection(nodes[8], nodes[8], -0.025484025422054933),
            new Connection(nodes[4], nodes[9], -0.02084856381644095),
            new Connection(nodes[9], nodes[6], 4.9614062853759124),
            new Connection(nodes[9], nodes[9], -0.008672587457112968)
        };
        _network = new CyclicNetwork(nodes, connections, 5, 3, 2);
    }

    public int GetMove(int snowballs, int opponentBalls, int ducks, int opponentDucks, int maxSnowballs)
    {
        _network.InputSignalArray[0] = snowballs;
        _network.InputSignalArray[1] = opponentBalls;
        _network.InputSignalArray[2] = ducks;
        _network.InputSignalArray[3] = opponentDucks;
        _network.InputSignalArray[4] = maxSnowballs;

        _network.Activate();

        double max = double.MinValue;
        int best = 0;
        for (var i = 0; i < _network.OutputCount; i++)
        {
            var current = _network.OutputSignalArray[i];

            if (current > max)
            {
                max = current;
                best = i;
            }
        }

        _network.ResetState();

        return best;
    }
}

public class CyclicNetwork
{
    protected readonly List<Neuron> _neuronList;
    protected readonly List<Connection> _connectionList;
    protected readonly int _inputNeuronCount;
    protected readonly int _outputNeuronCount;
    protected readonly int _inputAndBiasNeuronCount;
    protected readonly int _timestepsPerActivation;
    protected readonly double[] _inputSignalArray;
    protected readonly double[] _outputSignalArray;
    readonly SignalArray _inputSignalArrayWrapper;
    readonly SignalArray _outputSignalArrayWrapper;

    public CyclicNetwork(List<Neuron> neuronList, List<Connection> connectionList, int inputNeuronCount, int outputNeuronCount, int timestepsPerActivation)
    {
        _neuronList = neuronList;
        _connectionList = connectionList;
        _inputNeuronCount = inputNeuronCount;
        _outputNeuronCount = outputNeuronCount;
        _inputAndBiasNeuronCount = inputNeuronCount + 1;
        _timestepsPerActivation = timestepsPerActivation;

        _inputSignalArray = new double[_inputNeuronCount];
        _outputSignalArray = new double[_outputNeuronCount];

        _inputSignalArrayWrapper = new SignalArray(_inputSignalArray, 0, _inputNeuronCount);
        _outputSignalArrayWrapper = new SignalArray(_outputSignalArray, 0, outputNeuronCount);
    }
    public int OutputCount
    {
        get { return _outputNeuronCount; }
    }
    public SignalArray InputSignalArray
    {
        get { return _inputSignalArrayWrapper; }
    }
    public SignalArray OutputSignalArray
    {
        get { return _outputSignalArrayWrapper; }
    }
    public virtual void Activate()
    {
        for (int i = 0; i < _inputNeuronCount; i++)
        {
            _neuronList[i + 1].OutputValue = _inputSignalArray[i];
        }

        int connectionCount = _connectionList.Count;
        int neuronCount = _neuronList.Count;
        for (int i = 0; i < _timestepsPerActivation; i++)
        {
            for (int j = 0; j < connectionCount; j++)
            {
                Connection connection = _connectionList[j];
                connection.OutputValue = connection.SourceNeuron.OutputValue * connection.Weight;
                connection.TargetNeuron.InputValue += connection.OutputValue;
            }
            for (int j = _inputAndBiasNeuronCount; j < neuronCount; j++)
            {
                Neuron neuron = _neuronList[j];
                neuron.OutputValue = neuron.Calculate(neuron.InputValue);
                neuron.InputValue = 0.0;
            }
        }
        for (int i = _inputAndBiasNeuronCount, outputIdx = 0; outputIdx < _outputNeuronCount; i++, outputIdx++)
        {
            _outputSignalArray[outputIdx] = _neuronList[i].OutputValue;
        }
    }
    public virtual void ResetState()
    {
        for (int i = 1; i < _inputAndBiasNeuronCount; i++)
        {
            _neuronList[i].OutputValue = 0.0;
        }
        int count = _neuronList.Count;
        for (int i = _inputAndBiasNeuronCount; i < count; i++)
        {
            _neuronList[i].InputValue = 0.0;
            _neuronList[i].OutputValue = 0.0;
        }
        count = _connectionList.Count;
        for (int i = 0; i < count; i++)
        {
            _connectionList[i].OutputValue = 0.0;
        }
    }
}
public class Connection
{
    readonly Neuron _srcNeuron;
    readonly Neuron _tgtNeuron;
    readonly double _weight;
    double _outputValue;

    public Connection(Neuron srcNeuron, Neuron tgtNeuron, double weight)
    {
        _tgtNeuron = tgtNeuron;
        _srcNeuron = srcNeuron;
        _weight = weight;
    }
    public Neuron SourceNeuron
    {
        get { return _srcNeuron; }
    }
    public Neuron TargetNeuron
    {
        get { return _tgtNeuron; }
    }
    public double Weight
    {
        get { return _weight; }
    }
    public double OutputValue
    {
        get { return _outputValue; }
        set { _outputValue = value; }
    }
}

public class Neuron
{
    readonly uint _id;
    readonly NodeType _neuronType;
    double _inputValue;
    double _outputValue;

    public Neuron(uint id, NodeType neuronType)
    {
        _id = id;
        _neuronType = neuronType;

        // Bias neurons have a fixed output value of 1.0
        _outputValue = (NodeType.Bias == _neuronType) ? 1.0 : 0.0;
    }
    public double InputValue
    {
        get { return _inputValue; }
        set
        {
            if (NodeType.Bias == _neuronType || NodeType.Input == _neuronType)
            {
                throw new Exception("Attempt to set the InputValue of bias or input neuron. Bias neurons have no input, and Input neuron signals should be passed in via their OutputValue property setter.");
            }
            _inputValue = value;
        }
    }
    public double Calculate(double x)
    {
        return 1.0 / (1.0 + Math.Exp(-4.9 * x));
    }
    public double OutputValue
    {
        get { return _outputValue; }
        set
        {
            if (NodeType.Bias == _neuronType)
            {
                throw new Exception("Attempt to set the OutputValue of a bias neuron.");
            }
            _outputValue = value;
        }
    }
}

public class SignalArray
{
    readonly double[] _wrappedArray;
    readonly int _offset;
    readonly int _length;

    public SignalArray(double[] wrappedArray, int offset, int length)
    {
        if (offset + length > wrappedArray.Length)
        {
            throw new Exception("wrappedArray is not long enough to represent the requested SignalArray.");
        }

        _wrappedArray = wrappedArray;
        _offset = offset;
        _length = length;
    }

    public double this[int index]
    {
        get
        {
            return _wrappedArray[_offset + index];
        }
        set
        {
            _wrappedArray[_offset + index] = value;
        }
    }
}

public enum NodeType
{
    /// <summary>
    /// Bias node. Output is fixed to 1.0
    /// </summary>
    Bias,
    /// <summary>
    /// Input node.
    /// </summary>
    Input,
    /// <summary>
    /// Output node.
    /// </summary>
    Output,
    /// <summary>
    /// Hidden node.
    /// </summary>
    Hidden
}

```
> 16 votes

# Answer
# PrioritizedRandomBot, Java

```
import java.util.Random;

public class PrioritizedRandomBot implements SnowballFighter {
    static int RELOAD = 0;
    static int THROW = 1;
    static int DUCK = 2;
    static Random rand = new Random();

    public static void main(String[] args) {
        int t = Integer.parseInt(args[0]);
        int s = Integer.parseInt(args[1]);
        int os = Integer.parseInt(args[2]);
        int d = Integer.parseInt(args[3]);
        int od = Integer.parseInt(args[4]);
        int ms = Integer.parseInt(args[5]);
        if (s > os + od) {
            System.out.println(THROW);
            return;
        }
        if (os == 0) {
            if (s == ms || s > 0 && s == od && rand.nextInt(1001 - t) == 0) {
                System.out.println(THROW);
            } else {
                System.out.println(RELOAD);
            }
            return;
        }
        if (os == ms && d > 0) {
            System.out.println(DUCK);
            return;
        }
        int r = rand.nextInt(os + od);
        if (r < s) {
            System.out.println(THROW);
        } else if (r < s + d) {
            System.out.println(DUCK);
        } else {
            System.out.println(RELOAD);
        }
    }
}

```

This bot selects a random integer in the range `0` to `os + od`, and then chooses to either throw, duck, or reload, with the thresholds determined by its current number of snowballs and ducks.

One thing that is important to realize, is that once one bot has more snowballs than the other bot has snowballs + ducks, then you can force a win. From this, we can come up with the concept of "points":

```
my points = s - os - od
op points = os - s - d

 effects of moves on my points
        OPPONENT
       R    T    D
   R        L   ++
 M T   W
 E D   -    +    +

```

If either of these numbers becomes positive, then that player is able to force a win.

```
points dif = p - op = 2*(s - os) + d - od

 effects of moves on the difference in points (me - my opponent)
        OPPONENT
       R    T    D
   R        L   +++
 M T   W         -
 E D  ---   +

points sum = p + op = - (d + od)

 effects of moves on the sum of points (me + my opponent)
        OPPONENT
       R    T    D
   R        L    +
 M T   W         +
 E D   +    +   ++

```

The "difference in points" table forms the foundation of the game theory for this competition. It doesn't quite capture all information, but it does show how snowballs are fundamentally more valuable than ducks (as snowballs are both offense and defense). If the opponent throws a snowball and you successfully duck, then you are one step closer to a forcible victory, since your opponent used up a more valuable resource. This table also describes what you should do in a lot of the special cases, such as when certain move options are not available.

The "sum of points" table shows how, over time, the sum of points approaches zero (as both players run out of ducks), at which point the first player to make a mistake (reload when they didn't need to) immediately loses.

Now, let's try to extend this forcing strategy to cases where it's not actually forcible (as in, we're winning by a large margin but mind-reading on the part of the opponent will beat us). Basically, we have `s` snowballs but need to snowball our opponent `s+1` (or `s+2`, etc.) time consecutively to win. In this case, we want to either perform a few ducks or a few reloads to buy ourselves some time.

Right now, this bot always tries to sneak in some ducks, simply because then it doesn't risk an immediate loss: we assume that the opponent is following a similar strategy of lobbing as many snowballs as it can, so attempting to reload is really dangerous. Also, in order to prevent predictability, we want to sneak these in following a uniformly-random distribution: the probability of ducking is related to how many ducks we need to perform relative to the number of snowballs we need to throw.

If we are losing badly, in which case `s + d < os + od` then we need to sneak in some reloads in addition to using all of our ducks, in this case, we want to reload randomly, but only as many times as we need.

This is why our bots prioritizes in the order of throw, duck, and reload, and uses `os + od` to generate the random number, since that is the threshold number of moves that we need to make.

There is one edge case, and two other special cases, that the bot currently handles. The edge case is when the opponent has neither snowballs nor ducks, and so randomization doesn't work, so we throw if possible, otherwise we reload. One other special case is when the opponent cannot reload, and so there is no benefit to throwing (since the opponent will either duck or throw), so we always duck (since saving our snowballs is more valuable than saving our ducks). The final special case is if the opponent has no snowballs, in which case we play it safe and reload if possible.
> 7 votes

# Answer
# NeceBot - Python

Here's the game theory table for the game:

```
        OPPONENT
       R    T     D
   R   ~    L   +D+S
 M T   W    ~   +D-S
 E D -D-S  -D+S   ~

```

Where `~` means no advantage, `W` is win, `L` is lose, `+-S` means a snowball is gained / lost over the opponent, and `+-D` means a duck is gained / lost over the opponent. This is a completely symmetrical game.

Note that my solution does not take that table into account. Because I'm bad at maths.

```
import sys

RELOAD = 0
THROW = 1
DUCK = 2

def main(turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs):
    if 2 + ducks <3:
        if 2 + snowballs <3:
            return RELOAD
        if 2 + opponent_ducks <3 or 2 + opponent_snowballs <3:
            return THROW
        return RELOAD
    if 2 + snowballs <3:
        if -opponent_snowballs <3 - 5 or 2 + abs(opponent_snowballs - 1) <3:
            return DUCK
        return RELOAD
    if 2 + opponent_ducks <3 or 2 + abs(snowballs - max_snowballs) <3:
        return THROW
    if -snowballs <3 - 6 or turn % 5 <3:
        return THROW
    return DUCK

print(main(*map(int, sys.argv[1:])))

```

It's called the NeceBot because it tries to reduce what is necessary first. It has some arbitrary strategies after that, which I hope work.
> 6 votes

# Answer
# Save One, Python

Throws most of its snowballs immediately, but always saves one in case the opponent is watching for a lack of ammo. Then, it ducks as long as possible (again, saving 1) before reloading unless there is a guaranteed safe reload or guaranteed kill.

```
import sys
turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = map(int, sys.argv[1:])

reload_snowball=0
throw=1
duck=2

if snowballs<=1:
    if opponent_snowballs==0:
        if opponent_ducks==0:
            print throw
        else:
            print reload_snowball
    elif ducks > 1:
        print duck
    else:
        print reload_snowball
else:
    print throw

```
> 6 votes

# Answer
## Coward - Scala

Throws, if opponent doesn't have any ammo, otherwise (in order of priority) ducks, throws or reloads.

```
object Test extends App {
  val s = args(1).toInt
  val os = args(2).toInt
  val d = args(3).toInt

  val move =
    if(os == 0)
      if(s > 0)
        1
      else
        0
    else if(d > 0)
        2
    else if(s > 0)
      1
    else
      0

  println(move)
}

```
> 5 votes

# Answer
# TheUglyDuckling - Python

Will always duck until it can't then tries to throw if the opponent is empty or reload if both are empty. Will use reload as a last resort.

```
import sys

arguments = sys.argv;

turn = int(arguments[1])
snowballs = int(arguments[2])
opponent_snowballs = int(arguments[3])
ducks = int(arguments[4])
opponent_ducks = int(arguments[5])
max_snowballs = int(arguments[6])

if ducks > 0:
    print 2
elif opponent_snowballs == 0 and snowballs > 0:
    print 1
elif opponent_snowballs == 0 and snowballs <= 0:
    print 0
elif snowballs > 0:
    print 1
elif snowballs <= 0:
    print 0

```
> 5 votes

# Answer
# SimpleBot - Python 2

```
import sys
turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = map(int, sys.argv[1:])

if opponent_snowballs > 0 and ducks > 0: print 2
elif snowballs: print 1
else: print 0

```

Simple stuff.

* If the opponent has snowballs and you have ducks, then you duck.
* If the opponent doesn't have snowballs and you have, then you throw.
* On any other case, you reload.
> 5 votes

# Answer
# The Naming-things-is-hard Bot - VB.NET

Naming things is hard, and I'm not sure I have a cohesive strategy to name it off of.

Tries to gamble the first few rounds to get an early victory. After that, plays safer the rest of the time, trying to win by attrition.

```
Module SnowballFight

    Private Enum Action
        Reload = 0
        ThrowSnowball = 1
        Duck = 2
    End Enum

    Sub Main(args As String())
        Dim turn As Integer = args(0)
        Dim mySnowballs As Integer = args(1)
        Dim opponentSnowballs As Integer = args(2)
        Dim myDucks As Integer = args(3)
        Dim opponentDucks As Integer = args(4)
        Dim maxSnowballs As Integer = args(5)

        If mySnowballs = 0 AndAlso opponentSnowballs = 0 Then
            ' can't throw, no need to duck
            Console.WriteLine(Action.Reload)
            Exit Sub
        End If

        If turn = 2 AndAlso opponentSnowballs > 0 Then
            ' everyone will probably reload and then throw, so try and duck, and throw turn 3
            Console.WriteLine(Action.Duck)
            Exit Sub
        End If

        If turn = 3 AndAlso opponentSnowballs = 0 Then
            ' they threw on turn 2, get them!
            Console.WriteLine(Action.ThrowSnowball)
            Exit Sub
        End If

        If mySnowballs > 0 AndAlso opponentSnowballs = 0 Then
            ' hope they don't duck
            Console.WriteLine(Action.ThrowSnowball)
            Exit Sub
        End If

        If mySnowballs = 0 AndAlso opponentSnowballs > 0 Then
            If myDucks > 0 Then
                ' watch out!
                Console.WriteLine(Action.Duck)
                Exit Sub
            Else
                ' well, maybe we'll get lucky
                Console.WriteLine(Action.Reload)
                Exit Sub
            End If
        End If

        If opponentSnowballs > 0 AndAlso myDucks > 5 Then
            ' play it safe
            Console.WriteLine(Action.Duck)
            Exit Sub
        End If

        If mySnowballs > 5 OrElse opponentDucks < 5 Then
            ' have a bunch saved up, start throwing them
            Console.WriteLine(Action.ThrowSnowball)
            Exit Sub
        End If

        ' start saving up
        Console.WriteLine(Action.Reload)
    End Sub

End Module

```
> 5 votes

# Answer
# MachineGun, Python 3

Tries to save up snowballs until it's either guaranteed to kill the opponent, or until its out of ducks (In which case, it starts blindly firing all its snowballs, like a machine gun)

It also ducks whenever the opponent has a snowball, because it doesn't want to die.

```
from os import sys
args = sys.argv[1:]
turn = int(args[0])
snowballs = int(args[1])
opponent_snowballs = int(args[2])
ducks = int(args[3])
opponent_ducks = int(args[4])
max_snowballs = int(args[5])
if ducks > 0 and opponent_snowballs > 0:
    print("2")
elif snowballs > 0 and opponent_snowballs == 0 and opponent_ducks == 0:
    print("1")
elif ducks == 0 and snowballs > 0:
    print("1")
elif snowballs < max_snowballs:
    print("0")
elif snowballs == max_snowballs:
    print("1")
else:
    print("0")

```
> 5 votes

# Answer
# Knowbot, Python3

Keeps track frequency of previous moves, assumes opponent will make the most frequent one again, defends against that.

\** Updated to not expect moves opponent can't make \**

```
import sys,pickle
TURN,BALLS,OTHROWS,DUCKS,ODUCKS,MAXB,OLOADS = [i for i in range(7)]

def save_state(data,prob):
    with open('snowball.pickle', 'wb') as f:
        pickle.dump((data,prob), f)

def load_state():
    with open('snowball.pickle', 'rb') as f:
        return pickle.load(f)

def reload(data = None):
    if not data or data[BALLS]<data[MAXB]:
        print(0)
        return True
    return False

def throw(data):
    if data[BALLS]>0:
        print(1)
        return True
    return False
def duck(data):
    if data[DUCKS]>0:
        print(2)
        return True
    return False

data = [int(v) for v in sys.argv[1:]]
data.append(0)

if data[TURN] > 0:
    last_data,prob = load_state()
    delta = [l-n for l,n in zip(last_data, data)]
    if delta[OTHROWS]<0:
        delta[OTHROWS]=0
        delta[OLOADS]=1
    prob = [p+d for p,d in zip(prob,delta)]
else:
    prob = [0]*7

expected = sorted(((prob[action],action) for action in [OTHROWS, ODUCKS, OLOADS]),
                      reverse=True)
expect = next( (a for p,a in expected if data[a]>0), OLOADS)

if expect == OTHROWS:
    duck(data) or throw(data) or reload()
elif expect == ODUCKS:
    reload(data) or duck(data) or throw(data) or reload()
else:
    throw(data) or reload(data) or duck(data) or reload()

save_state(data,prob);

```
> 5 votes

# Answer
# Braingolf, The Aggressor

```
<<?1:0

```

The aggressor is no coward! If he has a snowball, he shall throw! If he has no snowballs, he shall make more!

# Braingolf, The Insane

This isn't actually a bot, it's just a programmer whom I kidnapped and forced to port every project he's ever made over to braingolf. He no longer has a shred of sanity.

```
<3r!?:1+|%

```

Generates a random number less than 3, and outputs `t % r` where t is the current turn and r is the random number

To run these, you'll need to download `braingolf.py` from github, then either save the braingolf code to a file and run

```
python3 braingolf.py -f filename <space separated inputs>

```

or simply insert the code directly like this

```
python3 braingolf.py -c '<<?1:0' <space separated inputs>

```

The inputs are fairly irrelevant as long as the 2nd argument after the code/filename is the amount of snowballs The Aggressor has.

Note: The aggressor actually behaves identically to the TestBot, I just wanted to make an entry in braingolf

# Braingolf, The Brainy \[Broken right now\]

```
VR<<<!?v1:v0|R>!?v1:v0|>R<<!?v1:v0|>R<!?v1:v0|<VR<<.m<.m~v<-?~v0:~v1|>vc
VRv.<.>+1-?2_;|>.M<v?:0_;|1

```
> 4 votes

# Answer
# TestBot - Python

This is a test submission to show you what a valid submission may look like. The strategy: Alternate reloading and throwing. Quite a bad strategy but it gives you an idea of how your program should work.

```
from os import sys
arguments = sys.argv;
turn = int(arguments[1])
print(turn % 2)

```
> 3 votes

# Answer
# UpperHandBot, Python 3

```
import sys
turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = map(int, sys.argv[1:])

if snowballs <= opponent_snowballs:
  if opponent_snowballs > 0 and ducks > 0:
    print(2)
  else:
    if snowballs < max_snowballs:
      print(0)
    else:
      print(1)
else:
  print(1)

```

This bot tries to collect more snowballs than its opponent, and at that point starts throwing. If at any point UHB doesn't have more snowballs than its opponent, it will:

* Duck, if the opponent has snowballs and it has ducks left
* Otherwise, reload (unless UHB is at the maximum, then it throws instead, although I don't think this situation would ever come up)
> 2 votes

# Answer
## Yggdrasli, Java

```
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Yggdrasil implements SnowballFighter {
    public static boolean debug = false;
    static int RELOAD = 0;
    static int THROW = 1;
    static int DUCK = 2;
    static int INVALID = -3;
    static Random rand = new Random();

    public static void main(String[] args) {
        int t = Integer.parseInt(args[0]);
        int s = Integer.parseInt(args[1]);
        int os = Integer.parseInt(args[2]);
        int d = Integer.parseInt(args[3]);
        int od = Integer.parseInt(args[4]);
        int ms = Integer.parseInt(args[5]);
        System.out.println((new Yggdrasil()).move(t, s, os, d, od, ms));
    }

    public final int move(int t, int s, int os, int d, int od, int ms) {
        State state = State.get(s, os, d, od);
        double val = state.val(4);
        double[] strat = state.strat;
        int move = INVALID;
        if (debug) {
            System.out.println(val + " : " + strat[0] + " " + strat[1] + " " + strat[2]);
        }
        while (move == INVALID) {
            double r = rand.nextDouble();
            if (r < strat[RELOAD] && strat[RELOAD] > 0.0001) {
                move = RELOAD;
            } else if (r < strat[RELOAD] + strat[THROW] && strat[THROW] > 0.0001) {
                move = THROW;
            } else if (r < strat[RELOAD] + strat[THROW] + strat[DUCK] && strat[DUCK] > 0.0001) {
                move = DUCK;
            }
        }
        return move;
    }

    public static class State {

        public static boolean debug = false;
        public static int ms = 50;
        public int s;
        public int os;
        public static int md = 25;
        public int d;
        public int od;

        public State(int s, int os, int d, int od) {
            super();
            this.s = s;
            this.os = os;
            this.d = d;
            this.od = od;
        }

        Double val;
        int valdepth;
        double[] strat = new double[3];

        public Double val(int maxdepth) {
            if (s < 0 || s > ms || d < 0 || d > md || os < 0 || os > ms || od < 0 || od > md) {
                return null;
            } else if (val != null && valdepth >= maxdepth) {
                return val;
            }
            if (s > os + od) {
                val = 1.0; // force win
                strat = new double[] { 0, 1, 0 };
            } else if (os > s + d) {
                val = -1.0; // force loss
                strat = new double[] { 1.0 / (1.0 + s + d), s / (1.0 + s + d), d / (1.0 + s + d) };
            } else if (d == 0 && od == 0) {
                val = 0.0; // perfect tie
                if (s > 0) {
                    strat = new double[] { 0, 1, 0 };
                } else {
                    strat = new double[] { 1, 0, 0 };
                }
            } else if (maxdepth <= 0) {
                double togo = 1 - s + os + od;
                double otogo = 1 - os + s + d;
                double per = otogo * otogo / (togo * togo + otogo * otogo);
                double oper = togo * togo / (togo * togo + otogo * otogo);
                val = per - oper;
            } else {
                Double[][] fullmatrix = new Double[3][3];
                boolean[] vm = new boolean[3];
                boolean[] ovm = new boolean[3];
                for (int i = 0; i < 3; i++) {
                    int dest_s = s;
                    int dest_d = d;
                    if (i == 0) {
                        dest_s++;
                    } else if (i == 1) {
                        dest_s--;
                    } else {
                        dest_d--;
                    }
                    for (int j = 0; j < 3; j++) {
                        int dest_os = os;
                        int dest_od = od;
                        if (j == 0) {
                            dest_os++;
                        } else if (j == 1) {
                            dest_os--;
                        } else {
                            dest_od--;
                        }
                        if (i == 0 && j == 1 && dest_os >= 0 && dest_s <= ms) {
                            fullmatrix[i][j] = -1.0; // kill
                        } else if (i == 1 && j == 0 && dest_s >= 0 && dest_os <= ms) {
                            fullmatrix[i][j] = 1.0; // kill
                        } else {
                            fullmatrix[i][j] = get(dest_s, dest_os, dest_d, dest_od).val(maxdepth - 1);
                        }
                        if (fullmatrix[i][j] != null) {
                            vm[i] = true;
                            ovm[j] = true;
                        }
                    }
                }

                if (debug) {
                    System.out.println();
                    System.out.println(maxdepth);
                    System.out.println(s + " " + os + " " + d + " " + od);
                    for (int i = 0; i < 3; i++) {
                        System.out.print(vm[i]);
                    }
                    System.out.println();
                    for (int i = 0; i < 3; i++) {
                        System.out.print(ovm[i]);
                    }
                    System.out.println();
                    for (int i = 0; i < 3; i++) {
                        for (int j = 0; j < 3; j++) {
                            System.out.printf(" %7.4f", fullmatrix[i][j]);
                        }
                        System.out.println();
                    }
                }
                // really stupid way to find an approximate best strategy
                val = -1.0;
                double[] p = new double[3];
                for (p[0] = 0; p[0] < 0.0001 || vm[0] && p[0] <= 1.0001; p[0] += 0.01) {
                    for (p[1] = 0; p[1] < 0.0001 || vm[1] && p[1] <= 1.0001 - p[0]; p[1] += 0.01) {
                        p[2] = 1.0 - p[0] - p[1];
                        if (p[2] < 0.0001 || vm[2]) {
                            double min = 1;
                            for (int j = 0; j < 3; j++) {
                                if (ovm[j]) {
                                    double sum = 0;
                                    for (int i = 0; i < 3; i++) {
                                        if (vm[i]) {
                                            sum += fullmatrix[i][j] * p[i];
                                        }
                                    }
                                    min = Math.min(min, sum);
                                }
                            }
                            if (min > val) {
                                val = min;
                                strat = p.clone();
                            }
                        }
                    }
                }
                if (debug) {
                    System.out.println("v:" + val);
                    System.out.println("s:" + strat[0] + " " + strat[1] + " " + strat[2]);
                }
            }
            valdepth = maxdepth;
            return val;
        }

        static Map<Integer, State> cache = new HashMap<Integer, State>();

        static State get(int s, int os, int d, int od) {
            int key = (((s) * 100 + os) * 100 + d) * 100 + od;
            if (cache.containsKey(key)) {
                return cache.get(key);
            }
            State res = new State(s, os, d, od);
            cache.put(key, res);
            return res;
        }
    }
}

```

I named this bot "Yggdrasil" because it actually looks ahead down the game tree and performs state valuation, from which it can compute an approximately-ideal mixed strategy. Because it relies on mixed strategies, it is *very* non-deterministic. I don't know how well this thing will do in real competition.

A few things about this bot:

* The core is a recursive function that calculation the value and near-ideal mixed strategy for any particular game state. Right now I have it set to look 4 steps ahead.
* It plays extremely drawish, as in a lot of cases this bot is equivalent to "picking a random move in rock-paper-scissors". It holds its ground and hopes that its opponent gives it a statistical advantage. If this bot were perfect (which it's not), the best you could do against it would be 50% wins and 50% losses. As a result, there is no opponent that it consistently beats, but also none it consistently loses to.
> 2 votes

# Answer
# Pain in the Nash (C++)

So called because the fact that I had to write my own Nash equilibrium solver was a real pain. I'm amazed that there aren't any readily-available Nash-solving libraries!

```
#include <fstream>
#include <iostream>
#include <vector>
#include <array>
#include <random>
#include <utility>

typedef double NumT;
static const NumT EPSILON = 1e-5;

struct Index {
    int me;
    int them;

    Index(int me, int them) : me(me), them(them) {}
};

struct Value {
    NumT me;
    NumT them;

    Value(void) : me(0), them(0) {}

    Value(NumT me, NumT them) : me(me), them(them) {}
};

template <int subDimMe, int subDimThem>
struct Game {
    const std::array<NumT, 9> *valuesMe;
    const std::array<NumT, 9> *valuesThemT;

    std::array<int, subDimMe> coordsMe;
    std::array<int, subDimThem> coordsThem;

    Game(
        const std::array<NumT, 9> *valuesMe,
        const std::array<NumT, 9> *valuesThemT
    )
        : valuesMe(valuesMe)
        , valuesThemT(valuesThemT)
        , coordsMe{}
        , coordsThem{}
    {}

    Index baseIndex(Index i) const {
        return Index(coordsMe[i.me], coordsThem[i.them]);
    }

    Value at(Index i) const {
        Index i2 = baseIndex(i);
        return Value(
            (*valuesMe)[i2.me * 3 + i2.them],
            (*valuesThemT)[i2.me + i2.them * 3]
        );
    }

    Game<2, 2> subgame22(int me0, int me1, int them0, int them1) const {
        Game<2, 2> b(valuesMe, valuesThemT);
        b.coordsMe[0] = coordsMe[me0];
        b.coordsMe[1] = coordsMe[me1];
        b.coordsThem[0] = coordsThem[them0];
        b.coordsThem[1] = coordsThem[them1];
        return b;
    }
};

struct Strategy {
    std::array<NumT, 3> probMe;
    std::array<NumT, 3> probThem;
    Value expectedValue;
    bool valid;

    Strategy(void)
        : probMe{}
        , probThem{}
        , expectedValue()
        , valid(false)
    {}

    void findBestMe(const Strategy &b) {
        if(b.valid && (!valid || b.expectedValue.me > expectedValue.me)) {
            *this = b;
        }
    }
};

template <int dimMe, int dimThem>
Strategy nash_pure(const Game<dimMe, dimThem> &g) {
    Strategy s;
    int choiceMe = -1;
    int choiceThem = 0;
    for(int me = 0; me < dimMe; ++ me) {
        for(int them = 0; them < dimThem; ++ them) {
            const Value &v = g.at(Index(me, them));
            bool valid = true;
            for(int me2 = 0; me2 < dimMe; ++ me2) {
                if(g.at(Index(me2, them)).me > v.me) {
                    valid = false;
                }
            }
            for(int them2 = 0; them2 < dimThem; ++ them2) {
                if(g.at(Index(me, them2)).them > v.them) {
                    valid = false;
                }
            }
            if(valid) {
                if(choiceMe == -1 || v.me > s.expectedValue.me) {
                    s.expectedValue = v;
                    choiceMe = me;
                    choiceThem = them;
                }
            }
        }
    }
    if(choiceMe != -1) {
        Index iBase = g.baseIndex(Index(choiceMe, choiceThem));
        s.probMe[iBase.me] = 1;
        s.probThem[iBase.them] = 1;
        s.valid = true;
    }
    return s;
}

Strategy nash_mixed(const Game<2, 2> &g) {
    //    P    Q
    // p a A  b B
    // q c C  d D

    Value A = g.at(Index(0, 0));
    Value B = g.at(Index(0, 1));
    Value C = g.at(Index(1, 0));
    Value D = g.at(Index(1, 1));

    // q = 1-p, Q = 1-P
    // Pick p such that choice of P,Q is arbitrary

    // p*A+(1-p)*C = p*B+(1-p)*D
    // p*A+C-p*C = p*B+D-p*D
    // p*(A+D-B-C) = D-C
    // p = (D-C) / (A+D-B-C)

    NumT p = (D.them - C.them) / (A.them + D.them - B.them - C.them);

    // P*a+(1-P)*b = P*c+(1-P)*d
    // P*a+b-P*b = P*c+d-P*d
    // P*(a+d-b-c) = d-b
    // P = (d-b) / (a+d-b-c)

    NumT P = (D.me - B.me) / (A.me + D.me - B.me - C.me);

    Strategy s;
    if(p >= -EPSILON && p <= 1 + EPSILON && P >= -EPSILON && P <= 1 + EPSILON) {
        if(p <= 0) {
            p = 0;
        } else if(p >= 1) {
            p = 1;
        }
        if(P <= 0) {
            P = 0;
        } else if(P >= 1) {
            P = 1;
        }
        Index iBase0 = g.baseIndex(Index(0, 0));
        Index iBase1 = g.baseIndex(Index(1, 1));
        s.probMe[iBase0.me] = p;
        s.probMe[iBase1.me] = 1 - p;
        s.probThem[iBase0.them] = P;
        s.probThem[iBase1.them] = 1 - P;
        s.expectedValue = Value(
            P * A.me + (1 - P) * B.me,
            p * A.them + (1 - p) * C.them
        );
        s.valid = true;
    }
    return s;
}

Strategy nash_mixed(const Game<3, 3> &g) {
    //    P    Q    R
    // p a A  b B  c C
    // q d D  e E  f F
    // r g G  h H  i I

    Value A = g.at(Index(0, 0));
    Value B = g.at(Index(0, 1));
    Value C = g.at(Index(0, 2));
    Value D = g.at(Index(1, 0));
    Value E = g.at(Index(1, 1));
    Value F = g.at(Index(1, 2));
    Value G = g.at(Index(2, 0));
    Value H = g.at(Index(2, 1));
    Value I = g.at(Index(2, 2));

    // r = 1-p-q, R = 1-P-Q
    // Pick p,q such that choice of P,Q,R is arbitrary

    NumT q = ((
        + A.them * (I.them-H.them)
        + G.them * (B.them-C.them)
        - B.them*I.them
        + H.them*C.them
    ) / (
        (G.them+E.them-D.them-H.them) * (B.them+I.them-H.them-C.them) -
        (H.them+F.them-E.them-I.them) * (A.them+H.them-G.them-B.them)
    ));

    NumT p = (
        ((G.them+E.them-D.them-H.them) * q + (H.them-G.them)) /
        (A.them+H.them-G.them-B.them)
    );

    NumT Q = ((
        + A.me * (I.me-F.me)
        + C.me * (D.me-G.me)
        - D.me*I.me
        + F.me*G.me
    ) / (
        (C.me+E.me-B.me-F.me) * (D.me+I.me-F.me-G.me) -
        (F.me+H.me-E.me-I.me) * (A.me+F.me-C.me-D.me)
    ));

    NumT P = (
        ((C.me+E.me-B.me-F.me) * Q + (F.me-C.me)) /
        (A.me+F.me-C.me-D.me)
    );

    Strategy s;
    if(
        p >= -EPSILON && q >= -EPSILON && p + q <= 1 + EPSILON &&
        P >= -EPSILON && Q >= -EPSILON && P + Q <= 1 + EPSILON
    ) {
        if(p <= 0) { p = 0; }
        if(q <= 0) { q = 0; }
        if(P <= 0) { P = 0; }
        if(Q <= 0) { Q = 0; }
        if(p + q >= 1) {
            if(p > q) {
                p = 1 - q;
            } else {
                q = 1 - p;
            }
        }
        if(P + Q >= 1) {
            if(P > Q) {
                P = 1 - Q;
            } else {
                Q = 1 - P;
            }
        }
        Index iBase0 = g.baseIndex(Index(0, 0));
        s.probMe[iBase0.me] = p;
        s.probThem[iBase0.them] = P;
        Index iBase1 = g.baseIndex(Index(1, 1));
        s.probMe[iBase1.me] = q;
        s.probThem[iBase1.them] = Q;
        Index iBase2 = g.baseIndex(Index(2, 2));
        s.probMe[iBase2.me] = 1 - p - q;
        s.probThem[iBase2.them] = 1 - P - Q;
        s.expectedValue = Value(
            A.me * P + B.me * Q + C.me * (1 - P - Q),
            A.them * p + D.them * q + G.them * (1 - p - q)
        );
        s.valid = true;
    }
    return s;
}

template <int dimMe, int dimThem>
Strategy nash_validate(Strategy &&s, const Game<dimMe, dimThem> &g, Index unused) {
    if(!s.valid) {
        return s;
    }

    NumT exp;

    exp = 0;
    for(int them = 0; them < dimThem; ++ them) {
        exp += s.probThem[them] * g.at(Index(unused.me, them)).me;
    }
    if(exp > s.expectedValue.me) {
        s.valid = false;
        return s;
    }

    exp = 0;
    for(int me = 0; me < dimMe; ++ me) {
        exp += s.probMe[me] * g.at(Index(me, unused.them)).them;
    }
    if(exp > s.expectedValue.them) {
        s.valid = false;
        return s;
    }

    return s;
}

Strategy nash(const Game<2, 2> &g, bool verbose) {
    Strategy s = nash_mixed(g);
    s.findBestMe(nash_pure(g));
    if(!s.valid && verbose) {
        std::cerr << "No nash equilibrium found!" << std::endl;
    }
    return s;
}

Strategy nash(const Game<3, 3> &g, bool verbose) {
    Strategy s = nash_mixed(g);
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(1, 2,  1, 2)), g, Index(0, 0)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(1, 2,  0, 2)), g, Index(0, 1)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(1, 2,  0, 1)), g, Index(0, 2)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 2,  1, 2)), g, Index(1, 0)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 2,  0, 2)), g, Index(1, 1)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 2,  0, 1)), g, Index(1, 2)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 1,  1, 2)), g, Index(2, 0)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 1,  0, 2)), g, Index(2, 1)));
    s.findBestMe(nash_validate(nash_mixed(g.subgame22(0, 1,  0, 1)), g, Index(2, 2)));
    s.findBestMe(nash_pure(g));
    if(!s.valid && verbose) {
        // theory says this should never happen, but fp precision makes it possible
        std::cerr << "No nash equilibrium found!" << std::endl;
    }
    return s;
}

struct PlayerState {
    int balls;
    int ducks;

    PlayerState(int balls, int ducks) : balls(balls), ducks(ducks) {}

    PlayerState doReload(int maxBalls) const {
        return PlayerState(std::min(balls + 1, maxBalls), ducks);
    }

    PlayerState doThrow(void) const {
        return PlayerState(std::max(balls - 1, 0), ducks);
    }

    PlayerState doDuck(void) const {
        return PlayerState(balls, std::max(ducks - 1, 0));
    }

    std::array<double,3> flail(int maxBalls) const {
        // opponent has obvious win;
        // try stuff at random and hope the opponent is bad

        (void) ducks;

        int options = 0;
        if(balls > 0) {
            ++ options;
        }
        if(balls < maxBalls) {
            ++ options;
        }
        if(ducks > 0) {
            ++ options;
        }

        std::array<double,3> p{};
        if(balls < balls) {
            p[0] = 1.0f / options;
        }
        if(balls > 0) {
            p[1] = 1.0f / options;
        }
        return p;
    }
};

class GameStore {
protected:
    const int balls;
    const int ducks;
    const std::size_t playerStates;
    const std::size_t gameStates;

public:
    static std::string filename(int turn) {
        return "nashdata_" + std::to_string(turn) + ".dat";
    }

    GameStore(int maxBalls, int maxDucks)
        : balls(maxBalls)
        , ducks(maxDucks)
        , playerStates((balls + 1) * (ducks + 1))
        , gameStates(playerStates * playerStates)
    {}

    std::size_t playerIndex(const PlayerState &p) const {
        return p.balls * (ducks + 1) + p.ducks;
    }

    std::size_t gameIndex(const PlayerState &me, const PlayerState &them) const {
        return playerIndex(me) * playerStates + playerIndex(them);
    }

    std::size_t fileIndex(const PlayerState &me, const PlayerState &them) const {
        return 2 + gameIndex(me, them) * 2;
    }

    PlayerState stateFromPlayerIndex(std::size_t i) const {
        return PlayerState(i / (ducks + 1), i % (ducks + 1));
    }

    std::pair<PlayerState, PlayerState> stateFromGameIndex(std::size_t i) const {
        return std::make_pair(
            stateFromPlayerIndex(i / playerStates),
            stateFromPlayerIndex(i % playerStates)
        );
    }

    std::pair<PlayerState, PlayerState> stateFromFileIndex(std::size_t i) const {
        return stateFromGameIndex((i - 2) / 2);
    }
};

class Generator : public GameStore {
    static char toDat(NumT v) {
        int iv = int(v * 256.0);
        return char(std::max(std::min(iv, 255), 0));
    }

    std::vector<Value> next;

public:
    Generator(int maxBalls, int maxDucks)
        : GameStore(maxBalls, maxDucks)
        , next()
    {}

    const Value &nextGame(const PlayerState &me, const PlayerState &them) const {
        return next[gameIndex(me, them)];
    }

    void make_probabilities(
        std::array<NumT, 9> &g,
        const PlayerState &me,
        const PlayerState &them
    ) const {
        const int RELOAD = 0;
        const int THROW = 1;
        const int DUCK = 2;

        g[RELOAD * 3 + RELOAD] =
            nextGame(me.doReload(balls), them.doReload(balls)).me;

        g[RELOAD * 3 + THROW] =
            (them.balls > 0) ? -1
            : nextGame(me.doReload(balls), them.doThrow()).me;

        g[RELOAD * 3 + DUCK] =
            nextGame(me.doReload(balls), them.doDuck()).me;

        g[THROW * 3 + RELOAD] =
            (me.balls > 0) ? 1
            : nextGame(me.doThrow(), them.doReload(balls)).me;

        g[THROW * 3 + THROW] =
            ((me.balls > 0) == (them.balls > 0))
            ? nextGame(me.doThrow(), them.doThrow()).me
            : (me.balls > 0) ? 1 : -1;

        g[THROW * 3 + DUCK] =
            (me.balls > 0 && them.ducks == 0) ? 1
            : nextGame(me.doThrow(), them.doDuck()).me;

        g[DUCK * 3 + RELOAD] =
            nextGame(me.doDuck(), them.doReload(balls)).me;

        g[DUCK * 3 + THROW] =
            (them.balls > 0 && me.ducks == 0) ? -1
            : nextGame(me.doDuck(), them.doThrow()).me;

        g[DUCK * 3 + DUCK] =
            nextGame(me.doDuck(), them.doDuck()).me;
    }

    Game<3, 3> make_game(const PlayerState &me, const PlayerState &them) const {
        static std::array<NumT, 9> globalValuesMe;
        static std::array<NumT, 9> globalValuesThemT;
        #pragma omp threadprivate(globalValuesMe)
        #pragma omp threadprivate(globalValuesThemT)

        make_probabilities(globalValuesMe, me, them);
        make_probabilities(globalValuesThemT, them, me);
        Game<3, 3> g(&globalValuesMe, &globalValuesThemT);
        for(int i = 0; i < 3; ++ i) {
            g.coordsMe[i] = i;
            g.coordsThem[i] = i;
        }
        return g;
    }

    Strategy solve(const PlayerState &me, const PlayerState &them, bool verbose) const {
        if(me.balls > them.balls + them.ducks) { // obvious answer
            Strategy s;
            s.probMe[1] = 1;
            s.probThem = them.flail(balls);
            s.expectedValue = Value(1, -1);
            return s;
        } else if(them.balls > me.balls + me.ducks) { // uh-oh
            Strategy s;
            s.probThem[1] = 1;
            s.probMe = me.flail(balls);
            s.expectedValue = Value(-1, 1);
            return s;
        } else if(me.balls == 0 && them.balls == 0) { // obvious answer
            Strategy s;
            s.probMe[0] = 1;
            s.probThem[0] = 1;
            s.expectedValue = nextGame(me.doReload(balls), them.doReload(balls));
            return s;
        } else {
            return nash(make_game(me, them), verbose);
        }
    }

    void generate(int turns, bool saveAll, bool verbose) {
        next.clear();
        next.resize(gameStates);
        std::vector<Value> current(gameStates);
        std::vector<char> data(2 + gameStates * 2);

        for(std::size_t turn = turns; (turn --) > 0;) {
            if(verbose) {
                std::cerr << "Generating for turn " << turn << "..." << std::endl;
            }
            NumT maxDiff = 0;
            NumT msd = 0;
            data[0] = balls;
            data[1] = ducks;
            #pragma omp parallel for reduction(+:msd), reduction(max:maxDiff)
            for(std::size_t meBalls = 0; meBalls < balls + 1; ++ meBalls) {
                for(std::size_t meDucks = 0; meDucks < ducks + 1; ++ meDucks) {
                    const PlayerState me(meBalls, meDucks);
                    for(std::size_t themBalls = 0; themBalls < balls + 1; ++ themBalls) {
                        for(std::size_t themDucks = 0; themDucks < ducks + 1; ++ themDucks) {
                            const PlayerState them(themBalls, themDucks);
                            const std::size_t p1 = gameIndex(me, them);

                            Strategy s = solve(me, them, verbose);

                            NumT diff;

                            data[2+p1*2  ] = toDat(s.probMe[0]);
                            data[2+p1*2+1] = toDat(s.probMe[0] + s.probMe[1]);
                            current[p1] = s.expectedValue;
                            diff = current[p1].me - next[p1].me;
                            msd += diff * diff;
                            maxDiff = std::max(maxDiff, std::abs(diff));
                        }
                    }
                }
            }

            if(saveAll) {
                std::ofstream fs(filename(turn).c_str(), std::ios_base::binary);
                fs.write(&data[0], data.size());
                fs.close();
            }

            if(verbose) {
                std::cerr
                    << "Expectations changed by at most " << maxDiff
                    << " (RMSD: " << std::sqrt(msd / gameStates) << ")" << std::endl;
            }
            if(maxDiff < 0.0001f) {
                if(verbose) {
                    std::cerr << "Expectations have converged. Stopping." << std::endl;
                }
                break;
            }
            std::swap(next, current);
        }

        // Always save turn 0 with the final converged expectations
        std::ofstream fs(filename(0).c_str(), std::ios_base::binary);
        fs.write(&data[0], data.size());
        fs.close();
    }
};

void open_file(std::ifstream &target, int turn, int maxDucks, int maxBalls) {
    target.open(GameStore::filename(turn).c_str(), std::ios::binary);
    if(target.is_open()) {
        return;
    }

    target.open(GameStore::filename(0).c_str(), std::ios::binary);
    if(target.is_open()) {
        return;
    }

    Generator(maxBalls, maxDucks).generate(200, false, false);
    target.open(GameStore::filename(0).c_str(), std::ios::binary);
}

int choose(int turn, const PlayerState &me, const PlayerState &them, int maxBalls) {
    std::ifstream fs;
    open_file(fs, turn, std::max(me.ducks, them.ducks), maxBalls);

    unsigned char balls = fs.get();
    unsigned char ducks = fs.get();
    fs.seekg(GameStore(balls, ducks).fileIndex(me, them));
    unsigned char p0 = fs.get();
    unsigned char p1 = fs.get();
    fs.close();

    // only 1 random number per execution; no need to seed a PRNG
    std::random_device rand;
    int v = std::uniform_int_distribution<int>(0, 254)(rand);
    if(v < p0) {
        return 0;
    } else if(v < p1) {
        return 1;
    } else {
        return 2;
    }
}

int main(int argc, const char *const *argv) {
    if(argc == 4) { // maxTurns, maxBalls, maxDucks
        Generator(atoi(argv[2]), atoi(argv[3])).generate(atoi(argv[1]), true, true);
        return 0;
    }

    if(argc == 7) { // turn, meBalls, themBalls, meDucks, themDucks, maxBalls
        std::cout << choose(
            atoi(argv[1]),
            PlayerState(atoi(argv[2]), atoi(argv[4])),
            PlayerState(atoi(argv[3]), atoi(argv[5])),
            atoi(argv[6])
        ) << std::endl;
        return 0;
    }

    return 1;
}

```

Compile as C++11 or better. For performance, it's good to compile with OpenMP support (but this is just for speed; it's not required)

```
g++ -std=c++11 -fopenmp pain_in_the_nash.cpp -o pain_in_the_nash

```

---

This uses Nash equilibria to decide what to do on each turn, which means that *in theory* it will always win or draw in the long run (over many games), no matter what strategy the opponent uses. Whether that's the case in practice depends on whether I made any mistakes in the implementation. However, since this KoTH competition only has a single round against each opponent, it probably won't do very well on the leaderboard.

My original idea was to have a simple valuation function for each game state (e.g. each ball is worth +b, each duck is +d), but this leads to obvious problems figuring out what those valuations should be, and means it can't act on diminishing returns of gathering more and more balls, etc. So instead, this will analyse the *entire game tree*, working backwards from turn 1000, and fill in the actual valuations based on how each game could pan out.

The result is that I have absolutely no idea what strategy this uses, except for a couple of hard-coded "obvious" behaviours (throw snowballs if you have more balls than your opponent has balls+ducks, and reload if you're both out of snowballs). If anybody wants to analyse the dataset it produces I imagine there's some interesting behaviour to discover!

Testing this against "Save One" shows that it does indeed win in the long-run, but only by a small margin (514 wins, 486 losses, 0 draws in the first batch of 1000 games, and 509 wins, 491 losses, 0 draws in the second).

---

# Important!

This will work out-of-the-box, but that's not a great idea. It takes about 9 minutes on my moderately-developer-spec laptop to generate the full game tree. But it will save the final probabilities into a file once they're generated, and after that each turn is just generating a random number and comparing it against 2 bytes, so it's super-fast.

To shortcut all that, just download this file (3.5MB) and put it in the directory with the executable.

Or you can generate it yourself by running:

```
./pain_in_the_nash 1000 50 25

```

Which will save one file per turn, until convergence. Note that each file is 3.5MB and it will converge at turn 720 (i.e. 280 files, ~1GB), and since most games don't get anywhere near turn 720, the pre-convergence files have very low importance.
> 2 votes

# Answer
# Swift - TheCrazy\_XcodeRandomness

Sadly, this can only be ran locally, in Xcode, because it contains the `Foundation` module and its function, `arc4random_uniform()`. However, you can pretty much tell what the algorithm is:

```
import Foundation

func game(turn: Int, snowballs: Int, opponent_snowballs: Int, ducks: Int, opponent_ducks: Int, max_snowballs: Int) -> Int{
    let RELOAD = 0
    let THROW = 1
    let DUCK = 2
    if turn == 0{
        return arc4random_uniform(2)==0 ? THROW : DUCK
    }
    else if ducks == 0{
        if snowballs != 0{return THROW}
        else {return RELOAD}
    }
    else if snowballs < max_snowballs && snowballs != 0{
        if opponent_ducks == 0 && opponent_snowballs == 0{return THROW}
        else if opponent_snowballs == 0{
            return arc4random_uniform(2)==0 ? THROW : RELOAD
        }
        else if opponent_ducks == 0{return THROW}
        else { return arc4random_uniform(2)==0 ? THROW : RELOAD }
    }
    else if opponent_snowballs == max_snowballs{
        return DUCK
    }
    else if snowballs == max_snowballs || opponent_ducks < 1 || turn < max_snowballs{return THROW}
    return arc4random_uniform(2)==0 ? THROW : RELOAD
}

```
> 1 votes

# Answer
# TableBot, Python 2

Called TableBot because it was created by implementing this table:

```
snow   duck   osnow   oduck   move
0      0      0       0       0
0      0      0       1       0
0      0      1       0       0
0      0      1       1       0
0      1      0       0       0
0      1      0       1       0
0      1      1       0       2
0      1      1       1       2
1      0      0       0       1
1      0      0       1       1
1      0      1       0       1
1      0      1       1       1
1      1      0       0       1
1      1      0       1       1
1      1      1       0       1
1      1      1       1       1

```

A 1 represents having 1 or more, a 0 represents having none.

The bot:

```
import sys

reload=0
throw=1
duck=2

t,snowballs,o_snowballs,ducks,o_ducks,m=map(int,sys.argv[1:])

if snowballs > 0:
	print throw
elif ducks==0:
	print reload
elif o_snowballs==0:
	print reload
else:
	print duck

```

Try it online!
> 1 votes

# Answer
# AmbBot - Racket Scheme

I mostly wanted to try out using `amb`, because it's cool. This bot randomly orders the options (reload, throw, and duck), filters out the ones that don't make sense, and picks the first option. But with `amb`, we get to use continuations and backtracking!

```
#lang racket
(require racket/cmdline)

; Defining amb.
(define failures null)

(define (fail)
  (if (pair? failures) ((first failures)) (error "no more choices!")))

(define (amb/thunks choices)
  (let/cc k (set! failures (cons k failures)))
  (if (pair? choices)
    (let ([choice (first choices)]) (set! choices (rest choices)) (choice))
    (begin (set! failures (rest failures)) (fail))))

(define-syntax-rule (amb E ...) (amb/thunks (list (lambda () E) ...)))

(define (assert condition) (unless condition (fail)))

(define (!= a b)
  (not (= a b)))

(define (amb-list list)
  (if (null? list)
      (amb)
      (amb (car list)
           (amb-list (cdr list)))))

; The meaningful code!
; Start by defining our options.
(define reload 0)
(define throw 1)
(define duck 2)

; The heart of the program.
(define (make-choice turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (let ((can-reload? (reload-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs))
        (can-throw? (throw-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs))
        (can-duck? (duck-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs)))
    (if (not (or can-reload? can-throw? can-duck?))
        (random 3) ; something went wrong, panic
        (let* ((ls (shuffle (list reload throw duck)))
               (action (amb-list ls)))
          (assert (or (!= action reload) can-reload?))
          (assert (or (!= action throw) can-throw?))
          (assert (or (!= action duck) can-duck?))
          action))))

; Define what makes a move possible.
(define (reload-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (not (or
        (= snowballs max_snowballs) ; Don't reload if we're full.
        (and (= opponent_ducks 0) (= opponent_snowballs max_snowballs)) ; Don't reload if opponent will throw.
        )))

(define (throw-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (not (or
        (= snowballs 0) ; Don't throw if we don't have any snowballs.
        (= opponent_snowballs max_snowballs) ; Don't throw if our opponent won't be reloading.
        )))

(define (duck-valid? snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (not (or
        (= ducks 0) ; Don't duck if we can't.
        (= opponent_snowballs 0) ; Don't duck if our opponent can't throw.
        )))

; Parse the command line, make a choice, print it out.
(command-line
 #:args (turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
 (writeln (make-choice
           (string->number turn)
           (string->number snowballs)
           (string->number opponent_snowballs)
           (string->number ducks)
           (string->number opponent_ducks)
           (string->number max_snowballs))))

```

I also made a small test program to run two of these bots against each other. It feels like the second bot wins more often, so I may have made a mistake somewhere.

```
(define (run)
  (run-helper 0 0 0 5 5 5))

(define (run-helper turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (printf "~a ~a ~a ~a ~a ~a ~n" turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (let ((my-action (make-choice turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs))
        (opponent-action (make-choice turn opponent_snowballs snowballs opponent_ducks ducks max_snowballs)))
    (cond ((= my-action reload)
           (cond ((= opponent-action reload)
                  (run-helper (+ turn 1) (+ snowballs 1) (+ opponent_snowballs 1) ducks opponent_ducks max_snowballs))
                 ((= opponent-action throw)
                  (writeln "Opponent wins!"))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) (+ snowballs 1) opponent_snowballs ducks (- opponent_ducks 1) max_snowballs))))
          ((= my-action throw)
           (cond ((= opponent-action reload)
                  (writeln "I win!"))
                 ((= opponent-action throw)
                  (run-helper (+ turn 1) (- snowballs 1) (- opponent_snowballs 1) ducks opponent_ducks max_snowballs))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) (- snowballs 1) opponent_snowballs ducks (- opponent_ducks 1) max_snowballs))))
          ((= my-action duck)
           (cond ((= opponent-action reload)
                  (run-helper (+ turn 1) snowballs (+ opponent_snowballs 1) (- ducks 1) opponent_ducks max_snowballs))
                 ((= opponent-action throw)
                  (run-helper (+ turn 1) snowballs (- opponent_snowballs 1) (- ducks 1) opponent_ducks max_snowballs))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) snowballs opponent_snowballs (- ducks 1) (- opponent_ducks 1) max_snowballs)))))))

```
> 1 votes

# Answer
# MonteBot, C++

I basically took the code from this koth and modified it for this challenge. It uses the Decoupled UCT Monte Carlo Tree Search algorithm. It should be pretty close to the nash equilibrium.

```
#include <cstdlib>
#include <cmath>
#include <random>
#include <cassert>
#include <iostream>

static const int TOTAL_ACTIONS = 3;
static const int RELOAD = 0;
static const int THROW = 1;
static const int DUCK = 2;

//The number of simulated games we run every time our program is called.
static const int MONTE_ROUNDS = 10000;

struct Game
{
    int turn;
    int snowballs;
    int opponentSnowballs;
    int ducks;
    int opponentDucks;
    int maxSnowballs;
    bool alive;
    bool opponentAlive;

    Game(int turn, int snowballs, int opponentSnowballs, int ducks, int opponentDucks, int maxSnowballs)
        : turn(turn),
          snowballs(snowballs),
          opponentSnowballs(opponentSnowballs),
          ducks(ducks),
          opponentDucks(opponentDucks),
          maxSnowballs(maxSnowballs),
          alive(true),
          opponentAlive(true)
    {
    }

    Game(int turn, int snowballs, int opponentSnowballs, int ducks, int opponentDucks, int maxSnowballs, bool alive, bool opponentAlive)
        : turn(turn),
        snowballs(snowballs),
        opponentSnowballs(opponentSnowballs),
        ducks(ducks),
        opponentDucks(opponentDucks),
        maxSnowballs(maxSnowballs),
        alive(alive),
        opponentAlive(opponentAlive)
    {
    }

    bool atEnd() const
    {
        return !(alive && opponentAlive) || turn >= 1000;
    }

    bool isValidMove(int i, bool me)
    {
        if (atEnd())
        {
            return false;
        }

        switch (i)
        {
        case RELOAD:
            return (me ? snowballs : opponentSnowballs) < maxSnowballs;
        case THROW:
            return (me ? snowballs : opponentSnowballs) > 0;
        case DUCK:
            return (me ? ducks : opponentDucks) > 0 && (me ? opponentSnowballs : snowballs) > 0;
        default:
            throw "This should never be executed.";
        }

    }

    Game doTurn(int my_action, int enemy_action)
    {
        assert(isValidMove(my_action, true));
        assert(isValidMove(enemy_action, false));

        Game result(*this);

        result.turn++;

        switch (my_action)
        {
        case RELOAD:
            result.snowballs++;
            break;
        case THROW:
            result.snowballs--;
            if (enemy_action == RELOAD)
            {
                result.opponentAlive = false;
            }
            break;
        case DUCK:
            result.ducks--;
            break;
        default:
            throw "This should never be executed.";
        }

        switch (enemy_action)
        {
        case RELOAD:
            result.opponentSnowballs++;
            break;
        case THROW:
            result.opponentSnowballs--;
            if (my_action == RELOAD)
            {
                result.alive = false;
            }
            break;
        case DUCK:
            result.opponentDucks--;
            break;
        default:
            throw "This should never be executed.";
        }

        return result;
    }
};

struct Stat
{
    int wins;
    int attempts;

    Stat() : wins(0), attempts(0) {}
};

/**
* A Monte tree data structure.
*/
struct MonteTree
{
    //The state of the game.
    Game game;

    //myStats[i] returns the statistic for doing the i action in this state.
    Stat myStats[TOTAL_ACTIONS];
    //opponentStats[i] returns the statistic for the opponent doing the i action in this state.
    Stat opponentStats[TOTAL_ACTIONS];
    //Total number of times we've created statistics from this tree.
    int totalPlays = 0;

    //The action that led to this tree.
    int myAction;
    //The opponent action that led to this tree.
    int opponentAction;

    //The tree preceding this one.
    MonteTree *parent = nullptr;

    //subtrees[i][j] is the tree that would follow if I did action i and the
    //opponent did action j.
    MonteTree *subtrees[TOTAL_ACTIONS][TOTAL_ACTIONS] = { { nullptr } };

    MonteTree(const Game &game) :
        game(game), myAction(-1), opponentAction(-1) {}

    MonteTree(Game game, MonteTree *parent, int myAction, int opponentAction) :
        game(game), myAction(myAction), opponentAction(opponentAction), parent(parent)
    {
        //Make sure the parent tree keeps track of this tree.
        parent->subtrees[myAction][opponentAction] = this;
    }

    //The destructor so we can avoid slow ptr types and memory leaks.
    ~MonteTree()
    {
        //Delete all subtrees.
        for (int i = 0; i < TOTAL_ACTIONS; i++)
        {
            for (int j = 0; j < TOTAL_ACTIONS; j++)
            {
                auto branch = subtrees[i][j];

                if (branch)
                {
                    branch->parent = nullptr;
                    delete branch;
                }
            }
        }
    }

    double scoreMove(int move, bool me)
    {

        const Stat &stat = me ? myStats[move] : opponentStats[move];
        return stat.attempts == 0 ?
            HUGE_VAL :
            double(stat.wins) / stat.attempts + sqrt(2 * log(totalPlays) / stat.attempts);
    }

    MonteTree * expand(int myAction, int enemyAction)
    {
        return new MonteTree(
            game.doTurn(myAction, enemyAction),
            this,
            myAction,
            enemyAction);
    }

    int bestMove() const
    {
        //Select the move with the highest win rate.
        int best;
        double bestScore = -1;
        for (int i = 0; i < TOTAL_ACTIONS; i++)
        {
            if (myStats[i].attempts == 0)
            {
                continue;
            }

            double score = double(myStats[i].wins) / myStats[i].attempts;
            if (score > bestScore)
            {
                bestScore = score;
                best = i;
            }
        }

        return best;
    }
};

int random(int min, int max)
{
    static std::random_device rd;
    static std::mt19937 rng(rd());

    std::uniform_int_distribution<int> uni(min, max - 1);

    return uni(rng);
}

/**
* Trickle down root until we have to create a new leaf MonteTree or we hit the end of a game.
*/
MonteTree * selection(MonteTree *root)
{
    while (!root->game.atEnd())
    {
        //First pick the move that my bot will do.

        //The action my bot will do.
        int myAction;
        //The number of actions with the same bestScore.
        int same = 0;
        //The bestScore
        double bestScore = -1;

        for (int i = 0; i < TOTAL_ACTIONS; i++)
        {
            //Ignore invalid or idiot moves.
            if (!root->game.isValidMove(i, true))
            {
                continue;
            }

            //Get the score for doing move i. Uses
            double score = root->scoreMove(i, true);

            //Randomly select one score if multiple actions have the same score.
            //Why this works is boring to explain.
            if (score == bestScore)
            {
                same++;
                if (random(0, same) == 0)
                {
                    myAction = i;
                }
            }
            //Yay! We found a better action.
            else if (score > bestScore)
            {
                same = 1;
                myAction = i;
                bestScore = score;
            }
        }

        //The action the enemy will do.
        int enemyAction;

        //Use the same algorithm to pick the enemies move we use for ourselves.
        same = 0;
        bestScore = -1;
        for (int i = 0; i < TOTAL_ACTIONS; i++)
        {
            if (!root->game.isValidMove(i, false))
            {
                continue;
            }

            double score = root->scoreMove(i, false);
            if (score == bestScore)
            {
                same++;
                if (random(0, same) == 0)
                {
                    enemyAction = i;
                }
            }
            else if (score > bestScore)
            {
                same = 1;
                enemyAction = i;
                bestScore = score;
            }
        }

        //If this combination of actions hasn't been explored yet, create a new subtree to explore.
        if (!(*root).subtrees[myAction][enemyAction])
        {
            return root->expand(myAction, enemyAction);
        }

        //Do these actions and explore the next subtree.
        root = (*root).subtrees[myAction][enemyAction];
    }
    return root;
}

/**
* Chooses a random move for me and my opponent and does it.
*/
Game doRandomTurn(Game &game)
{
    //Select my random move.
    int myAction;
    int validMoves = 0;

    for (int i = 0; i < TOTAL_ACTIONS; i++)
    {
        //Don't do idiotic moves.
        //Select one at random.
        if (game.isValidMove(i, true))
        {
            validMoves++;
            if (random(0, validMoves) == 0)
            {
                myAction = i;
            }
        }
    }

    //Choose random opponent action.
    int opponentAction;

    //Whether the enemy has encountered this situation before
    bool enemyEncountered = false;

    validMoves = 0;

    //Weird algorithm that works and I don't want to explain.
    //What it does:
    //If the enemy has encountered this position before,
    //then it chooses a random action weighted by how often it did that action.
    //If they haven't, makes the enemy choose a random not idiot move.
    for (int i = 0; i < TOTAL_ACTIONS; i++)
    {
        if (game.isValidMove(i, false))
        {
            validMoves++;
            if (random(0, validMoves) == 0)
            {
                opponentAction = i;
            }
        }
    }

    return game.doTurn(myAction, opponentAction);
}

/**
* Randomly simulates the given game.
* Has me do random moves that are not stupid.
* Has opponent do random moves.
*
* Returns 1 for win. 0 for loss. -1 for draw.
*/
int simulate(Game game)
{
    while (!game.atEnd())
    {
        game = doRandomTurn(game);
    }

    if (game.alive > game.opponentAlive)
    {
        return 1;
    }
    else if (game.opponentAlive > game.alive)
    {
        return 0;
    }
    else //Draw
    {
        return -1;
    }
}

/**
* Propagates the score up the MonteTree from the leaf.
*/
void update(MonteTree *leaf, int score)
{
    while (true)
    {
        MonteTree *parent = leaf->parent;
        if (parent)
        {
            //-1 = draw, 1 = win for me, 0 = win for opponent
            if (score != -1)
            {
                parent->myStats[leaf->myAction].wins += score;
                parent->opponentStats[leaf->opponentAction].wins += 1 - score;
            }
            parent->myStats[leaf->myAction].attempts++;
            parent->opponentStats[leaf->opponentAction].attempts++;
            parent->totalPlays++;
            leaf = parent;
        }
        else
        {
            break;
        }
    }
}

int main(int argc, char* argv[])
{
    Game game(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]), atoi(argv[5]), atoi(argv[6]));

    MonteTree current(game);

    for (int i = 0; i < MONTE_ROUNDS; i++)
    {
        //Go down the tree until we find a leaf we haven't visites yet.
        MonteTree *leaf = selection(&current);

        //Randomly simulate the game at the leaf and get the result.
        int score = simulate(leaf->game);

        //Propagate the scores back up the root.
        update(leaf, score);
    }

    int move = current.bestMove();

    std::cout << move << std::endl;

    return 0;
}

```

Compile Instructions for linux:

Save to `MonteBot.cpp`.
Run `g++ -o -std=c++11 MonteBot MonteBot.cpp`.

Command to run: `./MonteBot <args>`
> 1 votes

# Answer
# The Procrastinator \- Python 3

The procrastinator will procrastinate by playing save the first couple of turns. Suddenly the panic monster wants to avoid loosing the resource war by countering the opponents most used move.

```
import sys

turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = map(int, sys.argv[1:])

max_ducks = 25
times_opponent_ducked = max_ducks - ducks
times_opponent_thrown = (turn - times_opponent_ducked - opponent_snowballs) / 2
times_opponent_reloaded = times_opponent_thrown + opponent_snowballs

## return a different action, if the disiered one is not possible
def throw():
    if snowballs:
        return 1
    else:
        return duck()

def duck():
    if ducks:
        return 2
    else:
        return reload()

def reload():
    return 0

def instant_gratification_monkey():
    ## throw, if you still have a ball left afterwards
    if snowballs >= 2 or opponent_ducks == 0:
        return throw()
    ## duck, if opponent can throw
    elif opponent_snowballs > 0:
        return duck()
    ## reload, if opponent has no balls and you have only one
    else:
        return reload()

def panic_monster():
    ## throw while possible, else reload
    if times_opponent_reloaded > times_opponent_ducked:
        if snowballs > 0:
            return throw()
        else:
            return reload()
    ## alternating reload and duck
    else:
        if turn % 2 == 1:
            return reload()
        else:
            return duck()

def procrastinator():
    if turn < 13 or (snowballs + ducks > opponent_snowballs + opponent_ducks):
        return instant_gratification_monkey()
    else:
        return panic_monster()

print(procrastinator())

```
> 1 votes

# Answer
# ParanoidBot and PanicBot - ActionScript3 (RedTamarin)

From an unfitting, niche language (with extensions to provide command-line arguments) hails skittish ParanoidBot and his dull ally, PanicBot.

## ParanoidBot

ParanoidBot is losing its mind, and has a needlessly specific strategy to depend on. First, it launches snowballs until a threshold is reached, keeping some in reserve. Then, after three cautionary ducks, paranoia sets in, and the bot attempts to stockpile more snowballs in between random ducks. After replenishing its supply, ParanoidBot returns to blindly throwing. Due to the voices in its head, ParanoidBot can tell if it is guaranteed to win or lose, and will "strategize" accordingly.

```
import shell.Program;
import shell;

var TURN:int = Program.argv[0];
var SB:int = Program.argv[1];
var OPSB:int = Program.argv[2];
var DC:int = Program.argv[3];
var OPDC:int = Program.argv[4];
var MAXSB:int = Program.argv[5];
var usedDucks:int = 0;

if (!FileSystem.exists("data"))
    FileSystem.write("data", 0);
else
    usedDucks = FileSystem.read("data");

if (SB > OPSB + OPDC)
{ trace(1); Program.abort(); }
if (SB + DC < OPSB) {
if (DC > 0)
    trace(2);
else if (SB > 0)
    trace(1);
else
    trace(0);
Program.abort(); }

if (usedDucks >= 3) {
    if (SB > MAXSB / 3) {
        usedDucks = 0;
        FileSystem.write("data", usedDucks);
        trace(1);
        Program.abort();
    }
    else {
        if (Number.random() > 0.5 && DC > 0)
            trace(2);
        else
            trace(0);
    }
}
else {
    if (SB > (MAXSB / 6) && SB >= 3)
    { trace(1); Program.abort(); }
    else {
        usedDucks++;
        FileSystem.write("data", usedDucks);
        if (DC > 0)
            trace(2);
        else if (SB > 0)
            trace(1);
        else
            trace(0);
        Program.abort();
    }
}

```

<sub>Braces are a little wonky to help condense size</sub>

## PanicBot

Having already gone insane, PanicBot reacts out of instinctual fear. After running out of ducks from cowering in fear, PanicBot blindly throws all of its snowballs, then desperately makes and throws more snowballs until (probably) defeated.

```
import shell.Program;

var SB:int = Program.argv[1];
var DC:int = Program.argv[3];

if (DC > 0)
{ trace(2); Program.abort(); }
if (SB > 0)
{ trace(1); Program.abort(); }
else
{ trace(0); Program.abort(); }

```

---

This is one of less than 15 other entries using AS3 here on PPCG. One day, perhaps this arguably exotic language will find a puzzle to dominate.
> 0 votes

# Answer
# Defender, Python

Reloads when neither player has snowballs. If it has snowballs, it throws. If it doesn't have snowballs, but the opponent does, it ducks if it can, otherwise reloads.

```
def get_move(turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs):
    if snowballs == opponent_snowballs == 0:
        return 0 #Reload
    elif snowballs > 0:
        return 1 # Throw
    elif ducks > 0:
        return 2 # Duck
    else:
        return 0 # Reload

if __name__ == "__main__": # if this is the main program
    import sys
    print(main(*[int(arg) for arg in sys.argv[1:]]))

```

Note: not tested yet
> 0 votes

---
Tags: king-of-the-hill
---


title: Construct a Permuter

text:
# Question
Title: Construct a Permuter
For this challenge you are going to make a function (your function may be a complete program) that takes a list as input and returns a permutation of that list. Your function must obey the following requirements.

* It must be deterministic.
* Composing your function with itself a variable number of times should be capable of getting a list to any of its permutations.

This is a code-golf question so answers will be scored in bytes, with less bytes being better.

## Further rules

* You may take any type of list, (`[Integer]`,`[String]`,`[[Integer]]`) as long as it

+ Can be non empty
    + Can contain distinct objects with at least 16 possible values. (You can't use a Haskell `[()]` and claim your function is `id`)
    + Can contain duplicate objects (no sets)
* You may write a program or a function, but must obey standard IO.

# Answer
> 4 votes
## CJam (11 bytes)

```
{_e!_@a#(=}

```

Online demo showing the full cycle for a four-element list with one duplicate element.

### Dissection

```
{      e# Define a block
  _e!  e#   Find all permutations of the input. Note that if there are duplicate
       e#   elements in the input then only distinct permutations are produced.
       e#   Note also that the permutations are always generated in lexicographic
       e#   order, so the order is independent of the input.
  _@a# e#   Find the index of the input in the list
  (=   e#   Decrement and get the corresponding element of the list
       e#   Incrementing would also have worked, but indexing by -1 feels less
       e#   wrong than indexing by the length, and makes this more portable to
       e#   GolfScript if it ever adds a "permutations" built-in
}

```

# Answer
> 2 votes
## JavaScript (ES6), ~~145~~ ~~139~~ ~~137~~ ~~134~~ 108 bytes

*Saved a whopping 25 bytes thanks to @Neil!*

Takes input as an array of alphabetical characters. Returns the next permutation as another array.

```
a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,a.concat(a.splice(x+1).sort()))

```

### How?

This is a generation in lexicographic order that processes the 4 following steps at each iteration:

1. Find the largest index *X* such that *a\[X\] \< a\[X+1\]*

```
a.map((v, i) => v < a[i + 1] ? (t = v, x = i) : ...)

```
2. Find the largest index *Y* greater than *X* such that *a\[Y\] \> a\[X\]*

```
a.map((v, i) => v < a[i + 1] ? ... : y = i > x & v > t ? i : y)

```
3. Swap the value of *a\[X\]* with that of *a\[Y\]*

```
a[x] = a[y], a[y] = t

```
4. Sort the sequence from *a\[X + 1\]* up to and including the final element, in ascending lexicographic order

```
a.concat(a.splice(x + 1).sort())

```

Example:

### Demo

```
let f =

a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,a.concat(a.splice(x+1).sort()))

for(a = ["A", "B", "C", "D"], n = 0; n < 25; n++) {
  console.log(a.join(','));
  a = f(a);
}
```

# Answer
> 2 votes
## Mathematica + Combinatorica (Built-in Package) 34 Bytes

19 bytes to load the package and 15 for the function.

```
<<"Combinatorica`";NextPermutation

```

Usage:

```
%@{c, b, a}

```

Without the built-in, 61 Bytes

```
Extract[s=Permutations[Sort@#],Mod[s~Position~#+1,Length@s]]&

```

Combinatorica is supposed to be fully incorporated into Mathematica, but I think the NextPermutation function was overlooked.

# Answer
> 2 votes
# Python 3, 90 bytes

```
from itertools import*
def f(l):p=[*permutations(sorted(l))];return p[-~p.index(l)%len(p)]

```

Try it online!

# Answer
> 2 votes
# C++, 42 bytes

```
#include <algorithm>
std::next_permutation

```

This exact operation is a builtin in C++.

# Answer
> 1 votes
# Jelly, 6 bytes

```
Œ¿’œ?Ṣ

```

Cycles through the permutations in descending lexicographical order.

Try it online!

### How it works

```
Œ¿’œ?Ṣ  Main link. Argument: A (array)

Œ¿      Compute the permutation index n of A, i.e., the index of A in the
        lexicographically sorted list of permutations of A.
  ’     Decrement the index by 1, yielding n-1.
     Ṣ  Sort A.
   œ?   Getthe (n-1)-th permutation of sorted A.

```

# Answer
> 1 votes
# Python 2, 154 bytes

```
x=input()
try:exec'%s=max(k for k in range(%s,len(x))if x[%s-1]<x[k]);'*2%tuple('i1kjii');x[i-1],x[j]=x[j],x[i-1];x[i:]=x[:i-1:-1]
except:x.sort()
print x

```

Try it online!

# Answer
> 1 votes
# C, 161 bytes

Actual O(n) algorithm.

```
#define S(x,y){t=x;x=y;y=t;}
P(a,n,i,j,t)int*a;{for(i=n;--i&&a[i-1]>a[i];);for(j=n;i&&a[--j]<=a[i-1];);if(i)S(a[i-1],a[j])for(j=0;j++<n-i>>1;)S(a[i+j-1],a[n-j])}

```

Example usage:

```
int main(int argc, char** argv) {
    int i;
    int a[] = {1, 2, 3, 4};

    for (i = 0; i < 25; ++i) {
        printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
        P(a, 4);
    }

    return 0;
}

```

# Answer
> 0 votes
# Jelly, 10 bytes

```
ṢŒ!Q©i⁸‘ị®

```

Try it online!

Sort \> all permutation \> find input \> add 1 \> index into "all permutation

# Answer
> 0 votes
# 05AB1E, 7 bytes

```
œêD¹k>è

```

Try it online!

# Answer
> 0 votes
# PHP, 117 bytes

Takes input/output as string list of lower letters

```
$a=str_split($s=$argn);rsort($a);if(join($a)!=$s)for($n=$s;($c=count_chars)(++$n)!=$c($s););else$n=strrev($s);echo$n;

```

Try it online!

---
Tags: code-golf, permutations, open-ended-function
---


title: Mutation-hardened quine

text:
# Question
Title: Mutation-hardened quine
Your task is to make a program that prints out its own source.

"Hey, we already have this challenge, and tons of variations of it! Why are you making another one?" you may ask, but this one is going to be one of the most difficult ones (hopefully, anyway).

Your quine must be "mutation-hardened", which means the quine, even when any one of its characters are duplicated in place, must output the source code of the original program.

For example, if you have a quine (the following example is not written in any language, it's just pseudocode):

```
abcd

```

These programs must all output `abcd`:

```
aabcd
abbcd
abccd
abcdd

```

(In each of those programs, `a`, `b`, `c` and `d` are each duplicated in-place, which means the duplicated character was placed directly after the original character.)

## Rules:

* Standard quine rules apply.
* A multi-byte character counts as one character, and the character is not "split" into its respective bytes when duplicated.

This is , so shortest code in bytes wins!

# Answer
# \>\<\>, 56 bytes

```
^
.
+
8
f
0
o
a
o
~
:
?
~
:
?
:
-
*
4
8
:
^
^
}
*
3
d
'

```

Try it online! or verify all mutations.

### How the original program works (outdated)

The interpreter starts in cell **(0, 0)**. `^` sets the direction to *upwards*, so the instruction pointer (IP) wraps around to cell **(0, 20)**.

`'` activates string mode: until the next `'` is encountered, all characters under the IP are pushed on the stack. The same `'` is found again after wrapping around, so we push

```
d3*}^^:84*=?~oao0f.^

```

The IP lands at **(0, 19)**, still going upwards. Executing `d3*}` pushes **13 = 0xd**, then **3**, multiplies both values (**39** / *single quote*), then rotates the stack to the right. This leaves the stack as follows.

```
'd3*}^^:84*=?~oao0f.^

```

The next two instructions (`^`) do nothing at this point.

`:84*=` duplicates the top of the stack, pushes **8** and **4**, multiplies them (**32** / *space*), then tests the duplicated character for equality with *space*. For the unaltered program, this will always push **0**.

`?` skips the next instruction if the top of the stack is falsy. For the original program, it always is, so `~` is always skipped.

`oao` pops and prints the top of the stack, pushes a **10** / *linefeed*, then pops and prints *linefeed*.

Finally `0f.` jumps to cell **(0, 15)** (the bottommost `^`), starting over with the next character on the stack.

Once the stack is empty, the entire source code has been printed. `:` will fail and the program exits.

### How the mutated programs work (outdated)

Duplicating any non-linefeed character will only extend the program horizontally. Since the program is executed vertically, these extra instructions will never get executed.

Duplicating any linefeed before the bottomost `^` will shift cells **(0, 14)** and **(0, 15)** to **(0, 15)** and **(0, 16)**. `0f.` will now jump to the cell before the bottommost `^`, which is also a `^`, so the program is not affected by the shift.

Finally, any duplicated linefeed character will also alter the string. Short lines are padded with spaces, so a **32** / *space* will be inserted at the linefeed's position. `84*=` will push **1** for space, so `?` doesn't skip the next instruction. In this case, `~` pops and discards *space*, so the following `o` will print the character above *space* instead.
> 18 votes

---
Tags: code-golf, quine, radiation-hardening
---


title: Prankster Santa

text:
# Question
Title: Prankster Santa
It is widely known that Santa Claus delivers presents to houses all over the world in December. However, not many people know what he does during the rest of the year. You see, Santa enjoys a jolly good prank, and he'll often find himself pranking entire cities when he's not busy making or delivering toys.

One place that he particularly enjoys pranking is the South Pole. You might be saying, "The South Pole isn't a city." You would be right, but Santa doesn't care. There are `h` houses in the South Pole, which are conveniently numbered from `1` to `h`. Whenever Santa is in the mood for pranking, he'll start at a particular house, s. He rings the doorbell, then runs to another house.

He always visits houses in order, but just so he doesn't arouse suspicion, he only knocks on every `k`th house (for example, every `2`nd or `3`rd house), where `k``2`. This is because the residents (who are penguins) would know that something's up if one or both of their next door neighbors were pranked as well. Once Santa pranks `p` houses that day (or passes house number `h`), he goes back home to the North Pole.

After pranking houses for `d` days, though, Santa feels bad for pranking the penguins so many times. To make things right, he decides that next Christmas he will award the biggest and best gift to the penguin who got pranked the most. If there are multiple houses that got pranked the most, he will award the gift to the penguin in the lowest numbered house.

**The Problem:** Help Santa by telling him which house should receive the biggest and best gift the following Christmas. Santa, of course, wants to make amends each and every year so he needs your suggestion for each one.

**The Input:** Two integers, `h` and `d`, representing the number of houses and the number of days that Santa pranked the South Pole that year, respectively. Additionally, take in multiple sets of three integers, `s`, `k`, and `p`, denoting the starting house, the number representing his frequency of visiting houses (he skips `k`-1 houses), and the maximum number of houses he pranks that day. Note that he will visit p houses unless he passes the very last house. You may take these inputs in any reasonable format.

Output `g`, where `g` is the house number that should receive the biggest and best gift (the house that got pranked the most, and the lowest house number in the case of a tie). **Note that you may not use zero-based indexing, because Santa doesn't know what a computer is.**

Test cases:

```
4 3
1 2 1
3 4 2
2 2 2
Output: 1

10 2
2 3 2
3 2 5
Output: 5

50 100
10 10 36
17 7 1
37 2 19
28 2 49
29 3 29
48 3 12
35 3 25
28 4 20
38 8 27
39 3 19
26 4 9
20 7 8
47 10 1
6 10 43
31 3 29
35 2 23
24 9 44
10 3 25
29 10 37
32 5 47
21 5 31
44 5 43
46 4 47
16 10 5
5 3 18
7 8 10
48 5 31
29 4 7
31 8 5
23 9 43
34 8 4
41 10 38
30 6 23
17 7 1
43 5 24
29 2 37
22 10 19
17 6 43
37 3 22
42 10 9
48 4 47
11 6 3
29 7 42
11 9 28
3 4 9
39 9 7
20 9 5
47 5 29
20 4 4
44 10 30
30 6 21
39 10 38
7 9 18
32 10 47
14 9 13
7 2 8
44 3 19
40 4 12
4 10 12
3 5 46
3 5 37
29 9 45
16 4 26
27 9 32
37 10 16
30 5 39
36 2 26
25 2 28
13 3 16
8 8 27
27 6 29
39 10 10
34 7 47
5 4 17
39 2 9
45 2 24
4 6 11
8 10 24
50 7 30
7 4 37
35 10 44
35 9 28
49 10 7
20 5 17
30 4 50
18 7 4
4 7 14
38 9 40
27 3 15
39 5 13
8 2 46
15 4 13
21 9 49
28 6 29
48 5 35
8 8 5
27 3 41
35 10 23
14 4 15
12 2 22
Output: 48

```

**Scoring:** Number of bytes. Subtract 20 bytes from your score if your program can handle inputs of up to 100,000 (both days and houses) in less than 5 seconds on a standard desktop PC. Note that in all these inputs k will be less than or equal to 10.

# Answer
> 3 votes
# Jelly, 20 bytes

```
Ḣrm⁸Ḣ¤ḣ⁸
ç€FµĠLÐṀḢḢị

```

A dyadic link taking a list of lists of numbers, the list of `s,k,p` values, and a number `h` (`d` is just the length of the list so is redundant), returning the house number.

**Try it online!**

### How?

Builds lists of house numbers visited each day, then finds those visited the most and returns the minimal numbered one.

```
Ḣrm⁸Ḣ¤ḣ⁸ - Link 1, get houses visited on one day: list, [s,k,p]; number, h
Ḣ        - head  = s (modifies the list to become [k,p])
 r       - inclusive range = [s,s+1,s+2,...,h]
     ¤   - nilad followed by link(s) as a nilad:
   ⁸     -   chain's left argument = [k,p]
    Ḣ    -   head = k (modifies the list to become [p])
  m      - modulo slice (take the 1st item then every kth item of the range)
       ⁸ - chain's left argument = [p]
      ḣ  - head to index (vectorises) (take the first p items, or all if less
         -   this will yield a list of length 1 containing the truncated list)

ç€FµĠLÐṀḢḢị - Link: list of lists [[s1,k1,p1],[s2,k2,p2],...]; number, h
ç€          - call the last link as a dyad for €ach
  F         - flatten into a single list (all the houses visited)
   µ        - monadic chain separation, call that v
    Ġ       - group indexes by value (indexes of smallest houses will go first)
      ÐṀ    - filter to keep only those with maximal:
     L      -   length (the groups containing indexes of houses visited most)
        Ḣ   - head (get the first such group)
         Ḣ  - head (get the fist index from the group)
          ị - index into v (get the house number)

```

# Answer
> 0 votes
# Python 3, 158 bytes

```
r=range
def f(h,_,x):
 L=[0]*h
 for s,k,p in x:
  n=0
  for i in r(s,h+1,k):
   if n>p:break
   L[i-1]+=1
   n+=1
 return[i for i in r(h)if L[i]==max(L)][0]+1

```

Try it online

So this is barely golfed or optimized, but it's a start. I may return to it if I think of better ways to do it. And it doesn't get the bonus. v\_v

# Answer
> 0 votes
# Python 2, 78 bytes

```
h,a=input();l=[]
for s,k,p in a:l+=range(s,h+1,k)[:p]
print max(l,key=l.count)

```

Try it online!

Takes input without the numbers of days.

---
Tags: code-golf, math
---