Salah satu sistem pemungutan suara yang paling umum untuk pemilihan pemenang tunggal adalah metode pemilihan pluralitas. Sederhananya, kandidat dengan suara terbanyak menang. Namun, pemilihan pluralitas secara matematis tidak sehat dan bertanggung jawab untuk menciptakan situasi di mana pemilih didorong untuk memilih "yang lebih rendah dari dua kejahatan" yang bertentangan dengan kandidat yang benar-benar mereka sukai.
Dalam permainan ini, Anda akan menulis program yang memanfaatkan sistem pemilihan pluralitas. Ini akan memberikan suara untuk satu dari tiga kandidat dalam pemilihan. Setiap kandidat dikaitkan dengan imbalan tertentu untuk diri Anda sendiri, dan tujuan Anda adalah memaksimalkan imbalan yang Anda harapkan.
Imbalannya "seragam" didistribusikan secara acak, diubah dengan setiap pemilihan, dan tambahkan ke 100. Kandidat A bisa mendapatkan hadiah 40, Calon B bisa mendapatkan hadiah 27, dan Calon C bisa memiliki hadiah 33. Setiap pemain memiliki serangkaian hadiah yang berbeda.
Ketika giliran Anda untuk memilih, Anda akan memiliki informasi yang tidak lengkap. Di bawah ini adalah informasi yang tersedia untuk Anda. Karena Anda tidak tahu apa hadiah individu pemain lain, itu akan menjadi tantangan Anda untuk memprediksi bagaimana mereka akan memberikan hasil jajak pendapat saat ini.
- Sebagian hasil pemilu sejauh ini
- Jumlah pendaftar (tidak termasuk diri Anda), yang belum memberikan suara
- Hadiah pribadi Anda untuk masing-masing kandidat
- Total hadiah grup untuk masing-masing kandidat
Setelah masing-masing pemain diberi kesempatan untuk memilih, kandidat dengan suara terbanyak menang sesuai dengan pemilihan pluralitas. Setiap pemain kemudian menerima jumlah poin yang sesuai dengan hasil mereka dari kandidat itu. Jika ada ikatan suara, maka jumlah poin yang diberikan akan menjadi rata-rata kandidat terikat.
Struktur Turnamen
Ketika pertama kali dipakai, peserta akan diberitahu jumlah pemilihan yang diadakan di turnamen. Saya akan mencoba menjalankan pemilihan yang sangat besar. Kemudian, setiap pemilihan akan dilakukan satu per satu.
Setelah peserta dikocok, masing-masing diberikan giliran untuk memilih. Mereka diberi informasi terbatas yang tercantum di atas dan mengembalikan nomor yang menandakan suara mereka. Setelah setiap pemilihan berakhir, setiap bot diberikan hasil jajak pendapat akhir dan skor mereka meningkat dari pemilihan itu.
Peserta yang menang akan menjadi orang dengan skor total tertinggi setelah sejumlah besar pemilihan diadakan. Pengontrol juga menghitung skor "dinormalisasi" untuk setiap kontestan dengan membandingkan skornya dengan distribusi skor yang diprediksi untuk bot pemungutan suara secara acak.
Rincian Pengiriman
Pengajuan akan mengambil bentuk Java 8 kelas. Setiap peserta harus mengimplementasikan antarmuka berikut:
public interface Player
{
public String getName();
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs);
public void receiveResults(int[] voteCounts, double result);
}
- Konstruktor Anda harus mengambil satu
int
sebagai parameter, yang akan mewakili jumlah pemilihan yang akan diadakan. - The
getName()
Metode mengembalikan nama untuk digunakan pada leaderboard. Ini memungkinkan Anda untuk memiliki nama yang diformat dengan baik, hanya saja jangan menjadi gila. - The
getVote(...)
kembali metode0
,1
atau2
untuk menandakan calon mana yang akan menerima suara. - The
receiveResults(...)
Metode ini terutama untuk memungkinkan adanya lebih strategi kompleks yang menggunakan data historis. - Anda diizinkan untuk membuat hampir semua metode / variabel instan lain yang ingin Anda rekam dan proses informasi yang diberikan kepada Anda.
Siklus Turnamen, Diperluas
- Peserta masing-masing instantiated dengan
new entrantName(int numElections)
. - Untuk setiap pemilihan:
- Pengontrol secara acak menentukan hadiah untuk setiap pemain untuk pemilihan ini. Kode untuk ini diberikan di bawah ini. Kemudian, itu mengocok pemain dan membuat mereka mulai memilih.
- Metode peserta ini
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
dipanggil, dan peserta mengembalikan suara mereka dari0
,1
atau2
untuk calon pilihan mereka. - Peserta yang
getVote(...)
metodenya tidak memberikan suara sah akan diberi suara acak. - Setelah semua orang memberikan suara, pengontrol menentukan hasil pemilihan dengan metode pluralitas.
- Para peserta diberitahu tentang penghitungan suara akhir dan imbalannya dengan memanggil metode mereka
public void receiveResults(int[] voteCounts, double result)
.
- Setelah semua pemilihan diadakan, pemenangnya adalah yang memiliki skor tertinggi.
Distribusi Hasil Secara Acak
The tepat distribusi akan memiliki dampak yang signifikan pada gameplay. Saya telah memilih distribusi dengan standar deviasi yang besar (sekitar 23,9235) dan yang mampu menciptakan hasil yang sangat tinggi dan sangat rendah. Saya telah memeriksa bahwa masing-masing dari tiga hadiah memiliki distribusi yang identik.
public int[] createPlayerPayoffs()
{
int cut1;
int cut2;
do{
cut1 = rnd.nextInt(101);
cut2 = rnd.nextInt(101);
} while (cut1 + cut2 > 100);
int rem = 100 - cut1 - cut2;
int[] set = new int[]{cut1,cut2,rem};
totalPayoffs[0] += set[0];
totalPayoffs[1] += set[1];
totalPayoffs[2] += set[2];
return set;
}
Lebih banyak aturan
Berikut adalah beberapa aturan yang lebih umum.
- Program Anda tidak boleh menjalankan / memodifikasi / membuat instantiate bagian dari controller atau peserta lain atau ingatan mereka.
- Karena program Anda tetap "hidup" untuk seluruh turnamen, jangan buat file apa pun.
- Jangan berinteraksi dengan, membantu, atau menargetkan program peserta lainnya.
- Anda dapat mengirimkan beberapa peserta, selama mereka cukup berbeda, dan selama Anda mengikuti aturan di atas.
- Saya belum menentukan batas waktu yang tepat, tetapi saya akan sangat menghargai runtime yang secara signifikan kurang dari satu detik per panggilan. Saya ingin bisa menjalankan pemilihan sebanyak mungkin.
Pengendali
Kontroler dapat ditemukan di sini . Program utamanya adalah Tournament.java
. Ada juga dua bot sederhana, yang akan bersaing, berjudul RandomBot
dan PersonalFavoriteBot
. Saya akan memposting dua bot ini sebagai jawaban.
Papan peringkat
Sepertinya ExpectantBot adalah pemimpin saat ini, diikuti oleh Monte Carlo dan kemudian StaBot.
Leaderboard - 20000000 elections:
767007688.17 ( 937.86) - ExpectantBot
766602158.17 ( 934.07) - Monte Carlo 47
766230646.17 ( 930.60) - StatBot
766054547.17 ( 928.95) - ExpectorBot
764671254.17 ( 916.02) - CircumspectBot
763618945.67 ( 906.19) - LockBot
763410502.67 ( 904.24) - PersonalFavoriteBot343
762929675.17 ( 899.75) - BasicBot
761986681.67 ( 890.93) - StrategicBot50
760322001.17 ( 875.37) - Priam
760057860.67 ( 872.90) - BestViableCandidate (2842200 from ratio, with 1422897 tie-breakers of 20000000 total runs)
759631608.17 ( 868.92) - Kelly's Favorite
759336650.67 ( 866.16) - Optimist
758564904.67 ( 858.95) - SometimesSecondBestBot
754421221.17 ( 820.22) - ABotDoNotForget
753610971.17 ( 812.65) - NoThirdPartyBot
753019290.17 ( 807.12) - NoClueBot
736394317.17 ( 651.73) - HateBot670
711344874.67 ( 417.60) - Follower
705393669.17 ( 361.97) - HipBot
691422086.17 ( 231.38) - CommunismBot0
691382708.17 ( 231.01) - SmashAttemptByEquality (on 20000000 elections)
691301072.67 ( 230.25) - RandomBot870
636705213.67 ( -280.04) - ExtremistBot
The tournament took 34573.365419071 seconds, or 576.2227569845166 minutes.
Berikut adalah beberapa turnamen yang lebih tua, tetapi tidak ada bot yang berubah fungsi sejak berjalan.
Leaderboard - 10000000 elections:
383350646.83 ( 661.14) - ExpectantBot
383263734.33 ( 659.99) - LearnBot
383261776.83 ( 659.97) - Monte Carlo 48
382984800.83 ( 656.31) - ExpectorBot
382530758.33 ( 650.31) - CircumspectBot
381950600.33 ( 642.64) - PersonalFavoriteBot663
381742600.33 ( 639.89) - LockBot
381336552.33 ( 634.52) - BasicBot
381078991.83 ( 631.12) - StrategicBot232
380048521.83 ( 617.50) - Priam
380022892.33 ( 617.16) - BestViableCandidate (1418072 from ratio, with 708882 tie-breakers of 10000000 total runs)
379788384.83 ( 614.06) - Kelly's Favorite
379656387.33 ( 612.31) - Optimist
379090198.33 ( 604.83) - SometimesSecondBestBot
377210328.33 ( 579.98) - ABotDoNotForget
376821747.83 ( 574.84) - NoThirdPartyBot
376496872.33 ( 570.55) - NoClueBot
368154977.33 ( 460.28) - HateBot155
355550516.33 ( 293.67) - Follower
352727498.83 ( 256.36) - HipBot
345702626.33 ( 163.50) - RandomBot561
345639854.33 ( 162.67) - SmashAttemptByEquality (on 10000000 elections)
345567936.33 ( 161.72) - CommunismBot404
318364543.33 ( -197.86) - ExtremistBot
The tournament took 15170.484259763 seconds, or 252.84140432938332 minutes.
Saya juga menjalankan turnamen 10m kedua, mengkonfirmasikan keunggulan ExpectantBot.
Leaderboard - 10000000 elections:
383388921.83 ( 661.65) - ExpectantBot
383175701.83 ( 658.83) - Monte Carlo 46
383164037.33 ( 658.68) - LearnBot
383162018.33 ( 658.65) - ExpectorBot
382292706.83 ( 647.16) - CircumspectBot
381960530.83 ( 642.77) - LockBot
381786899.33 ( 640.47) - PersonalFavoriteBot644
381278314.83 ( 633.75) - BasicBot
381030871.83 ( 630.48) - StrategicBot372
380220471.33 ( 619.77) - BestViableCandidate (1419177 from ratio, with 711341 tie-breakers of 10000000 total runs)
380089578.33 ( 618.04) - Priam
379714345.33 ( 613.08) - Kelly's Favorite
379548799.83 ( 610.89) - Optimist
379289709.83 ( 607.46) - SometimesSecondBestBot
377082526.83 ( 578.29) - ABotDoNotForget
376886555.33 ( 575.70) - NoThirdPartyBot
376473476.33 ( 570.24) - NoClueBot
368124262.83 ( 459.88) - HateBot469
355642629.83 ( 294.89) - Follower
352691241.83 ( 255.88) - HipBot
345806934.83 ( 164.88) - CommunismBot152
345717541.33 ( 163.70) - SmashAttemptByEquality (on 10000000 elections)
345687786.83 ( 163.30) - RandomBot484
318549040.83 ( -195.42) - ExtremistBot
The tournament took 17115.327209018 seconds, or 285.25545348363335 minutes.
sumber
Array
berisi hitungan semua suara. Apakah saya benar?Jawaban:
NoThirdPartyBot
Bot ini mencoba menebak kandidat mana yang akan menjadi yang ketiga, dan memilih kandidat yang paling disukainya dari dua pelari terdepan.
CircumspectBot
Bot ini memilih favoritnya yang belum dihilangkan secara matematis.
sumber
ExpectantBot
Bot ini menghitung nilai yang diharapkan dari setiap opsi pemungutan suara dengan asumsi bahwa semua pemilih sesudahnya akan memilih secara acak.
sumber
HipBot
HipBot tidak peduli dengan pembayaran. Uang hanyalah obat penenang yang mengalihkan perhatian dari seni sejati.
HipBot ingin memilih seseorang yang nyata , bukan sekadar perusahaan. Dia juga ingin mengenakan baju kampanye setelah kekalahan memalukan mereka, jadi dia merasa superior setiap kali pemenang melakukan sesuatu yang salah.
Oleh karena itu, HipBot memberikan suara untuk orang dengan suara terendah atau, jika ada seri, siapa pun yang mendapatkan pembayaran yang lebih baik. Makan organik saja tidak gratis.
HipBot juga belum diuji, jadi beri tahu saya jika ada sesuatu yang terjadi.
EDIT: ditambahkan dalam tiebreak yang lebih kompetitif, komentar bernas.
sumber
PersonalFavoriteBot
Bot ini hanya memberikan suara untuk kandidat dengan hadiah pribadi tertinggi, mengabaikan yang lainnya. Salah satu poin utama dari tantangan ini adalah untuk menunjukkan bagaimana ini bukan strategi yang optimal.
RandomBot
Bot ini memberikan suara secara acak. Terlepas dari jumlah pemilihan yang dilakukan (selama itu cukup tinggi, seperti lebih dari 100), skor yang dinormalisasi kontestan ini berfluktuasi antara -2 dan 2.
sumber
Pengikut
Follower ingin menyesuaikan diri. Ia berpikir cara terbaik untuk mencapainya adalah dengan memilih dengan cara yang sama seperti orang lain, atau setidaknya dengan pluralitas sejauh ini. Ini akan memutuskan hubungan dengan preferensi sendiri, untuk menunjukkan sedikit kebebasan. Tapi jangan terlalu banyak.
Catatan: Saya belum menguji ini, jadi beri tahu saya jika ada kesalahan.
sumber
Monte Carlo
Ini mensimulasikan sejumlah besar pemilihan acak. Kemudian ia memilih pilihan yang memaksimalkan keuntungannya sendiri.
sumber
StatBot
StatBot didasarkan pada ExpectantBot; namun, alih-alih mengasumsikan bahwa setiap suara sama-sama memungkinkan, ia mengumpulkan statistik tentang bagaimana orang memilih dan menggunakannya untuk memperkirakan probabilitas.
sumber
Calon yang layak
Versi yang cukup banyak direvisi kiriman asli saya. Yang ini masih menghilangkan setiap kandidat yang tidak dapat menang mengingat sisa suara yang akan diberikan, tetapi kemudian menggunakan strategi yang mencoba untuk mengoptimalkan hasil relatif daripada yang absolut. Tes pertama adalah mengambil rasio pembayaran pribadi saya dengan hasil keseluruhan untuk setiap kandidat, mencari nilai terbaik di sana. Saya kemudian mencari rasio lain yang sangat dekat dengan yang terbaik dan jika ada satu yang memiliki hasil keseluruhan yang lebih rendah daripada yang terbaik saya memilih yang sebaliknya. Semoga ini akan cenderung menekan pembayaran pemain lain sambil menjaga milik saya cukup tinggi.
Bot ini hampir sama baiknya dengan yang asli pada pengujian saya sendiri, tetapi tidak cukup. Kita harus melihat bagaimana hal itu bertentangan dengan bidang penuh.
sumber
CircumspectBot
?Optimis
Optimis sangat optimis dan mengasumsikan bahwa setengah dari pemilih yang tersisa akan memilih kandidat yang memberikan hadiah terbaik.
sumber
ABotDoNotForget
Tujuannya sederhana: menentukan kecenderungan keseluruhan menggunakan total hadiah dan menghitung jumlah waktu yang lebih rendah / sedang / lebih tinggi dimenangkan. Dia kemudian akan memilih yang paling mungkin menang.
Edit:
Beberapa perubahan dilakukan dalam algorythm keputusan, sekarang memperhitungkan hasil terbaiknya sendiri. Seharusnya sekarang dapat memilih lebih baik ketika distribusi saat ini membuatnya memilih untuk Bawah sendiri ketika orang lain di mana memberikan suara untuk hasil yang lebih tinggi.sumber
Priam
Priam membenci rekursi. Dia memperkirakan probabilitas setiap bot yang tersisa berdasarkan total hadiah dan kemudian menghitung cara terbaik untuk memaksimalkan hadiahnya.
Jauh lebih cepat daripada Odysseus karena tidak ada rekursi (berjalan dalam waktu O (n ^ 2)) dan dapat melakukan satu juta pemilihan dalam waktu sekitar 15 detik.
sumber
NoClueBot
NoClue tidak benar-benar mengenal Java atau matematika dengan baik, jadi dia tidak tahu apakah rasio bobot ini akan membantunya menang. Tapi dia berusaha.
SomeClueBot
SomeClueBot telah dinonaktifkan.
sebenarnya menggunakan logika! dulu menggunakan logika, yang ternyata tidak efisien, jadi alih-alih dia menjadi sadar akan hasil total, bukan miliknya sendiri. menggunakan logika lagi! Tetapi dia tidak melakukannya dengan baik dengan semua pengikut dan optimis ini, dan bahkan orang-orang yang tidak peduli! :)Terkadang SecondBestBot
Pada dasarnya PersonalFavouriteBot, ditingkatkan (dalam teori).
sumber
Ekstremis
Selalu pilih kandidat dengan hadiah terendah
sumber
SmashAttemptByEquality
Tujuannya adalah untuk menyamakan semua kandidat, lalu SMASH! semua bot lain di babak terakhir.
Ini adalah algoritma destruktif yang mencoba untuk menghilangkan semua yang lain, untuk mengklaim kemenangan.
Perhatikan bahwa ini belum teruji !
sumber
Bot Dasar
Basic Bot hanya memberikan suara untuk kandidat yang tidak dihilangkan dan memiliki hasil maksimum terbesar dari kandidat tersebut.
sumber
Favorit Kelly
Saya mulai dengan CircumspectBot, tetapi tidak banyak yang tersisa. Membuat semacam tebakan membosankan pada distribusi probabilitas suara yang tersisa, dan kemudian membuat pilihan yang memaksimalkan utilitas log-nya sendiri (Kriteria Kelly). Bukan yang tercepat, tetapi di dalam ball park beberapa yang lain. Juga, ini cukup kompetitif dengan bidangnya (seperti ketika saya mulai mengerjakan ini, dan mengunduh bot lain).
Juga tersedia di https://gist.github.com/jkominek/dae0b3158dcd253e09e5 jika itu lebih sederhana.
sumber
CommunismBot
CommunismBot berpikir kita semua harus akur dan memilih kandidat yang terbaik untuk semua orang.
Hatebot
Hatebot selalu memilih kandidat terbaik. Kecuali kalau mereka adalah pesta kotor 1. Orang-orang itu mengerikan.
StrategicBot
Pemungutan suara StrategicBot untuk kandidat terbaik asalkan mereka berada dalam satu standar deviasi dari kandidat terbaik berikutnya, mengingat jumlah pemilih yang tersisa.
sumber
ExpectorBot
Berusaha memprediksi bagaimana semua Bot lainnya akan memberikan suara dengan menghitung Pembayaran rata-rata untuk yang lain. Suara default untuk hadiah terbaik, tetapi akan memilih terbaik kedua, jika memiliki suara yang lebih diharapkan daripada yang terbaik, pembayaran yang lebih baik daripada rata-rata untuk saya dan pembayaran terburuk memiliki peluang untuk memenangkan hal ini.
sumber
LockBot
Hanya seorang filsuf yang kesepian, mencari "e" -nya ...
sumber
Menang kalah
Jika Anda menang, saya kalah! Sesederhana itu. Jadi bot ini memilih salah satu yang dia suka dan tidak disukai semua orang.
sumber