Voting Strategis, Permainan

37

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 intsebagai 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 metode 0, 1atau 2untuk 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

  1. Peserta masing-masing instantiated dengan new entrantName(int numElections).
  2. Untuk setiap pemilihan:
    1. 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.
    2. Metode peserta ini public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)dipanggil, dan peserta mengembalikan suara mereka dari 0, 1atau 2untuk calon pilihan mereka.
    3. Peserta yang getVote(...)metodenya tidak memberikan suara sah akan diberi suara acak.
    4. Setelah semua orang memberikan suara, pengontrol menentukan hasil pemilihan dengan metode pluralitas.
    5. Para peserta diberitahu tentang penghitungan suara akhir dan imbalannya dengan memanggil metode mereka public void receiveResults(int[] voteCounts, double result).
  3. 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 RandomBotdan 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.
PhiNotPi
sumber
oO wow, punyaku sangat buruk!
Ismael Miguel
Menurut apa yang saya lihat dalam kode, parameter ke-2 adalah jumlah suara yang tersisa. Dan yang pertama adalah yang Arrayberisi hitungan semua suara. Apakah saya benar?
Ismael Miguel
1
@ IsmaelMiguel Ya.
PhiNotPi
1
Kedua. Mereka adalah hasil parsial dari pemilihan, yang merupakan suara yang dibuat oleh orang-orang di depan Anda dalam urutan acak.
PhiNotPi
2
Anda mungkin juga ingin melihat apa yang terjadi ketika Anda memberi para pemilih banyak klon. Sekilas, kadang-kadang SecondBestBot, NoThirdPartyBot dan optimis semua tampaknya mendapat manfaat dari kelompok pemungutan suara yang lebih besar. (Seperti halnya ekstrimis, dan, dengan caranya sendiri, komunisme tetapi itu kurang penting)
Saidoro

Jawaban:

10

NoThirdPartyBot

Bot ini mencoba menebak kandidat mana yang akan menjadi yang ketiga, dan memilih kandidat yang paling disukainya dari dua pelari terdepan.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NoThirdPartyBot implements Player {

    public NoThirdPartyBot(int e) {
    }


    @Override
    public String getName() {
        return "NoThirdPartyBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> order = order(totalPayoffs);

        if (payoffs[order.get(0)] > payoffs[order.get(1)]) {
            return order.get(0);
        } else {
            return order.get(1);
        }
    }

    static List<Integer> order(int[] array) {
        List<Integer> indexes = Arrays.asList(0, 1, 2);
        Collections.sort(indexes, (i1, i2) -> array[i2] - array[i1]);
        return indexes;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {
    }
}

CircumspectBot

Bot ini memilih favoritnya yang belum dihilangkan secara matematis.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class CircumspectBot implements Player {

    public CircumspectBot(int elections) {
    }

    @Override
    public String getName() {
        return "CircumspectBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> indexes = new ArrayList<>();
        int topVote = Arrays.stream(voteCounts).max().getAsInt();
        for (int index = 0; index < 3; index++) {
            if (voteCounts[index] + votersRemaining + 1 >= topVote) {
                indexes.add(index);
            }
        }
        Collections.sort(indexes, (i1, i2) -> payoffs[i2] - payoffs[i1]);

        return indexes.get(0);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }

}
Winston Ewert
sumber
4
Saya bertaruh Circumspect Bot benar-benar lebih baik daripada Bot Favorit Pribadi. Bagus.
isaacg
10

ExpectantBot

Bot ini menghitung nilai yang diharapkan dari setiap opsi pemungutan suara dengan asumsi bahwa semua pemilih sesudahnya akan memilih secara acak.

import java.util.Arrays;

public class ExpectantBot implements Player {

    public ExpectantBot(int elections) {
    }

    @Override
    public String getName() {
        return "ExpectantBot";
    }

    static double choose(int x, int y) {
        if (y < 0 || y > x) return 0;
        if (y > x/2) {
            // choose(n,k) == choose(n,n-k), 
            // so this could save a little effort
            y = x - y;
        }

        double denominator = 1.0, numerator = 1.0;
        for (int i = 1; i <= y; i++) {
            denominator *= i;
            numerator *= (x + 1 - i);
        }
        return numerator / denominator;
    }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = Arrays.stream(newVoteCounts).max().getAsInt();
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v*Math.pow(1/3.0, votersRemaining);
                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {      
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        return bestVote;

    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {   
    }

}
Winston Ewert
sumber
Tanpa metagaming berat dari lawan lain, aku akan terkejut jika ada yang mengalahkan orang ini.
DoctorHeckle
@ DoctorHeckle, saya punya harapan untuk StatBot, tapi saya pikir Anda benar.
Winston Ewert
9

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.

public class HipBot implements Player{

    public HipBot(int rounds){ /*Rounds are a social construct*/ }

    public String getName(){ return "HipBot"; }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs){

        int coolest = 0;
        int lowest = 100000000;
        int gains = 0;

        for( int count = 0; count < voteCounts.length; count++ ){

            if( voteCounts[count] < lowest || (voteCounts[count] == lowest && payoffs[count] > gains) ){

                lowest = voteCounts[count];
                coolest = count;
                gains = payoffs[count];

            }

        }

        return coolest;

    }

    public void receiveResults(int[] voteCounts, double result){ /*The past is dead*/ }

}

HipBot juga belum diuji, jadi beri tahu saya jika ada sesuatu yang terjadi.

EDIT: ditambahkan dalam tiebreak yang lebih kompetitif, komentar bernas.

DoctorHeckle
sumber
bekerja untuk saya, meskipun rasa iba untuk yang lebih longgar tidak berbuat banyak untuk nilainya :)
euanjt
5
Dia menang dalam pikirannya, dan baginya, itu yang terpenting: D
DoctorHeckle
8

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.

import java.lang.Math;
import java.util.Random;
/**
 * This bot picks the candidate with the highest personal payoff, ignoring everyone else's actions.
 * 
 * @author PhiNotPi 
 * @version 5/27/15
 */
public class PersonalFavoriteBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class PersonalFavoriteBot
     */
    public PersonalFavoriteBot(int e)
    {
       rnd = new Random(); 
       name = "PersonalFavoriteBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        //return rnd.nextInt(3);
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(payoffs[i] > payoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}

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.

import java.lang.Math;
import java.util.Random;
/**
 * This bot votes for a random candidate.
 * 
 * @author PhiNotPi 
 * @version 5/27/15
 */
public class RandomBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class RandomBot
     */
    public RandomBot(int e)
    {
       rnd = new Random(); 
       name = "RandomBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        return rnd.nextInt(3);
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}
PhiNotPi
sumber
7

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.

public class Follower implements Player
{
    public Follower(int e) { }

    public String getName()
    {
        return "Follower";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int mostPopular = 0;
        int mostVotes = voteCounts[0];
        for (int i = 1; i < voteCounts.length; i++) {
            int votes = voteCounts[i];
            if (votes > mostVotes || (votes == mostVotes && payoffs[i] > payoffs[mostPopular])) {
                mostPopular = i;
                mostVotes = votes;
            }
        }
        return mostPopular;

    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Catatan: Saya belum menguji ini, jadi beri tahu saya jika ada kesalahan.

isaacg
sumber
Tampaknya berhasil.
PhiNotPi
4

Monte Carlo

Ini mensimulasikan sejumlah besar pemilihan acak. Kemudian ia memilih pilihan yang memaksimalkan keuntungannya sendiri.

import java.util.ArrayList;
import java.util.List;

public class MonteCarlo implements Player{

    private static long runs = 0;
    private static long elections = 0;

    public MonteCarlo(int e) {
        elections = e;
    }

    @Override
    public String getName() {
        return "Monte Carlo (difficulty " + (runs / elections) + ")";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {
        elections++;
        double[] predictedPayoffs = new double[3];
        long startTime = System.nanoTime();
        while (System.nanoTime() - startTime <= 200_000){ //Let's give us 200 micro-seconds.
            runs++;
            int[] simulatedVoteCounts = voteCounts.clone();
            for (int j = 0; j < votersRemaining; j++){
                simulatedVoteCounts[((int) Math.floor(Math.random() * 3))]++;
            }
            for (int j = 0; j < 3; j++) {
                simulatedVoteCounts[j]++;
                List<Integer> winners = new ArrayList<>();
                winners.add(0);
                for (int k = 1; k < 3; k++) {
                    if (simulatedVoteCounts[k] > simulatedVoteCounts[winners.get(0)]) {
                        winners.clear();
                        winners.add(k);
                    } else if (simulatedVoteCounts[k] == simulatedVoteCounts[winners.get(0)]) {
                        winners.add(k);
                    }
                }
                for (int winner : winners) {
                    predictedPayoffs[j] += payoffs[winner] / winners.size();
                }
                simulatedVoteCounts[j]--;
            }
        }
        int best = 0;
        for (int i = 1; i < 3; i++){
            if (predictedPayoffs[i] > predictedPayoffs[best]){
                best = i;
            }
        }
        return best;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }
}
TheNumberOne
sumber
4

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.

import java.util.Arrays;


public class StatBot implements Player {

    static private int[][][] data = new int[3][3][3];
    private int[] voteCounts;

    StatBot(int unused) {

    }

    @Override
    public String getName() {
        return "StatBot";

    }

     static double choose(int x, int y) {
            if (y < 0 || y > x) return 0;
            if (y > x/2) {
                // choose(n,k) == choose(n,n-k), 
                // so this could save a little effort
                y = x - y;
            }

            double denominator = 1.0, numerator = 1.0;
            for (int i = 1; i <= y; i++) {
                denominator *= i;
                numerator *= (x + 1 - i);
            }
            return numerator / denominator;
        }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        int [] stats = data[indexes[0]][indexes[1]];
        int total_stats = Arrays.stream(stats).sum();
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = 0;
                for (int h : newVoteCounts) {
                    if (h > highest) highest = h;
                }
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v;
                value *= Math.pow((double)stats[0]/(double)total_stats, firstPartyVoters);
                value *= Math.pow((double)stats[1]/(double)total_stats, secondPartyVoters);
                value *= Math.pow((double)stats[2]/(double)total_stats, thirdPartyVoters);

                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {      
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        voteCounts[bestVote]++;
        this.voteCounts = voteCounts;

        return bestVote;

    }

    @Override
    public void receiveResults(int[] endVoteCounts, double result) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        for(int i = 0; i < 3; i++){
            data[indexes[0]][indexes[1]][i] += endVoteCounts[i] - voteCounts[i];
        }
    }
}
Winston Ewert
sumber
4

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.

 /**
  * This bot picks the candidate with the highest relative payoff out of those
  * candidates who are not already mathematically eliminated.
  *
  * @author Ralph Marshall
  * @version 5/28/2015
  */

import java.util.List;
import java.util.ArrayList;


public class BestViableCandidate implements Player
{
    private static int NUM_CANDIDATES = 3;
    private int relativeCount = 0;
    private int relativeCountLowerTotal = 0;
    private int totalRuns;

    public BestViableCandidate(int r) {
        totalRuns = r;
    }

    public String getName() {
        return "BestViableCandidate (" + relativeCount + " from ratio, with " + relativeCountLowerTotal + " tie-breakers of " + totalRuns + " total runs)";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {

        int i, maxVoteSoFar = 0;

        // First we figure out the maximum possible number of votes each candidate would get
        // if every remaining bot voted for it
        int [] maxPossibleVotes = new int[NUM_CANDIDATES];
        for (i = 0; i < NUM_CANDIDATES; i++) {

            // The voters remaining does not include me, so we need to add one to it
            maxPossibleVotes[i] = voteCounts[i] + votersRemaining + 1;

            if (voteCounts[i] > maxVoteSoFar) {
                maxVoteSoFar = voteCounts[i];
            }
        }

        // Then we throw out anybody who cannot win even if they did get all remaining votes
        List<Integer> viableCandidates = new ArrayList<Integer>();
        for (i = 0; i < NUM_CANDIDATES; i++) {
            if (maxPossibleVotes[i] >= maxVoteSoFar) {
                viableCandidates.add(Integer.valueOf(i));
            }
        }

        // And of the remaining candidates we pick the one that has the personal highest payoff
        // relative to the payoff to the rest of the voters
        int maxCandidate = -1;
        double maxRelativePayoff = -1;
        int maxPayoff = -1;
        int minTotalPayoff = Integer.MAX_VALUE;

        int originalMaxCandidate = -1;
        double originalMaxPayoff = -1;

        double DELTA = 0.01;

        double tiebreakerCandidate = -1;

        for (Integer candidateIndex : viableCandidates) {
            double relativePayoff = (double) payoffs[candidateIndex] / (double) totalPayoffs[candidateIndex];
            if (maxRelativePayoff < 0 || relativePayoff - DELTA > maxRelativePayoff) {
                maxRelativePayoff = relativePayoff;
                maxCandidate = candidateIndex;

                maxPayoff = payoffs[candidateIndex];
                minTotalPayoff = totalPayoffs[candidateIndex];

            } else if (Math.abs(relativePayoff - maxRelativePayoff) < DELTA) {
                if (totalPayoffs[candidateIndex] < minTotalPayoff) {
                    tiebreakerCandidate = candidateIndex;

                    maxRelativePayoff = relativePayoff;
                    maxCandidate = candidateIndex;

                    maxPayoff = payoffs[candidateIndex];
                    minTotalPayoff = totalPayoffs[candidateIndex];

                }
            }

            if (payoffs[candidateIndex] > originalMaxPayoff) {
                originalMaxPayoff = payoffs[candidateIndex];
                originalMaxCandidate = candidateIndex;
            }
        }

        if (tiebreakerCandidate == maxCandidate) {
            relativeCountLowerTotal++;
        }

        if (originalMaxCandidate != maxCandidate) {
            /*                System.out.printf("%nSelecting candidate %d with relative payoff %f (%d/%d) instead of %d with relative payoff %f (%d/%d)%n",
                              maxCandidate, (double) payoffs[maxCandidate]/(double)totalPayoffs[maxCandidate], payoffs[maxCandidate], totalPayoffs[maxCandidate],
                              originalMaxCandidate, (double) payoffs[originalMaxCandidate]/(double)totalPayoffs[originalMaxCandidate], payoffs[originalMaxCandidate], totalPayoffs[originalMaxCandidate]);
            */
            relativeCount++;
        }

        return maxCandidate;
    }
}
Ralph Marshall
sumber
1
Bukankah ini sama dengan CircumspectBot?
TheNumberOne
Ya, ternyata itu; Saya membuat komentar untuk efek itu di pertanyaan utama. Ketika saya mulai mengkodekannya, saya tidak tahu persis bagaimana cara kerjanya. Sejak CircumspectBot ditulis terlebih dahulu, ia seharusnya mendapatkan kredit untuk ide tersebut.
Ralph Marshall
Saya pikir Anda melewatkan akhir kelas Anda.
Winston Ewert
Terima kasih. Saya kehilangan penjepit terakhir; tidak ada kode lain setelah apa yang ada di sana.
Ralph Marshall
3

Optimis

Optimis sangat optimis dan mengasumsikan bahwa setengah dari pemilih yang tersisa akan memilih kandidat yang memberikan hadiah terbaik.

import java.lang.Integer;
import java.lang.String;
import java.util.Arrays;
import java.util.Comparator;

public class Optimist implements Player
{
    public Optimist(int _) { }
    public String getName() { return "Optimist"; }
    public int getVote(int[] curVotes, int rem, final int[] payoffs, int[] _)
    {
        Integer[] opt = new Integer[] { 0, 1, 2 };
        Arrays.sort(opt, new Comparator<Integer>() { public int compare(Integer i1, Integer i2) { return payoffs[i1] > payoffs[i2] ? -1 : payoffs[i1] == payoffs[i2] ? 0 : 1; } });
        int a = curVotes[opt[0]], b = curVotes[opt[1]], c = curVotes[opt[2]];
        double rest = (double)rem / 4;
        if (b <= a + rest && c <= a + rest)
            return opt[0];
        else if (c <= b)
            return opt[1];
        else
            return opt[0];
    }
    public void receiveResults(int[] _, double __) { }
}
LegionMammal978
sumber
3

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.

import java.util.ArrayList;

public class ABotDoNotForget implements Player
{
    private int nbElec;
    private int countElec=0;
    private int[] currPayoffs=new int[3];
    private int[] lmh=new int[3];
    private int[] wins=new int[3];

    public ABotDoNotForget(int nbElec)
    {
        this.nbElec=nbElec;
    }

    public String getName() {return "ABotDoNotForget";}

    public int getVote(int[] voteCounts, 
                        int votersRemaining, 
                        int[] payoffs,
                        int[] totalPayoffs) 
    {
        countElec++;
        System.arraycopy(totalPayoffs, 0, currPayoffs, 0, totalPayoffs.length);

        if(countElec<=nbElec/20&&countElec<=20)
        {
            int best=0;
            for(int i=1;i<payoffs.length;i++)
                if(payoffs[i]>=payoffs[best])
                    best=i;
            return best;
        }

        for(int i =1;i<totalPayoffs.length;i++)
        {
            if(totalPayoffs[i]<totalPayoffs[i-1])
            {
                int tmp= totalPayoffs[i];
                totalPayoffs[i]=totalPayoffs[i-1];
                totalPayoffs[i-1]=tmp;
                if(i==2&&totalPayoffs[i-1]<totalPayoffs[i-2]){
                    tmp= totalPayoffs[i-1];
                    totalPayoffs[i-1]=totalPayoffs[i-2];
                    totalPayoffs[i-2]=tmp;
                }
            }
        }
        lmhDist(currPayoffs,totalPayoffs);
        int best=0;
        for(int i=1;i<wins.length;i++)
            if(wins[i]>=wins[best]){
                best=i;
            }
        int ownH=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownH])
                ownH=i;
        int ownM=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownM]&&i!=ownH)
                ownM=i;

        int persBest=(voteCounts[ownH]-voteCounts[ownM]+(votersRemaining/3)>=0
                &&voteCounts[ownH]-voteCounts[best]<(votersRemaining/3))?ownH:ownM;

        return persBest;

    }

    public void receiveResults(int[] voteCounts, double result) 
    {
        int best=0,bestV=voteCounts[best];
        for(int i=1;i<voteCounts.length;i++)
            if(voteCounts[i]>=bestV){
                best=i;
                bestV=voteCounts[i];
            }
        wins[lmh[best]]++;

    }

    private void lmhDist(int[] a,int[] s)
    {
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(a[0]);al.add(a[1]);al.add(a[2]);
        lmh[0]=al.indexOf(s[0]);
        lmh[1]=al.indexOf(s[1]);
        lmh[2]=al.indexOf(s[2]);

    }
}

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.

Katenkyo
sumber
3

Priam

Priam membenci rekursi. Dia memperkirakan probabilitas setiap bot yang tersisa berdasarkan total hadiah dan kemudian menghitung cara terbaik untuk memaksimalkan hadiahnya.

public class Priam implements Player {
    private static double[] smallFactorials = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800.,87178291200.,1307674368000.,20922789888000.,355687428096000.,6402373705728000.,121645100408832000.,2432902008176640000.};
    @Override
    public String getName() {
        return "Priam";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        int totalPayoff = totalPayoffs[0] + totalPayoffs[1] + totalPayoffs[2];
        double p0 = ((double)totalPayoffs[0])/totalPayoff;
        double p1= ((double) totalPayoffs[1])/totalPayoff;
        double p2 = ((double)totalPayoffs[2])/totalPayoff;
        double[] expectedPayoffs = {0,0,0};
        for(int myChoice=0;myChoice<3;myChoice++)
        {
            for(int x0 = 0; x0 <= votersRemaining; x0++)
            {
                for(int x1 = 0; x1 <= (votersRemaining-x0); x1++)
                {
                    int x2 = votersRemaining - (x1 + x0);
                    double probability =
                            Math.pow(p0, x0)
                            * Math.pow(p1, x1)
                            * Math.pow(p2, x2)
                            * Choose(votersRemaining, x0)
                            * Choose(votersRemaining-x0, x1);
                    int votes0 = voteCounts[0];
                    int votes1 = voteCounts[1];
                    int votes2 = voteCounts[2];
                    if(myChoice == 0)
                    {
                        votes0++;
                    }
                    else if(myChoice==1)
                    {
                        votes1++;
                    }
                    else
                    {
                        votes2++;
                    }

                    votes0+=x0;
                    votes1+=x1;
                    votes2+=x2;
                    if(votes0>votes1 && votes0>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[0];
                    }
                    else if(votes1>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[1];
                    }
                    else
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[2];
                    }
                }
            }
        }
        if(expectedPayoffs[0]>expectedPayoffs[1] && expectedPayoffs[0]>expectedPayoffs[2])
        {
            return 0;
        }
        else if(expectedPayoffs[1]>expectedPayoffs[2])
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }

    private long Choose(int source, int team) {
        return Factorial(source)/(Factorial(team)*Factorial(source-team));
    }

    private long Factorial(int n) {
        if(n<=20)
        {
            return (long)smallFactorials[n];
        }
        double d=(double)n;
        double part1 = Math.sqrt(2*Math.PI*d);
        double part2 = Math.pow(d/Math.E, d);
        return (long)Math.ceil(part1 * part2);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {


    }
    public Priam(int i)
    {

    }
}

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.

euanjt
sumber
"Saya pikir ini adalah bot pertama yang menggunakan parameter hasil total untuk keuntungannya sendiri :)" Lihat bot saya (ABotDoNotForget), dia sudah menggunakannya, maaf: D
Katenkyo
Sangat mirip dengan bot terbaru saya, ExpectantBot, kecuali Anda menggunakan totalPembayaran untuk memprediksi probabilitas dan saya menganggap setiap suara sama-sama memungkinkan. Saya ingin melihat strategi mana yang paling berhasil.
Winston Ewert
@ WinstonEwert Saya pikir Anda melakukannya, Anda telah memenangkan tiga tes terakhir yang saya lakukan.
euanjt
Saya baru saja melihat kesamaannya - saya mencoba membuat versi Odysseus yang tidak membutuhkan waktu 10 jam untuk menjalankan 100 pemilihan, jadi saya gunakan untuk loop
euanjt
Sejujurnya, saya terinspirasi untuk mengambil pendekatan saya oleh Odysseus.
Winston Ewert
2

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.

import java.lang.Math;
import java.util.*;
/**
 * Created by Admin on 5/27/2015.
 */
public class NoClueBot implements Player {

    public NoClueBot(int e) { }

    public String getName() {
        return "NoClueBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        double x = 0;
        int y = 0;
        for (int i=0; i<3; i++) {
            double t = (double) voteCounts[i] * ((double) payoffs[i]/(double) totalPayoffs[i]);
            if (x<t) {
                x = t;
                y = i; 
            }
        }
        return y;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}


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).

import java.lang.Math;
/**
 * Created by Admin on 5/27/2015.
 */
public class SometimesSecondBestBot implements Player {
    public SometimesSecondBestBot(int e) { }

    public String getName() {
        return "SometimesSecondBestBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        int m = 0;
        int n = 0;
        for(int i = 1; i< 3; i++) {
            if(payoffs[i] > payoffs[m]) { n = m; m = i; }
        }
        return (voteCounts[n]>voteCounts[m]&&totalPayoffs[n]>totalPayoffs[m])||(voteCounts[m]+votersRemaining<voteCounts[n])||voteCounts[m]+votersRemaining<voteCounts[Math.min(3-n-m, 2)] ? n : m;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}
Kade
sumber
1
Sepertinya Anda menghitung angka yang terbesar dari tiga bobot dan daripada mengambil nilai itu mod 3 untuk memilih kandidat terbaik. Apakah itu benar dan jika demikian bukankah itu pada dasarnya angka acak? Saya mengerti bahwa Anda menyebut ini "matematika Barbie sulit", jadi saya tidak yakin saya memiliki konsep.
Ralph Marshall
@RalphMarshall Ya, ini pada dasarnya acak. Namun, saya sama sekali tidak bermaksud melakukan itu, tidak memperhatikan, haha. Perbaiki sekarang.
Kade
@ PhiNotPhi Saya pikir saya sudah memperbaikinya keluar dari jangkauan sekarang. Dan ya, saya tidak terkejut.
Kade
Ya Tuhan ini buruk .. dalam pekerjaan pertahananku sangat menguras mental hari ini.
Kade
2

Ekstremis

Selalu pilih kandidat dengan hadiah terendah

public class ExtremistBot implements Player
{
    public ExtremistBot(int e){}

    public void receiveResults(int[] voteCounts, double result){}

    public String getName(){
        return "ExtremistBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int min = 0;
        for(int i = 1; i<payoffs.length; i++){
            if(payoffs[i] <payoffs[min]){
                min = i;
            }
        }
        return min;
    }
}
pelaku diet
sumber
2

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.

public class SmashAttemptByEquality implements Player {
    static private int elections;

    public SmashAttemptByEquality(int e) { 
        this.elections = e;
    }

    public String getName() {
        return "SmashAttemptByEquality (on " + String.valueOf(this.elections) + " elections)";
    }

    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {

        //if there are no votes or it is a tie
        if(voteCounts.length == 0 || (voteCounts[0] == voteCounts[1] && voteCounts[1] == voteCounts[2]))
        {
            //let the system handle the (distributed?) randomness
            return 3;
        }

        //we want to win, so, lets not mess when there are no voters left
        if( votersRemaining > 0 )
        {
            //lets bring some equality!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 2;
                }
                else
                {
                    return 0;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
            else
            {
                return 0;
            }
        }
        else
        {
            //just play for the winner!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 0;
                }
                else
                {
                    return 2;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return 0;
            }
        }
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Perhatikan bahwa ini belum teruji !

Ismael Miguel
sumber
2

Bot Dasar

Basic Bot hanya memberikan suara untuk kandidat yang tidak dihilangkan dan memiliki hasil maksimum terbesar dari kandidat tersebut.

public class BasicBot implements Player {
    public BasicBot(int e) { }
    public String getName()
    {
        return "BasicBot";
    }
    public static int getMax(int[] inputArray){ 
    int maxValue = inputArray[0]; 
    for(int i=1;i < inputArray.length;i++){ 
      if(inputArray[i] > maxValue){ 
         maxValue = inputArray[i]; 
      } 
    } 
    return maxValue; 
   }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        // Check for Eliminated Candidates
        int eliminated0 = 0;
        int eliminated1 = 0;
        int eliminated2 = 0;
        if( ((voteCounts[0] + votersRemaining) < voteCounts[1]) || ((voteCounts[0] + votersRemaining) < voteCounts[2]))
        {
            eliminated0 = 1;
        }
        if( ((voteCounts[1] + votersRemaining) < voteCounts[0]) || ((voteCounts[1] + votersRemaining) < voteCounts[2]))
        {
            eliminated1 = 1;
        }
        if( ((voteCounts[2] + votersRemaining) < voteCounts[0]) || ((voteCounts[2] + votersRemaining) < voteCounts[1]))
        {
            eliminated2 = 1;
        }
        // Choose the Candidates that is not elimated with the largest payoff
        if ((payoffs[0] == getMax(payoffs)) && eliminated0 == 0)
            return 0
        else if ((payoffs[1] == getMax(payoffs)) && eliminated1 == 0)
            return 1
        else
            return 2

    }

    public void receiveResults(int[] voteCounts, double result)
    {
    }

}
Roboter
sumber
2

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).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class KellysFavorite implements Player {
    private ArrayList<Double> cache = new ArrayList<Double>();

    public KellysFavorite(int elections) {
        cache.add(0.0);
        double v = 0.0;
        for(int i=1; i<1000; i++) {
            v += Math.log(i);
            cache.add(v);
        }
    }

    @Override
    public String getName() {
        return "Kelly's Favorite";
    }

    private double factln(int n) {
        return cache.get(n);
    }

    private  double binll(int x, int n, double p)
    {
        double ll = 0.0;
        ll += ((double)x)*Math.log(p);
        ll += ((double)(n - x))*Math.log(1.0 - p);
        ll += factln(n) - factln(x) - factln(n-x);
        return ll;
    }

    public  double logAdd(double logX, double logY) {
        // 1. make X the max
        if (logY > logX) {
            double temp = logX;
            logX = logY;
            logY = temp;
        }
        // 2. now X is bigger
        if (logX == Double.NEGATIVE_INFINITY) {
            return logX;
        }
        // 3. how far "down" (think decibels) is logY from logX?
        //    if it's really small (20 orders of magnitude smaller), then ignore
        double negDiff = logY - logX;
        if (negDiff < -20) {
            return logX;
        }
        // 4. otherwise use some nice algebra to stay in the log domain
        //    (except for negDiff)
        return logX + java.lang.Math.log(1.0 + java.lang.Math.exp(negDiff));
    }

    @Override
    public int getVote(int[] voteCounts,
                       int votersRemaining,
                       int[] payoffs,
                       int[] totalPayoffs) {
        int totalviable = 0;
        boolean[] viable = { false, false, false };
        int topVote = Arrays.stream(voteCounts).max().getAsInt();
        for (int index = 0; index < 3; index++) {
            if (voteCounts[index] + votersRemaining + 1 >= topVote) {
                viable[index] = true;
                totalviable += 1;
            }
        }

        // if only one candidate remains viable, vote for them
        if(totalviable == 1) {
            for(int index = 0; index < 3; index++)
                if(viable[index])
                    return index;
        } else {
            double votelikelihoods[] = { 0.0, 0.0, 0.0 };
            double totalweight = 0.0;
            for(int index=0; index<3; index++) {
                if(!viable[index])
                    votelikelihoods[index] -= 10.0;
                else if(voteCounts[index] < topVote)
                    votelikelihoods[index] -= 0.1;

                totalweight += Math.exp(votelikelihoods[index]);
            }

            double probs[] = new double[3];
            for(int index=0; index<3; index++) {
                probs[index] = Math.exp(votelikelihoods[index]) / totalweight;
            }

            double[] utilities = {0,0,0};
            for(int mychoice=0; mychoice<3; mychoice++) {
                boolean seen[] = { false, false, false };
                double likelihoods[] = { Double.NEGATIVE_INFINITY,
                                         Double.NEGATIVE_INFINITY,
                                         Double.NEGATIVE_INFINITY };
                int[] localVoteCounts = { voteCounts[0] + (mychoice==0?1:0),
                                          voteCounts[1] + (mychoice==1?1:0),
                                          voteCounts[2] + (mychoice==2?1:0) };
                for(int iVotes=0; iVotes<=votersRemaining; iVotes++)
                    for(int jVotes=0; jVotes<=(votersRemaining-iVotes); jVotes++) {
                        int kVotes = votersRemaining - iVotes - jVotes;

                        int a = localVoteCounts[0] + iVotes;
                        int b = localVoteCounts[1] + jVotes;
                        int c = localVoteCounts[2] + kVotes;
                        int wincount = Math.max(a, Math.max(b, c));
                        int winners = 0;
                        if(a>=wincount) { winners += 1; }
                        if(b>=wincount) { winners += 1; }
                        if(c>=wincount) { winners += 1; }

                        double likelihood =
                            binll(iVotes, votersRemaining, probs[0])
                            + binll(jVotes, votersRemaining-iVotes, probs[1] / (probs[1] + probs[2]));

                        likelihood += Math.log(1.0/winners);

                        if(a>=wincount) {
                            if(seen[0])
                                likelihoods[0] = logAdd(likelihoods[0],
                                                        likelihood);
                            else
                                likelihoods[0] = likelihood;
                            seen[0] = true;
                        }
                        if(b>=wincount) {
                            if(seen[1])
                                likelihoods[1] = logAdd(likelihoods[1],
                                                        likelihood);
                            else
                                likelihoods[1] = likelihood;
                            seen[1] = true;
                        }
                        if(c>=wincount) {
                            if(seen[2])
                                likelihoods[2] = logAdd(likelihoods[2],
                                                        likelihood);
                            else
                                likelihoods[2] = likelihood;
                            seen[2] = true;
                        }

                    }

                for(int index=0; index<3; index++)
                    utilities[mychoice] += Math.exp(likelihoods[index]) * Math.log((double)payoffs[index]);
            }

            double maxutility = Math.max(utilities[0], Math.max(utilities[1], utilities[2]));
            int choice = 0;
            for(int index=0; index<3; index++)
                if(utilities[index]>=maxutility)
                    choice = index;
            return choice;
        }

        throw new InternalError();
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }

}

Juga tersedia di https://gist.github.com/jkominek/dae0b3158dcd253e09e5 jika itu lebih sederhana.

Jay Kominek
sumber
2

CommunismBot

CommunismBot berpikir kita semua harus akur dan memilih kandidat yang terbaik untuk semua orang.

public class CommunismBot implements Player
{
    Random rnd;
    String name;
    public CommunismBot(int e) {
        rnd = new Random(); 
        name = "CommunismBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(totalPayoffs[i] > totalPayoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Hatebot

Hatebot selalu memilih kandidat terbaik. Kecuali kalau mereka adalah pesta kotor 1. Orang-orang itu mengerikan.

import java.util.Random;


public class HateBot implements Player
{
    Random rnd;
    String name;
    public HateBot(int e) {
        rnd = new Random(); 
        name = "HateBot" + rnd.nextInt(1000); }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        if(payoffs[0]>payoffs[2])
            return 0;
        else
            return 2;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

StrategicBot

Pemungutan suara StrategicBot untuk kandidat terbaik asalkan mereka berada dalam satu standar deviasi dari kandidat terbaik berikutnya, mengingat jumlah pemilih yang tersisa.

import java.util.Random;

public class StrategicBot implements Player
{
    Random rnd;
    String name;
    public StrategicBot(int e) {
        rnd = new Random(); 
        name = "StrategicBot" + rnd.nextInt(1000);

    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        double margin = 9.0*votersRemaining/9;
        int maxloc = 0;
        boolean noLead=false;
        for(int i = 1; i< 3; i++)
        {
            for(int j = 1; j < 3; j++)
            {
                if(payoffs[j] + margin > payoffs[i])
                    noLead=true;
            }
            if(payoffs[i] > payoffs[maxloc] && noLead)
            {
                maxloc = i;
            }
            noLead=false;
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}
Saidoro
sumber
2

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.

import java.util.Arrays;

public class ExpectorBot implements Player
{
    class Votee
    {
        int index;
        int payoff;
        float avgPayoff;
        float expectedVotes;
    }

    public ExpectorBot( final int e )
    {

    }

    @Override
    public String getName()
    {
        return "ExpectorBot";
    }

    @Override
    public int getVote( final int[] voteCounts, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final int otherVoters = Arrays.stream( voteCounts ).sum() + votersRemaining;
        final Votee[] v = createVotees( voteCounts, otherVoters, votersRemaining, payoffs, totalPayoffs );

        final Votee best = v[ 0 ]; // Most Payoff
        final Votee second = v[ 1 ];
        final Votee worst = v[ 2 ];

        int voteFor = best.index;

        if( ( second.expectedVotes >= best.expectedVotes + 1 ) // Second has more votes than Best even after I vote
                && ( second.payoff >= second.avgPayoff ) // Second payoff better than average for the others
                && ( worst.expectedVotes >= best.expectedVotes + 0.5f ) ) // Worst has a chance to win
        {
            voteFor = second.index;
        }

        return voteFor;
    }

    private Votee[] createVotees( final int[] voteCounts, final int otherVoters, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final Votee[] v = new Votee[ 3 ];

        for( int i = 0; i < 3; ++i )
        {
            v[ i ] = new Votee();
            v[ i ].index = i;
            v[ i ].payoff = payoffs[ i ];

            // This is the average payoff for other Players from this Votee
            v[ i ].avgPayoff = (float)( totalPayoffs[ i ] - payoffs[ i ] ) / otherVoters;

            // The expected number of Votes he will get if everyone votes for biggest payoff
            v[ i ].expectedVotes = voteCounts[ i ] + ( votersRemaining * v[ i ].avgPayoff / 100.0f );
        }

        Arrays.sort( v, ( o1, o2 ) -> o2.payoff - o1.payoff );

        return v;
    }

    @Override
    public void receiveResults( final int[] voteCounts, final double result )
    {

    }
}
Falco
sumber
1

LockBot

Hanya seorang filsuf yang kesepian, mencari "e" -nya ...

//He thinks he's the father of democracy, but something's missing....
public class LockBot implements Player {

public LockBot(int i) {
    //One election, 10000000, what's the difference?
}

@Override
public String getName() {
    return "LockBot";
}

@Override
public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
        int[] totalPayoffs) {

    double totalPlayers = voteCounts.length + votersRemaining;
    double totalPayoff = totalPlayers * 100;

    //adjust total payoffs to ignore my own
    for( int i = 0; i < totalPayoffs.length; i++){
        totalPayoffs[i] -= payoffs[i];
    }

    //Votes are probably proportional to payoffs
    //So lets just find the highest weight
    double[] expectedOutcome = new double[3];
    for(int i = 0; i< expectedOutcome.length; i++){
        expectedOutcome[i] = (totalPayoffs[i] / totalPayoff) * payoffs[i];
    }

    //Find the highest
    int choice = 0;
    if(expectedOutcome[1] > expectedOutcome[choice]){
        choice = 1;
    }
    if(expectedOutcome[2] > expectedOutcome[choice]){
        choice = 2;
    }




    return choice;
}

@Override
public void receiveResults(int[] voteCounts, double result) {
    // TODO Auto-generated method stub

}

}
Kain
sumber
0

Menang kalah

Jika Anda menang, saya kalah! Sesederhana itu. Jadi bot ini memilih salah satu yang dia suka dan tidak disukai semua orang.

public class WinLose implements Player
{
    public WinLose(int e) { }

    public String getName()
    {
        return "WinLose";
    }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int max = 0;
        for(int i = 1; i< 3; i++)
        {
            if(10*payoffs[i]-totalPayoffs[i] > 10*payoffs[max]-totalPayoffs[max])
            {
                max = i;
            }
        }
        return max;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}
MegaTom
sumber