W tym pytaniu opracowano grę, w której gracze będą stawiali czoła sobie w parach w parach w Dylemacie Więźnia, aby ustalić, która strategia iteracyjna uzyskała najwyższą ocenę w porównaniu z innymi.

W tym pytaniu wymyśliłem sposób, w jaki wiele osób może jednocześnie rozgrywać przeciwko sobie Dylemat Więźniów. W tym wariancie macierz wypłat jest niepotrzebna, a każdy wynik między każdą parą dwóch graczy stanowi sumę dwóch niezależnych funkcjonalnie decyzji.

Twoim zadaniem jest zbudowanie sztucznej inteligencji, aby zagrać w tę symetryczną, uogólnioną wersję Dylematu Więźnia dla wielu graczy, która osiągnie najwyższy możliwy wynik.

Zasady gry

W każdej rundzie tego wieloosobowego dylematu Więźnia z wieloma rundami gracz Amoże zdecydować o „wzięciu 1” od innego gracza B. W tych okolicznościach Awynik wzrasta o 1, a Bwynik maleje o 2. Ta decyzja może się wydarzyć między każdą uporządkowaną parą graczy.

Jest to jedyna decyzja podjęta dla każdego gracza - albo „wziąć 1”, albo nie „wziąć 1” od drugiego gracza, którzy są odpowiednio homologiczni dla odejścia i współpracy. Efektywna macierz wypłat pomiędzy dwoma graczami P1i P2wygląda następująco:

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

Procedura turniejowa

Gra będzie się składać z P * 25rund, w których Pjest liczba uczestniczących graczy. Wszyscy gracze zaczynają od wyniku 0. Każda runda będzie składać się z następującej procedury:

Na początku rundy każdy program otrzyma historię poprzednich rund ze standardowego wejścia , w następującym formacie:

• Jedna linia zawiera 3 numery, P, D, i N.

  • Pto całkowita liczba graczy w grze. Każdy gracz jest losowo przypisany numer identyfikacyjny od 1celu Pna początku gry.

  • D to identyfikator bieżącego gracza.

  • N to liczba rozegranych rund.

• Nlinie, każda linia reprezentująca wyniki rundy. W linii kz N, będzie kilka liczba n_kzamówionych par (a, b), oddzielonych spacjami, które stanowią, że gracz z ID a„wziął 1” od gracza z ID bw tej rundzie.

• Jednolicie losowa liczba Rod 0do 18446744073709551615(2 ⁶⁴ - 1), która działa jak ziarno pseudolosowe. Liczby te zostaną odczytane z wstępnie wygenerowanego pliku, który zostanie wydany pod koniec turnieju, aby ludzie mogli sami zweryfikować wyniki.

• Jedna dodatkowa linia, która reprezentuje jakąś formę stanu do odczytania w twoim programie, jeśli twój program wytworzył takie wyjście w poprzedniej rundzie. Na początku gry ta linia będzie zawsze pusta. Ta linia nie będzie modyfikowana ani przez kod oceniający, ani przez inne programy.

Każdy program wykorzysta następnie swoją strategię do uzyskania następujących wyników na standardowe wyjście :

• Lista Kliczb, które są identyfikatorami programów, które „pobierze 1” z tej rundy. Pusty wynik oznacza, że ​​nic nie da.

• Opcjonalnie jedna dodatkowa linia reprezentująca jakąś formę stanu, która zostanie przekazana do późniejszych rund. Ta dokładna linia zostanie przekazana do programu w następnej rundzie.

Poniżej znajduje się przykładowe dane wejściowe na początek gry dla gracza o ID 3w grze 4-osobowej:

4 3 0
4696634734863777023

Poniżej znajduje się przykład danych wejściowych dla tej samej gry z kilkoma już rozegranymi rundami:

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

Każdy program będzie zasilany dokładnie tym samym wejściem dla rundy, z wyjątkiem numeru ID, Dktóry jest unikalny dla każdego programu.

Poniżej znajduje się przykładowy wynik, w którym gracz 3bierze 1 od wszystkich innych:

1 2 4

Pod koniec wszystkich wymaganych rund zwycięzcą zostanie gracz z najwyższym wynikiem końcowym.

Oś czasu

Kodowanie tego turnieju potrwa łącznie 7 dni. Termin składania wniosków upływa 2014-05-09 00:00 UTC.

Nie publikuj rzeczywistych programów przed tą datą - opublikuj skrót SHA256 kodu źródłowego swojego programu jako zobowiązanie. Możesz zmienić ten skrót w dowolnym momencie przed upływem terminu, ale zobowiązania zaksięgowane po tym terminie nie zostaną zaakceptowane do wydania wyroku. (Proszę używać notacji bazowej 64 do swoich skrótów, ponieważ mój program weryfikacyjny wyrzuca bazową 64 i jest to bardziej zwarta notacja).

Po upływie terminu będziesz miał 1 dzień (do 2014-05-10 00:00 UTC) opublikowania faktycznego kodu źródłowego swojego programu do przesłania. Jeśli skrót SHA256 opublikowanego kodu źródłowego nie pasuje do żadnego skrótu, który opublikowałeś przed upływem terminu, kod nie zostanie przyjęty do turnieju.

Następnie pobiorę wszystkie zgłoszenia na własny komputer i przeprowadzę wszystkie zgłoszenia do turnieju w tej bitwie królewskiej, miejmy nadzieję, że opublikuję wyniki w ciągu 2 dni od tego czasu 2014-05-12 00:00 UTC.

Przyjmę odpowiedź z najwyższym wynikiem i przyznam nagrodę +100 za tę odpowiedź, jeśli jej końcowy wynik jest większy niż 0.

Po zakończeniu turnieju wyślę losowy plik źródłowy używany do przeprowadzenia zawodów, a ludzie mogą zacząć publikować inne rozwiązania, próbując przewyższyć te stosowane w turnieju. Nie będą jednak liczone jako akceptacja ani nagroda.

Maszyna hosta

Będę uruchamiał te rozwiązania na maszynie wirtualnej na moim komputerze. Na tej maszynie wirtualnej będzie działał Ubuntu Linux 14.04 z 2 gigabajtami pamięci RAM. Moja maszyna podstawowa ma procesor Intel i7-2600K działający z częstotliwością 3,40 GHz.

Wymagania

Twój program musi być napisany w języku, dla którego istnieje kompilator lub interpreter, który skompiluje Twój program i jest łatwo dostępny dla najnowszej wersji systemu Ubuntu Linux, dzięki czemu mogę uruchomić wszystkie zgłoszenia i ocenić je na maszynie wirtualnej.

Twój program nie może zająć więcej niż 2.000 secondsuruchomienie każdej rundy. Jeśli programowi zabraknie czasu lub wystąpi błąd, jego wynik zostanie uznany za pusty dla tej rundy.

Twój program musi być deterministyczny; to znaczy zawsze musi zwracać to samo wyjście dla tego samego wejścia. Dozwolone są rozwiązania pseudolosowe; ich losowość musi jednak zależeć od losowego ziarna podanego jako dane wejściowe i nic więcej. Plik źródłowy został wygenerowany przy użyciu Pythona os.urandom. Zawiera w sumie 500 wierszy (w razie potrzeby zostanie wygenerowanych więcej), a jego skrót SHA256 to K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. Zostanie przesłany tutaj po zakończeniu turnieju.

Rośliny

Na początek będą cztery „rośliny” reprezentujące początkowe naiwne strategie. Będą one grały w turnieju wraz z twoimi zgłoszeniami. Jednak w mało prawdopodobnym przypadku, gdy jeden z nich wygra, najwyższy wynik uzyskany przez gracza innego niż roślina zostanie uznany za zwycięzcę.

Aby obliczyć skrót pliku każdej rośliny, zamień każdą grupę 4 spacji na tabulator, ponieważ formater tutaj nie lubi znaków tabulacji.

Leniwy - nic nie robi.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

Chciwy - zawsze bierze 1 od wszystkich innych.

+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

Gniewny - bierze 1 od wszystkich pozostałych w pierwszej rundzie i bierze 1 od wszystkich, którzy wzięli 1 z poprzedniej rundy później.

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

Zazdrość - bierze 1 z 50% graczy z bieżącym najwyższym wynikiem wyłączając siebie, zaokrąglając w dół.

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

W turnieju obejmującym 100 rund spośród czterech, otrzymają wyniki:

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

Program oceniania

Opublikowałem program dla sędziów, z którego będę korzystać w Github . Pobierz i przetestuj. (I może naprawić błąd lub dwa, jeśli znajdziesz jeden.: P)

W tej chwili nie ma opcji kompilacji dla niczego innego niż Python. Uwzględnię je później - jeśli ludzie mogą wnieść skrypt do kompilacji lub interpretacji dla innych języków, byłbym bardzo zobowiązany.

Faza 2: przesłanie kodu źródłowego

W tournamentkonkursie opublikowałem nowy oddział do repozytorium Github, zawierający plik pd_rand i inne wpisy roślin. Możesz albo opublikować kod źródłowy tutaj, albo przesłać go do tego oddziału jako żądanie ściągnięcia.

Kolejność uczestników będzie następująca:

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

Ostateczne wyniki

Dane wyjściowe mojego programu testującego:

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

Rankingi:

 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

Okazuje się, że zwycięzcą jest gracz - to The Regular, z -204 punktami!

Niestety jego wynik nie był pozytywny, ale nie możemy się spodziewać, że w symulacji dylematu Więzionego Więźnia, w którym wszyscy grają, aby wygrać.

Niektóre zaskakujące wyniki (przynajmniej tak myślałem, że były zaskakujące):

• Chciwi zdobyli więcej niż Tit za Tat, a właściwie ogólnie więcej niż większość strzelców.

• Sędzia, który miał być swego rodzaju postacią „egzekwującego moralność” (w zasadzie zabrał 1 od tego, kto zabrał 1 komukolwiek ponadprzeciętną liczbę razy), uzyskał dość wysoką ocenę, podczas gdy w testach symulacyjnych faktycznie uzyskać raczej niski wynik.

I inne, które (myślałem) nie były tak zaskakujące:

• Pacjent uzyskał pełne 484 punkty więcej niż Gniewny. Naprawdę opłaca się współpracować za pierwszym razem.

• Jeden procent bardzo szybko nie miał prawie nikogo, kto mógłby kopnąć, gdy byli na dole. Wydaje się, że 1% jest w stanie tak pozostać, ponieważ ma więcej graczy w grze.

W każdym razie, po zakończeniu turnieju, możesz opublikować tak wielu dodatkowych graczy, jak chcesz, i przetestować je z nimi za pomocą programu sędziego.

The Regular

Wersja tego wpisu, którą wybrałem do turnieju (SHA-256 :),ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc= wykorzystuje strategię Joey'a „ Random sucker ” (choć z niewielką i prawdopodobnie nieznaczącą zmianą), która zajęła drugie miejsce w ostatnim konkursie. Niestety nowsza, bardziej skuteczna wersja przesłana zaledwie 3 minuty 25 sekund przed terminem zawiera poważny błąd, więc nie można jej było użyć. Niemniej jednak ta wersja nadal radzi sobie stosunkowo dobrze.

<?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";

Wersja buggy ma skrót SHA-256 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";

Aby to naprawić, wykonaj następujące wymiany:

• Wymienić $hashOutput = rtrim(fgets(STDIN), "\n");z $line .= fgets(STDIN);(nie to, że naprawdę się liczy).
• Wymień if ($betterScore >= 3 * $myScore) {się if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {(to jest to, co go zabił).

Jeden procent

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Patrzy z góry na tych więźniów, których uważa pod sobą.

Po prostu bierze od każdego, kto ma punkty mniejsze lub równe sobie. Zakłada się, że ci więźniowie mają mniejsze szanse na przyjęcie w zamian (lub mieliby więcej). Nie wiem, jakie to dobre założenie, ale na tym właśnie działa.

Również bierze od wszystkich w ostatniej rundzie. Nie ma to dosłownie żadnej wady, ponieważ po tym nikt nie może kraść zemsty.

Jeśli masz problemy z uzyskaniem skrótu z powodu tabulacji / spacji z wklejonego kodu, oto link do samego pliku.

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

}

Oto kilka innych roślin, które będą uczestniczyć w grze. Te są bardziej zaawansowane, a ich kod źródłowy nie zostanie ujawniony do końca fazy kodowania.

Podobnie jak cztery zakłady w pytaniu, jeśli uda im się zdobyć więcej punktów niż wszyscy inni gracze, tylko najwyższy wynik osiągnięty przez faktycznego zawodnika zostanie uznany za zwycięzcę.

Łobuz

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Odbiera ludzi.

Sędzia

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Karze złoczyńców.

The Lunatic

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

Nie ma pojęcia co robi.

Pacjent

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Nigdy nie wykonuje pierwszego ruchu.

Tit-for-tat

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Podobne do Wrathful, z kilkoma (miejmy nadzieję) zmianami zwiększającymi wydajność.

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

Dźgnięcie w plecy

Python 3

Mimo nazwy, ten bot jest w rzeczywistości dość łaskawy. Ale nie zaznaczaj tego.

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)

EDYCJA 2 : Wysłane źródło. Tak

EDYCJA : Po kilku testach naprawiłem kilka wad, które znalazłem. Nie są algorytmiczne, tylko niektóre problemy z odczytem danych wejściowych.

Begrudger

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Kod

Przyznam, że nie spędziłem dużo czasu na tym ...

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)