Apa cara akurat untuk mengevaluasi posisi catur?

Saya tertarik untuk sementara waktu tentang algoritma AI catur komputer (dan mendapat kesempatan untuk mengerjakannya di beberapa titik) seperti Minimax , dan sebagai komponen inti dari algoritma ini adalah fungsi evaluasi yang disebut untuk menentukan apa yang dimaksud dengan konfigurasi papan yang baik , dan apa yang buruk .

Dengan kata lain, diberikan konfigurasi papan Catur Anda, bagaimana Anda menentukan bahwa itu untuk keuntungan Anda, dan dengan tingkat kepercayaan apa?

Sebagai contoh:

• Jika Anda memiliki pusat, ini agak menguntungkan.
• Jika Anda memiliki lebih banyak potongan daripada lawan Anda, ini agak menguntungkan.
• Jika Anda kehilangan Ratu Anda, ini agak tidak menguntungkan.
• Jika Anda memiliki pion yang hampir dipromosikan, ini menguntungkan.
• ...

Jadi saya ingin meminta saran tentang cara membuat fungsi evaluasi yang baik , berdasarkan beberapa pengetahuan ahli tentang permainan Catur secara umum. Dan jika mungkin, tingkat kesukaan (katakanlah antara 1 menjadi sangat tidak menguntungkan, sampai 100 sangat menguntungkan).

Ide pada akhirnya adalah untuk dapat membuat algoritma yang akan melihat kemungkinan hingga kedalaman tertentu dan mengevaluasi apa konfigurasi yang paling menguntungkan untuk langkah selanjutnya (dengan mempertimbangkan beberapa langkah di masa depan) berdasarkan pada apa menguntungkan pemain dan tidak menguntungkan lawan. Tetapi tanpa fungsi evaluasi yang baik, algoritma tidak ada artinya.

Inilah titik awal yang baik. Perbandingan material adalah kunci (dan mudah), maka Anda dapat menyetelnya untuk mempertimbangkan aspek posisi seperti peringkat terbuka / file / diagonal, struktur gadai, dll.

https://www.chessprogramming.org/Evaluation

Menambah jawaban oleh @Eve Freeman, saya akan menyarankan mencari bagaimana mesin komputer terbaik di dunia, Stockfish, mengevaluasi posisi yang diberikan. Ketika kode sumber terbuka, Anda dapat melakukannya secara gratis. Saya pikir file dengan fungsi evaluasi yang Anda cari adalah yang ini .

Saya merasa saya agak terlambat pada jawaban ini tetapi - Saya juga sedang dalam proses membuat mesin. Kode sumber menggunakan Python (yang cukup mudah dibaca, bahkan jika Anda tidak mengetahuinya) dan tersedia di sini jika Anda ingin membacanya. Daftar 'heuristik' yang saat ini aktif (pada saat posting):

• Potongan yang dikembangkan lebih jauh (lebih dekat ke sisi berlawanan) lebih baik
• Gada yang lebih dekat ke promosi bagus
• Kings diberi skor secara terpisah berdasarkan fase permainan (pembukaan, tengah, akhir)
• Jika pemain memiliki kedua uskup, itu menerima bonus
• Jika pemain telah kastil, terima bonus
• Pion terisolasi (pion dengan tidak ada di sekitar mereka) tidak baik
• Menggandakan pion (dua pion pada file yang sama tanpa kesenjangan antara) tidak baik
• Memiliki semua 8 pion tidak perlu hal yang baik dan dihukum (mereka mengacaukan papan dan menghalangi jalan)
• Lihatlah fungsi evaluasi hebat ini yang juga digunakan
• Para uskup dengan lebih banyak bidak pada kotak warna yang sama dengan sang uskup dihukum (mereka tidak sebagus dalam situasi yang penuh sesak)
• Belum dilaksanakan, tetapi direncanakan: Ksatria mendapatkan bonus dalam situasi yang lebih ramai

Dalam salah satu poin itu, saya menyebutkan 'fase' permainan (mis. Pembukaan, midgame, endgame), dan jika Anda ingin memasukkannya ke dalam mesin Anda, Anda mungkin akan mengalami masalah yang sama seperti yang saya lakukan: tidak ada garis yang jelas memisahkan mereka. Fungsi saya yang menentukan fase permainan ini menggunakan beberapa hal:

• Jumlah materi di papan (segera setelah ada bagian yang terbunuh, itu menandai permainan sebagai tidak di pembukaan)
• Jumlah gerakan (kurang dari 6 gerakan penuh adalah pembukaan, apa pun yang terjadi)
• pergerakan ratu (jika kedua ratu telah dipindahkan, tandai game sebagai midgame)

Jawaban ini mungkin panjang, terlambat dan di luar topik, tapi saya harap itu membantu.

Yang mengejutkan, ternyata mesin Minimax akan bermain cukup baik ketika fungsi evaluasi acak ; ini dikenal sebagai efek Beale, dan hasil dari prinsip bahwa posisi yang memberi Anda lebih banyak opsi dan opsi lawan yang lebih sedikit umumnya menguntungkan. Salah satu cara yang masuk akal untuk menghasilkan evaluasi acak secara konsisten dan efisien adalah dengan menghasilkan hash Zobrist untuk posisi tersebut (menggunakan koefisien yang dipilih secara acak pada awal permainan), dan memperoleh evaluasi acak langsung dari hash.

Di ujung skala, AlphaZero dan Leela melakukan evaluasi yang sangat canggih dari setiap posisi yang dicari, menggunakan jaringan saraf besar . Tidak praktis untuk menggambarkan dalam istilah manusia apa fungsi yang diterapkan jaringan ini secara efektif, tetapi tidak dapat disangkal lebih efektif daripada fungsi evaluasi Stockfish. Makalah penelitian AlphaZero menunjukkan bahwa pendekatan ini bekerja paling baik dengan Pencarian Pohon Monte-Carlo daripada Minimax.

Di lain pihak, jika Anda ingin mengembangkan mesin analisis untuk membantu pemain manusia atau komentator memahami nuansa suatu posisi, mungkin bermanfaat untuk mengimplementasikan fungsi evaluasi konvensional menggunakan nilai-nilai material yang sudah ada dan teori posisi . Contoh yang bagus diberikan oleh Inside Rebel karya Ed Schröder , yang mendokumentasikan fitur desain utama dari mesin yang dianggap baik yang digunakan di beberapa komputer catur Mephisto. Anda mungkin ingin menggunakan tingkat tertentu pembelajaran mesin untuk menentukan kepentingan relatif setiap elemen fungsi evaluasi Anda, dan juga membagi elemen-elemen ini secara individual untuk presentasi dalam GUI.

Saya pikir programmer catur cenderung tidak bergantung pada pengetahuan pemain catur yang kuat ketika merancang fungsi evaluasi mereka, tetapi mencoba elemen yang berbeda, dan kemudian mengujinya dalam permainan melawan mesin lain, dan memutuskan apa yang harus disimpan. Larry Kaufman berbicara sedikit tentang pandangannya tentang apa pemahaman manusia, tetapi kedengarannya Rajlich dan Dailey sangat berorientasi pada hasil, dan tidak mengadopsi gagasan Kaufman secara keseluruhan.

Satu artikel yang saya temukan menarik adalah Zach Wegner membandingkan fungsi evaluasi Rybka dan Buah. Salah satu area di mana Rybka mungkin telah mewakili langkah maju adalah penggabungan tabel ketidakseimbangan material berdasarkan kombinasi potongan tertentu. Kaufman menulis artikel tentang ini juga.

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

Tautan ini adalah titik awal IMHO terbaik. Saya menggunakan ini sebagai titik awal saya untuk program catur saya sendiri & menemukan itu mudah dimengerti dan bermanfaat juga.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

Singkatnya, pendekatan standar untuk menyetel parameter mesin catur adalah dengan:

1. Tentukan parameternya
2. Berikan nilai nominal (awal) parameter
3. Jalankan mesin untuk melihat kinerjanya
4. Sesuaikan nilai parameter untuk mencoba meningkatkan kinerjanya

Kemudian ulangi Langkah 3 dan 4 sampai Anda mencapai tujuan Anda untuk kinerja.

Pendekatan yang biasa dilakukan adalah dengan mendirikan laboratorium di mana mesin berhadapan di turnamen mesin. Banyak game digunakan di mana mesin memainkan kedua warna. Turnamen utama yang menarik melibatkan menjalankan mesin dengan nilai parameter set A melawan mesin yang sama dengan nilai parameter set B.

Seperti yang bisa Anda tebak, hasil dari pendekatan ini sangat bergantung pada:

• Parameter yang dipilih
• Bagaimana parameter ditentukan
• Bagaimana nilai parameter divariasi selama pengujian
• Bagaimana mesin dijalankan (ply-depth, waktu terbatas, sensitivitas, dll)

Pendekatan ini juga menghabiskan banyak waktu.

Pendekatan yang lebih baru (dan inovatif) dikembangkan pada tahun 2010 oleh para peneliti menggunakan teknik Algoritma Genetika untuk a) menentukan parameter, dan b) menyesuaikan nilai parameter. Para penyelidik pertama-tama menjalankan mesin dengan nilai parameter awal yang dimulai terhadap serangkaian game grandmaster untuk melihat apakah itu dapat secara efektif memilih "langkah terbaik". "Langkah terbaik" didefinisikan sebagai langkah yang dibuat grandmaster *. Di mana pun hal itu gagal dilakukan, dicatat. Kemudian, set nilai parameter lain dicoba, dan kinerja relatif vs run sebelumnya ditentukan.

Kemudian, pendekatan terprogram untuk menggabungkan nilai - nilai parameter diadili, menggunakan prinsip Genetika Algoritma survival of the "fittest". Di sini, "fittest" berarti yang menghasilkan keluaran yang paling cocok dengan yang ideal. (Ini juga terjadi pada teknik statistik dari regresi "kuadrat cocok", teknik yang digunakan untuk menilai kualitas perkiraan.)

Hanya setelah parameter engine ditemukan yang dapat meniru GM dengan cukup baik, fase turnamen engine yang sebenarnya dimulai. Dalam fase ini, set nilai parameter yang berbeda sekali lagi diadu satu sama lain, kali ini secara langsung . Teknik peningkatan Algoritma Genetika diterapkan untuk menghasilkan generasi mesin yang lebih baik secara berturut-turut.

Dalam proyek penelitian ini, 36 parameter digunakan, termasuk semua nilai material dari potongan-potongan, dan banyak kriteria evaluasi strategis yang lebih umum, seperti pion mundur, petak lemah, pasangan uskup, dan sebagainya. Namun, para peneliti menambahkan beberapa parameter baru, seperti "tekanan raja", "mobilitas" nilai untuk setiap jenis potongan, meng-rook pada file yang berdekatan dengan raja, rook pada file semi-terbuka, benteng menyerang raja pada - / b- / g- / h-file, pemisahan antara gadai yang disahkan dan raja yang membela, dan banyak lagi.

Sayangnya, para peneliti tidak menguraikan bagaimana mereka datang dengan rangkaian parameter ini, dan parameter alternatif apa yang mungkin telah mereka uji dan tolak. Akan masuk akal untuk mengasumsikan bahwa mereka mulai dengan set yang jauh lebih besar, dan menentukan (melalui coba-coba) mana yang memiliki efek terbesar pada kinerja, dan mana yang tidak signifikan atau turunannya, dan dengan demikian dapat dibatalkan.

Jika ini sepertinya bermanfaat, Anda dapat menemukan penelitian di sini .

* Peringatan tentang fase pendekatan yang digunakan para peneliti. Dalam bukunya Introduction to Understanding Chess Move by Move , John Nunn memilih "... game-game perjuangan keras antara grandmaster yang kuat ..." untuk mengilustrasikan tema-temanya. Dia kemudian menambahkan:

Pembaca mungkin cukup terkejut melihat jumlah tanda tanya yang menghiasi permainan dalam buku ini. Tentunya, Anda mungkin berpikir, dengan hanya tiga puluh permainan untuk dipilih, seharusnya mudah untuk menemukan beberapa permainan suara. Namun, saya dapat meyakinkan Anda bahwa itu tidak benar. ... adalah mungkin untuk menemukan kesalahan dengan hampir semua permainan yang rumit dan sulit ... Saya tidak pernah merasa bahwa permainan saya hampir sepenuhnya akurat, jadi saya pribadi tidak menganggap wahyu ini menyedihkan. Namun, beberapa orang mungkin merasa sulit untuk mengakui bahwa catur yang dimainkan oleh manusia kurang akurat daripada yang diperkirakan sebelumnya.

Poin yang diangkat oleh Dr. Nunn menunjukkan bahwa pendekatan awal para peneliti untuk mengatur parameter mesin dengan mengharuskan mereka untuk meniru gerakan grandmaster mungkin cacat karena permainan manusia cacat . Bahkan, sudah mapan bahwa mesin sudah bermain lebih baik daripada manusia .

Oleh karena itu, mungkin pendekatan yang lebih baik untuk mengatur parameter awal adalah mencocokkan mesin baru dengan mesin yang sudah ada .

Ada situs web yang bagus di:

https://hxim.github.io/Stockfish-Evaluation-Guide/

Ini memberi Anda pengantar tentang bagaimana fungsi Stockfish bekerja.