Schneeballschlacht KoTH!

35

Ergebnisse (22. Mai 2017 21:40:37 UTC)

Master18 Runden gewonnen, 2 Runden verloren und 0 Runden
Save Oneunentschieden 15 Runden gewonnen, 3 Runden verloren und 2 Runden
Machine Gununentschieden 14 Runden gewonnen, 3 Runden verloren und 3 Runden
Monte Botunentschieden 14 Runden gewonnen, 3 Runden verloren und 3 Runden
Amb Botunentschieden 12 Runden gewonnen Runden, 8 Runden verloren und 0 Runden unentschieden
Cowardgewonnen 11 Runden, 3 Runden verloren und 6 Runden unentschieden
Pain in the Nashgewonnen 11 Runden, 9 Runden verloren und 0 Runden unentschieden
Nece Botgewonnen 10 Runden, 7 Runden verloren und 3 Runden unentschieden
Naming Things is Hardgewonnen 10 Runden, 7 Runden verloren und 3 Runden
The Procrastinatorunentschieden 10 Runden gewonnen, 8 Runden verloren und 2 Runden
Yggdrasilunentschieden 10 Runden gewonnen, 10 Runden verloren und 0 Runden
Simple Botunentschieden 9 Runden gewonnen, 4 Runden verloren und 7 Runden
Table Botunentschieden 9 Runden verloren, 6 Runden verloren Runden und Unentschieden 5 Runden haben
Prioritized Random Bot8 Runden gewonnen, 7 Runden verloren und 5 Runden unentschieden
Upper Hand Bot7 Runden gewonnen, 13 Runden verloren und 0 Runden
Aggressorunentschieden 6 Runden gewonnen, 10 Runden verloren und 4 Runden
Insaneunentschieden 5 Runden gewonnen, 15 Runden verloren und 0 Runden
The Ugly Ducklingunentschieden 4 Runden gewonnen, 16 Runden verloren und 0 Runden
Know Botunentschieden 3 Runden gewonnen Runden, 14 Runden verloren und 3 Runden unentschieden
Paranoid Botgewonnen 0 Runden, 19 Runden verloren und 1 Runde unentschieden
Panic Botgewonnen 0 Runden, 19 Runden verloren und 1 Runde unentschieden

Leider konnte ich The Crazy X-Code Randomess nicht testen, da ich es nicht von Bash auf Linux ausführen kann. Ich werde es hinzufügen, wenn ich es zum Laufen bringen kann.

Volle Controller-Ausgabe


Das Spiel

Dies ist ein sehr einfaches KoTH-Spiel. Es ist eine Eins-zu-Eins-Schneeballschlacht. Sie haben einen anfänglich leeren Behälter, der kSchneebällen standhalten kann. Sie können sich bis zu jZeiten ducken . In jeder Runde werden beide Spieler gebeten, gleichzeitig eine Wahl für ihren Zug zu treffen. Es gibt drei Züge:

  • reload: gibt dir noch einen schneeball (bis zu k)
  • werfen: Wirft einen Schneeball, der den anderen Spieler tötet, wenn er sich zum Nachladen entscheidet. Wenn beide Spieler einen Schneeball werfen, stirbt niemand (sie haben ein so gutes Ziel, dass sie sich gegenseitig auf die Schneebälle schlagen)
  • duck: tut nichts und vermeidet es, getroffen zu werden, wenn der andere Spieler einen Schneeball wirft. Wenn du keine Enten mehr hast, passiert nichts und wenn der andere Spieler einen Schneeball wirft, stirbst du.

Zielsetzung

Stirb nicht

Herausforderungsspezifikationen

Ihr Programm kann in jeder Sprache geschrieben werden. Sie müssen jede dieser Variablen als Argument für jede Ausführung verwenden:

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

turn- wie viele Runden sind vergangen ( 0bei der ersten Iteration)
snowballs- wie viele Schneebälle hast du
opponent_snowballs- wie viele Schneebälle hat der Gegner
ducks- wie oft du ducken kannst
opponent_ducks- wie oft der Gegner ducken kann - wie viele
max_snowballsSchneebälle kannst du maximal store ( k)

Die Ausgabe der Tastenfunktion sollte 0für das Nachladen, 1für das Werfen und 2für die Ente sein. Sie müssen Ihren Umzug ausgeben, Newline beendet. Bitte gib keine ungültigen Züge aus, aber der Controller ist sehr belastbar und bricht nicht ab, wenn du ungültige Züge ausgibst (auch wenn dein Zug keine ganze Zahl ist). Es muss jedoch mit einem Zeilenvorschub abgeschlossen werden. Wenn der Umzug nicht erfolgt [0, 1, 2], wird standardmäßig der Umzug nach ausgeführt 0. Der Gewinner wird als der Spieler mit den meisten Gewinnen aus einem Full-Round-Robin-Turnier ermittelt.

Regeln

Sie können von / zu einer Datei lesen / schreiben, um zwischen den Iterationen Speicherplatz zu schaffen. Ihr Bot wird in einem eigenen Verzeichnis abgelegt, damit es nicht zu Dateikonflikten kommt. Sie können keine eingebauten Funktionen (wie den Zufallsgenerator) ändern. Es war ziemlich lustig, als es das erste Mal gemacht wurde , aber es wird nicht mehr sein. Ihr Programm ist nicht berechtigt, Dinge zu tun, die nur ein offenes Anhalten der Ausführung bedeuten. Es gelten Standardlücken .

Testen

Den Quellcode für den Controller finden Sie hier . Beispiel für das Laufen: java Controller "python program1/test1.py" "python program2/test2.py" 10 5für 10 Schneebälle und 5 Enten.

Beurteilen

Der Gewinner wird durch Auswahl der Person mit den meisten Gewinnen nach einem vollständigen Round-Robin ermittelt. Entfernen Sie alle Personen, die nicht die meisten Siege haben, während dies ein Unentschieden ist. Dann wiederholen, bis eine Person gewinnt. Der Richtstandard wird 50 Schneebälle und 25 Enten sein.

Alles Gute!

BEARBEITEN : Das Spiel wird für unentschieden erklärt, wenn 1000 Runden verstrichen sind. Ihr Bot könnte das annehmen turn < 1000.

HyperNeutrino
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis
@HyperNeutrino Weitere Fragen: Ich dachte, der "Richtstandard" wäre 50 Schneebälle und 25 Enten? Und warum gibt es manchmal nach ~ 18 Runden ein Unentschieden?
CommonGuy
@Manu Ehh Mist Ich habe vergessen, die Einstellungen in meinen VM-Argumenten zu ändern. Und das liegt auch daran, dass wenn sie in eine endlose Schleife von Schneeballkollisionen geraten, diese nach 10 Runden Wiederholen einer Periode-1 oder Periode-2-Schleife beendet wird.
HyperNeutrino
1
Also, wird es noch eine Runde geben? Denn ich möchte meinen Bot hochladen und wäre gespannt, wie gut er funktionieren würde.
erbsenhirn
@erbsenhirn Wenn du einen Bot hochlädst und mich im Chat oder auf The Nineteenth Byte anpingst, starte ich einen weiteren Lauf.
HyperNeutrino

Antworten:

13

Meister, C #

Ich habe ein kleines neuronales Netzwerk trainiert (mit Sharpneat ). Es scheint, als würde man gerne Schneebälle einsammeln und sich ducken ...

In einer früheren Version des Controllers wurde sogar ein Fehler gefunden. Es ging von 0% Gewinn zu 100%, als es entdeckte, wie man durch Schummeln gewinnt.

Bearbeiten: Ich habe vergessen, den Netzwerk-Interal-Status zurückzusetzen und das Netzwerk falsch trainiert. Das neu geschulte Netzwerk ist viel kleiner.

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
}
CommonGuy
quelle
Offensichtlich hat das Zurücksetzen des Netzwerkstatus die Leistung
erheblich verbessert
Gegen was hast du das neuronale Netz trainiert? Gegen andere hier gepostete Bots?
JAD
@ JarkoDubbeldam Ja, ich habe mehrere von ihnen nach C # portiert und das Netzwerk auf sie trainiert. Deshalb wird es wahrscheinlich gegen neue Bots verlieren.
CommonGuy
Oder trainiere einfach ein anderes Netzwerk gegen die Bots und dieses: p
JAD
Wat. 8 Stimmen für ein neuronales Netz!
Christopher
6

Speichern Sie eine, Python

Wirft die meisten seiner Schneebälle sofort ab, speichert jedoch immer einen, falls der Gegner auf Munitionsmangel achtet. Dann duckt es sich so lange wie möglich (erneut mit 1), bevor es erneut geladen wird, es sei denn, es gibt ein garantiertes sicheres Nachladen oder einen garantierten 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
Schnarchfrosch
quelle
2
Wenn Sie 0 Schneebälle haben, wird versucht, 1 zu werfen
Carl Bosch
@CarlBosch das sollte unmöglich zu erreichen sein (außer mit 0 zu beginnen), aber ich werde eine Änderung
vornehmen
2
@ SnoringFrog, um die Regeln zu klären, beginnen Sie mit 0 Schneebällen
PhiNotPi
@PhiNotPi Das muss ich völlig übersehen haben. Vielen Dank für die Klarstellung
SnoringFrog
6

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);
        }
    }
}

Dieser Bot wählt eine zufällige Ganzzahl im Bereich 0bis aus os + odund wählt dann entweder werfen, ducken oder nachladen, wobei die Schwellenwerte durch die aktuelle Anzahl von Schneebällen und Enten bestimmt werden.

Eine wichtige Erkenntnis ist, dass Sie einen Sieg erzwingen können, wenn ein Bot mehr Schneebälle als der andere Bot Schneebälle + Enten hat. Daraus können wir das Konzept der "Punkte" entwickeln:

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   -    +    +

Wenn eine dieser Zahlen positiv wird, kann dieser Spieler einen Gewinn erzwingen.

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   +    +   ++

Die Tabelle "Punktedifferenz" bildet die Grundlage der Spieltheorie für diesen Wettbewerb. Es erfasst nicht alle Informationen, zeigt jedoch, wie wertvoll Schneebälle grundsätzlich sind als Enten (da Schneebälle sowohl Angriff als auch Verteidigung sind). Wenn der Gegner einen Schneeball wirft und du dich erfolgreich duckst, bist du einem gewaltsamen Sieg einen Schritt näher, da dein Gegner eine wertvollere Ressource verbraucht hat. In dieser Tabelle wird auch beschrieben, was Sie in vielen Sonderfällen tun sollten, z. B. wenn bestimmte Verschiebungsoptionen nicht verfügbar sind.

Die "Summe der Punkte" -Tabelle zeigt, wie sich die Summe der Punkte im Laufe der Zeit Null nähert (da beiden Spielern die Enten ausgehen). Zu diesem Zeitpunkt hat der erste Spieler einen Fehler begangen (neu geladen, wenn er es nicht musste) verliert.

Versuchen wir nun, diese Forcierungsstrategie auf Fälle auszudehnen, in denen sie nicht wirklich erzwungen werden kann (wie in, wir gewinnen mit großem Vorsprung, aber das Gedankenlesen des Gegners wird uns schlagen). Grundsätzlich haben wir sSchneebälle, aber wir müssen unseren Gegner s+1(oder s+2usw.) die Zeit nacheinander beschneiden, um zu gewinnen. In diesem Fall möchten wir entweder ein paar Enten oder ein paar Nachladungen durchführen, um uns etwas Zeit zu verschaffen.

Im Moment versucht dieser Bot immer, sich in ein paar Enten zu schleichen, nur weil er dann keinen unmittelbaren Verlust riskiert: Wir gehen davon aus, dass der Gegner eine ähnliche Strategie verfolgt und versucht, so viele Schneebälle wie möglich nachzuladen gefährlich. Um Vorhersagbarkeit zu vermeiden, möchten wir diese auch nach einer gleichmäßig zufälligen Verteilung einschleichen: Die Entenwahrscheinlichkeit hängt davon ab, wie viele Enten wir im Verhältnis zur Anzahl der zu schleudernden Schneebälle ausführen müssen.

Wenn wir stark verlieren, s + d < os + odmüssen wir in diesem Fall einige Nachladevorgänge einleiten und zusätzlich alle unsere Enten einsetzen. In diesem Fall möchten wir nach dem Zufallsprinzip nachladen, jedoch nur so oft, wie wir es benötigen.

Dies ist der Grund, warum unsere Bots Prioritäten in der Reihenfolge werfen, ducken und nachladen setzen und os + oddie Zufallszahl generieren, da dies der Schwellenwert für die Anzahl der Züge ist, die wir ausführen müssen.

Es gibt einen Randfall und zwei weitere Sonderfälle, die der Bot derzeit behandelt. Der Edge-Fall ist, wenn der Gegner weder Schneebälle noch Enten hat und die Zufallsgenerierung daher nicht funktioniert. Wenn möglich, werfen wir also, andernfalls laden wir nach. Ein anderer Sonderfall ist, wenn der Gegner nicht nachladen kann und das Werfen keinen Vorteil hat (da der Gegner entweder duckt oder wirft), also ducken wir uns immer (da das Speichern unserer Schneebälle wertvoller ist als das Speichern unserer Enten). Der letzte Sonderfall ist, wenn der Gegner keine Schneebälle hat. In diesem Fall gehen wir auf Nummer sicher und laden nach Möglichkeit nach.

PhiNotPi
quelle
Dies kann dazu führen, dass mehrere Nummern gedruckt werden, die möglicherweise nicht richtig funktionieren.
HyperNeutrino
@HyperNeutrino Ich habe vergessen, einen "else" -Block hinzuzufügen, als ich diesen Bot neu geschrieben habe, weil er Return-to-Print-Anweisungen verwendet.
PhiNotPi
1
@HyperNeutrino Es hat für mich getan, und ich hielt es für abgehört ...
Erik der Outgolfer
Ah. Ja, entschuldige, dass du deinen Code durcheinander gebracht hast: P Aber schönes, erstes Programm, das Zufälligkeit benutzt!
HyperNeutrino
6

NeceBot - Python

Hier ist die Spieltheorie-Tabelle für das Spiel:

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

Wo ~bedeutet, dass kein Vorteil Wist, gewinnen List, verlieren ist, +-Sbedeutet , dass ein Schneeball gegenüber dem Gegner gewonnen / verloren ist, und +-Dbedeutet, dass eine Ente gegenüber dem Gegner gewonnen / verloren ist. Dies ist ein völlig symmetrisches Spiel.

Beachten Sie, dass meine Lösung diese Tabelle nicht berücksichtigt. Weil ich schlecht in Mathe bin.

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:])))

Es heißt NeceBot, weil es zuerst versucht, das Notwendige zu reduzieren. Danach gibt es einige willkürliche Strategien, von denen ich hoffe, dass sie funktionieren.

Artyer
quelle
4
Whee so viele <3s lol. +1 für ein Spieltisch und dann nicht verwenden: P Aber schöne Lösung :)
HyperNeutrino
3 + opponent_snowballs <3Das könnte ein Fehler sein?
PhiNotPi
@PhiNotPi Yup. Soll 2 sein. Jetzt behoben, danke!
Artyer
Leider macht die große Anzahl von <3s den Code ziemlich schwer zu verstehen :(
CalculatorFeline
5

Feigling - Scala

Wirft, wenn der Gegner keine Munition hat, ansonsten (in der Reihenfolge der Priorität) duckt, wirft oder lädt nach.

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)
}
IchBinKeinBaum
quelle
Scheint, dass dies mein Bot
stört
5

TheUglyDuckling - Python

Duckt sich immer, bis er nicht mehr werfen kann, wenn der Gegner leer ist, oder lädt nach, wenn beide leer sind. Wird reload als letzten Ausweg verwenden.

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
Thrax
quelle
5

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

Einfaches Zeug.

  • Wenn der Gegner Schneebälle hat und du Enten hast, dann duckst du dich.
  • Wenn der Gegner keine Schneebälle hat und Sie, dann werfen Sie.
  • In jedem anderen Fall laden Sie neu.
Erik der Outgolfer
quelle
5

Der Naming-things-is-hard-Bot - VB.NET

Dinge zu benennen ist schwer, und ich bin nicht sicher, ob ich eine zusammenhängende Strategie habe, um sie zu benennen.

Versucht in den ersten Runden zu spielen, um einen frühen Sieg zu erringen. Danach spielt der Rest der Zeit sicherer und versucht, durch Abrieb zu gewinnen.

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
Brian J
quelle
5

MachineGun, Python 3

Versucht, Schneebälle aufzubewahren, bis der Gegner garantiert getötet wird oder bis die Enten verschwunden sind.

Es duckt sich auch, wenn der Gegner einen Schneeball hat, weil er nicht sterben will.

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")
Tron
quelle
5

Knowbot, Python3

Verfolgt die Häufigkeit der vorherigen Züge, geht davon aus, dass der Gegner wieder die häufigste macht, und verteidigt sich dagegen.

** Aktualisiert, um keine Züge zu erwarten, die der Gegner nicht ausführen kann **

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);
Ahelly
quelle
Ich bin nicht sicher, wie das genau funktioniert, aber wenn es Daten zwischen Runden speichert (im Gegensatz zu Runden), werden leider alle Daten zwischen Runden gelöscht. Es macht Ihre Lösung nicht ungültig, aber denken Sie daran :)
HyperNeutrino
Es wird nicht erwartet, dass Daten zwischen den Runden gespeichert werden, nur um zu erwarten, dass der aktuelle Gegner konsistent ist.
AShelly
In Ordung. Okay. Ich wollte nur sicherstellen, dass es keine Missverständnisse gibt. :)
HyperNeutrino
4

Braingolf , der Angreifer

<<?1:0

Der Angreifer ist kein Feigling! Wenn er einen Schneeball hat, muss er werfen! Wenn er keine Schneebälle hat, soll er mehr machen!

Braingolf , der Wahnsinnige

Dies ist eigentlich kein Bot, sondern nur ein Programmierer, den ich entführt und gezwungen habe, jedes Projekt, das er jemals gemacht hat, auf Braingolf zu portieren. Er hat kein bisschen mehr Verstand.

<3r!?:1+|%

Erzeugt eine Zufallszahl kleiner als 3 und gibt aus, t % rwobei t die aktuelle Runde und r die Zufallszahl ist

Um diese auszuführen, müssen Sie braingolf.pyvon Github herunterladen , dann entweder den Braingolf-Code in einer Datei speichern und ausführen

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

oder einfach den Code direkt so einfügen

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

Die Eingaben sind ziemlich irrelevant, solange das zweite Argument nach dem Code / Dateinamen die Anzahl der Schneebälle angibt, die The Aggressor hat.

Hinweis: Der Angreifer verhält sich eigentlich identisch zum TestBot, ich wollte nur einen Eintrag in Braingolf machen

Braingolf , The Brainy [Derzeit gebrochen]

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
Skidsdev
quelle
Natürlich musste das jemand machen: D Schön und sogar golfen! : D
HyperNeutrino
Oh, warte, das ist dasselbe wie meins, außer Gofier. lol
HyperNeutrino
@HyperNeutrino yup, ich arbeite gerade an einem echten in einer echten Sprache. Ich würde Braingolf für eine echte verwenden, aber es kann keine verschachtelten Bedingungen erfüllen, so dass die Dinge schwierig werden
Skidsdev
2
Ich denke, Sie sollten "The Brainy" als separate Antwort posten. Auch ich denke, dass es sich irrt.
Erik der Outgolfer
"The Insane" ist kein stabiler Bot, daher bin ich mir nicht sicher, wie @HyperNeutrino das überprüfen würde.
Erik der Outgolfer
3

TestBot - Python

Dies ist ein Testbeitrag, der Ihnen zeigt, wie ein gültiger Beitrag aussehen kann. Die Strategie: Abwechselnd nachladen und werfen. Eine ziemlich schlechte Strategie, aber sie gibt Ihnen eine Vorstellung davon, wie Ihr Programm funktionieren sollte.

from os import sys
arguments = sys.argv;
turn = int(arguments[1])
print(turn % 2)
HyperNeutrino
quelle
Wären _, turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = sys.argvdie Argumente?
Artyer
@Artyer Ja. Es stellt sich heraus, dass das erste Argument den Dateinamen hat.
HyperNeutrino
Sie können nur verwenden, sys.argv[1:]wenn Sie sich nicht damit _
anlegen
2

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)

Dieser Bot versucht, mehr Schneebälle als sein Gegner zu sammeln und wirft dann los. Wenn UHB zu irgendeinem Zeitpunkt nicht mehr Schneebälle als sein Gegner hat, wird es:

  • Ente, wenn der Gegner Schneebälle hat und noch Enten übrig sind
  • Andernfalls laden Sie neu (es sei denn, UHB ist auf dem Maximum, dann wirft es stattdessen, obwohl ich nicht glaube, dass diese Situation jemals eintreten würde)
Geschäfts-Katze
quelle
2

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;
        }
    }
}

Ich habe diesen Bot "Yggdrasil" genannt, weil er tatsächlich im Spielbaum nach vorne schaut und eine Zustandsbewertung durchführt, aus der er eine annähernd ideale gemischte Strategie berechnen kann. Da es auf gemischten Strategien beruht, ist es sehr nicht deterministisch. Ich weiß nicht, wie gut dieses Ding im echten Wettbewerb abschneiden wird.

Ein paar Dinge über diesen Bot:

  • Der Kern ist eine rekursive Funktion, die den Wert und die nahezu ideale gemischte Strategie für einen bestimmten Spielzustand berechnet. Im Moment habe ich es eingestellt, um 4 Schritte vorauszusehen.
  • Es spielt sich extrem zierlich, da dieser Bot in vielen Fällen dem "Wählen einer zufälligen Bewegung mit einer Stein-Papier-Schere" gleichkommt. Es behauptet sich und hofft, dass sein Gegner ihm einen statistischen Vorteil verschafft. Wenn dieser Bot perfekt wäre (was nicht der Fall ist), wäre das Beste, was Sie dagegen tun könnten, 50% Gewinne und 50% Verluste. Infolgedessen gibt es keinen Gegner, den es beständig schlägt, aber auch keinen, gegen den es beständig verliert.
PhiNotPi
quelle
Ich verstehe immer noch nicht den Namen ...: P
HyperNeutrino
@HyperNeutrino Yggdrasil ist ein mythologischer Baum, und in diesem Fall beziehe ich mich auf den Spielbaum.
PhiNotPi
Ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh Hätte ich mich daran erinnern sollen. : P Schön!
HyperNeutrino
2

Schmerz im Nash (C ++)

So genannt, weil die Tatsache, dass ich meinen eigenen Nash-Gleichgewichtslöser schreiben musste, ein echtes Problem war. Ich bin erstaunt, dass es keine verfügbaren Nash-Lösungsbibliotheken gibt!

#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;
}

Kompilieren Sie als C ++ 11 oder besser. Für die Leistung ist es gut, mit OpenMP-Unterstützung zu kompilieren (dies dient jedoch nur der Geschwindigkeit; es ist nicht erforderlich).

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

Dabei werden die Nash-Gleichgewichte verwendet, um zu entscheiden, was in jeder Runde zu tun ist. Dies bedeutet, dass es theoretisch (über viele Spiele hinweg) auf lange Sicht immer gewinnt oder unentschieden bleibt, unabhängig davon, welche Strategie der Gegner anwendet. Ob dies in der Praxis der Fall ist, hängt davon ab, ob ich Fehler bei der Implementierung gemacht habe. Da dieser KoTH-Wettbewerb jedoch nur eine Runde gegen jeden Gegner hat, wird er in der Rangliste wahrscheinlich nicht sehr gut abschneiden.

Meine ursprüngliche Idee war es, eine einfache Bewertungsfunktion für jeden Spielstand zu haben (z. B. jeder Ball ist + b, jede Ente ist + d), aber dies führt zu offensichtlichen Problemen, um herauszufinden, wie diese Bewertungen aussehen sollten, und bedeutet, dass dies nicht möglich ist Handeln Sie, indem Sie die Renditen verringern, indem Sie immer mehr Bälle sammeln, usw. Stattdessen wird der gesamte Spielbaum analysiert , wobei ab Runde 1000 rückwärts gearbeitet wird. Geben Sie dann die tatsächlichen Bewertungen ein, die darauf basieren, wie sich jedes Spiel entwickeln könnte.

Das Ergebnis ist, dass ich absolut keine Ahnung habe, welche Strategie dies verwendet, außer ein paar hartcodierten "offensichtlichen" Verhaltensweisen (Schneebälle werfen, wenn Sie mehr Bälle haben als Ihr Gegner Bälle + Enten hat, und nachladen, wenn Sie beide aus sind von Schneebällen). Wenn jemand den von ihm erzeugten Datensatz analysieren möchte, stelle ich mir ein interessantes Verhalten vor!

Das Testen gegen "Save One" zeigt, dass es zwar langfristig gewinnt, aber nur mit einem kleinen Vorsprung (514 Siege, 486 Niederlagen, 0 Unentschieden in der ersten Partie von 1000 Spielen und 509 Siege, 491 Niederlagen, 0) zeichnet im zweiten).


Wichtig!

Dies funktioniert sofort, aber das ist keine gute Idee. Auf meinem Laptop mit moderaten Entwicklerspezifikationen dauert es ungefähr 9 Minuten, um den vollständigen Spielbaum zu generieren. Die endgültigen Wahrscheinlichkeiten werden jedoch in einer Datei gespeichert, sobald sie generiert wurden. Danach wird in jeder Runde nur eine Zufallszahl generiert und mit 2 Bytes verglichen. Das ist also superschnell.

Laden Sie einfach diese Datei (3,5 MB) herunter und legen Sie sie in dem Verzeichnis ab, in dem sich die ausführbare Datei befindet.

Oder Sie können es selbst generieren, indem Sie Folgendes ausführen:

./pain_in_the_nash 1000 50 25

Womit eine Datei pro Runde bis zur Konvergenz gespeichert wird. Beachten Sie, dass jede Datei 3,5 MB groß ist und bei 720 Runden konvergiert (dh 280 Dateien, ~ 1 GB). Da die meisten Spiele bei 720 Runden nicht annähernd ankommen, sind die Dateien vor der Konvergenz von sehr geringer Bedeutung.

Dave
quelle
Ist es möglich, dass das Programm nur das Endergebnis ausgibt? Vielen Dank!
HyperNeutrino
@HyperNeutrino Alle anderen Ausgaben sollten auf stderr eingestellt sein, daher sollten sie keine Auswirkungen haben. Ich habe sie jedoch so aktualisiert, dass sie nur den Fortschritt anzeigen, wenn sie im Vorverarbeitungsmodus ausgeführt werden. Es wird jetzt nur bei normaler Ausführung auf stdout geschrieben. Ich schlage jedoch vor, dem "wichtigen" Vorschlag zu folgen, da er ansonsten nur einige Minuten in der ersten Kurve herumhängt (zumindest bei Vorverarbeitung können Sie den Fortschritt sehen).
Dave
Oh ok. Ich werde diesem Vorschlag folgen, danke!
HyperNeutrino
Ich würde es begrüßen, wenn Sie die Datendateien hochladen könnten, da es ewig dauert, alle zu generieren. Wenn Sie das tun könnten, wäre das großartig :)
HyperNeutrino
@HyperNeutrino OK, es hat auch ewig gedauert, bis ich es in meinem schrecklichen Internet hochgeladen habe, aber die konvergierte 3,5-MB-Datei ist hier verfügbar: github.com/davidje13/snowball_koth_pitn/blob/master/… (einfach in dasselbe Verzeichnis stellen).
Dave
1

Swift - TheCrazy_XcodeRandomness

Leider kann dies nur lokal in Xcode ausgeführt werden, da es das FoundationModul und seine Funktion enthält arc4random_uniform(). Sie können jedoch ziemlich genau sagen, was der Algorithmus ist:

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
}
Mr. Xcoder
quelle
Kann dies von Bash unter Linux ausgeführt werden?
HyperNeutrino
@HyperNeutrino Ich weiß, dass es unter macOS funktioniert, aber ich weiß nicht, ob es unter Linux funktioniert. Wenn Sie das überprüfen können, wäre es großartig. Probieren Sie den swiftBefehl aus und prüfen Sie, ob er funktioniert
Mr. Xcoder,
Es scheint nicht zu existieren; Es gibt ein Paket, aber es ist nicht Swift die Sprache. Also kann ich das nicht testen, bis ich etwas zum Laufen bringen kann, sorry.
HyperNeutrino
Die einzigen möglichen Komplizen sind Xcode und IntelliJ, aber es kann nicht online ausgeführt werden, weil Foundation, sorry: /
Mr. Xcoder
Ruhe in Frieden. Ich müsste in der Lage sein, es von der Befehlszeile aus auszuführen, um den Controller damit auszuführen, aber wenn ich Zeit habe, könnte ich dies auch für alle anderen Bots manuell ausführen.
HyperNeutrino
1

TableBot, Python 2

Bezeichnet TableBot, weil es durch Implementierung dieser Tabelle erstellt wurde:

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 bedeutet 1 oder mehr, A 0 bedeutet keine.

Der 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

Probieren Sie es online!

Genosse SparklePony
quelle
1

AmbBot - Schlägersystem

Ich wollte es meistens ausprobieren amb, weil es cool ist. Dieser Bot ordnet die Optionen nach dem Zufallsprinzip an (neu laden, werfen und sich ducken), filtert diejenigen heraus, die keinen Sinn ergeben, und wählt die erste Option aus. Aber mit ambkönnen wir Fortsetzungen und Backtracking verwenden!

#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))))

Ich habe auch ein kleines Testprogramm erstellt, um zwei dieser Bots gegeneinander auszuführen. Es fühlt sich an, als würde der zweite Bot öfter gewinnen, also habe ich vielleicht irgendwo einen Fehler gemacht.

(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)))))))
Andrew sagt Reinstate Monica
quelle
1

MonteBot, C ++

Im Grunde genommen habe ich den Code von dieser Koth genommen und für diese Herausforderung modifiziert. Es verwendet den entkoppelten UCT-Monte-Carlo-Baumsuchalgorithmus. Es sollte ziemlich nahe am Nash-Gleichgewicht sein.

#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;
}

Kompilieranleitung für Linux:

Speichern in MonteBot.cpp.
Rennen g++ -o -std=c++11 MonteBot MonteBot.cpp.

Befehl zum Ausführen: ./MonteBot <args>

Die Nummer eins
quelle
1

Der Zauderer - Python 3

Der Zauderer wird zögern, indem er die ersten paar Runden spielt. Plötzlich will das Panikmonster vermeiden, den Ressourcenkrieg zu verlieren, indem es den am häufigsten verwendeten Zug des Gegners kontert.

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())
erbsenhirn
quelle
"Der Zauderer". Also, jeder bei PPCG, der eigentlich Hausaufgaben machen soll? (
Leugnen
1
"Instant Gratification Monkey" Du hast das TEDTalk auch gesehen? :)
HyperNeutrino
0

ParanoidBot und PanicBot - ActionScript3 ( RedTamarin )

Aus einer unpassenden Nischensprache (mit Erweiterungen zur Bereitstellung von Befehlszeilenargumenten) stammt der skittische ParanoidBot und sein langweiliger Verbündeter PanicBot.

ParanoidBot

ParanoidBot verliert den Verstand und hat eine unnötig spezifische Strategie, auf die man sich verlassen kann. Zuerst werden Schneebälle abgefeuert, bis eine Schwelle erreicht ist, wobei einige davon in Reserve bleiben. Dann, nach drei vorsichtigen Enten, setzt Paranoia ein und der Bot versucht, mehr Schneebälle zwischen zufälligen Enten zu lagern. Nachdem ParanoidBot seinen Vorrat aufgefüllt hat, kehrt er zum Blindwerfen zurück. An den Stimmen in seinem Kopf erkennt ParanoidBot, ob es garantiert gewinnt oder verliert, und "strategisiert" entsprechend.

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();
    }
}

Zahnspangen sind etwas wackelig, um die Größe zu reduzieren

PanicBot

PanicBot ist bereits verrückt geworden und reagiert aus instinktiver Angst. Nachdem PanicBot vor Angst keine Enten mehr hat, wirft er blind alle seine Schneebälle weg und wirft verzweifelt weitere Schneebälle, bis er (wahrscheinlich) besiegt ist.

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(); }



Dies ist einer von weniger als 15 anderen Einträgen, die AS3 hier auf PPCG verwenden. Vielleicht findet diese wohl exotische Sprache eines Tages ein Rätsel, das es zu lösen gilt.


quelle
Kann dies von Bash unter Linux ausgeführt werden?
HyperNeutrino
Ich habe das nicht getestet, aber ja, das sollte es. Die ausführbare RedTamarin-Datei (Redshell) wurde für Windows, Mac und Linux erstellt: http://redtamarin.com/tools/redshell . Wenn einer der obigen Bots in einer Datei mit dem Namen gespeichert wird snow.as, sollte in bash Folgendes funktionieren:$ ./redshell snow.as -- 0 50 50 25 25
Es gibt mir eine Erlaubnis verweigert Fehler, wenn ich versuche, dies auszuführen.
HyperNeutrino
@HyperNeutrino chmod +x redshellist dein Freund hier ...
Erik der Outgolfer
Vielleicht chmod 777 alles? Möglicherweise gibt es auch auf der RedTamarin-Website eine Fehlerbehebung
0

Verteidiger, Python

Lädt nach, wenn keiner der Spieler Schneebälle hat. Wenn es Schneebälle hat, wirft es. Wenn er keine Schneebälle hat, aber der Gegner, duckt er sich, wenn er kann, sonst lädt er nach.

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:]]))

Hinweis: noch nicht getestet

Solomon Ucko
quelle