Tugas ini merupakan bagian dari Push Puzzle Pemrograman Premier Periodik Pertama dan dimaksudkan sebagai demonstrasi proposal tipe tantangan raja-dari-bukit -baru .
Tugasnya adalah menulis program untuk memainkan dilema tahanan yang diulang lebih baik daripada peserta lainnya.
Lihat, Vinny. Kami tahu teman satu selmu --- siapa namanya? Ya McWongski, mafia Nippo-Irlandia-Ukrania - terserah sesuatu dan Anda tahu apa itu.
Kami berusaha bersikap baik di sini, Vinnie. Memberi Anda kesempatan.
Jika Anda memberi tahu kami apa yang dia rencanakan, kami akan melihat Anda mendapat tugas kerja yang baik.
Dan jika Anda tidak ...
Aturan main
- Kontes ini terdiri dari round-robin penuh (semua pasangan mungkin) dari dua kontestan pada suatu waktu (termasuk bermain sendiri).
- Ada 100 putaran yang dimainkan antara masing-masing pasangan
- Dalam setiap putaran masing-masing pemain diminta untuk memilih antara bekerja sama dengan pemain lain atau mengkhianati mereka, tanpa mengetahui niat pemain lain dalam masalah ini, tetapi dengan memori hasil putaran sebelumnya dimainkan melawan lawan ini.
- Poin diberikan untuk setiap putaran berdasarkan pilihan gabungan. Jika kedua pemain bekerja sama, masing-masing mendapat 2 poin. Pengkhianatan timbal balik menghasilkan masing-masing 1 poin. Dalam kasus campuran, pemain yang mengkhianati diberikan 4 poin dan kooperator dihukum 1 poin.
- Pertandingan "resmi" akan berjalan tidak lebih cepat dari 10 hari setelah memposting dengan semua kiriman yang saya dapat mulai bekerja dan digunakan untuk memilih pemenang yang "diterima". Saya memiliki kotak Mac OS 10.5, jadi solusi POSIX harus bekerja, tetapi ada linuxisms yang tidak. Demikian juga, saya tidak memiliki dukungan untuk API win32. Saya bersedia melakukan upaya dasar untuk menginstal sesuatu, tetapi ada batasnya. Batas-batas sistem saya sama sekali tidak mewakili batas-batas respons yang dapat diterima, hanya batas-batas yang akan dimasukkan dalam pertandingan "resmi".
Antarmuka Programmer
- Entri harus dalam bentuk program yang dapat dijalankan dari baris perintah; keputusan harus keluaran (tunggal!) dari program pada keluaran standar. Sejarah putaran sebelumnya dengan lawan ini akan disajikan sebagai argumen baris perintah.
- Outputnya bisa berupa "c" (untuk clam up ) atau "t" (untuk semua ).
- Sejarah adalah string tunggal karakter yang mewakili babak sebelumnya dengan putaran terbaru yang paling awal dalam string. Karakternya adalah
- "K" (untuk menjaga iman yang berarti kerja sama)
- "R" (untuk tikus b @ st @ rd terjual habis! )
- "S" (untuk pengisap! Artinya Anda mendapat manfaat dari pengkhianatan)
- "E" (untuk semua orang mencari nomor satu pada pengkhianatan timbal balik)
Braket
Empat pemain akan disediakan oleh penulis
- Malaikat - selalu bekerja sama
- Iblis - selalu berbicara
- TitForTat - Bekerja sama di babak pertama lalu selalu melakukan apa yang dia lakukan di babak terakhir
- Acak - 50/50
di mana saya akan menambahkan semua entri yang bisa saya jalankan.
Skor total akan menjadi skor penjumlahan terhadap semua lawan (termasuk permainan mandiri hanya sekali dan menggunakan skor rata-rata).
Peserta
(saat ini pada 2 Mei 2011 7:00)
Jabat Tangan Rahasia | Rudal Anti-T42T | Ketidakpercayaan (varian) | Anti-Jabat Tangan | The Little Lisper | Konvergensi | Hiu | Probabimatic | Pavlov - Menangkan Menginap, Kalah Beralih | Hormatilah Pencuri | Bantu Vampir | Druid | Schemer Kecil | Dulu | Gayung Dua Tats | Simpleton |
Pencetak gol
#! /usr/bin/python
#
# Iterated prisoner's dilemma King of Hill Script Argument is a
# directory. We find all the executables therein, and run all possible
# binary combinations (including self-plays (which only count once!)).
#
# Author: dmckee (https://codegolf.stackexchange.com/users/78/dmckee)
#
import subprocess
import os
import sys
import random
import py_compile
###
# config
PYTHON_PATH = '/usr/bin/python' #path to python executable
RESULTS = {"cc":(2,"K"), "ct":(-1,"R"), "tc":(4,"S"), "tt":(1,"E")}
def runOne(p,h):
"""Run process p with history h and return the standard output"""
#print "Run '"+p+"' with history '"+h+"'."
process = subprocess.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
return process.communicate()[0]
def scoreRound(r1,r2):
return RESULTS.get(r1[0]+r2[0],0)
def runRound(p1,p2,h1,h2):
"""Run both processes, and score the results"""
r1 = runOne(p1,h1)
r2 = runOne(p2,h2)
(s1, L1), (s2, L2) = scoreRound(r1,r2), scoreRound(r2,r1)
return (s1, L1+h1), (s2, L2+h2)
def runGame(rounds,p1,p2):
sa, sd = 0, 0
ha, hd = '', ''
for a in range(0,rounds):
(na, ha), (nd, hd) = runRound(p1,p2,ha,hd)
sa += na
sd += nd
return sa, sd
def processPlayers(players):
for i,p in enumerate(players):
base,ext = os.path.splitext(p)
if ext == '.py':
py_compile.compile(p)
players[i] = '%s %sc' %( PYTHON_PATH, p)
return players
print "Finding warriors in " + sys.argv[1]
players=[sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)]
players=processPlayers(players)
num_iters = 1
if len(sys.argv) == 3:
num_iters = int(sys.argv[2])
print "Running %s tournament iterations" % (num_iters)
total_scores={}
for p in players:
total_scores[p] = 0
for i in range(1,num_iters+1):
print "Tournament %s" % (i)
scores={}
for p in players:
scores[p] = 0
for i1 in range(0,len(players)):
p1=players[i1];
for i2 in range(i1,len(players)):
p2=players[i2];
# rounds = random.randint(50,200)
rounds = 100
#print "Running %s against %s (%s rounds)." %(p1,p2,rounds)
s1,s2 = runGame(rounds,p1,p2)
#print (s1, s2)
if (p1 == p2):
scores[p1] += (s1 + s2)/2
else:
scores[p1] += s1
scores[p2] += s2
players_sorted = sorted(scores,key=scores.get)
for p in players_sorted:
print (p, scores[p])
winner = max(scores, key=scores.get)
print "\tWinner is %s" %(winner)
total_scores[p] += 1
print '-'*10
print "Final Results:"
players_sorted = sorted(total_scores,key=total_scores.get)
for p in players_sorted:
print (p, total_scores[p])
winner = max(total_scores, key=total_scores.get)
print "Final Winner is " + winner
- Keluhan tentang python mengerikan saya diterima, karena saya yakin ini menyebalkan lebih dari satu cara
- Perbaikan bug diterima
Daftar Perubahan Pencetak Gol:
- Cetak pemain dan skor yang diurutkan, dan nyatakan pemenang (29/4, Casey)
- Menjalankan beberapa turnamen secara opsional (
./score warriors/ num_tournaments)
) default = 1, mendeteksi & mengkompilasi sumber python (4/29, Casey) - Perbaiki bug yang sangat bodoh di mana pemain kedua melewati sejarah yang salah. (4/30, dmckee; terima kasih Josh)
Prajurit awal
Sebagai contoh, dan agar hasilnya dapat diverifikasi
malaikat
#include <stdio.h>
int main(int argc, char**argv){
printf("c\n");
return 0;
}
atau
#!/bin/sh
echo c
atau
#!/usr/bin/python
print 'c'
setan
#include <stdio.h>
int main(int argc, char**argv){
printf("t\n");
return 0;
}
Acak
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
int main(int argc, char**argv){
srandom(time(0)+getpid());
printf("%c\n",(random()%2)?'c':'t');
return 0;
}
Perhatikan bahwa pencetak gol dapat memanggil kembali prajurit berkali-kali dalam satu detik, jadi upaya serius harus dilakukan untuk memastikan keacakan hasil jika waktu digunakan untuk seed PRNG.
TitForTat
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv){
char c='c';
if (argv[1] && (
(argv[1][0] == 'R') || (argv[1][0] == 'E')
) ) c='t';
printf("%c\n",c);
return 0;
}
Yang pertama yang benar-benar melakukan sesuatu dengan sejarah.
Menjalankan pencetak gol hanya pada hasil prajurit yang disediakan
Finding warriors in warriors/
Running warriors/angel against warriors/angel.
Running warriors/angel against warriors/devil.
Running warriors/angel against warriors/random.
Running warriors/angel against warriors/titfortat.
Running warriors/devil against warriors/devil.
Running warriors/devil against warriors/random.
Running warriors/devil against warriors/titfortat.
Running warriors/random against warriors/random.
Running warriors/random against warriors/titfortat.
Running warriors/titfortat against warriors/titfortat.
('warriors/angel', 365)
('warriors/devil', 832)
('warriors/random', 612)
('warriors/titfortat', 652)
Iblis itu, dia seorang perajin, dan orang-orang baik tampaknya datang terakhir.
Hasil
dari menjalankan "resmi"
('angel', 2068)
('helpvamp', 2295)
('pavlov', 2542)
('random', 2544)
('littleschemer', 2954)
('devil', 3356)
('simpleton', 3468)
('secrethandshake', 3488)
('antit42t', 3557)
('softmajo', 3747)
('titfor2tats', 3756)
('convergence', 3772)
('probabimatic', 3774)
('mistrust', 3788)
('hyperrationalwasp', 3828)
('bygones', 3831)
('honoramongthieves', 3851)
('titfortat', 3881)
('druid', 3921)
('littlelisper', 3984)
('shark', 4021)
('randomSucker', 4156)
('gradual', 4167)
Winner is ./gradual
sumber
return (s1, L1+h1), (s2, L2+h1)
kereturn (s1, L1+h1), (s2, L2+h2)
[NoteL2+h2
bukannyaL2+h1
di akhir]? // Kesalahan cut-n-paste atau sesuatu yang sama bodohnya. Sheesh!Jawaban:
Bertahap
Strategi ini didasarkan pada sebuah makalah oleh Beaufils, Delahaye dan Mathieu . C saya benar-benar bukan yang terbaik, jadi jika ada yang punya saran untuk meningkatkan / mempercepat kode, beri tahu saya!
[Sunting] Layak untuk dicatat adalah bahwa Gradual dirancang untuk menjadi strategi yang mengungguli Tit untuk Tat. Ia memiliki sifat yang serupa dalam hal ia bersedia untuk bekerja sama dan membalas terhadap lawan yang membelot. Tidak seperti Tit untuk Tat, yang hanya memiliki ingatan tentang babak terakhir yang dimainkan, Gradual akan mengingat interaksi lengkap dan cacat berapa kali lawan telah membelot sejauh ini. Akan tetapi, itu akan menawarkan kerja sama timbal balik lagi.
Seperti biasa, kinerja strategi sedikit tergantung pada susunan strategi lainnya. Juga kertas asli tidak benar-benar jelas pada beberapa detail.
sumber
Jabat Tangan Rahasia
Strategi di sini adalah mengorbankan 10 putaran pertama untuk melakukan jabat tangan "rahasia". Jika saya bersel dengan diri saya sendiri, saya kemudian mengenali sejarah 10 langkah pertama dan memakai topi Malaikat saya untuk sisa permainan. Segera setelah saya menyadari bahwa teman satu sel saya bukan diri saya sendiri, saya berubah menjadi Iblis dalam upaya untuk mengambil keuntungan dari teman sel yang terlalu kooperatif.
Apakah dengan mengorbankan 10 putaran pertama akan memungkinkan saya untuk menyingkirkan Iblis itu sendiri sangat bergantung pada berapa banyak entri yang ada. Untuk meminimalkan kerusakan, hanya 3 yang bekerja sama muncul di jabat tangan.
Sunting: TAGMATCH dinamis sekarang untuk mencegah kesalahan bodoh seperti hanya mengubah salah satunya dan agar saya dapat membuat TAG dinamis di beberapa titik di masa mendatang.
Sunting 2: Sekarang menghasilkan tag secara acak pada jalankan pertama dan menyimpannya dalam file yang ditentukan oleh
sys.argv[0]
(.pyc
diganti dengan.py
jadi pergi ke kode, bukan bytecode, file). Saya pikir ini adalah satu-satunya informasi yang dimiliki semua contoh saya yang tidak dimiliki orang lain, jadi sepertinya satu-satunya pilihan untuk menghindari parasit.sumber
TAG
sedang diputar mundur. Namun, bukankah seharusnya AndaTAGMATCH
menjadi 'KEEEKEEEKE'?"".join({('c', 'c'):'K', ('t', 't'): 'E'}[moves] for moves in zip(TAG, TAG))
.py
file untuk kode Anda dan mengekstrak TAG. Saya tidak akan melakukan itu di C, ...Si Kecil Lisper
Iblis
Pertimbangkan yang berikut ini, format (Player1, Player2)
Dengan asumsi bahwa P2 adalah iblis, tidak mungkin iblis kehilangan poin, bahkan hal terburuk yang dapat ia lakukan adalah mendapatkan hanya satu poin. Oleh karena itu, melawan lawan yang murni acak, skor terburuk iblis akan tepat (5/2) * n di mana n adalah jumlah "permainan" yang dimainkan. Kasus terburuk absolutnya adalah melawan dirinya sendiri, di mana skornya akan n, dan kasus terbaiknya adalah melawan malaikat, yang akan menjadi 4 * n
Menegaskan: optimal_strat = iblis
ini pertandingan. Melakukan backstabbing pada teman satu sel saya adalah strategi yang jauh lebih baik daripada kerja sama karena ini membantu skor saya lebih banyak (+4). BONUS - dia terbanting (-1)! Jika saya menjulurkan leher untuknya, saya berdiri untuk mendapatkan (+2) dan longgar (-1). Oleh karena itu, pengkhianatan secara statistik dihargai.
Tetapi apakah itu optimal?
Tidak ada alasan untuk PERNAH (di bawah sistem penilaian ini) bekerja sama.
Dalam sistem KOTH, memaksimalkan pengembalian sangat penting. Bahkan jika Anda memiliki dua bot yang disinkronkan dan bekerja sama dengan sempurna, skor individu mereka hanya akan dikuatkan oleh 200 poin untuk sportivitas mereka. Iblis di sisi lain akan mendapatkan setidaknya 100 poin, dengan kasus rata-rata 200 dan maksimum 400, dan biaya lawan-lawannya masing-masing hingga 100 poin! Jadi bisa dibilang, iblis benar-benar skor rata-rata 300 permainan, naik menjadi 500.
Intinya - waktu akan memberi tahu
Bagi saya, sepertinya skor harus dipertimbangkan kembali agar iblis tidak mengambil hari itu. Meningkatkan skor kerjasama ke 3 semua mungkin melakukannya. Namun dimungkinkan untuk mendeteksi setan dan mencegah mereka dari mencetak 400 penuh mereka, seperti pavlov dan dendam menunjukkan. Dapatkah saya membuktikan bahwa salah satu dari mereka akan mengambil poin yang cukup untuk kerja sama mereka untuk membenarkan iman mereka? tidak. Semua itu tergantung pada bidang final pesaing.
Dan tolong lakukan yang terburuk untuk posting ini. Saya ingin menulis makalah senior saya tentang ini ketika semua dikatakan dan dilakukan.
Riwayat versi
VERSI RESMI DARI LISPER
MENGEMBANGKAN VERSI LISPER
sumber
fink install clisp
:: mengetuk jari berulang kali ::There is no reason to EVER (under this scoring system) co-operate
hanya setengah benar. Jika Anda tahu bahwa lawan Anda tidak memperhitungkan sejarah (malaikat, iblis, acak) maka Anda harus selalu membelot. Jika lawan Anda memperhitungkan histori dan Anda dapat melakukan sinkronisasi maka Anda bisa melakukan yang lebih baik. Saya punya beberapa ide yang berputar di sekitar mendeteksi apakah lawan itu rasional atau superrasional.(random 20)
memberi 2, 5, atau 8,(/ (+1 rand-num) 10)
adalah 0,3, 0,6, 0,9, dan sisa pembagian dengan 0,3 adalah 0; jadi(floor *dbag* *margin*)
mati.Ketidakpercayaan (varian)
Yang ini keluar pertama dalam tes saya sendiri bertahun-tahun yang lalu (saat itu saya di kelas 11 dan melakukan tesis kecil tentang hal ini, menggunakan strategi yang dirancang oleh siswa lain juga). Ini dimulai dengan urutan
tcc
(dan bermain seperti Tit untuk Tat setelah itu.Permintaan maaf untuk kode yang mengerikan; jika seseorang bisa membuat itu lebih pendek sementara tidak bermain golf, saya akan berterima kasih :-)
sumber
case 1: case2: printf(...); break;
. Dan gcc ingin deklarasi eksplisitstring.h
untuk digunakanstrlen
. Dalam hal apapun saya menjalankannya.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
kapanh = ''
. Saya menebakargc=1
.Rudal Anti-T42T
Apakah cukup baik terhadap pangkalan prajurit: membunuh Angel, sedikit dipukuli oleh Iblis (tetapi menjaga skor rendah), umumnya mengalahkan RAND dengan mudah, dan hanya sedikit mengalahkan Tit untuk Tat. Apakah buruk saat bermain melawan dirinya sendiri.
sumber
Konvergensi
Awalnya bagus, lalu bermain secara acak dengan memperhatikan sejarah lawan.
Saya sudah mencoba mengurangi bobot pada sejarah, tetapi belum mengoptimalkannya dengan baik.
sumber
Hiu
Cukup baik terhadap daftar base.
sumber
Pavlov - Menangkan Menginap, Kalah Beralih
Pada giliran pertama itu bekerja sama, dan kemudian bekerja sama jika dan hanya jika kedua pemain memilih pilihan yang sama pada langkah sebelumnya.
sumber
hist[0]
(hist[-1]
selalu merupakan langkah pertama dari putaran)?Hormatilah Pencuri
Perhatikan bahwa pada
THIEVES_CANT
dasarnya itu adalah jabat tangan, meskipun itu hanya akan muncul saat bermain melawan kooperator. Namun, ia menghindari masalah parasit dengan memeriksa persilangan selanjutnya. Cukup baik terhadap daftar base.sumber
"Probabimatic"
Mulai dengan bekerja sama, lalu memilih opsi mana saja yang memberikan nilai tertinggi yang diharapkan. Sederhana.
Dulu mulai dengan bekerja sama, tetapi sekarang tampaknya membelot sebenarnya bekerja lebih baik. EDIT: Oh, tunggu, sebenarnya tidak.
sumber
for (char c = *str;
kechar c; for (c = *str;
maka gcc akan mengkompilasi ini tanpa mengeluh bahwa itu perlu dimasukkan ke mode C99.Tawon Hiperrasional
Diimplementasikan di Jawa karena saya tidak yakin bagaimana rumitnya struktur data akan berakhir. Jika ini merupakan masalah bagi seseorang maka saya pikir saya dapat mem-port-nya ke bash tanpa terlalu banyak masalah karena pada akhirnya hanya menggunakan array asosiatif sederhana.
Catatan : Saya telah menghapus ini dari sebuah paket sesuai dengan versi terbaru dari patch saya ke pencetak gol untuk menangani Java. Jika Anda ingin memposting solusi Java yang menggunakan kelas dalam maka Anda harus menambal tambalan.
Perubahan yang saya buat pada pencetak gol untuk menjalankan ini adalah:
Terima kasih kepada @rmckenzie karena melipat dalam fungsi penantang saya.
sumber
Exception in thread "main" java.lang.NoClassDefFoundError: //warriors/HyperrationalWasp Caused by: java.lang.ClassNotFoundException: ..warriors.HyperrationalWasp at java.net.URLClassLoader$1.run(URLClassLoader.java:217) at java.security.AccessController.doPrivileged(Native Method) at java.net.URLClassLoader.findClass(URLClassLoader.java:205) at java.lang.ClassLoader.loadClass(ClassLoader.java:321) at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:294) at java.lang.ClassLoader.loadClass(ClassLoader.java:266)
Soft_majo
Ah well, satu lagi strategi standar, hanya untuk melengkapi line-up.
Yang ini memilih gerakan yang paling banyak dilakukan lawan; jika sama itu bekerja sama.
sumber
Pengisap acak
Yang ini akan cacat jika lawan terlalu sering cacat (ambang batas), tetapi secara acak akan mencoba menusuk kembali setiap saat.
Apakah cukup baik terhadap semua orang kecuali pemain Java dan Lisp (yang saya tidak bisa menjalankan, karena baik Java maupun Lisp pada mesin uji); setidaknya sebagian besar waktu.
sumber
BYGONES
Belum menemukan nilai terbaik untuk saat
bygones
ini. Saya tidak berharap ini menjadi strategi kemenangan , tapi saya tertarik pada kinerja strategi seperti apa yang saya pikir "baik" dalam kehidupan nyata. Revisi di masa depan mungkin termasuk memeriksa jumlah pembelotan bersama juga.sumber
Bantu Vampir
Memiliki hasil asimetris yang lucu ketika diadu dengan dirinya sendiri. Kalau saja solusi ini bisa diterapkan dalam kehidupan nyata.
sumber
Druid
Apakah cukup baik terhadap daftar pangkalan.
sumber
Simpleton
Tidak apa-apa terhadap daftar base.
sumber
Schemer kecil
Tidak buruk terhadap base set, tetapi cukup baik terhadap targetnya. Jelas, tidak ditulis dalam Skema.
sumber
Gayung untuk Dua Tats
favorit lama lainnya
sumber
sys.exit(0)
? Atau biarkan saja selesai. Sunting: Juga permohonan pertama ke program Anda tanpa riwayat yang menyebabkanIndexError
kapan Anda melakukannyaargv[1]
.len(history)<2
klausa, karena yang terakhir terlihat sepertielse
bagian.return
terutama untukku !