Em esta questão , um jogo foi inventado em que os jogadores teriam de enfrentar um ao outro par a par no Dilema do Prisioneiro, para determinar qual estratégia iterativa obteve a maior pontuação contra os outros.

Em esta pergunta , eu desenvolveu uma maneira para várias pessoas para jogar Dilema dos Prisioneiros uns contra os outros, tudo ao mesmo tempo. Nesta variação, a matriz de pagamento é desnecessária, com cada resultado entre cada par de dois jogadores sendo a soma de duas decisões funcionalmente independentes.

Sua tarefa é criar uma IA para jogar esta versão simétrica e generalizada do dilema do prisioneiro multiplayer que alcançará a maior pontuação possível.

Regras do jogo

Em cada rodada deste Dilema do Prisioneiro, multijogador e multijogador, um jogador Apode decidir "tirar 1" de outro jogador B. Nessa circunstância, Aa pontuação aumenta em 1, enquanto Ba pontuação diminui em 2. Essa decisão pode acontecer entre cada par de jogadores ordenados.

Esta é a única decisão tomada para cada jogador - "tomar 1" ou não "tomar 1" um do outro jogador, que são homólogos à deserção e à cooperação, respectivamente. A matriz de pagamento efetiva entre dois jogadores P1e P2tem a seguinte aparência:

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

Procedimento do Torneio

O jogo consistirá em P * 25rodadas, onde Pé o número de jogadores participantes. Todos os jogadores começam com uma pontuação de 0. Cada rodada consistirá no seguinte procedimento:

No início de uma rodada, cada programa receberá um histórico das rodadas anteriores a partir da entrada padrão , no seguinte formato:

• Uma linha contendo 3 números, P, D, e N.

  • Pé o número total de jogadores no jogo. Cada jogador recebe um número de identificação aleatoriamente de 1até Pno início do jogo.

  • D é o ID do jogador atual.

  • N é o número de rodadas que foram jogadas.

• Nlinhas, cada linha representando os resultados de uma rodada. Na linha kde N, haverá um número n_kde pares ordenados (a, b), separados por espaços, que representam que o jogador com ID a"tirou 1" do jogador com ID bnessa rodada.

• Um número uniformemente aleatório Rde 0a 18446744073709551615(2 ⁶⁴ - 1), para atuar como uma semente pseudo-aleatória. Esses números serão lidos a partir de um arquivo pré-gerado, que será lançado no final do torneio para que as pessoas possam verificar os resultados por si mesmas.

• Uma linha extra que representa alguma forma de estado a ser lida no seu programa, se o seu programa produziu essa saída na rodada anterior. No início do jogo, esta linha estará sempre vazia. Esta linha não será modificada pelo código de pontuação ou por outros programas.

Cada programa usará sua estratégia para produzir o seguinte para a saída padrão :

• Uma lista de Knúmeros, que são os IDs dos programas que serão "retirados 1" desta rodada. Uma saída vazia significa que não fará nada.

• Opcionalmente, uma linha extra representando algum tipo de estado para repassar para as rodadas posteriores. Essa linha exata será retornada ao programa na próxima rodada.

Abaixo está um exemplo de entrada para o início do jogo para um jogador de ID 3em um jogo para 4 jogadores:

4 3 0
4696634734863777023

Abaixo está um exemplo de entrada para o mesmo jogo com algumas rodadas já jogadas:

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

Cada programa será alimentado exatamente da mesma entrada para uma rodada, exceto o número de identificação Dexclusivo de cada programa.

Abaixo está um exemplo de saída em que o jogador 3recebe 1 de todos os outros:

1 2 4

No final de todas as rodadas necessárias, o jogador com a maior pontuação final será o vencedor.

Linha do tempo

A codificação deste torneio durará um total de 7 dias. O prazo para envio é 2014-05-09 00:00 UTC.

Não publique programas reais antes desta data - publique o hash SHA256 do código fonte do seu programa como um compromisso. Você pode alterar esse hash a qualquer momento antes do prazo final, mas os compromissos postados após o prazo final não serão aceitos para julgamento. (Use a notação base 64 para seus hashes, pois meu programa de verificação apresenta a base 64 e é uma notação mais compacta.)

Após o término do prazo, você terá 1 dia (até 2014-05-10 00:00 UTC) para publicar o código-fonte real do seu programa para envio. Se o hash SHA256 do seu código-fonte postado não corresponder a nenhum hash que você postou antes do prazo, seu código não será aceito no torneio.

Depois disso, baixarei todos os envios para o meu próprio computador e executarei todas as entradas do torneio neste battle royale, postando os resultados dentro de dois dias a partir de então 2014-05-12 00:00 UTC.

Aceitarei a resposta com a pontuação mais alta e atribuirei uma recompensa de +100 a essa resposta se sua pontuação final for maior que 0.

Após o término do torneio, publicarei o arquivo de distribuição aleatória usado para executar a competição, e as pessoas poderão começar a postar outras soluções tentando superar as usadas no torneio. No entanto, eles não contarão para aceitação ou recompensa.

A máquina host

Eu executarei essas soluções em uma máquina virtual no meu computador. Esta máquina virtual executará o Ubuntu Linux 14.04, com 2 gigabytes de RAM. Minha máquina base possui um processador Intel i7-2600K rodando a 3,40 GHz.

Exigências

Seu programa deve ser escrito em um idioma para o qual exista um compilador ou intérprete que irá compilar seu programa e esteja prontamente disponível para a versão mais recente do Ubuntu Linux, para que eu possa executar todos os envios e julgá-los em uma máquina virtual.

Seu programa não deve demorar mais do que 2.000 secondspara executar cada rodada. Se o seu programa ficar sem tempo ou produzir um erro, sua saída será considerada vazia para essa rodada.

Seu programa deve ser determinístico; isto é, sempre deve retornar a mesma saída para a mesma entrada. Soluções pseudo-aleatórias são permitidas; no entanto, sua aleatoriedade deve depender da semente aleatória fornecida como entrada e nada mais. O arquivo inicial foi gerado usando o Python os.urandom. Ele contém um total de 500 linhas (mais será gerado, se necessário) e seu hash SHA256 é K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. Será carregado aqui assim que o torneio terminar.

Plantas

Para começar, haverá quatro "plantas", representando estratégias iniciais ingênuas. Eles estarão jogando no torneio junto com as suas inscrições. No entanto, no caso improvável de um deles vencer, a pontuação mais alta obtida por um jogador que não seja uma planta será considerada vencedora.

Para calcular o hash do arquivo de cada planta, substitua cada grupo de 4 espaços por uma tabulação, pois o formatador aqui não parece gostar de caracteres de tabulação.

O Preguiçoso - nunca faz nada.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

The Greedy - sempre tira 1 de todo mundo.

+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 - pega 1 de todos os outros no primeiro turno e pega 1 de todos que tiraram 1 dele na rodada anterior depois.

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 - pega 1 dos 50% de jogadores com a pontuação mais alta atual, excluindo-se, arredondando para baixo.

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

Em um torneio de 100 rodadas, dentre as quatro, eles recebem dezenas de:

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

Programa de Julgamento

Publiquei o programa de juízes que utilizarei no Github . Faça o download e teste. (E talvez conserte um bug ou dois, se você encontrar um.: P)

Ele não tem opções de compilação para nada além de Python no momento. Vou incluí-los mais tarde - se as pessoas pudessem contribuir com scripts de compilação ou interpretação para outros idiomas, ficaria muito grato.

Fase 2: Envio do Código Fonte

tournamentPubliquei uma nova ramificação no repositório do Github para o concurso, contendo o arquivo pd_rand e outras entradas da planta. Você pode postar seu código-fonte aqui ou enviá-lo para esse ramo como uma solicitação de recebimento.

A ordem dos competidores será a seguinte:

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

Pontuações finais

A saída do meu programa de teste:

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

Classificação:

 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

Acontece que o vencedor é realmente um jogador - é o The Regular, com -204 pontos!

Infelizmente, sua pontuação não foi positiva, mas mal podemos esperar isso em uma simulação do Dilema do Prisioneiro Iterado, onde todos estão jogando para ganhar.

Alguns resultados surpreendentes (pelo menos eu pensei que eram surpreendentes):

• Os gananciosos marcaram mais que Tit por Tat e, de fato, geralmente são mais altos do que a maioria dos artilheiros.

• O juiz, que deveria ser uma espécie de personagem "impositor da moralidade" (basicamente levou 1 de quem tirou 1 de alguém um número acima da média de vezes) acabou pontuando bastante alto, enquanto nos testes de simulação, na verdade, obtenha uma pontuação bastante baixa.

E outros que (eu pensei) não eram tão surpreendentes:

• O Paciente marcou 484 pontos a mais que The Wrathful. Realmente vale a pena cooperar nessa primeira vez.

• Um por cento muito rapidamente não tinha quase ninguém para chutar enquanto caíam. Parece que o 1% só é capaz de permanecer assim, porque eles têm mais jogadores no jogo.

De qualquer forma, agora que o torneio terminou, fique à vontade para postar quantos jogadores extras desejar e testar com eles usando o programa de juízes.

The Regular

A versão desta entrada que eu escolhi para o torneio (SHA-256 :)ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc= usa o nome de Joey " estratégia Random sucker " de (embora com uma mudança menor e provavelmente insignificante), que ficou em segundo lugar no último concurso. Infelizmente, uma versão mais nova e mais eficaz enviada apenas 3 minutos e 25 segundos antes do prazo final apresentar um bug sério, não pode ser usada. No entanto, esta versão ainda se sai relativamente bem.

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

A versão de buggy possui um hash SHA-256 de 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";

Para corrigi-lo, faça estas substituições:

• Substituir $hashOutput = rtrim(fgets(STDIN), "\n"); por $line .= fgets(STDIN);(não que isso realmente importe).
• Substitua if ($betterScore >= 3 * $myScore) {por if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {(foi isso que o matou).

Um por cento

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Olha para os prisioneiros que ele considera embaixo dele.

Simplesmente tira de todo mundo que tem pontos menores ou iguais a si mesmo. A suposição é que esses prisioneiros são menos propensos a receber em troca (ou teriam mais). Não sei como é bom de um pressuposto de que é, mas isso é o que ele está operando em.

Também leva de todos na última rodada. Não há literalmente nenhuma desvantagem nisso, já que ninguém pode se vingar e roubar depois disso.

Se você tiver problemas para obter o hash devido a tab / espaços do código colado, aqui está um link para o próprio arquivo.

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

}

Aqui estão mais algumas plantas que participarão do jogo. Esses são mais avançados e seu código-fonte não será revelado até o final da fase de codificação.

Assim como as quatro plantas em questão, se conseguirem pontuar mais que todos os outros jogadores, apenas a pontuação mais alta alcançada por um competidor será considerada vencedora.

O bully

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Escolhas as pessoas.

O juiz

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Pune os transgressores.

O Lunático

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

Não tem ideia do que está fazendo.

O paciente

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Nunca dá o primeiro passo.

Chapim-para-tat

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Semelhante ao Wrathful, com algumas (esperançosamente) mudanças no desempenho.

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

Apesar do nome, este bot é realmente muito gentil. Mas não marque.

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 : Fonte postada. Yay.

EDIT : Depois de alguns testes, corrigi algumas falhas que encontrei. Eles não são algorítmicos, apenas alguns problemas ao ler a entrada.

The Begrudger

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Código

Admito que não gastei muito tempo nisso ...

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)