Bagaimana cara menggunakan Kecerdasan Buatan pada Catur Komputer

Dalam beberapa makalah (historis), catur telah disebut sebagai drosophila kecerdasan buatan. Sementara saya mengira bahwa dalam penelitian saat ini, aplikasi algoritma pencarian belaka adalah yang terbaik ilmu komputer , saya percaya bahwa masih ada daerah di mana dapat menerapkan (dan berlatih) teknik AI.

Contoh sederhana akan membuka buku belajar di mana seseorang dapat mengajarkan program apakah menggunakan atau tidak menggunakan gerakan tertentu dalam pembukaan karena program tidak cocok untuk jenis posisi tertentu. Kita dapat menggunakan bentuk pembelajaran penguatan kembali dan mengotomatiskan ini: Saya kira saya bisa memainkan program melawan dirinya sendiri dan meningkatkan probabilitas garis menang dan mengurangi kemungkinan garis hilang.

Contoh yang lebih kompleks adalah dengan menggunakan fungsi evaluasi pembelajaran (misalnya, seseorang dapat mengubah nilai tabel piece-square ). Namun, saya berpikir:

diberikan semua kebisingan karena ada sejumlah besar posisi realistis (sebagai lawan dari jumlah garis pembukaan realistis)
dan dengan biaya (durasi) permainan catur komputer, dan kebutuhan untuk bermain banyak.

Bagaimana seseorang dapat melakukan ini secara efektif? (Atau haruskah saya melihat teknik lain, misalnya jaringan saraf.)

artificial-intelligence board-games ljgw
sumber

Pendekatan standar adalah minimax pemangkasan alpha-beta. dengan heuristik. Itu dari keluarga Pencarian AI, bukan dari keluarga mesin-belajar.

Lyndon White

Master catur yang sebenarnya pada dasarnya hanya mengingat semua game yang telah mereka mainkan sebelumnya ... Jadi mereka memiliki memoisasi yang kuat.

Ada juga klaim kontra. Saya tidak ingat siapa yang mengatakannya tetapi seperti ini. Ahli biologi menggunakan percobaan pada drosophila untuk mendapatkan pemahaman yang lebih dalam dan lebih dalam tentang fisiologi, genetika dan sebagainya. Orang AI menulis komputer catur menjadi lebih baik dan lebih baik dalam bermain catur. Ini sama sekali tidak mengajarkan kita tentang ilmu komputer; itu akan seperti para ahli biologi membiakkan drosophila super cepat, super kuat dan membuat mereka saling bertarung.

David Richerby

Dengan metafora, itu bisa dibayangkan lebih dari "drosophila kecerdasan buatan" dengan aspek yang berbeda, terutama mengingat itu tidak secara meyakinkan mengalahkan manusia top sampai ~ 1997, & penelitian ke dalamnya terus berlanjut, dll

vzn

Jawaban:

Seluruh ruang negara untuk catur sangat besar - kira-kira dapat diperkirakan sebagai 10 ⁴³ (nomor Shannon (Shannon, 1950) , ( Wikipedia )).

Gagasan yang Anda sajikan - agen Pembelajaran Penguatan yang saling bermain untuk mempelajari permainan - berhasil diterapkan pada Backgammon - TD-Gammon (Tesauro, 1995) , ( Bab dalam Pembelajaran Penguatan oleh Sutton & Barto ). Itu juga menggunakan Neural Networks untuk memperkirakan fungsi nilai gim. Namun masalah ini jauh lebih sederhana, karena jumlah negara di Backgammon secara signifikan lebih kecil daripada di catur, yaitu: 18.528.584.051.601.162.496 ( thread Arsip Forum Backgammon ).

Jika Anda, bagaimanapun, akan mengakhiri permainan setelah beberapa langkah awal dan bertujuan hanya untuk belajar "bukaan yang baik" Anda bisa berhasil dengan pendekatan analog. Masalah utama adalah untuk mengevaluasi permainan setelah pertandingan pembukaan, yang tampaknya sulit. Hanya mengukur kesamaan dengan posisi yang ditetapkan setelah bukaan terkenal tidak cukup, karena posisi bisa jauh dari mereka jika lawan akan membuat langkah bodoh (jadi itu bukan karena kesalahan agen pembelajaran, sehingga posisi bahkan jika "salah "Harus dievaluasi sebagai hasil yang baik).

Referensi:

BartoszKP
sumber

Bagian tersulit memang datang dengan cara empiris untuk menilai hasil dari pembukaan. Bukaan yang berbeda adalah baik dengan cara yang berbeda, jadi mungkin ada banyak bukaan yang dapat diterima.

JDong

Saya cukup yakin bahwa setiap kemungkinan (atau aneh) metode AI atau ML dalam buku teks telah dicoba dan cukup banyak gagal dibandingkan dengan brute force sederhana.

Perspektif pribadi saya adalah bahwa catur itu sendiri tidak lagi menarik bagi AI modern ... Sederhananya, karena diselesaikan : dengan hanya menggunakan komputer modern dan kekuatan kasar. Jadi, saya tidak merasa bahwa ada kebutuhan untuk menciptakan sistem "cerdas" untuk menyelesaikannya secara lebih efisien (berfungsi dengan baik di ponsel saya), dan saya percaya bahwa tidak ada kebutuhan untuk beberapa yang tidak dikenal dan lebih Pendekatan "cerdas" ada.

iliasfl
sumber

Saya tidak yakin mengapa ini diturunkan. Argumen bahwa catur "diselesaikan" sedikit tidak akurat, bahwa tidak ada komputer yang dapat melihat posisi yang memungkinkan dan mengevaluasinya dengan sempurna. Yang mengatakan, iliasfl adalah spot-on bahwa catur telah kehilangan sebagian besar daya tariknya untuk penelitian AI. Untuk satu hal, program catur komputer terbaik sekarang jauh lebih kuat daripada manusia terbaik, diberi cukup kekuatan pemrosesan dan waktu. Ini membuat semakin sulit bagi programmer bahkan untuk mengevaluasi seberapa baik suatu algoritma bekerja.

elixenide

Terima kasih, saya katakan diselesaikan dalam arti bahwa kekerasan adalah solusi. Tentu saja komunitas AI (secara umum tidak hanya di sini) tidak senang dengan "solusi" itu. Namun, kami sudah memiliki sistem komputasi yang menghadirkan perilaku "cerdas" untuk menyelesaikan tugas ini, dan bahkan memenangkan manusia terbaik, titik. Secara pribadi, saya percaya bahwa catur akan di luar topik untuk AI setelah beberapa tahun ketika banyak akademisi saat ini yang menghabiskan karir untuk menyerang itu pensiun.

Saya tidak akan menyebut implementasi catur komputer saat ini sebagai 'diselesaikan dengan brute force' - mereka masih mencari lebih banyak gamestate, tetapi ada banyak komponen non-brute force di sana. Tentu saja, mereka bukan solusi "gaya manusia" yang akan menggeneralisasi dengan baik untuk masalah lain, tapi saya tidak akan terkejut bahwa jika kita memiliki AI catur "gaya manusia", maka itu akan menjadi beberapa urutan besarnya kurang efisien daripada solusi khusus saat ini, menjadikannya lebih rendah.

Peteris

Saya pikir jawaban ini dan komentarnya cukup jelas dibantah oleh Google AlphaZero: en.wikipedia.org/wiki/AlphaZero Bahkan jika Anda menerima kritik tentang pengaturan untuk Stockfish dan mereka telah menarik semua pertandingan, sistem yang mencapai tingkat itu dengan beberapa jam pelatihan jelas lebih unggul.

Kamal

Saya pikir perlu dicatat bahwa untuk menentukan bagaimana mengatasi masalah AI Anda harus mendefinisikannya. Apakah itu sepenuhnya dapat diamati atau sebagian dapat diamati , dan apakah itu bersifat deterministik atau stokastik / peluang.

Catur adalah Sepenuhnya diamati, (tidak seperti Backgammon, Monopoly atau poker misalnya) Hal ini juga deterministik (seperti Checkers, dan Go misalnya) Terakhir, musuh ada dan karena itu saat menentukan berikutnya langkah terbaik hal ini berguna untuk menggunakan Adversarial Pencarian jenis algoritma seperti MiniMax. Mengklasifikasikan masalah dapat membantu kami menentukan jenis algoritma pencarian yang ingin kami terapkan. Dan dalam hal catur, Pencarian Adversarial akan cocok.

Minimax khususnya memiliki a

$O(b^n)$

$O(bm)$

Jadi dalam hal catur, b akan menjadi 35, dan m akan menjadi 100. Ada cara di sekitarnya atau strategi untuk membuatnya lebih efisien, seperti cutoff alpha-beta.

Iancovici
sumber

Juga perlu dicatat dalam konteks ini, bahwa permainan akhir untuk catur hingga beberapa potong sudah ditabulasi - optimasi lebih lanjut.

BartoszKP

Ini adalah pendekatan normal tetapi bukan pendekatan pembelajaran mesin. Pertanyaannya menggunakan tag Machine-learning.

Lyndon White

@Oxinabox meskipun itu dulu benar, penanya tidak menyebutkan di mana dalam judul atau badan yang ia minati dalam pendekatan pembelajaran mesin, hanya pada bagian akhir di mana ia berbagi satu contoh pendekatan yang ada dalam pikirannya. Tidak perlu membatasi masalah untuk Pembelajaran Mesin, atau algoritma pembelajaran tunggal (NN).

Iancovici

Memang, ini bagus

Lyndon White

tepatnya, catur tidak dapat diamati sepenuhnya, karena diberi posisi yang kita tidak tahu, misalnya, apakah seorang raja atau benteng sudah bergerak atau tidak, meskipun itu penting untuk generasi bergerak (apakah masih ada kemungkinan castling?), tetapi seorang programmer dapat membuatnya Sepenuhnya Diobservasi dengan mengubah representasi posisi yang membedakan king / rook yang tidak bergerak dan memindahkan king / rook sebagai angka yang berbeda, meskipun itu menambah beberapa kesulitan.