Dans cette question , un jeu a été conçu dans lequel les joueurs s'affronteraient paire par paire dans le dilemme du prisonnier, afin de déterminer quelle stratégie itérative a marqué le plus haut contre les autres.
Dans cette question , j'ai imaginé un moyen pour plusieurs personnes de jouer le dilemme des prisonniers les uns contre les autres en même temps. Dans cette variante, la matrice des gains n'est pas nécessaire, chaque résultat entre chaque paire de deux joueurs étant la somme de deux décisions fonctionnellement indépendantes.
Votre tâche consiste à créer une IA pour jouer à cette version symétrique et généralisée du dilemme du prisonnier multijoueur qui atteindra le meilleur score possible.
Règles du jeu
À chaque tour de ce dilemme du prisonnier multijoueur et à plusieurs tours, un joueur A
peut décider de "prendre 1" à un autre joueur B
. Dans ce cas, A
le score de augmente de 1, tandis que B
le score de diminue de 2. Cette décision peut se produire entre chaque paire ordonnée de joueurs.
C'est la seule décision prise pour chaque joueur - soit de «prendre 1», soit de ne pas «prendre 1» de chaque autre joueur, qui sont respectivement homologues à la défection et à la coopération. La matrice de gain efficace entre deux joueurs P1
et P2
se présente comme suit:
P1/P2 P1 Take1 P1 Don't
P2 Take1 -1/-1 -2/+1
P2 Don't +1/-2 0/ 0
Procédure du tournoi
Le jeu se composera de P * 25
tours, où P
est le nombre de joueurs participants. Tous les joueurs commencent avec un score de 0
. Chaque tour comprendra la procédure suivante:
Au début d'un cycle, chaque programme recevra un historique des cycles précédents à partir de l'entrée standard , dans le format suivant:
Une ligne contenant 3 numéros,
P
,D
etN
.P
est le nombre total de joueurs dans le jeu. Chaque joueur se voit attribuer au hasard un numéro d'identification de1
àP
au début de la partie.D
est l'ID du joueur actuel.N
est le nombre de tours qui ont été joués.
N
lignes, chaque ligne représentant les résultats d'un tour. En lignek
deN
, il y aura un certain nombren_k
de paires ordonnées(a, b)
, séparées par des espaces, qui représentent que le joueur avec IDa
"a pris 1" du joueur avec IDb
dans ce tour.Un nombre uniformément aléatoire
R
de0
à18446744073709551615
(2 64 - 1), pour agir comme une graine pseudo-aléatoire. Ces chiffres seront lus à partir d'un fichier pré-généré, qui sera publié à la fin du tournoi afin que les gens puissent vérifier eux-mêmes les résultats.Une ligne supplémentaire qui représente une forme d'état à lire dans votre programme, si votre programme a produit une telle sortie lors du cycle précédent. Au début du jeu, cette ligne sera toujours vide. Cette ligne ne sera pas modifiée par le code de notation ou d'autres programmes.
Chaque programme utilisera ensuite sa stratégie pour produire les résultats suivants en sortie standard :
Une liste de
K
numéros, qui sont les identifiants des programmes qu'il "prendra 1" de ce tour. Une sortie vide signifie qu'elle ne fera rien.Facultativement, une ligne supplémentaire représentant une certaine forme d'état à transmettre aux tours ultérieurs. Cette ligne exacte sera renvoyée au programme lors du prochain tour.
Voici un exemple d'entrée pour le début du jeu pour un joueur d'ID 3
dans un jeu à 4 joueurs:
4 3 0
4696634734863777023
Voici un exemple d'entrée pour le même jeu avec quelques tours déjà joués:
4 3 2
(1, 2) (1, 3) (1, 4) (4, 2)
(1, 3) (2, 1) (2, 4) (3, 1) (4, 1)
4675881156406346380
Chaque programme recevra exactement la même entrée pour un tour, à l'exception du numéro d'identification D
qui est unique à chaque programme.
Voici un exemple de sortie dans laquelle le joueur 3
prend 1 à tout le monde:
1 2 4
À la fin de tous les tours requis, le joueur avec le score final le plus élevé sera le vainqueur.
Chronologie
Le codage de ce tournoi durera 7 jours au total. La date limite de soumission est 2014-05-09 00:00 UTC
.
Ne publiez pas de programmes réels avant cette date - publiez le hachage SHA256 du code source de votre programme comme engagement. Vous pouvez modifier ce hachage à tout moment avant la date limite, mais les engagements postés après la date limite ne seront pas acceptés pour jugement. (Veuillez utiliser la notation base 64 pour vos hachages, car mon programme de vérification crache la base 64 et c'est une notation plus compacte.)
Une fois la date limite dépassée, vous aurez 1 jour (jusqu'à 2014-05-10 00:00 UTC
) pour publier le code source réel de votre programme pour votre soumission. Si le hachage SHA256 de votre code source publié ne correspond à aucun hachage que vous avez publié avant la date limite, votre code ne sera pas accepté dans le tournoi.
Après cela, je téléchargerai toutes les soumissions sur mon propre ordinateur et exécuterai toutes les entrées du tournoi dans cette bataille royale, en espérant publier les résultats dans les 2 jours à compter de ce moment 2014-05-12 00:00 UTC
.
J'accepterai la réponse avec le score le plus élevé et j'accorderai une prime de +100 à cette réponse si son score final est supérieur à 0
.
Une fois le tournoi terminé, je publierai le fichier de départ aléatoire utilisé pour organiser la compétition, et les gens peuvent commencer à publier d'autres solutions en essayant de dépasser celles utilisées dans le tournoi. Cependant, ils ne compteront pas pour l'acceptation ou la prime.
La machine hôte
J'exécuterai ces solutions sur une machine virtuelle sur mon ordinateur. Cette machine virtuelle exécutera Ubuntu Linux 14.04, avec 2 gigaoctets de RAM. Ma machine de base possède un processeur Intel i7-2600K fonctionnant à 3,40 GHz.
Exigences
Votre programme doit être écrit dans une langue pour laquelle un compilateur ou un interprète qui compilera votre programme existe et est facilement disponible pour la dernière version d'Ubuntu Linux, afin que je puisse exécuter toutes les soumissions et les juger dans une machine virtuelle.
Votre programme ne doit pas prendre plus que 2.000 seconds
d'exécuter chaque tour. Si votre programme manque de temps ou produit une erreur, sa sortie sera considérée comme vide pour ce tour.
Votre programme doit être déterministe; c'est-à-dire qu'il doit toujours renvoyer la même sortie pour la même entrée. Les solutions pseudo-aléatoires sont autorisées; cependant, leur caractère aléatoire doit dépendre de la graine aléatoire qui lui est donnée en entrée et rien d'autre. Le fichier de départ a été généré à l'aide de Python os.urandom
. Il contient un total de 500 lignes (d'autres seront générées si nécessaire), et son hachage SHA256 l'est K+ics+sFq82lgiLanEnL/PABQKnn7rDAGmO48oiYxZk=
. Il sera téléchargé ici une fois le tournoi terminé.
Les plantes
Pour commencer, il y aura quatre "usines", représentant les premières stratégies naïves. Ceux-ci joueront dans le tournoi avec vos soumissions. Cependant, dans le cas peu probable où l'un d'entre eux gagne, le score le plus élevé obtenu par un joueur autre qu'une plante sera considéré comme gagnant.
Pour calculer le hachage du fichier de chaque plante, remplacez chaque groupe de 4 espaces par une tabulation, car le formateur ici ne semble pas aimer les caractères de tabulation.
Le paresseux - ne fait jamais rien.
n1bnYdeb/bNDBKASWGywTRa0Ne9hMAkal3AuVZJgovI=
pass
The Greedy - prend toujours 1 à tout le monde.
+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
Le courroucé - prend 1 à tous les autres au premier tour et prend 1 à tous ceux qui en ont pris 1 au tour suivant.
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 - prend 1 sur 50% des joueurs avec le score le plus élevé actuel en excluant lui-même, en arrondissant.
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
Dans un tournoi de 100 rounds juste parmi ces quatre, ils reçoivent des scores de:
Lazy: -204
Greedy: -100
Wrathful: -199
Envious: -199
Programme de jugement
J'ai publié le programme de juge que j'utiliserai sur Github . Téléchargez-le et testez-le. (Et peut-être corriger un bogue ou deux si vous en trouvez un.: P)
Il n'a pas d'options de compilation pour autre chose que Python pour le moment. Je les inclurai plus tard - si les gens pouvaient contribuer à la compilation ou à l'interprétation de scripts pour d'autres langues, je serais très obligé.
Phase 2: Soumission du code source
J'ai posté une nouvelle branche tournament
dans le référentiel Github pour le concours, contenant le fichier pd_rand et d'autres entrées d'usine. Vous pouvez publier votre code source ici ou le soumettre à cette branche en tant que demande de tirage.
L'ordre des candidats sera le suivant:
'begrudger'
'regular'
'patient'
'lazy'
'backstab'
'bully'
'lunatic'
'envious'
'titfortat'
'greedy'
'wrathful'
'judge'
'onepercent'
Scores finaux
La sortie de mon programme de test:
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
Classements:
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
Il s'avère donc que le gagnant est bien un joueur - c'est The Regular, avec -204 points!
Malheureusement, son score n'était pas positif, mais on peut difficilement s'attendre à cela dans une simulation du dilemme du prisonnier itéré où tout le monde joue pour gagner.
Quelques résultats surprenants (du moins que je trouvais surprenants):
The Greedy a marqué plus que Tit pour Tat, et en fait, généralement plus que la plupart des buteurs.
Le juge, qui était censé être une sorte de personnage «respecteur de moralité» (il en a fallu 1 à quiconque avait pris 1 à quiconque un nombre supérieur à la moyenne) a fini par obtenir un score plutôt élevé, alors que dans les tests de simulation, il obtenir un score assez faible.
Et d'autres qui (je pensais) n'étaient pas si surprenantes:
Le patient a marqué 484 points de plus que The Wrathful. Cela vaut vraiment la peine de coopérer cette première fois.
One Percent n'a eu très rapidement presque personne pour donner des coups de pied alors qu'ils étaient à terre. Il semble que le 1% ne peut rester que parce qu'il y a plus de joueurs dans le jeu.
Quoi qu'il en soit, maintenant que le tournoi est terminé, n'hésitez pas à poster autant de joueurs supplémentaires que vous le souhaitez et à tester avec eux en utilisant le programme des juges.
la source
Réponses:
The Regular
La version de cette entrée que j'ai choisie pour le tournoi (SHA-256 :)
ggeo+G2psAnLAevepmUlGIX6uqD0MbD1aQxkcys64oc=
utilise la stratégie de " Random sucker " de Joey (bien qu'avec un changement mineur et probablement insignifiant), qui est arrivée en deuxième position lors du dernier concours. Malheureusement, une version plus récente et plus efficace soumise seulement 3 minutes 25 secondes avant la date limite a un bug sérieux, elle n'a donc pas pu être utilisée. Néanmoins, cette version se porte encore relativement bien.La version buggy a un hachage SHA-256 de
2hNVloFt9W7/uA5aQXg+naG9o6WNmrZzRf9VsQNTMwo=
:Pour le réparer, faites ces remplacements:
$hashOutput = rtrim(fgets(STDIN), "\n");
par$line .= fgets(STDIN);
(pas ce qui compte vraiment).if ($betterScore >= 3 * $myScore) {
parif ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {
(c'est ce qui l'a tué).la source
Un pourcent
Regarde les prisonniers qu'il considère sous lui.
Prend simplement de tous ceux qui ont des points inférieurs ou égaux à lui-même. L'hypothèse est que ces prisonniers sont moins susceptibles de recevoir en retour (ou ils en auraient plus). Je ne sais pas à quel point cette hypothèse est bonne , mais c'est ce sur quoi il opère.
Prend également de tout le monde au dernier tour. Il n'y a littéralement aucun inconvénient à cela, car personne ne peut se venger de voler après cela.
Si vous rencontrez des problèmes pour obtenir le hachage à cause des tabulations / espaces du code collé, voici un lien vers le fichier lui-même.
la source
05-09 00:00
date limite.Voici quelques autres plantes qui participeront au jeu. Celles-ci sont plus avancées et leur code source ne sera révélé qu'à la fin de la phase de codage.
Tout comme les quatre plantes de la question, si elles réussissent à marquer plus haut que tous les autres joueurs, seul le score le plus élevé atteint par un concurrent réel sera considéré comme gagnant.
Le harceleur
29AGVpvJmDEDI5Efe/afmMJRLaJ+TpjwVcz1GkxgYZs=
Choisit les gens.
Le juge
yjdCQ3uQ4YKe7xAKxdTFLF4d72fD4ACYpDLwkbzdISI=
Punit les malfaiteurs.
Le fou
m3FsRPocekCcK6GDswgnobV2CYOxX8LquChnKxrx1Wo=
N'a aucune idée de ce qu'il fait.
Le patient
nd7Pt3bVpFnuvDVeHQ5T9EPTq7KjNraVzp/KGtI73Vo=
Ne fait jamais le premier pas.
la source
Tit-for-tat
Similaire à Wrathful, avec quelques changements (espérons-le) améliorant les performances.
la source
Poignarder dans le dos
Python 3
Malgré son nom, ce bot est en fait assez gracieux. Mais ne cochez pas.
EDIT 2 : Source publiée. Yay.
EDIT : Après quelques tests, j'ai corrigé quelques défauts que j'ai trouvés. Ils ne sont pas algorithmiques, juste quelques problèmes de lecture de l'entrée.
la source
le Begrudger
Code
J'avoue que je n'y ai pas passé beaucoup de temps ...
la source
o += a.split(', ')[0]
ne laisse pas d'espace entre les chiffres.