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 A
może zdecydować o „wzięciu 1” od innego gracza B
. W tych okolicznościach A
wynik wzrasta o 1, a B
wynik 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 P1
i P2
wyglą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 * 25
rund, w których P
jest 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
, iN
.P
to całkowita liczba graczy w grze. Każdy gracz jest losowo przypisany numer identyfikacyjny od1
celuP
na początku gry.D
to identyfikator bieżącego gracza.N
to liczba rozegranych rund.
N
linie, każda linia reprezentująca wyniki rundy. W liniik
zN
, będzie kilka liczban_k
zamówionych par(a, b)
, oddzielonych spacjami, które stanowią, że gracz z IDa
„wziął 1” od gracza z IDb
w tej rundzie.Jednolicie losowa liczba
R
od0
do18446744073709551615
(2 64 - 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
K
liczb, 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 3
w 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, D
który jest unikalny dla każdego programu.
Poniżej znajduje się przykładowy wynik, w którym gracz 3
bierze 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 seconds
uruchomienie 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 tournament
konkursie 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.
źródło
Odpowiedzi:
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.Wersja buggy ma skrót SHA-256
2hNVloFt9W7/uA5aQXg+naG9o6WNmrZzRf9VsQNTMwo=
:Aby to naprawić, wykonaj następujące wymiany:
$hashOutput = rtrim(fgets(STDIN), "\n");
z$line .= fgets(STDIN);
(nie to, że naprawdę się liczy).if ($betterScore >= 3 * $myScore) {
sięif ($betterScore >= 0.5 * $myScore && !psRand(0, $betterPlayer)) {
(to jest to, co go zabił).źródło
Jeden procent
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.
źródło
05-09 00:00
terminu.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.
źródło
Tit-for-tat
Podobne do Wrathful, z kilkoma (miejmy nadzieję) zmianami zwiększającymi wydajność.
źródło
Dźgnięcie w plecy
Python 3
Mimo nazwy, ten bot jest w rzeczywistości dość łaskawy. Ale nie zaznaczaj tego.
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.
źródło
Begrudger
Kod
Przyznam, że nie spędziłem dużo czasu na tym ...
źródło
o += a.split(', ')[0]
nie pozostawia spacji między liczbami.