In dieser Frage wurde ein Spiel entwickelt, in dem sich die Spieler im Gefangenendilemma paarweise gegenüberstehen, um zu bestimmen, welche iterative Strategie die höchste Punktzahl gegen andere erzielt.

In dieser Frage habe ich mir eine Möglichkeit ausgedacht, mit der mehrere Personen gleichzeitig das Gefangenendilemma gegeneinander spielen können. Bei dieser Variante ist die Auszahlungsmatrix nicht erforderlich, wobei jedes Ergebnis zwischen jedem Paar von zwei Spielern die Summe von zwei funktional unabhängigen Entscheidungen ist.

Ihre Aufgabe ist es, eine KI zu bauen, um diese symmetrische, verallgemeinerte Version des Mehrspieler-Gefangenendilemmas zu spielen, die die höchstmögliche Punktzahl erzielt.

Spielregeln

In jeder Runde dieses Multiplayer-Mehrrunden-Gefangenen-Dilemmas kann sich ein Spieler Aentscheiden, von einem anderen Spieler "1" zu nehmen B. Unter diesen Umständen Aerhöht sich die Punktzahl um 1, während sich Bdie Punktzahl um 2 verringert. Diese Entscheidung kann zwischen jedem bestellten Spielerpaar getroffen werden.

Dies ist die einzige Entscheidung, die für jeden Spieler getroffen wird - entweder "nimm 1" oder nicht "nimm 1" von jedem anderen Spieler, der für die Übergabe bzw. die Zusammenarbeit homolog ist. Die effektive Auszahlungsmatrix zwischen zwei Spielern P1und P2sieht wie folgt aus :

  P1/P2     P1 Take1   P1 Don't
P2 Take1     -1/-1      -2/+1
P2 Don't     +1/-2       0/ 0

Turnierablauf

Das Spiel besteht aus P * 25Runden, in denen Pdie Anzahl der teilnehmenden Spieler angegeben ist. Alle Spieler beginnen mit einer Punktzahl von 0. Jede Runde besteht aus dem folgenden Verfahren:

Zu Beginn einer Runde erhält jedes Programm eine Historie der vorherigen Runden aus der Standardeingabe in folgendem Format:

• Eine Zeile , die 3 Zahlen P, Dund N.

  • Pist die Gesamtzahl der Spieler im Spiel. Jedem Spieler wird 1zu PBeginn des Spiels nach dem Zufallsprinzip eine ID-Nummer von bis zugewiesen .

  • D ist die ID des aktuellen Spielers.

  • N ist die Anzahl der Runden, die gespielt wurden.

• NLinien, wobei jede Linie die Ergebnisse einer Runde darstellt. In Zeile kvon N, wird es einige Zahl sein n_kgeordneter Paare (a, b)durch Zwischenräume getrennt, die darstellen , dass der Spieler mit der ID avon dem Spieler „1 nahm“ mit der ID bin dieser Runde.

• Eine gleichmäßig zufällige Zahl Rvon 0bis 18446744073709551615(2 ⁶⁴ - 1), die als Pseudozufallskeim fungiert. Diese Zahlen werden aus einer vorgenerierten Datei gelesen, die am Ende des Turniers veröffentlicht wird, damit die Teilnehmer die Ergebnisse selbst überprüfen können.

• Eine zusätzliche Zeile, die eine Art von Status darstellt, der in Ihr Programm eingelesen werden soll, wenn Ihr Programm in der vorherigen Runde eine solche Ausgabe erzeugt hat. Zu Beginn des Spiels ist diese Zeile immer leer. Diese Zeile wird weder vom Scoring-Code noch von anderen Programmen geändert.

Jedes Programm verwendet dann seine Strategie, um Folgendes für die Standardausgabe zu erzeugen :

• Eine Liste von KZahlen, die die IDs der Programme sind, die von dieser Runde "1" erhalten. Eine leere Ausgabe bedeutet, dass sie nichts bewirkt.

• Optional eine zusätzliche Zeile, die eine Art von Status darstellt, der an spätere Runden weitergegeben werden soll. Diese genaue Zeile wird in der nächsten Runde an das Programm zurückgemeldet.

Nachfolgend finden Sie ein Eingabebeispiel für den Beginn des Spiels für einen Spieler mit Ausweis 3in einem 4-Spieler-Spiel:

4 3 0
4696634734863777023

Nachfolgend finden Sie eine Beispieleingabe für dasselbe Spiel mit einigen bereits gespielten Runden:

4 3 2
(1, 2) (1, 3) (1, 4) (4, 2)
(1, 3) (2, 1) (2, 4) (3, 1) (4, 1)
4675881156406346380

Jedes Programm erhält für eine Runde genau die gleiche Eingabe, mit Ausnahme der ID-Nummer, Ddie für jedes Programm eindeutig ist.

Unten sehen Sie eine Beispielausgabe, in der der Spieler 3von allen anderen eine 1 nimmt:

1 2 4

Am Ende aller erforderlichen Runden gewinnt der Spieler mit der höchsten Endpunktzahl.

Zeitleiste

Die Kodierung für dieses Turnier dauert insgesamt 7 Tage. Einsendeschluss ist 2014-05-09 00:00 UTC.

Veröffentlichen Sie keine aktuellen Programme vor diesem Datum. Veröffentlichen Sie den SHA256-Hash des Quellcodes Ihres Programms als Verpflichtung. Sie können diesen Hash jederzeit vor Ablauf der Frist ändern, nach Ablauf der Frist eingegangene Verpflichtungen werden jedoch nicht zur Entscheidung angenommen. (Bitte benutzen Sie die Basis 64 Notation für Ihre Hashes, da mein Verifizierungsprogramm die Basis 64 ausspuckt und es eine kompaktere Notation ist.)

Nach Ablauf der Frist haben Sie 1 Tag (bis 2014-05-10 00:00 UTC) Zeit, um den tatsächlichen Quellcode Ihres Programms für Ihre Einreichung zu veröffentlichen. Wenn der SHA256-Hash Ihres veröffentlichten Quellcodes mit keinem Hash übereinstimmt, den Sie vor Ablauf der Frist veröffentlicht haben, wird Ihr Code nicht in das Turnier aufgenommen.

Danach lade ich alle Einsendungen auf meinen eigenen Computer herunter und führe alle Turnierteilnahmen in diesem Battle Royale durch. Hoffentlich veröffentliche ich die Ergebnisse innerhalb von 2 Tagen 2014-05-12 00:00 UTC.

Ich werde die Antwort mit der höchsten Punktzahl akzeptieren und dieser Antwort eine Prämie von +100 gewähren, wenn ihre endgültige Punktzahl größer als ist 0.

Nach dem Ende des Turniers werde ich die zufällige Startdatei veröffentlichen, die zur Durchführung des Wettbewerbs verwendet wurde, und möglicherweise werden andere Lösungen veröffentlicht, die versuchen, die im Turnier verwendeten zu übertreffen. Sie zählen jedoch nicht für die Annahme oder das Kopfgeld.

Die Host-Maschine

Ich werde diese Lösungen auf einer virtuellen Maschine auf meinem Computer ausführen. Auf dieser virtuellen Maschine wird Ubuntu Linux 14.04 mit 2 Gigabyte RAM ausgeführt. Mein Basiscomputer verfügt über einen Intel i7-2600K-Prozessor mit 3,40 GHz.

Bedarf

Ihr Programm muss in einer Sprache geschrieben sein, für die es einen Compiler oder Interpreter gibt, der Ihr Programm kompiliert, und der für die neueste Version von Ubuntu Linux verfügbar ist, damit ich alle Einsendungen ausführen und sie in einer virtuellen Maschine beurteilen kann.

Ihr Programm darf nicht mehr als 2.000 secondseine Runde dauern . Wenn Ihr Programm keine Zeit mehr hat oder einen Fehler erzeugt, wird die Ausgabe für diese Runde als leer betrachtet.

Ihr Programm muss deterministisch sein; Das heißt, es muss immer dieselbe Ausgabe für dieselbe Eingabe zurückgegeben werden. Pseudozufallslösungen sind zulässig; Ihre Zufälligkeit muss jedoch von dem zufälligen Startwert abhängen, der ihr als Eingabe gegeben wird, und von nichts anderem. Die Seed-Datei wurde mit Python's generiert os.urandom. Es enthält insgesamt 500 Zeilen (bei Bedarf werden weitere Zeilen generiert) und der SHA256-Hash lautet K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. Sobald das Turnier vorbei ist, wird es hier hochgeladen.

Pflanzen

Zum Auftakt gibt es vier "Pflanzen", die anfängliche naive Strategien darstellen. Diese werden zusammen mit Ihren Einsendungen im Turnier gespielt. In dem unwahrscheinlichen Fall, dass einer von ihnen gewinnt, wird die höchste Punktzahl eines anderen Spielers als einer Pflanze als Sieger gewertet.

Um den Hash jeder Pflanzendatei zu berechnen, ersetzen Sie jede Gruppe von 4 Leerzeichen mit einem Tabulator, da der Formatierer hier keine Tabulatorzeichen zu mögen scheint.

Der Faule - macht nie etwas.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

The Greedy - nimmt immer 1 von allen anderen.

+k0L8NF27b8+Xf50quRaZFFuflZhZuTCQOR5t5b0nMI=

import sys

line1 = sys.stdin.readline()
n = [int(i) for i in line1.split()]
for i in range(n[0]):
    if i+1 != n[1]:
        print i+1,
print

The Wrathful - nimmt 1 von allen anderen in der ersten Runde und 1 von allen, die danach in der vorherigen Runde 1 davon genommen haben.

Ya2dIv8TCh0zWzRfzUIdFKWj1DF9GXWhbq/uN7+CzrY=

import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        lines.append(sys.stdin.readline())
    lastline = lines[-1]
    takes = re.findall(r'\([0-9]+, [0-9]+\)', lastline)
    for take in takes:
        sides = [int(i) for i in re.findall(r'[0-9]+', take)]
        if sides[1] == pid:
            print sides[0],
    print

The Envious - Nimmt 1 von den 50% der Spieler mit der aktuell höchsten Punktzahl ohne sich selbst und rundet ab.

YhLgqrz1Cm2pEcFlsiIL4b4MX9QiTxuIOBJF+wvukNk=

import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []
scores = [0] * players

if rounds == 0:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        takes = re.findall(r'\([0-9]+, [0-9]+\)', sys.stdin.readline())
        for take in takes:
            sides = [int(i) for i in re.findall(r'[0-9]+', take)]
            scores[sides[0] - 1] += 1
            scores[sides[1] - 1] -= 2
    score_pairs = [(i+1, scores[i]) for i in range(players)]
    score_pairs.sort(key=lambda x:(x[1], x[0]))
    score_pairs.reverse()
    taken = 0
    j = 0
    while taken < (players) / 2:
        if score_pairs[j][0] != pid:
            print score_pairs[j][0],
            taken += 1
        j += 1

In einem Turnier mit 100 Runden erhalten sie unter diesen vier Punkten:

Lazy: -204
Greedy: -100
Wrathful: -199
Envious: -199

Bewertungsprogramm

Ich habe das Richterprogramm veröffentlicht, das ich bei Github verwenden werde . Laden Sie es herunter und testen Sie es. (Und vielleicht ein oder zwei Fehler beheben, wenn Sie einen finden.: P)

Es gibt momentan keine Kompilierungsoptionen für etwas anderes als Python. Ich werde diese später einbeziehen - wenn die Leute Zusammenstellungs- oder Interpretationsskripte für andere Sprachen beisteuern könnten, wäre ich sehr dankbar.

Phase 2: Einreichung des Quellcodes

Ich habe tournamentfür den Wettbewerb einen neuen Zweig ins Github-Repository gestellt, der die Datei pd_rand und andere Pflanzeneinträge enthält. Sie können Ihren Quellcode entweder hier veröffentlichen oder als Pull-Anfrage an diese Filiale senden.

Die Reihenfolge der Teilnehmer ist wie folgt:

'begrudger'
'regular'
'patient'
'lazy'
'backstab'
'bully'
'lunatic'
'envious'
'titfortat'
'greedy'
'wrathful'
'judge'
'onepercent'

Endergebnisse

Die Ausgabe meines Testprogramms:

Final scores:
begrudger -2862
regular -204
patient -994
lazy -2886
backstab -1311
bully -1393
lunatic -1539
envious -2448
titfortat -985
greedy -724
wrathful -1478
judge -365
onepercent -1921

Ranglisten:

 1. regular      -204
 2. judge        -365
 3. greedy       -724
 4. titfortat    -985
 5. patient      -994
 6. backstab    -1311
 7. bully       -1393
 8. wrathful    -1478
 9. lunatic     -1539
10. onepercent  -1921
11. envious     -2448
12. begrudger   -2862
13. lazy        -2886

Es stellt sich also heraus, dass der Gewinner tatsächlich ein Spieler ist - es ist The Regular mit -204 Punkten!

Leider war die Punktzahl nicht positiv, aber wir können kaum erwarten, dass in einer Simulation des Dilemmas des Iterierten Gefangenen, in dem alle spielen, um zu gewinnen.

Einige überraschende Ergebnisse (zumindest, was ich für überraschend hielt):

• Der Gierige erzielte mehr als Tit für Tat, und in der Tat im Allgemeinen höher als die meisten Torschützen überhaupt.

• Der Richter, der eigentlich eine Art "Moral-Vollstrecker" sein sollte (im Grunde genommen hat er 1 von demjenigen genommen, der 1 von einem überdurchschnittlich oft genommen hatte), erzielte ziemlich hohe Punkte, während dies bei Simulationstests tatsächlich der Fall war bekomme eine eher niedrige Punktzahl.

Und andere, die (ich dachte) nicht so überraschend waren:

• Der Patient erzielte volle 484 Punkte mehr als The Wrathful. Es lohnt sich wirklich, das erste Mal zusammenzuarbeiten.

• Ein Prozent hatte sehr schnell fast niemanden zu treten, während sie unten waren. Scheint, dass die 1% nur so bleiben können, weil sie mehr Spieler im Spiel haben.

Jetzt, da das Turnier vorbei ist, können Sie so viele zusätzliche Spieler einstellen, wie Sie möchten, und mit ihnen mithilfe des Richterprogramms herumprobieren.

Das regelmäßige

Die Version dieses Eintrags, die ich für das Turnier ausgewählt habe (SHA-256 :) , ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc=verwendet Joeys " Random Sucker " -Strategie (allerdings mit einer geringfügigen und wahrscheinlich unbedeutenden Änderung), die im letzten Wettbewerb den zweiten Platz belegte. Leider hat eine neuere, effektivere Version nur 3 Minuten und 25 Sekunden vor Ablauf der Frist einen schwerwiegenden Fehler gemeldet, sodass sie nicht verwendet werden konnte. Trotzdem schneidet diese Version noch relativ gut ab.

<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
    }
}

$hashOutput = rtrim(fgets(STDIN), "\n");
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => ''];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ( $other === $myPlayerId) {
            continue;
        }

        if ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

Die Buggy-Version hat einen SHA-256-Hash von 2hNVloFt9W7/uA5aQXg+naG9o6WNmrZzRf9VsQNTMwo=:

<?php

$secretKey = '95CFE71F76CF4CD2';
$hashOutput = '';
$hashSeq = 0;
$hashIndex = 64;

function psRand($min = null, $max = null) {
    global $secretKey, $state, $hashOutput, $hashSeq, $hashIndex;
    if ($hashIndex > 56) {
        $hashOutput = hash_hmac('sha256', ++$hashSeq . ' ' . $state['rand'], $secretKey);
        $hashIndex = 0;
    }

    $num = (int)(hexdec(substr($hashOutput, $hashIndex, 8)) / 2);
    $hashIndex += 8;

    return $min === null ? $num : (int)($min + $num * ($max - $min + 1) / 2147483648);
}

$line = fgets(STDIN);
sscanf($line, "%d %d %d", $numPlayers, $myPlayerId, $roundsPlayed);
$roundsCount = 25 * $numPlayers;
$roundsRemaining = $roundsCount - $roundsPlayed - 1;

$betrayalCount = array_fill(1, $numPlayers, 0);
$scoreWindow = array_fill(1, $numPlayers, array_fill(1, $numPlayers, 0));
$lastMove = array_fill(1, $numPlayers, array_fill(1, $numPlayers, false));
for ($round = 0; $round < $roundsPlayed; ++$round) {
    $line = fgets(STDIN);
    preg_match_all('/\((\d+), (\d+)\)/', $line, $matches, PREG_SET_ORDER);
    foreach ($matches as $m) {
        $defector = (int)$m[1];
        $victim = (int)$m[2];
        if ($victim === $myPlayerId) {
            ++$betrayalCount[$defector];
        }
TAB>TAB>if ($round >= $roundsPlayed - 10) {
TAB>TAB>TAB>$scoreWindow[$defector][$victim] -= 2;
TAB>TAB>TAB>$scoreWindow[$victim][$defector] += 1;
TAB>TAB>}
TAB>TAB>if ($round === $roundsPlayed - 1) {
TAB>TAB>TAB>$lastMove[$defector][$victim] = true;
TAB>TAB>}
    }
}

$line .= fgets(STDIN);
$state = unserialize(rtrim(fgets(STDIN), "\n"));
if (!$state) {
    $state = ['rand' => '', 'copying' => array_fill(1, $numPlayers, 0)];
}

$state['rand'] = hash_hmac('sha256', $state['rand'] . $line, $secretKey);
$victims = [];

if ($roundsPlayed > 1) {
    for ($other = 1; $other <= $numPlayers; ++$other) {
        if ($other === $myPlayerId) {
            continue;
        }

TAB>TAB>if ($roundsPlayed >= 10) {
TAB>TAB>TAB>$myScore = $scoreWindow[$other][$myPlayerId];
TAB>TAB>TAB>foreach ($scoreWindow[$other] as $betterPlayer => $betterScore) {
TAB>TAB>TAB>TAB>if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {
TAB>TAB>TAB>TAB>TAB>$state['copying'][$other] = $betterPlayer;
TAB>TAB>TAB>TAB>}
TAB>TAB>TAB>}
TAB>TAB>}

TAB>TAB>if ($state['copying'][$other]) {
TAB>TAB>TAB>if ($lastMove[$state['copying'][$other]][$other]) {
TAB>TAB>TAB>TAB>$victims[] = $other;
TAB>TAB>TAB>}
        } elseif ($betrayalCount[$other] > 7 || psRand() % 1024 < 32 || !$roundsRemaining ) {
            $victims[] = $other;
        }
    }
}

echo implode(' ', $victims), "\n", serialize($state), "\n";

Nehmen Sie die folgenden Ersetzungen vor, um das Problem zu beheben:

• Ersetzen $hashOutput = rtrim(fgets(STDIN), "\n");durch $line .= fgets(STDIN);(nicht, dass es wirklich darauf ankommt).
• Ersetzen if ($betterScore >= 3 * $myScore) {durch if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {(das hat es getötet).

Ein Prozent

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Sieht auf die Gefangenen herab, die er unter sich betrachtet.

Nimmt einfach von jedem, der Punkte hat, die kleiner oder gleich ihm sind. Es wird davon ausgegangen, dass diese Gefangenen mit geringerer Wahrscheinlichkeit eine Gegenleistung erbringen (oder dass sie mehr haben würden). Ich weiß nicht, wie gut diese Annahme ist, aber das ist es, woran er arbeitet.

Auch nimmt jeder an der letzten Runde teil. Es gibt buchstäblich keinen Nachteil, da niemand danach rächen kann.

Wenn Sie Probleme haben, den Hash aufgrund von Tabulatoren / Leerzeichen aus eingefügtem Code abzurufen, finden Sie hier einen Link zur Datei selbst.

import java.io.BufferedReader;
import java.io.InputStreamReader;

class OnePercent {

    static int numPlayers;
    static int me;
    static int turn;
    static int[] values;

    public static void main(String[] args) {
        if(!readInput())
            return;
        String out = "";
        for(int i=1;i<values.length;i++){
            if(i != me && (values[i] <= values[me] || turn > (numPlayers*25-2)))
                out += i + " ";
        }
        out.trim();
        System.out.print(out);
    }

    static boolean readInput(){
        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String line = reader.readLine();
            if(line == null)
                return false;
            String[] tokens = line.split(" ");
            if(tokens.length < 3)
                return false;
            numPlayers = Integer.valueOf(tokens[0]);
            me = Integer.valueOf(tokens[1]);
            turn = Integer.valueOf(tokens[2]);
            values = new int[numPlayers+1];
            for(int i=0;i<values.length;i++)
                values[i]=0;

            for(int i=0;i<turn;i++){
                line = reader.readLine();
                line = line.replaceAll("[)]",",");
                line = line.replaceAll("[( ]", "");
                tokens = line.split(",");
                for(int j=0;j<tokens.length-1;j+=2){
                    int thief = Integer.valueOf(tokens[j]);
                    int poor = Integer.valueOf(tokens[j+1]);
                    if(thief<1||poor<1||thief>numPlayers||poor>numPlayers)
                        continue;
                    values[thief]++;
                    values[poor] -= 2;
                }
            }
            reader.close();
        } catch(Exception e) {
            return false;
        }
        return true;
    }

}

Hier sind noch ein paar Pflanzen, die am Spiel teilnehmen werden. Diese sind fortgeschrittener und ihr Quellcode wird erst am Ende der Codierungsphase bekannt gegeben.

Genau wie die vier Pflanzen in der Frage, wird nur die höchste Punktzahl, die ein tatsächlicher Teilnehmer erzielt, als Sieger gewertet, wenn sie es schaffen, höher als alle anderen Spieler zu punkten.

Der Tyrann

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Picks auf Menschen.

Der Richter

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Bestraft Übeltäter.

Der Wahnsinnige

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

Hat keine Ahnung was es macht.

Der Patient

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Mach niemals den ersten Schritt.

Wie du mir so ich dir

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Ähnlich wie Wrathful, mit ein paar (hoffentlich) leistungssteigernden Änderungen.

import sys
import re

line1 = [int(i) for i in sys.stdin.readline().split()]

players = line1[0]
pid = line1[1]
rounds = line1[2]

lines = []

if rounds == 0:
    print
elif rounds == 25 * players - 1:
    for i in range(players):
        if i+1 != pid:
            print i+1,
    print
else:
    for i in range(rounds):
        lines.append(sys.stdin.readline())
    lastline = lines[-1]
    takes = re.findall(r'\([0-9]+, [0-9]+\)', lastline)
    for take in takes:
        sides = [int(i) for i in re.findall(r'[0-9]+', take)]
        if sides[1] == pid:
            print sides[0],
    print

Backstab

Python 3

Trotz des Namens ist dieser Bot wirklich sehr liebenswürdig. Aber nicht abhaken.

import sys, math

inp = [int(i) for i in sys.stdin.readline().split()]
inp.append([])
for i in range(inp[2]):
    inp[3].append(
        [eval(i+')') for i in sys.stdin.readline().split(')')[:-1]]
    )
inp += sys.stdin.readline()

# inp is [P, D, N, [M1, M2...], R]

dat = [[], inp[2] % 2] # average runlength take and don't per player, parity of round

lastatk = []

for i in range(inp[0]):
    dat[0].append([])
    lastatk.append(0)

for i,r in enumerate(inp[3]): # each round
    for m in r: # each move
        if m[1] == inp[1]:
            dat[0][m[0]-1].append(i) # round num they attacked
            lastatk[m[0]-1] = i # keep track of last attack

# now that we know who attacked me when, i can do some stats

nav = []
rl = []

for i in range(inp[0]):
    nav.append([[0], False])
    rl.append([[], []]) # attack, don't

for i in range(inp[2]): # each round
    for p in range(1, inp[0]+1): # each player
        if p != inp[1]: # let's not judge ourselves
            if i in dat[0][p-1]: # p attacked me in round i
                if nav[p-1][1]: # attack chain?
                    nav[p-1][0][-1] += 1
                else: # start attack chain!
                    rl[p-1][1] += [nav[p-1][0][-1]] # copy peace chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = True
            else: # peace!
                if not nav[p-1][1]: # peace chain?
                    nav[p-1][0][-1] += 1
                else: # peace to all!
                    rl[p-1][0] += [nav[p-1][0][-1]] # copy atk chain
                    nav[p-1][0].append(1)
                    nav[p-1][1] = False

print(nav)

print(inp[3])

# now, rl has runlengths for each player.

print(rl)

rl = [[sum(i[0])/len(i[0]+[0]), sum(i[1])/len(i[1]+[0])] for i in rl]

# rl now contains the averages w/ added zero.

# So, now we have average runtime and last attack. Let's quickly make some descisions.

out = []

for p in range(1, inp[0]+1): # each player
    if p != inp[1]: # again, let's not judge ourselves
        if lastatk[p-1] == inp[0]-1: # they attacked us!
            out.append(p)
        else: # whew, we can recover
            if inp[0] - lastatk[p-1] > rl[p-1][0]: # they're due to defend!
                out.append(p)
            elif int(__import__('binascii').b2a_hex(inp[-1].encode()), 16) % 4 == 0: # 1 in 4 chance of doing this
                out.append(p) # backstab!!1!!1one!!!1!!

print(*out)

EDIT 2 : Gepostete Quelle. Yay.

EDIT : Nach einigen Tests habe ich einige Fehler behoben, die ich gefunden habe. Sie sind nicht algorithmisch, nur einige Probleme beim Lesen der Eingabe.

Der Bettler

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Code

Ich gebe zu, dass ich nicht viel Zeit damit verbracht habe ...

import sys
p, d, n, o = input().split(' ') + ['']
p, d, n = int(p), int(d), int(n)
for i in range(n):
    r = input()
    r = r[1:len(r)-1].split(') (')
    for a in r:
        if int(a.split(', ')[1]) == d and not a.split(', ')[0] in o:
            o += a.split(', ')[0] + " "

input()
print(o)