Снежок Бой Кот!

35

Результаты (22 мая 2017 21:40:37 UTC)

Masterвыиграл 18 раундов, проиграл 2 раунда и
Save Oneвыиграл 0 раундов, выиграл 15 раундов, проиграл 3 раунда и
Machine Gunвыиграл 2 раунда, выиграл 14 раундов, проиграл 3 раунда и
Monte Botвыиграл 3 раунда, выиграл 14 раундов, проиграл 3 раунда и
Amb Botвыиграл 3 раунда, выиграл 12 раундов, проиграл 8 раундов, и 0 раундов
Cowardвыиграл 11 раундов, проиграл 3 раунда, 6 раундов
Pain in the Nashвыиграл 11 раундов, потерял 9 раундов, и 0 раундов
Nece Botвыиграл 10 раундов, проиграл 7 раундов, а 3 раунда
Naming Things is Hardвыиграл 10 раундов, проиграл 7 раундов и сыграл в три раунда,
The Procrastinatorвыиграл 10 раундов, проиграл 8 раундов, проиграл 2 раунда,
Yggdrasilвыиграл 10 раундов, проиграл 10 раундов и сыграл в сетку 0 раундов,
Simple Botвыиграл 9 раундов, проиграл 4 раунда, и сыграл в 7 раундов,
Table Botвыиграл 9 раундов, потерял 6 раундов и 5 раундов
Prioritized Random Botвыиграл 8 раундов, проиграл 7 раундов и 5 раундов
Upper Hand Botвыиграл 7 раундов, проиграл 13 раундов и
Aggressorвыиграл 0 раундов, выиграл 6 раундов, проиграл 10 раундов и
Insaneвыиграл 4 раунда, выиграл 5 раундов, проиграл 15 раундов и сыграл 0 раундов,
The Ugly Ducklingвыиграл 4 раунда, проиграл 16 раундов и
Know Botвыиграл 0 раундов 3 раундов, проиграв 14 раундов и сыграв в 3 раунда,
Paranoid Botвыиграл 0 раундов, проиграл 19 раундов и 1 раунда
Panic Botвыиграл 0 раундов, проиграл 19 раундов и связал 1 раунд

К сожалению, я не смог протестировать The Crazy X-Code Randomess, потому что не могу запустить его из bash на Linux. Я включу его, если смогу заставить его работать.

Полный выход контроллера


Игра

Это очень простая игра KoTH. Это снежный бой один на один. У вас есть изначально пустой контейнер, который может вместить kснежки. Вы можете уклониться от jвремени. Каждый ход обоим игрокам предлагается одновременно выбирать, какой ход делать. Есть три хода:

  • перезагрузка: дает вам еще один снежный ком (до k)
  • throw: бросает снежный ком, который убьет другого игрока, если он решит перезагрузить. Если оба игрока бросают снежный ком, никто не умирает (у них такая хорошая цель, что они бьют друг друга снежками)
  • утка: ничего не делает и избегает попадания, если другой игрок бросает снежок. Если у вас больше не осталось уток, то ничего не происходит, и если другой игрок бросает снежок, вы умрете.

Задача

Не умирай

Challlenge Технические характеристики

Ваша программа может быть написана на любом языке. Вы должны принять каждую из этих переменных в качестве аргумента при каждом выполнении:

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

turn- сколько ходов прошло ( 0на первой итерации)
snowballs- сколько снежков у вас есть
opponent_snowballs- сколько снежных комов у противника
ducks- сколько еще раз вы можете прыгнуть
opponent_ducks- сколько еще раз противник может прыгнуть
max_snowballs- максимальное количество снежных комов вы можете магазин ( k)

Вывод ключевой функции должен быть 0для перезагрузки, 1для броска и 2для утки. Вы должны вывести свой ход, перевод строки завершен. Пожалуйста, не выводите недопустимые ходы, но контроллер очень устойчив и не сломается, если вы выводите недопустимые ходы (даже если ваш ход не является целым числом). Это должно быть завершено новой строкой, хотя. Если движение не включено [0, 1, 2], оно по умолчанию будет перемещено в 0. Победитель будет определен как игрок с наибольшим количеством побед в полном круговом турнире.

правила

Вы можете читать / записывать из / в один файл для хранения памяти между итерациями. Ваш бот будет размещен в своем собственном каталоге, чтобы не возникало конфликтов с именами файлов. Вы не можете изменить встроенные функции (такие как генератор случайных чисел). В первый раз это было довольно забавно , но больше не будет. Ваша программа не имеет права делать вещи, которые являются просто явным срывом выполнения. Применяются стандартные лазейки .

тестирование

Исходный код для контроллера можно найти здесь . Пример бега на нем: java Controller "python program1/test1.py" "python program2/test2.py" 10 5на 10 снежков и 5 уток.

судейство

Победитель будет определен путем выбора человека, получившего наибольшее количество побед после полного раунда. Пока это ничья, уберите всех людей, у которых больше нет побед. Затем повторяйте, пока один человек не победит. Стандарт судейства - 50 снежков и 25 уток.

С Днем Рождения!

РЕДАКТИРОВАТЬ : Игра будет объявлена ​​ничья, если 1000 раундов проходит. Ваш бот может предположить, что turn < 1000.

HyperNeutrino
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Денис
@HyperNeutrino Еще вопросы: я думал, что «стандарт судейства» будет 50 снежками и 25 утками? И почему иногда происходит ничья после ~ 18 раундов?
CommonGuy
@Manu Ehh дерьмо я забыл изменить настройки в аргументах моей виртуальной машины. А также, потому что, если они попадают в бесконечный цикл столкновений снежного кома, это завершает его после 10 раундов повторения цикла период-1 или период-2.
HyperNeutrino
1
Итак, будет ли еще один раунд? Потому что я хочу загрузить своего бота и было бы интересно, насколько хорошо он будет работать.
Эрбсенгирн
@erbsenhirn Если вы загрузите бота и пингуете меня в чате или в «Девятнадцатом байте» , я проведу еще один прогон.
HyperNeutrino

Ответы:

13

Мастер, C #

Я тренировал небольшую нейронную сеть (используя Sharpneat ). Кажется, нравится собирать снежки и нырять ...

В предыдущей версии контроллера он даже обнаружил ошибку. Он пошел от 0% выигрыша до 100%, когда обнаружил, как выиграть, обманывая.

Изменить: я забыл сбросить внутреннее состояние сети и неправильно обучил сеть. Вновь обученная сеть намного меньше.

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
источник
Видимо, сброс состояния сети сделал производительность намного лучше :)
HyperNeutrino
Против чего ты тренировал нейронную сеть? Против других ботов, размещенных здесь?
JAD
@JarkoDubbeldam Да, я перенес несколько из них на C # и натренировал сеть против них. Вот почему он, вероятно, проиграет новым ботам.
CommonGuy
Или просто обучите другую сеть против ботов и эту: p
JAD
Wat. 8 голосов за нейронную сеть!
Кристофер
6

Сохранить один, Python

Немедленно выбрасывает большинство снежных комов, но всегда спасает их, если противник наблюдает за отсутствием патронов. Затем он уклоняется как можно дольше (опять же, сохраняя 1) перед перезагрузкой, если нет гарантированной безопасной перезагрузки или гарантированного уничтожения.

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
SnoringFrog
источник
2
если у вас 0 снежков, он попытается бросить 1
Карл Бош
@CarlBosch, который должен быть невозможным, чтобы достичь состояния (кроме начала с 0), но я все
равно
2
@SnoringFrog, чтобы уточнить правила, вы начинаете с 0 снежков
PhiNotPi
@PhiNotPi Должно быть, я полностью упустил это. Спасибо за разъяснения
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);
        }
    }
}

Этот бот выбирает случайное целое число в диапазоне 0до os + od, а затем выбирает бросок, уток или перезагрузку, с порогами, определяемыми его текущим количеством снежков и уток.

Важно понимать, что если у одного бота больше снежков, чем у другого - снежки + утки, вы можете выиграть. Отсюда можно придумать понятие «очки»:

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

Если любое из этих чисел становится положительным, то этот игрок может выиграть.

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

Таблица «разница в очках» составляет основу теории игр для этого соревнования. Он не совсем фиксирует всю информацию, но показывает, что снежки в основном ценнее уток (так как снежки - это и нападение, и защита). Если противник бросает снежный ком, и вы успешно уклоняетесь, то вы на один шаг ближе к насильственной победе, поскольку ваш противник израсходовал более ценный ресурс. В этой таблице также описано, что вам следует делать во многих особых случаях, например, когда определенные варианты перемещения недоступны.

Таблица «сумма очков» показывает, как со временем сумма очков приближается к нулю (когда у обоих игроков заканчиваются утки), и в этот момент первый игрок, совершивший ошибку (перезагружается, когда им это не нужно), немедленно проигрывает.

Теперь давайте попробуем распространить эту стратегию форсирования на случаи, когда она на самом деле не является насильственной (например, мы выигрываем с большим отрывом, но чтение мыслей со стороны оппонента нас побьет). В основном, у нас есть sснежные комья, но нам нужно время для того, чтобы выиграть у нашего оппонента s+1(или s+2и т. Д.). В этом случае мы хотим либо выполнить несколько уток, либо несколько перезагрузок, чтобы выиграть себе время.

Прямо сейчас, этот бот всегда пытается прокрасться в некоторых утках, просто потому, что тогда он не рискует немедленной потерей: мы предполагаем, что противник придерживается аналогичной стратегии, выпуская как можно больше снежков, поэтому попытка перезагрузки действительно опасно. Кроме того, чтобы предотвратить предсказуемость, мы хотим использовать их в соответствии с равномерно-случайным распределением: вероятность уклонения связана с тем, сколько уток нам нужно выполнить относительно количества снежных комов, которые нам нужно бросить.

Если мы сильно проигрываем, и в этом случае s + d < os + odнам нужно подкрасться к некоторым перезагрузкам в дополнение к использованию всех наших уток, в этом случае мы хотим перезагрузить случайно, но только столько раз, сколько нам нужно.

Вот почему наши боты расставляют приоритеты в порядке броска, утки и перезагрузки и используют os + odдля генерации случайного числа, поскольку это пороговое число ходов, которое нам нужно сделать.

Есть один крайний случай и два других особых случая, которые в данный момент обрабатывает бот. Крайний случай - когда у противника нет ни снежков, ни уток, и поэтому рандомизация не работает, поэтому мы бросаем, если возможно, в противном случае мы перезагружаемся. Еще один особый случай - когда противник не может перезарядиться, и поэтому нет смысла бросать (так как противник будет либо уклоняться, либо бросать), поэтому мы всегда уклоняемся (поскольку спасение наших снежных комов более ценно, чем спасение наших уток). Последний особый случай - если у противника нет снежных комов, в этом случае мы берем его на себя и перезагружаем, если это возможно.

PhiNotPi
источник
Это может привести к печати нескольких номеров, которые могут работать неправильно.
HyperNeutrino
@HyperNeutrino Я забыл добавить блок "else", когда переписал этого бота с использованием возвратов в операторы печати.
PhiNotPi
1
@HyperNeutrino Это сделало для меня, и я посчитал, что это прослушивается ...
Эрик Outgolfer
Ах. Да, извините, что испортил ваш код: P Но хорошая, первая программа, которая использует случайность!
HyperNeutrino
6

NeceBot - Python

Вот таблица теории игр для игры:

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

Где ~означает отсутствие преимущества, Wэто победа, Lпроигрыш, +-Sозначает, что снежный ком получен / потерян над противником, и +-Dозначает, что утка получена / потеряна над противником. Это абсолютно симметричная игра.

Обратите внимание, что мое решение не учитывает эту таблицу. Потому что я плохо разбираюсь в математике.

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

Он называется NeceBot, потому что он сначала пытается уменьшить то, что необходимо. После этого у него есть несколько произвольных стратегий, которые, я надеюсь, сработают.

Artyer
источник
4
Где так много <3с лол. +1 за то, что у вас есть игровой стол, а затем он не используется: P Но хорошее решение :)
HyperNeutrino
3 + opponent_snowballs <3это может быть ошибкой?
PhiNotPi
@PhiNotPi Да. Имеется в виду 2. Исправлено сейчас, спасибо!
Artyer
К сожалению, большое количество <3s делает код довольно сложным для понимания :(
CalculatorFeline
5

Трус - Скала

Броски, если у противника нет боеприпасов, в противном случае (в порядке приоритета) уток, бросок или перезарядка.

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
источник
Похоже, это заклинило моего бота ...
Эрик Аутгольфер
5

TheUglyDuckling - Python

Всегда будет прятаться, пока не сможет бросить, если противник пуст, или перезагрузить, если оба пусты. Будет использовать перезагрузку в качестве последнего средства.

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
источник
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

Простые вещи.

  • Если у противника снежки, а у вас утки, значит, вы утки.
  • Если у противника нет снежных комов, а у вас есть, то вы бросаете.
  • В любом другом случае вы перезагрузите.
Эрик Аутгольфер
источник
5

Бот, который называет вещи сложными - VB.NET

Назвать вещи сложно, и я не уверен, что у меня есть сплоченная стратегия, чтобы назвать это.

Пытается сыграть в первые несколько раундов, чтобы одержать раннюю победу. После этого играет безопаснее остальное время, пытаясь победить путем истощения.

Module SnowballFight

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

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

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

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

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

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

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

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

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

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

End Module
Брайан Дж
источник
5

Пулемет, Питон 3

Пытается накопить снежные комья, пока не будет гарантированно убит противник или пока он не выйдет из уток (В этом случае он начинает вслепую стрелять всеми своими снежными комьями, как пулемет)

Он также уклоняется всякий раз, когда у противника есть снежный ком, потому что он не хочет умирать.

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
источник
5

Knowbot, Python3

Отслеживает частоту предыдущих ходов, предполагает, что противник сделает самый повторный ход, защищается от этого.

** Обновлено, чтобы не ожидать ходов, которые противник не может сделать **

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);
AShelly
источник
Я не уверен, как именно это работает, но если он хранит данные между раундами (в отличие от поворотов), к сожалению, все данные удаляются между раундами. Это не обесценит ваше решение, но просто помните об этом :)
HyperNeutrino
Он не ожидает сохранения данных между раундами, просто ожидает, что текущий противник будет последовательным.
AShelly
Хорошо. Хорошо. Я просто хотел убедиться, что не было неправильных представлений. :)
HyperNeutrino
4

Брайнгольф , Агрессор

<<?1:0

Агрессор не трус! Если у него снежный ком, он бросит! Если у него нет снежков, он сделает больше!

Braingolf , Безумный

На самом деле это не бот, а просто программист, которого я похитил и заставил переносить каждый проект, который он когда-либо делал, в Braingolf. У него больше нет клочка здравомыслия.

<3r!?:1+|%

Генерирует случайное число меньше 3 и выдает, t % rгде t - текущий поворот, а r - случайное число

Чтобы запустить их, вам нужно скачать braingolf.pyс github, а затем либо сохранить код Braingolf в файл и запустить

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

или просто вставьте код прямо так

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

Входные данные довольно неактуальны, поскольку второй аргумент после кода / имени файла - это количество снежных комов, которые имеет Агрессор.

Примечание: агрессор фактически ведет себя идентично TestBot, я просто хотел сделать запись в Braingolf

Braingolf , The Brainy [ сломано прямо сейчас]

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
источник
Конечно, кто-то должен был сделать это: D Хорошо, и даже в гольф! : D
HyperNeutrino
Ой, подождите, это так же, как у меня, кроме Gofier. LOL
HyperNeutrino
@HyperNeutrino Да, я сейчас работаю над реальным языком. Я бы использовал Braingolf для реального, но он не может выполнять вложенные условные
выражения
2
Я думаю, что вы должны опубликовать «Мозговой» в качестве отдельного ответа. Кроме того, я думаю, что это ошибается.
Эрик Аутгольфер,
«The Insane» не является стабильным ботом, поэтому я не уверен, как @HyperNeutrino проверит его.
Эрик Аутгольфер,
3

TestBot - Python

Это тестовое представление, чтобы показать вам, как может выглядеть действительное представление. Стратегия: Альтернативная перегрузка и бросание. Довольно плохая стратегия, но она дает вам представление о том, как ваша программа должна работать.

from os import sys
arguments = sys.argv;
turn = int(arguments[1])
print(turn % 2)
HyperNeutrino
источник
Будут _, turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = sys.argvли аргументы?
Artyer
@ Артье Да. Оказывается, первый аргумент имеет имя файла.
HyperNeutrino
Вы можете просто использовать, sys.argv[1:]если вы не хотите возиться с этим_
sagiksp
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)

Этот бот пытается собрать больше снежков, чем его противник, и в этот момент начинает бросать. Если в любой момент UHB не имеет больше снежных комов, чем его противник, он будет:

  • Утка, если у противника есть снежки, и у него остались утки
  • В противном случае перезагрузите компьютер (если UHB не достигает максимума, вместо этого он выбрасывает, хотя я не думаю, что такая ситуация когда-либо возникнет)
Бизнес Кот
источник
2

Иггдрасли, Ява

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

Я назвал этого бота "Yggdrasil", потому что он на самом деле смотрит вниз по дереву игры и выполняет оценку состояния, из которой он может вычислить приблизительно идеальную смешанную стратегию. Поскольку он опирается на смешанные стратегии, он очень недетерминирован. Я не знаю, насколько хорошо это будет сделано в реальной конкуренции.

Несколько вещей об этом боте:

  • Ядро представляет собой рекурсивную функцию, которая вычисляет значение и почти идеальную смешанную стратегию для любого конкретного игрового состояния. Сейчас я настроен на 4 шага вперед.
  • Он играет крайне дерьмово, так как во многих случаях этот бот эквивалентен «выбору случайного хода каменными ножницами». Он сохраняет свою позицию и надеется, что его противник дает ему статистическое преимущество. Если бы этот бот был идеальным (а это не так), лучшее, что вы могли бы сделать против него, это 50% побед и 50% потерь. В результате, нет противника, которого он постоянно побеждает, но и нет того, кому он последовательно проигрывает.
PhiNotPi
источник
Я до сих пор не понимаю имя ...: P
HyperNeutrino
@HyperNeutrino Yggdrasil - это мифологическое дерево, и в данном случае я имею в виду дерево игр.
PhiNotPi
Оооо верно, я чувствую, что должен был вспомнить это. : P Здорово!
HyperNeutrino
2

Боль в Нэше (C ++)

Так назвали, потому что факт, что я должен был написать свой собственный решатель равновесия Нэша, был настоящей болью. Я поражен, что нет никаких доступных библиотек, решающих Nash!

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

Компилировать как C ++ 11 или лучше. Для производительности хорошо скомпилировать с поддержкой OpenMP (но это только для скорости; это не обязательно)

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

Это использует равновесия Нэша, чтобы решить, что делать на каждом ходу, что означает, что в теории он всегда будет выигрывать или выигрывать в долгосрочной перспективе (в течение многих игр), независимо от того, какую стратегию использует противник. Будет ли это на практике, зависит от того, допустил ли я какие-либо ошибки в реализации. Однако, так как в этом соревновании KoTH есть только один раунд против каждого оппонента, он, вероятно, не будет очень хорошо в таблице лидеров.

Моя первоначальная идея состояла в том, чтобы иметь простую функцию оценки для каждого игрового состояния (например, каждый шар стоит + b, каждая утка + d), но это приводит к очевидным проблемам с определением того, какими должны быть эти оценки, и означает, что это не может действовать на уменьшение отдачи, собирая все больше и больше шаров и т. д. Таким образом, вместо этого будет проанализировано все игровое дерево , работающее в обратном направлении, начиная с хода 1000, и заполнены фактические оценки, основанные на том, как каждая игра может получиться.

В результате я понятия не имею, какую стратегию он использует, за исключением пары жестко закодированных «очевидных» действий (бросайте снежки, если у вас больше мячей, чем у вашего противника, шары + утки, и перезагружайте, если вы оба выбываете) снежки). Если кто-то хочет проанализировать набор данных, который он производит, я думаю, что есть интересное поведение, которое нужно обнаружить!

Тестирование против «Save One» показывает, что он действительно выигрывает в долгосрочной перспективе, но только с небольшим отрывом (514 побед, 486 поражений, 0 ничьих в первой партии из 1000 игр и 509 побед, 491 поражение, 0 рисует во втором).


Важный!

Это будет работать из коробки, но это не очень хорошая идея. На моем ноутбуке с умеренной спецификацией требуется около 9 минут, чтобы создать полное дерево игр. Но он сохранит окончательные вероятности в файле, как только они будут сгенерированы, и после этого каждый ход просто генерирует случайное число и сравнивает его с 2 байтами, так что это супер-быстро.

Чтобы сократить все это, просто загрузите этот файл (3,5 МБ) и поместите его в каталог с исполняемым файлом.

Или вы можете создать его самостоятельно, запустив:

./pain_in_the_nash 1000 50 25

Который будет сохранять один файл за ход, до схождения. Обратите внимание, что каждый файл имеет размер 3,5 МБ, и он будет сходиться на повороте 720 (то есть 280 файлов, ~ 1 ГБ), и, поскольку большинство игр не приближаются к повороту 720, файлы предварительной конвергенции имеют очень низкую важность.

Дейв
источник
Можно ли заставить программу выводить только конечный результат? Благодарность!
HyperNeutrino
@HyperNeutrino все остальные выходные данные должны быть в stderr, поэтому не должны иметь никакого влияния, но я обновил его, чтобы он отображал только прогресс при работе в режиме предварительной обработки. Теперь он будет писать только в стандартный вывод при нормальной работе. Тем не менее, я предлагаю следовать «важному» предложению, так как в противном случае он будет просто зависать на первом повороте в течение нескольких минут (по крайней мере, при предварительной обработке вы сможете увидеть прогресс).
Дейв
Ох, ну ладно. Я последую этому предложению, спасибо!
HyperNeutrino
Я был бы признателен, если бы вы могли загрузить файлы данных, потому что на их создание уходит целая вечность. Если бы вы могли это сделать, это было бы здорово :)
HyperNeutrino
@HyperNeutrino Хорошо, загрузка в моем ужасном Интернете заняла целую вечность, но конвергентный файл размером 3,5 МБ доступен здесь: github.com/davidje13/snowball_koth_pitn/blob/master/… (просто поместите его в тот же каталог).
Дейв
1

Свифт - TheCrazy_XcodeRandomness

К сожалению, это может быть выполнено только локально, в Xcode, потому что он содержит Foundationмодуль и его функцию arc4random_uniform(). Тем не менее, вы можете в значительной степени сказать, что алгоритм:

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
}
Мистер Xcoder
источник
Это можно запустить из bash в Linux?
HyperNeutrino
@ HyperNeutrino Я знаю, что это возможно в macOS, но я не знаю, работает ли это в Linux. Если вы можете проверить это, было бы здорово. Попробуйте swiftкоманду, а затем проверьте, работает ли она
Mr. Xcoder
Похоже, не существует; с ним есть пакет, но это не язык Swift. Так что я не могу проверить это, пока не получу что-нибудь работающее, извините.
HyperNeutrino
единственными возможными компиляторами являются Xcode и IntelliJ, но он не может быть запущен онлайн из-за Foundation, извините: /
Mr. Xcoder
Покойся с миром. Мне нужно было бы иметь возможность запустить его из командной строки, чтобы запустить контроллер с ним, но если у меня будет время, я мог бы вручную запустить это снова все остальные боты.
HyperNeutrino
1

TableBot, Python 2

Вызывается TableBot, потому что он был создан путем реализации этой таблицы:

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

1 обозначает наличие 1 или более, 0 обозначает отсутствие.

Бот:

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

Попробуйте онлайн!

Товарищ Спаркл Пони
источник
1

AmbBot - Схема ракеток

Я в основном хотел попробовать amb, потому что это круто. Этот бот случайным образом упорядочивает параметры (перезагрузить, выбросить и сбросить), отфильтровывает те, которые не имеют смысла, и выбирает первый вариант. Но с помощью ambмы получаем использование продолжения и возврата!

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

Я также создал небольшую тестовую программу для запуска двух этих ботов друг против друга. Такое чувство, что второй бот побеждает чаще, так что, возможно, я где-то допустил ошибку.

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

(define (run-helper turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (printf "~a ~a ~a ~a ~a ~a ~n" turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs)
  (let ((my-action (make-choice turn snowballs opponent_snowballs ducks opponent_ducks max_snowballs))
        (opponent-action (make-choice turn opponent_snowballs snowballs opponent_ducks ducks max_snowballs)))
    (cond ((= my-action reload)
           (cond ((= opponent-action reload)
                  (run-helper (+ turn 1) (+ snowballs 1) (+ opponent_snowballs 1) ducks opponent_ducks max_snowballs))
                 ((= opponent-action throw)
                  (writeln "Opponent wins!"))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) (+ snowballs 1) opponent_snowballs ducks (- opponent_ducks 1) max_snowballs))))
          ((= my-action throw)
           (cond ((= opponent-action reload)
                  (writeln "I win!"))
                 ((= opponent-action throw)
                  (run-helper (+ turn 1) (- snowballs 1) (- opponent_snowballs 1) ducks opponent_ducks max_snowballs))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) (- snowballs 1) opponent_snowballs ducks (- opponent_ducks 1) max_snowballs))))
          ((= my-action duck)
           (cond ((= opponent-action reload)
                  (run-helper (+ turn 1) snowballs (+ opponent_snowballs 1) (- ducks 1) opponent_ducks max_snowballs))
                 ((= opponent-action throw)
                  (run-helper (+ turn 1) snowballs (- opponent_snowballs 1) (- ducks 1) opponent_ducks max_snowballs))
                 ((= opponent-action duck)
                  (run-helper (+ turn 1) snowballs opponent_snowballs (- ducks 1) (- opponent_ducks 1) max_snowballs)))))))
Эндрю говорит восстановить Монику
источник
1

MonteBot, C ++

Я в основном взял код из этого кота и изменил его для этой задачи. Он использует алгоритм поиска дерева Монте-Карло в разложенном виде. Это должно быть довольно близко к равновесию Нэша.

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

Инструкция по компиляции для Linux:

Сохранить в MonteBot.cpp.
Беги g++ -o -std=c++11 MonteBot MonteBot.cpp.

Команда для запуска: ./MonteBot <args>

Номер один
источник
1

Прокрастинатор - Python 3

Промедлитель откладывает игру, сохраняя первые пару ходов. Внезапно панический монстр хочет избежать проигрыша в войне за ресурсы, противодействуя наиболее часто используемому ходу противников.

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
источник
"Прокрастинатор". Итак, все на PPCG, кто на самом деле должен делать домашнюю работу? (Не отрицайте это, люди, которые читают это. И я)
HyperNeutrino
1
"Обезьяна мгновенного удовлетворения" Вы тоже видели этот TEDTalk? :)
HyperNeutrino
0

ParanoidBot и PanicBot - ActionScript3 ( RedTamarin )

Из неподходящего нишевого языка (с расширениями для обеспечения аргументов командной строки) приветствуется хитрый ParanoidBot и его скучный союзник PanicBot.

ParanoidBot

ParanoidBot сходит с ума и имеет совершенно ненужную стратегию, от которой зависит. Во-первых, он запускает снежки до тех пор, пока не будет достигнут порог, оставляя некоторые в запасе. Затем, после трех предостерегающих уток, начинается паранойя, и бот пытается накапливать больше снежных комов между случайными утками. После пополнения запаса ParanoidBot возвращается к слепому броску. Из-за голоса в его голове, ParanoidBot может сказать, гарантированно он выиграет или проиграет, и будет соответствующим образом «разрабатывать стратегию».

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

Брекеты немного шаткие, чтобы уменьшить размер

PanicBot

Уже сойдя с ума, PanicBot реагирует из-за инстинктивного страха. После того, как утки утекли от страха, PanicBot вслепую бросает все свои снежные комья, затем отчаянно делает и бросает больше снежных комов, пока (вероятно) не победит.

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



Это одна из менее чем 15 других записей, использующих AS3 здесь на PPCG. Однажды, возможно, этот, возможно, экзотический язык найдет загадку для доминирования.


источник
Это можно запустить из bash в Linux?
HyperNeutrino
Я этого не проверял, но да, так и должно быть. Исполняемый файл RedTamarin (redshell) создан для Windows, Mac и Linux: http://redtamarin.com/tools/redshell . Если один из приведенных выше ботов сохранен в файле с именем snow.as, в bash должно работать следующее:$ ./redshell snow.as -- 0 50 50 25 25
Это дает мне ошибку «Отказано в разрешении», когда я пытаюсь запустить это.
HyperNeutrino
@HyperNeutrino chmod +x redshellтвой друг здесь ...
Эрик Outgolfer
Может быть, chmod 777 все? На веб-сайте RedTamarin могут быть некоторые неполадки
0

Защитник, Питон

Перезагрузка, когда ни у одного из игроков нет снежков. Если у него есть снежки, он бросает. Если у него нет снежных комов, но у противника есть, он уклоняется, если может, иначе перезагружается.

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

Примечание: еще не проверено

Соломон Уцко
источник