En esta pregunta , se ideó un juego en el que los jugadores se enfrentarían par a par en el Dilema del prisionero, para determinar qué estrategia iterativa obtuvo el puntaje más alto contra los demás.

En esta pregunta , ideé una forma para que varias personas jueguen el Dilema de los Prisioneros entre sí al mismo tiempo. En esta variación, la matriz de pagos es innecesaria, y cada resultado entre cada par de dos jugadores es la suma de dos decisiones funcionalmente independientes.

Tu tarea es construir una IA para jugar esta versión simétrica y generalizada del Dilema del Prisionero multijugador que logrará la mayor puntuación posible.

Reglas del juego

En cada ronda de este multijugador, el dilema del prisionero de varias rondas, un jugador Apuede decidir "tomar 1" de otro jugador B. En esta circunstancia, Ael puntaje aumenta en 1, mientras que Bel puntaje disminuye en 2. Se permite que esta decisión ocurra entre cada par ordenado de jugadores.

Esta es la única decisión tomada para cada jugador, ya sea "tomar 1" o no "tomar 1" del otro jugador, que son homólogos a la deserción y la cooperación, respectivamente. La matriz de pagos efectivos entre dos jugadores P1y se P2ve de la siguiente manera:

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

Procedimiento de torneo

El juego consistirá en P * 25rondas, donde Pestá el número de jugadores participantes. Todos los jugadores comienzan con una puntuación de 0. Cada ronda consistirá en el siguiente procedimiento:

Al comienzo de una ronda, a cada programa se le dará un historial de las rondas anteriores a partir de la entrada estándar , en el siguiente formato:

• Una línea que contiene 3 números, P, D, y N.

  • Pes el número total de jugadores en el juego. A cada jugador se le asigna aleatoriamente un número de identificación desde 1al Pprincipio del juego.

  • D es la ID del jugador actual.

  • N es la cantidad de rondas que se han jugado.

• Nlíneas, cada línea representa los resultados de una ronda. En la línea kde N, habrá un número n_kde pares ordenados (a, b), separados por espacios, que representan que el jugador con ID a"tomó 1" del jugador con ID ben esa ronda.

• Un número uniformemente aleatorio Rdesde 0hasta 18446744073709551615(2 ⁶⁴ - 1), para actuar como una semilla pseudoaleatoria. Estos números se leerán de un archivo pregenerado, que se publicará al final del torneo para que las personas puedan verificar los resultados por sí mismos.

• Una línea adicional que representa alguna forma de estado para leer en su programa, si su programa produjo tal salida en la ronda anterior. Al comienzo del juego, esta línea siempre estará vacía. Esta línea no será modificada ni por el código de puntuación ni por otros programas.

Luego, cada programa usará su estrategia para producir lo siguiente para la salida estándar :

• Una lista de Knúmeros, que son los ID de los programas que "tomará 1" de esta ronda. Una salida vacía significa que no hará nada.

• Opcionalmente, una línea adicional que representa alguna forma de estado para pasar a rondas posteriores. Esta línea exacta se retroalimentará al programa en la próxima ronda.

A continuación se muestra un ejemplo de entrada para el comienzo del juego para un jugador de ID 3en un juego de 4 jugadores:

4 3 0
4696634734863777023

A continuación se muestra una entrada de ejemplo para el mismo juego con algunas rondas ya jugadas:

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

Cada programa se alimentará exactamente con la misma entrada para una ronda, excepto por el número de identificación Dque es único para cada programa.

A continuación se muestra un ejemplo de salida en el que el jugador 3toma 1 de todos los demás:

1 2 4

Al final de todas las rondas requeridas, el jugador con el puntaje final más alto será el ganador.

Cronograma

La codificación para este torneo durará un total de 7 días. La fecha límite para la presentación es 2014-05-09 00:00 UTC.

No publique programas reales antes de esta fecha: publique el hash SHA256 del código fuente de su programa como un compromiso. Puede cambiar este hash en cualquier momento antes de la fecha límite, pero los compromisos publicados después de la fecha límite no serán aceptados para juicio. (Utilice la notación de base 64 para sus hashes, ya que mi programa de verificación escupe la base 64 y es una notación más compacta).

Una vez finalizado el plazo, tendrá 1 día (hasta 2014-05-10 00:00 UTC) para publicar el código fuente real de su programa para su envío. Si el hash SHA256 de su código fuente publicado no coincide con ningún hash que haya publicado antes de la fecha límite, su código no será aceptado en el torneo.

Después de esto, descargaré todas las presentaciones en mi propia computadora y ejecutaré todas las entradas del torneo en esta batalla real, con la esperanza de publicar los resultados dentro de 2 días a partir de entonces 2014-05-12 00:00 UTC.

Aceptaré la respuesta con el puntaje más alto y otorgaré una recompensa de +100 a esa respuesta si su puntaje final es mayor que 0.

Después de que termine el torneo, publicaré el archivo semilla aleatorio utilizado para ejecutar la competencia, y la gente puede comenzar a publicar otras soluciones tratando de superar las utilizadas en el torneo. Sin embargo, no contarán para la aceptación o la recompensa.

La máquina host

Ejecutaré estas soluciones en una máquina virtual en mi computadora. Esta máquina virtual ejecutará Ubuntu Linux 14.04, con 2 gigabytes de RAM. Mi máquina base tiene un procesador Intel i7-2600K que funciona a 3.40 GHz.

Requisitos

Su programa debe estar escrito en un lenguaje para el cual exista un compilador o intérprete que compile su programa y esté disponible para la última versión de Ubuntu Linux, de modo que pueda ejecutar todos los envíos y juzgarlos en una máquina virtual.

Su programa no debe tomar más que 2.000 secondsejecutar cada ronda. Si su programa se queda sin tiempo o produce un error, su salida se considerará vacía para esa ronda.

Su programa debe ser determinista; es decir, siempre debe devolver la misma salida para la misma entrada. Se permiten soluciones pseudoaleatorias; sin embargo, su aleatoriedad debe depender de la semilla aleatoria dada como entrada y nada más. El archivo semilla se generó usando Python os.urandom. Contiene un total de 500 líneas (se generarán más si es necesario), y su hash SHA256 es K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=. Se cargará aquí una vez que termine el torneo.

Plantas

Para comenzar, habrá cuatro "plantas", que representan estrategias ingenuas iniciales. Estos se jugarán en el torneo junto con tus presentaciones. Sin embargo, en el caso improbable de que uno de ellos gane, el puntaje más alto obtenido por un jugador que no sea una planta se considerará ganador.

Para calcular el hash del archivo de cada planta, reemplace cada grupo de 4 espacios con una pestaña, ya que al formateador aquí no parece gustarle los caracteres de tabulación.

The Lazy - nunca hace nada.

n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=

pass

The Greedy : siempre toma 1 de todos los demás.

+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 : toma 1 de todos los demás en la primera ronda y toma 1 de todos los que tomaron 1 de ella en la ronda anterior posterior.

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 : toma 1 del 50% de los jugadores con el puntaje más alto actual excluyéndose, redondeando hacia abajo.

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

En un torneo de 100 rondas solo entre estas cuatro, reciben puntuaciones de:

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

Programa de juzgamiento

He publicado el programa de jueces que usaré en Github . Descárgalo y pruébalo. (Y tal vez corrija un error o dos si encuentra uno.: P)

No tiene opciones de compilación para nada más que Python en este momento. Los incluiré más adelante: si la gente pudiera contribuir con scripts de compilación o interpretación para otros idiomas, estaría muy agradecido.

Fase 2: envío del código fuente

He publicado una nueva sucursal tournamenten el repositorio de Github para el concurso, que contiene el archivo pd_rand y otras entradas de la planta. Puede publicar su código fuente aquí o enviarlo a esa sucursal como una solicitud de extracción.

El orden de los concursantes será el siguiente:

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

Puntajes finales

La salida de mi programa de prueba:

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

Rankings:

 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

Así que resulta que el ganador es un jugador: ¡es The Regular, con -204 puntos!

Desafortunadamente, su puntaje no fue positivo, pero difícilmente podemos esperar que en una simulación del Dilema del Prisionero Iterado donde todos estén jugando para ganar.

Algunos resultados sorprendentes (al menos eso pensé que eran sorprendentes):

• El codicioso anotó más que Tit para Tat, y de hecho, generalmente más alto que la mayoría de los anotadores.

• El Juez, que estaba destinado a ser una especie de personaje "ejecutor de la moralidad" (básicamente tomó 1 de quien había tomado 1 de alguien un número superior al promedio de veces) terminó obteniendo un puntaje bastante alto, mientras que en las pruebas de simulación, en realidad obtener un puntaje bastante bajo.

Y otros que (pensé) no fueron tan sorprendentes:

• El paciente obtuvo 484 puntos más que The Wrathful. Realmente vale la pena cooperar esa primera vez.

• Uno por ciento muy rápidamente no tenía a nadie a quien patear mientras estaban abajo. Parece que el 1% solo puede mantenerse así porque tienen más jugadores en el juego.

De todos modos, ahora que el torneo ha terminado, siéntase libre de publicar tantos jugadores adicionales como desee y pruebe con ellos utilizando el programa de jueces.

El regular

La versión de esta entrada que elegí para el torneo (SHA-256 :)ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc= usa la estrategia de " Random sucker " de Joey (aunque con un cambio menor y probablemente insignificante), que quedó en segundo lugar en el último concurso. Desafortunadamente, una versión más nueva y más efectiva enviada solo 3 minutos y 25 segundos antes de la fecha límite tiene un error grave, por lo que no se pudo usar. Sin embargo, a esta versión todavía le va relativamente bien.

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

La versión con errores tiene un 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 solucionarlo, realice estos reemplazos:

• Reemplazar $hashOutput = rtrim(fgets(STDIN), "\n");con $line .= fgets(STDIN);(no es que eso realmente importe).
• Reemplazar if ($betterScore >= 3 * $myScore) {con if ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {(esto es lo que lo mató).

Uno porciento

b61189399ae9494b333df8a71e36039f64f1d2932b838d354c688593d8f09477

Desprecia a los prisioneros que considera debajo de él.

Simplemente toma de todos los que tienen puntos menores o iguales a sí mismo. La suposición es que esos presos tienen menos probabilidades de recibir a cambio (o tendrían más). No sé qué tan buena es una suposición, pero eso es en lo que está operando.

También toma de todos en la última ronda. Literalmente, no hay inconveniente en esto, ya que nadie puede vengarse después de eso.

Si tiene problemas para obtener el hash debido a tab / espacios del código pegado, aquí hay un enlace al archivo en sí.

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

}

Aquí hay algunas plantas más que participarán en el juego. Estos son más avanzados y su código fuente no se revelará hasta el final de la fase de codificación.

Al igual que las cuatro plantas en la pregunta, si logran obtener un puntaje más alto que todos los demás jugadores, solo el puntaje más alto alcanzado por un concursante real se considerará ganador.

El acosador

29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=

Selecciones en las personas.

El juez

yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=

Castiga a los malhechores.

El lunático

m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=

No tiene idea de lo que está haciendo.

El paciente

nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=

Nunca hace el primer movimiento.

Tit por tat

9GkjtTDD2jrnMYg/LSs2osiVWxDDoSOgLCpWvuqVmSM=

Similar a Wrathful, con algunos (con suerte) cambios que mejoran el rendimiento.

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

Puñalada

Python 3

A pesar del nombre, este bot es bastante amable. Pero no lo marques.

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 : Fuente publicada. Hurra.

EDITAR : Después de algunas pruebas, solucioné algunos defectos que encontré. No son algorítmicos, solo algunos problemas al leer la entrada.

los Begrudger

g1TXBu2EfVz/uM/RS24VeJuYMKLOaRatLxsA+DN1Mto=

Código

Admito que no pasé mucho tiempo en esto ...

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)