Dagaz: Awal yang baru

Ia berlari ke selatan dan berputar ke utara, berputar, berputar untuk berlari bersama anginnya
Dan menurut sirkuitnya angin kembali;
Semua sungai mengalir ke laut - dan laut tidak meluap,
Ke tempat di mana sungai mengalir, - Di sana mereka terus mengalir;

Kitab gerejawi

Pada tahun 1998, aplikasi yang benar-benar unik, untuk masanya dikembangkan yang memungkinkan Anda mengurangi proses pengembangan permainan papan abstrak (atau teka-teki) menjadi bahasa deskripsi teks kecil, yang sedikit mengingatkan pada Lisp . Proyek ini disebut Zillions of Games . Itu menciptakan kehebohan di antara penggemar game papan. Saat ini, lebih dari 2.000 aplikasi telah dibuat menggunakan teknologi ini.

Dengan cepat menjadi jelas bahwa ZoG memiliki banyak kelemahan. Saya sudah menulis tentang ini di Habr dan saya tidak akan mengulangi lagi. Izinkan saya mengatakan bahwa para pengembang tidak memperhitungkan fitur-fitur dari sejumlah besar game yang ada dan beberapa opsi penting sudah dikodekan, sehingga perubahan mereka menjadi sangat bermasalah. Greg Schmidt, pada 2007, mencoba memperbaiki situasi dengan merilis Axiom Development Kit , tetapi integrasi yang erat dengan ZoG tidak memungkinkan menyelesaikan semua masalah.

Project Ludi menunjukkan batas baru, menggunakan "mesin" permainan universal dan algoritma genetika untuk mengotomatiskan proses pengembangan game papan baru. Sayangnya, pendekatan ini pada awalnya dianggap sebagai penyederhanaan yang disengaja dari mekanisme permainan dan tingkat AI yang digunakan. Diskusi tujuan proyek ini berada di luar ruang lingkup artikel ini, tetapi beberapa solusi teknisnya, tidak diragukan lagi, menjadi titik awal untuk pengembangan saya sendiri.

Tujuan saya adalah pengembangan "mesin" yang lebih fleksibel dan ramah pengguna untuk pembuatan game papan abstrak. Selama hampir satu tahun saya telah mempelajari kemungkinan ZoG dan Aksioma dan belajar banyak tentang keterbatasan mereka. Saya pikir saya bisa menyelesaikan masalah mereka dengan menciptakan solusi yang lebih universal dan lintas platform. Tentang kemajuan pekerjaan pada proyek ini saya akan melaporkan.

Keterbukaan dan modularitas

Mungkin kelemahan utama ZoG adalah penutupannya. Produk ini dirakit “sekali dan selamanya” di bawah satu platform tunggal - Windows. Kalau itu kode sumber terbuka, orang bisa mencoba untuk mem-portalnya di Linux, Android, iOS ... Masalah lain adalah monolitiknya.

Di ZoG ada permulaan modularitas, memungkinkan untuk koneksi ke game DLL, termasuk implementasi kustom AI. Aksioma berjalan sedikit lebih jauh, memungkinkan Anda untuk menjalankan aplikasi dalam mode autoplay, tanpa menggunakan kernel ZoG. Sekalipun ada keterbatasan serius dari solusi ini (hanya mendukung aplikasi untuk dua pemain), contoh ini menunjukkan bagaimana modularitas akan membantu! Kesempatan untuk mengatur permainan dengan dua bot (menggunakan pengaturan AI yang berbeda) dan untuk mengumpulkan statistik pada sejumlah besar permainan tidak dapat ditaksir terlalu tinggi. Tetapi akan jauh lebih baik jika produk tersebut sepenuhnya modular!

• Pindahkan modul pembangkit
• Pindahkan modul eksekusi
• Modul kontrol
• Modul AI
• Modul visualisasi

Semua pekerjaan yang menggambarkan permainan harus dilakukan oleh modul pemindahan generasi. Ini adalah "jantung" proyek. Pemindahan semua tugas yang tidak terhubung dengan fungsi ini ke modul lain akan membuatnya sesederhana mungkin. Anda dapat meningkatkan modul ini, tanpa melihat masalah AI dan interaksi pengguna. Anda dapat sepenuhnya mengubah format deskripsi game atau menambahkan dukungan untuk deskripsi dalam format ZoG, Axiom dan Ludi. Modularitas adalah dasar dari fleksibilitas solusi!

Modul eksekusi langkah adalah penjaga kondisi permainan. Informasi tentang status permainan saat ini ditransfer ke semua modul lain sesuai permintaan. Untuk alasan yang akan saya berikan di bawah ini, kemajuan eksekusi harus melewati modul generasi, yang tugasnya adalah pembentukan perintah dalam hal pelaksanaan modul. Juga, tugas dari modul pembangkitan bergerak adalah konfigurasi utama ruang gim, berdasarkan deskripsi gim.

Modul kontrol sebenarnya adalah aplikasi itu sendiri. Itu meminta modul generasi bergerak untuk daftar langkah yang mungkin dan mengubah keadaan permainan, melewati langkah yang dipilih ke modul eksekusi langkah. Modul kontrol dapat dihubungkan untuk memainkan satu atau lebih bot AI. Sebanyak yang Anda butuhkan (dan mungkin berbeda)! Jenis unit kontrol ditentukan oleh pembagian tugas. Ini mungkin putar otomatis untuk mengumpulkan statistik game, server game (dapat mengontrol beberapa toko negara, memimpin sejumlah besar sesi permainan) atau aplikasi individual untuk bermain offline.

Kemampuan untuk menghubungkan berbagai implementasi AI akan meningkatkan kualitas permainan. Dapat dipahami bahwa modul untuk permainan catur dan Go harus menggunakan pendekatan yang berbeda. Gim dengan informasi yang tidak lengkap dan gim yang menggunakan data acak juga membutuhkan pendekatan individual. Implementasi universal AI akan sama buruknya memainkan semua game! Koneksi modular AI akan memungkinkan untuk membandingkan "kekuatan" dari algoritma, termasuk mode permainan "satu sama lain." Karena arsitektur AI dipisahkan dari kondisi penyimpanan permainan, satu contoh bot permainan dapat mendukung jumlah yang tidak terbatas sesi game secara bersamaan.

Visualisasi proses permainan juga dapat bervariasi. Hal pertama yang terlintas dalam pikiran adalah implementasi 2D dan 3D. Platform tempat aplikasi sedang dikembangkan, juga penting. Yang kurang jelas adalah bahwa visualisasi mungkin menjadi bagian penting dari permainan! Misalnya, dalam permainan Surakarta , mengambil barang akan sama sekali tidak jelas karena tidak ada animasi gerakan yang tepat.


Secara umum, modularitas tampaknya merupakan ide yang bagus untuk proyek semacam itu, dan kode sumber terbuka akan memungkinkan semua orang yang ingin berpartisipasi dalam proyek tersebut. Saat ini, saya tidak menetapkan tujuan komersial untuk diri saya, tetapi saya pikir, jika diinginkan, saya akan menemukan cara untuk menghasilkan uang tanpa menutup kode sumber.

Ruang permainan

Sebelum memulai pertunjukan, Anda perlu mengatur panggung. Papan bukan hanya tempat di mana potongan tersusun. Selain itu, arah pergerakan potongan dapat ditentukan (pada kenyataannya, koneksi antara posisi papan) area bermain (misalnya, area untuk konversi potongan) bidang terlarang, dll. Berikut adalah bagaimana definisi papan catur terlihat dalam implementasi ZoG:


Anda mungkin memperhatikan bahwa di samping pengaturan gim, berikut adalah pengaturan yang terkait dengan visualisasi. Saya sangat yakin bahwa pengaturan ini bukan di sini. Dalam menerapkan modul visualisasi, beberapa pengaturan dapat digunakan dan pengaturan yang berbeda mungkin diperlukan. Selain itu, game simulasi dapat bekerja tanpa modul visualisasi sama sekali (seperti pemutaran otomatis di Axiom). Memang, karena Aksioma digunakan untuk memvisualisasikan ZoG, definisi tersebut tidak mengandung sesuatu yang berlebihan:


Sayangnya, Aksioma juga tidak memiliki cara untuk menentukan zona game (lokasi zona game harus ditentukan secara manual dalam kode). Ini bukan satu-satunya penyederhanaan aksioma. Definisi papan dalam proyek ini tidak boleh mengandung lebih dari satu kisi dan kisi ini harus dua dimensi. Papan, dengan demikian didefinisikan, adalah array satu dimensi, tetapi untuk kenyamanan programmer, sinonim didefinisikan untuk masing-masing ruang sebagai berikut:


Dibandingkan dengan skema definisi grid yang lebih fleksibel dalam ZoG, batasan ini cukup tidak nyaman (terutama mengingat fakta bahwa skema penamaan yang diberlakukan menggunakan bidang ini untuk tujuan visualisasi). Untungnya, dimungkinkan untuk mendefinisikan dewan dengan bentuk yang sewenang-wenang. Baik Aksioma dan ZoG memberikan kesempatan untuk mengidentifikasi elemen-bijaksana setiap posisi di papan bersama dengan kemampuan untuk menentukan hubungan antara pasangan posisi yang sewenang-wenang. Dengan menggunakan pendekatan ini, kita dapat mendefinisikan papan topologi apa pun. Satu-satunya kelemahan adalah verbositas ekstrim dan kompleksitas deskripsi.

Selain lokasi potongan-potongan di papan tulis dan di cadangan, sistem harus memiliki kemampuan untuk menyimpan atribut untuk potongan-potongan individual dan untuk ruang-ruang di papan tulis. Sebuah contoh yang baik tentang perlunya menggunakan atribut aturan " castling " dalam catur . Ini adalah langkah yang sulit, yang termasuk gerakan simultan dari raja dan benteng, diizinkan, asalkan tidak satupun dari potongan-potongan ini telah bergerak sebelum melakukan langkah ini. Atribut dapat digunakan untuk menyimpan tag Boolean yang menunjukkan apakah bagian tersebut pernah dipindahkan. Atribut field juga dapat menemukan beberapa aplikasi menarik.

Perlu dicatat bahwa atribut bukan hanya variabel tetapi bagian dari kondisi permainan. Nilai atribut dapat diubah dengan eksekusi belokan (termasuk oleh modul AI) dan harus tersedia untuk semua belokan berikutnya, tetapi tidak untuk belokan yang dilakukan di cabang lain dari game. Saat ini, ZoG mendukung penyimpanan atribut boolean. Atribut aksioma penyimpanan tidak didukung, tetapi Anda dapat menambahkan deskripsi definisi variabel dan array ke definisi board. Variabel-variabel ini dapat digunakan, seperti penghitung jumlah potongan yang ditangkap:

 {board 5 18 {grid} {variable} WhitePieces {variable} BlackPieces board} 

Namun batasan lain dari ZoG dan Aksioma adalah aturan bahwa setiap posisi dewan dapat berisi tidak lebih dari satu bagian. Jika ada bagian yang menyelesaikan perpindahan ke posisi yang ditempati oleh bagian lain, bagian yang sebelumnya menempati posisi tersebut secara otomatis dianggap "dimakan". Aturan ini berjalan dengan baik dengan prinsip "catur" mengambil barang dan berfungsi untuk menyederhanakan deskripsi game ini, tetapi mempersulit implementasi game seperti " bashni checkers " dan " tavreli ".



Dalam permainan ini, potongan dapat diatur dalam "kolom". "Kolom" seperti itu dapat dipindahkan bersama-sama, sebagai satu kesatuan. Setelah beberapa refleksi, saya memutuskan bahwa lebih baik tidak meninggalkan implementasi otomatis dari tangkapan "Catur", tetapi untuk meningkatkan mekanisme untuk memindahkan kelompok potongan. Memang, untuk implementasi "pilar", Anda selalu dapat menambahkan ke dimensi lain (ini sangat mudah, selama modul visualisasi dipisahkan dari modul penghasil bergerak dan dari AI, maka Anda dapat menggunakan logika apa pun. untuk merender papan tiga dimensi ke dalam visualisasi dua dimensinya). Argumen tambahan yang mendukung keputusan ini adalah bahwa gerakan “tumpukan tinggi” bukan satu-satunya jenis perjalanan kelompok. Misalnya, dalam fragmen papan " Pentago " dapat diputar bersama-sama dengan potongan yang dipasang di atasnya.


Merangkum, saya dapat mengatakan bahwa, untuk kerangka permainan saya, saya memutuskan untuk mengambil semua yang terbaik yang telah dipikirkan di ZoG, Axiom, dan Ludi, dan menambahkan apa pun, yang menurut saya, tidak ada.

Pindahkan generasi

Move generation mirip dengan pemrograman non-deterministik . Tugas generator gerakan menyediakan, atas permintaan, daftar semua kemungkinan perpindahan dari posisi saat ini. Perpindahan mana dari daftar ini yang akan dipilih oleh pemain atau AI bukan fungsinya. Mari kita lihat bagaimana generasi gerakan dilakukan dalam ZoG. Sebagai contoh, kami mengambil langkah makro untuk bagian jangka panjang (ratu atau uskup). Ini adalah bagaimana ia digunakan dalam menentukan gerakan untuk potongan-potongan ini:

 (piece (name Bishop) (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp" Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp") (moves (slide ne) (slide nw) (slide se) (slide sw) ) ) 

Sebagai parameter, makro dilewatkan arah gerakan di papan tulis. Jika Anda tidak mempertimbangkan kemungkinan untuk memasang potongan-potongan baru di papan tulis, pembuatan langkah terlihat sederhana. Untuk masing-masing bagian di papan tulis, semua gerakan yang mungkin sesuai dengan aturan dihitung. Kemudian keajaiban dimulai ...

Setiap definisi dapat ditambahkan ke daftar sejumlah gerakan yang mungkin! Menambahkan langkah ke daftar dilakukan dengan perintah add (pada saat yang sama memposisikan setiap bagian yang bergerak di papan). Saya sudah menulis tentang bagaimana solusi arsitektur ini sangat buruk. Perintah untuk pembentukan langkah harus dipisahkan dari perintah yang memanipulasi potongan (seperti yang dilakukan dalam Aksioma). Mari kita lihat cara kerja makro:

 (define slide ( $1 (while empty? add $1 ) (verify not-friend?) add )) 

Pertama, perpindahan dilakukan oleh satu sel, dalam arah yang diberikan, kemudian dalam siklus ruang yang dicapai diperiksa untuk tidak adanya potongan-potongan di atasnya, bergerak terbentuk, dan pengaturan berlanjut ke sel lain dalam arah yang sama. Jika Anda berhenti di sini, bidak dapat "meluncur" melalui sel-sel kosong, tetapi bagaimana Anda bisa mengambil bidak musuh?

Sangat sederhana! Setelah menjalankan perintah verifikasi, verifikasi bahwa bidang tersebut tidak ditempati oleh bagian yang ramah, kami membentuk perintah tambahan lain, menyelesaikan langkah. Jika pada sel ini ditemukan bagian musuh, itu akan diambil secara otomatis (seperti pada satu ruang papan, pada satu waktu, Anda tidak dapat memiliki lebih dari satu bagian). Jika bagian itu ramah, perhitungan langkah akan dibatalkan dengan perintah verifikasi (pelanggaran terhadap kondisi yang ditentukan dalam perintah ini segera mengakhiri perhitungan langkah saat ini).

Z baik ZoG dan Aksioma, seseorang hanya dapat memindahkan kepingannya sendiri (atau lebih tepatnya, memindahkan kepingan lawan dimungkinkan, tetapi hanya jika ditentukan dalam mode perhitungan kepindahan salah satu kepingannya sendiri). Saya menemukan ini sebagai batasan yang sangat tidak nyaman, karena ada banyak permainan di mana Anda dapat langsung memindahkan bagian lawan (dalam " Stavropol Checkers ", misalnya). Akan lebih konsisten untuk melakukan perhitungan langkah untuk semua bagian, terlepas dari afiliasinya. Di makro yang menentukan langkah, seseorang hanya perlu menambahkan satu centang untuk memungkinkan hanya memindahkan bagiannya sendiri:

 (define slide ( (verify friend?) $1 (while empty? add $1 ) (verify not-friend?) add )) 

Penting adalah kemampuan untuk melakukan gerakan yang terdiri dari beberapa gerakan "parsial". Dalam implementasi draft, kemampuan ini digunakan untuk melakukan tangkapan "rantai":

 (define checker-jump ($1 (verify enemy?) capture $1 (verify empty?) (if (not-in-zone? promotion-zone) (add-partial jumptype) else (add-partial King jumptype) ) ) ) 

Perintah move parsial dibentuk dengan add-partial (untuk perintah ini, serta untuk perintah add, ada variasi dari langkah tersebut, dengan "transformasi" potongan-potongan). Langkah seperti itu selalu merupakan bagian dari langkah "komposit" yang lebih besar. Sebagai aturan, untuk gerakan selanjutnya, "mode" diatur, yang harus diimplementasikan kelanjutan. Jadi pada checker, tangkapan hanya dapat dilanjutkan dengan tangkapan berikut tetapi tidak dengan gerakan "lunak" (tidak menangkap).


Sistem deskripsi aturan seperti itu sangat fleksibel, tetapi kadang-kadang diperlukan logika yang lebih kompleks. Sebagai contoh, jika sambungan, selama "parsial" kemajuan tidak boleh melewati kembali bidang yang sebelumnya dilalui, adalah logis untuk menggunakan bendera yang terkait dengan posisi di papan tulis. Setelah mengunjungi ruang, kami menetapkan bendera, jadi selanjutnya tidak pergi ke ruang ini lagi:

 (verify (not-position-flag? my-flag)) (set-position-flag my-flag true) 

Selain bendera "posisional", di ZoG Anda dapat menggunakan bendera global. Kemampuan ini tidak harus disamakan dengan atribut potongan. Tidak seperti yang terakhir, ini bukan bagian dari kondisi permainan. Sayangnya, kedua atribut potongan dan bendera di ZoG hanya bisa boolean (dalam atribut aksioma bahkan tidak didukung). Keterbatasan ini membuat sulit untuk melakukan operasi yang terkait dengan berbagai jenis penghitungan. Misalnya, dalam teka-teki kecil ini , saya harus menggunakan untuk “menghitung” keping, terjebak dalam “garpu”, sepasang bendera boolean (jumlah persis yang tidak saya butuhkan, asalkan kepingannya lebih dari satu).

Hal lain yang harus diperbaiki adalah kurangnya “siklus hidup” yang jelas dalam pelaksanaan langkah tersebut. Semua flag secara otomatis diatur ulang sebelum memulai langkah, tetapi akan lebih mudah untuk mengidentifikasi dengan jelas fase inisialisasi. Menurut pendapat saya, dalam perhitungan langkah, harus ada fase berikut:

1. Inisialisasi variabel dan memeriksa prasyarat untuk langkah komposit
2. Inisialisasi variabel dan memeriksa prasyarat untuk langkah parsial
3. Generasi dari gerakan parsial
4. Memeriksa kondisi akhir dari gerakan parsial
5. Menghasilkan, menyelesaikan, dan memeriksa postconditions dari langkah komposit
6. Memeriksa kondisi penghentian permainan

Kelompok langkah dari yang kedua ke yang keempat, dalam gerakan komposit penuh, dapat diulang berkali-kali. Gagasan pra-dan pasca-kondisi, yang saya sebut invarian, saya ambil dari proyek Ludi. Saya bercerita lebih banyak tentang penggunaan invarian.

Tentang pentingnya notasi

Generasi dari semua kemungkinan pergerakan dari posisi hanya setengah dari cerita. Untuk mengontrol keadaan gim, diperlukan presentasi ringkas dari gerakan yang dihasilkan. Dalam ZoG, untuk tujuan ini, notasi ZSG digunakan. Berikut ini adalah catatan kemungkinan awal permainan catur dalam bentuk ini:

 1. Pawn e2 - e4 1. Pawn e7 - e5 2. Knight g1 - f3 2. Knight b8 - c6 3. Bishop f1 - c4 3. Knight g8 - f6 4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0 4. Pawn d7 - d5 5. Pawn e4 x d5 5. Knight f6 x d5 

Skrip ini dekat dengan notasi catur biasa dan umumnya ramah pengguna. Hanya langkah keempat putih yang dapat menyebabkan kebingungan. Jadi di ZSG sepertinya seperti castling . Bagian dari deskripsi langkah sebelum karakter '@' cukup jelas; itu adalah gerakan serentak benteng dan raja, tetapi apa yang terjadi selanjutnya? Jadi, dalam ZSG, sepertinya diperlukan reset atribut dari potongan-potongan untuk mencegah kemungkinan castling berulang.


Rekaman langkah dalam notasi ZSG harus berisi informasi lengkap yang cukup untuk mengubah keadaan game dengan benar. Jika informasi tentang perubahan atribut hilang, dalam permainan sesuai dengan catatan seperti itu, suatu langkah bisa diulang secara tidak benar (misalnya, pemain akan memiliki kesempatan untuk mengeksekusi kembali castling). Sayangnya, dalam ekstensi DLL (seperti Aksioma), informasi tambahan tidak dapat dikirim.

Bekerja dengan ekstensi DLL, ZoG dipaksa untuk membuat manipulasi yang cukup cerdik ketika memposisikan ke langkah yang dipilih (misalnya, ketika Anda memutar mundur suatu langkah). Dari [setiap] posisi sebelumnya [bekerja dari awal permainan], semua gerakan yang mungkin dihasilkan, dan kemudian, dalam daftar itu, seseorang harus mencari gerakan dengan representasi ZSG [yang sesuai]. Efek samping [masing-masing] yang dihasilkan diterapkan ke kondisi permainan [setiap berturut-turut], karena dimungkinkan untuk melakukan efek samping yang tidak tercermin dalam representasi ZSG gerakan tersebut.

Situasi ini diperparah oleh fakta bahwa satu-satunya cara untuk mencapai keadaan permainan pada saat bergerak di masa lalu, adalah aplikasi yang konsisten dari semua gerakan dari awal permainan, ke keadaan awal papan. Dalam kasus yang sangat kompleks , navigasi semacam ini tidak terjadi dengan cepat. Kerugian lain dari notasi ZSG dapat diilustrasikan dengan merekam langkah berikut dalam permainan Go :

 1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19 

Di sini, di posisi G19, sebuah batu putih ditempatkan yang menangkap sekelompok batu hitam. Karena semua bagian yang terlibat dalam kinerja penempatan harus disebutkan dalam kinerja ZSG, catatan belokan mungkin tampak sangat panjang (dalam Go, satu tetes dapat menangkap hingga 360 batu). Untuk apa ini dapat menyebabkan, saya menulis sebelumnya . Ukuran buffer yang dialokasikan untuk merekam gerakan ZoG, mungkin tidak cukup. Selain itu, jika karena alasan tertentu urutan pemindahan batu berubah (dalam proses pengembangan permainan itu terjadi), upaya untuk menerapkan langkah, dari urutan tangkapan lama, akan gagal.

Untungnya, ada cara sederhana untuk menangani semua masalah ini. Mari kita lihat bagaimana mendefinisikan gerakan potongan di ZRF:

 (piece (name Pawn) (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp" Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp") (moves (Pawn-capture nw) (Pawn-capture ne) (Pawn-move) (En-Passant e) (En-Passant w) ) ) 

Nama gerakan, didefinisikan dalam makro ZoG, tidak dapat diakses sebagai generator gerakan. Tapi apa yang mencegah kita menyerah pada makro dan membuat deskripsi gerakan dengan nama mereka? Begini cara catatan mencari permainan catur:

 1. e2 - e4 Pawn-move 1. e7 - e5 Pawn-move 2. g1 - f3 leap2 n nw 2. b8 - c6 leap2 n ne 3. f1 - c4 slide nw 3. g8 - f6 leap2 n nw 4. e1 - g1 OO 4. d7 - d5 Pawn-move 5. e4 x d5 Pawn-capture nw 5. f6 x d5 leap2 w nw 

Manfaat dari catatan semacam itu tidak jelas, tetapi memiliki satu keuntungan penting. Semua gerakan dijelaskan dengan cara yang seragam dan deskripsi ini tidak mengandung tambahan apa pun (nama deskripsi gerakan, tentu saja, dapat dibuat lebih “deskriptif”). Dalam deskripsi castling, seseorang berhasil menyingkirkan perubahan atribut dan deskripsi rook move (deskripsi ini tidak lagi tergantung pada detail implementasi dari move). Kegunaan yang lebih jelas dari catatan semacam itu ada dalam kasus permainan Go:

 1. G19 drop-to-empty White Stone 

Dan itu dia! Jika batu lawan diambil sesuai dengan aturan permainan, tidak perlu mendaftar semuanya dalam deskripsi langkah. Cukup untuk menunjukkan ruang awal dan akhir perpindahan (mungkin dengan tanda untuk mengambil), nama langkah pelaksana dan garis parameter yang diteruskan ke sana. Tentu saja, untuk melakukan pemindahan sesuai dengan deskripsi ini, untuk decoding, perlu mengakses modul pemindahan pemindahan, tetapi ZoG melakukannya!

Kemungkinan lain, yang harus didukung, muncul dalam fungsi gerakan "parsial". Berikut adalah contoh dari " catur Rusia ":

 1. Checker g3 - f4 1. Checker f6 - g5 2. Checker e3 - d4 2. partial 2 Checker g5 - e3 = XChecker on f4 2. Checker e3 - c5 = XChecker on d4 x d4 x f4 

Di sini orang kulit hitam, pada langkah kedua mereka, ambil dua bagian pada d4 dan f4. "Transformasi" awal dari karya-karya ini ke XChecker adalah fitur dari implementasi ini dan berfungsi untuk mencegah pengambilan kembali potongan-potongan "yang dikalahkan" pada langkah yang sama. Ungkapan "parsial 2" menggambarkan awal dari kursus "komposit", yang terdiri dari dua gerakan "parsial". Bentuk uraian ini tidak nyaman, karena pada saat generasi gerakan pertama, panjang urutan gerakan "parsial" mungkin tidak diketahui. Begini cara uraian ini dalam format baru:

 1. g3 - f4 checker-shift nw 1. f6 - g5 checker-shift ne 2. e3 - d4 checker-shift nw 2. + g5 - e3 checker-jump nw 2. + e3 - c5 checker-jump sw 2. + 

Detail implementasi terkait dengan "transformasi" karya tidak relevan. Penangkapan potongan juga tidak ditentukan, seperti pada catur, penangkapan terjadi sebagai "efek samping" dari gerakan potongan dan tidak sesuai dengan "prinsip catur." Kemajuan sebagian akan dikodekan dengan simbol "+" di awal. dari garis. Satu-satunya "+" menunjukkan penyelesaian dari suatu "langkah komposit" (pada kenyataannya, ini adalah langkah "parsial" biasa, berisi langkah yang hilang, string kosong).

Jadi, dengan menggunakan aturan yang disebutkan untuk implementasi gerakan, seseorang telah berhasil membuat notasi universal, sepenuhnya memenuhi persyaratan kami. Tentu saja, itu tidak ada hubungannya dengan catur standar atau dengan notasi lainnya, tetapi kebetulan notasi konvensional untuk catur, catur dan permainan lainnya juga tidak ada hubungannya dengan satu sama lain. Modul visualisasi selalu dapat mengubah catatan pindah ke bentuk yang lebih akrab diterima untuk game tertentu. Konversi juga dapat menjadi beberapa bentuk universal, seperti SGF (Smart Game Format) .

Siklus hidup game

Selain informasi tentang menempatkan potongan-potongan di papan tulis, urutan belokan adalah bagian penting dari status permainan, variabel dalam proses permainan. Dalam kasus yang paling sederhana (dan paling umum), untuk menyimpan informasi ini satu bit sudah cukup, tetapi ZoG menyediakan beberapa peluang lagi untuk mengimplementasikan kasus yang lebih kompleks. Di sini adalah bagaimana deskripsi urutan bergerak bisa mencari permainan Splut! :

 (players South West North East) (turn-order South West West repeat North North North East East East South South South West West West ) 

Dalam permainan ini, setiap pemain membuat tiga gerakan pada satu waktu, tetapi jika Anda memberi pemain pertama kesempatan untuk membuat tiga gerakan dari posisi awal, ia akan dapat menghancurkan salah satu potongan lawan, yang akan memberinya keuntungan yang signifikan. Untuk alasan ini, pemain pertama harus membuat hanya satu gerakan (ini memberikan kesempatan untuk bersiap menyerang pemain lawan, tetapi tidak menyerangnya), yang kedua - dua gerakan (ini juga tidak cukup untuk menyerang pemain lawan), setelah dimana setiap pemain selalu membuat tiga gerakan.


Label repeat menunjukkan awal dari urutan gerakan berulang yang berulang. Jika tidak muncul, seluruh deskripsi diulangi secara berulang. ZoG tidak memungkinkan penggunaan label berulang lebih dari satu kali. Fitur penting lainnya adalah spesifikasi urutan belokan. Begini cara uraian urutan putaran permainan di mana setiap pemain melakukan dua putaran (langkah pertama - gerakan bergerak, gerakan kedua - menangkap potongan lawan) terlihat:

 (players White Black) (turn-order (White normal-move) (White capture-move) (Black normal-move) (Black capture-move) ) 

Ada satu lagi kemampuan yang terkait dengan deskripsi memindahkan potongan orang lain, tetapi sangat tidak nyaman untuk digunakan. Masalahnya adalah deskripsi seperti itu tidak memiliki alternatif. Jika deskripsi menyatakan bahwa langkah itu harus dilakukan oleh bagian musuh, pemain harus melakukan langkah ini! Dalam ZoG, tidak mungkin untuk menggambarkan pilihan untuk memindahkan miliknya sendiri atau milik orang lain. Jika kemampuan seperti itu diperlukan dalam permainan (seperti dalam " Stavropol Checkers "), perlu untuk membuat semua bagian netral (menciptakan untuk tujuan ini pemain yang tidak berpartisipasi dalam permainan) dan menentukan kesempatan bagi semua pemain untuk peluang untuk memindahkan bagian yang netral. Saya telah mengatakan di atas bahwa jauh lebih mudah secara default untuk memungkinkan semua pemain kemampuan untuk memindahkan setiap bagian (milik mereka sendiri maupun milik lawan mereka) dengan menambahkan pemeriksaan yang diperlukan dalam algoritme pembangkit bergerak.

Seperti yang Anda lihat, kisaran opsi yang disediakan oleh ZoG untuk deskripsi urutan belokan sangat terbatas. Aksioma juga gagal menambahkan fitur baru, karena (biasanya) berjalan di atas ZoG. Ludi, dalam hal ini, bahkan lebih miskin. Untuk memaksimalkan penyatuan aturan permainan (diperlukan untuk kemungkinan menggunakan algoritma generik), dalam proyek ini, semua kemampuan deskriptif sengaja disederhanakan, yang telah menyebabkan penghapusan seluruh lapisan permainan.


" Bao Swahili " adalah contoh yang baik dari sebuah game dengan siklus hidup yang kompleks. Dalam game ini, ada dua fase dengan aturan untuk eksekusi bergerak yang berbeda secara signifikan. Di awal permainan, bagian dari batu adalah "di tangan" "Dari masing-masing pemain. Sementara masih ada batu" di tangan ", batu dimasukkan ke dalam sumur, satu batu pada satu waktu. Ketika batu" di tangan "habis, fase kedua permainan dimulai, dengan distribusi dimasukkan Orang tidak dapat mengatakan bahwa permainan ini tidak dapat dijelaskan dalam ZRF (bahasa deskripsi ZoG), tetapi karena keterbatasan ZoG, implementasi ini akan sangat membingungkan (yang tentunya tidak terbaik untuk kualitas pekerjaan AI). Mari kita lihat bagaimana deskripsi game seperti itu akan terlihat di "dunia ideal":

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (label phase-ii) (turn-order (South p-ii-move) (North p-ii-move) ) ) 

Di sini, setiap daftar turn-order menentukan urutan gerakan yang berulang (membedakan dirinya dengan mode eksekusi bergerak). Label kata kunci mendefinisikan label yang dapat dibuat transisi selama pembuatan langkah terbaru. Anda mungkin memperhatikan bahwa di sini kita melanjutkan dari asumsi implisit bahwa transisi seperti itu selalu terjadi setelah perpindahan pemain kedua (jika tidak maka akan melanggar urutan gerakan). Bagaimana cara melakukan transisi ke fase berikutnya pada waktu yang sewenang-wenang?

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (turn-order (labels - phase-ii) (South p-ii-move) (labels phase-ii -) (North p-ii-move) ) ) 

Di sini, label dilakukan dalam badan loop dan terdiri dari dua nama. Nama label dalam daftar label muncul dalam urutan transfer pemain dalam daftar pemain. Nama yang digunakan untuk transisi ditentukan oleh pemain mana yang melakukan langkah terakhir. Jika ini adalah Utara, itu akan beralih ke label pertama, jika tidak, ke yang kedua. Jika salah satu nama dalam label tidak akan digunakan, posisi yang sesuai dapat diisi dengan tanda hubung.


Aspek penting dalam pengelolaan gerakan bergantian, adalah kemampuan untuk melakukan putaran berulang. Dalam gim keluarga Tables , seperti Nard , Backgammon , atau Ur , misalnya, kemampuan untuk melakukan belokan berulang adalah elemen penting dari taktik gim. Di ZoG kita dapat menggunakan passing untuk meniru fitur ini, tetapi pendekatan ini secara signifikan menyulitkan deskripsi permainan (terutama dengan lebih banyak pemain). Akan jauh lebih logis untuk menggunakan label untuk mengulangi belokan:

 (players South North) (turn-order (label repeat) South (label repeat) North ) 

Permainan setelah melompat ke label repeat, pemain akan kembali memainkan gilirannya (label yang paling dekat dengan posisi saat ini dalam daftar putaran akan berlaku). Saya suka pendekatan Perl dalam definisi implisitnya. Pembuatan struktur kontrol yang tersirat dapat menyederhanakan deskripsi game secara signifikan. Sejauh gerakan berulang dapat digunakan dalam banyak permainan, label ulangi, mengantisipasi kemungkinan pengulangan setiap belokan dapat tersirat:

 (players South North) (turn-order South North ) 

Selain itu, karena urutan belokan sepenuhnya konsisten dengan urutan tertulis dari pemain dalam susunan pemain, Anda dapat secara otomatis menghasilkan seluruh frase urutan belokan:

 (players South North) 

Semakin mudah deskripsinya untuk menulis, semakin baik.

Invarian yang mudah pecah

Hal utama yang saya tidak suka di ZoG dapat diekspresikan dengan satu kata - skakmat. Pada pandangan pertama, itu hanya suatu kondisi (sangat umum dalam permainan keluarga catur ) yang menghubungkan akhir permainan dengan pembentukan situasi pasangan. Sayangnya, pada pemeriksaan lebih dekat, kesederhanaan menunjukkan dirinya menipu. Penggunaan kata kunci ini berarti tidak hanya kinerja, setelah setiap gerakan, dari cek untuk penyelesaian permainan, tetapi juga membebani pemain "perilaku" tertentu.


Dari Shogi yang biasa, permainan ini hanya berbeda dalam jumlah pemain. Sayangnya, perbedaan ini cukup untuk membuat tugas menentukan skakmat (dan semua yang terkait dengan kata "ajaib") salah. Memverifikasi sedang dalam pemeriksaan dilakukan hanya terkait dengan salah satu pemain. Akibatnya, raja bisa datang untuk diserang, dan dimakan [oleh kombinasi giliran lawan bahkan ketika tidak ditinggalkan di "periksa"]! Bahwa ini tidak optimal akan tercermin dalam karya AI.

Jika masalah ini tampaknya tidak signifikan, perlu diingat koalisi biasanya dibentuk dalam permainan empat pemain "berpasangan dengan pasangan". Dalam kasus pembentukan koalisi, kita harus mempertimbangkan bahwa potongan-potongan yang ramah kepada raja tidak mengancamnya! Jadi, misalnya, dua Raja yang bersahabat mungkin tinggal di ruang tetangga papan.


Menjadi lebih rumit dari sebelumnya jika seorang pemain memiliki beberapa raja. Dalam " catur Tamerlane ", pion kerajaan berubah menjadi pangeran (sebenarnya, raja kedua). Jika ini terjadi, Anda hanya bisa menang dengan menangkap raja pertama (salah satu dari keduanya), dan mengawinkan yang kedua. Dalam game ini, Anda bahkan bisa mendapatkan raja ketiga, menghabiskan dua kali lipat untuk transformasi "pion pion"! Kemampuan ekspresif "skakmat" tidak cukup untuk menggambarkan situasi ini secara memadai.

Kesulitan lain mungkin adalah proses memberi pasangan. Jadi dalam catur Mongolia ( Shatar ), hasil percobaan pasangan tergantung pada urutan di mana potongan-potongan mengeksekusi "cek" berurutan. Hasilnya bisa terbukti menang atau seri (seperti jodoh oleh pion), atau bahkan kalah (jodoh dilarang, tetapi Anda bisa memberi cek). Dalam hal ini, yang kurang eksotis adalah Shogi Jepang. Dalam game ini, dilarang memberi jodoh dengan pion yang jatuh, tetapi Anda bisa memberi cek dengan pion yang dijatuhkan dan memberikan jodoh dengan pion yang dipindahkan.


Jelas, seseorang harus memisahkan logika verifikasi akhir pertandingan dari tes karena raja telah jatuh ke dalam pemeriksaan, yang merupakan aturan yang tidak berubah yang diperiksa setelah setiap belokan. Pelanggaran aturan membuatnya tidak mungkin untuk melakukan langkah tersebut (langkah tersebut dihapus dari daftar langkah yang tersedia). Jadi tes (disederhanakan) untuk seorang raja yang sedang diperiksa mungkin terlihat seperti ini untuk "catur Tamerlane":

 (verify (or (> (count (pieces my? (is-piece? King))) 1) (= (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

Penting untuk dipahami bahwa tes ini harus dilakukan hanya untuk raja sendiri (saya menggunakan predikat saya ?, karena teman predikat ?, dengan dukungan untuk koalisi, akan puas tidak hanya untuk bagian sendiri, tetapi juga untuk semua pemain yang ramah). Dapat diterima (dan diinginkan, [jika ada beberapa raja ramah]) adalah situasi di mana raja musuh jatuh di bawah kendali, setelah pindah, tetapi oleh raja sendiri. Situasi ini seharusnya tidak mungkin [kecuali ada beberapa raja yang ramah]! Setelah memberikan dukungan untuk memeriksa aturan seperti itu, memeriksa penyelesaian game dengan skakmat menjadi sepele. Jika tidak ada gerakan yang mungkin dan raja [satu-satunya] berada dalam kendali, permainan berakhir [jika raja itu milik pemain bertahan terakhir dari koalisi bertahan kedua terakhir]:

 (loss-condition (and (= (count moves) 0) (= (count (pieces my? (is-piece? King)) 1) (> (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

Kemampuan untuk menentukan invarian akan berguna di gim lain, seperti di gim . Kesulitan terbesar dalam implementasi permainan keluarga ini, terkait dengan penerapan "aturan mayoritas". Di hampir semua draf gim, menangkap adalah wajib. Juga, di sebagian besar permainan keluarga ini, ada penyelesaian karakteristik "tangkapan rantai" dalam satu putaran. Pemeriksa, setelah ditangkap, terus mengambil potongan lainnya, jika mungkin. Dalam sebagian besar permainan, pemain diharuskan untuk melakukan penangkapan berantai sampai akhir, tetapi ada pengecualian untuk aturan ini, misalnya, Fanorona .


Menggunakan mekanisme gerakan parsial, menerapkan "tangkapan rantai" cukup sederhana. Kesulitan muncul ketika, selain itu, seseorang memaksakan suatu kondisi di mana, dari semua opsi yang mungkin, seseorang harus memilih rantai di mana jumlah maksimum potongan ditangkap. Dalam ZoG, logika ini harus diimplementasikan dari awal di tingkat "hardcoding":

 (option "maximal captures" true) 

Pengaturan ini cocok untuk " catur internasional ", tetapi dalam " catur Italia " aturan mayoritas dirumuskan secara berbeda. Dalam versi gim ini, jika ada beberapa opsi untuk jumlah tangkapan yang sama, Anda harus memilih opsi yang menangkap jumlah raja yang lebih banyak yang diubah (raja). Pengembang ZoG telah menyediakan ini. Anda memasukkan pengaturan berikut:

 (option "maximal captures" 2) 

Dalam pengaturan ini, seseorang tidak hanya menghitung jumlah potongan yang diambil, tetapi juga tipenya. Sayangnya, tidak semuanya bisa diramalkan. Inilah cara "aturan mayoritas" dirumuskan dalam "catur Prancis kuno":

Jika dengan serangkaian tangkapan dimungkinkan untuk menangkap jumlah biji yang sama dengan orang sederhana atau dengan raja, pemain harus menggunakan raja. Namun, jika jumlah biji sama dalam kedua kasus, tetapi dalam satu ada raja musuh (atau ada lebih banyak), pemain harus memilih opsi ini, bahkan jika penangkapan kemudian dilakukan dengan menggunakan pemeriksa sederhana, dan tidak menggunakan raja.

Tentu saja, pada saat ini, hampir tidak ada yang memainkan versi checker ini, tetapi keberadaannya dengan jelas menunjukkan kekurangan implementasi “hardcoded”. Menggunakan mekanisme invarian memungkinkan untuk semua opsi yang memungkinkan untuk "aturan mayoritas" secara universal. Untuk " catur Prancis lama " implementasi akan sebagai berikut:

 (verify (>= capturing-count max-capturing-count) ) (if (> capturing-count max-capturing-count) (let max-capturing-count capturing-count) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= capturing-sum max-capturing-sum) ) (if (> capturing-sum max-capturing-sum) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= attacking-value max-attacking-value) ) (let max-attacking-value attacking-value) 

Di sini, kami mengasumsikan bahwa aturan untuk pembuatan tangkapan dengan benar mengisi variabel lokal [berikut]:

• capturing-count - total potongan yang ditangkap
• capturing-sum - jumlah raja yang ditangkap
• attacking-value - nilai penangkapan potongan

Terkait dengan masing-masing variabel ini adalah akumulator nilai, disimpan dalam variabel dengan awalan maks. Tiga cek dieksekusi secara seri. Pelanggaran terhadap salah satu kondisi verifikasi segera mengganggu pembuatan opsi belokan berikutnya (tangkapan tidak disimpan dalam daftar kemungkinan belokan). Karena pemeriksaan yang dilakukan terkait dengan nilai variabel, itu tidak cukup [untuk menguji hanya opsi penangkapan baru saat ini]. Setiap tes menghasilkan "aturan yang dapat ditekuk" yang terkait dengan tangkapan yang dihasilkan [yang dapat merevisi nilai maksimum terakumulasi]. Setelah setiap perubahan dalam akumulator apa pun, semua aturan terkait harus diperiksa lagi [untuk setiap opsi dalam daftar]. Jika ada kondisi yang dilanggar untuk opsi yang dibuat sebelumnya, opsi itu harus dihapus dari daftar opsi belok yang mungkin.

Kesimpulan

Ini adalah terjemahan dari artikel saya tahun 2014 tahun. Sejak itu, saya telah memikirkan kembali banyak hal dan proyek Dagaz telah menjadi kenyataan, tetapi saya tidak mengubah apa pun dalam teks. Artikel ini diterjemahkan oleh teman saya Howard McCay dan saya berterima kasih padanya untuk pekerjaan yang dilakukan.