Ini Natal pada bulan Juli, jadi cara apa yang lebih baik untuk merayakannya selain pertukaran hadiah gajah putih virtual!

Untuk tantangan King of the Hill ini, Anda harus membuat bot yang bermain dalam simulasi pertukaran Gajah Putih , berusaha mendapatkan hadiah dengan nilai tertinggi yang bisa didapat.

Aturan Game

• Gim ini akan dimainkan dalam banyak putaran, masing-masing terdiri dari jumlah putaran yang bervariasi.
• Putaran Pengaturan : Akan ada banyak hadiah karena ada pemain dalam permainan, masing-masing dinilai secara acak dalam kisaran [0 ... 1), dengan nilai ini tidak diketahui hingga hadiah "dibuka". Pemain akan dimasukkan dalam urutan acak dalam antrian. Pemain pertama akan muncul dari depan antrian.
• Ketika giliran pemain, mereka dapat membuka hadiah atau mencuri hadiah pemain lain, melewati pemain yang hadiahnya dicuri.
  • Setiap hadiah dapat dicuri hingga 3 kali.
  • Anda tidak dapat mencuri dari pemain yang baru saja mencuri dari Anda.
  • Setiap pemain hanya dapat memiliki satu hadiah pada suatu waktu.
• Setelah hadiah dibuka, bermain maju ke pemain berikutnya muncul dari depan antrian. Ini akan menjadi pemain berikutnya secara berurutan yang belum mendapat giliran.
• Round End : Ketika semua hadiah telah dibuka, babak berakhir, dan nilai dari hadiah yang dipegang oleh masing-masing pemain ditambahkan ke skor pemain itu. Babak baru dimulai, dengan masing-masing pemain sekarang tidak memegang hadiah dan urutan pemain diacak.
• Game End : Permainan akan berakhir ketika setidaknya satu pemain memiliki skor 100 500 poin, dengan kemenangan diberikan kepada pemain dengan nilai total hadiah tertinggi.

Coding

Semua kiriman harus kompatibel dengan Python 3.7. Anda harus menulis kelas yang mewarisi langsung dari WhiteElephantBot. Contohnya:

class FooBot(WhiteElephantBot):
    # Your implementation here

Anda dapat memberikan __init__metode (yang mengambil satu argumen, name) di kelas bot Anda, yang harus dihubungi super().__init__(name). Kelas Anda harus memiliki take_turnmetode yang mengharapkan argumen berikut dalam urutan ini:

• players: Daftar nama pemain, secara berurutan, dari semua pemain yang belum memiliki hadiah.
• presents: Kamus yang memetakan nama-nama pemain ke 2-tupel yang berisi nilai sekarang yang dipegang oleh pemain itu dan berapa kali ini telah dicuri. Ini hanya akan mencakup pemain lain yang saat ini memegang hadiah.
• just_stole: Jika aksi terakhir yang diambil adalah mencuri, ini akan menjadi nama pemain yang baru saja mencuri. Jika tidak, itu akan terjadi None.

Setiap argumen akan berubah atau objek baru sehingga mengubah salah satu dari mereka tidak akan berpengaruh pada permainan. Anda dapat menyimpan salinan argumen apa pun jika diinginkan.

Nilai contoh untuk presents:

{
    'Alice':   (0.35, 0),
    'Bob':     (0.81, 2),
    'Charlie': (0.57, 1)
}

take_turnMetode Anda harus mengembalikan nama pemain yang ingin Anda curi atau Noneuntuk membuka hadiah. Jika itu menimbulkan pengecualian, mengembalikan sesuatu selain dari stratau None, atau nama pemain yang tidak dapat Anda curi, Anda akan membuka hadiah secara default.

Konstruktor Anda akan dipanggil pada awal setiap putaran, sehingga Anda tidak bisa mengingat status dari putaran ke putaran.

Dengan mewarisi dari WhiteElephantBot, Anda akan memiliki akses ke steal_targetsmetode yang akan mengambil dict hadiah dan just_stoledan mengembalikan daftar nama pemain yang dapat Anda curi.

Modul apa pun yang dibutuhkan skrip Anda harus diimpor di bagian atas entri Anda.

Driver Penguji

Driver tes dapat ditemukan di sini . Anda tidak perlu memasukkan from white_elephant import WhiteElephantBotjawaban yang Anda kirim, namun modul lokal perlu melakukannya.

Pesaing Dasar

• Acak : Memilih secara acak apakah akan membuka hadiah baru atau mencuri, dengan target mencuri dipilih secara acak secara acak.
• Serakah : mencuri hadiah paling berharga yang bisa dicuri. Jika tidak ada hadiah yang bisa dicuri, buka hadiah.
• Bagus : Selalu membuka hadiah baru. Tidak pernah mencuri.

Aturan tambahan

• Adalah tanggung jawab Anda untuk menangkap semua pengecualian. Jika kelas Anda gagal menangkap pengecualian, itu akan didiskualifikasi. Selain itu, tolong jangan menangkap KeyboardInterrupts.
• Jangan menggunakan file atau metode lain untuk memotong ketidakmampuan untuk menyimpan keadaan di antara game. Anda mungkin tidak, misalnya, menyimpan status jaringan saraf ke file yang sedang berjalan.
• Bot Anda harus mandiri dalam kode kelas dan konstanta terkait.
• Anda hanya dapat menggunakan impor pustaka standar.
• Tidak ada persyaratan kinerja yang ketat. Bersikaplah masuk akal dan bijaksana. Jika kinerja menjadi masalah, saya berhak untuk menambah batas waktu.
• Satu entri per orang. Jika Anda mengirim lebih dari satu entri, bot Anda mungkin tidak bekerja bersama. Saya akan memperbolehkan beberapa entri per orang untuk saat ini, meskipun saya dapat reban nanti jika itu menjadi masalah.
• Ini adalah kompetisi terbuka tanpa tanggal akhir yang berbeda. Ini akan dijalankan kembali kapan saja saya bisa ketika ada perubahan signifikan.

EDIT1: Skor kemenangan berubah dari 100 menjadi 500 sehingga peringkat lebih konsisten. Driver penguji memiliki perbaikan bug baru dan juga mencerminkan perubahan skor menang.

EDIT2: Klarifikasi catatan tentang impor yang diperlukan.

Papan peringkat (per 8 Agustus 2018)

1. SampleBot (500.093)
2. LastMinuteBot (486.163)
3. RobinHood (463.160)
4. OddTodd (448.825)
5. GreedyBot (438.520)
6. SecondPlaceBot (430.598)
7. ThresholdBot (390.480)
8. Penjudi (313.362)
9. NiceBot (275.536)
10. RandomBot (256.172)
11. GoodSamaritan (136.298)

LastMinuteBot

(Dengan terima kasih banyak kepada @Mnemonic untuk kerangka kode, karena saya hampir tidak tahu Python.)

class LastMinuteBot(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):
        targets = self.steal_targets(presents, just_stole)
        if len(targets) <= 1:
            return None

        target = None

        # If most of the presents are already distributed, try to steal an 
        #  un-restealable gift of high value
        if len(presents) > (len(players) + len(presents)) * 0.75:
            at_threshold = [t for t in targets if presents[t][1]==2 and presents[t][0]>=0.8]
            if at_threshold:
                target = max(at_threshold, key=lambda x: presents[x][0])

        # Otherwise, take the best available
        if not target:
            target = max(targets, key=lambda x: presents[x][0])

        return target if presents[target][0] > 0.5 else None

Manfaatkan fakta bahwa hadiah tidak dapat dicuri lebih dari tiga kali, lakukan pencurian ketiga sendiri jika Anda menemukan hadiah bernilai tinggi dan sebagian besar hadiah telah dibuka.

Todd ganjil

class OddTodd(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):

        targets = self.steal_targets(presents, just_stole)

        # if none to steal, pick present
        if len(targets) <= 1:
            return None

        # steals the best gift that he can, as long as he's the 1st/3rd steal
        targets = [t for t in targets if presents[t][1] % 2 == 0]
        if targets:
            return max(targets, key=lambda x:presents[x][0])

        else:
            return None

Mencuri hadiah terbaik yang dia bisa, tetapi tidak ingin menjadi orang kedua yang mencuri hadiah, karena jika dicuri, dia tidak bisa mendapatkannya kembali.

SecondPlaceBot

class SecondPlaceBot(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):
        targets = self.steal_targets(presents, just_stole)
        if len(targets) <= 1:
            return None

        # If most of the presents are already distributed, take the second best.
        if len(presents) > (len(players) + len(presents)) * 0.8:
            target = sorted(targets, key=lambda x: presents[x][0])[-2]
        # Otherwise, take the best and hope someone steals it later.
        else:
            target = max(targets, key=lambda x: presents[x][0])

        return target if presents[target][0] > 0.5 else None

Semua orang akan berjuang untuk mendapatkan hadiah yang paling berharga. Hadiah terbaik berikutnya hampir sama baiknya, tetapi kecil kemungkinannya untuk dicuri.

ThresholdBot

import random

class ThresholdBot(WhiteElephantBot):
    def __init__(self, name):
        self.name = name
        # Choose a minimum value to be happy.
        self.goal = 1 - random.random() ** 2

    def take_turn(self, players, presents, just_stole):
        # Find who has a gift that's sufficiently valuable.
        targets = self.steal_targets(presents, just_stole)
        targets = [x for x in targets if presents[x][0] >= self.goal]
        targets = sorted(targets, key=lambda x: presents[x][0])

        if not targets:
            return None

        # Choose a target (biased toward the best gifts).
        weighted = []
        for i, target in enumerate(targets, 1):
            weighted += [target] * i ** 2
        return random.choice(weighted)

Kami tidak benar-benar peduli tentang mendapatkan hadiah terbaik , hanya sesuatu yang cukup bagus . Selama ada sesuatu yang pantas dicuri, kami akan melakukannya.

SampleBot

import random

class SampleBot(WhiteElephantBot):
    def rollout(self, values, counts, just_stole, next_move):
        targets = set()
        move_chosen = False
        for i, (v, n) in enumerate(zip(values, counts)):
            if v and n < 3 and i != just_stole and i != 0:
                targets.add(i)
        for i in range(len(values)):
            if values[i]:
                break
            while True:
                if not targets:
                    break
                if move_chosen:
                    j = max(targets, key=lambda i: values[i])
                    if values[j] < 0.5:
                        break
                else:
                    move_chosen = True
                    if next_move is None:
                        break
                    j = next_move
                values[i] = values[j]
                counts[i] = counts[j] + 1
                values[j] = 0
                counts[j] = 0
                if just_stole is not None and counts[just_stole] < 3:
                    targets.add(just_stole)
                if j in targets:
                    targets.remove(j)
                just_stole = i
                i = j
            values[i] = random.random()
            for player in (just_stole, i):
                if player is not None and values[player] and counts[player] < 3:
                    targets.add(player)
        return values[0]
    def take_turn(self, players, presents, just_stole, n_rollouts=2000):
        names = [self.name] + players + list(presents.keys())
        values = [presents[name][0] if name in presents else None for name in names]
        counts = [presents[name][1] if name in presents else 0 for name in names]
        if just_stole is not None:
            just_stole = names.index(just_stole)
        targets = [None]
        for i, (v, n) in enumerate(zip(values, counts)):
            if v and n < 3 and i != just_stole and i != 0:
                targets.append(i)
        if len(targets) == 1:
            return targets[0]
        scores = [0. for _ in targets]
        n = n_rollouts // len(targets)
        for i, target in enumerate(targets):
            for _ in range(n):
                scores[i] += self.rollout(list(values), list(counts), just_stole, target) / float(n)
        target_index = targets[scores.index(max(scores))]
        if target_index is None:
            return None
        return names[target_index]

Menjalankan 2000 simulasi dengan masing-masing pemain bertindak rakus dan memilih aksi terbaik.

Robin Hood

class RobinHood(WhiteElephantBot):       
    def take_turn(self, players, presents, just_stole):
        #get the possible steal targets
        targets = self.steal_targets(presents, just_stole)
        #who stole his gift?
        targets = [x for x in targets if presents[x][1] > 0]
        #sort by value
        targets = sorted(targets, key=lambda x: presents[x][0])        
        #only steal back if it's worth it        
        targets = [x for x in targets if presents[x][0] > 0.5]

        if len(targets)>0:
           return targets.pop()

Curi dari orang kaya yang tidak mendapat hadiah

GoodSamaritan

class GoodSamaritan(WhiteElephantBot):     
    def take_turn(self, players, presents, just_stole):  
        targets = self.steal_targets(presents, just_stole)

         #if only one player has a gift, don't steal it!
        if len(presents)<=1 or len(targets)==0:
             return None
        else:       
             #Steal the worst present  
             return min(targets, key=lambda x: presents[x][0])

Beri orang yang beruntung kesempatan lain untuk keberuntungan

Penjudi

class Gambler(WhiteElephantBot):
    def take_turn(self, players, presents, just_stole):        
        #get the possible steal targets
        targets = self.steal_targets(presents, just_stole)        

        #last player 
        if len(players)==0:
            #lets gamble! Try and get the highest score
            return None

        #If you are not last, steal the best gift that can be restolen so maybe you can become the last player
        targets = [t for t in targets if presents[t][1]<2 ]
        if targets:
            return max(targets, key=lambda x: presents[x][0])   

The Gambler kecanduan, dia mencoba menjadi pemain terakhir, lalu bertaruh pada hadiah baru untuk mengalahkan semua pemain lainnya.

Top3Bot

class Top3Bot(WhiteElephantBot):
    def __init__(self, name):
        super().__init__(name)
        self.firstturn = True

    def take_turn(self, players, presents, just_stole):
        if self.firstturn:
            num_presents = len(players) + len(presents) + 1
            self.value_limit = (num_presents - 3) / num_presents
            self.firstturn = False

        targets = self.steal_targets(presents, just_stole)

        if players:
            targets += None

        return max(
            targets,
            key=lambda name: self.steal_ranking(name, presents, len(players))
        )


    def steal_ranking(self, name, presents, presents_remaining):
        if name is None:
            return (0, 0)

        present_value = presents[name][0]
        num_steals = presents[name][1]
        if present_value >= self.value_limit:
            if num_steals == 2:
                return (5, present_value)
            elif  num_steals == 0:
                return (4, -presemt_value)
            elif num_steals == 1 and presents_remaining == 0:
                return (3, -present_value)
            else:
                return (-1, present_value)
        else:
            if num_steals < 2:
                return (2, present_value)
            else:
                return (-2, present_value)

Bot ini tidak mencoba untuk mendapatkan hadiah terbaik, tetapi mencoba untuk mendapatkan hadiah yang bernilai> = (n-3) / n, di mana n adalah jumlah hadiah. Dalam sebagian besar kasus, akan ada hadiah yang dihargai sebesar itu, dan Top3Bot akan mencoba untuk mendapatkan salah satu dari ini, tetapi dia tidak benar-benar peduli yang mana yang didapatnya.