Didedikasikan untuk semua orang yang sekarang menonton serial TV terkenal "The Queen's Gambit". Lebih banyak istilah catur dalam terjemahan baru kami.
Pada artikel ini, kita akan mencoba memahami cara kerja mesin catur dengan mem-porting mesin catur sunfish ke Go. Sunfish terkenal karena kesederhanaan dan ukurannya yang kecil, tetapi masih bisa memainkan permainan catur yang layak. Go, di sisi lain, dikenal sebagai bahasa pemrograman yang sederhana dan mudah dibaca, jadi saya harap mereka bisa menjadi pasangan yang hebat.
Untuk membuat mesin catur, Anda harus terlebih dahulu memutuskan tiga poin penting:
- Bagaimana cara merepresentasikan papan catur (sel, bidak, gerakan yang diizinkan)?
- Bagaimana Anda menilai dewan (siapa yang lebih mungkin menang)?
- Bagaimana cara menemukan gerakan yang optimal?
Potongan kode dalam posting ini disederhanakan dan hanya berisi bagian yang paling penting. Anda dapat menemukan kode mesin lengkapnya di github.com/zserge/carnatus (carnatus adalah nama latin untuk ikan bass, spesies Sebastes carnatus).
Sel dan bentuk
Penting untuk menemukan representasi papan yang nyaman yang tidak memakan banyak ruang, karena ribuan variasi papan akan disimpan dalam memori sambil mencari gerakan optimal.
Biasanya papan adalah kumpulan sel. Kami akan menambahkan bantalan di sekitar papan standar 8x8 sehingga potongan yang tidak valid masuk ke area ini. Ini akan memungkinkan kita untuk menghindari pemeriksaan batas dan sangat menyederhanakan kode.
Kami akan menggunakan array linier. Jarak terjauh yang bisa ditempuh bidak catur adalah jurus ksatria 2 kotak. Tentu saja, potongan geser lainnya dapat bergerak dalam jarak yang jauh, tetapi gerakan seperti itu akan dievaluasi secara berurutan saat setiap kotak dilintasi, yang berarti bahwa batas papan akan terdeteksi sebelum potongan tersebut dapat melampauinya.
Jadi, kita membutuhkan ruang dua sel di sepanjang tepi papan. Kita dapat membuat papan berukuran 12x12, tetapi karena kita merepresentasikannya sebagai larik garis, kita memerlukan papan 12x10 karena bujur sangkar paling kanan pada baris sebelumnya dapat digunakan sebagai bujur sangkar paling kiri pada baris berikutnya (× = indentasi):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
Dalam notasi kita, "a1" akan terlihat seperti 9 × 10 + 1 = 91, dan "a8" akan terlihat seperti "2 × 10 + 1" = 21.
Setiap sel dalam larik papan akan mewakili bidak catur, kotak kosong, atau zona indentasi. dapat menggunakan konstanta numerik untuk nilai-nilai ini, tetapi untuk menyederhanakan proses debug, kami menggunakan karakter yang dapat dibaca manusia. Huruf besar dan kecil mewakili bentuk, spasi mewakili zona indentasi, dan titik mewakili sel kosong:
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Penguraian singkatan
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Akhirnya, kita bisa mulai menulis beberapa kode:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
Bentuk memiliki nilai tertentu. Nilai-nilai ini diperlukan untuk mengevaluasi posisi di papan dan memahami siapa yang menang. Biasanya bidak = 100, ksatria = 280, uskup = 320, benteng = 479, ratu = 929, dan raja sangat berharga sehingga mengalahkan 8 ratu (bidak berubah menjadi ratu) dalam hubungannya dengan pasangan ksatria, uskup, dan benteng. Jika kita memiliki semua kekayaan ini, tetapi kita kehilangan raja, menghitung masih akan menunjukkan bahwa kita akan kalah.
Setiap jenis memiliki metode Flip () yang mengembalikan nilai yang sama setelah membalik papan sebelum lawan bergerak. Untuk bentuk, ini mengubah kapitalisasi simbol bentuk. Di kotak, dia mengembalikan 119 kotak (dihitung dari ujung papan lainnya). Sedangkan untuk papan, dia menyalin semua bagian dari kotak dengan urutan terbalik, mengubah kotaknya.
Generator langkah
Jadi, kami sudah memiliki blok bangunan untuk mesin, dan sekarang kami dapat memikirkan posisi permainan. Posisi adalah papan dengan potongan dan status tambahan dalam permainan, seperti kotak bagian, kotak pengembara, dan kemungkinan kastil. Jika kami ingin menyederhanakan permainan, kami dapat menggunakan kembali jenis Papan, tetapi kami akan membuat jenis Posisi terpisah untuk gerakan dan evaluasi papan.
Apa itu gerakan? Ini adalah kombinasi dari dua sel - sel tempat potongan itu sebelumnya dipindahkan dan sel tempat potongan itu dipindahkan. Posisi adalah papan catur dengan skor, aturan kastil untuk setiap pemain, dan kotak bagian / pengembaraan. Kedua tipe juga memiliki metode Flip () untuk gerakan lawan.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Sekarang kita bisa menulis metode besar pertama - generator bergerak yang diizinkan. Kami hanya peduli pada bidak putih, karena untuk bermain hitam kami akan membalik papan dan memindahkan putih lagi.
Untuk menghasilkan semua gerakan yang valid, kita membutuhkan:
- membuat daftar semua gerakan satu langkah di setiap arah untuk setiap bagian;
- lakukan hal yang sama untuk semua sel, abaikan bagian non-putih;
- tentukan gerakan ke setiap arah yang mungkin untuk setiap bagian putih;
- jika panjang langkah bidak tidak terbatas (benteng, uskup, ratu), terus gerakkan sampai rintangan ditemukan di jalan: bidak lawan atau lekukan di belakang tepi papan.
Ini adalah kode yang disederhanakan yang tidak memperhitungkan penangkapan dan kastling. Anda dapat menemukan implementasi penuh di Github , tidak jauh berbeda.
Untuk membuat aritmatika arah lebih mudah dibaca, kita akan menggunakan konstanta arah N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
Ini semua adalah aturan permainan catur yang perlu kita pertimbangkan untuk membuat gerakan yang valid. Langkah selanjutnya adalah menerapkan perpindahan ke posisi tersebut untuk membuat posisi permainan baru. Tanpa memperhitungkan menangkap bagian, promosi gadai dan rokade, metodenya akan terlihat seperti ini:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
Dia hanya memindahkan bidak, menandai sel yang sebelumnya kosong, dan membalik papan. Penerapan penuh dari metode ini dapat ditemukan di Github , ini menangani semua pion dan raja khusus bergerak dengan benar.
Pada tahap ini, Anda dapat bermain catur "manusia melawan manusia", mengontrol proses dan hanya membuat langkah hukum. Atau Anda dapat membuat mesin catur primitif yang membuat gerakan acak hingga kalah.
Tetapi bagaimana kita memahami bahwa kita kalah?
Peringkat dewan
Poin diberikan untuk setiap posisi di papan. Awalnya, skornya nol, karena kedua pemain memulai dengan kondisi yang sama. Setelah menyelesaikan satu gerakan, skor berubah tergantung pada bidak mana yang ditangkap dan bagaimana bidak mengubah posisi di papan.
Dalam kasus yang paling sederhana, kita dapat menghitung bidak di papan dan menjumlahkan nilainya (dikurangi bidak lawan). Perhitungan seperti itu akan menunjukkan jika raja dinyatakan cek dan skakmat. Tetapi ini adalah sistem penilaian yang sangat lemah.
Pendekatan yang jauh lebih akurat dan sangat sederhana adalah Tabel Rasio Bentuk-ke-Persegi ( PST- Tabel Sepotong-Persegi). Untuk setiap bidak, sebuah tabel dibuat dengan ukuran yang sama seperti papan catur, di mana nilai yang sesuai ditetapkan ke setiap kotak. Nilai-nilai ini empiris, jadi saya ambil saja dari mesin Sunfish.
Faktanya, mesin catur yang lebih maju memperbarui PST selama permainan karena nilai bidak berubah (yaitu bidak menjadi lebih berharga menjelang akhir permainan). Tapi kami akan memiliki mesin yang sederhana.
Untuk mengevaluasi posisi setelah pindah, kita membutuhkan:
- tentukan peringkat posisi saat ini,
- kurangi nilai bidak yang dipindahkan,
- tambahkan nilai angka baru sesuai dengan tabel PTS,
- tambahkan nilai barang yang ditangkap, jika ada.
Selain itu, dalam tabel PST kita perlu menyesuaikan nilai benteng selama rokade dan nilai bidak selama promosi atau penangkapan saat umpan. Tetapi di sini kami tidak akan mempertimbangkan ini:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Sekarang kita dapat membuat mesin yang sedikit lebih canggih yang akan memilih gerakan terbaik, daripada yang valid.
Tetapi mesin catur sungguhan melakukan analisis yang lebih dalam dan melakukan iterasi melalui cabang-cabang gerakan yang mungkin di setiap sisi untuk menemukan gerakan terbaik dalam jangka panjang.
Algoritma pencarian
Algoritme pencarian yang paling umum di mesin catur lebih sederhana - pencarian kedalaman-pertama, yang dimulai dari akar dan turun ke batas kedalaman tertentu, mengulangi semua gerakan yang mungkin sebelum kembali. Untuk setiap nilai posisi goresan dihitung menggunakan algoritma minimax (minimax) c pemangkasan alfa-beta (pemangkasan alfa-beta ).
Minimax adalah aturan yang digunakan untuk meminimalkan kemungkinan kerugian dalam skenario kasus terburuk: pemain mempertimbangkan semua gerakan terbaik lawan dan memilih gerakan seperti itu sehingga strategi terbaik lawan menghasilkan poin sebanyak mungkin.
Algoritme minimax sederhana akan terlalu lambat untuk catur dan akan membutuhkan pengulangan terlalu banyak gerakan untuk menemukan yang bagus.
Pemangkasan alfa-beta digunakan untuk mempercepat algoritme minimax dengan menghapus node yang tidak layak dipertimbangkan. Pemotongan alfa-beta didasarkan pada logika berikut: Bayangkan Anda sedang bermain catur dan menemukan gerakan yang sangat bagus A. Anda terus melihat papan dan menemukan gerakan B yang lebih baik. Tetapi kemudian Anda menganalisis situasinya lebih dalam dan memahami bahwa jika Anda memilihnya di langkah B, musuh akan menyatakan cek dan skakmat untuk Anda dalam beberapa gerakan. Sekarang Anda membuang B dan jangan buang waktu menganalisis kemungkinan kombinasi lain setelah B.
Baik pemotongan minimax dan alfa-beta penting untuk memahami cara kerja mesin catur. Mesin Sunfish menggunakan algoritma pencarian lanjutan MDF (f) , yang juga merupakan varian dari algoritma minimax yang dikombinasikan dengan kliping.
Di mesin kami, kami akan secara bertahap meningkatkan kedalaman pencarian dan memanggil algoritma MDF (f) untuk menemukan batas bawah dan atas dari hasil yang optimal. Algoritme MDF (f) akan menggunakan iterasi pemotongan alfa-beta dengan cache transposisi.
Transposisi kas adalah cache di mana untuk setiap posisi di papan kita menghafal kedalaman, hitungan, dan gerakan yang membawa kita ke posisi itu. Kemudian, saat mempertimbangkan posisi baru, pertama kali dicek pada tabel transposisi.
Saya tidak akan memposting kode algoritma pencarian di sini, karena ini hanya beberapa baris pencarian rekursif, tetapi Anda selalu dapat menemukan kode sumber lengkap mesin catur di GitHub .
Apa berikutnya?
Jika Anda tertarik dengan mesin catur sederhana, saya sangat merekomendasikan bermain dengan Sunfish. Ngomong-ngomong, Sunfish didasarkan pada mesin Micromax dan dilengkapi dengan dokumentasi yang sangat baik dari penulisnya, yang pasti patut dibaca.
Dalam hal mesin kami di Go, saya menambahkan implementasi kecil dari protokol UCI sehingga dapat digunakan dengan PyChess UI. Kemungkinan besar, ini masih memiliki banyak bug dan banyak potensi untuk perbaikan, tetapi itu adalah jalur yang menarik: dari ide mengembangkan mesin catur hingga program catur komputer yang siap pakai dan berfungsi.
Ya, dia lemah, tapi dia memainkan permainan catur sungguhan!
Saya harap Anda menikmati artikel ini. Anda dapat mengikuti saya di Github , Twitter atau berlangganan melalui rss .