Ini adalah Tantangan Fortnightly # 3. Tema: Algoritma Genetika
Tantangan ini sedikit percobaan. Kami ingin melihat apa yang bisa kami lakukan, berdasarkan tantangan, dengan algoritma genetika. Tidak semuanya mungkin optimal, tetapi kami mencoba yang terbaik untuk membuatnya dapat diakses. Jika ini berhasil, siapa yang tahu apa yang mungkin kita lihat di masa depan. Mungkin genetik King of the Hill?
Speknya cukup panjang! Kami telah mencoba memisahkan spec ke dalam The Basics - minimum yang perlu Anda ketahui untuk mulai bermain dengan framework dan mengirimkan jawaban - dan The Gory Details - spec lengkap, dengan semua detail tentang controller, berdasarkan mana Anda bisa menulis sendiri
Jika Anda memiliki pertanyaan apa pun, silakan bergabung dengan kami di obrolan!
Anda seorang peneliti dalam psikologi perilaku. Ini Jumat malam dan Anda dan kolega Anda memutuskan untuk bersenang-senang dan menggunakan tikus lab Anda untuk balapan tikus kecil. Faktanya, sebelum kita terlalu terikat secara emosional dengan mereka, mari kita sebut mereka spesimen .
Anda telah menyiapkan trek balap kecil untuk spesimen, dan untuk membuatnya lebih menarik, Anda telah meletakkan beberapa dinding dan perangkap serta teleporter di sepanjang trek. Sekarang, spesimen Anda masih tikus ... mereka tidak tahu apa itu jebakan atau teleporter. Yang mereka lihat adalah beberapa hal dalam berbagai warna. Mereka juga tidak memiliki memori apa pun - yang dapat mereka lakukan hanyalah membuat keputusan berdasarkan lingkungan mereka saat ini. Saya kira seleksi alam akan memilih spesimen yang tahu bagaimana menghindari jebakan dari yang tidak (perlombaan ini akan memakan waktu ...). Biarkan game dimulai! †
† 84.465 spesimen terluka dalam pembuatan tantangan ini.
Dasar
Ini adalah permainan pemain tunggal (Anda dan kolega Anda tidak ingin mencampuradukkan populasi sehingga masing-masing membangun trek balap mereka sendiri). Jalur balap adalah kotak persegi panjang, tinggi 15 sel dan lebar 50 sel. Anda mulai dengan 15 spesimen pada sel acak (tidak harus berbeda) di tepi kiri (di mana x = 0 ). Spesimen Anda harus mencoba mencapai tujuan yang merupakan sel mana pun pada x ≥ 49 dan 0 ≤ y ≤ 14 (spesimen dapat melampaui jejak ke kanan). Setiap kali ini terjadi, Anda mendapat poin. Anda juga memulai permainan dengan 1 poin. Anda harus mencoba memaksimalkan poin Anda setelah 10.000 putaran.
Beberapa spesimen dapat menempati sel yang sama dan tidak akan berinteraksi.
Pada setiap belokan, setiap spesimen melihat kisi 5x5 di sekelilingnya (dengan sendirinya di tengah). Setiap sel grid yang akan berisi warna -1
untuk 15
. -1
mewakili sel yang di luar batas. Spesimen Anda mati jika bergerak di luar batas. Sedangkan untuk warna lain, mereka mewakili sel kosong, perangkap, dinding dan teleporter. Tetapi spesimen Anda tidak tahu warna mana yang mewakili apa dan Anda juga tidak. Namun ada beberapa kendala:
- 8 warna akan mewakili sel kosong.
- 4 warna akan mewakili teleporter. Teleporter akan mengirim spesimen ke sel tertentu dalam lingkungan 9x9. Offset ini akan sama untuk semua teleporter dengan warna yang sama.
- 2 warna akan mewakili dinding. Pindah ke dinding sama dengan berdiri diam.
- 2 warna akan mewakili jebakan. Jebakan menunjukkan bahwa salah satu dari 9 sel di lingkungan terdekatnya adalah mematikan (tidak harus sel jebakan itu sendiri). Offset ini akan sama untuk semua jebakan dengan warna yang sama.
Sekarang, tentang seleksi alam ... setiap spesimen memiliki genom, yang merupakan angka dengan 100 bit. Spesimen baru akan dibuat dengan mengembangbiakkan dua spesimen yang ada, dan kemudian sedikit bermutasi genom. Semakin sukses suatu spesimen, semakin besar peluangnya untuk bereproduksi.
Jadi, inilah tugas Anda : Anda akan menulis satu fungsi, yang menerima sebagai input kisi warna 5x5 yang dilihat spesimen, serta genomnya. Fungsi Anda akan mengembalikan gerakan (Δx, Δy) untuk spesimen, di mana Δx dan Δy masing-masing akan menjadi satu {-1, 0, 1}
. Anda tidak boleh menyimpan data apa pun di antara panggilan fungsi. Ini termasuk menggunakan generator nomor acak Anda sendiri. Fungsi Anda akan dilengkapi dengan RNG yang diunggulkan yang bebas Anda gunakan sesuai keinginan.
Skor kiriman Anda akan menjadi rata - rata geometrik dari jumlah poin di 50 trek acak. Kami telah menemukan bahwa skor ini sedikit berbeda. Karena itu, skor ini akan menjadi permulaan . Setelah tantangan ini mereda, batas waktu akan diumumkan. Pada akhir batas waktu, 100 papan akan dipilih secara acak, dan semua pengiriman akan disimpan kembali di 100 papan ini. Jangan ragu untuk memberikan perkiraan skor pada jawaban Anda, tetapi kami akan menilai sendiri setiap pengiriman untuk memastikan tidak ada yang menipu.
Kami telah menyediakan program pengontrol dalam beberapa bahasa. Saat ini, Anda dapat menulis kiriman Anda dengan Python (2 atau 3), Ruby , C ++ , C # atau Java . Pengontrol menghasilkan papan, menjalankan permainan dan menyediakan kerangka kerja untuk algoritma genetika. Yang harus Anda lakukan adalah menyediakan fungsi bergerak.
Tunggu, jadi apa yang harus saya lakukan dengan genom?
Tantangannya adalah untuk mencari tahu!
Karena spesimen tidak memiliki memori, yang Anda dapatkan pada gilirannya adalah kotak warna 5x5 yang tidak berarti apa-apa bagi Anda. Jadi, Anda harus menggunakan genom untuk mencapai tujuan. Gagasan umum adalah bahwa Anda menggunakan bagian genom untuk menyimpan informasi tentang warna atau tata letak kisi, dan bot Anda mendasarkan keputusannya pada informasi tambahan yang disimpan dalam genom.
Sekarang, tentu saja Anda tidak dapat menyimpan apa pun di sana secara manual. Jadi informasi aktual yang tersimpan di sana pada awalnya akan sepenuhnya acak. Tetapi algoritma genetika akan segera memilih spesimen-spesimen yang genomnya mengandung informasi yang tepat sambil membunuh yang memiliki informasi yang salah. Tujuan Anda adalah menemukan pemetaan dari bit genom dan bidang pandang Anda ke suatu langkah, yang memungkinkan Anda menemukan jalur ke tujuan dengan cepat dan yang secara konsisten berevolusi menjadi strategi kemenangan.
Ini harus menjadi informasi yang cukup untuk memulai. Jika mau, Anda dapat melewati bagian berikutnya, dan pilih pengontrol pilihan Anda dari daftar pengontrol di bagian bawah (yang juga berisi informasi tentang cara menggunakan pengontrol tertentu).
Baca terus jika Anda ingin semua ...
Detail Gory
Spesifikasi ini lengkap. Semua pengendali harus menerapkan aturan ini.
Semua keacakan menggunakan distribusi yang seragam, kecuali dinyatakan sebaliknya.
Pembuatan trek:
- Lagu tersebut adalah kotak persegi panjang, lebar X = 53 sel dan tinggi Y = 15 sel. Sel dengan x ≥ 49 adalah sel tujuan (di mana x berbasis nol).
- Setiap sel memiliki warna tunggal dan mungkin atau mungkin tidak mematikan - sel tidak mematikan kecuali ditentukan oleh salah satu jenis sel di bawah ini.
- Ada 16 warna sel yang berbeda, berlabel dari
0
ke15
, yang artinya akan berubah dari satu game ke game lainnya. Selain itu,-1
merupakan sel yang berada di luar batas - ini mematikan . - Pilih 8 warna acak . Ini akan menjadi sel kosong (yang tidak memiliki efek).
- Pilih 4 warna lebih acak . Ini adalah teleporter. Untuk dua warna ini, pilih offset non-nol di lingkungan 9x9 (dari (-4, -4) hingga (4,4) kecuali (0,0)). Untuk dua warna lainnya, balikkan offset tersebut. Jika spesimen menginjak teleporter, ia segera dipindahkan oleh offset itu.
- Pilih 2 warna lebih acak . Ini adalah jebakan. Untuk masing-masing warna ini, pilih offset di lingkungan 3x3 (dari (-1, -1) hingga (1,1)). Jebakan menunjukkan bahwa sel pada offset itu mematikan . Catatan: Sel perangkap itu sendiri belum tentu mematikan.
- The 2 warna yang tersisa adalah dinding, yang menghambat gerakan. Mencoba untuk pindah ke sel dinding akan mengubah gerakan menjadi diam. Sel-sel dinding sendiri mematikan .
- Untuk setiap sel non-tujuan dari kisi, pilih warna acak. Untuk setiap sel sasaran pilih warna kosong acak .
- Untuk setiap sel di tepi kiri lintasan, tentukan apakah tujuan dapat dicapai dalam 100 putaran (sesuai dengan aturan urutan putaran di bawah). Jika demikian, sel ini adalah sel awal yang dapat diterima . Jika kurang dari 10 sel awal, buang trek dan hasilkan yang baru.
- Buat 15 spesimen, masing-masing dengan genom acak dan usia 0 . Tempatkan setiap spesimen pada sel awal yang acak.
Putar pesanan:
- Langkah-langkah berikut akan dilakukan, secara berurutan, untuk setiap spesimen. Spesimen tidak berinteraksi atau melihat satu sama lain, dan dapat menempati sel yang sama.
- Jika usia spesimen adalah 100 , ia akan mati. Kalau tidak, tambah umurnya 1.
- Spesimen diberi bidang pandang - kotak warna 5x5, berpusat pada spesimen - dan mengembalikan gerakan di lingkungan 3x3. Bergerak di luar rentang ini akan menyebabkan pengontrol berakhir.
- Jika sel target adalah dinding, maka bergerak diubah menjadi (0,0).
- Jika sel target adalah teleporter, spesimen dipindahkan oleh offset teleporter. Catatan: Langkah ini dilakukan satu kali , bukan secara iteratif.
- Jika sel saat ini ditempati oleh spesimen (berpotensi setelah menggunakan satu teleporter) mematikan , spesimen mati. Ini adalah satu - satunya waktu spesimen mati (terlepas dari langkah 1.1. Di atas). Secara khusus, spesimen baru yang memunculkan sel yang mematikan tidak akan langsung mati, tetapi memiliki kesempatan untuk pindah dari sel berbahaya terlebih dahulu.
- Jika spesimen menempati sel tujuan, skor poin, pindahkan spesimen ke sel awal acak dan setel ulang umurnya ke 0.
- Jika ada kurang dari dua spesimen yang tersisa di papan, permainan berakhir.
- Buat 10 spesimen baru dengan usia 0 . Setiap genom ditentukan (secara individu) oleh aturan pemuliaan di bawah ini. Tempatkan setiap spesimen pada sel awal yang acak.
Pembiakan:
Ketika spesimen baru dibuat pilih dua orang tua yang berbeda secara acak, dengan bias terhadap spesimen yang telah berkembang lebih jauh ke kanan. Probabilitas spesimen yang akan dipilih sebanding dengan skor kebugaran saat ini . Skor kebugaran spesimen adalah
1 + x + 50 * berapa kali mencapai tujuan
di mana x adalah indeks horisontal berbasis 0. Spesimen yang dibuat pada gilirannya yang sama tidak dapat dipilih sebagai orang tua.
Dari dua orang tua, pilih satu yang acak untuk mengambil bit genom pertama.
- Sekarang saat Anda berjalan di sepanjang genom, alihkan orang tua dengan probabilitas 0,05 , dan terus ambil bit dari orang tua yang dihasilkan.
- Mutasikan genom yang dirakit lengkap: untuk setiap bit, balikkan dengan probabilitas 0,01 .
Mencetak:
- Satu pertandingan berlangsung 10.000 putaran.
- Pemain memulai permainan dengan 1 poin (untuk memungkinkan penggunaan mean geometrik).
- Setiap kali spesimen mencapai tujuan, pemain mendapat skor.
- Untuk saat ini, pengiriman masing-masing pemain akan dijalankan selama 50 pertandingan, masing-masing dengan trek acak yang berbeda.
- Pendekatan di atas menghasilkan lebih banyak variasi daripada yang diinginkan. Setelah tantangan ini mereda, batas waktu akan diumumkan. Pada akhir tenggat waktu, 100 papan akan dipilih secara acak, dan semua pengiriman akan disimpan di 100 papan ini.
- Skor keseluruhan pemain adalah rata - rata geometrik dari skor masing-masing game ini.
Pengendali
Anda dapat memilih salah satu dari pengontrol berikut (karena mereka secara fungsional setara). Kami telah menguji semuanya, tetapi jika Anda menemukan bug, ingin meningkatkan kode atau kinerja, atau menambahkan fitur seperti output grafis, silakan kirim menimbulkan masalah atau mengirim permintaan tarik di GitHub! Anda juga dapat menambahkan pengontrol baru dalam bahasa lain!
Klik nama bahasa untuk setiap pengontrol untuk sampai ke direktori yang benar di GitHub, yang berisi README.md
dengan petunjuk penggunaan yang tepat.
Jika Anda tidak terbiasa dengan git dan / atau GitHub, Anda dapat mengunduh seluruh repositori sebagai ZIP dari halaman depan (lihat tombol di bilah sisi).
Python
- Paling teruji. Ini adalah implementasi referensi kami.
- Bekerja dengan Python 2.6+ dan Python 3.2+!
- Sangat lambat. Kami sarankan menjalankannya dengan PyPy untuk mempercepat.
- Mendukung output grafis menggunakan salah satu
pygame
atautkinter
.
Rubi
- Diuji dengan Ruby 2.0.0. Harus bekerja dengan versi yang lebih baru.
- Ini juga cukup lambat, tetapi Ruby mungkin nyaman untuk membuat prototipe ide untuk pengiriman.
C ++
- Membutuhkan C ++ 11.
- Secara opsional mendukung multithreading.
- Sejauh ini pengontrol tercepat dalam kelompok itu.
C #
- Menggunakan LINQ, sehingga membutuhkan .NET 3.5.
- Agak lambat.
Jawa
- Tidak terlalu lambat. Tidak terlalu cepat.
Papan Awal Pendahuluan
Semua skor bersifat sementara. Namun demikian, jika ada sesuatu yang salah atau kedaluwarsa, beri tahu saya. Pengajuan contoh kami terdaftar untuk perbandingan, tetapi tidak dalam pertentangan.
Score | # Games | User | Language | Bot
===================================================================================
2914.13 | 2000 | kuroi neko | C++ | Hard Believers
1817.05097| 1000 | TheBestOne | Java | Running Star
1009.72 | 2000 | kuroi neko | C++ | Blind faith
782.18 | 2000 | MT0 | C++ | Cautious Specimens
428.38 | | user2487951 | Python | NeighborsOfNeighbors
145.35 | 2000 | Wouter ibens | C++ | Triple Score
133.2 | | Anton | C++ | StarPlayer
122.92 | | Dominik Müller | Python | SkyWalker
89.90 | | aschmack | C++ | LookAheadPlayer
74.7 | | bitpwner | C++ | ColorFarSeeker
70.98 | 2000 | Ceribia | C++ | WallGuesser
50.35 | | feersum | C++ | Run-Bonus Player
35.85 | | Zgarb | C++ | Pathfinder
(34.45) | 5000 | Martin Büttner | <all> | ColorScorePlayer
9.77 | | DenDenDo | C++ | SlowAndSteady
3.7 | | flawr | Java | IAmARobotPlayer
1.9 | | trichoplax | Python | Bishop
1.04 | 2000 | fluffy | C++ | Gray-Color Lookahead
Kredit
Tantangan ini adalah upaya kolaborasi yang sangat besar:
- Nathan Merril: Menulis pengontrol Python dan Java. Mengubah konsep tantangan dari King-of-the-Hill menjadi Balap Tikus.
- trichoplax: Playtesting. Bekerja pada pengontrol Python.
- feersum: Menulis kontroler C ++.
- VisualMelon: Menulis kontroler C #.
- Martin Büttner: Konsep. Menulis pengontrol Ruby. Playtesting. Bekerja pada pengontrol Python.
- T Abraham: Playtesting. Diuji Python dan ditinjau C # dan C ++ controller.
Semua pengguna di atas (dan mungkin beberapa lagi saya lupa) telah berkontribusi pada keseluruhan desain tantangan.
Pembaruan pengontrol C ++
Jika Anda menggunakan C ++ dengan Visual Studio dan multithreading, Anda harus mendapatkan pembaruan terbaru karena bug dengan seeding generator nomor acak mereka yang memungkinkan papan duplikat untuk diproduksi.
sumber
'In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.'
Jawaban:
Iman buta - C ++ - tampaknya skor di atas 800 (!) Selama 2000 berjalan
Genom pengkodean warna dengan umpan balik trek misterius dan pencegah pukulan dinding yang efektif
Contoh hasil:
Berdasarkan pengujian panjang feersum yang tidak sukarela, saya rasa 2000 run sudah cukup untuk menghasilkan hasil yang cukup stabil.
Karena pengontrol saya yang dimodifikasi menampilkan rata-rata geometrik saat ini setelah setiap putaran, saya mengkonfirmasi secara visual bahwa variasi selama 50 putaran terakhir relatif kecil (+ - 10 poin).
Apa yang membuat makhluk ini berdetak
Alih-alih memberikan prioritas yang sama untuk setiap warna, saya mempertimbangkan nilai-nilai yang mungkin ini:
Meskipun saya terlalu malas untuk menamainya kembali, ini lebih merupakan "detektor bahaya" yang menunjukkan lokasi (seharusnya) perangkap yang sebenarnya, sebuah tembok, seorang teleporter yang menunggu untuk mengirim pengembara yang tidak curiga ke tempat yang tidak menyenangkan atau bahkan pintu masuk orang mati -akhir. Singkatnya, tempat di mana tikus bijak lebih suka tidak pergi.
gen yang baik atau buruk hanya mengambil 2 bit untuk menyimpan (misalnya
11
dan10
), tapi perangkap memerlukan 4 bit (0ttt
di manattt
merupakan salah satu yang mungkin 8 lokasi "berbahaya").Untuk menjaga setiap gen konsisten (yaitu mempertahankan artinya setelah dicampur ke dalam genom yang sama sekali berbeda, yang mengharuskan setiap gen kode warna berada di lokasi tetap), semua nilai dikodekan pada 4 bit (sehingga baik dikodekan sebagai
11xx
dan buruk sebagai10xx
), dengan total 16 * 4 = 64 bit.36 bit yang tersisa digunakan sebagai "anti-wall-bangers" (lebih lanjut tentang itu nanti). 25 warna di sekitarnya di-hash menjadi indeks 36 bit ini. Setiap bit menunjukkan arah vertikal yang disukai (atas atau bawah), yang digunakan ketika ada pilihan yang mungkin antara dua sel.
Strateginya adalah sebagai berikut:
Hai tikus, lihatlah musuh-musuh jenismu
Hal terburuk yang dapat terjadi pada suatu populasi adalah belum menghasilkan pemenang, tetapi banyak tikus yang menempel di dinding atau di dalam lingkaran teleportasi tak terbatas yang cukup dekat dengan tujuan untuk memiliki kesempatan dominan dipilih untuk berkembang biak .
Bertentangan dengan tikus yang terjepit dalam perangkap atau dipindahkan ke dinding, hewan pengerat ini hanya akan dibunuh pada usia lanjut.
Mereka tidak memiliki keunggulan kompetitif atas sepupu mereka yang terjebak 3 sel sejak awal, tetapi mereka akan memiliki cukup waktu untuk membiakkan generasi demi generasi kretin sampai genom mereka menjadi dominan, sehingga merusak keragaman genetik dengan buruk tanpa alasan yang jelas.
Untuk mengurangi fenomena ini, idenya adalah untuk membuat keturunan dari tikus-tikus yang buruk dan jahat ini lebih mungkin untuk dihindari mengikuti langkah-langkah nenek moyang mereka.
Indikasi arah vertikal hanya 1 bit panjang (pada dasarnya mengatakan "coba naik atau turun dulu di lingkungan ini"), dan beberapa bit cenderung memiliki efek pada jalur yang diikuti, sehingga mutasi dan / atau crossover harus memiliki dampak signifikan.
Banyak keturunan akan memiliki perilaku yang berbeda dan tidak akan membenturkan kepala mereka pada dinding yang sama (di antara mayat leluhur mereka yang kelaparan).
Subtelty di sini adalah bahwa indikasi ini bukan faktor dominan dalam perilaku tikus. Interpretasi warna akan tetap berlaku dalam banyak kasus (pilihan naik / turun hanya akan berarti jika memang ada dua "baik"dan apa yang dilihat tikus sebagai warna yang tidak berbahaya bukanlah seorang teleporter yang menunggu untuk melemparkannya ke dinding).
Mengapa ini (tampaknya) berhasil?
Saya masih tidak tahu persis mengapa.
Sentuhan absolut keberuntungan yang tetap menjadi misteri yang belum terpecahkan adalah logika pemetaan perangkap. Tanpa diragukan lagi itu adalah landasan kesuksesan, tetapi ia bekerja dengan cara misteriusnya sendiri.
Dengan pengkodean yang digunakan, genom acak akan menghasilkan 25% pengidentifikasi warna "baik", 25% "buruk" dan 50% "perangkap".
pengidentifikasi "jebakan" pada gilirannya akan menghasilkan estimasi "baik" dan "buruk" berkorelasi dengan lingkungan 5x5.
Akibatnya, tikus di lokasi tertentu akan "melihat" dunia sebagai campuran dari warna "go / no go" yang stabil dan kontekstual.
Seperti yang ditunjukkan oleh mekanisme anti-banging yang cukup berhasil, elemen terburuk di trek adalah dinding yang ditakuti (dan sepupunya loop teleportasi, tapi saya kira ini jauh lebih jarang terjadi).
Kesimpulannya adalah, program yang berhasil harus di atas segalanya berhasil untuk mengembangkan tikus yang mampu mendeteksi posisi yang akan menyebabkan kelaparan lambat tanpa mencapai tujuan.
Bahkan tanpa "menebak" dua warna yang mewakili dinding, warna "perangkap" tampaknya berkontribusi pada penghindaran dinding dengan membiarkan tikus melewati beberapa rintangan bukan karena "melihat" dinding, tetapi karena estimasi "perangkap" mengesampingkan ini. sel-sel dinding tertentu di lingkungan tertentu ini.
Meskipun tikus mencoba bergerak ke arah tujuan (yang mungkin mengarah pada pemikiran bahwa indikator perangkap yang paling "berguna" adalah yang mengindikasikan bahaya di depan), saya pikir semua arah perangkap memiliki pengaruh yang hampir sama: perangkap yang mengindikasikan "bahaya di belakang "Terletak 2 sel di depan tikus memiliki pengaruh yang sama dengan yang menunjukkan" bahaya di depan "ketika tikus berdiri tepat di atasnya.
Sayangnya, mengapa campuran ini memiliki properti untuk membuat genome menyatu dengan sukses adalah jauh melampaui matematika saya, sayangnya.
Saya merasa lebih nyaman dengan alat penangkis-tembok. Ini hanya bekerja sesuai rencana, meskipun jauh di atas harapan saya (skor pada dasarnya dikalikan dengan empat).
Saya meretas controller untuk menampilkan beberapa data. Berikut ini beberapa langkah:
Di sini berkembang biak tikus super muncul lebih awal (jalur mungkin diizinkan berjalan dalam garis lurus dan beberapa tikus yang beruntung pada generasi pertama memiliki DNA yang tepat untuk mengambil keuntungan darinya). Jumlah spesimen pada akhirnya adalah sekitar setengah dari max teoritis dari beberapa 100.000 tikus, yang berarti hampir setengah makhluk memperoleh kemampuan untuk bertahan hidup jalur khusus ini tanpa batas (!).
Tentu saja skor yang dihasilkan hanya cabul - seperti waktu perhitungan, omong-omong.
Di sini kita bisa melihat perbaikan genom di tempat kerja. Silsilah antara dua genom terakhir muncul dengan jelas. The baik dan buruk evaluasi adalah yang paling signifikan. The perangkap indikasi tampaknya berosilasi sampai mereka menstabilkan ke "berguna" perangkap atau bermutasi menjadi baik atau buruk .
Tampaknya gen warna memiliki beberapa karakteristik bermanfaat:
(warna tertentu harus ditangani dengan cara tertentu).
Setiap pengkodean warna dapat dilemparkan ke dalam genom yang sama sekali berbeda tanpa mengubah perilaku secara dramatis - kecuali jika warna tersebut ternyata merupakan fakta yang menentukan (biasanya dinding atau teleporter yang mengarah ke loop tak terbatas).
Ini kurang demikian dengan pengkodean prioritas dasar, karena warna yang paling utama adalah satu-satunya informasi yang digunakan untuk memutuskan ke mana harus pindah. Di sini semua warna "baik" sama, sehingga warna yang diberikan ditambahkan ke daftar "baik" akan memiliki dampak yang lebih kecil.
, pengkodean baik / buruk hanya memiliki 2 bit signifikan dari 4, dan lokasi perangkap mungkin berubah sebagian besar waktu tanpa mengubah perilaku tikus secara signifikan.
. Gen yang bermutasi menjadi "baik" akan memiliki sedikit efek (jika misalnya sesuai dengan sel kosong, itu mungkin memungkinkan untuk menemukan jalur baru yang lebih pendek, tetapi itu juga bisa mengarahkan tikus langsung ke perangkap), atau yang dramatis (jika warnanya mewakili dinding, tikus yang baru kemungkinan besar akan terjebak di suatu tempat).
Gen yang beralih ke "perangkap" akan menghilangkan tikus dari warna esensial atau tidak memiliki efek nyata.
Mutasi lokasi jebakan hanya akan berarti jika memang ada jebakan (atau sesuatu yang berbahaya) di depan, yang memiliki probabilitas yang relatif kecil (saya akan mengatakan sekitar 1/3).
Terakhir, saya kira 36 bit terakhir berkontribusi tidak hanya untuk menghindari tikus terjebak, tetapi juga untuk menyebarkan tikus lebih merata di trek, sehingga menjaga keragaman genetik sampai genom pemenang muncul dan menjadi dominan melalui bagian kode warna.
Pekerjaan selanjutnya
Saya harus mengatakan saya menemukan makhluk kecil ini menarik.
Sekali lagi terima kasih kepada semua kontributor untuk tantangan luar biasa ini.
Saya berpikir untuk membantai controller lebih jauh untuk menampilkan data yang lebih signifikan, seperti nenek moyang tikus yang sukses.
Saya juga sangat ingin melihat tikus-tikus ini beraksi, tetapi bahasa C ++ b ** ch ini membuat membuat - apalagi menjiwai - gambar (di antara banyak hal lain) tugas yang berantakan.
Pada akhirnya, saya ingin menghasilkan setidaknya penjelasan tentang sistem perangkap, dan mungkin memperbaikinya.
Peretasan pengontrol
Jika seseorang tertarik, saya dapat mempublikasikan modifikasi yang saya buat ke controller.
Mereka kotor dan murah, tetapi mereka melakukan pekerjaan itu.
Saya bukan ahli GitHub, jadi itu harus melalui posting belaka.
sumber
^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^
makna Anda ? Sisanya bisa saya tebak, tetapi saya mengalami masalah dengan bagian itu?Percaya keras - C ++ - (teleporter yang ditingkatkan): 10.000+ untuk 2000 run
(ini adalah evolusi dari keyakinan Buta , jadi Anda mungkin ingin memanjat dinding teks lain sebelum ini)
Episode IV: mendapatkan posisi kita di grid
Hasil
Saya beralih ke g ++ / MinGW dan 3 utas.
Kode yang dihasilkan oleh GNU lebih dari dua kali lebih cepat dari Microsoft.
Tidak heran, ada apa dengan implementasi STL mereka yang mengerikan.
Teleporter
Efek teleporter sangat tergantung pada posisi. Sampai sekarang saya senang menganggap teleporter sebagai selalu baik (dilihat sebagai ruang kosong) atau selalu buruk (dilihat sebagai dinding sehingga tidak ada hewan pengerat yang mau menerimanya).
Ini model yang terlalu kasar.
Teleporter yang diberikan dapat mendorong tikus ke depan sampai beberapa sel dari gawang, tetapi begitu ada teleporter yang sama dapat membuang tikus dari papan.
Teleporter seperti itu kemungkinan besar akan diakui sebagai lumayan (karena ia meningkatkan kebugaran lebih cepat daripada ketika "berjalan" ke lokasi x yang sama), menjadi bagian dari genom dominan dan membunuh hampir semua tikus yang mempercayainya sebagai "selalu aman".
Karena tikus tidak memiliki cara untuk mengetahui posisi X mereka, satu-satunya solusi untuk mendeteksi teleporter berbahaya ini adalah memutuskan apakah akan menginjaknya berdasarkan satu-satunya data kontekstual yang tersedia, yaitu kotak warna 5x5.
Untuk melakukannya, saya mendefinisikan 4 jenis gen warna:
Idenya adalah untuk mencoba membedakan teleporter dengan melihat 8 tetangga terdekatnya. Karena kemungkinan memiliki 8 tetangga yang identik di lokasi yang diberikan sangat rendah, yang seharusnya memungkinkan untuk mengidentifikasi contoh unik dari setiap teleporter.
8 warna tetangga dapat dikombinasikan untuk membentuk tanda tangan lokal, yang masing-masing berbeda dengan posisi di labirin. Sayangnya, 8 tetangga hanya terlihat untuk sel yang terletak di dalam bidang penglihatan 3x3 bidang batin, sehingga tanda tangan akan tidak akurat pada tepi bidang penglihatan.
Namun demikian, ini akan memberi kita informasi kontekstual yang konstan di lingkungan terdekat, yang cukup untuk meningkatkan kemungkinan menavigasi teleporter dengan sukses.
gen balok memiliki bidang variabel 2 bit.
Untuk tanda tangan lokal teleporter yang diberikan, ada satu kesempatan dalam empat bahwa sel balok akan dianggap tidak bisa dilewati. Setiap nilai bidang memilih satu dari empat kemungkinan ini.
Akibatnya, mutasi gen berkas pada 2 bit ini akan berputar melalui 4 kemungkinan signifikansi kontekstual dari warna.
Selain itu, warna yang paling penting untuk ditebak adalah dinding dan jebakan. Ini berarti kita harus mengizinkan deteksi teleporter hanya setelah tikus mengetahui di mana dinding dan jebakan berada.
Ini dilakukan dengan memperbarui tanda tangan lokal hanya sesekali. Kriteria saat ini untuk memperbarui tanda tangan lokal adalah berada di dekat warna yang diidentifikasi sebagai teleporter potensial.
Pengkodean menggunakan 5 bit per gen warna dan tipe grup untuk membebaskan 3 bit yang kurang signifikan untuk mengkodekan nilai 0,7:
Setiap gen balok memiliki 1/4 peluang untuk dianggap sebagai blok dan 3/4 peluang dianggap kosong, sehingga 4 balok mewakili rata-rata 1 blok dan 3 kosong.
Proporsi rata-rata yang diwakili oleh sebaran acak 16 warna adalah sebagai berikut:
Campuran ini tampaknya memberikan hasil terbaik sejauh ini, tetapi saya belum selesai mengubah-ubahnya.
Mutabilitas gen
Satu hal yang pasti: nilai kode yang dipilih untuk mewakili jenis gen sangat penting. Membalikkan dua nilai dapat menelan biaya 2000 poin atau lebih.
Sekali lagi di sini alasan mengapa di luar matematika saya.
Dugaan saya adalah bahwa probabilitas mutasi dari satu jenis ke yang lain harus seimbang, atau yang lain, seperti dalam matriks Markow, probabilitas kumulatif cenderung membatasi nilai pada subset yang memiliki probabilitas transisi masuk tertinggi.
Menuju penyelamatan
Pathing akan mengurangi jumlah sel yang dikunjungi secara dramatis, memungkinkan untuk menguji hanya yang paling mungkin mengarah ke tujuan. Dengan demikian, tidak hanya jalan buntu yang sering dihindari, tetapi kode warna yang salah juga jauh lebih mungkin ditemukan sebelumnya.
Akibatnya, waktu konvergensi sangat menurun.
Namun, ini tidak membantu menyelesaikan peta di mana genom tidak dapat menghasilkan representasi trek yang tepat.
Apa yang harus dilakukan dengan orang bodoh?
Setelah melihat secara visual di trek, saya mengerti mengapa strategi default yang mencoba untuk bergerak maju bahkan ketika tampaknya tidak ada apa-apa selain dinding di depan memang lebih baik daripada menahan.
"Dinding" sebenarnya bisa menjadi teleporter yang menghasilkan begitu banyak hasil yang tidak menguntungkan sehingga genom memetakannya sebagai hambatan yang tidak pernah dapat diinjak, tetapi pada kesempatan yang jarang terjadi, teleporter nakal ini dapat memiliki efek positif (atau setidaknya tidak mematikan). , jadi mengambil alih-alih kembali meningkatkan kemungkinan menemukan jalan menuju kemenangan.
Konvergensi awal
Menurut saya tingkat mutasi agak sedikit terlalu rendah (setidaknya untuk tikus saya).
Pengaturan 0,01 saat ini memberikan DNA 37% peluang untuk selamat dari proses mutasi secara utuh. Mengubah parameter menjadi 0,0227 menurunkan probabilitas ini menjadi sekitar 10%
Saya menjalankan kembali tes yang sama persis (menggunakan urutan tetap biji acak) dengan probabilitas 10%.
Pada banyak peta, kegagalan sebelumnya berubah menjadi keberhasilan (terbatas). Di sisi lain, ledakan populasi yang besar lebih sedikit (yang memiliki efek samping yang menarik untuk mempercepat komputasi).
Meskipun skor yang sangat tinggi (satu juta +) kurang umum, jumlah lari yang lebih sukses lebih dari cukup untuk mengimbangi.
Pada akhirnya, rata-rata naik dari 1400+ menjadi sekitar 2000.
Pengaturan P hingga 5%, sebaliknya, menghasilkan rata-rata sekitar 600.
Saya berasumsi tingkat mutasi begitu tinggi sehingga genom tikus yang menang terlalu sering berpindah ke varian yang kurang efisien.
Bagaimana cara kerjanya?
Dengan detektor teleporter yang ditambahkan, jumlah game yang gagal (skor <10) turun secara signifikan.
Pada uji coba 2000 berjalan, hanya ada 1/3 kegagalan.
Rata-rata geometrik hanya naik dari 2900 menjadi 3300, tetapi angka ini gagal mencerminkan peningkatan.
Warna kosong sering ditebak sebagai balok dan bahaya (biasanya 2 hingga 5). Genom "menggunakan" warna-warna ini untuk memblokir jalur yang akan membuat tikus kesulitan.
Genom cukup bagus dalam menebak perangkap (yaitu begitu tikus menjadi mampu mencapai tujuan, warna yang mewakili detektor perangkap aktual ditebak sekitar 90% dari waktu).
Itu juga memanfaatkan kode balok baru untuk para teleporter, meskipun lebih jarang (mungkin karena teleporter "berbahaya" lebih jarang daripada perangkap, dan warna balok / bahaya lainnya berevolusi untuk memblokir jalan ke contoh terakhir dari pengkhianat ini).
Menilai dari jumlah permainan di mana genom pemenang muncul setelah 5.000 putaran atau lebih, saya rasa jenis baru ini akan mendapat banyak manfaat dari peningkatan tingkat mutasi.
sumber
ColorScorePlayer, skor awal ≈ 22
Ini adalah bot yang Anda lihat bekerja di GIF dalam tantangan.
Ini adalah bot pengujian kami sepanjang fase pengembangan. Ini menggunakan genom untuk menyimpan skor kualitas untuk masing-masing 16 warna. Kemudian itu membuat langkah maju yang memindahkannya ke warna dengan skor terbaik (dan tidak pernah bergerak ke
-1
). Dalam kasus dasi, suatu gerakan acak antara sel-sel yang mengikat diambil.Kami telah mem-porting pemutar ini ke semua bahasa pengontrol, jadi ini berfungsi sebagai contoh cara menggunakannya:
Python
Rubi
C ++
C #
Jawa
Skor pemain tidak konsisten. Berikut adalah 50 putaran acak:
sumber
ColorFarSeeker, C ++ ≈ 74,7
Tantangan ini benar-benar sangat menyenangkan dan sederhana jika Anda mencobanya.
Jangan tertunda oleh deskripsi panjang.
Cukup kunjungi GitHub dan periksa semuanya ... semuanya akan jauh lebih jelas! :)
Simulator C ++ sangat disarankan untuk kecepatannya. Bahkan setelah saya selesai menerjemahkan program python saya ke C ++, simulasi python masih belum berhenti.
Ini adalah varian yang disempurnakan dari ColorScorePlayer. Untuk memanfaatkan tampilan 5x5 dengan baik, ia mempertimbangkan langkah 2 langkah dari itu menggunakan fungsi tertimbang. Bergerak 1 langkah di depan itu diberi bobot lebih tinggi, karena mereka memiliki efek langsung lebih banyak pada kelangsungan hidup. Bergerak 2 langkah ke depan diberi bobot lebih rendah.
Berusaha untuk bergerak maju, tetapi jika tidak ada langkah aman yang terlihat ... kemudian mencoba ke samping ... dan jika semuanya gagal, bergerak mundur secara acak.
Skor:
Ada sedikit 1 ... yang bisa sedikit menyedihkan ketika Anda melihat konsol memuntahkan 1 setelah satu sama lain. Seperti sebuah planet dengan semua kebutuhan untuk kehidupan, tetapi tidak ada tanda-tanda peradaban tikus maju ...
Lalu lonjakan sesekali. :)
Hmm ... rupanya saya beruntung untuk batch pertama saya berjalan, mendapatkan geometrik 300+. Skor benar-benar berfluktuasi sedikit. Tapi bagaimanapun, dengan lebih banyak menjalankan simulator, itu mungkin lebih dekat ke ≈ 74. (Thx feersum untuk membantu saya mensimulasikan dan programnya yang sangat cepat)
sumber
Uskup - Python, skor awal 1,901
Uskup selalu bergerak secara diagonal sehingga setengah papan tidak dapat diakses pada perjalanan yang diberikan melintasi papan, tetapi ini berarti lebih sedikit potensi gerakan untuk disandikan, sehingga setiap bit genom dapat mewakili gerakan (Uskup tidak pernah mundur). Bit yang mana untuk merujuk ditentukan berdasarkan blok 3x3 kotak di depan (di sebelah kanan) spesimen. Langkah terbaik untuk situasi tertentu hanya dengan sedikit mutasi saja.
Bot ini awalnya belajar dengan cepat, tetapi kemudian sering mengenai langit-langit sebelum mencapai finish, mungkin di mana salah satu dari dua masalah berikut terjadi:
Kode
Terlepas dari keterbatasan ini, pada kesempatan langka Uskup melakukannya dengan baik, dengan masing-masing spesimen menyelesaikan beberapa putaran papan. Saya berpikir bahwa pada pangkuan tertentu spesimen hanya dapat bergerak di setengah papan (setara dengan hanya kotak hitam atau hanya kotak putih di papan catur). Namun, seperti yang ditunjukkan Martin Büttner, seorang teleporter dapat memindahkan spesimen dari kotak hitam ke kotak putih atau sebaliknya sehingga pada kebanyakan papan mereka tidak akan dibatasi.
(Ada dua pasang tipe teleporter yang cocok dan masing-masing memiliki probabilitas 0,5 untuk memiliki offset yang memindahkan spesimen ke bagian lain dari kotak hitam dan putih. Jadi probabilitas papan memiliki teleporter yang membatasi spesimen hanya pada satu setengah dari papan per putaran hanya 0,25.)
Skor menunjukkan bahwa kemenangan sesekali diselingi dengan periode panjang gagal mencapai finish:
sumber
Run-bonus player: Rata-rata geometri 50,35 (uji 5000-game)
Bot ini mencetak kuadrat berdasarkan warna masing-masing berdasarkan bagian 6-bit dari DNA seperti pemain skor warna, tetapi dengan sistem angka yang berbeda. Bot ini dimotivasi oleh pemikiran bahwa agak sewenang-wenang bahwa salah satu bit mengubah nilai skor dengan 32, sementara yang lain melakukannya dengan hanya 1. Ini menetapkan nilai n (n + 1) / 2 untuk menjalankan n berturut-turut 1 bit. Selain itu, ia menambahkan mekanisme pengacakan dalam upaya untuk menghindari macet. Ini akan membuat langkah maju acak dengan peluang 1 banding 30.
Sebagai perbandingan, pemain skor warna mencetak 30 hingga 35 dalam beberapa tes 1000 pertandingan. Menariknya, skor permainan maksimum pemain warna-skor berada di kisaran 3-5 juta, sementara maksimum run-bonus hanya 200 ribu. Jalankan-bonus manfaat dari sistem penilaian rata-rata logaritmik dengan mendapatkan skor bukan nol lebih konsisten.
Menjalankan 5000 game membutuhkan waktu sekitar 20 menit dengan 6 utas pada pengontrol C ++.
sumber
StarPlayer | C ++ | Nilai: 162 (berdasarkan 500 game run)
Pemain ini mencoba menggunakan A * untuk menemukan jalan maju terbaik. Itu memberi bobot dengan cara yang sama seperti ColorScorePlayer dan mencoba untuk menemukan jalannya ke tepi kanan tampilan. Implementasinya bukan yang tercantik yang pernah saya lakukan tetapi setidaknya tidak terlalu lambat.
Skor sampel:
sumber
WallGuesser - Mencetak 113.266 dalam tes 1000 pertandingan
Pengkodean
Saya membuat penyandian 6 bit / warna yang sangat sederhana. Untuk memecahkan kode warna [n]
Dengan menyebarkan bit untuk warna di seluruh genom saya meningkatkan kemungkinan bit dari kedua orang tua akan digunakan untuk setiap warna.
Gerakan
Saya menggunakan (saya yakin tidak sangat efisien) pencarian berbasis * untuk mencari jalur biaya terendah ke salah satu kotak tepi kanan. Jika warna memetakan ke, "diblokir", maka itu tidak akan pernah dimasukkan oleh pencarian. Jika pencarian tidak dapat menemukan jalan, ia menganggap bahwa tikus ini tidak cocok untuk direproduksi dan mencoba untuk mengakhirinya dengan memindahkan satu ke kiri.
Mengurangi jumlah tikus yang tidak layak
Karena genom saya secara efektif menebak kotak mana yang merupakan tikus teleporter dinding atau mundur yang tidak memiliki tebakan (tidak ada warna yang dipetakan untuk diblokir) tidak terlalu cocok. Untuk mencoba dan menghapus tikus-tikus ini jika tidak ada warna yang ditandai sebagai diblokir maka SETIAP warna ditandai sebagai diblokir dan tikus akan selalu bergerak satu ke kiri.
MELAKUKAN
Saat ini tidak ada keacakan dalam perilaku sehingga mudah bagi tikus untuk terjebak.
sumber
g++ -std=c++11 .\wallguesser.cpp -O2 -o .\wallguesser.exe
. Saya mendapatkan banyak kesalahan tetapi yang pertama adalah.\wallguesser.cpp:47:19: error: 'dna_t' has no member named 'at' if (d.at(i) == true){
at
untuk[]
memperbaikinya.The FITTEST - Skor rata-rata geometris: ~ 922 (2K berjalan)
Pendekatan saya adalah:
Saya menguji lebih dari 2000 set parameter dengan 50 biji yang sama. Set yang paling menjanjikan dipilih dan diberi skor menggunakan 250 biji identik dan yang dengan peringkat tertinggi adalah input untuk putaran tes berikutnya. Jadi saya berhasil membuat algoritma genetika untuk menemukan algoritma genetika yang optimal untuk masalah ini seperti yang disarankan oleh pengguna mbomb007 .
Perilaku yang diinginkan:
Metode penyimpanan data:
Kami ingin spesies mempelajari hal-hal, beradaptasi dengan lingkungannya, menjadi yang paling cocok. Tidak dapat dihindari ini hanya bekerja, jika pembelajaran dapat disimpan entah bagaimana. Pembelajaran akan 'disimpan' dalam 100 bit DNA. Ini adalah cara penyimpanan yang aneh, karena kita tidak dapat mengubah nilai DNA kita. Jadi kami berasumsi bahwa DNA sudah menyimpan informasi gerakan yang buruk dan baik. Jika untuk spesies tertentu informasi yang benar disimpan dalam DNA-nya ia akan bergerak maju dan menghasilkan banyak spesies baru dengan DNA-nya.
Saya menemukan skor rata-rata geometris sensitif terhadap bagaimana informasi disimpan. Mari kita asumsikan kita membaca 4 bit pertama dari 100 bit DNA dan ingin menyimpan ini dalam variabel integer. Kita dapat melakukan ini dalam beberapa cara:
dnarange
, contoh: 4bits1011
akan menjadi `1x2 ^ 3 + 0x2 ^ 2 + 1x2 ^ 1 + 1x2 ^ 0 = 15. Nilai yang mungkin (untuk 4 bit): [0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]dnaStreakRange
fungsi (didefinisikan di bawah), contoh: 4bits 1011 akan menjadi1x1 + 0x1 + 1x1+ 1x2 = 4
. Nilai yang mungkin (untuk 4 bit): [0, 1, 2, 3, 6, 10]dnaCountRange
fungsi (didefinisikan di bawah), contoh: 4bits 1011 akan menjadi1x1 + 0x1 + 1x1 + 1x1 = 3
. Nilai yang mungkin (untuk 4 bit): [0, 1, 2, 3, 4]Perbedaan antara metode penyimpanan adalah:
Prioritaskan solusi.
Ketika ColorScorePlayer telah mengidentifikasi dua gerakan maju dengan skor yang identik, pilihan sewenang-wenang dibuat. IMHO, Anda tidak boleh menggunakan fungsi
v.rng.rint()
fungsi acak . Alih-alih, Anda harus menggunakan kesempatan ini dengan skor yang sama sebagai pengait untuk mengevaluasi solusi untuk efek urutan kedua.Efek urutan pertama mendapatkan prioritas tertinggi. Jika skor yang sama tercapai, solusi dengan prioritas 2 menang dan seterusnya. Dengan mengubah parameter solusi, Anda dapat memengaruhi peluang terjadinya skor yang sama dan dengan demikian mengubah bobot prioritas 1 dan prioritas 2.
Implementasi perilaku yang diinginkan
Pelajari warna mana yang aman:
threshold = 63/3=21
, di mana 63 adalah skor maksimum untuk 6 bit dan 33% = 1/3 (dapat dilihat pada grafik di atas).Jika tidak ada gerakan bagus yang tersedia, gerakkan vertikal atau mundur:
weightMove
variabel.Lihat apa yang ada di luar:
x2
dany2
loop) apa pilihan terbaik (melaluimainSubScore
variabel). Kolom paling kanan di kotak 3x3 itu memimpin.Identifikasi jebakan:
Saya memeriksa DNA spesies dengan skor tertinggi ketika permainan arbitrer berakhir menggunakan penyimpanan bitsum4 (jadi skor warna memiliki rentang [0,4]):
Dari sini dapat disimpulkan bahwa dinding dan bank mendapatkan skor yang benar. Jebakan tidak diidentifikasi karena tergantung pada arah dan warna asal, sedangkan penilaian dilakukan pada warna tujuan. Oleh karena itu ada kebutuhan untuk juga menyimpan data pada warna asal, jadi
v(0,0)
. Dalam dunia ideal kami ingin menyimpan informasi untuk 16 warna x 8 arah x 3 bit = 384 bit.Sayangnya, hanya ada 100 bit yang tersedia dan kami tidak dapat menggunakannya semuanya karena kami juga membutuhkan beberapa memori untuk solusi yang dijelaskan di atas. Karena itu kami akan membuat 4 tempat sampah warna:
dan 4 tempat sampah arah bergerak
Ketika skor desimal adalah 4 atau lebih tinggi (100.101.110.111), diasumsikan jebakan dikaitkan dengan sel ini, akibatnya gerakan ini tidak akan dipilih ketika skor yang sama muncul. Jadi identifikasi perangkap adalah efek urutan kedua dan 'lihat apa yang ada di luar' akan menjadi solusi prioritas ketiga.
Asumsi yang salah tentang dinding digandakan berkali-kali menjadi bayi baru lahir oleh orang bodoh:
Beberapa spesies salah berasumsi bahwa dinding itu bagus dan mencoba untuk bergerak sepanjang waktu sehingga terhambat di depan dinding. Mereka juga bisa terjebak dalam loop teleporter yang tak terbatas. Efeknya sama dalam kedua kasus.
Masalah utama adalah bahwa setelah beberapa ratus iterasi beberapa gen menjadi sangat dominan . Jika ini adalah gen 'kanan', Anda bisa mendapatkan skor sangat tinggi (> 1 juta poin). Jika ini salah, Anda mandek, karena Anda perlu keanekaragaman untuk menemukan gen yang 'tepat'.
Pertarungan orang bodoh: Solusi 1: pembalikan warna
Solusi pertama yang saya coba adalah upaya untuk memanfaatkan bagian dari memori yang tidak terpakai yang masih sangat beragam. Mari kita asumsikan Anda telah mengalokasikan 84 bit ke memori warna Anda dan menjebak memori temuan. 16 bit yang tersisa akan sangat beragam. Kita dapat mengisi 2 variabel desimal8 yang memiliki nilai pada interval [0,255] dan mereka homogen, yang berarti bahwa setiap nilai memiliki peluang 1/256. Variabel akan dipanggil
inInverse
daninReverse
.Jika
inInverse
sama dengan 255 (peluang 1/256), maka kami akan membalikkan interpretasi skor warna . Jadi tembok yang dianggap tolol aman karena skornya tinggi, akan mendapat skor rendah dan karenanya akan menjadi langkah buruk. Kerugiannya adalah ini juga akan memengaruhi gen 'hak', jadi skor kita akan sangat rendah. Lebih jauh lagi,inInverse
spesies ini harus mereproduksi dirinya sendiri dan anak-anaknya juga akan mendapatkan bagian dari DNA dominan. Bagian terpenting adalah mengembalikan keragaman.Jika
inReverse
sama dengan 255 (peluang 1/256), maka kami akan membalik urutan posisi penyimpanan skor warna . Jadi sebelum warna 0 disimpan dalam bit 0-3. Sekarang warna 15 akan disimpan di posisi itu. Perbedaannya denganinInverse
pendekatan adalah bahwainReverse
kehendak membatalkan pekerjaan yang dilakukan sejauh ini. Kami kembali di titik awal. Kami telah menciptakan spesies yang memiliki gen yang sama seperti ketika permainan dimulai (kecuali untuk memori jebakan)Melalui pengoptimalan, ini diuji jika bijaksana untuk menggunakan
inInverse
daninReverse
pada saat yang sama. Setelah optimisasi disimpulkan skornya tidak meningkat. Masalahnya adalah kita memiliki populasi gen yang lebih beragam, tetapi ini juga mempengaruhi 'DNA yang tepat'. Kami membutuhkan solusi lain.Pertarungan orang bodoh: Solusi 2: kode hash
Spesies memiliki 15 posisi awal yang memungkinkan dan saat ini ada kemungkinan terlalu besar ia akan mengikuti jalur yang sama persis jika ia mulai pada posisi awal yang sama. Jika dia adalah orang bodoh yang mencintai dinding, dia akan terjebak di dinding yang sama berulang-ulang. Jika dia berhasil mencapai dinding yang jauh di depan, dia akan mulai mendominasi kumpulan DNA dengan asumsi yang salah. Yang kita butuhkan adalah bahwa keturunannya akan mengikuti jalan yang sedikit berbeda (karena baginya bagaimanapun juga sudah terlambat), dan tidak akan terjebak di dinding yang jauh di depan, tetapi di tembok yang lebih dekat . Ini dapat dicapai dengan memperkenalkan kode hash .
Sebuah kode hash harus memiliki maksud untuk mengidentifikasi dan label posisi saat di papan unik. Tujuannya bukan untuk mencari tahu apa posisi (x, y) itu, tetapi untuk menjawab pertanyaan apakah leluhur saya pernah berada di lokasi ini?
Mari kita asumsikan Anda akan memiliki papan lengkap di depan Anda dan Anda akan membuat jpg dari masing-masing sel 5 dengan 5 sel mungkin. Anda akan berakhir dengan (53-5) x (15-5) = 380 gambar. Mari kita berikan angka-angka gambar dari 1 hingga 380. Kode hash kita harus dilihat sebagai ID seperti itu, dengan perbedaan yang tidak berjalan dari 1 hingga 330, tetapi memiliki IDS yang hilang, jadi mis. 563, 3424, 9424, 21245, dll.
Bilangan prima
17
dan31
ada di sana untuk mencegah informasi yang ditambahkan di awal dalam loop menghilang. Nanti lebih lanjut tentang cara mengintegrasikan kode hash kami ke dalam sisa program.Mari kita ganti mekanisme subscoring "lihat apa yang ada di luar" dengan mekanisme subscoring lain. Ketika dua atau tiga sel memiliki skor utama yang sama akan ada peluang 50% yang teratas akan diambil, peluang 50% bahwa sel-sel bawah diambil dan peluang 0% bahwa sel tengah akan diambil. Kesempatan tidak akan ditentukan oleh generator acak, tetapi oleh bit dari memori , karena dengan cara itu kami memastikan bahwa dalam situasi yang sama pilihan yang sama dibuat.
Dalam dunia ideal (di mana kita memiliki jumlah memori tak terbatas), kita akan menghitung kode hash unik untuk situasi kita saat ini, misalnya 25881, dan pergi ke lokasi memori 25881 dan membaca di sana jika kita harus memilih sel atas atau bawah (ketika ada adalah skor yang sama). Dengan cara itu kita akan berada dalam situasi yang sama persis (ketika kita mis bepergian ke papan untuk kedua kalinya dan mulai pada posisi yang sama) membuat keputusan yang sama. Karena kita tidak memiliki memori tak terbatas, kita akan menerapkan modulo ukuran memori yang tersedia ke kode hash . Kode hash saat ini baik dalam arti bahwa distribusi setelah operasi modulo adalah homogen.
Ketika keturunan melakukan perjalanan papan yang sama dengan DNA sedikit berubah dia dalam banyak kasus (> 99%) akan membuat keputusan yang persis sama. Tetapi semakin jauh dia datang, semakin besar peluangnya untuk menjadi jalan yang dipilihnya berbeda dari leluhurnya. Jadi kemungkinan dia akan terjebak di dinding yang jauh di depan ini kecil. Walaupun terjebak di dinding yang sama dengan leluhurnya relatif besar, tetapi ini tidak terlalu buruk, karena ia tidak akan menghasilkan banyak keturunan. Tanpa pendekatan kode hash , kemungkinan terjebak di dinding terdekat dan jauh hampir sama
Optimasi
Setelah optimasi, disimpulkan bahwa tabel identifikasi perangkap tidak diperlukan dan 2 bit per warna sudah cukup. Sisa memori 100-2x16 = 68 bit digunakan untuk menyimpan kode hash. Tampaknya mekanisme kode hash dapat menghindari jebakan.
Saya telah mengoptimalkan 15 parameter. Kode ini termasuk set parameter tweak terbaik (sejauh ini):
Ini adalah program C ++ pertama saya. Saya memiliki sebagian besar dari Anda sekarang latar belakang dalam analisis gnome. Saya ingin mengucapkan terima kasih kepada panitia, karena saya sangat menikmati mengerjakan ini.
Jika Anda memiliki umpan balik, silakan tinggalkan komentar di bawah ini. Permintaan maaf untuk teks yang panjang.
sumber
Pathfinder, C ++, skor awal 35.8504 (50 putaran)
Perombakan total! Saya memindahkan algoritma saya ke C ++ dan mengubahnya sedikit, tetapi nilainya masih tidak terlalu tinggi, mungkin karena tikus terus membenturkan kepalanya ke dinding. Saya lelah mencoba untuk memperbaiki ini, jadi saya akan membiarkannya untuk saat ini.
Penjelasan
Gagasan umum adalah untuk mengklasifikasikan setiap warna sebagai jebakan atau tidak, kemudian menetapkan arah ke jebakan dan bobot untuk non-jebakan, dan mencoba mengikuti jalur bobot minimum ke batas kanan kisi visi.
Dalam 80 bit pertama genom, setiap warna diklasifikasikan menggunakan 5 bit
abcde
. Jikaab = 01
, warnanya adalah jebakan, dancde
mengkodekan arahnya (delapan kemungkinan). Jikaab ≠ 01
, warnanya bukan jebakan, dan beratnya adalaha + b + 2*(c + d + e)
.Selanjutnya, kita menginisialisasi kotak 3x7, yang mewakili bidang penglihatan tikus di sebelah kanannya, diisi dengan warna "tidak dikenal". Bit 80-84 mengkodekan berat sel yang tidak diketahui mirip dengan warna non-trap, dan bit 85-89 mengkodekan berat umum untuk perangkap. Kami mengisi kisi-kisi dengan bobot, menghitung jalur terpendek, dan menambahkan beberapa bobot ekstra (dikodekan dalam bit 90-95) ke sel-sel yang berada langsung di atas dan di bawah tikus untuk mencegah gerakan menghindar. Bit 95-99 mengkodekan berat tujuan. Jika berat minimum jalan di bawahnya, tikus mungkin terjebak di suatu tempat, dan mulai bergerak secara acak (tetapi tidak pernah mundur). Jika tidak, itu mengikuti jalur berat minimum. Dengan probabilitas kecil tergantung pada berat yang mencegah sidestep, tikus memilih jalur berat kedua hingga minimum sebagai gantinya. Ini untuk mencegah macet di dinding (tapi sepertinya tidak berfungsi dengan baik sekarang).
sumber
LookAheadPlayer C ++ ≈ 89.904
Pikiran awal saya adalah mencari 4 bit yang cocok dengan warna yang saya cari, dan menggunakan beberapa bit berikut sebagai skor. Ini ternyata merupakan ide yang mengerikan, kemungkinan karena mutasi.
Jadi saya berpikir tentang cara-cara melindungi terhadap mutasi dan crossover, dan itu mengingatkan saya pada pekerjaan yang telah saya lakukan pada decoding kode QR. Dalam kode QR, data dipecah menjadi blok dan bergaris untuk menghindari kesalahan karena merusak terlalu banyak bagian data yang diberikan.
Karena itu, seperti ColorScorePlayer, saya memotong DNA menjadi 16 bagian dan menggunakannya sebagai skor yang diberikan. Namun, skor bergaris sehingga bit individual dari setiap skor tidak berbatasan. Saya kemudian menjumlahkan skor dari kedua kemungkinan gerakan saat ini dan potensi pergerakan selanjutnya dan memilih langkah terbaik untuk dilakukan.
Catatan: ini diberi kode / diuji pada MinGW. Itu tidak akan dikompilasi dengan optimisasi, atau dengan multithreading. Saya tidak memiliki instalasi Linux atau Visual Studio yang praktis untuk menggunakan kompiler di mana ini akan bekerja. Saya akan mengujinya cepat besok pagi, tapi tolong beri tahu saya jika Anda mengalami masalah.
sumber
SlowAndSteady C ++ (skor 9.7)
Kita tidak dapat bergantung pada menafsirkan potongan genom sebagai angka karena bit-flip tunggal dapat memiliki efek yang sangat berbeda tergantung pada posisinya. Itulah mengapa saya hanya menggunakan 16 segmen 6-bit dan memberi skor pada jumlah
1
s. Awalnya111111
adalah baik dan000000
buruk, dan sementara itu tidak masalah dalam jangka panjang (setelah genom sepenuhnya berkembang) dalam konfigurasi awal dari DNA sebagian besar segmen memiliki 2-4 yang, jadi saya beralih menggunakan9 - (#1 - 3)^2
untuk penilaian, ini memungkinkan lebih banyak kebebasan bergerak di putaran pertama dan evolusi yang lebih cepat.Saat ini saya hanya melihat 7 tetangga terdekat, menambahkan bias arah ke skor warna dan bergerak di salah satu arah tertinggi secara acak.
Meskipun skornya sendiri tidak terlalu tinggi, makhluk saya mencapai garis finish dan skor> 1 dalam 3/4 kasus.
Dan sampel mencetak 100 papan
Skor rata-rata geometri: 9,76557
sumber
WeightChooser | C # | Skor: 220,8262 dalam 1520 Game
Menghitung berat untuk gerakan selanjutnya yang mungkin (biru) berdasarkan pada berat rata-rata dari gerakan yang mungkin diikuti (kuning)
sumber
RATS IN ACTION (bukan jawaban, tetapi alat grafis untuk bot C ++)
Sejak awal tantangan ini, saya mengalami kesulitan mencari tahu apa yang sebenarnya dihadapi tikus di lintasan.
Pada akhirnya saya meretas controller dan menulis alat samping untuk mendapatkan beberapa representasi grafis dari sebuah lagu.
Saya akhirnya melakukan beberapa peretasan lagi dan menambahkan visualisasi tentang kemungkinan jalur DNA tikus yang diberikan.
Peta ini sangat berantakan dan membutuhkan sedikit pembiasaan, tetapi saya merasa cukup membantu untuk memahami bagaimana bot saya bekerja.
Berikut ini sebuah contoh:
Anda mungkin perlu memperbesar untuk melihat sesuatu, jadi inilah babak pertama:
Pada awalnya, mari kita lihat jalur tikus. Ada satu jalur untuk setiap lokasi awal yang mungkin (biasanya 15, kadang-kadang sedikit kurang). Biasanya mereka cenderung bergabung, idealnya mengarah ke lokasi kemenangan tunggal.
Jalan diwakili oleh panah lurus besar. Warna menggambarkan hasil:
Dalam contoh ini, kami memiliki 12 posisi awal yang menang, satu mengarah ke loop tak terbatas dan dua menuju kematian yang melelahkan (diteleportasikan ke dalam perangkap, seperti yang terlihat).
Diskontinuitas jalur disebabkan oleh teleportasi, yang dapat Anda ikuti dengan panah melengkung yang sesuai.
Sekarang untuk simbol berwarna. Mereka mewakili makna 16 warna (yang abu-abu mewakili apa yang dilihat tikus).
warna kosong adalah ... baik ... kosong.
Teleporter memiliki panah keluar yang menunjuk ke tujuan mereka.
Detektor perangkap juga memiliki panah yang menunjukkan perangkap, yang dianggap sebagai lingkaran merah.
Dalam satu kasus dari 9, perangkap terletak di sel yang sama dengan detektornya, di mana Anda akan melihat octogon kecil di atas lingkaran merah.
Ini adalah kasus perangkap kuning pucat dalam contoh ini.
Anda juga dapat melihat detektor perangkap ungu muda menunjuk ke perangkap yang ditunjukkan.
Perhatikan bahwa terkadang lingkaran merah jebakan akan disembunyikan di bawah dinding. Keduanya mematikan sehingga hasilnya sama dalam hal teleportasi.
Perhatikan juga bahwa sebuah jebakan mungkin terletak pada seorang teleporter, dalam hal mana teleporter didahulukan (yaitu tikus diteleportasi sebelum jatuh ke dalam jebakan, pada dasarnya menetralkan jebakan).
Terakhir, simbol abu-abu mewakili apa yang dilihat tikus saya (yaitu makna genomnya dikaitkan dengan warna).
Pada dasarnya, semua sel yang duduk di persegi abu-abu dianggap sebagai dinding oleh tikus.
Big X mewakili sel yang dianggap sebagai perangkap, dengan octogon yang sesuai menunjukkan detektor yang melaporkannya.
Dalam contoh ini, kedua dinding diidentifikasi seperti itu, seperti perangkap kuning pucat (menunjukkan memang sel yang mematikan, sehingga mewakili itu sebagai dinding sudah benar).
Detektor perangkap ungu muda telah diidentifikasi seperti itu (itu duduk di octogon abu-abu), tetapi lokasi perangkap tidak benar (Anda dapat melihat bahwa beberapa lingkaran merah tidak memiliki salib di bawahnya).
Dari 4 teleporter, 2 dianggap sebagai dinding (pirus dan tan), dan 2 sebagai sel kosong (kemerahan dan kekuningan).
Beberapa sel kosong dianggap sebagai detektor atau dinding perangkap. Melihat dari dekat, Anda dapat melihat bahwa "detektor rusak" ini memang melarang masuk ke dalam sel yang akan membuat tikus bermasalah, jadi meskipun mereka gagal mencocokkan warna asli, mereka memiliki tujuan yang pasti.
Kode
Yah itu berantakan, tapi itu bekerja dengan baik.
Dilihat dari kode pemain, saya hanya menambahkan satu antarmuka: fungsi jejak yang digunakan untuk melaporkan arti DNA yang diberikan. Dalam kasus saya, saya menggunakan 3 jenis (dinding, detektor perangkap dan kosong) tetapi pada dasarnya Anda dapat menampilkan apa pun yang berhubungan dengan warna (atau tidak sama sekali jika Anda tidak menginginkan grafis yang berhubungan dengan genom).
Saya meretas controller untuk menghasilkan string karakter besar yang menyusun deskripsi trek dan warna dengan "run kering" DNA tikus dari semua lokasi yang mungkin.
Ini berarti hasilnya akan benar-benar bermakna hanya jika bot tidak menggunakan nilai acak. Jika tidak, jalur yang ditampilkan hanya akan mewakili satu hasil yang mungkin.
Terakhir, semua jejak ini dimasukkan ke dalam file teks besar yang kemudian dibaca oleh utilitas PHP yang menghasilkan output grafis.
Dalam versi saat ini, saya mengambil snapshot setiap kali tikus mati setelah mencapai kebugaran maksimal baru (yang menunjukkan dengan cukup baik penyempurnaan progresif genom tanpa memerlukan terlalu banyak snapshot), dan snapshot akhir di akhir permainan (yang menunjukkan DNA yang paling berhasil).
Jika seseorang tertarik, saya dapat mempublikasikan kodenya.
Jelas ini hanya berfungsi untuk bot C ++, dan Anda harus menulis fungsi jejak dan mungkin memodifikasi kode PHP jika Anda ingin menampilkan beberapa data spesifik genom (angka abu-abu dalam kasus saya).
Bahkan tanpa informasi spesifik DNA, Anda dapat melihat jalur yang diikuti oleh DNA Anda pada peta tertentu dengan sedikit usaha.
Mengapa output antara?
Pertama-tama, C ++ tidak memiliki perpustakaan grafik portabel yang layak untuk dibicarakan, terutama ketika menggunakan MSVC. Bahkan jika Win32 membangun biasanya tersedia, mereka sering datang sebagai renungan, dan jumlah perpustakaan eksternal, paket dan basa-basi seperti unix lain yang diperlukan membuat menulis aplikasi grafis cepat dan sederhana menjadi rasa sakit yang mengerikan di bagian tubuh seseorang yang kesopanan mencegah saya dari penamaan.
Saya mempertimbangkan untuk menggunakan Qt (tentang satu-satunya lingkungan yang membuat GUI portable / pengembangan grafis dalam C ++ menjadi tugas yang sederhana dan bahkan menyenangkan, IMHO - mungkin karena ia menambahkan sistem pesan à la Objective C yang C ++ sangat kurang dan melakukan pekerjaan luar biasa membatasi memori manajemen seminimal mungkin), tetapi ini terlihat seperti kerja keras yang berlebihan untuk tugas yang ada (dan siapa pun yang ingin menggunakan kode harus menginstal SDK biggish - hampir tidak sepadan dengan usaha, saya kira).
Bahkan dengan asumsi perpustakaan portabel, tidak ada persyaratan kecepatan untuk berbicara tentang (satu detik atau lebih untuk menghasilkan gambar sebagian besar cukup), dan dengan kekakuan pepatah dan kekacauan yang melekat, C ++ tentu bukan alat terbaik untuk pekerjaan itu.
Selain itu, memiliki output teks menengah menambah banyak fleksibilitas. Setelah data ada, Anda dapat menggunakannya untuk tujuan lain (menganalisis kinerja bot, misalnya).
Kenapa PHP?
Saya menemukan bahasanya sangat sederhana dan mudah beradaptasi, sangat nyaman untuk prototyping. Saya menjadikannya bahasa hewan peliharaan saya untuk tantangan kode yang tidak memerlukan performa ekstrem.
Meskipun demikian, ini adalah bahasa yang mengerikan untuk bermain golf, tetapi golf tidak pernah menjadi cangkir teh saya.
Saya kira python atau Ruby akan sama menyenangkan untuk digunakan untuk tujuan yang sama, tetapi saya tidak pernah memiliki kesempatan untuk melakukan beberapa pekerjaan serius dengan mereka, dan saya bekerja di situs web belakangan ini, jadi PHP itu.
Bahkan jika Anda tidak tahu bahasa, tidak boleh terlalu sulit untuk memodifikasi kode yang sesuai dengan kebutuhan Anda. Hanya saja, jangan lupakan
$
s sebelum variabel, sama seperti hari-hari dasar yang baik :).sumber
SkyWalker - Python - skor kurang dari 231 dalam 50 pertandingan
Jadi kode dulu dan kemudian beberapa penjelasan. Saya harap tidak ada yang rusak saat menyalin.
Beberapa Penjelasan
Menurut pendapat saya perbedaan utama adalah bahwa saya tidak kode setiap warna. Sebagai gantinya, saya mencoba menyimpan jumlah warna yang penting. Menurut saya warna-warna itu adalah jebakan, dinding, dan teleporter. Spesimen tidak perlu tahu warna sel yang baik. Oleh karena itu, genom saya terstruktur dengan cara berikut.
Ini membuat total 52 bit digunakan. Namun, saya hanya menggunakan bit pertama dari 3 decoder teleporter (saya memeriksa apakah jumlahnya lebih besar 3). Oleh karena itu, 2 lainnya dapat dihapus, meninggalkan saya di 44 bit yang digunakan.
Pada setiap belokan, saya memeriksa setiap bidang visi saya apakah itu salah satu warna buruk (+ bagian luar papan -1) dan menambahkannya ke daftar bidang yang tidak ingin dipindahkan spesimennya. Dalam kasus jebakan, saya menambahkan bidang yang ada pada offset yang disimpan untuk warna jebakan itu.
Berdasarkan daftar bidang buruk itu langkah selanjutnya dihitung. Urutan bidang yang disukai adalah:
Jika dua bidang kategori berlaku, satu dipilih secara acak.
Hasil
Pikiran
Saya tidak tahu, apakah saya beruntung dengan 50 berjalan atau jika sebenarnya ada beberapa kebijaksanaan dalam strategi saya.
Lari saya sepertinya tidak pernah lepas landas dan mendapatkan skor super tinggi tetapi mereka juga cenderung menemukan setidaknya beberapa kali tujuannya
Beberapa keacakan kecil baik untuk tidak terjebak dalam perangkap di suatu tempat yang dekat dengan akhir lomba
Saya pikir warna non-spesial tidak pernah buruk. Namun, contoh dari mereka bisa menjadi buruk, ketika mereka berada di offset perangkap. Dengan demikian, pelabelan warna buruk jika tidak menjebak, dinding atau teleporter buruk tidak masuk akal.
Tembok adalah musuh terbesar
Perbaikan
Pertama, meskipun saya akan kehilangan melihat kotak hitam semakin dekat dan lebih dekat ke tujuan port C ++ diperlukan untuk melakukan lebih banyak tes dan mendapatkan hasil yang lebih bermakna.
Salah satu masalah utama adalah bahwa jika ada sel-sel jahat (atau yang spesimennya anggap buruk) di depan tikus itu dengan mudah mulai bergerak naik dan turun dalam lingkaran. Ini bisa dihentikan atau dikurangi dengan melihat 2 bergerak maju dalam kasus-kasus itu dan mencegahnya pindah ke bidang di mana ia hanya akan bergerak kembali.
Seringkali dibutuhkan waktu hingga tikus dengan gen baik mencapai tujuan dan mulai menyebarkan gen. Mungkin saya perlu beberapa strategi untuk meningkatkan keragaman dalam kasus-kasus itu.
Karena teleporter sulit untuk dihitung, mungkin saya harus membagi populasi pada mereka yang berisiko dan selalu mengambil teleporter yang baik dan mereka yang lebih peduli dan hanya mengambilnya jika tidak ada pilihan lain.
Saya harus menggunakan bagian kedua genom saya.
sumber
self.bit_chunk(16, 4)
danself.bit_chunk(20, 4)
memiliki kedua nilai yang0010
Anda miliki, secara efektif hanya menyimpan info tentang salah satu dari dua jebakan.itervalues
menjadivalues
.Python, NeighborsOfNeighbors, Score = 259.84395 lebih dari 100 game
Ini adalah variasi pada ColorScorePlayer. Setiap 6 bit menyimpan skor kualitas untuk kuadrat. Ketika bot bergerak, skor masing-masing dari 3 kotak maju - diagonal ke atas, ke depan, dan diagonal ke bawah. Skornya adalah kualitas kotak ditambah setengah kualitas rata-rata dari 3 kotak berikutnya. Ini memberi bot beberapa pandangan ke depan, tanpa membebani kualitas kotak pertama. Algoritma ini mirip dengan LookAheadPlayer, yang tidak saya lihat sebelum menulis solusi ini.
sumber
else None
menjadielse 0
pada baris sebelumnya untuk menghitung skor Anda. Mudah-mudahan itu meninggalkan logika Anda tidak berubah (saya tidak membuat perubahan pada kode Anda di sini di SE selain menambahkan indentasi yang hilang).ROUS (Hewan Pengerat dari Ukuran Tidak Biasa), Jawa, Skor = 0
Ini hash lingkungan untuk memutuskan ke mana harus pergi.
Karena pengontrol Java tidak berfungsi saya tidak memiliki skor untuk ini. Ini hanya akan menjadi sangat jauh jika menemukan beberapa teleporter untuk membantunya.Ini cenderung punah dan crash controller sesekali. Ini mungkin disebabkan oleh fakta bahwa lingkungan alaminya adalah Rawa Api.sumber
Gray-Color Lookahead (C ++, ~ 1.35)
Yang ini rata-rata tidak bekerja dengan sangat baik, tetapi kadang-kadang jarang terjadi dengan sangat baik. Sayangnya, kami sedang dinilai pada rata-rata geometris (1,35), dan tidak pada skor maksimum (20077).
Algoritma ini bekerja dengan hanya menggunakan kode abu-abu 4-bit untuk memetakan skor setiap warna di suatu tempat dari -2 ke 2 (dengan bias terhadap kisaran [-1.1.1]), dan menghitung skor setiap ubin gerakan dan gerakan selanjutnya . Itu juga menggunakan kode abu-abu 2-bit untuk menentukan pengganda untuk ubin itu sendiri serta faktor biasing untuk bergerak ke kanan. (Kode abu-abu jauh lebih rentan terhadap lompatan besar karena mutasi, meskipun mereka tidak benar-benar melakukan bantuan untuk crossover mid-codepoint ...)
Itu juga sama sekali tidak mencoba menangani jebakan khusus, dan saya curiga itu mungkin kejatuhan (walaupun saya belum menambahkan instrumentasi apa pun ke controller untuk menguji teori ini).
Untuk setiap gerakan yang mungkin, ia menentukan skor, dan di antara semua gerakan dengan skor tertinggi yang dipilihnya secara acak.
Pada putaran terakhir saya, saya mendapat skor: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1
Saya berharap bisa mendapatkan lebih banyak dari 20077 dan lebih sedikit dari 1s. :)
sumber
C ++, TripleScore, Nilai: 100 ~ 400
Pertama-tama, skor saya sangat bervariasi selama beberapa kali (terutama karena jumlah 1).
Inti menghitung skor 5 arah: atas, bawah, maju-maju, maju dan maju-turun. Pertama skor naik dan turun dihitung, daripada hasilnya dibandingkan dengan nilai tinggal di tempat. Jika tetap di tempat lebih baik daripada bergerak ke atas atau ke bawah, arah ini tidak akan dipilih (jadi harus maju). Ini untuk mencegah memantul (naik, turun, naik, turun, ...) antara 2 titik.
Sekarang 3 arah lainnya diberi skor: maju-naik, lurus ke depan dan maju-turun. Dari semua arah yang diselidiki, yang dengan skor tertinggi disimpan dan 1 di antaranya dipilih secara acak.
Mencetak arah: TripleScore menghitung skor suatu gerakan menggunakan 3 subskala:
Seperti dengan jawaban lain, skor sangat tergantung pada jumlah 1-skor yang dikembalikan.
sumber
Ruby - ProbabilisticScorePlayer
Tikus yang sangat tidak deterministik ini menghitung probabilitas untuk pergi ke suatu tempat oleh lingkungannya. 16 slot pertama dalam genom mewakili 16 warna. 1 dalam slot berarti warnanya baik untuk diinjak, 0 berarti buruk. 16 berikutnya memegang yang sama untuk ruang di depan target Anda, dan seterusnya.
Keuntungan utama dari pendekatan probabilistik adalah bahwa hampir tidak mungkin terjebak di balik tembok terlalu lama. Kerugiannya adalah Anda hampir tidak akan pernah mendapatkan tikus yang hampir sempurna.
sumber
c
nilai awal? Tampaknya tidak ditentukan saat Anda menggunakannya di pertamaif
.coords
bukan daftar, Anda menggunakan&&
bukanand
dan lupa tanda kurung, dan bahkan setelah memperbaiki semua ini Anda tidak membatasi nilai RNG sehingga Anda mendapatkan arah kosong. Apakah ini pseudo-code, atau sesuatu yang dimaksudkan untuk dijalankan dengan semacam dialek Ruby?Java, RunningStar, Score = 1817.050970291959 lebih dari 1000 pertandingan
Bot ini menggunakan kode warna Run-Bonus dengan teknik StarPlayer .
Pembaruan: Memperbaiki pengontrol java.
sumber
LeapForward, Python 2
Tidak terlalu terobosan tapi itu adalah satu-satunya upaya saya yang dilakukan ok-ish.
Pada dasarnya, kode empat warna (masing-masing 4 bit) untuk menghindari, dalam genom. Kemudian maju ke warna yang tidak ada dalam daftar itu. Jika semua warna buruk, itu masih melompat ke depan ke yang tidak diketahui.
sumber
Java - IAmARobotPlayer - Skor 3.7
Saya baru saja membuat tikus robot ini untuk perbandingan dengan program lain (tidak terlalu menarik sejauh ini) yang saya buat. Skor keseluruhan tidak baik, tetapi jika skor di suatu tempat, itu akan mendapatkan banyak tikus melalui. Idenya adalah bahwa ia hanya akan melihat tiga sel di depannya, setiap sel baik atau buruk. Ini memberikan angka biner. Kemudian akan mencari nomor ini dalam genomnya, mengambil tiga bit berturut-turut, juga mengubahnya menjadi angka dan mengambil tindakan yang disimpan di bawah nomor ini. Jadi itu bertindak selalu sama ketika menghadapi situasi yang sama.
Hasil:
sumber
Cautious Specimens - C ++ - skor sekitar 2030 lebih dari 200 berjalan
Ini menggunakan bagian warna (16x4 bit) dari pengkodean DNA dari Buta Buta tetapi meninggalkan sisanya (36bit) dari DNA yang sama sekali tidak digunakan.
Pengkodean warna adalah:
Di mana X menunjukkan bit yang tidak digunakan. Mengingat bahwa hanya 2 dari 16 warna yang merupakan jebakan yang akan menggunakan semua 4 bitnya (dan hanya jika jebakan diimbangi, yang akan menjadi kasus 8-dari-9 kali) maka biasanya akan ada 64 bit yang tidak digunakan - teorinya adalah bahwa mutasi yang mempengaruhi bit-bit yang tidak terpakai ini tidak akan merusak genom dan stabilitas lebih baik daripada solusi mewah yang dapat menggunakan bit-bit yang tersisa.
Spesimen kemudian menggunakan ini untuk merencanakan rute yang aman dalam kisi 7x7 yang berpusat pada diri mereka sendiri (5x5 yang memungkinkan penglihatan mereka ditambah 1 kuadrat di setiap sisi untuk memungkinkan jebakan ofset) memprioritaskan bergerak jarak terbesar ke depan setelah 3 gerakan.
Saya awalnya mulai membangun beberapa cek untuk memastikan bahwa fakta bahwa warna spesimen saat ini berdiri tidak mematikan sesuai dengan genom dan menandai setiap warna yang salah sebagai kotak keselamatan UNSURE (dan kotak yang berdekatan) - namun menambahkan signifikan komplikasi untuk keuntungan kecil atau tidak sama sekali dibandingkan dengan menandai kotak-kotak itu sebagai AMAN dan membunuh beberapa spesimen tambahan. Saya akan kembali ke ini jika saya punya waktu.
Skor Contoh:
Skor Maks selama pengujian: 8.150.817 Spesimen Disimpan.
sumber