Apa tip umum yang Anda miliki untuk membuat bot untuk berpartisipasi dalam tantangan King of the Hill? Strategi apa yang Anda gunakan untuk mulai dari mempertimbangkan tantangan untuk menciptakan bot Anda? Struktur data apa yang menurut Anda paling berguna?

Silakan kirim satu tip per jawaban.

Menemukan Nash Equilibria

Ini adalah konsep yang sangat penting ketika KOTH melibatkan serangkaian keputusan yang relatif sederhana, hanya melibatkan beberapa pemain (biasanya 2), dan bersifat deterministik. Ekuilibrium Nash menggambarkan posisi "kemacetan": jika kedua pemain telah memutuskan dua strategi mereka, maka kedua pemain tersebut secara efektif terkunci di posisi tersebut: salah satu pemain yang mengubah strategi mereka hanya menciptakan kerentanan tambahan.

Contoh permainan di mana kesetimbangan Nash penting adalah:

• Rock-Paper-Scissors (-Lizard-Spock), di mana strategi "tak terkalahkan" adalah permainan acak
• Morra , yang memiliki "spektrum" keseimbangan. Peter Taylor menulis contoh yang baik dalam jawabannya di sini .
• Dilema Tahanan, permainan kooperatif yang terkenal karena memiliki "semua orang kehilangan" kemacetan

Cara menemukan keseimbangan

Menemukan keseimbangan sebenarnya sebenarnya cukup sederhana untuk sebagian besar permainan sederhana, dan seringkali cukup intuitif. Sebuah ton detail tentang berbagai metode dapat ditemukan di internet. Konsep dasar, yang biasanya berlaku, adalah membuat daftar strategi yang memungkinkan yang dapat digunakan oleh dua pemain (opsi yang disediakan oleh permainan). Jika satu strategi "didominasi" oleh yang lain, maka strategi itu dapat dihapus dari daftar, dan prosesnya diulang. Dengan "dominasi," maksud saya bahwa jika strategi A selalu memberikan hasil yang sama atau lebih baik daripada strategi B, terhadap semua strategi lawan yang tersisa, maka strategi B dapat dihapus dari daftar.

Contoh: Rock-Paper-Gunting

RPS memiliki sesuatu yang disebut keseimbangan "campuran", yang berarti bahwa suatu distribusi terlibat. Alih-alih memainkan gerakan yang sama berulang kali (yang akan menyebabkan kekalahan cepat), keseimbangannya adalah memainkan 1/3 rock, 1/3 kertas, dan 1/3 gunting dalam distribusi acak. Jika saya bermain secara acak, tidak ada yang bisa dilakukan lawan saya untuk mendapatkan keunggulan pada saya, titik. Jika lawan saya memilih untuk tidak bermain secara acak, maka itu hanya menciptakan kerentanan di pihaknya.

Game dengan kesetimbangan campuran mungkin yang paling umum di PPCG, karena mereka dapat mengambil banyak bentuk ( satu - satunya permainan menarik yang bisa saya pikirkan dengan keseimbangan murni adalah dilema tahanan). Saya harus mencatat bahwa keseimbangan campuran tidak harus acak secara acak , hanya sesuatu selain memainkan gerakan yang sama setiap waktu.

Menggunakan informasi ini

Ekuilibrium Nash dari sebuah permainan sering kali mewakili "garis dasar" dari mana Anda harus mencoba beroperasi. Dalam RPS, bermain secara acak menjamin tempat finishing di sekitar bagian tengah paket. Untuk pindah ke atas, Anda harus mulai mengidentifikasi kelemahan pemain lain.

Untuk melakukan ini, Anda harus tetap pada keseimbangan ketika tidak yakin dengan kelemahan lawan. Begitu kelemahan-kelemahan itu telah diidentifikasi (Anda telah mendeteksi bahwa lawan Anda tidak berada dalam keseimbangan), maka Anda perlu dengan lembut bergeser keluar dari keseimbangan untuk mengambil keuntungan dari lawan Anda. Tindakan ini, pada gilirannya, menciptakan kelemahan pada Anda sendiri. Anda kemudian harus mendeteksi kapan lawan Anda mengubah strateginya, sehingga Anda dapat menghentikan serangan dan melanjutkan permainan acak.

Mendeteksi variasi dari keseimbangan

Ini cukup sulit, dan saya bukan ahli. Variasi dapat datang dalam berbagai bentuk:

• Mendukung beberapa opsi di atas / di bawah yang lain tanpa alasan, seperti pemain RPS yang memainkan rock dua kali lebih sering daripada gunting, atau yang menghindari bermain kertas. Beberapa statistik yang relatif sederhana dapat mendeteksi ini.
• Mendasarkan pergerakan saat ini dari gerakan masa lalu, dalam beberapa pola yang dapat diprediksi. Ini termasuk salinan-kucing, "mengalahkan apa yang mengalahkan bot terakhir Anda", atau bot "bersepeda". Ini membutuhkan logika tambahan untuk dideteksi, karena keseluruhan distribusi gerakan dapat didistribusikan secara merata, meskipun gerakan tersebut tidak acak. Anda harus mencoba mengambil catatan langkah dan menemukan korelasi seperti "langkah yang saya buat 2 putaran lalu dan langkah yang dibuat lawan saya sekarang" dan "langkah yang dibuatnya 1 lalu, dan langkah yang dia buat sekarang", dll.
• Bot yang pendistribusian perpindahannya didasarkan pada milikmu. Kerentanan dalam bot ini sering tidak dibuat (dalam jumlah yang dapat diukur) sampai setelah Anda sendiri bervariasi dari distribusi acak. Secara umum, bot Anda sendiri termasuk dalam kategori ini.

Lebih spesifik tentang persyaratan untuk menjalankan bot Anda

Bot dapat ditulis dalam berbagai bahasa (dan versi dari bahasa-bahasa itu), sehingga membantu semua orang keluar saat Anda:

1. Uji di lingkungan yang ditentukan OP (atau sedekat mungkin).
2. Uji di berbagai lingkungan lain jika memungkinkan (untuk membantu orang lain yang ingin menjalankannya).
3. Lebih spesifik tentang bahasa dan versi yang Anda gunakan, dan jelaskan cara menjalankan bot Anda.

Sebagai bonus: jika Anda menggunakan bahasa yang kurang dikenal, buat tautan ke tempat orang dapat mengunduh biner / sumber untuk menjalankannya.

Jika berbasis tim, bekerja sama dengan tim Anda

Meskipun Anda biasanya dapat menulis bot yang berfungsi solo untuk menyelesaikan tugas untuk membantu tim Anda, ada keuntungan yang jauh lebih besar ketika Anda mengoordinasikan masuk dan keluar dari permainan. Contoh utama dari hal ini dapat dilihat di Merah atau Biru - Pixel Team Battlebots .

Selama pengembangan, tim dapat mengobrol dan mendiskusikan bagaimana mengoordinasikan bot mereka agar berfungsi lebih baik daripada sendirian. Sementara secara teknis bot yang sama, SphiNotPi3000 ditulis untuk bekerja bersama-sama dengan yang lain dari dirinya sendiri, dan mampu bergerak dengan cara yang memperhitungkan kelemahan yang akan dihadapi jika itu sendiri. Hasil akhirnya adalah bahwa mereka mampu hampir sepenuhnya mendominasi medan perang, bahkan ketika itu hanya mereka berdua melawan seluruh tim lainnya .

Jadi di luar permainan, rencanakan dan koordinasikan dengan rekan satu tim Anda tentang strategi apa yang harus dicakup. Mungkin seseorang memiliki bot yang memindai peta secara diagonal? Minta pemindaian Anda secara horizontal (hanya sebuah contoh). Di dalam permainan, jika tantangan memungkinkan untuk komunikasi tim, manfaatkan itu. Dalam permainan battlebots misalnya, Anda dapat mengirim pesan ke rekan tim Anda tentang posisi bot di luar bidang penglihatan mereka, dan kemudian mendorong mereka untuk menulis bot mereka dengan cara yang kompatibel untuk memanfaatkan sinyal-sinyal itu.

Gunakan strategi meta

Untuk hampir setiap strategi pintar ada strategi lain yang mengalahkannya: Misalnya, lawan Anda mungkin menggunakan alasan yang persis sama dengan Anda untuk mengantisipasi langkah selanjutnya dan kemudian menangkisnya. Sekarang Anda mungkin mencoba menebak-nebak lawan Anda lagi, tetapi sulit untuk mengetahui kapan harus berhenti .

Masalah lain adalah bahwa strategi yang baik dalam menebak lawan yang cerdas mungkin jauh dari optimal terhadap lawan yang lebih sederhana.

Bagaimana Anda bisa menyelesaikan ini? Anda membiarkan bot Anda memutuskan strategi mana yang akan digunakan!

Untuk ini, Anda mulai dengan memberikan bot Anda repertoar strategi yang berbeda. Kemudian, sebelum setiap gerakan, bot Anda melihat sejarah permainan yang tercatat sejauh ini dan mengevaluasi bagaimana strategi yang berbeda ini akan berhasil. Maka foto yang paling sukses.

Termasuk strategi yang kuat di tempat pertama akan membantu memberikan bot pilihan yang baik untuk dipilih. Tetapi Anda juga harus memasukkan yang benar-benar sederhana, karena mereka sering bekerja lebih baik melawan lawan yang bodoh.

Anda dapat mempertimbangkan untuk membuat bias pada beberapa strategi, baik untuk menghindari overfitting (misalnya mencoba untuk mengalahkan pola di mana lawan hanya bertindak secara acak) atau untuk mendukung strategi tertentu di awal ketika belum banyak informasi.

Tentu saja, pendekatan ini hanya akan berfungsi untuk jenis tantangan raja-bukit tertentu. Itu sangat baik bagi saya dalam pertandingan Rock-Paper-Scissors-Lizard-Spock . Dalam permainan lain hampir mustahil untuk mengevaluasi bagaimana strategi tertentu akan bernasib jika tidak benar-benar dimainkan.

Bentuk ekstrem dari pendekatan meta ini (yang berbatasan dengan kecurangan) adalah memasukkan perilaku yang diketahui dari semua bot lain ke dalam bot Anda sendiri, sehingga dapat mengantisipasi gerakan mereka dengan sempurna.