Dalam tantangan ini, Anda akan memainkan dilema tahanan yang diulang-ulang dan berisik.
The Dilema Tahanan adalah skenario dalam teori permainan di mana ada dua pemain, masing-masing dengan dua pilihan: bekerja sama, atau cacat. Setiap pemain melakukan lebih baik untuk diri mereka sendiri jika mereka cacat daripada jika mereka bekerja sama, tetapi kedua pemain akan lebih suka hasil di mana kedua pemain bekerja sama dengan yang di mana kedua pemain cacat.
Dilema tahanan yang diulang adalah permainan yang sama, kecuali Anda bermain melawan lawan yang sama berulang kali, dan Anda tahu apa yang telah dimainkan lawan Anda di masa lalu. Tujuan Anda adalah selalu mengumpulkan skor tertinggi untuk diri sendiri, terlepas dari bagaimana lawan Anda melakukannya.
Dilema narapidana yang bising dan berulang-ulang menimbulkan kebisingan dalam komunikasi. Pengetahuan Anda tentang apa yang telah dimainkan lawan Anda di masa lalu akan memiliki sedikit kebisingan. Anda juga akan tahu gerakan apa yang Anda lakukan di masa lalu. Tingkat kebisingan konstan pada putaran melawan lawan yang sama, tetapi berbeda antara putaran yang berbeda.
Tantangan
Dalam tantangan ini, Anda akan menulis sebuah program Python 3 untuk memainkan dilema narapidana iterated yang berisik.
Program Anda akan menerima tiga input:
Gerakan Anda sendiri, tanpa flips acak diterapkan.
Gerakan lawan Anda, dengan flips acak diterapkan.
Variabel status, yang dimulai sebagai daftar kosong setiap putaran, dan yang dapat Anda modifikasi jika diinginkan. Anda dapat mengabaikan ini jika Anda tidak ingin menggunakannya.
Program Anda harus menampilkan 'c'
untuk bekerja sama atau 'd'
cacat.
Misalnya, inilah program yang bekerja sama jika lawan telah bekerja sama setidaknya 60% dari waktu di masa lalu, setelah membalik acak diterapkan, dan untuk 10 membalik pertama:
def threshold(my_plays, their_flipped_plays, state):
if len(their_flipped_plays) < 10:
return 'c'
opp_c_freq = their_flipped_plays.count('c')/len(their_flipped_plays)
if opp_c_freq > 0.6:
return 'c'
else:
return 'd'
Jika Anda tidak tahu Python, tulis kiriman Anda dalam pseudocode, dan seseorang (saya atau anggota lain dari situs) dapat membuat program Python yang sesuai.
Gameplay
Pelari turnamen dapat ditemukan di sini: permainan berisik . Lari noisy-game.py
untuk menjalankan turnamen. Saya akan menjaga repositori itu diperbarui dengan kiriman baru. Contoh program dapat ditemukan di basic.py
.
Skor keseluruhan suatu program adalah total skornya lebih dari 100 permainan.
Sebuah permainan terdiri dari pertarungan round-robin dari setiap pemain melawan masing-masing pemain, termasuk dirinya sendiri. Sebuah pertarungan terdiri dari 100 putaran. Putaran terdiri dari 300 gerakan, yang masing-masing melibatkan keluaran 'c'
atau 'd'
.
Kiriman Anda akan memainkan pertarungan melawan setiap kiriman, termasuk milik Anda. Setiap pertandingan akan terdiri dari 100 putaran. Selama setiap putaran, probabilitas balik akan dipilih secara acak dari [0, 0.5]
.
Setiap putaran akan terdiri dari 300 gerakan. Pada setiap gerakan, kedua program akan menerima semua permainan sebelumnya yang telah mereka coba, dan semua permainan sebelumnya yang telah dibuat oleh program lain, setelah flips diterapkan, dan variabel status, yang merupakan daftar yang dapat diubah yang dapat diubah oleh program jika diinginkan. Program akan menampilkan gerakan mereka.
Bergerak diberi skor sebagai berikut: Jika suatu program memainkan 'c'
, program lawan mendapat 2 poin. Jika suatu program memainkan 'd'
, program itu mendapat 1 poin.
Kemudian, setiap gerakan dibalik secara independen dengan probabilitas sama dengan probabilitas balik, dan disimpan untuk ditunjukkan kepada lawan.
Setelah semua putaran dimainkan, kami menjumlahkan jumlah poin yang didapat setiap pemain dalam setiap pertandingan. Kemudian, kami menggunakan sistem penilaian berikut untuk menghitung skor setiap pemain untuk permainan. Skor ini dilakukan setelah semua pertandingan selesai.
Mencetak gol
Kami akan menggunakan skor evolusi. Setiap program dimulai dengan bobot yang sama. Kemudian, bobot diperbarui sebagai berikut, untuk 100 iterasi, menggunakan total poin dari game:
Bobot baru masing-masing program sebanding dengan produk dari bobot sebelumnya dan total poin rata-rata, ditimbang oleh bobot lawan-lawannya.
100 pembaruan semacam itu diterapkan, dan bobot terakhir adalah skor masing-masing program untuk permainan tersebut.
Skor keseluruhan akan menjadi jumlah lebih dari 100 kali permainan.
Para pemain akan menjadi semua jawaban yang valid untuk tantangan ini, ditambah enam program dasar untuk memulai.
Peringatan
Jangan memodifikasi input. Jangan mencoba untuk mempengaruhi pelaksanaan program lain, kecuali melalui bekerja sama atau membelot. Jangan membuat pengorbanan pengorbanan yang mencoba untuk mengakui pengajuan lain dan manfaat lawan itu dengan biaya sendiri. Celah standar dilarang.
EDIT: Kiriman mungkin tidak sama persis dengan duplikat program dasar atau pengajuan sebelumnya.
Jika Anda memiliki pertanyaan, jangan ragu untuk bertanya.
Hasil saat ini
nicht_genug: 40.6311
stealer: 37.1416
enough: 14.4443
wait_for_50: 6.947
threshold: 0.406784
buckets: 0.202875
change_of_heart: 0.0996783
exploit_threshold: 0.0670485
kickback: 0.0313357
tit_for_stat: 0.0141368
decaying_memory: 0.00907645
tit_for_whoops: 0.00211803
slider: 0.00167053
trickster: 0.000654875
sounder: 0.000427348
tit_for_tat: 9.12471e-05
stubborn_stumbler: 6.92879e-05
tit_for_time: 2.82541e-05
jedi2sith: 2.0768e-05
cooperate: 1.86291e-05
everyThree: 1.04843e-05
somewhat_naive: 4.46701e-06
just_noise: 1.41564e-06
growing_distrust: 5.32521e-08
goldfish: 4.28982e-09
vengeful: 2.74267e-09
defect: 3.71295e-10
alternate: 2.09372e-20
random_player: 6.74361e-21
Hasil dengan hanya jawaban untuk pertanyaan ini dan program dasar yang mengabaikan permainan lawan:
nicht_genug: 39.3907
stealer: 33.7864
enough: 20.9032
wait_for_50: 5.60007
buckets: 0.174457
kickback: 0.0686975
change_of_heart: 0.027396
tit_for_stat: 0.024522
decaying_memory: 0.0193272
tit_for_whoops: 0.00284842
slider: 0.00153227
sounder: 0.000472289
trickster: 0.000297515
stubborn_stumbler: 3.76073e-05
cooperate: 3.46865e-05
tit_for_time: 2.42263e-05
everyThree: 2.06095e-05
jedi2sith: 1.62591e-05
somewhat_naive: 4.20785e-06
just_noise: 1.18372e-06
growing_distrust: 6.17619e-08
vengeful: 3.61213e-09
goldfish: 3.5746e-09
defect: 4.92581e-10
alternate: 6.96497e-20
random_player: 1.49879e-20
Kemenangan
Kompetisi akan tetap terbuka tanpa batas waktu, karena kiriman baru diposting. Namun, saya akan mengumumkan pemenang (menerima jawaban) berdasarkan hasil 1 bulan setelah pertanyaan ini diposting.
sumber
exploit_threshold()
beberapa kaliexploit_threshold1()
, dll dan menambahkannya keplayers
daftar. Mengapa saya mendapatkan hasil yang sangat berbeda untuk strategi yang identik?Jawaban:
Genug ist nicht genug
(bisa juga disebut
enough2
ataustealback
)Saya belajar bahwa tit asli untuk dua tats memang menunggu dua tats berturut-turut seperti
tit_for_whoops
halnya, dan memang sepertinya kita harus memaafkan dan melupakan (well, hampir ...) single tats sebelumnya. Dan banyak pemain yang cacat di babak terakhir. Saya masih lebih suka bersikap baik ketika semuanya baik-baik saja sejauh ini, tetapi bar toleransi bot terus semakin rendah.sumber
Tit-Untuk-Whoops
Terinspirasi oleh strategi dari ncase.me/trust
Cacat hanya jika pemain lain telah membelot dua kali berturut-turut, untuk mencegah kesalahpahaman.
sumber
Perubahan perasaan
Memiliki perubahan hati setengah jalan. Ternyata sangat baik.
sumber
Pencuri Strategi
Terinspirasi oleh cukup, change_of_heart, dan tit-for-whoops. Seharusnya sedikit lebih memaafkan. Saya mencoba mengubah angka untuk hasil terbaik tetapi mereka tidak ingin banyak berubah.
sumber
Tit-Untuk-Waktu
Jika Anda telah menghabiskan sebagian besar waktu menyakiti saya, saya hanya akan menyakiti Anda kembali. Mungkin.
sumber
Tumbuhnya Ketidakpercayaan
Semakin lawan mengkhianatiku, semakin aku tidak percaya itu hanya suara.
sumber
state
argumen bahwa secara default daftar? Daftar bisa berubah, sehingga negara dapat dimodifikasi dengan mudah.Jedi2Sith
Mulai dari semua yang bagus dan tanpa pamrih, tetapi seiring waktu pengaruh sisi gelap tumbuh semakin kuat, sampai titik tanpa kembali. Tidak ada yang bisa menghentikan pengaruh ini, tetapi semua hal buruk yang dilihatnya terjadi hanya berkontribusi pada kekuatan sisi gelap ...
Cobalah online!
sumber
Slider
Mulai dengan 'c', dan secara bertahap meluncur ke arah atau menjauh dari 'd'.
sumber
Stumbborn Stumbler
Didasarkan pada strategi ambang eksploit Anda dengan hanya permainan yang konsisten terus melacak untuk beralih antara cacat dan sebagian besar bekerja sama
UPDATE: Melacak dua bermain berturut-turut dan tiga berturut-turut, hanya menghukum dalam kondisi yang lebih keras dan menambahkan pilihan acak ketika tidak yakin
UPDATE 2: Kondisi dihapus dan fungsi distribusi ditambahkan
sumber
Bot Kebisingan
Saya pasti bekerja sama bot. Itu hanya kebisingan.
sumber
Cukup sudah
Mulai sebagai gayung untuk dua tats di mana dua tats tidak harus berturut-turut (tidak seperti
tit_for_whoops
). Jika harus bermaind
terlalu sering,d
-total.sumber
Bot Ikan Mas
Seekor ikan mas tidak pernah memaafkan, tetapi dengan cepat lupa.
sumber
sumber
Memori yang membusuk
Menimbang lebih banyak riwayat terkini. Perlahan-lahan melupakan masa lalu.
sumber
Pembayaran kembali
Beberapa ide yang kabur ...
sumber
Tidak Benar-Benar Mendapat Masalah "Kebisingan" Utuh
Jangan pernah memaafkan pengkhianat.
sumber
sounder:
sunting: menambahkan pembalasan dalam skenario dengan noise rendah
pada dasarnya, jika semua 4 langkah pertama bekerja sama, itu berarti kita harus mengharapkan lebih sedikit suara daripada biasanya. defect sedikit setiap sesekali untuk menebus poin yang lebih sedikit yang kita dapatkan dari tidak pernah membelot, dan membuatnya dapat disalahkan pada noise. kami juga membalas jika mereka membelot terhadap kami
jika lawan kita melakukan banyak pembelokan dalam belokan itu (2 atau lebih) kita hanya membelot ke arah mereka. jika itu hanya suara bising, suara itu akan mempengaruhi gerakan kita.
jika tidak, jika hanya 1 gerakan yang cacat, kami hanya melakukan tit sederhana untuk sisa permainan.
sumber
Bergantian
Pilihan secara acak di babak pertama, lalu berganti. Selalu cacat dalam 10 putaran terakhir.
sumber
Tunggu 50
Setelah 50 cacat, biarkan mereka memilikinya!
sumber
Entah mengapa naif
Saya hanya akan berasumsi bahwa jika Anda membelot kurang dari probabilitas balik (kira-kira) di n terakhir bergantian, itu kebisingan dan tidak Anda sedang berarti!
Belum angka keluar yang terbaik n , mungkin melihat lebih jauh ke dalam.
sumber
Setiap tiga
Cacat setiap tiga putaran terlepas. Juga cacat 50 putaran terakhir. Juga cacat jika lawannya membelot 4 dari 5 putaran terakhir.
sumber
Ember
Dimainkan dengan baik untuk memulai. Lihatlah 20 terakhir mereka, jika <25% d, mengembalikan c,> 75% d, mengembalikan d, dan di antaranya memilih secara acak di sepanjang fungsi probabilitas linier. 50 cacat terakhir. Punya ini pada 10 terakhir tetapi melihat banyak 50 cacat terakhir.
Pertama kali di sini jadi beri tahu saya jika ada sesuatu yang perlu diperbaiki (atau bagaimana saya bisa menguji ini).
sumber
players
untuk iterasi cepat.Tit-For-Stat
Cacat jika lawan telah membelot lebih dari separuh waktu.
sumber