Snowball Fight KoTH!

35

Wyniki (22 maja 2017 21:40:37 UTC)

Masterwygrał 18 rund, przegrał 2 rundy i remis 0 rund
Save Onewygrał 15 rund, przegrał 3 rundy i remis 2 rund
Machine Gunwygrał 14 rund, przegrał 3 rundy i remis 3 rundy
Monte Botwygrał 14 rund, przegrał 3 rundy i remis 3 rund
Amb Botwygrał 12 rundy, przegrał 8 rund i remis 0 rund
Cowardwygrał 11 rund, przegrał 3 rundy, remis 6 rund
Pain in the Nashwygrał 11 rund, przegrał 9 rund, a remis 0 rund
Nece Botwygrał 10 rund, przegrał 7 rund, a remis 3 rund
Naming Things is Hardwygrał 10 rund, przegrał 7 rund, a remis 3 rund
The Procrastinatorwygrał 10 rund, przegrał 8 rund, remis 2 rund
Yggdrasilwygrał 10 rund, przegrał 10 rund, a remis 0 rund
Simple Botwygrał 9 rund, przegrał 4 rundy, a remis 7 rund
Table Botwygrał 9 rund, przegrał 6 rundy i remis 5 rund
Prioritized Random Botwygrał 8 rund, przegrał 7 rund i remis 5 rund
Upper Hand Botwygrał 7 rund, stracił 13 rund i remis 0 rund
Aggressorwygrał 6 rund, przegrał 10 rund i remis 4 rund
Insanewygrał 5 rund, przegrał 15 rund, a remis 0 rund
The Ugly Ducklingwygrał 4 rundy, przegrał 16 rund, a remis 0 rund
Know Botwygrał 3 rundy, przegrane 14 rund i remis 3 rund,
Paranoid Botwygrane 0 rund, przegrane 19 rund, a remis 1 rundy,
Panic Botwygrane 0 rund, przegrane 19 rund i remis 1 rundy

Niestety nie mogłem przetestować Szalonego losowego kodu X, ponieważ nie mogę go uruchomić z Linuksa. Uwzględnię go, jeśli uda mi się go uruchomić.

Pełna moc wyjściowa kontrolera


Gra

To bardzo prosta gra KoTH. To pojedynek na śnieżki jeden na jednego. Masz początkowo pusty pojemnik, który może pomieścić kśnieżki. Możesz uchylać się do jczasów. W każdej turze obaj gracze proszeni są jednocześnie o wybór sposobu wykonania ruchu. Istnieją trzy ruchy:

  • reload: daje kolejną śnieżkę (do k)
  • rzut: rzuca śnieżką, która zabije drugiego gracza, jeśli zdecyduje się go przeładować. Jeśli obaj gracze rzucą śnieżką, nikt nie umiera (mają tak dobry cel, że trafią się śnieżkami)
  • Kaczka: nic nie robi i unika trafienia, jeśli inny gracz rzuci śnieżną kulą. Jeśli nie masz już kaczek, nic się nie dzieje, a jeśli inny gracz rzuci śnieżną kulą, giniesz.

Cel

Nie umieraj

Specyfikacje wyzwania

Twój program może być napisany w dowolnym języku. Każdą z tych zmiennych należy traktować jako argument przy każdym wykonaniu:

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

turn- ile tur minęło ( 0przy pierwszej iteracji)
snowballs- ile masz śnieżek
opponent_snowballs- ile śnieżek ma przeciwnik
ducks- ile razy możesz uchylić się
opponent_ducks- ile razy przeciwnik może uchylić się
max_snowballs- maksymalna liczba śnieżek store ( k)

Wyjście kluczowej funkcji powinno być 0do przeładowania, 1do rzutu i 2do kaczki. Musisz wyprowadzić swój ruch, nowa linia została zakończona. Nie wysyłaj nieprawidłowych ruchów, ale kontroler jest bardzo odporny i nie zepsuje się, jeśli wyślesz nieprawidłowe ruchy (nawet jeśli twój ruch nie jest nawet liczbą całkowitą). To musi być zakończony znakiem nowej linii chociaż. Jeśli nie ma ruchu [0, 1, 2], domyślnie zostanie on przeniesiony do 0. Zwycięzca zostanie wyłoniony jako gracz, który uzyska najwięcej zwycięstw w pełnym turnieju round-robin.

Zasady

Możesz czytać / zapisywać z / do jednego pliku w celu przechowywania w pamięci między iteracjami. Twój bot zostanie umieszczony we własnym katalogu, aby konflikty nazw plików nie wystąpiły. Nie można zmieniać wbudowanych funkcji (takich jak generator losowy). To było dość zabawne za pierwszym razem , ale już nie będzie. Twój program nie może robić rzeczy, które są po prostu rażącym opóźnieniem wykonania. Obowiązują standardowe luki .

Testowanie

Kod źródłowy kontrolera można znaleźć tutaj . Przykład uruchomienia: java Controller "python program1/test1.py" "python program2/test2.py" 10 5na 10 śnieżek i 5 kaczek.

Osądzać

Zwycięzca zostanie wyłoniony przez wybranie osoby, która uzyska najwięcej zwycięstw po pełnej rundzie. Chociaż jest to remis, usuń wszystkich ludzi, którzy nie mają najwięcej wygranych. Następnie powtarzaj, aż jedna osoba wygra. Standardem oceny będzie 50 śnieżek i 25 kaczek.

Happy KoTHing!

EDYCJA : Gra zostanie uznana za remis, jeśli przejdzie 1000 rund. Twój bot może to założyć turn < 1000.

HyperNeutrino
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Dennis
@HyperNeutrino Więcej pytań: Myślałem, że „standardem oceny” byłoby 50 śnieżek i 25 kaczek? I dlaczego czasami następuje remis po ~ 18 rundach?
CommonGuy
@Manu Ehh bzdura Zapomniałem zmienić ustawienia w moich argumentach VM. A także dlatego, że jeśli wejdą w niekończącą się pętlę kolizji śnieżki, kończy się to po 10 rundach powtarzania pętli okresu 1 lub okresu 2.
HyperNeutrino
1
Czy będzie kolejna runda? Bo chcę załadować mojego bota i byłbym ciekawy, jak dobrze by działał.
erbsenhirn
@erbsenhirn Jeśli załadujesz bota i wyślesz mi ping na czacie lub w The Nineteenth Byte , a ja uruchomię kolejny bieg.
HyperNeutrino

Odpowiedzi:

13

Master, C #

Trenowałem małą sieć neuronową (używając Sharpneat ). Wydaje się, że lubisz podnosić śnieżki i schować się ...

W poprzedniej wersji kontrolera nawet znalazł błąd. Z 0% wygrał do 100%, kiedy odkrył, jak wygrywać poprzez oszukiwanie.

Edycja: Zapomniałem zresetować stan interalu sieci i źle wyszkoliłem sieć. Nowo przeszkolona sieć jest znacznie mniejsza.

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
źródło
Najwyraźniej zresetowanie stanu sieci znacznie poprawiło wydajność :)
HyperNeutrino
Przeciw czemu trenowałeś sieć neuronową? Przeciw innym botom opublikowanym tutaj?
JAD
@JarkoDubbeldam Tak, przeniosłem kilka z nich do C # i przeszkoliłem sieć przeciwko nim. Dlatego prawdopodobnie przegra z nowymi botami.
CommonGuy
Lub po prostu wytrenuj kolejną sieć przeciwko botom i tej: p
JAD
Wat. 8 głosów na sieć neuronową!
Christopher
6

Save One, Python

Natychmiast rzuca większość śnieżek, ale zawsze ratuje jedną na wypadek, gdyby przeciwnik szukał amunicji. Następnie kacze tak długo, jak to możliwe (ponownie, oszczędzając 1) przed przeładowaniem, chyba że istnieje zagwarantowane bezpieczne przeładowanie lub zabójstwo.

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
źródło
2
jeśli masz 0 śnieżek, spróbuje rzucić 1
Carl Bosch
@CarlBosch, do którego osiągnięcie stanu powinno być niemożliwe (poza początkiem 0), ale i tak
dokonam
2
@SnoringFrog w celu wyjaśnienia zasad, zaczynasz od 0 śnieżek
PhiNotPi
@PhiNotPi Musiałem to całkowicie przeoczyć. Dzięki za wyjaśnienie
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);
        }
    }
}

Bot wybiera losowo liczbę całkowitą w zakresie 0do os + odi wybiera albo rzutu, kaczka lub wymianie z progów oznaczyć przez jego aktualnej liczbie kami i kaczki.

Jedną rzeczą, o której należy pamiętać, jest to, że gdy jeden bot ma więcej śnieżek niż drugi ma śnieżki + kaczki, możesz zmusić wygraną. Na tej podstawie możemy wymyślić pojęcie „punktów”:

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

Jeśli którakolwiek z tych liczb stanie się dodatnia, gracz ten może wymusić wygraną.

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

Tabela „Różnica punktów” stanowi podstawę teorii gier dla tego konkursu. Nie do końca przechwytuje wszystkie informacje, ale pokazuje, że śnieżki są zasadniczo cenniejsze niż kaczki (ponieważ śnieżki są zarówno atakiem, jak i obroną). Jeśli przeciwnik rzuci śnieżną kulą i uda ci się uchylić, jesteś o krok bliżej do wymuszonego zwycięstwa, ponieważ twój przeciwnik zużył cenniejsze zasoby. W tej tabeli opisano także, co należy zrobić w wielu specjalnych przypadkach, na przykład gdy niektóre opcje ruchu nie są dostępne.

Tabela „suma punktów” pokazuje, jak z biegiem czasu suma punktów zbliża się do zera (gdy obu graczom zabrakło kaczek), w którym momencie pierwszy gracz popełni błąd (przeładuje, gdy nie musiał) natychmiast przegrywa

Teraz spróbujmy rozszerzyć tę strategię wymuszania na przypadki, w których tak naprawdę nie jest to możliwe (na przykład, wygrywamy z dużym marginesem, ale czytanie myśli przez przeciwnika nas pokona). Zasadniczo mamy sśnieżki, ale musimy wygrywać śnieżkami przeciwnika s+1(lub s+2itd.), Aby wygrać. W takim przypadku chcemy wykonać kilka kaczek lub kilka przeładowań, aby kupić sobie trochę czasu.

W tej chwili ten bot zawsze próbuje się zakraść w niektórych kaczkach, po prostu dlatego, że nie ryzykuje natychmiastowej straty: zakładamy, że przeciwnik stosuje podobną strategię lobbowania jak największej liczby śnieżek, więc próba przeładowania jest naprawdę niebezpieczny. Ponadto, aby zapobiec przewidywalności, chcemy się do nich przekraść, postępując zgodnie z rozkładem równomiernie losowym: prawdopodobieństwo zanurkowania zależy od tego, ile kaczek musimy wykonać w stosunku do liczby śnieżek, które musimy rzucić.

Jeśli przegrywamy bardzo źle, w takim przypadku s + d < os + odmusimy podkraść się w niektórych przeładowaniach oprócz korzystania z wszystkich naszych kaczek, w tym przypadku chcemy przeładować losowo, ale tylko tyle razy, ile potrzebujemy.

Właśnie dlatego nasze boty ustalają priorytety w kolejności rzucania, uchylania się i przeładowywania oraz używają os + oddo generowania losowej liczby, ponieważ jest to progowa liczba ruchów, którą musimy wykonać.

Istnieje jeden przypadek krawędzi i dwa inne przypadki szczególne, które bot obecnie obsługuje. Przypadek skrajny ma miejsce, gdy przeciwnik nie ma śnieżek ani kaczek, a więc losowanie nie działa, więc rzucamy, jeśli to możliwe, w przeciwnym razie przeładowujemy. Innym szczególnym przypadkiem jest sytuacja, w której przeciwnik nie może przeładować, więc rzucanie nie ma żadnej korzyści (ponieważ przeciwnik będzie rzucał lub rzucał), więc zawsze uciekamy (ponieważ ratowanie naszych śnieżek jest cenniejsze niż ratowanie naszych kaczek). Ostatni szczególny przypadek dotyczy sytuacji, gdy przeciwnik nie ma śnieżek, w którym to przypadku gramy bezpiecznie i przeładowujemy, jeśli to możliwe.

PhiNotPi
źródło
Może to spowodować wydrukowanie wielu numerów, które mogą nie działać poprawnie.
HyperNeutrino
@HyperNeutrino Zapomniałem dodać bloku „else”, gdy przepisałem temu botowi używanie zwrotów do wypisywania instrukcji.
PhiNotPi
1
@HyperNeutrino Zrobił to dla mnie i uważałem, że jest zepsuty ...
Erik the Outgolfer
Ach Tak, przepraszam za zepsucie kodu: P Ale fajny, pierwszy program, który używa losowości!
HyperNeutrino
6

NeceBot - Python

Oto tabela teorii gry:

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

Gdzie ~oznacza, że ​​żadna przewaga, nie Wjest wygrana, Ljest przegrana, +-Soznacza , że śnieżka jest zdobywana / przegrywana nad przeciwnikiem, a +-Doznacza, że ​​kaczka jest zdobywana / tracona nad przeciwnikiem. To jest całkowicie symetryczna gra.

Pamiętaj, że moje rozwiązanie nie uwzględnia tej tabeli. Ponieważ jestem kiepski z matematyki.

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

Nazywa się NeceBot, ponieważ najpierw próbuje zmniejszyć to, co jest konieczne. Potem ma jakieś arbitralne strategie, które, mam nadzieję, zadziałają.

Artyer
źródło
4
Whee tylu <3s lol. +1 za posiadanie stołu do gry i nieużywanie go: P Ale fajne rozwiązanie :)
HyperNeutrino
3 + opponent_snowballs <3to może być pomyłka?
PhiNotPi
@PhiNotPi Tak. Ma być 2. Naprawiony teraz, dzięki!
Artyer
Niestety duża liczba <3s sprawia, że ​​kod jest trudny do zrozumienia :(
CalculatorFeline
5

Tchórz - Scala

Rzuca, jeśli przeciwnik nie ma amunicji, w przeciwnym razie (w kolejności pierwszeństwa) kaczki, rzuty lub przeładowania.

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
źródło
Wygląda na to, że to zacina mojego bota ...
Erik the Outgolfer
5

TheUglyDuckling - Python

Zawsze uchyla się, dopóki nie będzie mógł rzucić, jeśli przeciwnik jest pusty lub przeładować, jeśli oba są puste. Użyje przeładowania w ostateczności.

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
źródło
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

Proste rzeczy.

  • Jeśli przeciwnik ma śnieżki, a ty masz kaczki, to uciekasz.
  • Jeśli przeciwnik nie ma śnieżek, a ty masz, rzucasz.
  • W każdym innym przypadku przeładujesz.
Erik the Outgolfer
źródło
5

Bot Naming-Things-is-hard - VB.NET

Nazywanie rzeczy jest trudne i nie jestem pewien, czy mam spójną strategię, by to nazwać.

Próbuje zagrać przez kilka pierwszych rund, aby uzyskać wczesne zwycięstwo. Następnie gra bezpieczniej przez resztę czasu, próbując wygrać przez ścieranie.

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.
źródło
5

MachineGun, Python 3

Próbuje oszczędzać śnieżki, dopóki nie zabije przeciwnika lub nie wydostanie się z kaczek (w takim przypadku zaczyna ślepo strzelać wszystkimi śnieżkami, jak karabin maszynowy)

Kacze także, gdy przeciwnik ma śnieżkę, ponieważ nie chce umrzeć.

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
źródło
5

Knowbot, Python3

Śledzi częstotliwość poprzednich ruchów, zakłada, że ​​przeciwnik ponownie wykona najczęstszy, broni się przed tym.

** Zaktualizowano, aby nie oczekiwać ruchów, których przeciwnik nie może wykonać **

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
źródło
Nie jestem pewien, jak to dokładnie działa, ale jeśli przechowuje dane między rundami (w przeciwieństwie do zwojów), niestety wszystkie dane są usuwane między rundami. To nie unieważnia twojego rozwiązania, ale pamiętaj o tym :)
HyperNeutrino
Nie oczekuje się przechowywania danych między rundami, wystarczy oczekiwać, że obecny przeciwnik jest konsekwentny.
AShelly
W porządku. W porządku. Chciałem tylko upewnić się, że nie ma żadnych nieporozumień. :)
HyperNeutrino,
4

Braingolf , Agresor

<<?1:0

Agresor nie jest tchórzem! Jeśli ma śnieżkę, rzuci! Jeśli nie ma śnieżek, uczyni więcej!

Braingolf , Szalony

To nie jest bot, to tylko programista, którego porwałem i zmuszałem do przeniesienia każdego projektu, który kiedykolwiek zrealizował, do braingolfa. Nie ma już odrobiny rozsądku.

<3r!?:1+|%

Generuje liczbę losową mniejszą niż 3 i wysyła, t % rgdzie t jest bieżącą turą, a r jest liczbą losową

Aby je uruchomić, musisz pobrać braingolf.pyz github, a następnie zapisać kod braingolfa w pliku i uruchomić

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

lub po prostu wstaw kod bezpośrednio w ten sposób

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

Dane wejściowe są dość nieistotne, dopóki drugi argument po kodzie / nazwie pliku jest liczbą śnieżek, które posiada Aggressor.

Uwaga: agresor zachowuje się identycznie jak TestBot, chciałem tylko zrobić wpis w braingolfie

Braingolf , The Brainy [Broken now teraz]

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
źródło
Oczywiście ktoś musiał to zrobić: D Fajnie, a nawet grał w golfa! : D
HyperNeutrino
Och, czekaj, to jest to samo co moje, z wyjątkiem gofiera. lol
HyperNeutrino
@HyperNeutrino, tak, teraz pracuję nad prawdziwym w prawdziwym języku. Użyłbym Braingolfa naprawdę, ale nie potrafi zagnieżdżać warunkowych, więc to utrudnia
Skidsdev
2
Myślę, że powinieneś opublikować „The Brainy” jako osobną odpowiedź. Myślę też, że to popełni błąd.
Erik the Outgolfer
„The Insane” nie jest stabilnym botem, więc nie jestem pewien, jak by to sprawdził @HyperNeutrino.
Erik the Outgolfer
3

TestBot - Python

To jest przesłanie testowe, które pokazuje, jak może wyglądać prawidłowe zgłoszenie. Strategia: naprzemienne przeładowywanie i rzucanie. Zła strategia, ale daje wyobrażenie o tym, jak powinien działać Twój program.

from os import sys
arguments = sys.argv;
turn = int(arguments[1])
print(turn % 2)
HyperNeutrino
źródło
Czy _, turn, snowballs, opponent_snowballs, ducks, opponent_ducks, max_snowballs = sys.argvbyłyby argumenty?
Artyer
@Artyer Tak. Okazuje się, że pierwszy argument ma nazwę pliku.
HyperNeutrino
Możesz użyć, sys.argv[1:]jeśli nie chcesz z tym _
zadzierać
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)

Ten bot próbuje zebrać więcej śnieżek niż jego przeciwnik, i w tym momencie zaczyna rzucać. Jeśli w dowolnym momencie UHB nie ma więcej śnieżek niż jego przeciwnik, będzie:

  • Kaczka, jeśli przeciwnik ma śnieżki i pozostały kaczki
  • W przeciwnym razie przeładuj (chyba że UHB jest na maksimum, to zamiast tego rzuca, chociaż nie sądzę, że taka sytuacja kiedykolwiek by się pojawiła)
Business Cat
źródło
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;
        }
    }
}

Nazwałem tego bota „Yggdrasil”, ponieważ tak naprawdę spogląda on w dół drzewa gry i dokonuje oceny stanu, na podstawie której może obliczyć w przybliżeniu idealną strategię mieszaną. Ponieważ opiera się na strategiach mieszanych, jest bardzo niedeterministyczna. Nie wiem, jak dobrze to się sprawdzi w prawdziwej konkurencji.

Kilka rzeczy na temat tego bota:

  • Rdzeń jest funkcją rekurencyjną, która oblicza wartość i prawie idealną strategię mieszaną dla każdego konkretnego stanu gry. Teraz mam ustawiony 4 kroki do przodu.
  • Odgrywa bardzo nędzny charakter, ponieważ w wielu przypadkach bot ten jest równoważny z „wybieraniem losowego ruchu w papierowych nożyczkach”. Utrzymuje się i ma nadzieję, że przeciwnik da mu przewagę statystyczną. Gdyby ten bot był doskonały (a nie jest), najlepszym, co możesz zrobić, byłoby 50% wygranych i 50% strat. W rezultacie nie ma przeciwnika, którego konsekwentnie bije, ale także takiego, któremu konsekwentnie przegrywa.
PhiNotPi
źródło
Nadal nie rozumiem nazwy ...: P
HyperNeutrino
@HyperNeutrino Yggdrasil to drzewo mitologiczne, w tym przypadku mam na myśli drzewo gry.
PhiNotPi
Ohhhh racja. Czuję, że powinienem był o tym pamiętać. : P Fajnie!
HyperNeutrino
2

Pain in the Nash (C ++)

Tak zwane, ponieważ fakt, że musiałem napisać własny solver równowagi Nasha, był prawdziwym bólem. Dziwi mnie, że nie ma łatwo dostępnych bibliotek do rozwiązywania problemów z 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;
}

Skompiluj jako C ++ 11 lub nowszy. Dla wydajności dobrze jest skompilować ze wsparciem OpenMP (ale jest to tylko dla szybkości; nie jest wymagane)

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

To wykorzystuje równowagę Nasha do decydowania, co robić w każdej turze, co oznacza, że teoretycznie zawsze wygra lub zremisuje na dłuższą metę (w wielu grach), bez względu na to, jaką strategię stosuje przeciwnik. To, czy tak jest w praktyce, zależy od tego, czy popełniłem jakieś błędy przy wdrażaniu. Ponieważ jednak konkurencja KoTH ma tylko jedną rundę przeciwko każdemu przeciwnikowi, prawdopodobnie nie będzie dobrze na tablicy wyników.

Moim pierwotnym pomysłem było posiadanie prostej funkcji wyceny dla każdego stanu gry (np. Każda piłka jest warta + b, każda kaczka jest + d), ale prowadzi to do oczywistych problemów z określeniem, jakie powinny być te wyceny, i oznacza, że ​​nie może działać na malejące zyski ze zbierania coraz większej liczby piłek itp. Zamiast tego przeanalizuje to całe drzewo gry , pracując wstecz od tury 1000, i wypełni rzeczywiste wyceny na podstawie tego, w jaki sposób każda gra może się układać.

Rezultat jest taki, że nie mam absolutnie pojęcia, jakiej strategii to używa, poza kilkoma zakodowanymi „oczywistymi” zachowaniami (rzucaj śnieżkami, jeśli masz więcej piłek niż przeciwnik ma piłek + kaczek, i przeładuj, jeśli obaj jesteś poza śnieżek). Jeśli ktoś chce przeanalizować generowany przez siebie zestaw danych, wyobrażam sobie, że istnieje kilka ciekawych zachowań do odkrycia!

Testowanie tego pod kątem „Save One” pokazuje, że rzeczywiście wygrywa w długim okresie, ale tylko niewielką marżą (514 wygranych, 486 strat, 0 losowań w pierwszej partii 1000 gier i 509 wygranych, 491 strat, 0 zwraca drugą).


Ważny!

Będzie to działać od razu po wyjęciu z pudełka, ale to nie jest świetny pomysł. Wygenerowanie pełnego drzewa gry zajmuje około 9 minut na moim laptopie o średniej specyfikacji programistów. Ale zapisze ostateczne prawdopodobieństwa w pliku po ich wygenerowaniu, a następnie każda tura generuje losową liczbę i porównuje ją z 2 bajtami, więc jest superszybka.

Aby to wszystko skrócić, wystarczy pobrać ten plik (3,5 MB) i umieścić go w katalogu z plikiem wykonywalnym.

Możesz też wygenerować go samodzielnie, uruchamiając:

./pain_in_the_nash 1000 50 25

Co pozwoli zapisać jeden plik na turę, aż do konwergencji. Zauważ, że każdy plik ma 3,5 MB i zbiegnie się w czasie 720 (tj. 280 plików, ~ 1 GB), a ponieważ większość gier nie zbliża się do końca 720, pliki przed konwergencją mają bardzo małe znaczenie.

Dave
źródło
Czy jest możliwe, aby program wyświetlał tylko wynik końcowy? Dzięki!
HyperNeutrino
@HyperNeutrino wszystkie inne dane wyjściowe powinny być ustawione na stderr, więc nie powinny mieć żadnego wpływu, ale zaktualizowałem je, aby pokazywały postęp tylko w trybie wstępnego przetwarzania. Teraz będzie zapisywać tylko na standardowe wyjście, gdy działa normalnie. Proponuję jednak zastosować się do „ważnej” sugestii, ponieważ w przeciwnym razie po prostu zatrzyma się na pierwszym zakręcie przez kilka minut (przynajmniej przy wstępnym przetwarzaniu widać postęp).
Dave
W porządku Zastosuję się do tej sugestii, dzięki!
HyperNeutrino
Byłbym wdzięczny za przesłanie plików danych, ponieważ wygenerowanie ich wszystkich zajmuje wieczność. Gdybyś mógł to zrobić, byłoby świetnie :)
HyperNeutrino
@HyperNeutrino OK, przesłanie w moim strasznym Internecie zajęło również wieczność, ale konwergentny plik 3,5 MB jest dostępny tutaj: github.com/davidje13/snowball_koth_pitn/blob/master/… (po prostu umieść go w tym samym katalogu).
Dave
1

Swift - TheCrazy_XcodeRandomness

Niestety, może to być zabrakło tylko lokalnie, w Xcode, ponieważ zawiera Foundationmoduł i jego funkcji arc4random_uniform(). Jednak możesz właściwie powiedzieć, jaki jest algorytm:

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
}
Pan Xcoder
źródło
Czy można to uruchomić z systemu bash w systemie Linux?
HyperNeutrino
@HyperNeutrino Wiem, że może to zrobić w systemie macOS, ale nie wiem, czy działa w systemie Linux. Jeśli możesz to sprawdzić, byłoby świetnie. Wypróbuj swiftpolecenie, a następnie sprawdź, czy działa
Mr. Xcoder
Wydaje się, że nie istnieje; jest z nim pakiet, ale nie jest to język Swift. Przepraszam, więc nie mogę tego przetestować, dopóki czegoś nie uda mi się uruchomić.
HyperNeutrino
jedynymi możliwymi kompilatorami są Xcode i IntelliJ, ale nie można go uruchomić online z powodu Foundation, przepraszam: /
Pan Xcoder
rozerwać. Musiałem być w stanie uruchomić go z wiersza poleceń, aby uruchomić z nim kontroler, ale jeśli będę miał czas, mógłbym ręcznie uruchomić to ponownie dla wszystkich innych botów.
HyperNeutrino
1

TableBot, Python 2

Nazywany TableBot, ponieważ został utworzony przez implementację tej tabeli:

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 oznacza posiadanie 1 lub więcej, 0 oznacza brak.

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

Wypróbuj online!

Towarzyszu SparklePony
źródło
1

AmbBot - program rakietowy

Głównie chciałem wypróbować używanie amb, ponieważ jest fajne. Ten bot losowo porządkuje opcje (przeładuj, rzucaj i uciekaj), odfiltrowuje te, które nie mają sensu, i wybiera pierwszą opcję. Ale dzięki amb, możemy korzystać z kontynuacji i cofania się!

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

Zrobiłem również mały program testowy, aby uruchomić dwa z tych botów przeciwko sobie. Wydaje się, że drugi bot wygrywa częściej, więc mogłem gdzieś pomylić.

(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 mówi Przywróć Monikę
źródło
1

MonteBot, C ++

Zasadniczo wziąłem kod z tego Kotha i zmodyfikowałem go do tego wyzwania. Wykorzystuje algorytm Decoupled Tree Search Monte Carlo. Powinno być całkiem blisko równowagi Nasha.

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

Instrukcje kompilacji dla systemu Linux:

Zapisz w MonteBot.cpp.
Uruchom g++ -o -std=c++11 MonteBot MonteBot.cpp.

Polecenie do uruchomienia: ./MonteBot <args>

Numer jeden
źródło
1

Procrastinator - Python 3

Prokrastynator zwleka, grając z wyjątkiem pierwszych kilku tur. Nagle paniczny potwór chce uniknąć przegranej wojny o zasoby, przeciwstawiając się najczęściej używanemu ruchowi przeciwników.

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
źródło
„Procrastinator”. Więc wszyscy w PPCG, którzy tak naprawdę zamierzają odrabiać lekcje? (Nie zaprzeczajcie, ludzie, którzy to czytają. I ja)
HyperNeutrino
1
„Instant Gratification Monkey” Widziałeś też TEDTalk? :)
HyperNeutrino
0

ParanoidBot i PanicBot - ActionScript3 ( RedTamarin )

Z niedopasowanego, niszowego języka (z rozszerzeniami do dostarczania argumentów wiersza poleceń) pochodzi płochliwy ParanoidBot i jego tępy sojusznik, PanicBot.

ParanoidBot

ParanoidBot traci rozum i ma niepotrzebnie określoną strategię, na której może polegać. Po pierwsze, wystrzeliwuje śnieżki aż do osiągnięcia progu, zachowując trochę rezerwy. Następnie, po trzech ostrzegawczych kaczkach, pojawia się paranoja, a bot próbuje zgromadzić więcej śnieżek między losowymi kaczkami. Po uzupełnieniu zapasów ParanoidBot wraca do ślepego rzucania. Ze względu na głosy w głowie ParanoidBot może stwierdzić, czy na pewno wygra, czy przegra, i odpowiednio „strateguje”.

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

Szelki są trochę nieporęczne, aby pomóc skondensować rozmiar

PanicBot

Po tym, jak oszalał, PanicBot reaguje na instynktowny strach. Po wyczerpaniu się kaczek od kulącego się ze strachu PanicBot ślepo rzuca wszystkie swoje śnieżki, a następnie desperacko robi i rzuca więcej śnieżek, aż (prawdopodobnie) zostanie pokonany.

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



Jest to jeden z mniej niż 15 innych wpisów używających AS3 tutaj na PPCG. Pewnego dnia być może ten prawdopodobnie egzotyczny język znajdzie zagadkę do zdominowania.


źródło
Czy można to uruchomić z systemu bash w systemie Linux?
HyperNeutrino
Nie testowałem tego, ale tak, powinno. Plik wykonywalny RedTamarin (redshell) jest zbudowany dla systemów Windows, Mac i Linux: http://redtamarin.com/tools/redshell . Jeśli jeden z powyższych botów zostanie zapisany w pliku o nazwie snow.as, następujące czynności powinny działać w trybie bash:$ ./redshell snow.as -- 0 50 50 25 25
Daje mi błąd odmowy uprawnień podczas próby uruchomienia tego.
HyperNeutrino
@HyperNeutrino chmod +x redshelljest tutaj twoim przyjacielem ...
Erik the Outgolfer
Może wszystko chmod 777? Rozwiązywanie problemów na stronie RedTamarin może być także możliwe
0

Defender, Python

Przeładowuje, gdy żaden z graczy nie ma śnieżek. Jeśli ma śnieżki, rzuca. Jeśli nie ma śnieżek, ale przeciwnik tak, to skacze, jeśli może, inaczej przeładuje.

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

Uwaga: jeszcze nie przetestowane

Solomon Ucko
źródło