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, inilah utas penangkap, utas kucing dapat ditemukan di sini .
Pengontrol dapat diunduh di sini .
Ini adalah KOTH asimetris: Setiap kiriman 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 mencoba untuk mendapatkan skor sebesar mungkin, penangkap mencoba untuk 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 Pengendali), tetapi Anda juga dapat menulis fungsi tambahan di dalam kelas itu. Pengontrol hadir 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 diberikan yang dapat Anda gunakan: isValidMove()
/ isValidPosition()
untuk memeriksa apakah gerakan Anda (kucing) / posisi (penangkap) 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, metode itu juga akan didiskualifikasi. (Lebih disukai jauh lebih sedikit ...)
Program diperbolehkan untuk menyimpan informasi di antara langkah-langkah.
Pengajuan
- Anda dapat membuat kiriman sebanyak yang Anda inginkan.
- Harap jangan secara signifikan mengubah pengiriman yang sudah Anda kirim.
- Silakan setiap pengiriman dalam jawaban baru.
- Setiap pengiriman 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 191674 8 flawr
StupidFill 214246 9 flawr
Achilles 76820 6 The E
Agamemnon 74844 5 The E
CloseCatcher 54920 4 randomra
ForwordCatcher 94246 7 MegaTom
Dijkstra 46500 2 TheNumberOne
HexCatcher 48832 3 randomra
ChoiceCatcher 43828 1 randomra
RandCat 77928 7 flawr
StupidRightCat 81794 6 flawr
SpiralCat 93868 5 CoolGuy
StraightCat 82452 9 CoolGuy
FreeCat 106304 3 randomra
RabidCat 77770 8 cain
Dijkstra's Cat 114670 1 TheNumberOne
MaxCat 97768 4 Manu
ChoiceCat 113356 2 randomra
PRINT_STEPS = true
, pengaturan lebih rinci dalam fileMyFrame.java
). Lalu saya merekam ini dengan LICEcap dan mengeditnya dengan GIMP . Jika Anda memiliki pertanyaan lebih lanjut, tanyakan saja!Jawaban:
Achilles
Achilles tidak terlalu pintar tetapi dia sangat efisien. Pertama-tama dia menghentikan kucing dari menggunakan bungkus papan, lalu dia membagi papan menjadi dua. Lalu ia terus membagi bagian papan yang menjadi bagian kucing sampai kucing itu terperangkap.
Demonstrasi RandCat vs Achilles
sumber
Agamemnon
Agamemnon membelah area kucing menjadi dua dengan garis vertikal sampai kucing hanya memiliki strip lebar 2 untuk bergerak, pada titik mana ia menjebak kucing.
Agamemnon vs RandCat:
Penangkap ini secara konsisten lebih baik daripada Achilles dan saya pikir dia cukup berbeda untuk mendapatkan jawaban baru.
sumber
HexCatcher
Jika penangkap bisa mendapatkan kucing di bagian dalam segi enam besar dengan 3 unit sisi di mana sudut-sudut segi enam sudah ditempati oleh ember, penangkap dapat menjaga kucing di daerah ini dan menangkapnya. Segi enam terlihat seperti ini:
Inilah yang HexCatcher coba capai. Secara mental ubin bidang dengan heksagon besar ini dengan cara bahwa setiap sel sudut adalah bagian dari 3 heksagon besar.
Jika ada kesempatan untuk menjaga kucing di area saat ini dengan menghubungkan dua sudut di sebelah kucing, bot akan melakukan itu. (Misalnya dalam gambar jika kucing di 7,5 kita memilih 7,6 bahkan jika hanya 6,6 dan 8,5 sel belum ditempati.)
Jika sebelumnya bukan opsi, kami memilih untuk memainkan sudut yang merupakan bagian dari area tempat kucing berada. Jika semua sudut seperti itu sudah dipilih (seperti dalam gambar) kami memilih sel di sebelah kucing.
Beberapa perbaikan kecil mungkin dilakukan, seperti menangani lilitan dengan lebih baik (ubin pecah di sana) atau melakukan gerakan pasangan terakhir secara optimal. Saya mungkin melakukan beberapa di antaranya. Jika tidak diizinkan, saya hanya akan menambahkannya (keluar dari kompetisi) untuk yang tertarik.
DijkstrasCat vs HexCatcher:
sumber
CloseCatcher
Pilih salah satu posisi di mana kucing bisa melangkah di langkah berikutnya. Ia memilih jalur yang akan memberikan jalur paling mungkin setelah 3 langkah untuk kucing jika ia akan pindah ke sana dan bidang tidak akan berubah.
Kode hampir identik dengan entri Cat saya, FreeCat , yang memilih arah dengan cara yang sangat mirip.
SpiralCat vs CloseCatcher:
sumber
Dijkstra
Dia tidak terlalu suka kucing (:
v{ >
FreeCat vs Dijkstra
(perlu diperbarui):Cara dia mencoba menangkap kucing:
Dia menganalisis semua kotak papan dan mencoba untuk menemukan kotak yang meminimalkan keterbukaan papan, dan memaksimalkan seberapa banyak papan digantung; dalam kaitannya dengan kucing. Keterbukaan dan kekakuan papan dihitung menggunakan modifikasi dari algoritma yang terkenal .
Keterbukaan:
Keterbukaan papan relatif terhadap suatu posisi adalah jumlah posisi yang dapat dijangkau dari posisi itu.
Ketegaran:
Ketegangan papan relatif terhadap suatu posisi adalah jumlah jarak antara posisi yang dapat dijangkau dan posisi.
Dengan pembaruan terakhir:
Sekarang, dia jauh lebih baik dalam menangkap
FreeCat dan kucingnya sendirisemua kucing.Sayangnya, ia juga jauh lebih buruk dalam menangkap kucing gila yang tidak kooperatif. Dia bisa ditingkatkan dengan mendeteksi apakah kucing itu salah satu yang gila dan kemudian bertindak sebagai CloseCatcher.Bug diperbaiki.
sumber
error: cannot infer type arguments for PriorityQueue<>
di baris iniPriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {
.int[]
antara dua berlian kosong setelahPriorityQueue
.ForwordCatcher
Tempatkan ember di depan kucing, atau jika diambil, letakkan di belakang.
RabidCat vs ForwordCatcher:
sumber
ChoiceCatcher
Menggunakan mekanisme penilaian yang sama dengan entri ChoiceCat saya . Ada sedikit modifikasi yang membantu untuk memilih sel yang relevan pada beberapa langkah pertama karena ChoiceCat tidak peduli dengan beberapa ember pertama karena tidak melihat mereka sebagai ancaman.
ChoiceCatcher tampaknya mencetak skor yang jauh lebih baik daripada para penangkap saat ini.
ChoiceCat vs ChoiceCatcher:
sumber
RandCatcher
Ini dibuat hanya untuk menguji controller dan hanya secara acak menempatkan bucket (sangat tidak efisien).
sumber
StupidFillCatcher
Ini dibuat hanya untuk menguji controller. Itu hanya mengisi kolom demi kolom sampai kucing ditangkap.
sumber