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

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

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

Правила игры

В каждом раунде этой многопользовательской дилеммы с несколькими раундами игрок Aможет решить «взять 1» у другого игрока B. В этом случае количество Aочков увеличивается на 1, а количество Bочков уменьшается на 2. Это решение может приниматься между каждой заказанной парой игроков.

Это единственное решение, принятое для каждого игрока - либо «брать 1», либо не «брать 1» у каждого другого игрока, которые гомологичны дезертирству и сотрудничеству соответственно. Эффективная матрица выигрышей между двумя игроками P1и P2выглядят следующим образом :

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

Турнирная процедура

Игра будет состоять из P * 25раундов, где Pуказано количество участвующих игроков. Все игроки начинают со счета 0. Каждый раунд будет состоять из следующей процедуры:

В начале раунда каждой программе будет предоставлена ​​история предыдущих раундов из стандартного ввода в следующем формате:

• Одна линия , содержащая 3 числа, P, D, и N.

  • Pобщее количество игроков в игре. Каждому игроку случайным образом присваивается идентификационный номер от 1до Pв начале игры.

  • D это идентификатор текущего игрока.

  • N количество сыгранных раундов

• Nлинии, каждая строка, представляющая результаты раунда. На линии kиз N, будет некоторое количество n_kупорядоченных пар (a, b), разделенных пробелами, которые представляют собой , что игрок с идентификатором a«принял 1» от игрока с ID bв этом раунде.

• Равномерно случайное число Rот 0до 18446744073709551615(2 ⁶⁴ - 1), действующее как псевдослучайное семя. Эти числа будут считаны из предварительно сгенерированного файла, который будет выпущен в конце турнира, чтобы люди могли сами проверить результаты.

• Одна дополнительная строка, представляющая некоторую форму состояния, которая будет считана в вашу программу, если ваша программа выдала такой вывод в предыдущем раунде. В начале игры эта строка всегда будет пустой. Эта строка не будет изменена ни кодом оценки, ни другими программами.

Каждая программа затем использует свою стратегию для получения следующего стандартного результата :

• Список Kномеров, которые являются идентификаторами программ, которые он «возьмет 1» из этого раунда. Пустой вывод означает, что он ничего не будет делать.

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

Ниже приведен пример ввода для начала игры для игрока с ID 3в игре для 4 игроков:

4 3 0
4696634734863777023

Ниже приведен пример ввода для той же игры с несколькими уже сыгранными раундами:

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

Каждой программе будет предоставлен один и тот же вход для раунда, за исключением идентификационного номера, Dкоторый уникален для каждой программы.

Ниже приведен пример вывода, в котором игрок 3получает 1 от всех остальных:

1 2 4

В конце всех необходимых раундов игрок с наибольшим итоговым счетом будет победителем.

График

Кодирование для этого турнира будет длиться в общей сложности 7 дней. Крайний срок подачи заявок 2014-05-09 00:00 UTC.

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

После истечения крайнего срока у вас будет 1 день (до 2014-05-10 00:00 UTC), чтобы опубликовать фактический исходный код вашей программы для отправки. Если хеш SHA256 вашего опубликованного исходного кода не соответствует ни одному хешу, который вы опубликовали до истечения крайнего срока, ваш код не будет принят в турнир.

После этого я буду загружать все заявки на свой компьютер и запускать все записи турниров в этой битве, надеясь опубликовать результаты в течение 2 дней с этого момента 2014-05-12 00:00 UTC.

Я приму ответ с наивысшим баллом и назначу награду +100 за этот ответ, если его итоговый балл будет больше, чем 0.

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

Хост-машина

Я буду запускать эти решения на виртуальной машине на моем компьютере. Эта виртуальная машина будет работать под управлением Ubuntu Linux 14.04 с 2 гигабайтами оперативной памяти. На моей базовой машине установлен процессор Intel i7-2600K с тактовой частотой 3,40 ГГц.

Требования

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

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

Ваша программа должна быть детерминированной; то есть он всегда должен возвращать один и тот же вывод для одного и того же ввода. Разрешены псевдослучайные решения; тем не менее, их случайность должна зависеть от случайного начального числа, данного ему в качестве входных данных, и ничего более. Начальный файл был создан с использованием Python os.urandom. Он содержит в общей сложности 500 строк (при необходимости будет сгенерировано больше) и его хэш SHA256 K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. Он будет загружен здесь после окончания турнира.

растения

Для начала будет четыре «растения», представляющих первоначальные наивные стратегии. Они будут играть в турнире вместе с вашими представлениями. Однако в маловероятном случае, если один из них выиграет, победителем будет считаться наибольшее количество очков, полученное игроком, не являющимся растением.

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

Ленивый - никогда ничего не делает.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

Жадный - всегда получает 1 от всех остальных.

+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

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

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

Завистник - берет 1 из 50% игроков с текущим наибольшим счетом, исключая себя, округляя вниз.

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

В турнире из 100 туров только среди этих четырех они получают очки:

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

Программа судейства

Я разместил программу судейства, которую я буду использовать на Github . Загрузите и проверьте это. (И может исправить ошибку или два, если вы найдете один.: P)

На данный момент у него нет опций компиляции для чего-то кроме Python. Я включу их позже - если бы люди могли предоставить сценарии компиляции или интерпретации для других языков, я был бы очень благодарен.

Этап 2: Предоставление исходного кода

Я разместил новую ветку tournamentв репозитории Github для конкурса, содержащую файл pd_rand и другие записи завода. Вы можете опубликовать свой исходный код здесь или отправить его в эту ветку в виде запроса на извлечение.

Порядок участников будет следующим:

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

Итоговые результаты

Вывод моей тестовой программы:

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

Рейтинг:

 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

Вот и получается, что победителем действительно является игрок - это Регулярный, с -204 очками!

К сожалению, его оценка не была положительной, но мы вряд ли можем ожидать, что это в симуляции Дилеммы Итеративного Заключенного, где все играют, чтобы выиграть.

Некоторые неожиданные результаты (по крайней мере, я думал, что они были удивительными):

• Жадный забил больше, чем Тит за Тат, и на самом деле, как правило, выше, чем большинство бомбардиров вообще.

• Судья, который должен был быть своего рода персонажем, обеспечивающим соблюдение морали (по сути, он взял 1 от того, кто взял 1 у кого-либо выше среднего числа раз), в итоге получил довольно высокий балл, в то время как в симуляционном тестировании он фактически получить довольно низкий балл.

И другие, которые (я думал) не были такими удивительными:

• Пациент набрал на 484 балла больше, чем «Гневный». Это действительно выгодно сотрудничать в первый раз.

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

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

Регулярный

Версия этой записи я выбрал для турнира (SHA-256: ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc= использует стратегию Джои « Случайный присоски » (хотя и с незначительными и, вероятно, незначительными изменениями), которая заняла второе место в последнем конкурсе. К сожалению, новая, более эффективная версия, представленная всего за 3 минуты 25 секунд до истечения срока, имеет серьезную ошибку, поэтому ее нельзя использовать. Тем не менее, эта версия все еще живет относительно хорошо.

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

Версия с ошибками имеет хэш 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";

Чтобы это исправить, сделайте эти замены:

• Заменить $hashOutput = rtrim(fgets(STDIN), "\n");на $line .= fgets(STDIN);(не то, что действительно имеет значение).
• Заменить if ($betterScore >= 3 * $myScore) {на if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {(это то, что убило его).

Один процент

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Смотрит на тех заключенных, которых он считает под собой.

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

Также берет от всех на последнем туре. В этом нет буквального недостатка, так как никто не может отомстить за это.

Если у вас возникли проблемы с получением хеша из-за вставленных пробелов в вставленном коде, вот ссылка на сам файл.

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

}

Вот еще несколько растений, которые будут участвовать в игре. Они более продвинуты, и их исходный код не будет раскрыт до конца фазы кодирования.

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

Хулиган

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Выбирает людей.

Судья

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Наказывает правонарушителей.

Лунатик

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

Понятия не имеет, что делает.

Пациент

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Никогда не делает первый ход.

Зуб за зуб

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Подобно Wrathful, с несколькими (надеюсь) изменениями, улучшающими производительность.

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

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

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)

РЕДАКТИРОВАТЬ 2 : Опубликованный источник. Ура.

РЕДАКТИРОВАТЬ : После некоторого тестирования я исправил некоторые недостатки, которые я нашел. Они не алгоритмические, просто некоторые проблемы с чтением ввода.

Begrudger

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Код

Я признаю, что я не тратил много времени на это ...

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)