Membuat mesin catur, pembelajaran mesin vs. mesin tradisional?

17

Saya seorang pemain catur yang rajin dan programmer komputer. Saya akan mengatakan bahwa bermain catur dan pemrograman adalah dua hal yang paling sering saya lakukan. Secara alami, saya ingin membuat mesin sendiri dan, akhirnya, bot Lichess.

Setelah kinerja penghancuran AlphaZero terhadap Stockfish tahun lalu, saya mempertimbangkan apakah saya harus membuat mesin ini dengan pembelajaran mesin (beberapa jenis jaringan saraf, mungkin menggunakan Tensorflow) atau heuristik tradisional, kode keras.

Saya kurang terbiasa dengan jaringan saraf daripada jenis hard-coding lainnya. Namun, itu bisa menjadi cara yang baik bagi saya untuk belajar bekerja dengan jaringan saraf.

Hal lain yang saya pertimbangkan adalah apakah penting bahasa apa yang saya gunakan untuk kode mesin. Saya tahu banyak mesin catur menggunakan C ++, yang belum pernah saya gunakan sebelumnya. Saya telah menggunakan bahasa berbasis C lainnya yang melakukan banyak hal yang sama, dengan sebagian besar sintaks yang bervariasi. Saya paling akrab dengan Swift dan Javascript, tetapi saya juga akrab dengan Python dan merasa itu bisa melakukan trik untuk saya.

Jadi, dalam hal menciptakan mesin catur terkuat mungkin, haruskah saya menggunakan jaringan saraf atau hard-coded?

engines programming computer-chess David Chopin
sumber
4
Mereka kunci untuk mesin AI baru tidak begitu banyak NN sebagai pembelajaran penguatan. RL adalah topik yang kompleks, tetapi ada sumber pengantar online yang bagus seperti ceramah RL David Silver di UCL (slide di situs webnya dan ceramah di YouTube. Dia bekerja dengan Deepmind dan alfabet yang dibahas secara tradisional di kuliah terakhir. Anda mungkin bisa mengembangkan AI yang menarik mesin tanpa NN menggunakan heuristik berkode keras dan RL. Beginilah cara alphago dimulai!
asac - Reinstate Monica
Ini bukan catur, tetapi buku terbaru "Deep Learning and the Game Go" menunjukkan bagaimana menggunakan NNs untuk mesin game. Alpha-Go dan Alpha-Zero serupa di bawah tenda.
John Coleman
Mengingat pengalaman Python Anda, mungkin layak untuk melihat Nim
Darren H
Jika Anda ingin mencoba NN, ini menarik: arxiv.org/abs/1509.01549 Ada juga kode di github :)
Ant
@ Tidak perlu diketahui bahwa Giraffe tidak pernah sangat kuat dibandingkan dengan mesin-mesin top. (~ 2800 elo)
Oscar Smith

Jawaban:

8

Langkah pertama: Tentukan tujuan / alasan Anda

Saya pikir ini adalah faktor utama. Mana yang paling cocok untuk Anda? (Pilih satu saja )

  1. Anda ingin menikmati tugas pengkodean yang menyenangkan dan menantang
  2. Anda ingin membuat mesin catur yang sangat bagus
  3. Anda ingin belajar tentang cara kerja mesin catur
  4. Anda ingin belajar / berlatih keterampilan coding
  5. Anda ingin belajar / menerapkan konsep / teori sains komputer (mis. Pembelajaran mesin)
  6. (Lain)

IMO tidak apa-apa untuk "melempar koin" untuk apa pun kecuali 2. Untuk semua yang lain, Anda akan memenuhi tujuan Anda apakah Anda memilih ML atau hard-coding. Namun Anda mungkin menginginkan perbandingan antara pilihan untuk membantu Anda memutuskan.

Kasus untuk hard-coding

Bermain catur (sebagai manusia) melibatkan pemikiran logis. Anda menjelajahi ruang tindakan yang mungkin Anda dan lawan bisa ambil. Ini telah melahirkan bidang yang disebut teori permainan yang berisi kerangka teori untuk menganalisis game secara umum.

Jika Anda menikmati bekerja dengan detail dan menjadi spesifik dan bernalar tentang hal-hal maka ini bisa bekerja dengan baik untuk Anda. Sebagai perbandingan, pembelajaran mesin melibatkan lebih banyak "kotak hitam" algoritma yang fuzzy dan buram. Anda tidak tahu persis apa yang sedang terjadi.

Juga saya rasa Anda akan memiliki waktu yang lebih mudah "mencari tahu sendiri" jika Anda memilih rute hard-coding daripada pembelajaran mesin. Lebih sedikit hal menempelkan salinan yang tidak sepenuhnya Anda pahami.

Kasus untuk pembelajaran mesin

Sangat menyenangkan untuk melahirkan ciptaan dan menyaksikannya menjalani kehidupannya sendiri. Sementara hard-coding adalah semua tentang presisi dan detail, pembelajaran mesin fleksibel. Singkirkan beberapa neuron dan hasilnya mungkin akan serupa.

Hard-coding adalah tentang mempelajari catur. Pembelajaran mesin adalah tentang mempelajari makhluk yang telah Anda buat.

Dan pembelajaran mesin, tentu saja, adalah topik yang sangat panas.

Pilihan bahasa untuk hard-coded

Saya tidak yakin apa yang Anda maksud dengan "bahasa berbasis C lainnya". C ++ adalah satu-satunya bahasa umum yang mirip dengan C. Keuntungan C / C ++ adalah mereka cepat . Meskipun bahasa lain telah menyusul selama bertahun-tahun, C ++ masih memberi mereka uang.

C ++ tidak mudah. Anda akan mendapatkan performa luar biasa dari bahasa yang dikompilasi lebih modern seperti Rust, Golang atau Swift. Tetapi seharusnya tidak jauh lebih buruk jika Anda menggunakan bahasa JIT. Yaitu jangan menggunakan juru bahasa CPython ; gunakan IronPython atau Jython, atau Node, atau C # atau Java.

Pemrograman GPU membutuhkan pendekatan yang berbeda dan saya akan menyarankan untuk tidak melakukannya pada saat ini.

Pilihan bahasa untuk pembelajaran mesin

Masalah dengan TensorFlow adalah tingkatannya sangat rendah. Ini lebih tentang menulis algoritma angka-penggerusan (yang dapat ditanamkan ke perangkat keras paralel) daripada tentang antarmuka yang didedikasikan untuk pembelajaran mesin.

Tentu saja, ini bisa menjadi pengalaman belajar yang luar biasa! Dan tentunya belajar sangat bermanfaat hari ini. Namun, Anda mungkin ingin memulai dengan Keras atau PyTorch.

Artelius
sumber
1
Ini adalah respons yang fenomenal, sangat menyentuh semua poin yang saya sebutkan. Agak sulit untuk mengatakan mengapa saya ingin membuat mesin. Secara realistis, saya kemungkinan tidak akan bersaing dengan orang-orang seperti Stockfish, Komodo, dan Leela (bagaimanapun, saya hanya seorang mahasiswa). Tetap saja, akan menyenangkan untuk melihat pekerjaan saya berhadapan dengan mesin lain dan tidak dihancurkan setiap waktu. Bahkan jika alasan utama saya adalah membuat mesin yang kuat, saya kemungkinan akan belajar bahasa pemrograman baru dan meningkatkan pengetahuan catur saya sebagai produk sampingan dari pembuatan mesin.
David Chopin
1
Saya berpikir lebih dari apa pun yang saya inginkan, saya bisa membuat, memelihara, dan menyempurnakan jangka panjang. Saya juga ingin proyek yang secara obyektif akan memberi tahu saya seberapa baik kode saya (Menang / Menarik / Kehilangan, ELO, dll.).
David Chopin
1
Ini jawaban yang sangat menarik tetapi apakah Anda serius merekomendasikan Node over Cpython untuk masalah kinerja ?
Evpok
> "C ++ adalah satu-satunya bahasa utama yang mirip dengan C." C #? Karat? Jawa? Ada banyak bahasa yang setidaknya "mirip dengan C"
Maaark
Saya menganggap "like C" sebagai bahasa yang dikompilasi, sangat dioptimalkan, diimplementasikan ke mesin dengan sintaks C-style. C #, Java, dan PHP semuanya menggunakan mesin virtual, dengan kode mereka dikompilasi ke opcodes daripada bytecode khusus CPU (dan kompilasi PHP sepenuhnya transparan, seperti Python dan Bash). Dan Rust bukan arus utama. Hanya C ++ yang "seperti C" dalam hal ini, meskipun berbagi gaya sintaksis dengan beberapa bahasa utama lainnya.
Ghedipunk
24

Jika Anda mencoba membuat mesin sekuat tenaga, gunakan mesin NN.

Mesin tradisional hebat - Stockfish bisa dibilang masih merupakan mesin terkuat di planet ini pada perangkat keras yang setara - tetapi mereka sulit untuk ditulis. Mesin ini tidak sampai di tempat semalaman; mereka membutuhkan waktu bertahun-tahun untuk bekerja. Stockfish misalnya telah memperoleh elo selama enam tahun . Jika Anda memulai dari awal, Anda tidak akan mendapatkan kekuatan Stockfish dengan cepat; bahkan Anda mungkin akan berhenti beberapa ratus elo dari tempat Stockfish saat ini. Sebagai perbandingan, beberapa mesin penulis tunggal terkuat saat ini adalah Ethereal , Laser , dan Xiphos (saya mengabaikan Houdini & Fire karena tidak open source). Mesin-mesin ini jauh lebih lemah daripada Stockfish.

Mengapa mereka jauh lebih lemah? Dua alasan:

  1. Pada level ini, mengembangkan mesin membutuhkan banyak daya komputasi. Apa yang Anda lakukan adalah melihat-lihat kode Anda dan mengidentifikasi sebuah ide yang bisa mendapatkan lebih banyak. Sebuah ide contoh adalah, "jika kita tahu langkah ini mungkin baik, jangan mencari cabang yang membalikkan langkah itu" (jika ini tidak masuk akal bagi Anda, itu berarti akan ada kurva belajar yang tinggi juga). Anda kemudian menulis tambalan yang mengimplementasikan ide, dan menguji mesin yang dimodifikasi terhadap versi sebelumnya. Pada level ini, dibutuhkan puluhan ribu game untuk mendapatkan ukuran sampel yang cukup besar untuk mengetahui apakah patch tersebut efektif. Memainkan game-game ini membutuhkan daya komputasi yang sangat besar. Stockfish memiliki akses ke perangkat keras super: pada saat penulisan, Stockfish menguji Fishtestingsedang berjalan dengan 1038 core. Sebagai perbandingan, komputer desktop biasa mungkin memiliki 4-8 core.

  2. Alasan lainnya adalah Stockfish didukung oleh banyak otak. Pada saat penulisan, ada 8 tambalan yang ditulis oleh 5 orang yang diuji. Jika Anda melihat sejarah tambalan Anda akan menemukan lebih banyak pengembang yang telah menulis tambalan. Saya tidak tahu berapa banyak pengembang Stockfish aktif, tapi itu pasti> 20.

Di sisi lain, mesin NN (relatif) dengan mudah mencapai kekuatan yang jauh di atas Ethereal / Laser / Xiphos. Lihat sendiri di turnamen Kejuaraan Mesin Catur Top terbaru . Ethereal / Laser / Xiphos ada di League 1, yang cukup kredibel, tetapi mesin di divisi teratas (Division P) adalah:

  • Stockfish (mesin tradisional yang didukung masyarakat, berjalan dengan Fishtesting)
  • Komodo (mesin tradisional komersial, memiliki pengembang penuh waktu)
  • MCTS Komodo (mesin semi tradisional tradisional, memiliki pengembang penuh waktu)
  • Houdini (mesin tradisional komersial, adalah upaya satu orang, belum diperbarui selama dua tahun)
  • Leela Chess Zero (mesin NN yang didukung komunitas, berjalan dengan analog dari Fishtesting alias satu ton perangkat keras)
  • AllieStein (mesin NN 2-man)
  • Stoofvlees (mesin NN)
  • ScorpioNN (mesin NN)

Tiga mesin terakhir - AllieStein, Stoofvlees, dan ScorpioNN - semuanya merupakan kolaborasi kecil oleh orang-orang yang, sejauh yang saya tahu, adalah penggemar seperti Anda dan bukan pengembang penuh waktu. Mereka mendapatkan kekuatan Div P setelah kurang dari dua tahun mencoba (semua mesin NN ini hanya muncul setelah AlphaZero). Sebagai perbandingan, dalam sejarah catur komputer baru-baru ini hanya ada satu orang yang pernah menulis mesin tradisional yang berhasil bersaing dengan Stockfish & Komodo sendiri (Robert Houdart, penulis Houdini).

Memang benar bahwa Anda mungkin tidak akan memiliki perangkat keras untuk bersaing dengan Lc0, tetapi Lc0 mengambil kekuatan komputasi sebesar ini karena itu adalah mesin "nol" - itu seharusnya bermain catur tanpa pengetahuan manusia apa pun kecuali aturan. Anda tidak perlu menggunakan metodologi yang sama. Anda dapat menggunakan misalnya metodologi Stein yang menggunakan pembelajaran terawasi. Ini bisa dibilang lebih baik daripada menjadi "nol" - lagipula AllieStein bermain di dangkal, bukan Lc0.

Hasilnya adalah: jika tujuan Anda adalah untuk bersaing dengan mesin terbaik di dunia, Anda jauh lebih mungkin untuk berhasil dengan mesin NN daripada yang tradisional.

Daya tarik
sumber
6
Mungkin sebutkan sisi lain kesimpulan Anda: Jika tujuan Anda adalah untuk memperdalam pemahaman Anda tentang catur saat melakukan beberapa pemrograman, pilihlah yang tradisional.
blues
1
Saya setuju dengan kesimpulan Anda, tetapi saya juga akan merekomendasikan menggunakan jaringan baru-baru ini dari mesin yang kuat (dengan izin tentu saja) sebagai titik awal daripada memulai dari awal (tetapi melanjutkan dengan cara yang berbeda dari "melatih melalui permainan sendiri dan memperbarui bobot ", dengan menambah atau menghapus lapisan, menambahkan fitur input, menuntut output tambahan, dll.). Saya tidak ingat apakah Lc0 adalah satu kepala atau dua kepala, tapi saya percaya 3 kepala ( ijcai.org/proceedings/2018/0523.pdf ) saat ini tidak diimplementasikan oleh mesin catur, dan akhirnya dapat meningkat pada kondisi saat ini. -seni.
Steven Jackson
Saya pikir pencarian Allie yang membuatnya lebih kuat melawan mesin yang lebih lemah (KMCST, Stoofvlees), bukan jaringan Stein.
saya '
@blues Saya pikir memprogram mesin catur tidak benar-benar menjadikannya pemain catur yang lebih baik - dengan pengecualian Larry Kaufman (salah satu pengembang Komodo), tidak ada mesin teratas yang memiliki judul pemain sebagai pengembang, atau membuat pengembang mereka menjadi pemain berjudul.
Allure
@ Saya itu mungkin tapi Leelenstein adalah jaringan Stein menggunakan binary Lc0, dan itu dilakukan dengan baik di kejuaraan catur komputer catur.com, jadi jaringan Stein setidaknya sebanding dengan jaringan Lc0.
Allure
9

Jadi, dalam hal menciptakan mesin catur terkuat mungkin, haruskah saya menggunakan jaringan saraf atau hard-coded?

Jangan memilih NN kecuali Anda memiliki akses ke konyol (Beberapa ratus Nvidia V100s). Melatih NN untuk bermain catur membutuhkan banyak perangkat keras. Lihat orang-orang yang berkontribusi pada Lc0 untuk melatih lebih dari 200 juta game. Karena Anda mungkin akan kesulitan mengakses perangkat keras (Anda bisa mencoba mendapatkannya di Google Colabatory , tetapi hanya dengan itu, pelatihan akan menjadi sangat lambat).

Sunting: Menggunakan NN Dengan Pembelajaran terawasi, Anda MUNGKIN pergi hanya dengan Google Colab dan mungkin satu GPU kuat (2080, 2080Ti, Radeon VII).

Hal lain yang saya pertimbangkan adalah apakah penting bahasa apa yang saya gunakan untuk kode mesin. Saya tahu banyak mesin catur menggunakan C ++, yang belum pernah saya gunakan sebelumnya. Saya telah menggunakan bahasa berbasis C lainnya yang melakukan banyak hal yang sama, dengan sebagian besar sintaks yang bervariasi. Saya paling akrab dengan Swift dan Javascript, tetapi saya juga akrab dengan Python dan merasa itu bisa melakukan trik untuk saya.

Python dan Javascript mungkin terlalu lambat untuk mesin catur yang kuat. Saya belum pernah menggunakan Swift tetapi mungkin tidak akan menyukai platform selain macOS, jadi mungkin lebih baik menggunakan C atau C ++. Anda juga bisa menggunakan Rust, tetapi memiliki banyak fitur keamanan yang mengganggu dan tidak benar-benar Anda butuhkan, yang bisa mengganggu. Akan lebih sulit untuk mendapatkan kinerja yang baik dari itu karena optimasi tingkat rendah tertentu sulit dilakukan. Tentu saja, Anda selalu dapat menulisnya dalam pertemuan tetapi itu mungkin akan menjadi terlalu banyak pekerjaan. lihat https://www.chessprogramming.org/Languages/

saya'
sumber
1
Luar biasa, terima kasih banyak untuk informasinya! Saya mungkin akan mencoba membuat API yang mengambil posisi FEN dan menampilkan langkah yang dihitung. Saya pikir ini adalah cara terbaik untuk berintegrasi dengan bot Lichess.
David Chopin
Ada github.com/careless25/lichess-bot
me '
1
Apakah ini opsi untuk mengimplementasikan mesin NN berbeda yang hanya menggunakan jaringan lc0?
RemcoGerlich
1
@RemcoGerlich seperti yang saya mengerti, mesin NN menggunakan dua hal: biner, dan jaringan saraf. Menulis biner tidak mudah, tetapi melatih jaringan saraf relatif mudah. Dalam pengertian ini derivatif Lc0 sudah ada - Leelenstein & Deus X (alias. Fat Fritz) adalah derivatif semacam itu.
Allure
@RemcoGerlich dalam hal itu tidak akan benar-benar menjadi mesin yang berbeda, itu akan menjadi mesin Ic0 hanya dengan pembungkus / antarmuka yang berbeda / apa pun.
Peteris
3

Saya membangun mesin catur murni mainan menggunakan: catur python itu benar-benar baik tidak harus kode aturan permainan sendiri dan hanya fokus pada logika; namun, jumlah posisi yang dapat saya evaluasi per detik sangat rendah. Ini mungkin titik awal yang baik.

Akavall
sumber