Tle przyszłych

W 2017 roku ty i twój przeciwnik zmierzą się w futurystycznej bitwie na broń, w której tylko jeden może przetrwać. Czy masz wystarczające doświadczenie, aby pokonać przeciwnika? Nadszedł czas, aby szlifować umiejętności posługiwania się bronią w swoim ulubionym języku programowania i walczyć z wszelkimi przeciwnościami!

Wyniki turnieju

Ten turniej zakończył na UTC rano lutym 2 ^nd , 2017. Dzięki naszym zawodników, mieliśmy ekscytujący turniej futurystyczny!

MontePlayer jest ostatecznym zwycięzcą po bliskich bitwach z CBetaPlayer i StudiousPlayer. Trzech najlepszych pojedynków Guen wykonało pamiątkową fotografię:

                MontePlayer                         - by TheNumberOne
              +------------+
  CBetaPlayer |            |                        - by George V. Williams
 +------------+    #  1    | StudiousPlayer         - by H Walters
 |                         +----------------+
 |    #  2                        #  3      |       
 +------------------------------------------+
    The Futurustic Gun Duel @ PPCG.SE 2017

Gratulacje dla zwycięzców! Szczegółowa tabela wyników znajduje się na końcu tego postu.

Ogólne wskazówki

• Odwiedź oficjalne repozytorium kodu źródłowego używanego w tym turnieju.
• Wpisy w C ++: odziedzicz Playerklasę.
• Pozycje inne niż C ++: wybierz jeden interfejs w sekcji Interfejs dla zgłoszeń innych niż C ++ .
• Obecnie dozwolone języki inne niż C ++: Python 3, Java.

Pojedynek

• Każdy gracz zaczyna od rozładowanego pistoletu, który może załadować nieskończoną ilość amunicji.
• W każdej turze gracze jednocześnie wybiorą jedną z następujących akcji:
  • 0 - Załaduj 1 amunicję do pistoletu.
  • 1- Wystrzel kulę w przeciwnika; kosztuje 1 załadowaną amunicję.
  • 2- Wystrzel promień plazmy na przeciwnika; kosztuje 2 załadowanej amunicji.
  • - - Broń przychodzącą kulę za pomocą metalowej osłony.
  • = - Broń przychodzącą wiązkę plazmy za pomocą deflektora termicznego.
• Jeśli obaj gracze przetrwać po 100 ^th kolei obaj wydechowego do śmierci, co przekłada się remisem .

Gracz przegrywa pojedynek z bronią, jeśli on

• Czy nie używać metalową osłonę bronić przychodzące kulę.
• Czy NIE UŻYWAĆ deflektora termiczną bronić plazmy przychodzące.
• Wystrzel z pistoletu bez załadowania wystarczającej ilości amunicji, w której jego działo wybuchnie i zabije właściciela.

Ostrzeżenia

Zgodnie z instrukcją dla futurystycznych właścicieli broni :

• Metalowa osłona NIE MOŻE bronić przed nadchodzącą wiązką plazmy. Podobnie deflektor termiczny NIE MOŻE bronić przed nadlatującym pociskiem.
• Promień plazmy obezwładnia pocisk (ponieważ ten pierwszy wymaga więcej załadowanej amunicji). Dlatego jeśli gracz strzela wiązką plazmy w przeciwnika, który strzela kulą w tej samej turze, przeciwnik zostaje zabity.
• Jeśli obaj gracze wystrzelą do siebie pocisk w tej samej turze, pociski zostaną anulowane i obaj gracze przeżyją. Podobnie, jeśli obaj gracze wystrzelą na siebie wiązkę plazmy w tej samej turze, obaj gracze przeżyją.

Warto również zauważyć, że:

• NIE będziesz znać akcji przeciwnika po kolei, dopóki się nie skończy.
• Odbijanie wiązek plazmowych i pociski osłaniające NIE zaszkodzą przeciwnikowi.

Dlatego w każdej turze jest 25 prawidłowych kombinacji akcji:

+-------------+---------------------------------------------+
|   Outcome   |               P L A Y E R   B               |
|    Table    +--------+-----------------+------------------+
| for Players | Load   | Bullet   Plasma | Metal    Thermal |
+---+---------+--------+--------+--------+--------+---------+
| P | Load    |        | B wins | B wins |        |         |
| L +---------+--------+--------+--------+--------+---------+
| A | Bullet  | A wins |        | B wins |        | A wins  |
| Y |         +--------+--------+--------+--------+---------+
| E | Plasma  | A wins | A wins |        | A wins |         |
| R +---------+--------+--------+--------+--------+---------+
|   | Metal   |        |        | B wins |        |         |
|   |         +--------+--------+--------+--------+---------+
| A | Thermal |        | B wins |        |        |         |
+---+---------+--------+--------+---------------------------+

Note: Blank cells indicate that both players survive to the next turn.

Przykładowy pojedynek

Oto pojedynek, który kiedyś miałem z przyjacielem. Wtedy nie wiedzieliśmy wiele o programowaniu, więc używaliśmy gestów rąk i sygnalizowaliśmy prędkość dwóch obrotów na sekundę. Od lewej do prawej nasze działania były z kolei:

    Me: 001-000-1201101001----2
Friend: 00-10-=1-==--0100-1---1

Zgodnie z powyższymi zasadami przegrałem. Czy rozumiesz dlaczego? To dlatego, że wystrzeliłem ostatnią wiązkę plazmy, gdy miałem tylko 1 załadowaną amunicję, co spowodowało wybuch mojej broni.

Odtwarzacz C ++

Ty , jako cywilizowanego futurystycznym programista, nie będzie bezpośrednio obsługiwać broń. Zamiast tego piszesz kod, Playerktóry walczy z innymi ”. Publicznie dziedzicząc klasę c ++ w projekcie GitHub, możesz zacząć pisać miejską legendę.

Player.hpp can be found in Tournament\Player.hpp
An example of a derived class can be found in Tournament\CustomPlayer.hpp

Co musisz lub możesz zrobić

• Musisz odziedziczyć Playerklasę w drodze publicznego dziedziczenia i ogłosić klasę jako ostateczną.
• Musisz zastąpić Player::fight, która zwraca wartość poprawną za Player::Actionkażdym razem, gdy zostanie wywołana.
• Opcjonalnie możesz przesłonić Player::perceivei Player::declaredkontrolować działania przeciwnika i śledzić swoje zwycięstwa.
• Opcjonalnie użyj prywatnych elementów statycznych i metod w klasie pochodnej, aby wykonać bardziej złożone obliczenia.
• Opcjonalnie użyj innych standardowych bibliotek C ++.

Czego NIE wolno robić

• NIE wolno używać żadnej bezpośredniej metody rozpoznawania przeciwnika poza podanym identyfikatorem przeciwnika, który jest tasowany na początku każdego turnieju. Możesz zgadywać, kto jest graczem podczas gry w turnieju.
• NIE wolno zastępować żadnych metod w Playerklasie, które nie są zadeklarowane jako wirtualne.
• NIE wolno deklarować ani inicjować niczego w zakresie globalnym.
• Od debiutu (teraz zdyskwalifikowanego) BlackHatPlayergracze NIE mogą podglądać ani modyfikować stanu przeciwnika.

Przykładowy pojedynek

Proces pojedynku z bronią odbywa się za pomocą GunDuelklasy. Przykład walki można znaleźć Source.cppw sekcji Inicjowanie pojedynku .

Mamy pokazać GunClubPlayer, HumanPlayera GunDuelklasa, które można znaleźć w Tournament\katalogu repozytorium.

W każdym pojedynku GunClubPlayerzaładuje pocisk; odpal to; wypłukać i powtórzyć. Podczas każdej tury HumanPlayerpoprosi cię o akcję przeciwko przeciwnikowi. Twoje kontrole klawiaturowe są znaki 0, 1, 2, -i =. W systemie Windows można użyć HumanPlayerdo debugowania zgłoszenia.

Rozpoczęcie pojedynku

W ten sposób możesz debugować odtwarzacz za pomocą konsoli.

// Source.cpp
// An example duel between a HumanPlayer and GunClubPlayer.

#include "HumanPlayer.hpp"
#include "GunClubPlayer.hpp"
#include "GunDuel.hpp"

int main()
{
    // Total number of turns per duel.
    size_t duelLength = 100;

    // Player identifier 1: HumanPlayer.
    HumanPlayer human(2);
    // Player identifier 2: GunClubPlayer.
    GunClubPlayer gunClub(1);

    // Prepares a duel.
    GunDuel duel(human, gunClub, duelLength);
    // Start a duel.
    duel.fight();
}

Przykładowe gry

Minimalna liczba tur, które musisz pokonać, GunClubPlayerto 3. Oto powtórka z gry 0-1przeciwko GunClubPlayer. Liczba w nawiasie to liczba załadowanej amunicji dla każdego gracza po zakończeniu tury.

 :: Turn 0
    You [0/12/-=] >> [0] load ammo (1 ammo)
    Opponent selects [0] load ammo (1 ammo)
 :: Turn 1
    You [0/12/-=] >> [-] defend using metal shield (1 ammo)
    Opponent selects [1] fire a bullet (0 ammo)
 :: Turn 2
    You [0/12/-=] >> [1] fire a bullet (0 ammo)
    Opponent selects [0] load ammo (1 ammo)
 :: You won after 3 turns!
 :: Replay
    YOU 0-1
    FOE 010
Press any key to continue . . .

Najszybszym sposobem na pokonanie GunClubPlayerbez wykonywania nieprawidłowych ruchów jest sekwencja 0=, ponieważ pocisk strzela prosto przez deflektor termiczny. Powtórka jest

 :: Turn 0
    You [0/12/-=] >> [0] load ammo (1 ammo)
    Opponent selects [0] load ammo (1 ammo)
 :: Turn 1
    You [0/12/-=] >> [=] defend using thermal deflector (1 ammo)
    Opponent selects [1] fire a bullet (0 ammo)
 :: You lost after 2 turns!
 :: Replay
    YOU 0=
    FOE 01
Press any key to continue . . .

Turniej

Turniej odbywa się w formacie „Last Player Standing”. W turnieju wszystkie ważne zgłoszenia (w tym GunClubPlayer) są umieszczane w puli. Każde zgłoszenie ma przydzielony losowy, ale niepowtarzalny identyfikator, który pozostanie taki sam podczas całego turnieju. Podczas każdej rundy:

• Każde zgłoszenie rozpoczyna się od 0 punktów i rozegra 100 pojedynków z każdym innym zgłoszeniem.
• Każdy zwycięski pojedynek da 1 punkt; losowanie i przegrywanie daje 0 punktów.
• Pod koniec rundy zgłoszenia z minimalną liczbą punktów opuszczają turniej. W przypadku remisu, gracz z najmniejszą ilością punktów zdobytych od początku turnieju odejdzie.
• Jeśli pozostanie więcej niż jeden gracz, rozpocznie się następna runda.
• Punkty NIE przenoszą się do następnej rundy.

Zgłoszenie

Prześlesz jednego gracza na odpowiedź. Możesz przesłać wiele plików do odtwarzacza, o ile NIE kolidują one z innymi przesyłkami. Aby utrzymać płynność, proszę:

• Nazwij główny plik nagłówka jako <Custom>Player.hpp,
• Nazwij swoje inne pliki jako <Custom>Player*.*, np. MyLittlePlayer.txtJeśli nazwa klasy to MyLittlePlayer, lub EmoPlayerHates.cppjeśli nazwa klasy to EmoPlayer.
• Jeśli twoje imię Shooterlub podobne słowa pasują do kontekstu tego turnieju, nie musisz dodawać Playerna końcu. Jeśli uważasz, że nazwa zgłoszenia działa lepiej bez przyrostka Player, nie musisz go dodawać Player.
• Upewnij się, że kod można skompilować i połączyć w systemie Windows.

Możesz skomentować, poprosić o wyjaśnienia lub znaleźć luki. Mam nadzieję, że spodoba ci się ten futurystyczny pojedynek z bronią i życzę szczęśliwego nowego roku!

Wyjaśnienie

• Możesz mieć losowe zachowanie.
• Dozwolone są nieprawidłowe działania (strzelanie, gdy załadowana amunicja nie wystarcza).
• Jeśli gracz dokona nieprawidłowego wejścia, jego pistolet natychmiast wybuchnie.
• Możesz studiować odpowiedzi.
• Możesz wyraźnie rejestrować zachowanie przeciwnika w każdym turnieju.
• W każdej rundzie rozegrasz 100 pojedynków z każdym przeciwnikiem; kolejność 100 pojedynków jest jednak losowa - nie masz gwarancji stoczenia 100 pojedynczych przeciwników z rzędu.

Dodatkowe zasoby

@flawr przetłumaczył dostarczone źródło C ++ na Javę jako odniesienie, jeśli chcesz przesłać wpisy C ++.

Interfejs dla zgłoszeń innych niż C ++

Obecnie akceptowane: Python 3, Java.

Postępuj zgodnie z jedną z poniższych specyfikacji:

Specyfikacja interfejsu 1: kod wyjścia

Twoje zgłoszenie będzie uruchamiane raz na turę.

Expected Command Line Argument Format:
    <opponent-id> <turn> <status> <ammo> <ammo-opponent> <history> <history-opponent>

Expected Return Code: The ASCII value of a valid action character.
    '0' = 48, '1' = 49, '2' = 50, '-' = 45, '=' = 61

<opponent-id> is an integer in [0, N), where N is size of tournament.
<turn> is 0-based.
If duel is in progress, <status> is 3.
If duel is draw / won / lost, <status> is 0 / 1 / 2.
<history> and <history-opponent> are strings of actions, e.g. 002 0-=
If turn is 0, <history> and <history-opponent> are not provided.
You can ignore arguments you don't particularly need.

Możesz przetestować swoje zgłoszenie PythonPlayer\i JavaPlayer\katalogi.

Specyfikacja interfejsu 2: stdin / stdout

(Podziękowania dla H Waltersa)

Twoje zgłoszenie będzie realizowane raz na turniej.

Istnieje stały wymóg dla wszystkich zgłoszeń dotyczących wykonywania operacji we / wy, ponieważ zarówno stdin, jak i stdout są podłączone do sterownika turnieju. Naruszenie tego może doprowadzić do impasu. Wszystkie wpisy MUSZĄ być zgodne z tym DOKŁADNYM algorytmem (w pseudokodzie):

LOOP FOREVER
    READ LINE INTO L
    IF (LEFT(L,1) == 'I')
        INITIALIZE ROUND
        // i.e., set your/opponent ammo to 0, if tracking them
        // Note: The entire line at this point is a unique id per opponent;
        // optionally track this as well.
        CONTINUE LOOP
    ELSE IF (LEFT(L,1) == 'F')
        WRITELN F // where F is your move
    ELSE IF (LEFT(L,1) == 'P')
        PROCESS MID(L,2,1) // optionally perceive your opponent's action.
    END IF
CONTINUE LOOP
QUIT

Tutaj F jest jednym z 0, 1, 2, -, lub =za load / bullet / plasma / metal / thermal. PROCES oznacza opcjonalną reakcję na to, co zrobił twój przeciwnik (w tym śledzenie amunicji przeciwnika, jeśli to robisz). Zauważ, że akcja przeciwnika jest również jedną z „0”, „1”, „2”, „-” lub „=” i występuje w drugim znaku.

Ostateczna tablica wyników

08:02 AM Tuesday, February 2, 2017 Coordinated Universal Time (UTC)
| Player             | Language   | Points |     1 |     2 |     3 |     4 |     5 |     6 |     7 |     8 |     9 |    10 |    11 |    12 |    13 |    14 |    15 |    16 |
|:------------------ |:---------- | ------:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:| -----:|
| MontePlayer        | C++        |  11413 |  1415 |  1326 |  1247 |  1106 |  1049 |   942 |   845 |   754 |   685 |   555 |   482 |   381 |   287 |   163 |   115 |    61 |
| CBetaPlayer        | C++        |   7014 |   855 |   755 |   706 |   683 |   611 |   593 |   513 |   470 |   414 |   371 |   309 |   251 |   192 |   143 |   109 |    39 |
| StudiousPlayer     | C++        |  10014 |  1324 |  1233 |  1125 |  1015 |   907 |   843 |   763 |   635 |   555 |   478 |   403 |   300 |   201 |   156 |    76 |
| FatedPlayer        | C++        |   6222 |   745 |   683 |   621 |   655 |   605 |   508 |   494 |   456 |   395 |   317 |   241 |   197 |   167 |   138 |
| HanSoloPlayer      | C++        |   5524 |   748 |   668 |   584 |   523 |   490 |   477 |   455 |   403 |   335 |   293 |   209 |   186 |   153 |
| SurvivorPlayer     | C++        |   5384 |   769 |   790 |   667 |   574 |   465 |   402 |   354 |   338 |   294 |   290 |   256 |   185 |
| SpecificPlayer     | C++        |   5316 |   845 |   752 |   669 |   559 |   488 |   427 |   387 |   386 |   340 |   263 |   200 |
| DeceptivePlayer    | C++        |   4187 |   559 |   445 |   464 |   474 |   462 |   442 |   438 |   369 |   301 |   233 |
| NotSoPatientPlayer | C++        |   5105 |   931 |   832 |   742 |   626 |   515 |   469 |   352 |   357 |   281 |
| BarricadePlayer    | C++        |   4171 |   661 |   677 |   614 |   567 |   527 |   415 |   378 |   332 |
| BotRobotPlayer     | C++        |   3381 |   607 |   510 |   523 |   499 |   496 |   425 |   321 |
| SadisticShooter    | C++        |   3826 |   905 |   780 |   686 |   590 |   475 |   390 |
| TurtlePlayer       | C++        |   3047 |   754 |   722 |   608 |   539 |   424 |
| CamtoPlayer        | C++        |   2308 |   725 |   641 |   537 |   405 |
| OpportunistPlayer  | C++        |   1173 |   426 |   420 |   327 |
| GunClubPlayer      | C++        |    888 |   500 |   388 |
| PlasmaPlayer       | C++        |    399 |   399 |

Turniej potrwa do 1 lutego 2017 r., Chyba że zaznaczono inaczej.

MontePlayer

Ten gracz korzysta z algorytmu wyszukiwania drzewa Decoupled UCT Monte Carlo, aby zdecydować, jakich wyborów powinien dokonać. Śledzi to, co robi wróg, aby przewidzieć jego działania. Symuluje wroga jako samego, jeśli brakuje mu danych.

Ten bot radzi sobie naprawdę dobrze z każdym innym botem oprócz cβ. W meczu 10000 pojedynków z cβ, Monte wygrał 5246 pojedynków. Przy odrobinie matematyki oznacza to, że Monte wygra pojedynek z cβ 51,17% do 53,74% czasu (99% zaufania).

#ifndef __Monte_PLAYER_HPP__
#define __Monte_PLAYER_HPP__

#include "Player.hpp"
#include <cstdlib>
#include <ctime>
#include <memory>
#include <iostream>


class MontePlayer final : public Player
{
    static const int MAX_TURNS = 100;
    static const int TOTAL_ACTIONS = 5;

    //Increase this if number of players goes above 20.
    static const int MAX_PLAYERS = 20;

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


    /**
    * Represents the current state of the game.
    */
    struct Game
    {
        int turn;
        int ammo;
        int opponentAmmo;
        bool alive;
        bool opponentAlive;

        Game(int turn, int ammo, int opponentAmmo, bool alive, bool opponentAlive)
            : turn(turn), ammo(ammo), opponentAmmo(opponentAmmo), alive(alive), opponentAlive(opponentAlive) {}
        Game() : turn(0), ammo(0), opponentAmmo(0), alive(false), opponentAlive(false) {}
    };

    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 = NULL;

        //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] = { { NULL } };

        MonteTree(int turn, int ammo, int opponentAmmo) :
            game(turn, ammo, opponentAmmo, true, true) {}


        MonteTree(Game game, MonteTree *parent, int myAction, int opponentAction) :
            game(game), parent(parent), myAction(myAction), opponentAction(opponentAction)
        {
            //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 = NULL;
                        delete branch;
                    }
                }
            }
        }
    };

    //The previous state.
    Game prevGame;
    //The id of the opponent.
    int opponent;
    //opponentHistory[a][b][c][d] returns the number of times
    //that opponent a did action d when I had b ammo and he had c ammo.
    static int opponentHistory[MAX_PLAYERS][MAX_TURNS][MAX_TURNS][TOTAL_ACTIONS];

public:
    MontePlayer(size_t opponent = -1) : Player(opponent)
    {
        srand(time(NULL));
        this->opponent = opponent;
    }

public:

    virtual Action fight()
    {
        //Create the root tree. Will be auto-destroyed after this function ends.
        MonteTree current(getTurn(), getAmmo(), getAmmoOpponent());

        //Set the previous game to this one.
        prevGame = current.game;

        //Get these variables so we can log later if nessecarry.
        int turn = getTurn(),
            ammo = getAmmo(),
            opponentAmmo = getAmmoOpponent();

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

        //Get the best move.
        int move = bestMove(current);

        //Move string for debugging purposes.
        const char* m;

        //We have to do this so our bots state is updated.
        switch (move)
        {
        case Action::LOAD:
            load();
            m = "load";
            break;
        case Action::BULLET:
            bullet();
            m = "bullet";
            break;
        case Action::PLASMA:
            plasma();
            m = "plasma";
            break;
        case Action::METAL:
            metal();
            m = "metal";
            break;
        case Action::THERMAL:
            thermal();
            m = "thermal";
            break;
        default: //???
            std::cout << move << " ???????\n";
            throw move;
        }

        return (Action)move;
    }

    /**
    * Record what the enemy does so we can predict him.
    */
    virtual void perceive(Action action)
    {
        Player::perceive(action);
        opponentHistory[opponent][prevGame.ammo][prevGame.opponentAmmo][action]++;
    }
private:

    /**
    * 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 (!atEnd(root->game))
        {
            //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 (!isValidMove(root->game, i, true))
                {
                    continue;
                }

                //Get the score for doing move i. Uses
                double score = computeScore(*root, 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(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;

            //The number of times the enemy has been in this same situation.
            int totalEnemyEncounters = 0;
            for (int i = 0; i < TOTAL_ACTIONS; i++)
            {
                totalEnemyEncounters += opponentHistory[opponent][root->game.ammo][root->game.opponentAmmo][i];
            }

            //Assume the enemy will choose an action it has chosen before if we've
            //seen it in this situation before. Otherwise we assume that the enemy is ourselves.
            if (totalEnemyEncounters > 0)
            {
                //Randomly select an action that the enemy has done with
                //weighted by the number of times that action has been done.
                int selection = Random(totalEnemyEncounters);
                for (int i = 0; i < TOTAL_ACTIONS; i++)
                {
                    selection -= opponentHistory[opponent][root->game.ammo][root->game.opponentAmmo][i];
                    if (selection < 0)
                    {
                        enemyAction = i;
                        break;
                    }
                }
            }
            else
            {
                //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 (!isValidMove(root->game, i, false))
                    {
                        continue;
                    }

                    double score = computeScore(*root, i, false);
                    if (score == bestScore)
                    {
                        same++;
                        if (Random(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 expand(root, myAction, enemyAction);
            }

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

    /**
    * Creates a new leaf under root for the actions.
    */
    MonteTree * expand(MonteTree *root, int myAction, int enemyAction)
    {
        return new MonteTree(
            doTurn(root->game, myAction, enemyAction),
            root,
            myAction,
            enemyAction);
    }

    /**
    * Computes the score of the given move in the given position.
    * Uses the UCB1 algorithm and returns infinity for moves not tried yet.
    */
    double computeScore(const MonteTree &root, int move, bool me)
    {
        const Stat &stat = me ? root.myStats[move] : root.opponentStats[move];
        return stat.attempts == 0 ?
            HUGE_VAL :
            double(stat.wins) / stat.attempts + sqrt(2 * log(root.totalPlays) / stat.attempts);
    }

    /**
    * Randomly simulates the given game.
    * Has me do random moves that are not stupid.
    * Has opponent do what it has done in similar positions or random moves if not
    * observed in those positions yet.
    *
    * Returns 1 for win. 0 for loss. -1 for draw.
    */
    int simulate(Game game)
    {
        while (!atEnd(game))
        {
            game = doRandomTurn(game);
        }

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

    /**
    * Returns whether the game is over or not.
    */
    bool atEnd(Game game)
    {
        return !game.alive || !game.opponentAlive || game.turn > MAX_TURNS;
    }

    /**
    * Simulates the given actions on the game.
    */
    Game doTurn(Game game, int myAction, int enemyAction)
    {
        game.turn++;

        switch (myAction)
        {
        case Action::LOAD:
            game.ammo++;
            break;
        case Action::BULLET:
            if (game.ammo < 1)
            {
                game.alive = false;
                break;
            }
            game.ammo--;
            if (enemyAction == Action::LOAD || enemyAction == Action::THERMAL)
            {
                game.opponentAlive = false;
            }
            break;
        case Action::PLASMA:
            if (game.ammo < 2)
            {
                game.alive = false;
                break;
            }
            game.ammo -= 2;
            if (enemyAction != Action::PLASMA && enemyAction != Action::THERMAL)
            {
                game.opponentAlive = false;
            }
            break;
        }

        switch (enemyAction)
        {
        case Action::LOAD:
            game.opponentAmmo++;
            break;
        case Action::BULLET:
            if (game.opponentAmmo < 1)
            {
                game.opponentAlive = false;
                break;
            }
            game.opponentAmmo--;
            if (myAction == Action::LOAD || myAction == Action::THERMAL)
            {
                game.alive = false;
            }
            break;
        case Action::PLASMA:
            if (game.opponentAmmo < 2)
            {
                game.opponentAlive = false;
            }
            game.opponentAmmo -= 2;
            if (myAction != Action::PLASMA && myAction != Action::THERMAL)
            {
                game.alive = false;
            }
            break;
        }

        return game;
    }

    /**
    * 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 (isValidMove(game, i, true))
            {
                validMoves++;
                if (Random(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++)
        {
            int weight = opponentHistory[opponent][game.ammo][game.opponentAmmo][i];
            if (weight > 0)
            {
                if (!enemyEncountered)
                {
                    enemyEncountered = true;
                    validMoves = 0;
                }
                validMoves += weight;
                if (Random(validMoves) < weight)
                {
                    opponentAction = i;
                }
            }
            else if (!enemyEncountered && isValidMove(game, i, false))
            {
                validMoves++;
                if (Random(validMoves) == 0)
                {
                    opponentAction = i;
                }
            }
        }

        return doTurn(game, myAction, opponentAction);
    }

    /**
    * Returns whether the given move is valid/not idiotic for the game.
    */
    bool isValidMove(Game game, int move, bool me)
    {
        switch (move)
        {
        case Action::LOAD:
            return true;
        case Action::BULLET:
            return me ? game.ammo > 0 : game.opponentAmmo > 0;
        case Action::PLASMA:
            return me ? game.ammo > 1 : game.opponentAmmo > 1;
        case Action::METAL:
            return me ? game.opponentAmmo > 0 : game.ammo > 0;
        case Action::THERMAL:
            return me ? game.opponentAmmo > 1 : game.ammo > 1;
        default:
            return false;
        }
    }

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

    /**
    * There are three different strategies in here.
    * The first is not random, the second more, the third most.
    */
    int bestMove(const MonteTree &root)
    {
        //Select the move with the highest win rate.
        int best;
        double bestScore = -1;
        for (int i = 0; i < TOTAL_ACTIONS; i++)
        {
            if (root.myStats[i].attempts == 0)
            {
                continue;
            }

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

        return best;

        ////Select a move weighted by the number of times it has won the game.
        //int totalScore = 0;
        //for (int i = 0; i < TOTAL_ACTIONS; i++)
        //{
        //  totalScore += root.myStats[i].wins;
        //}
        //int selection = Random(totalScore);
        //for (int i = 0; i < TOTAL_ACTIONS; i++)
        //{
        //  selection -= root.myStats[i].wins;
        //  if (selection < 0)
        //  {
        //      return i;
        //  }
        //}

        ////Select a random move weighted by win ratio.
        //double totalScore = 0;
        //for (int i = 0; i < TOTAL_ACTIONS; i++)
        //{
        //  if (root.myStats[i].attempts == 0)
        //  {
        //      continue;
        //  }
        //  totalScore += double(root.myStats[i].wins) / root.myStats[i].attempts;
        //}
        //double selection = Random(totalScore);
        //for (int i = 0; i < TOTAL_ACTIONS; i++)
        //{
        //  if (root.myStats[i].attempts == 0)
        //  {
        //      continue;
        //  }
        //  selection -= double(root.myStats[i].wins) / root.myStats[i].attempts;
        //  if (selection < 0)
        //  {
        //      return i;
        //  }
        //}
    }

    //My own random functions.
    int Random(int max)
    {
        return GetRandomInteger(max - 1);
    }
    double Random(double max)
    {
        static auto seed = std::chrono::system_clock::now().time_since_epoch().count();
        static std::default_random_engine generator((unsigned)seed);
        std::uniform_real_distribution<double> distribution(0.0, max);
        return distribution(generator);
    }
};
//We have to initialize this here for some reason.
int MontePlayer::opponentHistory[MAX_PLAYERS][MAX_TURNS][MAX_TURNS][TOTAL_ACTIONS]{ { { { 0 } } } };

#endif // !__Monte_PLAYER_HPP__

The BlackHatPlayer

Gracz BlackHat wie, że kule i tarcze należą już do przeszłości; rzeczywiste wojny wygrywają ci, którzy potrafią zhakować programy przeciwnika.

Więc zakłada stałą metalową tarczę i zaczyna robić swoje.

Za pierwszym razem, gdy jest o to poproszony fight, próbuje zlokalizować wroga w pamięci. Biorąc pod uwagę strukturę areny walki, jest prawie pewne, że kompilator ostatecznie umieści swój adres (zawinięty w unique_ptr) i jednego przeciwnika tylko jeden obok drugiego.

Tak więc BlackHat ostrożnie chodzi po stosie, używając kilku prostych heurystyk, aby upewnić się, że nie spadnie, dopóki nie znajdzie wskaźnika dla siebie; następnie sprawdza, czy wartości na sąsiednich pozycjach są prawdopodobne dla jego przeciwnika - podobny adres, podobny adres vtable, prawdopodobny typeid.

Jeśli uda mu się go znaleźć, wysysa mózg i zastępuje go idiotą. W praktyce odbywa się to poprzez zamianę wskaźnika przeciwnika na vtable na adres Idiotvtable - głupiego gracza, który zawsze strzela.

Jeśli to wszystko się powiedzie (i w moich testach - gcc 6 na Linuksie 64-bitowym, MinGW 4.8 na 32-bitowym Winie - działa to całkiem niezawodnie), wojna wygrywa. Cokolwiek przeciwnik zrobił w pierwszej rundzie, nie jest ważne - w najgorszym wypadku nas zastrzelił, a my mieliśmy metalową tarczę.

Od tej pory mamy idiotę po prostu strzelającego; zawsze mamy włączoną tarczę, więc jesteśmy chronieni, a on wysadzi w powietrze 1 do 3 rund (w zależności od tego, co zrobił pierwszy bot fight).

Teraz: jestem prawie pewien, że należy to natychmiast zdyskwalifikować, ale to zabawne, że nie naruszam wyraźnie żadnej z powyższych zasad:

Czego NIE wolno robić

• NIE wolno używać żadnej bezpośredniej metody rozpoznawania przeciwnika innej niż podany identyfikator przeciwnika, który jest całkowicie losowy na początku każdego turnieju. Możesz zgadywać, kto jest graczem podczas gry w turnieju.

BlackHat nie próbuje rozpoznać przeciwnika - w rzeczywistości nie ma znaczenia, kim jest przeciwnik, biorąc pod uwagę, że jego mózg został natychmiast zastąpiony.

• NIE wolno zastępować żadnych metod w klasie Player, które nie zostały zadeklarowane jako wirtualne.
• NIE wolno deklarować ani inicjować niczego w zakresie globalnym.

Wszystko dzieje się lokalnie z fightfunkcją wirtualną.

// BlackHatPlayer.hpp

#ifndef __BLACKHAT_PLAYER_HPP__
#define __BLACKHAT_PLAYER_HPP__

#include "Player.hpp"
#include <stddef.h>
#include <typeinfo>
#include <algorithm>
#include <string.h>

class BlackHatPlayer final : public Player
{
public:
    using Player::Player;

    virtual Action fight()
    {
        // Always metal; if the other is an Idiot, he only shoots,
        // and if he isn't an Idiot yet (=first round) it's the only move that
        // is always safe
        if(tricked) return metal();
        // Mark that at the next iterations we don't have to do all this stuff
        tricked = true;

        typedef uintptr_t word;
        typedef uintptr_t *pword;
        typedef uint8_t *pbyte;

        // Size of one memory page; we use it to walk the stack carefully
        const size_t pageSize = 4096;
        // Maximum allowed difference between the vtables
        const ptrdiff_t maxVTblDelta = 65536;
        // Maximum allowed difference between this and the other player
        ptrdiff_t maxObjsDelta = 131072;

        // Our adversary
        Player *c = nullptr;

        // Gets the start address of the memory page for the given object
        auto getPage = [&](void *obj) {
            return pword(word(obj) & (~word(pageSize-1)));
        };
        // Gets the start address of the memory page *next* to the one of the given object
        auto getNextPage = [&](void *obj) {
            return pword(pbyte(getPage(obj)) + pageSize);
        };

        // Gets a pointer to the first element of the vtable
        auto getVTbl = [](void *obj) {
            return pword(pword(obj)[0]);
        };

        // Let's make some mess to make sure that:
        // - we have an actual variable on the stack;
        // - we call an external (non-inline) function that ensures everything
        //   is spilled on the stack
        // - the compiler actually generates the full vtables (in the current
        //   tournament this shouldn't be an issue, but in earlier sketches
        //   the compiler inlined everything and killed the vtables)
        volatile word i = 0;
        for(const char *sz = typeid(*(this+i)).name(); *sz; ++sz) i+=*sz;

        // Grab my vtable
        word *myVTbl = getVTbl(this);

        // Do the stack walk
        // Limit for the stack walk; use i as a reference
        word *stackEnd = getNextPage((pword)(&i));
        for(word *sp = pword(&i);       // start from the location of i
            sp!=stackEnd && c==nullptr;
            ++sp) {                     // assume that the stack grows downwards
            // If we find something that looks like a pointer to memory
            // in a page just further on the stack, take it as a clue that the
            // stack in facts does go on
            if(getPage(pword(*sp))==stackEnd) {
                stackEnd = getNextPage(pword(*sp));
            }
            // We are looking for our own address on the stack
            if(*sp!=(word)this) continue;

            auto checkCandidate = [&](void *candidate) -> Player* {
                // Don't even try with NULLs and the like
                if(getPage(candidate)==nullptr) return nullptr;
                // Don't trust objects too far away from us - it's probably something else
                if(abs(pbyte(candidate)-pbyte(this))>maxObjsDelta) return nullptr;
                // Grab the vtable, check if it actually looks like one (it should be
                // decently near to ours)
                pword vtbl = getVTbl(candidate);
                if(abs(vtbl-myVTbl)>maxVTblDelta) return nullptr;
                // Final check: try to see if its name looks like a "Player"
                Player *p = (Player *)candidate;
                if(strstr(typeid(*p).name(), "layer")==0) return nullptr;
                // Jackpot!
                return p;
            };

            // Look around us - a pointer to our opponent should be just near
            c = checkCandidate((void *)sp[-1]);
            if(c==nullptr) c=checkCandidate((void *)sp[1]);
        }

        if(c!=nullptr) {
            // We found it! Suck his brains out and put there the brains of a hothead idiot
            struct Idiot : Player {
                virtual Action fight() {
                    // Always fire, never reload; blow up in two turns
                    // (while we are always using the metal shield to protect ourselves)
                    return bullet();
                }
            };
            Idiot idiot;
            // replace the vptr
            (*(word *)(c)) = word(getVTbl(&idiot));
        }
        // Always metal shield to be protected from the Idiot
        return metal();
    }
private:
    bool tricked = false;
};

#endif // !__BLACKHAT_PLAYER_HPP__

Następnie, najbardziej przerażający ze wszystkich stworzeń, był w piekle iz powrotem i walczył z dosłownie 900000 innymi botami , jego ...

The BotRobot

BotRobot został nazwany, wyszkolony i zbudowany automatycznie przez bardzo podstawowy algorytm genetyczny.

Dwie drużyny po 9 zostały ustawione przeciwko sobie, w każdym pokoleniu, każdy robot z zespołu 1 jest wystawiany przeciwko każdemu robotowi z zespołu 2. Roboty z większą liczbą zwycięstw niż strat, zachowały pamięć, a drugie wróciły do ​​ostatniego kroku i miał okazję coś zapomnieć, miejmy nadzieję, że źle. Same boty to uwielbiane tabele odnośników, w których gdyby znalazły coś, czego wcześniej nie widzieli, po prostu wybraliby losową prawidłową opcję i zapisali ją w pamięci. Wersja C ++ tego nie robi, należy się tego nauczyć . Jak wspomniano wcześniej, zwycięskie boty zachowują tę nowo znalezioną pamięć, ponieważ wyraźnie działała. Utracone boty nie zachowują tego, od czego zaczęły.

W końcu walki botów były dość bliskie, rzadko patowe. Zwycięzca został wybrany z puli dwóch zespołów po ewolucji, która wynosiła 100 000 pokoleń.

BotRobot, z losowo wygenerowanym i PIĘKNA nazwie, był szczęśliwym.

Generator

bot.lua

Rewizja: Chociaż robot był dość inteligentny przeciwko sobie i innym podobnie generowanym robotom, okazał się dość bezużyteczny w rzeczywistych bitwach. Tak więc zregenerowałem jego mózg przeciwko niektórym już stworzonym botom.

Rezultaty, jak można łatwo zobaczyć, są znacznie bardziej złożonym mózgiem, z opcjami do wroga gracza posiadającego 12 amunicji.

Nie jestem pewien, z czym walczył, że dostał 12 amunicji, ale coś się udało.

I oczywiście gotowy produkt ...

// BotRobot
// ONE HUNDRED THOUSAND GENERATIONS TO MAKE THE ULTIMATE LIFEFORM!

#ifndef __BOT_ROBOT_PLAYER_HPP__
#define __BOT_ROBOT_PLAYER_HPP__

#include "Player.hpp"

class BotRobotPlayer final : public Player
{
public:
    BotRobotPlayer(size_t opponent = -1) : Player(opponent) {}

public:
    virtual Action fight()
    {
        std::string action = "";
        action += std::to_string(getAmmo());
        action += ":";
        action += std::to_string(getAmmoOpponent());

        int toDo = 3;

        for (int i = 0; i < int(sizeof(options)/sizeof(*options)); i++) {
            if (options[i].compare(action)==0) {
                toDo = outputs[i];
                break;
            }
        }

        switch (toDo) {
            case 0:
                return load();
            case 1:
                return bullet();
            case 2:
                return plasma();
            case 3:
                return metal();
            default:
                return thermal();
        }
    }

private:
    std::string options[29] =
    {
        "0:9",
        "1:12",
        "1:10",
        "0:10",
        "1:11",
        "0:11",
        "0:6",
        "2:2",
        "0:2",
        "2:6",
        "3:6",
        "0:7",
        "1:3",
        "2:3",
        "0:3",
        "2:0",
        "1:0",
        "0:4",
        "1:4",
        "2:4",
        "0:0",
        "3:0",
        "1:1",
        "2:1",
        "2:9",
        "0:5",
        "0:8",
        "3:1",
        "0:1"
    };

    int outputs[29] =
    {
        0,
        1,
        1,
        4,
        1,
        0,
        0,
        4,
        4,
        0,
        0,
        3,
        0,
        1,
        3,
        0,
        1,
        4,
        0,
        1,
        0,
        1,
        0,
        3,
        4,
        3,
        0,
        1,
        0
    };
};

#endif // !__BOT_ROBOT_PLAYER_HPP__

Ja nienawidzę C ++ teraz ...

CBetaPlayer (cβ)

Przybliżona równowaga Nasha.

Ten bot to po prostu fantazyjna matematyka z opakowaniem kodu.

Możemy zmienić to jako problem teorii gier. Oznacz wygraną przez +1 i przegraną przez -1. Teraz niech B (x, y) będzie wartością gry, w której mamy x amunicji, a nasz przeciwnik ma y amunicji. Zauważ, że B (a, b) = -B (b, a), a więc B (a, a) = 0. Aby znaleźć wartości B w kategoriach innych wartości B, możemy obliczyć wartość macierzy wypłat. Na przykład mamy, że B (1, 0) jest podany przez wartość następującej podgrupy:

       load      metal
load    B(0, 1)   B(2, 0)
bullet  +1        B(0, 0)

(Usunąłem „złe” opcje, czyli te, które są ściśle zdominowane przez istniejące rozwiązania. Na przykład nie próbowalibyśmy strzelać w plazmę, ponieważ mamy tylko 1 amunicję. Podobnie nasz przeciwnik nigdy nie użyłby deflektora termicznego, ponieważ nigdy nie będziemy strzelać w plazmę).

Teoria gier pozwala nam dowiedzieć się, jak znaleźć wartość tej macierzy wypłat, przy założeniu pewnych warunków technicznych. Otrzymujemy, że wartość powyższej macierzy wynosi:

                B(2, 0)
B(1, 0) = ---------------------
          1 + B(2, 0) - B(2, 1)

Przechodząc do wszystkich możliwych gier i zauważając, że B (x, y) -> 1 jako x -> nieskończoność ze stałą y, możemy znaleźć wszystkie wartości B, co z kolei pozwala nam obliczyć idealne ruchy!

Oczywiście teoria rzadko pokrywa się z rzeczywistością. Rozwiązanie równania nawet dla małych wartości xiy szybko staje się zbyt skomplikowane. Aby sobie z tym poradzić, wprowadziłem coś, co nazywam aproksymacją cβ. Przybliżenie to ma 7 parametrów: c0, β0, c1, β1, c, β i k. Założyłem, że wartości B przyjęły następującą formę (najpierw najbardziej szczegółowe):

B(1, 0) = k
B(x, 0) = 1 - c0 β0^x
B(x, 1) = 1 - c1 β1^x
B(x, y) = 1 - c β^(x - y)   (if x > y)

Jakieś przybliżone uzasadnienie, dlaczego wybrałem te parametry. Najpierw wiedziałem, że zdecydowanie chcę poradzić sobie z posiadaniem 0, 1 i 2 lub więcej amunicji osobno, ponieważ każda z nich otwiera inne opcje. Pomyślałem również, że geometryczna funkcja przetrwania byłaby najbardziej odpowiednia, ponieważ gracz defensywny w zasadzie zgaduje, jaki ruch wykonać. Uznałem, że posiadanie 2 lub więcej amunicji jest w zasadzie takie samo, więc zamiast tego skupiłem się na różnicy. Chciałem też potraktować B (1, 0) jako bardzo wyjątkowy przypadek, ponieważ myślałem, że bardzo się pokaże. Korzystanie z tych przybliżonych formularzy znacznie uprościło obliczenia wartości B.

W przybliżeniu rozwiązałem otrzymane równania, aby uzyskać każdą wartość B, którą następnie włożyłem z powrotem do macierzy w celu uzyskania macierzy wypłat. Następnie za pomocą liniowego solvera programującego znalazłem optymalne prawdopodobieństwo wykonania każdego ruchu i wrzuciłem je do programu.

Program jest uwielbianą tabelą odnośników. Jeśli obaj gracze mają od 0 do 4 amunicji, korzysta z macierzy prawdopodobieństwa, aby losowo określić, który ruch powinien wykonać. W przeciwnym razie próbuje ekstrapolować na podstawie swojej tabeli.

Ma kłopoty z głupimi deterministycznymi botami, ale całkiem dobrze radzi sobie z racjonalnymi botami. Z powodu wszystkich przybliżeń, czasami przegrywa z StudiousPlayer, kiedy tak naprawdę nie powinno.

Oczywiście, gdybym miał to zrobić ponownie, prawdopodobnie spróbowałbym dodać więcej niezależnych parametrów lub być może lepszą formę ansatz i znaleźć bardziej dokładne rozwiązanie. Również (celowo) zignorowałem limit skrętu, ponieważ utrudniało to wszystko. Można dokonać szybkiej modyfikacji, aby zawsze strzelać plazmą, jeśli mamy wystarczającą ilość amunicji i nie ma wystarczającej liczby zwrotów.

// CBetaPlayer (cβ)
// PPCG: George V. Williams

#ifndef __CBETA_PLAYER_HPP__
#define __CBETA_PLAYER_HPP__

#include "Player.hpp"
#include <iostream>

class CBetaPlayer final : public Player
{
public:
    CBetaPlayer(size_t opponent = -1) : Player(opponent)
    {
    }

public:
    virtual Action fight()
    {
        int my_ammo = getAmmo(), opp_ammo = getAmmoOpponent();

        while (my_ammo >= MAX_AMMO || opp_ammo >= MAX_AMMO) {
            my_ammo--;
            opp_ammo--;
        }

        if (my_ammo < 0) my_ammo = 0;
        if (opp_ammo < 0) opp_ammo = 0;

        double cdf = GetRandomDouble();
        int move = -1;
        while (cdf > 0 && move < MAX_MOVES - 1)
            cdf -= probs[my_ammo][opp_ammo][++move];

        switch (move) {
            case 0: return load();
            case 1: return bullet();
            case 2: return plasma();
            case 3: return metal();
            case 4: return thermal();
            default: return fight();
        }
    }

    static double GetRandomDouble() {
        static auto seed = std::chrono::system_clock::now().time_since_epoch().count();
        static std::default_random_engine generator((unsigned)seed);
        std::uniform_real_distribution<double> distribution(0.0, 1.0);
        return distribution(generator);
    }

private:
    static const int MAX_AMMO = 5;
    static const int MAX_MOVES = 5;

    double probs[MAX_AMMO][MAX_AMMO][5] =
        {
            {{1, 0, 0, 0, 0}, {0.58359, 0, 0, 0.41641, 0}, {0.28835, 0, 0, 0.50247, 0.20918}, {0.17984, 0, 0, 0.54611, 0.27405}, {0.12707, 0, 0, 0.56275, 0.31018}},
            {{0.7377, 0.2623, 0, 0, 0}, {0.28907, 0.21569, 0, 0.49524, 0}, {0.0461, 0.06632, 0, 0.53336, 0.35422}, {0.06464, 0.05069, 0, 0.43704, 0.44763}, {0.02215, 0.038, 0, 0.33631, 0.60354}},
            {{0.47406, 0.37135, 0.1546, 0, 0}, {0.1862, 0.24577, 0.15519, 0.41284, 0}, {0, 0.28343, 0.35828, 0, 0.35828}, {0, 0.20234, 0.31224, 0, 0.48542}, {0, 0.12953, 0.26546, 0, 0.605}},
            {{0.33075, 0.44563, 0.22362, 0, 0}, {0.17867, 0.20071, 0.20071, 0.41991, 0}, {0, 0.30849, 0.43234, 0, 0.25916}, {0, 0.21836, 0.39082, 0, 0.39082}, {0, 0.14328, 0.33659, 0, 0.52013}},
            {{0.24032, 0.48974, 0.26994, 0, 0}, {0.14807, 0.15668, 0.27756, 0.41769, 0}, {0, 0.26804, 0.53575, 0, 0.19621}, {0, 0.22106, 0.48124, 0, 0.2977}, {0, 0.15411, 0.42294, 0, 0.42294}}
        };


};

#endif // !__CBETA_PLAYER_HPP__

Wszędzie brakuje mi komentarza, więc nie mogę jeszcze zadawać pytań. Jest to więc bardzo prosty gracz, aby wygrać z pierwszym botem.

[Edytuj] Dzięki, teraz poprzedni status nie jest już prawdziwy, ale myślę, że lepiej go zachować, abyśmy mogli zrozumieć kontekst tego bota.

The Opportunist

Oportunista uczęszcza do tego samego klubu strzelców, co GunClubPlayers, jednak obstawił nowego gracza, że ​​może pokonać każdego GunClubPlayers. Wykorzystuje więc nawyk, który od dawna zauważył i zmusza się, aby nie strzelać, ale tylko chwilę poczekać, aby wygrać.

#ifndef __OPPORTUNIST_PLAYER_HPP__
#define __OPPORTUNIST_PLAYER_HPP__

#include <string>
#include <vector>

class OpportunistPlayer final: public Player
{
public:
    OpportunistPlayer(size_t opponent = -1) : Player(opponent) {}

public:
    virtual Action fight()
    {
        switch (getTurn() % 3)
        {
        case 0:
            return load();
            break;
        case 1:
            return metal();
            break;
        case 2:
            return bullet();
            break;
        }
        return plasma();
    }
};
#endif // !__OPPORTUNIST_PLAYER_HPP__

The BarricadePlayer

Gracz barykady ładuje pocisk w pierwszej rundzie, a następnie utrzymuje odpowiednią tarczę (wciąż nieco losową). Ładuje również kolejny strzał co 5 rundę. W każdej rundzie istnieje 15% szansy na zignorowanie algorytmu (z wyjątkiem przeładowania pierwszej tury) i wystrzelenie kuli. Kiedy wróg nie ma amunicji, ładuje się. Jeśli jakoś wszystko pójdzie nie tak, chłopcze, on po prostu strzela.

Najnowsze zmiany:

Poprawione losowe liczby (dzięki Frenzy Li).

// BarricadePlayer by devRicher
// PPCG: http://codegolf.stackexchange.com/a/104909/11933

// BarricadePlayer.hpp
// A very tactical player.

#ifndef __BARRICADE_PLAYER_HPP__
#define __BARRICADE_PLAYER_HPP__

#include "Player.hpp"
#include <cstdlib>
#include <ctime>

class BarricadePlayer final : public Player
{
public:
    BarricadePlayer(size_t opponent = -1) : Player(opponent) {}

public:
    virtual Action fight()
    {
        srand(time(NULL));
        if (getTurn() == 0) { return load(); }
        int r = GetRandomInteger(99) + 1; //Get a random
        if ((r <= 15) && (getAmmo() > 0)) { return bullet(); } //Override any action, and just shoot
        else
        {
            if (getTurn() % 5 == 0) //Every first and fifth turn
                return load();
            if (getAmmoOpponent() == 1) return metal();
            if (getAmmoOpponent() > 1) { return r <= 50 ? metal() : thermal(); }
            if (getAmmoOpponent() == 0) return load();

        }
        return bullet();
    }
};

#endif // !__BARRICADE_PLAYER_HPP__

The StudiousPlayer

Uważny gracz bada swoją ofiarę, modelując każdego napotkanego przeciwnika. Gracz zaczyna od podstawowej strategii losowo kierowanej miejscami i przechodzi do prostych strategii adaptacyjnych opartych na częstych pomiarach reakcji przeciwnika. Wykorzystuje prosty model przeciwników oparty na ich reakcji na kombinacje amunicji.

#ifndef __STUDIOUS_PLAYER_H__
#define __STUDIOUS_PLAYER_H__

#include "Player.hpp"
#include <unordered_map>

class StudiousPlayer final : public Player
{
public:
   using Player::GetRandomInteger;
   // Represents an opponent's action for a specific state.
   struct OpponentAction {
      OpponentAction(){}
      unsigned l=0;
      unsigned b=0;
      unsigned p=0;
      unsigned m=0;
      unsigned t=0;
   };
   // StudiousPlayer models every opponent that it plays,
   // and factors said model into its decisions.
   //
   // There are 16 states, corresponding to
   // 4 inner states (0,1,2,3) and 4 outer states
   // (0,1,2,3). The inner states represent our
   // (SP's) ammo; the outer represents the
   // Opponent's ammo.  For the inner or outer
   // states, 0-2 represent the exact ammo; and
   // 3 represents "3 or more".
   //
   // State n is (4*outer)+inner.
   //
   // State 0 itself is ignored, since we don't care
   // what action the opponent takes (we always load);
   // thus, it's not represented here.
   //
   // os stores states 1 through 15 (index 0 through 14).
   struct Opponent {
      std::vector<OpponentAction> os;
      Opponent() : os(15) {}
   };
   StudiousPlayer(size_t opponent)
      : Player(opponent)
      , strat(storedLs()[opponent])
      , ammoOpponent()
   {
   }
   Player::Action fight() {
      // Compute the current "ammo state".
      // For convenience here (aka, readability in switch),
      // this is a two digit octal number.  The lso is the
      // inner state, and the mso the outer state.
      unsigned ss,os;
      switch (ammoOpponent) {
      default: os=030; break;
      case 2 : os=020; break;
      case 1 : os=010; break;
      case 0 : os=000; break;
      }
      switch (getAmmo()) {
      default: ss=003; break;
      case 2 : ss=002; break;
      case 1 : ss=001; break;
      case 0 : ss=000; break;
      }
      // Store the ammo state.  This has a side effect
      // of causing actn() to return an OpponentAction
      // struct, with the opponent's history during this
      // state.
      osa = os+ss;
      // Get the opponent action pointer
      const OpponentAction* a=actn(osa);
      // If there's no such action structure, assume
      // we're just supposed to load.
      if (!a) return load();
      // Apply ammo-state based strategies:
      switch (osa) {
      case 001:
         // If opponent's likely to load, shoot; else load
         if (a->l > a->m) return bullet();
         return load();
      case 002:
      case 003:
         // Shoot in the way most likely to kill (or randomly)
         if (a->t > a->m+a->l) return bullet();
         if (a->m > a->t+a->l) return plasma();
         if (GetRandomInteger(1)) return bullet();
         return plasma();
      case 010:
         // If opponent tends to load, load; else defend
         if (a->l > a->b) return load();
         return metal();
      case 011:
         // Shoot if opponent tends to load
         if (a->l > a->b+a->m) return bullet();
         // Defend if opponent tends to shoot
         if (a->b > a->l+a->m) return metal();
         // Load if opponent tends to defend
         if (a->m > a->b+a->l) return load();
         // Otherwise randomly respond
         if (!GetRandomInteger(2)) return metal();
         if (!GetRandomInteger(1)) return load(); 
         return bullet();                         
      case 012:
      case 013:
         // If opponent most often shoots, defend
         if (a->b > a->l+a->m+a->t) return metal();
         // If opponent most often thermals, use bullet
         if (a->t > a->m) return bullet();
         // If opponent most often metals, use plasma
         if (a->m > a->t) return plasma();
         // Otherwise use a random weapon
         return (GetRandomInteger(1))?bullet():plasma();
      case 020:
         // If opponent most often loads or defends, load
         if (a->l+a->m+a->t > a->b+a->p) return load();
         // If opponent most often shoots bullets, raise metal
         if (a->b > a->p) return metal();
         // If opponent most often shoots plasma, raise thermal
         if (a->p > a->b) return thermal();
         // Otherwise raise random defense
         return (GetRandomInteger(1))?metal():thermal();
      case 021:
      case 031:
         // If opponent loads more often than not,
         if (a->l > a->m+a->b+a->p) {
            // Tend to shoot (67%), but possibly load (33%)
            return (GetRandomInteger(2))?bullet():load();
         }
         // If opponent metals more often than loads or shoots, load
         if (a->m > a->l+a->b+a->p) return load();
         // If opponent thermals (shrug) more often than loads or shoots, load
         if (a->t > a->l+a->b+a->p) return load();
         // If opponent tends to shoot bullets, raise metal
         if (a->b > a->p) return metal();
         // If opponent tends to shoot plasma, raise thermal
         if (a->p > a->b) return thermal();
         // Raise random shield
         return (GetRandomInteger(2))?metal():thermal();
      case 022:
         // If opponent loads or thermals more often than not, shoot bullet
         if (a->l+a->t > a->b+a->p+a->m) return bullet();
         // If opponent loads or metals more often than not, shoot plasma
         if (a->l+a->m > a->b+a->p+a->t) return plasma();
         // If opponent shoots more than loads or defends, defend
         if (a->b+a->p > a->l+a->m+a->t) {
            if (a->b > a->p) return metal();
            if (a->p > a->b) return thermal();
            return (GetRandomInteger(1))?metal():thermal();
         }
         // If opponent defends more than opponent shoots, load
         if (a->m+a->t > a->b+a->p) return load();
         // Use random substrategy;
         // load(33%)
         if (GetRandomInteger(2)) return load();
         // defend(33%)
         if (GetRandomInteger(1)) {
            if (a->b > a->p) return metal();
            if (a->b > a->b) return thermal();
            return (GetRandomInteger(1))?metal():thermal();
         }
         // Shoot in a way that most often kills (or randomly)
         if (a->m > a->t) return plasma();
         if (a->t > a->m) return bullet();
         return (GetRandomInteger(1))?bullet():plasma();
      case 023:
         // If opponent loads or raises thermal more often than not, shoot bullets
         if (a->l+a->t > a->b+a->p+a->m) return bullet();
         // If opponent loads or raises metal more often than not, shoot plasma
         if (a->l+a->m > a->b+a->p+a->t) return plasma();
         // If opponent shoots more than loads or defends, defend
         if (a->b+a->p > a->l+a->m+a->t) {
            if (a->b > a->p) return metal();
            if (a->p > a->b) return thermal();
            return (GetRandomInteger(1))?metal():thermal();
         }
         // If opponent defends more than shoots, shoot
         if (a->m+a->t > a->b+a->p) {
            if (a->m > a->t) return plasma();
            if (a->t > a->m) return bullet();
            return GetRandomInteger(1)?bullet():plasma();
         }
         // 50% defend
         if (GetRandomInteger(1)) {
            if (a->b > a->p) return metal();
            return thermal();
         }
         // 50% shoot
         if (a->m > a->t) return plasma();
         if (a->t > a->m) return bullet();
         return (GetRandomInteger(1))?bullet():plasma();
      case 030:
         // If opponent loads or shields more often than not, load
         if (a->l+a->m+a->t > a->b+a->p) return load();
         // If opponent tends to shoot, defend
         if (a->b+a->p >= a->l+a->m+a->t) {
            if (a->b > a->p) return metal();
            if (a->p > a->b) return thermal();
            return (GetRandomInteger(1))?metal():thermal();
         }
         // Otherwise, randomly shield (50%) or load
         if (GetRandomInteger(1)) {
            return (GetRandomInteger(1))?metal():thermal();
         }
         return load();
      case 032:
         // If opponent loads or thermals more often than not, shoot bullets
         if (a->l+a->t > a->b+a->p+a->m) return bullet();
         // If opponent loads or metals more often than not, shoot plasma
         if (a->l+a->m > a->b+a->p+a->t) return plasma();
         // If opponent shoots more often than loads or shields, defend
         if (a->b+a->p > a->l+a->m+a->t) {
            if (a->b > a->p) return metal();
            if (a->p > a->b) return thermal();
            return (GetRandomInteger(1))?metal():thermal();
         }
         // If opponent shields more often than shoots, load
         if (a->m+a->t > a->b+a->p) return load();
         // Otherwise use random strategy
         if (GetRandomInteger(2)) return load();
         if (GetRandomInteger(1)) {
            if (a->b > a->p) return metal();
            return thermal();
         }
         if (a->m > a->t) return plasma();
         if (a->t > a->m) return bullet();
         return (GetRandomInteger(1))?bullet():plasma();
      case 033:
         {
            // At full 3 on 3, apply random strategy
            // weighted by opponent's histogram of this state...
            // (the extra 1 weights towards plasma)
            unsigned sr=
               GetRandomInteger
               (a->l+a->t+a->p+a->b+a->m+1);
            // Shoot bullets proportional to how much
            // opponent loads or defends using thermal
            if (sr < a->l+a->t) return bullet();
            sr-=(a->l+a->t);
            // Defend with thermal proportional to how
            // much opponent attacks with plasma (tending to
            // waste his ammo)
            if (sr < a->p) return thermal();
            // Shoot plasma proportional to how
            // much opponent shoots bullets or raises metal
            return plasma();
         }
      }
      // Should never hit this; but rather than ruin everyone's fun,
      // if we do, we just load
      return load();
   }
   // Complete override; we use our opponent's model, not history.
   void perceive(Player::Action action) {
      // We want the ammo but not the history; since
      // the framework (Player::perceive) is "all or nothing", 
      // StudiousPlayer just tracks the ammo itself
      switch (action) {
      default: break;
      case Player::LOAD:   ++ammoOpponent; break;
      case Player::BULLET: --ammoOpponent; break;
      case Player::PLASMA: ammoOpponent-=2; break;
      }
      // Now we get the opponent's action based
      // on the last (incoming) ammo state
      OpponentAction* a = actn(osa);
      // ...if it's null just bail
      if (!a) return;
      // Otherwise, count the action
      switch (action) {
      case Player::LOAD    : ++a->l; break;
      case Player::BULLET  : ++a->b; break;
      case Player::PLASMA  : ++a->p; break;
      case Player::METAL   : ++a->m; break;
      case Player::THERMAL : ++a->t; break;
      }
   }
private:
   Opponent& strat;
   OpponentAction* actn(unsigned octalOsa) {
      unsigned ndx = (octalOsa%4)+4*(octalOsa/8);
      if (ndx==0) return 0;
      --ndx;
      if (ndx<15) return &strat.os[ndx];
      return 0;
   }
   unsigned osa;
   unsigned ammoOpponent;
   // Welcome, non-C++ persons, to the "Meyers style singleton".
   // "theMap" is initialized (constructed; initially empty)
   // the first time the declaration is executed.
   static std::unordered_map<size_t, Opponent>& storedLs() {
      static std::unordered_map<size_t, Opponent> theMap;
      return theMap;
   }
};

#endif

Zauważ, że śledzi to informacje o przeciwnikach zgodnie z regułami wyzwania; zobacz metodę „Meyers style singleton” „scoped” przechowywane Ls () na dole. (Niektórzy zastanawiali się, jak to zrobić; teraz już wiesz!)

The GunClubPlayer

Wytnij z pierwotnego pytania. To służy jako przykład minimalistycznej implementacji odtwarzacza pochodnego. Ten gracz weźmie udział w turnieju.

Do GunClubPlayers, aby przejść do klubu pistoletu. Podczas każdego pojedynku najpierw ładowali amunicję, a następnie strzelali kulą i powtarzali ten proces do końca pojedynku na świecie . Nie obchodzi ich to, czy wygrają, czy nie, i koncentrują się wyłącznie na przyjemnym doświadczeniu.

// GunClubPlayer.hpp
// A gun club enthusiast. Minimalistic example of derived class

#ifndef __GUN_CLUB_PLAYER_HPP__
#define __GUN_CLUB_PLAYER_HPP__

#include "Player.hpp"

class GunClubPlayer final: public Player
{
public:
    GunClubPlayer(size_t opponent = -1) : Player(opponent) {}

public:
    virtual Action fight()
    {
        return getTurn() % 2 ? bullet() : load();
    }
};

#endif // !__GUN_CLUB_PLAYER_HPP__

The PlasmaPlayer

Gracz plazmowy lubi strzelać pociskami plazmowymi. Spróbuje załadować i wystrzelić jak najwięcej. Jednakże, podczas gdy przeciwnik ma amunicję plazmową, użyje swojej osłony termicznej (pociski są dla słabych).

#ifndef __PLASMA_PLAYER_HPP__
#define __PLASMA_PLAYER_HPP__

#include "Player.hpp"

class PlasmaPlayer final : public Player
{
public:
    PlasmaPlayer(size_t opponent = -1) : Player(opponent) {}

    virtual Action fight()
    {
        // Imma Firin Mah Lazer!
        if (getAmmo() > 1) return plasma();

        // Imma Block Yur Lazer!
        if (getAmmoOpponent() > 1) return thermal();

        // Imma need more Lazer ammo
        return load();
    }
};

#endif // !__PLASMA_PLAYER_HPP__

Bardzo SadisticShooter

Wolałby patrzeć, jak cierpisz, niż zabijać. Nie jest głupi i zakryje się w razie potrzeby.

Jeśli jesteś całkowicie nudny i przewidywalny, zabije cię od razu.

// SadisticShooter by muddyfish
// PPCG: http://codegolf.stackexchange.com/a/104947/11933

// SadisticShooter.hpp
// A very sad person. He likes to shoot people.

#ifndef __SAD_SHOOTER_PLAYER_HPP__
#define __SAD_SHOOTER_PLAYER_HPP__

#include <cstdlib>
#include "Player.hpp"
// #include <iostream>

class SadisticShooter final : public Player
{
public:
    SadisticShooter(size_t opponent = -1) : Player(opponent) {}
private:
    bool historySame(std::vector<Action> const &history, int elements) {
        if (history.size() < elements) return false;

        std::vector<Action> lastElements(history.end() - elements, history.end());

        for (Action const &action : lastElements)
            if (action != lastElements[0]) return false;
        return true;
    }
public:
    virtual Action fight()
    {
        int my_ammo = getAmmo();
        int opponent_ammo = getAmmoOpponent();
        int turn_number = getTurn();
        //std::cout << " :: Turn " << turn_number << " ammo: " << my_ammo << " oppo: " << opponent_ammo << std::endl;

        if (turn_number == 90) {
            // Getting impatient
            return load();
        }
        if (my_ammo == 0 && opponent_ammo == 0) {
            // It would be idiotic not to load here
            return load();
        }
        if (my_ammo >= 2 && historySame(getHistoryOpponent(), 3)) {
            if (getHistoryOpponent()[turn_number - 1] == THERMAL) return bullet();
            if (getHistoryOpponent()[turn_number - 1] == METAL) return thermal();
        }
        if (my_ammo < 2 && opponent_ammo == 1) {
            // I'd rather not die thank you very much
            return metal();
        }
        if (my_ammo == 1) {
            if (opponent_ammo == 0) {
                // You think I would just shoot you?
                return load();
            }
            if (turn_number == 2) {
                return thermal();
            }
            return bullet();
        }
        if (opponent_ammo >= 2) {
            // Your plasma weapon doesn't scare me
            return thermal();
        }
        if (my_ammo >= 2) {
            // 85% more bullet per bullet
            if (turn_number == 4) return bullet();
            return plasma();
        }
        // Just load the gun already
        return load();
    }
};

#endif // !__SAD_SHOOTER_PLAYER_HPP__

The TurtlePlayer

TurtlePlayerjest tchórzem. Większość czasu ukrywa się za tarczami - stąd nazwa. Czasami może wyjść ze swojej skorupy (bez zamierzonej gry słów) i oddać strzał, ale zwykle leży nisko, podczas gdy wróg ma amunicję.

Ten bot nie jest szczególnie świetny - jednak każdy KOTH potrzebuje kilku początkowych wpisów, aby go uruchomić :)

Badania wykazały, że to lokalny wygrywa zarówno przed GunClubPlayeri Opportunist100% czasu. Bitwa przeciwko BotRobotPlayerzawsze wydawała się remisem, ponieważ obaj chowali się za tarczami.

#include "Player.hpp"

// For randomness:
#include <ctime>
#include <cstdlib>

class TurtlePlayer final : public Player {

public:
    TurtlePlayer(size_t opponent = -1) : Player(opponent) { srand(time(0)); }

public:
    virtual Action fight() {
        if (getAmmoOpponent() > 0) {
            // Beware! Opponent has ammo!

            if (rand() % 5 == 0 && getAmmo() > 0) 
                // YOLO it:
                return getAmmo() > 1 ? plasma() : bullet();

            // Play it safe:
            if (getAmmoOpponent() == 1) return metal();
            return rand() % 2 ? metal() : thermal();
        }

        if (getAmmo() == 0) 
            // Nobody has ammo: Time to load up.
            return load();

        else if (getAmmo() > 1) 
            // We have enough ammo for a plasma: fire it!
            return plasma();

        else 
            // Either load, or take a shot.
            return rand() % 2 ? load() : bullet();
    }
};