Asymmetrical KOTH: Catch the Cat
UPDATE : File inti diperbarui (termasuk submisisons baru) karena Controller.java tidak menangkap Pengecualian (hanya kesalahan). Itu sekarang menangkap kesalahan dan pengecualian dan juga mencetaknya.
Tantangan ini terdiri dari dua utas, ini adalah utas kucing, utas penangkap dapat ditemukan di sini .
Pengontrol dapat diunduh di sini .
Ini adalah KOTH asimetris: Setiap pengiriman adalah kucing atau penangkap . Ada permainan antara masing-masing pasangan masing-masing kucing dan penangkap. Kucing dan penangkap memiliki peringkat terpisah.
Penangkap
Ada kucing di kisi heksagonal. Tugas Anda adalah menangkapnya secepat mungkin. Setiap belokan, Anda dapat menempatkan ember air di satu sel kisi untuk mencegah kucing masuk ke sana. Tapi kucing itu (mungkin) tidak sebodoh itu, dan setiap kali Anda meletakkan ember, kucing itu akan pindah ke sel kisi lain. Karena kisi-kisi itu heksagonal, kucing dapat pergi ke 6 arah yang berbeda. Tujuan Anda adalah mengelilingi kucing dengan ember air, semakin cepat semakin baik.
Kucing
Anda tahu penangkap ingin menangkap Anda dengan menempatkan ember air di sekitar Anda. Tentu saja Anda mencoba menghindar, tetapi karena Anda adalah kucing malas (seperti kucing), Anda justru mengambil satu langkah pada saat itu. Ini berarti Anda tidak dapat tinggal di tempat yang sama dengan Anda, tetapi Anda harus pindah ke salah satu dari enam tempat di sekitarnya. Setiap kali Anda melihat bahwa penangkap menempatkan ember air baru Anda pergi ke sel lain. Tentu saja Anda berusaha menghindar selama mungkin.
Kisi
Kisi-kisi adalah heksagonal, tetapi karena kami tidak memiliki struktur data heksagonal, kami mengambil 11 x 11
larik 2d persegi dan meniru 'perilaku' heksagonal yang kucing hanya bisa bergerak dalam 6 arah:
Topologi adalah toroidal, itu berarti jika Anda menginjak sel 'luar' dari array, Anda hanya akan ditransfer ke sel yang sesuai di sisi lain array.
Permainan
Kucing mulai keluar pada posisi yang diberikan di grid. Penangkap dapat melakukan langkah pertama, kemudian kucing dan penangkapnya bergantian bergerak sampai kucing ditangkap. Jumlah langkah adalah skor untuk game itu. Kucing berusaha mendapatkan skor sebesar mungkin, penangkap mencoba mendapatkan skor serendah mungkin. Jumlah rata-rata dari semua game yang Anda ikuti akan menjadi skor pengajuan Anda. Ada dua peringkat yang terpisah, satu untuk kucing, satu untuk penangkap.
Pengendali
Kontroler yang diberikan ditulis dalam Java. Sebagai penangkap atau kucing, Anda masing-masing harus menyelesaikan masing-masing kelas Java (sudah ada beberapa contoh primitif) dan letakkan dalam players
paket (dan perbarui daftar kucing / penangkap di kelas Pengontrol), tetapi Anda juga dapat menulis fungsi tambahan di dalam kelas itu. Controller dilengkapi dengan masing-masing dua contoh kerja dari kelas kucing / penangkap sederhana.
Bidang ini adalah array 11 x 11
2D int
yang menyimpan nilai status sel saat ini. Jika sebuah sel kosong, ia memiliki nilai 0
, jika ada kucing ia memiliki nilai -1
dan jika ada sebuah ember ada sebuah 1
.
Ada beberapa fungsi yang dapat Anda gunakan: isValidMove()
/ isValidPosition()
untuk memeriksa apakah gerakan (kucing) / posisi (penangkap) Anda valid.
Setiap kali giliran Anda, fungsi Anda takeTurn()
dipanggil. Argumen tersebut berisi salinan kisi saat ini dan memiliki metode seperti read(i,j)
membaca sel di (i,j)
, serta isValidMove()/ isValidPosition()
memeriksa validitas jawaban Anda. Ini juga mengelola pembungkus topologi toroidal, yang berarti bahkan jika grid hanya 11 x 11, Anda masih dapat mengakses sel (-5,13).
Metode harus mengembalikan int
array dari dua elemen, yang mewakili kemungkinan pergerakan. Untuk kucing ini adalah {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}
yang mewakili posisi relatif dari mana kucing ingin pergi, dan para penangkap mengembalikan koordinat absolut di mana mereka ingin menempatkan ember {i,j}
.
Jika metode Anda menghasilkan langkah yang tidak valid, kiriman Anda akan didiskualifikasi. Langkah tersebut dianggap tidak valid, jika di tempat tujuan Anda sudah menjadi ember atau langkah tersebut tidak diperbolehkan / tujuan sudah ditempati (sebagai kucing), atau jika sudah ada ember / kucing (sebagai penangkap). Anda dapat memeriksa itu sebelumnya dengan fungsi yang diberikan.
Kiriman Anda harus bekerja cukup cepat. Jika metode Anda membutuhkan waktu lebih dari 200 ms untuk setiap langkah, itu juga akan didiskualifikasi. (Lebih disukai jauh lebih sedikit ...)
Program diizinkan untuk menyimpan informasi di antara langkah-langkah.
Pengajuan
- Anda dapat membuat kiriman sebanyak yang Anda inginkan.
- Tolong jangan secara signifikan mengubah kiriman yang sudah Anda kirim.
- Silakan setiap pengiriman dalam jawaban baru.
- Setiap pengajuan sebaiknya memiliki nama yang unik.
- Kiriman harus terdiri dari kode kelas Anda serta deskripsi yang memberi tahu kami bagaimana kiriman Anda bekerja.
- Anda dapat menulis baris
<!-- language: lang-java -->
sebelum kode sumber Anda untuk mendapatkan penyorotan sintaksis otomatis.
Mencetak gol
Semua kucing akan bersaing melawan semua penangkap dalam jumlah yang sama beberapa kali. Saya akan mencoba memperbarui skor saat ini sering, pemenang akan ditentukan ketika aktivitas telah menurun.
Tantangan ini terinspirasi oleh game flash lama ini
Terima kasih @PhiNotPi untuk pengujian dan memberikan umpan balik yang membangun.
Skor Saat Ini (100 Game per pasangan)
Name Score Rank Author
RandCatcher 191962 8 flawr
StupidFill 212688 9 flawr
Achilles 77214 6 The E
Agamemnon 74896 5 The E
CloseCatcher 54776 4 randomra
ForwordCatcher 93814 7 MegaTom
Dijkstra 47558 2 TheNumberOne
HexCatcher 48644 3 randomra
ChoiceCatcher 43834 1 randomra
RandCat 77490 9 flawr
StupidRightCat 81566 6 flawr
SpiralCat 93384 5 CoolGuy
StraightCat 80930 7 CoolGuy
FreeCat 106294 3 randomra
RabidCat 78616 8 cain
Dijkstra's Cat 115094 1 TheNumberOne
MaxCat 98400 4 Manu
ChoiceCat 113612 2 randomra
main.Controller
, memanggilgetCatchers()
, dan mensimulasikan / menyabot respons para penangkap melaluitakeTurn
metode mereka ?Jawaban:
FreeCat
Pilih langkah yang akan memberinya jalur paling mungkin setelah 3 langkah jika bidang tidak berubah.
FreeCat vs Achilles:
sumber
Kucing Dijkstra
Dia belajar dan menerapkan algoritma master masternya. Perhatikan bahwa ia bergantung pada beberapa metode di kelas penangkap yang sesuai.
Dijkstra's Cat vs Hexcatcher (perlu diperbarui):
Bagaimana dia bekerja:
Dia mencoba menemukan langkah yang meminimalkan kekasaran dewan sehubungan dengan dirinya sendiri. Untuk informasi lebih lanjut, lihat pos penangkap yang sesuai.
Dengan pembaruan:
Dia sekarang menghindari bentuk geometris aneh yang kadang-kadang terbentuk oleh ember air.
sumber
MaxCat
Saya mencoba menerapkan algoritma Minimax. Namun, itu tidak berkinerja sangat baik karena keterbatasan waktu. Sunting: Sekarang menggunakan multithreading, tetapi (minimal di komputer saya) saya tidak dapat mengatur kedalaman lebih tinggi. Kalau tidak, timeout terjadi. Menggunakan PC dengan 6 inti atau lebih, pengiriman ini akan jauh lebih baik :)
MaxCat vs Dijkstra:
sumber
Field
publik. Saya minta maaf saya belum memperbarui file, tetapi kami membahas ini sebelumnya!SpiralCat
Bergerak dengan cara spiral. Itu
SpiralCat vs Agamemnon:
sumber
turns[i]
untukturns[i%6]
untuk menghindari keluar batas (yang seharusnya tidak terjadi di stuation ini).turns[i%6]
? Maksudku,takeTurn
tidak akan dipanggil jika kucingnya diblokir, kan?i>=6
seharusnya tidak pernah terjadi.RabidCat
RabidCat memiliki hidrofobia, jadi dia takut dengan ember air. Dia menemukan yang terdekat dan berlari ke arah yang berlawanan.
RabidCat vs ForwordCatcher:
sumber
ChoiceCat
Untuk setiap posisi kucing baru yang mungkin, kami memeriksa kebaikannya dan memilih yang terbaik. Kebaikan adalah fungsi dari dua sel tetangga terbaik yang lebih jauh dari posisi kucing daripada posisi yang skornya kita hitung. Kami hanya menggunakan dua sel karena satu dapat diblokir dan kucing hanya perlu satu lagi untuk lolos. Fungsi kami lebih suka dua sel yang cukup baik daripada satu besar dan satu buruk. Posisi dengan bucket memiliki skor 0 dan sel bebas terjauh memiliki skor 1.
ChoiceCat tampaknya mendapat skor lebih baik daripada kucing saat ini.
ChoiceCat vs ChoiceCatcher:
sumber
StupidRightCat
Ini dibuat hanya untuk menguji controller. Kucing itu bergerak ke kanan kapan pun memungkinkan, jika tidak bergerak ke arah acak.
sumber
RandCat
Ini dibuat hanya untuk menguji controller. Kucing itu hanya bergerak secara acak.
sumber
StraightCat
Kucing ini bergerak lurus.
Pada awalnya, ia memilih arah acak dan terus bergerak ke arah ini sampai tidak bisa dalam hal ini, itu menggeser arah dengan cara searah jarum jam ke arah yang valid berikutnya dan mengulangi proses ini.
StraightCat vs Agamemnon:
sumber