Geekly articles weekly

Dagaz: Keluar dari Kabut

gambar Semua ini adalah ratu dari Ratu Mab.
Dia menenun di kandang kuda
Dan rambutnya merontokkan ...

William Shakespeare

Itu rilis panjang, tetapi banyak yang dilakukan. Seorang manajer sesi telah muncul , memungkinkan Anda untuk mundur dengan gerakan yang salah. Di beberapa tempat, desain suara ditambahkan. Namun, saya menemukan cara yang keren untuk mendorong beberapa opsi alternatif untuk penempatan awal dalam satu pertandingan. Dan yang paling penting - saya akhirnya sampai ke permainan dengan informasi yang tidak lengkap.

Saya akan menjelaskan apa yang dipertaruhkan. Dalam permainan papan yang biasa, seperti catur atau catur , pemain, setiap saat dalam permainan, memiliki informasi lengkap tentang lokasi potongan (milik mereka dan lawan), aturan untuk memindahkan mereka, tujuan permainan, dll. Game seperti itu dipelajari dengan cukup baik dan masuk dalam kategori " game dengan informasi lengkap ." Sekarang, bayangkan beberapa informasi ini mungkin disembunyikan dari pemain.


The Fog of War adalah ilustrasi yang bagus untuk temanya. Menurut aturan " Catur Buta ", pemain tidak dapat melihat semua bagian dari musuh, tetapi hanya mereka yang ditempatkan di ladang, yang dapat dicapai dengan satu gerakan dari setiap bagian mereka. Saya membuat dua tambahan pada aturan ini:

  1. Tentu saja, pemain selalu melihat potongannya, tetapi dengan cara mereka ditampilkan - dalam bentuk normal atau transparan, ia dapat menilai apakah lawan melihat mereka.
  2. Untuk tujuan dekoratif saja, saya menempatkan "awan" di area yang saat ini tidak terlihat.

Setelah menguasai prinsip umum, saya sedikit terbawa suasana dan membuat banyak permainan dengan "kabut perang". Selain Catur itu sendiri , saya memiliki opsi "gelap" untuk Xiang , Changi , Shatrange , Sittuyin dan banyak permainan lainnya. Bahkan ada " Blind Guns "! Semua game ini memiliki satu kesamaan:

Komputer curang!
Saya bahkan tidak mencoba untuk membuat perubahan pada algoritma bot untuk permainan ini, karena saya bertaruh bahwa kondisi yang tidak setara setidaknya sebagian mengimbangi permainan mereka yang sangat lemah dibandingkan dengan manusia. Seperti yang saya tulis sebelumnya, pengembangan AI berkualitas tinggi untuk permainan papan adalah tugas yang sangat sulit. Tentu saja, aturannya memiliki pengecualian. Bahkan dengan permainan bot yang sangat lemah, akan sulit bagi seseorang untuk memainkan permainan yang tidak dikenalnya, yang benar-benar penuh dengan jebakan. Apa yang bisa kita katakan tentang versi "gelap" nya

Namun, secara umum, ini bukan pendekatan yang sangat benar. Saya ingin melihat bot yang dapat melakukan persis dengan data yang dimiliki lawannya. Mengapa ini penting? Semuanya sangat sederhana - omong-omong bot bermain, kadang-kadang sangat mudah untuk menebak apakah ia memiliki akses ke informasi tersembunyi (mengintip) atau tidak. Dan tentu saja, jauh lebih menarik bagi seseorang untuk bermain dengan bot yang tidak mengintip (bermain dengan orang lain bahkan lebih menarik, tetapi ini adalah cerita yang berbeda).

Dan di sini ada baiknya memilih permainan yang sedikit berbeda dari Catur (karena saya tidak siap untuk mengembangkan bot "jujur" bermain catur "secara membabi buta"). Ada banyak permainan seperti itu dan tidak dapat dikatakan bahwa mereka lebih sederhana daripada catur atau catur. Mereka hanya berbeda dan memerlukan pendekatan individual.

Sebagai contoh
Ada satu permainan anak-anak dimana saya belum berhasil mengembangkan bot. Ini disebut "Jungle" atau Dou Shou Qi . Tujuan permainan ini adalah untuk menembus wilayah musuh. Masing-masing pemain memiliki "sarang" - bidang tengah di baris pertama. Jika ada tokoh musuh yang memasuki sarang, dia menang (Anda tidak dapat menempati sarang dengan tokoh Anda sendiri).


Angka-angka itu dipesan oleh senioritas. Gajah mengalahkan semua angka, diikuti oleh: Singa, Harimau, Macan Tutul, Anjing, Serigala, Kucing dan Tikus. Seekor tikus hanya bisa mengalahkan gajah dan tikus lain, di samping itu, ini adalah satu-satunya sosok yang bisa bergerak di air (di tengah papan ada dua reservoir). Seekor harimau dan singa dapat melompati air, tetapi hanya jika tikus itu tidak menghalangi air. Dengan pengecualian melompat, semua gambar bergerak dengan cara yang sama - ke satu bidang yang berdekatan secara vertikal atau horizontal. Sarang dikelilingi oleh perangkap. Sosok yang ada dalam perangkap rentan terhadap sosok musuh mana pun .

Seperti yang Anda lihat, aturannya cukup sederhana. Apa yang mencegah perkembangan bot untuk game ini? Pertama-tama, angka kecepatan rendah. Jika ada ancaman, saya bisa menghargai manfaat dari pertukaran, tetapi untuk sebagian besar permainan, potongan hanya berjalan satu demi satu dalam jarak yang cukup jauh. Saya tidak dapat melihat permainan untuk sejumlah besar gerakan ke depan (karena batasan pada durasi perhitungan langkah tersebut), akibatnya perubahan tersebut berada di luar cakrawala penglihatan dan semua gerakan menjadi setara untuk saya.

Pertama -tama, saya memutuskan untuk memikirkan BanQi - Chinese Blind Chess. Ini adalah game yang sangat orisinal dengan informasi tersembunyi, mirip dengan "Jungle". Penting bagi saya bahwa pengembangan, sehubungan dengan pembuatan bot untuk game ini, dapat digunakan di game lain, seperti Dou Shou Qi , Luzhan Qi , Stratego atau bahkan (mungkin) Tafl .


Aku akan memberitahumu tentang aturannya. Permainan berjalan dengan setengah papan untuk "Catur Cina" ( Xiang Qi ), sedangkan tata letak asli papan tidak memainkan peran apa pun. Potongan ditempatkan di dalam sel (seperti yang tradisional), dan bukan di persimpangan garis (seperti dalam catur Cina). Pada awal permainan, semua potongan dicampur dan ditempatkan menghadap ke bawah di papan (karena potongan tradisional Syants adalah semacam barel, dan jumlah mereka bertepatan dengan jumlah bidang pada setengah papan, tidak ada kesulitan).

Selanjutnya, para pemain mengganti gerakan mereka. Melakukan gerakan, pemain dapat membalik bagian yang tertutup, atau memindahkan bagian warna yang sebelumnya terbuka. Warna para pemain ditentukan oleh gerakan pertama. Jika potongan hitam pertama dibuka, pemain yang membukanya akan bermain hitam. Semua angka dalam permainan berjalan dengan cara yang sama (dengan pengecualian "Cannon" dalam versi Taiwan, yang akan saya bahas nanti) - pada satu sel yang berdekatan secara vertikal atau horizontal. Kemungkinan pengambilan ditentukan oleh urutan senioritas angka:

Umum> Penasihat> Gajah> Gerobak> Kuda> Meriam> Tentara

Sosok yang lebih tua mengalahkan yang lebih muda atau sama dengan mereka, dengan satu pengecualian: seorang prajurit memukul jenderal (semacam " Rock-Paper-Scissors "). Masih ada beberapa patah kata tentang BanQi Taiwan:

  1. Berbeda dengan versi Cina, di Taiwan BanQi, seorang jenderal tidak bisa mengalahkan seorang prajurit.
  2. Pistol bergerak sesuai dengan aturan XiangQi , yaitu, ke sejumlah bidang di sepanjang kecepatan rendah ortogonal (seperti kereta) atau mengenai sosok musuh, dengan melompat melalui "kereta", saat melakukan serangan.

Ada juga versi Hong Kong, tetapi praktis tidak berbeda dengan Cina, kecuali bahwa urutan senioritas angka telah diubah. Saya memutuskan untuk fokus pada versi peraturan Taiwan, sebagai taktik yang paling menarik.

Apa yang harus saya cari ketika mengembangkan bot?
Pertama, permainan terlihat sangat sederhana, tetapi ternyata tidak. Bahkan jika Anda tidak mempertimbangkan nuansa yang terkait dengan senjata Taiwan, biaya dari angka-angka itu berlawanan dengan intuisi. Meskipun "Penasihat" dapat mengalahkan angka lebih sedikit daripada "Jenderal", dia adalah protagonis utama dalam permainan. Pertama, pemain memiliki dua penasihat. Selain itu, hanya satu jendral musuh yang unggul dalam kekuatan masing-masing penasihat, sementara jenderal dapat diserang oleh sebanyak lima tentara! Untuk alasan yang sama, biaya seorang prajurit dalam permainan lebih tinggi daripada biaya seorang jenderal. Pada akhirnya, dia bisa mengalahkan sosok terkuat! Pertimbangan penting kedua menyarankan salah satu teka-teki "Canterbury" dari Henry Dudeney.


Ini lebih merupakan tugas lelucon daripada puzzle yang lengkap. Semua gambar dapat pergi ke satu bidang yang berdekatan secara vertikal atau horizontal. Putih bergerak terlebih dahulu, sementara putih dan hitam selalu membuat dua gerakan (dalam potongan berbeda)! Dalam kondisi ini, badut kiri tidak akan pernah bisa menangkap keledai kiri, dan buff kanan tidak akan pernah bisa menangkap keledai kanan (Anda bisa memeriksanya sendiri). Tentu saja, badut yang tepat dapat menangkap keledai kiri tanpa kesulitan. Ini semua tentang paritas!

Masalah ini memberi saya beberapa pemikiran. Pertama, tugas bot, dalam gim seperti BanQi atau DouShouQi, pertama-tama adalah menemukan jalur terpendek. Dari masing-masing bagian aktif (milik sendiri atau lawan), perlu untuk membangun rantai pergerakan ke semua tujuan yang mungkin (termasuk bagian mereka sendiri, untuk menghitung kemungkinan pertukaran). Setelah itu, rantai perlu dievaluasi dan opsi berikut dimungkinkan di sini.

  1. Sosok yang menyerang mengalahkan yang diserang - rantai (bonus) yang menguntungkan yang diestimasikan oleh biaya tokoh yang diserang (dikurangi biaya yang diserang, jika yang terakhir dilindungi), dengan mempertimbangkan panjang rantai.
  2. Sosok menyerang mengalahkan serangan - bukan rantai (penalti) menguntungkan, diperkirakan oleh nilai tokoh menyerang.
  3. Potongan-potongan mengalahkan satu sama lain (misalnya, mereka sama) - di sini semuanya tergantung pada paritas, rantai ganjil menguntungkan, dan yang genap harus dianggap sebagai yang penalti (jika tidak ada angka lain di lapangan, paritas akan sepenuhnya menentukan hasil pertandingan).

Tentu saja, semuanya tidak begitu sederhana. Paling tidak, Anda harus mengingat jalur meriam khusus di BanQi Taiwan (Mengenai “Hutan,” bahkan ada lebih banyak kasus khusus), tetapi di sinilah Anda dapat memulai. Dengan rangkaian lengkap rantai yang dievaluasi, Anda dapat mengevaluasi gerakan. Biaya perpindahan harus terdiri dari biaya rantai (baik bonus maupun gratis), yang panjangnya berkurang.

Pertama-tama, penting untuk dipahami bahwa tidak mungkin untuk dapat secara efektif menggunakan algoritma minimax di sini. Bergerak yang mengungkapkan bagian yang sebelumnya tersembunyi juga secara radikal mengubah estimasi posisi. Tidak memiliki informasi tentang kepingan tersembunyi, hampir tidak mungkin untuk melihat posisi yang banyak bergerak di depan. Tetapi setiap awan memiliki garis perak, tetapi kita dapat menggunakan heuristik yang jauh lebih kompleks (dalam hal perhitungan) untuk mengevaluasi gerakan itu sendiri!

Saya sudah memiliki bot yang mengevaluasi gerakan dengan heuristik mereka (diperlukan untuk satu permainan yang menyenangkan). Ini adalah algoritma yang sangat sederhana. Semua gerakan diurutkan dalam urutan menurun dengan heuristik (bergerak dengan nilai heuristik negatif umumnya dibuang), setelah itu mereka dipindai secara berurutan. Jika langkah selanjutnya mengarah ke posisi di mana tidak ada respons musuh yang mengarah ke kemenangan segera, bot menganggapnya sebagai yang terbaik. Dengan menggunakan algoritma ini, Anda tidak dapat repot dengan estimasi posisi, tetapi Anda harus berkutat pada heuristik .

Pertama-tama, kami membangun rantai
var getChains = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.chains)) { board.chains = []; var pieces = getGoals(design, board); var targets = getTargets(design, board, pieces); _.each(pieces.positions, function(pos) { var goals = pieces; var f = true; var piece = board.getPiece(pos); if (piece === null) return; if (!chinese && (piece.type == 12)) { goals = targets; f = false; } var group = [ pos ]; var level = []; level[pos] = 0; for (var i = 0; i < group.length; i++) { if (_.indexOf(goals.positions, group[i]) >= 0) { //  ... } if ((i > 0) && (board.getPiece(group[i]) !== null)) continue; _.each(design.allDirections(), function(dir) { p = design.navigate(board.player, group[i], dir); while (p !== null) { if (_.indexOf(group, p) >= 0) break; group.push(p); level[p] = level[ group[i] ] + 1; if (f || (board.getPiece(p) !== null)) break; p = design.navigate(board.player, p, dir); } }); } }); } return board.chains; }

Tentu saja, saya menyimpan semua data perantara dalam kondisi permainan, agar tidak membacanya beberapa kali. Selain itu, satu trik digunakan di sini, yang sangat berguna dalam menghitung area yang terhubung. Saya beralih di atas array grup , menempatkan elemen tambahan di dalamnya dalam loop, sesuai kebutuhan. Semua kesulitan dikaitkan dengan senjata. Bagi mereka, tujuan rantai bukanlah angka itu sendiri, tetapi bidang dari mana yang terakhir dapat diserang.

Rantai dievaluasi persis seperti yang saya katakan
 var getChainPrice = function(design, board, attacker, attacking, len) { var player = board.getValue(board.player); if ((player === null) || (attacker == null) || (attacking === null)) return 0; if (attacker.player == attacking.player) return 0; var isAttacking = isAttacker(design, attacker.type, attacking.type); var isAttacked = isAttacker(design, attacking.type, attacker.type); if (!chinese && (attacker.type == 12)) { isAttacking = true; isAttacked = (attacking.type == attacker.type) && (len == 1); } var price = 0; var f = (len % 2 == 0); if (attacker.player != player) f = !f; if (isAttacking) { if (isAttacked) { price = f ? (len - design.price[attacker.type]) : (design.price[attacking.type] - len); } else { price = design.price[attacking.type] - len; if (f) price = (price / 2) | 0; } } else { if (isAttacked) { price = len - design.price[attacker.type]; } } return price; }

... tergantung pada panjang dan paritas rantai, serta memperhitungkan biaya angka yang diserang dan diserang. Tapi ini baru setengah pertempuran! Penting untuk mengevaluasi setiap gerakan yang mungkin menggunakan rantai yang dibangun. Saya memperkenalkan satu lagi struktur perantara - ingin menggabungkan data yang tersedia. Penilaian kursus terdiri dari penilaian keinginan, yang memuaskan:

Sesuatu seperti ini
 var addWish = function(board, comment, price, src, dst) { if (_.isUndefined(board.wish[src])) { board.wish[src] = []; } if (_.isUndefined(dst)) dst = src; if (_.isUndefined(board.wish[src][dst])) { board.wish[src][dst] = price; } else { board.wish[src][dst] += price; } } var getWish = function(design, board) { if (_.isUndefined(board.wish)) { ... } return board.wish; } Dagaz.AI.heuristic = function(ai, design, board, move) { var wish = getWish(design, board); if (move.isSimpleMove() && !_.isUndefined(wish[ move.actions[0][0][0] ]) && !_.isUndefined(wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ])) { return wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ]; } return 0; }

Adapun fungsi getWish sendiri , sihir dimulai di sini (dan ini adalah tempat di mana saya kemungkinan besar membajak lebih dari sekali). Pertama-tama, saya membagikan penilaian langkah berdasarkan informasi terbuka dan pengenalan potongan baru ke dalam permainan. Ini tidak sepenuhnya benar, tetapi sejauh ini saya hanya tidak tahu bagaimana mendamaikan pendapat yang begitu beragam. Jika berdasarkan informasi terbuka tidak ada keinginan yang terbentuk, bot mencoba untuk membuka angka baru (ada juga beberapa trik di sini).

  1. Jika meriam musuh terbuka, dikelilingi oleh angka-angka yang tertutup, masuk akal untuk membuka salah satu angka di sebelahnya, karena kemungkinan ia akan dapat menyerang senapan, dan pistol tidak akan dapat mengalahkannya, dalam hal apa pun.
  2. Jika sosok selain meriam terbuka, Anda dapat mencoba membuka sosok yang terletak di "kereta" dari sana, karena ada kemungkinan itu akan berubah menjadi meriam.
  3. Jika ada rantai serangan dari sisi musuh, salah satu bagian dapat dibuka, di sebelah rantai, untuk mencegat serangan.
  4. Jika Anda tidak dapat melindungi gambar, Anda dapat membuka angka di sebelahnya, mencoba mengurangi situasi menjadi pertukaran.

Tentu saja, sangat berguna untuk mengevaluasi probabilitas pembukaan angka tertentu.
 var getShadow = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.shadow)) { board.shadow = []; _.each(design.allPositions(), function(pos) { var piece = board.getPiece(pos); if ((piece !== null) && (piece.type < 7)) { var value = piece.type + 7; if (piece.player != player) { value = -value; } board.shadow.push(value); } }); } return board.shadow; } var isFriend = function(design, x) { return x > 0; } var isPiece = function(design, x, y) { return x == y; } var isAttacker = function(design, x, enemy) { if (x < 0) return false; if ((x == 13) && (enemy == 7)) return true; if (!chinese && (x == 7) && (enemy == 13)) return false; if (!chinese && (x == 12)) return false; return x <= enemy; } var isDefender = function(design, x, enemy, friend) { if (!isAttacker(design, x, enemy)) return false; return design.price[friend] <= design.price[enemy]; } var estimate = function(design, board, p, y, z) { var shadow = getShadow(design, board); if (shadow.length == 0) return 0; var r = 0; _.each(shadow, function(x) { if (p(design, x, y, z)) r++; }); return (100 * r) / shadow.length; }

Pemain dapat mengevaluasi probabilitas dengan melacak angka-angka yang keluar dari permainan. Pada prinsipnya, bot dapat melakukan hal yang sama, tetapi ada cara yang lebih mudah - untuk melihat angka yang masih belum terbuka dalam jumlah besar dan untuk mengevaluasi kemungkinan membuka yang diinginkan berdasarkan informasi yang dikumpulkan. Selain itu, keberhasilan langkah yang dipilih tidak dijamin, tetapi jika probabilitas hasil yang menguntungkan rendah, langkah tersebut tidak akan dipilih sama sekali.

Pada prinsipnya, pendekatan itu membuahkan hasil, tetapi masih ada pekerjaan yang harus dilakukan.
Sementara gerakan defensif tidak terlalu baik. Beberapa tokoh dengan berani bertemu dengan musuh yang lebih kuat, bukannya melarikan diri darinya (meskipun melarikan diri dalam kasus mereka, sebagai suatu peraturan, sudah tidak berguna). Juga, ada kesulitan dalam mengkoordinasikan tindakan berbagai tokoh (ini dapat berguna untuk "mengusir" sisa-sisa tokoh musuh). Pendekatan itu sendiri terlihat sangat menjanjikan, tetapi heuristik masih harus dipertimbangkan.

Heuristik yang didasarkan pada "rantai" gerakan dapat berguna tidak hanya di BanQi, tetapi juga di banyak game lain, dengan dominasi potongan "bergerak lambat" (jika bukan sebagai kriteria yang menentukan, maka untuk penilaian awal kualitas gerakan dalam algoritma yang lebih kompleks, setidaknya paling tidak). Pendekatan ini sangat diminati di gim-gim tersebut yang penggunaan algoritma minimax sulit atau bahkan tidak mungkin (seperti misalnya Yonin Shogi ).


Tentu saja, saya akan terus bekerja pada permainan dengan informasi yang tidak lengkap. Gambar menunjukkan " Game of the General " Filipina, belum siap. Ini adalah game termudah dari keluarga besar, termasuk game seperti LuzhanQi dan Stratego . Dan tentu saja, saya masih berharap untuk membuat bot yang berfungsi untuk " Jungle "!

Dan bagi mereka yang masih membaca saya, saya dapat menawarkan permainan puzzle yang menyenangkan dengan informasi tersembunyi:


Saya memainkannya di masa kecil saya, dengan kalkulator yang dapat diprogram bernama Fox Hunt. Delapan rubah tersembunyi secara acak di lapangan, yang harus ditemukan menggunakan "metode poke". Saat Anda memilih area kosong, jumlah rubah di delapan arah ditampilkan. Tidak mungkin kalah, tetapi Anda dapat bersaing untuk jumlah klik minimum. Dan jika Anda bermain dengan headphone, matikan suaranya. Mungkin saya overdid dengan efek suara.

Source: https://habr.com/ru/post/id422427/

More articles:


All Articles