Halo!



Kami sedang dalam studi sarjana tahun pertama kami di Matematika Terapan dan Informatika di St. Petersburg HSE. Saat mengerjakan proyek tim semester di C ++, kami memutuskan untuk menulis Intellector versi komputer dengan bot - permainan catur di papan heksagonal dengan gambar khusus.



Pada artikel kali ini kita akan membahas tentang bagaimana perkembangan dari game tersebut, bagaimana cara menjinakkan hexagonal board, cara menggambar di command line, dan juga bagaimana kita membuat bot yang hampir tidak bisa kita kalahkan.







Ada 3 orang di tim kami: Yura Khudyakov, Valera Golovin, Misha Savrasov. Bagi kita masing-masing, ini adalah proyek tim pertama, jadi dalam proses kerja kita tidak hanya menulis tentang para profesional, tetapi juga belajar bekerja dalam tim dan menggunakan sistem kontrol versi (dalam kasus kita - git). Proyek ini memiliki sejumlah keanehan, khususnya sepeda - ada solusi bagus yang sudah jadi yang dapat digunakan. Namun, tujuan proyek kami adalah untuk mendapatkan pengalaman, jadi kami menemukan dan menerapkan banyak hal sendiri.

Apa itu Intellector?

Untuk memulainya, ada baiknya menjelaskan jenis game yang kami tulis.



Game "Intellector" telah muncul baru-baru ini dan masih mendapatkan popularitas. Kejuaraan terbuka pertama diadakan di St. Petersburg tahun ini .





Intellector berbeda dari catur dalam struktur lapangan, aturan dan sekumpulan bidak. Namun, banyak elemen yang serupa: misalnya, ada sosok Progressor di dalam game yang berperan sebagai Pion. Dia hanya berjalan ke depan dan dapat berubah menjadi sosok lain ketika dia mencapai baris ekstrim.



Raja di sini adalah sosok yang disebut Intellector. Tujuan dari permainan ini adalah untuk memotong bidak ini, bukan menskakmatnya (walaupun ini hampir sama).



Perbedaan dalam mekanisme permainan muncul dari kekhususan lapangan. Bidang Akal simetris, yang secara signifikan membedakannya dari catur dengan sisi raja dan sisi ratu.



Untuk memahami artikel ini, pengetahuan tentang aturan dan kemampuan bermain tidak diperlukan.

Arsitektur umum

Apa yang kita inginkan dalam aplikasi kita?

Agar game dapat bekerja, Anda perlu mengimplementasikan komponen utamanya: logika game. Ini termasuk model papan dan aturan bergerak. Selain itu, untuk kenyamanan, ada baiknya menyimpan riwayat pemindahan dan menerapkan undo / redo.



Papan harus ditampilkan dan diizinkan pengguna untuk bermain. Ini dilakukan oleh komponen grafis permainan - antarmuka. Antarmuka yang ramah pengguna harus memiliki menu dan pengaturan.



Bagaimanapun, Anda membutuhkan lawan untuk bermain. Kami memutuskan untuk membuat bot untuk tujuan ini agar pemain dapat bersaing dengan komputer. Dalam hal ini, kompleksitas bot harus dapat disesuaikan.

Rencana aplikasi:

1. Logika permainan
   • Model papan heksagonal
     
     Disimpan sebagai susunan dua dimensi sel heksagonal
   • Aturan untuk bidak bergerak
     
     Memeriksa diterimanya suatu kepindahan, mendapatkan semua gerakan yang tersedia untuk satu bidak, untuk seorang pemain
   • Pindah riwayat
     
     Urungkan dan ulangi pemindahan
2. Antarmuka
   
   Direncanakan 2 antarmuka: ncurses dan Qt. Hanya ncurses yang diimplementasikan dalam proyek ini, lihat bagian Antarmuka untuk detailnya.
   • Menampilkan bidang Merender
     
     dan memperbarui bidang di konsol
   • Gerakkan kursor dengan tombol keyboard, mainkan tanpa mouse
   • Menampilkan sejarah teks bergerak
   • Menampilkan menu utama
3. Bot
   • Bot acak
   • Bot serakah
   • Bot alfa-beta
     
     Dioptimalkan untuk mengulangi semua gerakan

Bagaimana caranya?

Arsitektur aplikasi yang sangat sederhana dijelaskan oleh diagram ini:





Bagian Game bertanggung jawab atas semua logika game dan menyimpan papan.



Saat game dengan komputer dihidupkan, Game berinteraksi dengan bot dari Bot



Controller, mengambil data tentang game dari Game dan mentransfernya ke Antarmuka untuk ditampilkan kepada para pemain. Antarmuka, pada gilirannya, mengembalikan hasil interaksi pengguna kembali ke Game melalui Pengontrol.



Tautan perantara dalam bentuk pengontrol berguna ketika ada beberapa antarmuka (awalnya kami berencana membuat 2 antarmuka: konsol dan grafis). Mereka semua berkomunikasi dengan game dengan cara yang seragam melalui pengontrol, alih-alih masing-masing melakukannya secara berbeda.

Detail teknis

Model permainan

Papan heksagonal

Pertimbangkan bagian Game dari diagram di atas. Itu harus menyimpan papan dan menangani semua logika dalam game.



Untuk pemahaman yang lebih baik, Anda dapat membaca artikel dari mana kami mengambil ide ini.



Kami akan menyimpan seluruh papan dalam array sel dua dimensi, elemen yang diindeks oleh pasangan koordinat (w,h)seperti yang ditunjukkan pada gambar di bawah. Pemilihan koordinat seperti itu tampak alami, tetapi tidak nyaman untuk menggambarkan pergerakan bentuk (amati, misalnya, bagaimana koordinat berubah saat bergerak di sepanjang diagonal).





^{Koordinat sel di sepanjang sumbu horizontal wdan sumbu vertikalh}



Untuk memudahkan mendeskripsikan pergerakan gambar, kita akan menggunakan koordinat tiga dimensi. Mari kita pilih beberapa sel sebagai sel referensi dengan koordinat {0,0,0}(untuk kenyamanan, ini akan bertepatan dengan sel (0, 0)array).





^{Koordinat tiga dimensi sel relatif terhadap sel pusat dengan koordinat{0,0,0}}



Perpindahan sepanjang diagonal "dari kanan ke kiri, dari bawah ke atas" dilambangkan dengan koordinat x, perpindahan dari bawah ke atas dengan koordinat ydan perpindahan sepanjang diagonal "dari kiri ke kanan, dari bawah ke atas" dengan koordinat z. Saat berpindah ke sel yang berdekatan, koordinat terkait akan berubah satu per satu. Dengan demikian, setiap sel menerima tiga koordinat, seperti pada gambar di atas.



Dalam kasus ini, sel diberi nomor secara ambigu. Misalnya, jika dari sel pusat dengan koordinat {0,0,0}kita bergerak ke kiri ke bawah lalu ke atas, kita mendapatkan koordinat sel tersebut {0,1,-1}. Tetapi sel yang sama memiliki koordinat {1,0,0}jika Anda datang langsung dari sel pusat, seperti yang Anda lihat pada gambar sebelumnya.





^{Pilihan lain untuk menentukan koordinat sel {1,0,0}.}



Melintasi setiap sel dalam siklus "kiri-bawah" - "atas" - "kanan bawah" membawa kita ke sel yang sama, tetapi menambahkan vektor ke koordinatnya {-1,1,-1}, yang jumlah koordinatnya sama dengan -1. Melakukan mental seperti berjalan dalam arah yang sama atau berlawanan beberapa kali, kita dapat mengubah koordinat sel apa pun menjadi sel yang setara, yang akan berbeda dengan proporsional vektor {-1,1,-1}. Untuk menghilangkan ambiguitas, di setiap kelas ekivalensi, kami memilih sebagai perwakilan tiga koordinat, yang jumlahnya sama dengan nol. Pilihan koordinat ini unik (buktikan!).



Mari kita jelaskan lebih lanjut algoritma untuk mengubah dari koordinat dua dimensi menjadi koordinat tiga dimensi dan sebaliknya di dalam kelas Position.

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

Perhatikan bahwa konstruktor menghasilkan koordinat (x,y,z)yang berjumlah nol. Dalam kasus ini, konversi koordinat (x,y,z)agar (w,h)berfungsi dengan benar untuk setiap rangkaian koordinat (jumlahnya tidak harus sama dengan nol).



Bagaimana kami menemukan semua rumus ini? Dengan metode poke ilmiah: dengan menganalisis perubahan koordinat tiga dimensi ketika salah satu koordinat dua dimensi digeser oleh 1(konstruktor) dan ke arah yang berlawanan (metode).



Dengan menggunakan koordinat tiga dimensi, kita dapat dengan mudah memeriksa bahwa sel-sel tersebut collinear. Misalnya, untuk memeriksa bahwa dua sel terletak pada diagonal yang sama z, kita perlu menemukan vektor yang menghubungkan sel-sel ini dan memeriksa bahwa kelas ekivalennya berisi vektor bentuk{0, 0, z}... Z bisa apa saja - angka ini memberikan jarak antar sel. Akan sangat mudah untuk mengimplementasikan pemeriksaan pemindahan untuk ketepatan dan menemukan semua sel yang tersedia untuk pemindahan.



Dalam larik dua dimensi yang mewakili papan, kami akan menyimpan informasi tentang posisi gambar. Di setiap sel, jika ada bidak catur, kita akan menyimpan jenis dan warnanya.



Dalam implementasi kami di kelas papan, kami hanya menyimpan jenis potongan dalam sel. Kami membutuhkan kelas yang dapat menemukan semua gerakan yang mungkin untuk bidak di papan ini dan memeriksa kebenaran gerakan.

Bergerak demi potongan

Kami telah membuat kelas FigureMoveValidatoryang memiliki 6 pewaris untuk setiap jenis gambar (itu mungkin dilakukan tanpa ahli waris, jika dalam setiap metode kami membuat kasus sakelar untuk jenis gambar). Konstruktor kelas memiliki 2 parameter: posisi dan referensi papan. Juga di kelas ada dua metode allMovesdan checkMove.



Mari pertimbangkan metodenya allMoves. Untuk menemukan semua gerakan, mari buat larik vektor perpindahan yang mungkin dan melewatinya. Untuk bidak yang bergerak satu langkah, kita perlu memeriksa bahwa kita tidak melompat dari papan dan tidak masuk ke sel tempat bidak kita berada. Untuk gambar yang memindahkan beberapa sel dalam satu garis lurus, tambahkan vektor bergerak saat kondisi sebelumnya berlalu.



SekarangcheckMove... Kami ingat bahwa kami tahu bagaimana memeriksa apakah angka-angka tersebut berada pada garis lurus yang sama. Jika kami memeriksa bahwa tidak ada bidak lain di baris ini, maka kami mendapatkan metode siap pakai untuk Dominator (analog benteng). Jika bidak terletak pada satu garis lurus, maka kita dapat menemukan jarak di antara mereka, dan mendapatkan metode untuk Progressor (bidak), Defenser (berjalan seperti raja), Intelijen (raja, hanya tidak dapat memotong) dan Liberator (dapat berjalan melalui satu sel ke sel mana pun). sisi). Masih ada agresor (analogi gajah), yang bergerak ke dalam sel secara diagonal dalam enam arah dari yang sekarang (dari sel {0, 0, 0}ke {0, 1, 1}, ke {0, 2, 2}, dll.: Lihat sel abu-abu pada gambar di bawah). Untuk gambar ini, Anda dapat mencoba nol salah satu koordinat dan memeriksa bahwa 2 koordinat yang tersisa sama dalam nilai absolut (berkat koordinat tiga dimensi).





^{Langkah yang mungkin untuk penyerang}



Sekarang kita perlu mencari tahu apa yang harus dilakukan dengan gerakan tersebut. Mari buat kelas Pindah yang akan menyimpan semua informasi yang diperlukan untuk pemindahan. Kami memutuskan untuk menyimpan 2 posisi dan 4 buah: posisi dari mana bidak itu bergerak, posisi bidak itu akan datang, dan informasi tentang bidak mana yang berdiri di masing-masing sel ini dan mana yang akan berdiri setelah menerapkan pemindahan. Ini akan memudahkan penerapan sistem riwayat pemindahan dan rollback pemindahan.

Antarmuka

Arsitektur

Aplikasi ini ditulis di perpustakaan ncurses konsol (di sini adalah tutorial untuk itu ) . Library ini memungkinkan Anda membuat grafik pseudo di konsol. Misalnya, Midnight Commander dan Nano didasarkan padanya .



Pilihannya mungkin tampak sangat aneh: ada banyak perpustakaan lain, lebih indah, nyaman, dan lintas platform. Hal tersebut terkait dengan fakta bahwa pada awalnya kami berencana untuk membuat 2 interface: konsol dan grafis. Kami tidak berhasil menulis 2 antarmuka pada saat proyek dikirimkan dan sebagai gantinya membuat lebih banyak fitur di versi konsol. Meski secara arsitektural, aplikasinya masih didesain untuk antarmuka yang berbeda.



Ada 2 entitas utama: tampilan dan pengontrol... Pemetaan menunjukkan gambar kepada para pemain, dan pengontrol menengahi antara pemetaan yang berbeda dan model permainan internal.



Layar menangani semua interaksi pengguna: posisi dan gerakan kursor, pemilihan bentuk, penyorotan bidang yang tersedia, penyelesaian game, dan banyak lagi. Tindakan yang mempengaruhi papan merujuk ke pengontrol dan mengirim / menerima informasi yang diperlukan ke / dari model.



Layar membuat versi papannya sendiri, tetapi dengan parameter tambahan yang dibutuhkan, seperti posisi kursor dan warna sel. Parameter ini tidak dapat ditambahkan ke model utama karena pemetaan yang berbeda memerlukan parameter yang berbeda. Misalnya, di antarmuka konsol, Anda perlu menyimpan posisi kursor, tetapi tidak di antarmuka grafis, karena pemilihan dan pergerakan gambar dilakukan dengan mouse.



Inilah yang terjadi jika seorang pemain ingin mengetahui bidang yang tersedia untuk pindah:

1. Pemain menggerakkan kursor ke bidang gambar dan menekan bilah spasi
2. Bidang dengan bentuk ditandai sebagai dipilih
3. Antarmuka mengacu pada metode selectCellpada pengontrol
4. Metode selectCellmengacu pada metode allFigureMovesmodel
5. allFigureMovesmembuat FigureMoveValidatoryang menghitung semua gerakan yang tersedia
6. allFigureMoves transfer yang ditemukan bergerak kembali ke pengontrol
7. Pengontrol meneruskannya ke antarmuka
8. Antarmuka menggambar ulang bidang tersebut, menyorot bidang yang tersedia

^{Kursor berada di tengah papan: di atas kotak biru pucat. Sebelum memindahkannya ke posisi ini, pengguna memilih bentuk. Gerakan yang tersedia untuk itu disorot dengan warna hijau, dan sel yang dipilih itu sendiri berwarna ungu.}

Bagaimana cara menggambar lapangan?

Antarmuka konsol ditampilkan dalam jendela persegi panjang dengan baris teks. Jika Anda meletakkan simbol di tempat yang tepat dan mewarnainya, Anda mendapatkan gambar:





^{(Evil Pacman, digambar dengan huruf "o")}



Sebuah fungsi move(int y, int x)di ncurses mengubah posisi saat ini, dan fungsi tersebut addch(chtype c)menambahkan karakter dan menggeser posisi 1 saat ini ke kanan ( x —> x+1).



Gambar yang kompleks dapat disimpan sebagai larik dua dimensi dan ditampilkan baris demi baris: saat baris berakhir, pindahkan posisi saat ini ke awal baris berikutnya. Prinsipnya sangat mirip dengan mesin tik.



Di komputer pengguna, bidang dalam permainan kita akan diwarnai jika terminal mendukung warna dan atribut teks lainnya.



Ncurses memungkinkan pengembang untuk mengubah atribut teks ketika itu adalah output ke konsol (warna, tebal, berkedip). Untuk melakukan ini, tulis kode:

attron( *attributes* );
addch(c);
attroff( *attributes* );

Setiap simbol memiliki warna dan warna latarnya masing-masing. Konsol modern mendukung maksimal 256 warna, sehingga Anda harus bekerja dengan terbatas set : cukup menyedihkan dalam hal desain warna.



Gambar untuk keluaran dapat disimpan dalam kode (seperti yang kita lakukan pada awalnya), atau dapat disimpan dalam file terpisah dan dibaca dari mereka ketika program dimulai. Untuk ini, kami telah membuat format file kami sendiri *.btn.



Ini menyimpan gambar teks yang akan dibaca dan ditampilkan oleh game. Misalnya, bentuk, atau tulisan "Putih menang" / "Hitam menang", atau tombol menu. Dalam kasus ini, terkadang Anda mungkin membutuhkan transparansi agar tidak menimpa apa yang telah digambar sebelumnya. Untuk melakukan ini, Anda dapat menambahkan hash di baris pertama #dan setelah daftar simbol "transparan" yang akan diabaikan dalam keluaran.



Misalnya, kita memiliki 3 persegi panjang yang digambar di layar:





Tambahkan persegi panjang dari file berikut ke tengah:

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

Dan kami mendapatkan gambar berikut:





^{(disorot dengan warna kuning untuk kejelasan)}



Format ini sangat berguna saat mengembangkan menu.

Tidak bisa

Permainan juga memiliki menu yang berisi pengaturan dan digambar sebelum permainan dimulai dan setelah permainan berakhir.



Tombol menu dibaca dari file *.btn. Tombol-tombol ini harus memiliki teks yang besar dan indah. Kami tidak tahu cara menggambar dengan indah menggunakan karakter ASCII, tetapi figlet , utilitas untuk menampilkan teks ASCII dalam font yang berbeda, dapat:





Tombol membingkai label yang dibaca dari file:





Mereka kemudian dipusatkan dan dikeluarkan secara berurutan:





Di beberapa menu, Anda bisa gagal dan, misalnya, menyesuaikan kompleksitas dan warna bot:





Bagian paling menarik dalam mendesain sistem menu adalah menggabungkan elemen-elemennya menjadi satu sistem. Ini dilakukan oleh elemen terpisah dari sistem, yang kami sebut multiplexer. Namanya terinspirasi oleh multiplexer terminal .



Multiplexer menerima tombol yang ditekan oleh pengguna dan mengirimkannya ke semua menu yang sedang ditampilkan. Setiap menu memutuskan sendiri apa yang harus dilakukan dengan tombol: abaikan atau proses. Hasil pemrosesan menu dikembalikan ke multiplexer, yang memutuskan apa yang harus dilakukan selanjutnya: tutup menu, buat yang baru, ubah pengaturan, tutup aplikasi ...



Pendekatan ini ternyata sesuai dengan kebutuhan kita, meskipun secara umum mungkin tidak cukup: 2 menu berbeda dapat merespons tombol yang sama, dan pengguna harus dapat memilih menu mana yang harus merespons. Solusinya adalah pintasan keyboard khusus yang memungkinkan Anda beralih di antara menu yang berbeda. Misalnya seperti di tmux . Tapi ini berlebihan dan tidak diperlukan.

Bot

Seperti disebutkan di atas, game kami memiliki bot. Kami mencoba membuatnya menarik untuk pemula dan pemain berpengalaman.



Sebelum menjelaskan bot, saya ingin berbicara tentang beberapa detail implementasi. Kami memberikan beberapa bobot untuk setiap bentuk. Semakin besar, semakin berharga angka ini. Kami menentukan seberapa baik posisi di papan tulis menggunakan rumus (jumlah bobot buah putih) - (jumlah bobot buah hitam). Bermanfaat bagi Putih untuk memaksimalkan ekspresi ini, dan untuk Hitam meminimalkan.



Perhitungan lengkap dari seluruh pohon gerakan adalah tugas yang terlalu sulit, jadi kami hanya menghitung beberapa gerakan pertama (melihat ke depan, saya akan mengatakan bahwa ternyata dihitung 6 langkah ke depan). Kami menganggap semua negara bagian di papan pada kedalaman tertentu sebagai daun pohon traversal.



Ada tiga jenis bot dalam gim:

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

Saat kami mulai bereksperimen dengan pengoptimalan, kami menyadari bahwa tidak mungkin dilakukan tanpa pengujian unit untuk bot, jadi kami membuat saudara kembar untuk AlphaBetaBot'a, yang kami beri nama OptimizedAlphaBetaBot. Kami menguji semua ide untuk pengoptimalan OptimizedAlphaBetaBot, dan pengujian unit membantu memastikan bahwa dua saudara kembar menemukan gerakan berguna yang sama. RandomBot telah membantu kami dengan baik dengan menghasilkan pola acak di papan. Untuk melakukan ini, cukup meminta RandomBotdan pergi beberapa lusin kali untuk kedua sisi.



Secara total OptimizedAlphaBetaBot , 3 pengoptimalan utama telah diterapkan (di sini disajikan dalam urutan utilitas menurun):

• Menggunakan rollback. Setelah pengoptimalan ini, tidak perlu lagi menyalin papan berkali-kali untuk bergerak.
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

Selain pengoptimalan besar, ada juga pengoptimalan yang lebih kecil. Misalnya, jika sebelum menyortir, Anda menghitung semua nilai posisi di papan, dengan mempertimbangkan gerakan tertentu, maka Anda tidak perlu lagi mengurutkan objek yang kompleks Move, tetapi cukup int.



Awalnya, direncanakan untuk melaksanakan beberapa rangkaian fungsi evaluasi: misalnya, sosok yang terancam oleh musuh diperkirakan setengah biaya. Tapi ternyata bot itu bermain cukup "bersih", kehilangan beberapa bagian, jadi jumlah yang sederhana ternyata lebih efektif.



Namun, arsitektur bot masih mendukung penambahan fungsi evaluasi baru. Untuk melakukan ini, Anda hanya perlu mendefinisikan tiga hal:

1. Berfungsi jika Anda perlu menghitung biaya "dari awal" untuk pengaturan angka tertentu
2. Fungsi delta, yang akan dengan cepat menghitung ulang biaya untuk gerakan tertentu.
3. Jumlah kumpulan fungsi ini untuk konstruktor kelas kustom FunctionSet.

Anda dapat mengaktifkan pertempuran bot dan melihat prosesnya.





^{Game yang terdiri dari 2 bot dengan tingkat kesulitan yang sama (level 4 dari 6). Kursor berada di tengah bidang untuk keseluruhan game}

Kesimpulan

Kami telah menerapkan permainan yang mirip dengan catur, tetapi dengan aturan berbeda dan papan yang tidak biasa. Implementasi kami memiliki ruang untuk berkembang. Intellector sendiri juga berkembang dan berubah: baru-baru ini ada pembaruan pada aturan, yang belum kami dukung di aplikasi kami. Misalnya, sekarang Anda tidak dapat melewati garis tengah untuk 2 putaran pertama.



Selain itu, ada berbagai fitur yang awalnya kami rencanakan, tetapi tidak berhasil diterapkan pada saat proyek. Misalnya, dalam aplikasi ini saya sangat ingin melihat permainan jaringan. Selain itu, antarmuka lintas platform yang bagus, misalnya, di Qt, tidak akan merugikan.



Mungkin semua atau sebagian dari ini akan muncul dalam waktu dekat. Sampai saat itu, terima kasih telah membaca!



Repositori Github