Saat bermain sesuai dengan aturan Gomoku standar, Black tidak membutuhkan lebih dari
35 gerakan untuk menang. Artikel ini menyajikan kepada Anda strategi kemenangan lengkap dan algoritma permainan yang sesuai.
Peragaan solusi lengkap - di
sini - Anda dapat bermain dan menemukan opsi terpanjang. Program selalu menang dan dihabiskan tidak lebih dari 35 gerakan. Kode sumber aplikasi, solusinya sendiri dan contoh pihak di akhir artikel.
Saya tidak akan memikirkan aturan dan taktik permainan. Topiknya dibahas secara rinci tentang habr di
sini , serta algoritma keputusan di
sini dan di
sini .
Penyimpangan kecil
Sebelum era smartphone, tic-tac-toe "lima berturut-turut" (Gomoku, Renju) adalah salah satu pembunuh terpopuler saat pelajaran sekolah. Mempertimbangkan kombinasi lebih menarik daripada perkembangan ekonomi nasional Afrika Utara atau klasifikasi bunga semanggi.
Pada musim gugur 1985, anak perempuan dari kelas 10 kami diambil dari kelas matematika. Kami, enam anak yang tersisa, kemungkinan besar memiliki komunikasi informal dengan seorang guru matematika tentang topik-topik abstrak. Guru memasuki ruang kelas dalam keheningan, membagikan selebaran kepada semua orang dalam sebuah kotak dan mulai menulis nama-nama yang hadir di papan tulis. Kami mengalami depresi, pekerjaan independen atau survei kilat telah direncanakan. Tetapi daftar di papan berubah menjadi kedudukan dan kami diumumkan aturan kejuaraan. Masing-masing dengan setiap seri lima pihak. Hadiah untuk pemenang - lima untuk majalah. Menurut hasil turnamen, saya beruntung menang, tetapi pertandingan tidak berakhir di sana. Guru itu berjanji untuk memberikan balita kepada semua orang jika pemenangnya memenangkan semua lima pertandingan seri secara berturut-turut. Hak langkah pertama diberikan kepada pemenang. Bertentangan dengan pernyataan guru kami bahwa pada kondisi seperti itu, dengan permainan yang tepat, Anda dapat memenangkan 10, 100, atau sejumlah permainan berturut-turut, bagi saya kemenangan tampaknya merupakan keberuntungan yang luar biasa.
Sembilan tahun kemudian, pada tahun 1994, bukti hipotesis ini dilaporkan oleh Dr. Lewis Victor Allis dalam sebuah artikel oleh
Go-Moku dan Threat-Space Search . Penulis tidak mempublikasikan strategi kemenangannya, yang memungkinkannya untuk memverifikasi buktinya. Namun, dalam bukunya 1996
Mencari Solusi dalam Game dan Kecerdasan Buatan , deskripsi umum dari algoritma disediakan. Sebagai kesimpulan, kami secara terpisah menyebutkan prosedur untuk memeriksa kelengkapan strategi kemenangan, yang bergantung pada ketepatan implementasi algoritma pencarian untuk "urutan ancaman" dan analisis opsi lawan lawan.
Contoh-contoh solusi yang diberikan dalam artikel dan buku dengan "gerakan yang tepat" dari lawan, yang merupakan bagian dari strategi kemenangan, menunjukkan kelemahan dari algoritma yang digunakan.
Misalnya, pada gambar, solusi program untuk aturan Gomoku standar. Jika Hitam merespons dengan j10 dan kemudian j8 sebagai tanggapan atas langkah ke-10 White g9, maka permainan berakhir dalam 29 gerakan alih-alih 45. Kemudian program dua kali "tidak memperhatikan" kombinasi "urutan ancaman" Black dalam 17 langkah setelah tanggal 16 dan setelah 26- Langkah White. Dan pada akhirnya, jika Putih membuat langkah ke-36 f12 alih-alih j12, ia akan bertahan setidaknya sampai langkah ke-49. Dalam keadilan, harus dikatakan bahwa dalam contoh ini, semua gerakan Black tidak memberikan kesempatan bagi White untuk mengakhiri permainan.
Di Internet, saya menemukan beberapa referensi untuk pekerjaan serupa yang mencari strategi kemenangan. Pertanyaan tentang optimalitas solusi yang ditemukan masih belum terselesaikan. Berapa jumlah minimum gerakan yang dibutuhkan Black untuk menang?
Jadi, memiliki sedikit waktu luang, sumber daya komputasi modern, dan penghormatan kepada hobi anak-anak 33 tahun setelah kejuaraan sekolah yang berkesan, ia menetapkan tugas untuk menemukan strategi kemenangan optimal bagi Black di Gomoku.
Digitasi posisi di papan tulis
Merekam suatu bagian sangat primitif. Hanya ada 225 sel di lapangan. Dengan demikian, setiap sel dikodekan oleh 1 byte. Untuk merekam kumpulan 35 gerakan, hanya 35 byte yang diperlukan. Tetapi catatan semacam itu sangat tidak cocok untuk evaluasi posisi karena dua alasan: posisi yang sama dapat diperoleh dalam urutan gerakan yang berbeda dan posisi simetris tidak diperhitungkan.
Mencapai tujuan permainan - membangun lima batu secara berurutan - dapat dilakukan dalam satu dari empat arah: vertikal, horizontal dan dua diagonal. Dengan demikian, kita dapat mewakili posisi apa pun sebagai seperangkat garis. Garis horizontal dan vertikal dengan panjang 15 sel dan garis diagonal dengan panjang 1 hingga 15 sel. Setiap gerakan mengubah nilai 4 baris dalam arah yang berbeda sekaligus.
Tugas mengevaluasi suatu posisi adalah menentukan semua angka penting untuk setiap baris. Untuk kesederhanaan, kami menggambarkan setiap sel garis dengan 2 bit. Bit pertama penuh ketika batu putih dipasang, bit kedua adalah batu hitam. Setiap baris berisi tidak lebih dari 15 sel dan dikodekan ke dalam integer 32-bit. Dengan demikian, pencarian bentuk pada garis dikurangi untuk membandingkan nilai numerik garis melalui jendela geser dengan pola bit bentuk.
Dalam contoh yang ditunjukkan pada gambar, posisi digambarkan oleh 26 baris. Dengan demikian, itu dikodekan dengan 104 byte, sedangkan catatan batch reguler hanya membutuhkan 17 byte.
Mudah ditebak bahwa semua simetri - belokan dan gambar cermin - diperoleh hanya dengan mengubah angka (pengocokan) dan arah garis. Untuk mengidentifikasi posisi dan mencari koleksi dengan cepat, prinsip ini mengimplementasikan fungsi hash 32-bit yang memberikan nilai yang berbeda hanya untuk posisi asimetris.
Penggunaan simetri secara signifikan mengurangi jumlah posisi yang dipertimbangkan. Misalnya, jumlah opsi untuk langkah kedua berkurang dari 224 menjadi 35.
Saat mencari solusi dan kombinasi (ini akan dibahas di bawah), posisi yang dihitung membentuk simpul dari grafik multilayer. Verteks dikelompokkan dalam lapisan sesuai dengan jumlah sel yang diisi. Bergerak membentuk tepi grafik, menghubungkan simpul dari lapisan yang berdekatan. Ketika gerakan yang gagal dibuang selama pencarian, ujung-ujungnya dihapus dan beberapa simpul kehilangan konektivitasnya dengan cabang utama. Karena itu, setelah langkah-langkah perhitungan, pengumpulan sampah (atau membangun kembali grafik dari atas) dilakukan.
Selama proses pengembangan, beberapa algoritma pengkodean dipertimbangkan, tetapi yang dijelaskan di atas menunjukkan tingkat estimasi posisi tertinggi.
Evaluasi posisi
Faktor penting untuk mengevaluasi suatu posisi adalah seberapa penting lawan membangun bagian yang signifikan.
Lima - jika bagian seperti itu ditemukan di papan tulis, permainan sudah berakhir. Untuk aturan standar, jangan berenam, tujuh, dll., Berikan Gomoku hadiah. Oleh karena itu, kelimanya, seperti, secara kebetulan, semua tokoh lainnya, memerlukan ketiadaan batu mereka pada sel-sel tetangga dalam satu garis.
Empat terbuka - panjang 6 sel, empat tengah ditempati oleh batu dengan warna yang sama, yang luar tentu kosong. Nah, seperti untuk lima, batu-batu mereka tidak ada di sel tetangga. Sosok yang sangat kuat berarti menang bahkan pada langkah orang lain.
Empat - panjang 5 sel, satu (ada) dari lima sel itu gratis. Memberi kemenangan sendiri. Itu menciptakan ancaman dan memaksa lawan untuk bergerak di sel bebas jika ia tidak memiliki empat selnya. Memberikan 5 poin di peringkat posisi selama pertahanan.
Triple terbuka - panjang 6 atau 7 sel, sel terluar tentu bebas. Untuk 6 sel, tiga dari empat sel tengah ditempati oleh batu dengan warna yang sama, satu bebas. Untuk 7 sel - tiga sel sedang ditempati oleh batu dengan warna yang sama. Sepotong pada gilirannya menjadi empat terbuka jika lawan tidak memiliki empat atau tiga terbuka. Pada gerakan orang lain, itu menciptakan ancaman dan memaksa lawan untuk menutup tiga atau menempatkan empat sebagai respons. Triple cell 6 memiliki 1 gerakan menaikkan dan 3 gerakan penutupan. Triple sel 7 memiliki 2 gerakan menaikkan dan hanya 2 gerakan penutupan. Memberikan 2 hingga 4 poin di peringkat posisi.
Rangkap tiga , atau rangkap tiga tertutup, adalah panjang 5 sel, tiga di antaranya ditempati oleh batu dengan warna yang sama. Ketiganya pada gilirannya bisa berubah menjadi empat dan digunakan dalam serangan dan pertahanan, menciptakan ancaman lebih dari tiga lawan yang terbuka. Memberikan 1 poin pada peringkat posisi.
Panjang (perspektif)
deuce - dari 6 hingga 7 sel. Saat menyerang, itu dikonversi menjadi tiga terbuka. Memberikan 1 atau 2 poin di peringkat posisi.
Sebuah plug pada saat yang sama dua atau lebih ancaman yang tidak bisa ditutup dalam sekali jalan. Ada garpu 3x3 (dua tripel terbuka), 3x4 (bertiga terbuka dan empat) dan garpu 4x4 (dua merangkak terbuka). Garpu memberikan kemenangan jika lawan tidak memiliki ancaman yang lebih besar - empat atau tiga terbuka untuk garpu 3x3, atau lawan tidak dapat berturut-turut menutup garpu, menciptakan ancaman besar - urutan merangkak untuk garpu 3x3.
Kombinasi - urutan ancaman dan pertahanan yang berkelanjutan terhadap ancaman lawan yang lebih signifikan, yang mengarah ke hasil positif bagi pemain. Kombinasi menyerang (atau menang) dan defensif.
Kombinasi serangan atau kemenangan berhasil jika, pada gerakan defensif atau menyerang lawan, gerakan respons ditemukan mengarah ke kemenangan. Kombinasi serangan berakhir dengan pemasangan colokan, yang tidak bisa ditutup lawan.
Kombinasi pertahanan, sebaliknya, berhasil ketika lawan berhenti membuat ancaman, atau batas langkah untuk perhitungan terlampaui. Kombinasi pertahanan terdiri dari gerakan defensif atau menciptakan ancaman yang lebih besar bagi lawan.
Saat mengevaluasi suatu posisi, pencarian untuk kombinasi pemenang dilakukan. Jika berhasil, kami menang. Kalau tidak, jika tidak ada ancaman dari lawan, negara netral. Jika ada ancaman dari lawan, kami mencari kombinasi pertahanan. Jika berhasil, negara netral, jika gagal, kita kalah.
Karena jumlah opsi untuk menyerang dan gerakan pembalasan paksa cukup terbatas, maka diperbolehkan untuk mencari kombinasi hingga kedalaman yang cukup besar. Selama konstruksi awal dari strategi optimal, kedalaman yang diperbolehkan dari pencarian untuk kombinasi ditetapkan lebih dari 25 gerakan. Saat menghitung ulang solusi untuk mengimplementasikan algoritma estimasi posisi dalam javascript, kedalaman pencarian yang diizinkan dikurangi menjadi 17 gerakan.
Saat menghitung strategi optimal, kedalaman pencarian kombinasi pemenang dari atas juga dibatasi oleh jumlah gerakan maksimum target.
Kami mencari solusi
Jadi, kami menilai posisi yang diberikan sebagai netral dan memilih langkah selanjutnya. Perilaku kita dalam hal ini tergantung pada apakah kita pihak yang menyerang atau bertahan. Untuk sisi yang menyerang, solusi lengkap akan menjadi urutan gerakan di mana untuk setiap pergerakan kembali lawan, posisi dievaluasi sebagai menang (kombinasi pemenang ditemukan) atau berisi langkah berikutnya dalam solusi. Perlu dicatat bahwa untuk menghitung strategi optimal, sisi menyerang selalu hitam, sisi bertahan putih.
Sisi penyerang perlu menemukan hanya satu gerakan, yang mengarah ke kemenangan tercepat. Dalam kondisi kekurangan sumber daya, penyerang secara artifisial membatasi jumlah opsi untuk melakukan busting, saya mempelajari terlebih dahulu semua gerakan yang mengarah ke posisi dengan skor penilaian tertinggi. Setelah solusi apa pun ditemukan, ke arah yang terpanjang di antara mereka, penyerang memperluas berbagai opsi, mengeksplorasi posisi yang kurang diberi peringkat untuk mengurangi panjang solusi.
Cukup bagi tim yang bertahan untuk menemukan satu gerakan tunggal yang tidak mengarah pada kemenangan lawan dalam batas gerakan yang diberikan. Semua sel bebas dapat digunakan untuk enumerasi.
Untuk mengurangi jumlah gerakan yang akan diurutkan, kami menggunakan algoritma "lewati". Kami melewatkan langkah bertahan dan mencari kombinasi serangan yang unggul. Jika berhasil, kemungkinan gerakan pertahanan mungkin terbatas pada gerakan yang memengaruhi keberhasilan kombinasi yang ditemukan. Rata-rata, pada setiap langkah ini memungkinkan Anda mengurangi area pencarian sebanyak 4-6 kali. Harap perhatikan bahwa di antara gerakan yang diabaikan mungkin ada cabang solusi yang lebih panjang. Oleh karena itu, untuk mencari solusi optimal, algoritma "lewati" hanya digunakan dalam pencarian awal.
Kami menghitung strateginya
Semua komponen sudah siap, kami menempatkan batu hitam pertama di tengah lapangan, mulai mencari solusi dan ... Pada ini, setelah beberapa jam, sumber daya laptop saya habis dan saya harus mengakui kekalahan "dalam pertempuran, tetapi tidak dalam pertempuran".
Sebenarnya, saya memiliki kekuatan komputasi di ujung jari saya dengan satu setengah ratus core Xeon dan satu terabyte RAM gratis. Tetapi, ingat bahwa pada pertengahan tahun sembilan puluhan, Allis hanya memiliki 10 SUN SPARCstation 2 pada masing-masing 128 MB RAM, merasa menyesal atas perilaku tidak sportif dan memutuskan untuk membatasi jumlah RAM pada mesin java menjadi 1 GB dan hanya mengalokasikan 1 utas untuk tugas tersebut. prosesor. Entah bagaimana itu bisa mengimbangi GHz saya dibandingkan dengan MHz-nya. Ditambah lagi dia berjanji pada akhir pekerjaan untuk mentransfer algoritma ke javascript untuk browser.
Jadi, pencarian strategi harus dimulai dengan keputusan sketsa debut. Penjelasan rinci tentang debut untuk permainan Renju dalam bahasa Rusia dapat ditemukan di buku-buku terkenal Sagar "Dari Debut ke Middlegame" dan "Ringing of the Stones" karya Mikhail Kozhin dan Alexander Nosovsky di
sini . Buku-buku tersebut sudah berusia 20 tahun, tetapi sejak itu sedikit literatur telah diterbitkan. Koleksi terbaru Dmitry Epifanov "Tiger in a cage" tahun 2015, sayangnya, tidak tersedia dalam bentuk elektronik.
Pencarian untuk keputusan pembukaan optimal dilakukan sesuai dengan algoritma berikut. Pada langkah pertama, perhitungan awal dilakukan tanpa membatasi panjang bets. Kemudian, untuk solusi terlama, optimasi dilakukan: mengganti kombinasi yang ditemukan dengan solusi yang lebih pendek untuk langkah-langkah terakhir dan mencari cabang keputusan yang lebih pendek untuk semua gerakan perantara. Optimalisasi dilakukan hingga batas target tercapai untuk semua cabang solusi. Kemudian batas target menurun dan upaya dilakukan untuk mengoptimalkan ke nilai baru.
Tidak ada masalah dengan debut vertikal ke-3 pada Gambar 3. Hasilnya adalah serangkaian solusi lengkap. Posisi paling sulit setelah langkah ke-4 i8 dan j10 sebagai hasilnya diselesaikan dalam 31 gerakan. Kemudian batas target 35 gerakan per game ditetapkan.
Dari diagonal untuk keputusan itu, ia secara tradisional memilih debut ke-7. Posisi paling sulit muncul setelah langkah ke-4 g9. Solusi panjang yang diizinkan ditemukan untuk 6 gerakan g8 dan g7.
Tetapi untuk opsi ini, dengan langkah ke-6 pada j9, saya tidak dapat menemukan solusi yang lebih pendek dari 33 gerakan. Itu hampir merupakan bencana. Karena putus asa, saya mencoba solusi untuk langkah ke-5 alternatif, serta semua jenis bukaan diagonal lainnya. Debut diselesaikan hingga akhir, tetapi tidak ada yang lebih pendek dari 39 gerakan per game yang tidak dapat ditemukan.
Kembali ke debut diagonal ke-7 yang asli, ia mengubah algoritme untuk menghasilkan kalimat untuk gerakan menyerang. Akibatnya, gerakan yang mengarah ke posisi dengan skor penilaian dari sepuluh ketiga secara tak terduga mulai memberikan hasil dan mengurangi panjang jalur solusi. Keragaman perhitungan dengan jumlah tersebut menjadi cukup besar. Dengan kedalaman 12 langkah solusi, terdapat lebih dari 2 juta posisi (tidak termasuk posisi saat mencari kombinasi). Kelanjutan terletak pada 1GB RAM yang dialokasikan untuk tugas tersebut. Dengan demikian, untuk memeriksa keputusan ke pertigaan final, dalam beberapa kasus perlu secara terpisah memutuskan posisi dari langkah ke-18.
Setelah debut diagonal ke-7 diputuskan dalam 35 gerakan yang diberikan, orang bisa merayakan kemenangan - perjuangan untuk pusat dimenangkan. Di depan masih ada sejumlah besar pekerjaan komputasi rutin, perhitungan langkah putih "tidak optimal" untuk menyelesaikan strategi. Dari total volume strategi optimal, jawaban untuk gerakan seperti itu adalah 80%. Untungnya, mereka secara otomatis diselesaikan sepenuhnya pada perhitungan awal setelah langkah ke-2, dan semua volume ini ditambahkan ke strategi optimal dalam beberapa hari.
Jadi, solusi untuk semua 2 gerakan ditemukan. Kami meletakkan batu hitam pertama di tengah lapangan, memulai pencarian solusi dan bahkan tidak punya waktu untuk merasakan pentingnya momen - posisi awal diselesaikan dalam 35 gerakan. Grafik strategi kemenangan optimal dibangun.
Memeriksa diri kita sendiri
Langkah selanjutnya adalah memverifikasi solusinya. Matikan kecerdasan pihak yang membela sepenuhnya. Setelah setiap gerakan Black, White pergi ke persegi bebas papan. Posisi yang diperoleh setelah kepindahan White harus ditemukan dalam grafik keputusan atau dievaluasi sebagai kemenangan untuk jumlah gerakan yang tidak melebihi cabang terpanjang di posisi awal. Saat mengevaluasi setiap posisi, kami memeriksa kombinasi pemenang yang ditemukan untuk semua gerakan yang dapat diterima White sebelum Black membuat bagian terakhir - lima berturut-turut.
Pemeriksaan itu dilakukan beberapa kali hingga selesai. Proses bebas kesalahan terakhir dalam mode single-threaded membutuhkan waktu 14 jam. Selama pemeriksaan, kesalahan ditemukan dan diperbaiki yang muncul sebagai akibat dari perbedaan kedalaman pencarian kombinasi, asumsi untuk melewatkan gerakan, duplikasi posisi simetris.
Jawab pertanyaan - apakah keputusan dalam 35 gerakan benar-benar paling optimal. Menurut penelitian saya, untuk sejumlah cabang terpanjang dari debut vertikal, adalah mungkin untuk menemukan solusi yang lebih optimal dengan panjang 33 langkah. Tetapi untuk diagonal setelah langkah ke-6 pada bulan j9, banyak waktu dihabiskan untuk mencari solusi dalam 33 langkah, variasi untuk Black diperluas menjadi 50 gerakan di setiap langkah dan tidak berhasil. Tidaklah mungkin untuk membuktikan secara ketat kurangnya solusi dalam 33 gerakan, waktu yang diberikan untuk proyek telah berakhir dan keputusan dibuat untuk berhenti pada batas target 35 gerakan.
Konversi dari java ke javascript
Publikasi solusi untuk suatu masalah membutuhkan kejelasan.
Untuk menggunakan solusi secara langsung di browser, diperlukan:- Kurangi kedalaman pencarian kombinasi saat mengevaluasi posisi menjadi 17 gerakan. Hal ini menyebabkan peningkatan 2-3 kali lipat dalam jumlah langkah yang dihitung dari strategi optimal.
- Ubah format grafik keputusan biner menjadi urutan gerakan JSON. Format ini lebih nyaman dalam javascript dan visual.
- Konversi kelas java ke modul javascript, kecuali untuk prosedur pengambilan keputusan. Di sini, di antarmuka web, ganti panggilan layanan lainnya dengan fungsi lokal.
Daftar kelas aplikasi:- Diskusi Dewan - dewan manajemen partai, antarmuka visual
- Vertex - atas grafik keputusan, diwarisi dari posisi
- Ujung - ujung grafik keputusan, pindahkan posisi penghubung
- Layout - position, berisi kumpulan garis
- Garis - garis dalam arah tertentu, berisi kumpulan bentuk
- Gambar - angka yang menentukan jenis dan awal dari suatu gambar pada suatu garis
- Pola - pola angka untuk perbandingan saat mencari
Solusi lengkap dalam format JSON dapat diunduh dari file gomoku.json .Sumber di repositori di GitHub .Untuk lebih jelasnya, saya akan memberikan contoh-contoh game terlama yang diperoleh dalam demonstrasi di bawah ini dengan mengklik Berikutnya.Debut diagonal:
Debut vertikal:
