Hikaru Nakamura, yang baru-baru ini menantang komputer.

Komputer telah lama mengalahkan seorang pria dalam catur, sekarang para pemain catur terkuat tidak mampu mengalahkan bahkan laptop lama. Sekarang mesin catur digunakan untuk menganalisis permainan, mencari opsi baru dan bermain melalui korespondensi.

Jika Anda tertarik pada bagaimana mesin catur diatur, selamat datang di kucing.

Pendahuluan

Pernah saya yakin bahwa program catur (mereka juga mesin, tetapi lebih lanjut tentang itu nanti) hanya mengingat sejumlah besar permainan yang dimainkan dan menemukan posisi mereka saat ini di dalamnya dan membuat langkah yang tepat. Menurut pendapat saya, saya membacanya di beberapa buku.

Ini tidak diragukan lagi pendapat yang sangat naif. Posisi baru dalam catur dapat diperoleh dengan gerakan kesepuluh. Meskipun ada lebih sedikit posisi dalam catur daripada di perjalanan , namun, setelah 3 gerakan (satu gerakan adalah satu gerakan putih dan hitam, setengah gerakan adalah gerakan hanya dari satu sisi) pohon gerakan terdiri dari hampir 120 juta node. Selain itu, ukuran pohon setelah 14 setengah bergerak dari posisi awal telah dipertimbangkan oleh penggemar selama lebih dari satu tahun, sejauh ini telah meningkat sekitar sepertiga.

Saya juga berpikir bahwa program catur, meskipun sudah lamamemenangkan pertandingan atas juara dunia masih dalam jangkauan orang-orang terbaik. Ini juga tidak benar.

Dalam pertandingan mini mesin manusia baru -baru ini, Hikaru Nakamura , salah satu pemain catur terkuat di dunia, bermain dengan Komodo , salah satu (dua) program catur terkuat di dunia. Program ini diluncurkan pada Xeon 24-core. Karena orang tidak bisa lagi bersaing dengan persyaratan yang sama dengan komputer, grandmaster mendapat keunggulan di masing-masing dari 4 game:

Pada gim pertama - gadai dan kepindahan: komputer dimainkan hitam dan tanpa gadai f7
Di kedua - hanya bidak: komputer bermain putih tanpa f2 gadai
Dalam ketiga - kualitas (perbedaan antara benteng dan tokoh cahaya diperkirakan sekitar 2 kaki): komputer tanpa a1 benteng putih, seorang pria tanpa b8 kuda dan benteng a8 di tempatnya.
Pada langkah keempat - empat: seseorang bermain putih dan bukannya gerakan pertama ia membuat 4 gerakan tanpa melewati tengah papan.

Ada beberapa perselisihan mengenai kecacatan - misalnya, tidak adanya pegadaian sedikit melemahkan sang raja, tetapi setelah casting memberikan garis terbuka kepada benteng. Tidak adanya bidak sentral mungkin memberi keuntungan lebih besar. 4 gerakan memberikan keuntungan posisi yang baik, tetapi jika Anda memainkan debut tertutup seperti pertahanan India Lama, maka keunggulan ini tidak begitu sulit untuk dibatalkan.

Selain itu, game yang dimainkan dengan kontrol 45 '15', yaitu 45 menit per game dan 15 detik dari uploadsetiap gerakan. Biasanya, kontrol yang lebih pendek memberikan keuntungan tambahan ke komputer, sementara yang lebih lama sedikit meningkatkan peluang seseorang. Bahkan dalam sepersekian detik, komputer akan dapat menyapu secara terbuka kehilangan gerakan, sementara karena pertumbuhan eksponensial dari pohon varian, setiap peningkatan selanjutnya dalam analisis memakan waktu lebih lama.

Namun, ada cacat dan orang tersebut kalah dalam pertandingan 2,5-1,5, setelah bermain imbang 3 pertandingan pertama dan kalah keempat. Pada saat yang sama, grandmaster yang lemah menang dengan cukup percaya diridengan cacat 2 pion. Oleh karena itu, keuntungan dari program terbaik daripada orang-orang terbaik saat ini adalah antara 1 dan 2 pion dari handicap. Tentu saja, penilaian ini sangat kasar, tetapi untuk penilaian yang akurat perlu memainkan beberapa ribu game antara orang dan program, dan tidak mungkin ada orang yang akan melakukannya. Harap perhatikan bahwa peringkat ELO, yang sering diindikasikan untuk program, tidak ada hubungannya dengan peringkat orang.

Apa itu mesin catur?

Agar seseorang dapat bermain catur dengan komputer, selain benar-benar mencari langkah terbaik, Anda memerlukan GUI. Untungnya, antarmuka universal ditemukan (bahkan dua, Winboard dan UCI , tetapi sebagian besar mesin menggunakan UCI) untuk komunikasi antara GUI dan program catur itu sendiri (mesin). Dengan demikian, programmer dapat fokus pada algoritma permainan catur, tanpa memikirkan antarmuka. Sisi sebaliknya dari koin adalah bahwa membuat GUI jauh lebih membosankan daripada menulis mesin, kemudian GUI gratis terasa kalah pada yang dibayar. Tidak seperti mesin, di mana Stockfish gratis dengan percaya diri berjuang untuk baris pertama peringkat dengan Komodo berbayar.

Bagaimana mereka masih bermain?

Jadi, bagaimana cara kerja mesin catur modern?

Presentasi Dewan

Dasar dari setiap mesin adalah representasi dari papan catur. Pertama-tama, perlu untuk "menjelaskan" ke komputer semua aturan catur dan memberikannya kesempatan untuk mempertahankan posisi catur. Tanpa ini, tidak mungkin untuk mengevaluasi posisi dan membuat gerakan.

Ada dua cara utama untuk menyimpan representasi papan - dengan bentuk atau sel . Dalam kasus pertama, kami menyimpan untuk masing-masing bagian di papan tulis, di bagian kedua - sebaliknya, untuk setiap sel kami menyimpan apa yang ada di sana. Setiap metode memiliki kelebihan dan kekurangan, tetapi saat ini semua mesin teratas menggunakan representasi papan - bitboard yang sama.

Bitboards

Untungnya, ada 64 sel di papan catur. Jadi, jika kita menggunakan satu bit untuk setiap sel, kita dapat menyimpan seluruh papan dalam integer 64-bit.
Dalam satu variabel kita akan menyimpan semua potongan putih, di yang lain - semua yang hitam, dan di 6 lebih - masing-masing jenis angka secara terpisah (opsi lain - 12 bitboard untuk setiap warna dan jenis angka secara terpisah)

Apa keuntungan dari opsi ini?
Yang pertama adalah memori. Seperti yang kita pelajari kemudian, selama analisis, representasi papan disalin berkali-kali, dan karenanya, RAM menggerogoti. Bitboard adalah salah satu representasi papan catur paling ringkas.
Kedua, kecepatan. Banyak perhitungan, misalnya, perhitungan gerakan yang mungkin, turun ke beberapa operasi bit. Karena ini, misalnya, menggunakan instruksi POPCNT memberikan akselerasi ~ 15% ke mesin modern. Selain itu, selama keberadaan bitboard, banyak algoritma dan optimisasi ditemukan, seperti, misalnya, bitboard "ajaib" .

Cari

Minimax

Di jantung sebagian besar mesin catur adalah algoritma pencarian minimax atau modifikasinya non-hamax. Singkatnya, kita turun pohon, mengevaluasi daun, dan kemudian naik, setiap kali memilih langkah optimal untuk pemain saat ini, meminimalkan skor untuk satu (hitam) dan memaksimalkan untuk yang kedua (putih). Karena itulah namanya. Setelah di root, kami mendapatkan urutan gerakan yang optimal untuk kedua pemain. Perbedaan antara minimax dan non-hamax adalah bahwa dalam kasus pertama, kami bergiliran memilih gerakan dengan peringkat maksimum dan minimum, dan di kedua, sebagai gantinya, mengubah tanda untuk semua peringkat dan selalu memilih maksimum (kami memahami dari mana asalnya). Lebih detail di sini dan di sini .

Alpha beta

Optimalisasi pertama adalah alpha beta . Ide alpha-beta sederhana - jika saya sudah memiliki langkah yang baik, maka Anda dapat memotong langkah yang jelas lebih buruk. Perhatikan contoh di gambar menyeramkan di sebelah kiri. Misalkan pemain A memiliki 2 kemungkinan gerakan - a3 dan b3. Setelah menganalisis jalannya a3, program menerima peringkat +1,75. Mulai mengevaluasi langkah b3, program melihat bahwa pemain B memiliki dua gerakan - a6 dan a5. Penilaian kursus a6 +0.5. Karena pemain B memilih langkah dengan skor minimum, ia tidak akan memilih langkah dengan skor lebih tinggi dari 0,5, yang berarti bahwa estimasi langkah b3 kurang dari 0,5, dan tidak ada gunanya untuk mempertimbangkannya. Dengan demikian, sisa subtree dari b3 terputus.

Untuk kliping, kami menyimpan batas atas dan bawah - alfa dan beta. Jika selama analisis suatu langkah mendapat skor lebih tinggi dari beta, maka simpul saat ini terputus. Jika skor lebih tinggi dari alpha, maka alpha diperbarui.

Node dalam alpha beta dibagi menjadi 3 kategori:

PV-Nodes - node yang evaluasinya jatuh ke jendela (antara alpha dan beta). Root dan simpul paling kiri selalu merupakan simpul jenis ini.
Cut-Nodes (atau fail-high node ) - node di mana beta cut-off terjadi.
All-Nodes (atau fail-low node ) - node di mana tidak ada langkah yang melebihi alpha sesuai dengan penilaian.

Menyortir bergerak

Saat menggunakan alpha beta, urutan gerakan menjadi penting. Jika kita dapat menempatkan langkah terbaik terlebih dahulu, maka langkah yang tersisa akan dianalisis lebih cepat karena cutoff beta.

Selain menggunakan hash dan langkah terbaik dari iterasi sebelumnya, ada beberapa teknik untuk menyortir gerakan.

Untuk menangkap, misalnya, MVV-LVA heuristik sederhana (Korban Paling Berharga - Aggressor Paling Berharga) dapat digunakan . Kami mengurutkan semua tangkapan dalam urutan nilai "korban", sementara di dalam kami menyortir lagi dalam urutan nilai "si penyerang". Jelas, biasanya lebih menguntungkan untuk mengambil ratu dengan pion daripada sebaliknya.

Untuk gerakan "diam", metode gerakan "pembunuh" digunakan - gerakan yang menyebabkan cutoff beta. Bergerak ini biasanya diperiksa segera setelah bergerak dari hash dan menangkap.

Tabel hash atau tabel permutasi

Meskipun ukuran pohonnya sangat besar, banyak simpul di dalamnya identik. Agar tidak menganalisis posisi yang sama dua kali, komputer menyimpan hasil analisis dalam sebuah tabel dan setiap kali memeriksa apakah sudah ada analisis siap dari posisi ini. Biasanya, tabel seperti itu menyimpan hash aktual dari posisi, peringkat, pergerakan terbaik, dan usia penilaian. Usia diperlukan untuk mengganti posisi lama saat mengisi tabel.

Pencarian berulang

Seperti yang Anda ketahui, jika kita tidak dapat menganalisis seluruh pohon sepenuhnya, minimax membutuhkan fungsi evaluasi. Kemudian setelah mencapai kedalaman tertentu, kami menghentikan pencarian, mengevaluasi posisi dan mulai memanjat pohon. Tetapi metode seperti itu membutuhkan kedalaman yang telah ditentukan dan tidak memberikan hasil antara berkualitas tinggi.

Pencarian berulang menyelesaikan masalah ini. Pertama, kami menganalisis hingga kedalaman 1, lalu ke kedalaman 2, dll. Jadi, setiap kali kita turun sedikit lebih dalam daripada yang terakhir, sampai analisis dihentikan. Untuk mengurangi ukuran pohon pencarian, hasil dari iterasi terakhir biasanya digunakan untuk memotong gerakan buruk yang sengaja dilakukan pada yang sekarang. Metode ini disebut jendela aspirasi dan digunakan secara universal.

Pencarian Diam

Metode ini dirancang untuk memerangi "efek cakrawala". Menghentikan pencarian di kedalaman yang tepat bisa sangat berbahaya. Bayangkan kita berhenti di tengah pertukaran ratu - putih mengambil ratu hitam, dan langkah selanjutnya hitam harus memilih putih. Tetapi saat ini di papan tulis - White memiliki ratu tambahan dan penilaian statis akan secara fundamental salah.

Untuk melakukan ini, sebelum melakukan penilaian statis, kami memeriksa semua tangkapan (kadang-kadang bahkan catur) dan turun pohon ke posisi di mana tidak ada penangkapan dan catur yang mungkin. Secara alami, jika semua tangkapan memperburuk estimasi, maka kami mengembalikan estimasi posisi saat ini.

Pencarian selektif

Gagasan pencarian selektif adalah mengambil lebih lama untuk mempertimbangkan gerakan "menarik" dan kurang menganggap tidak menarik. Untuk melakukan ini, gunakan ekstensi yang meningkatkan kedalaman pencarian di posisi tertentu, dan singkatan yang mengurangi kedalaman pencarian.

Kedalaman meningkat dalam hal penangkapan, pemeriksa, jika gerakan itu unik atau jauh lebih baik daripada alternatif atau di hadapan bidak yang lewat.

Guntingan dan pemotongan

Dengan luka dan luka, semuanya jauh lebih menarik. Mereka dapat secara signifikan mengurangi ukuran pohon.

Secara singkat tentang kliping:

- — , . , , . , , , , .
— , -. , , . (1-2).
— , , . . PV . .
Multi-Cut — M(, 6) C(, 3) Cut-node, .
null- — null- ( ) , . , , , , .

Reduksi digunakan ketika kita tidak begitu yakin bahwa gerakan itu buruk, dan karena itu jangan memotongnya, tetapi cukup kurangi kedalamannya. Sebagai contoh, razoring adalah singkatan asalkan estimasi statis dari posisi saat ini kurang dari alpha.

Karena penyortiran bergerak dan cutoff yang berkualitas tinggi, engine modern berhasil mencapai koefisien percabangan di bawah 2 . Karena itu, sayangnya, mereka kadang-kadang tidak memperhatikan korban dan kombinasi yang tidak standar.

NegaScout dan PVS

Dua teknik yang sangat mirip yang menggunakan fakta bahwa setelah kami menemukan PV-node (dengan asumsi gerakan kami diurutkan dengan cukup baik), kemungkinan besar tidak akan berubah, yaitu, semua node yang tersisa akan mengembalikan peringkat yang lebih rendah daripada alpha. Karena itu, alih-alih mencari dengan jendela dari alfa ke beta, kami mencari dengan jendela dari alfa ke alfa + 1, yang memungkinkan kami untuk mempercepat pencarian. Tentu saja, jika dalam beberapa node kita mendapatkan kliping beta, maka itu harus dihargai kembali, sudah dengan pencarian normal.

Perbedaan antara kedua metode ini hanya pada kata-kata - mereka dikembangkan pada waktu yang hampir bersamaan, tetapi secara independen, dan oleh karena itu dikenal dengan nama yang berbeda.

Pencarian paralel

Paralelisasi alpha beta adalah topik besar yang terpisah. Saya akan membahasnya sebentar, dan siapa yang peduli, lihat Penelusuran Paralel Alpha-Beta pada Shared Memory Multiprocessors . Kesulitannya adalah bahwa dalam pencarian paralel, banyak Cut-node dianalisis sebelum utas lain menemukan bantahan (menginstal beta), sementara dalam pencarian berurutan, dengan pengurutan yang baik, banyak dari node ini akan terputus.

SMP malas

Algoritma yang sangat sederhana. Kami baru saja memulai semua utas secara bersamaan dengan pencarian yang sama. Komunikasi mengalir melalui tabel hash. Lazy SMP ternyata efektif secara tak terduga, sedemikian rupa sehingga Stockfish kelas atas beralih ke YBW. Benar, beberapa percaya bahwa peningkatan itu disebabkan oleh implementasi YBWC yang buruk dan kliping yang terlalu agresif, dan bukan karena keunggulan SMP Malas.

Young Brothers Wait Concept (YBWC)

Node pertama (kakak) harus sepenuhnya dianalisis, setelah itu analisis paralel dari node yang tersisa (adik) dimulai. Idenya sama, langkah pertama akan secara signifikan meningkatkan alfa, atau bahkan memungkinkan Anda untuk memotong semua node lainnya.

Dynamic Tree Splitting (DTS)

Algoritma cepat dan kompleks. Sedikit tentang kecepatan: kecepatan pencarian diukur melalui ttd (waktu ke kedalaman), yaitu waktu selama pencarian mencapai kedalaman tertentu. Indikator ini biasanya dapat digunakan untuk membandingkan pekerjaan versi mesin yang berbeda atau mesin yang berjalan pada jumlah inti yang berbeda (walaupun Komodo, misalnya, menambah lebar pohon dengan lebih banyak core yang tersedia). Selain itu, selama operasi, mesin menampilkan kecepatan pencarian dalam nps (node per detik). Metrik ini jauh lebih populer, tetapi tidak memungkinkan bahkan mesin untuk membandingkan dengan dirinya sendiri. Malas SMP, di mana tidak ada sinkronisasi, hampir secara linear meningkatkan nps, tetapi karena sejumlah besar pekerjaan yang tidak perlu, ttdnya tidak begitu mengesankan. Sedangkan untuk DTS, nps dan ttd berubah hampir sama .

Sejujurnya, saya masih belum bisa sepenuhnya mengetahui algoritma ini, yang, meskipun efisiensi tinggi, digunakan secara harfiah dalam sepasang mesin. Untuk siapa ini sangat menarik, ikuti tautan di atas.

Peringkat

Jadi, kita telah mencapai kedalaman yang diperlukan, mencari ketenangan dan, akhirnya, kita perlu mengevaluasi posisi statis.

Komputer mengevaluasi posisi dalam pion: +1.0 berarti bahwa White memiliki keunggulan sama dengan 1 pion, -0.5 berarti bahwa Black memiliki keunggulan setengah pion. Mat diperkirakan sekitar 300 pion, dan posisi di mana jumlah perpindahan ke mat x diketahui berada pada (300-0,01x) pion. +299.85 berarti White mate dalam 15 gerakan. Dalam hal ini, program itu sendiri biasanya beroperasi dengan seluruh perkiraan dalam centipes (1/100 pion).

Parameter apa yang diperhitungkan komputer saat mengevaluasi suatu posisi?

Bahan dan mobilitas

Hal paling sederhana. Ratu adalah 9-12 pion, benteng 5-6, ksatria dan uskup 2,5-4 dan pion, masing-masing, satu pion. Secara umum, material adalah heuristik yang layak untuk mengevaluasi posisi dan setiap keuntungan posisi biasanya pada akhirnya berubah menjadi material.

Mobilitas dianggap sederhana - jumlah kemungkinan gerakan di posisi saat ini. Semakin banyak dari mereka, semakin mobile pasukan pemain.

Tabel Posisi Bentuk

Kuda di sudut papan biasanya buruk, bidak lebih dekat ke belakang musuh menjadi lebih berharga dan seterusnya. Untuk setiap angka, daftar bonus dan penalti dikompilasi tergantung pada posisinya di papan tulis.

Struktur gadai

Bidak ganda - dua bidak pada vertikal yang sama. Seringkali sulit mempertahankannya dengan bidak lain, itu dianggap sebagai kelemahan.
— , . , .
— , . ,
— , . , .

Semua parameter di atas memengaruhi peringkat game secara berbeda, tergantung pada tahap permainan. Dalam pembukaan tidak ada arti di pion yang sudah berlalu, tetapi di endgame Anda harus membawa raja ke tengah papan, dan tidak bersembunyi di belakang pion.

Oleh karena itu, banyak mesin memiliki peringkat yang terpisah untuk endgame dan untuk debutnya. Mereka mengevaluasi tahap permainan tergantung pada bahan yang tersisa di papan tulis dan, sesuai dengan ini, pertimbangkan peringkat - semakin dekat ke akhir permainan, semakin sedikit skor pembukaan terpengaruh dan semakin banyak itu adalah endgame.

Lainnya

Selain faktor-faktor dasar ini, mesin dapat menambahkan beberapa faktor lain ke dalam penilaian - misalnya, keamanan raja, potongan yang terkunci, pulau gadai, kontrol pusat, dll.

Peringkat akurat atau pencarian cepat?

Sengketa tradisional: yang lebih efisien, menilai posisi dengan akurat, atau mencapai kedalaman penelusuran yang lebih besar. Pengalaman menunjukkan bahwa fungsi evaluasi yang terlalu "berat" tidak efektif. Di sisi lain, penilaian yang lebih rinci, dengan mempertimbangkan lebih banyak faktor, biasanya mengarah ke permainan yang lebih "cantik" dan "agresif".

Debut buku dan tabel endgame

Buku debutnya

Pada awal catur komputer, program memainkan debut mereka dengan sangat lemah. Debut seringkali membutuhkan keputusan strategis yang akan memengaruhi seluruh permainan. Di sisi lain, teori pembukaan dikembangkan dengan baik pada orang-orang, pembukaan itu berulang kali dianalisis dan dimainkan dari memori. Jadi "memori" yang serupa diciptakan untuk komputer. Mulai dari posisi awal, pohon gerakan dibangun dan setiap gerakan dievaluasi. Selama permainan, mesin hanya memilih salah satu gerakan "bagus" dengan probabilitas tertentu.

Sejak itu, buku-buku debut telah berkembang, banyak debut dianalisis menggunakan komputer sampai akhir. Tidak perlu bagi mereka, mesin yang kuat telah belajar memainkan debut, tetapi mereka meninggalkan jalur utama dengan cukup cepat.

Tabel endgame

Kembali ke pengantar. Ingat ide menyimpan banyak posisi dalam memori dan memilih yang tepat. Itu dia. Untuk sejumlah kecil (hingga 7) angka, semua posisi yang ada dihitung. Artinya, di posisi ini komputer mulai bermain dengan sempurna, menang dalam jumlah minimum gerakan. Minus adalah ukuran dan waktu generasi. Pembuatan tabel-tabel ini membantu dalam mempelajari endgames.

Pembuatan tabel

Kami menghasilkan semua posisi yang mungkin (dengan mempertimbangkan simetri akun) dengan serangkaian bentuk tertentu. Di antara mereka, kami menemukan dan menunjuk semua posisi di mana matras berdiri. Dengan operan berikutnya, kami menunjukkan semua posisi di mana Anda dapat masuk ke posisi dengan matras - di posisi ini matras diletakkan dalam 1 giliran. Jadi kami menemukan semua posisi dengan pasangan 2,3,4, 549 bergerak. Di semua posisi tanpa tanda - undian.

Tabel Nalimov

Tabel endgame pertama diterbitkan kembali pada tahun 1998. Untuk setiap posisi, hasil permainan dan jumlah gerakan ke mat dengan permainan ideal disimpan. Ukuran semua ujung enam angka adalah 1,2 terabyte.

Tabel Lomonosov

Pada 2012, semua ujung tujuh angka (kecuali 6 lawan 1) dihitung pada superkomputer Lomonosov di Universitas Negeri Moskow . Basis-basis ini hanya tersedia untuk uang dan ini adalah satu-satunya tabel endgame tujuh angka lengkap yang ada.

Syzygy

Standar de facto. Basis-basis ini jauh lebih kompak daripada basis Nalimov. Mereka terdiri dari dua bagian - WDL (Win Draw Lose) dan DTZ (Distance to zeroing). Basis data WDL dimaksudkan untuk digunakan selama pencarian. Setelah simpul pohon ditemukan di tabel, kami memiliki hasil yang tepat dari permainan di posisi ini. DTZ dimaksudkan untuk digunakan di root - mereka menyimpan jumlah gerakan ke counter nullify dari gerakan (bergerak dengan bidak atau menangkap). Dengan demikian, basis WDL cukup untuk analisis, dan basis DTZ dapat berguna dalam menganalisis endgame. Syzygy jauh lebih kecil - 68 gigabyte untuk WDL enam angka dan 83 untuk DTZ. Tidak ada basis tujuh angka, karena generasinya membutuhkan sekitar terabyte RAM.

Gunakan

Tabel endgame digunakan terutama untuk analisis, peningkatan kekuatan mesin game kecil - 20-30 poin ELO . Namun demikian, karena kedalaman pencarian mesin modern bisa sangat besar, permintaan untuk basis endgame dari pohon pencarian masih terjadi dalam debut.

Menarik lainnya

Jerapah atau jaringan saraf bermain catur

Beberapa dari Anda mungkin pernah mendengar tentang mesin catur di jaringan saraf yang telah mencapai tingkat IM (yang, seperti yang kita pahami dalam pendahuluan, tidak begitu keren untuk mesin). Itu ditulis dan diposting di Bitbucket oleh Matthew Lai, yang sayangnya berhenti bekerja karena dia mulai bekerja di Google DeepMind .

Parameter Tuning

Menambahkan fitur baru ke mesin tidak sulit, tetapi bagaimana saya bisa memverifikasi bahwa itu memberikan amplifikasi? Opsi paling sederhana adalah memainkan beberapa game antara versi lama dan baru dan melihat siapa yang menang. Tetapi jika peningkatannya kecil, dan itu biasanya terjadi setelah semua fitur utama telah ditambahkan, harus ada beberapa ribu permainan, jika tidak maka tidak akan ada keandalan.

Stockfish

Ada banyak orang yang mengerjakan mesin ini, dan masing-masing ide mereka perlu diperiksa. Dengan kekuatan mesin saat ini, setiap peningkatan memberikan peningkatan beberapa poin penilaian, tetapi pada akhirnya, peningkatan yang stabil dari beberapa puluh poin diperoleh setiap tahun.

Solusi mereka adalah tipikal open source - sukarelawan memberikan kekuatan mereka untuk mengarahkan ratusan ribu game kepada mereka.

CLOP

Suatu program yang mengoptimalkan parameter melalui regresi linier, menggunakan hasil permainan mesin dengan dirinya sendiri dengan parameter yang berbeda. Dari minus - ukuran tugas yang sangat terbatas: untuk mengoptimalkan seratus parameter (jumlah yang cukup memadai untuk mesin) itu tidak mungkin, setidaknya untuk waktu yang memadai.

Tuning Texel

Memecahkan masalah metode sebelumnya. Kami mengambil sejumlah besar posisi (penulis menawarkan 9 juta posisi dari 64.000 game, saya mengambil 8 juta dari hampir 200.000), untuk masing-masing kami menyimpan hasil permainan (White menang 1, imbang 0,5, kalah 0). Sekarang kita meminimalkan kesalahan, yang merupakan jumlah kuadrat dari perbedaan hasil dan sigmoid estimasi. Metode ini efektif dan populer, tetapi tidak bekerja di semua mesin.

Penyetelan stockfish

Teknik lain dari pemimpin. Kami mengambil parameter sama dengan x, dan membandingkan (dalam beberapa puluhan ribu lot) mesin dengan parameter sama dengan x-sigma dan x + sigma. Jika mesin dengan parameter besar menang, gerakkan sedikit ke atas, jika tidak - sedikit ke bawah, dan ulangi.

Kompetisi mesin

Dari semua tes kompetisi yang dilakukan, saya ingin membedakan TCEC secara terpisah . Ini berbeda dari yang lainnya dalam perangkat kerasnya yang kuat, pemilihan bukaan yang cermat dan kontrol yang panjang. Di final terakhir, 100 pertandingan dimainkan pada 2 x Intel Xeon E5-2690v3 dengan 256 gigabytes RAM dengan kontrol 180 '+ 30 ". Dalam kondisi seperti itu, jumlah pengundian sangat besar, dan hanya 11 pertandingan yang efektif.

Kesimpulan

Jadi, secara singkat dalam artikel panjang ini, saya berbicara tentang struktur mesin catur. Banyak detail yang tidak diungkapkan, saya hanya tidak tahu tentang sesuatu atau lupa mengatakannya. Jika Anda memiliki pertanyaan, tulis di komentar. Selain itu, saya akan memberi tahu Anda tentang dua sumber yang mungkin Anda perhatikan jika Anda hati-hati membuka semua tautan yang tersebar di seluruh artikel:

Wiki pemrograman catur
Forum Talkchess
Dan satu lagi, tidak disebutkan sebelumnya - sudut programmer

Bagaimana komputer bermain catur?