Catur level grandmaster tanpa pencarian

 (github.com/google-deepmind)
2 poin oleh GN⁺ 2024-10-19 | 1 komentar | Bagikan ke WhatsApp
  • searchless_chess dari Google DeepMind adalah implementasi paper NeurIPS 2024 Amortized Planning with Large-Scale Transformers, yang mengevaluasi seberapa baik Transformer skala besar menangani masalah perencanaan menggunakan catur tanpa pencarian eksplisit
  • Dataset inti ChessBench terdiri dari 10 juta permainan catur dengan langkah legal dan anotasi nilai dari Stockfish 16, total 15 miliar titik data
  • Transformer hingga 270 juta parameter dilatih dengan supervised learning, lalu dibandingkan dampaknya dengan mengubah ukuran dataset, ukuran model, jenis arsitektur, dan target prediksi
  • Model terbesar dapat memprediksi action-value dengan cukup akurat pada papan baru, memecahkan puzzle catur sulit tanpa pencarian eksplisit, dan mencapai Elo blitz Lichess 2895 melawan pemain manusia
  • Algoritme berbasis pencarian milik Stockfish dapat didistilasi dengan cukup baik ke Transformer skala besar, tetapi distilasi penuh masih belum tercapai sehingga ChessBench tetap menjadi benchmark untuk riset lanjutan

Tujuan proyek dan konteks paper

  • searchless_chess adalah implementasi dari Amortized Planning with Large-Scale Transformers: A Case Study on Chess
  • Catur digunakan sebagai masalah perencanaan yang representatif dalam AI, dan proyek ini mengevaluasi kinerja Transformer pada tugas yang tetap tidak bermakna untuk dihafal bahkan dalam skala besar
  • Riset ini menguji di ranah catur apakah perilaku engine catur berbasis pencarian dapat didistilasi ke Transformer melalui supervised learning

Dataset ChessBench

  • ChessBench mencakup langkah legal dan anotasi nilai yang disediakan oleh Stockfish 16
    • Jumlah permainan catur: 10 juta
    • Total titik data: 15 miliar
    • Stockfish 16 digunakan sebagai engine catur tingkat mutakhir
  • Dataset dibagi menurut target prediksi

    • Action-Value

    • Behavioral Cloning

    • State-Value

      • puzzles.csv untuk evaluasi puzzle
      • Contoh ukuran unduhan adalah sebagai berikut
      • Train Action-Value: shard pertama 1.2GB, total 1.1TB, total 2148 shard
      • Train Behavioral Cloning: 34GB
      • Train State-Value: 36GB
      • Test Action-Value: 141MB
      • Test Behavioral Cloning: 4.1MB
      • Test State-Value: 4.4MB
      • Puzzles: 4.5MB

Model dan pengaturan eksperimen

  • Transformer dilatih hingga 270M parameter
  • Pelatihan dilakukan dengan supervised learning berbasis ChessBench
  • Eksperimen membandingkan pengaruh faktor-faktor berikut
    • ukuran dataset
    • ukuran model
    • jenis arsitektur
    • target prediksi: state-values, action-values, behavioral cloning
  • Model terbesar dapat memprediksi action-values dengan cukup akurat pada papan baru, menunjukkan generalisasi yang melampaui sekadar menghafal

Kinerja tanpa pencarian dan pembanding

  • Kebijakan catur akhir memecahkan puzzle catur sulit tanpa pencarian eksplisit
  • Model ini mencapai Elo 2895 pada Lichess blitz melawan pemain manusia, menunjukkan performa setingkat grandmaster
  • Pembanding mencakup Leela Chess Zero dan AlphaZero
    • Kedua sistem dibandingkan sebagai model yang dilatih lewat self-play
    • Perbandingan dilakukan baik saat menggunakan pencarian maupun tanpa pencarian
  • Algoritme berbasis pencarian milik Stockfish dapat didistilasi dengan sangat baik sebagai aproksimasi ke Transformer skala besar, tetapi distilasi penuh masih belum memungkinkan

Struktur repositori dan alur eksekusi

  • Direktori dan file utama memiliki peran berikut
    • src/engines: antarmuka untuk Stockfish, Leela Chess Zero, dan engine jaringan saraf
    • src/transformer.py: Transformer decoder-only
    • src/train.py: skrip contoh pelatihan dan evaluasi
    • src/puzzles.py: skrip evaluasi puzzle
    • src/tournament.py: skrip turnamen Elo
    • src/searchless_chess.ipynb: notebook analisis perilaku model
    • src/tokenizer.py: tokenisasi papan catur
  • Checkpoint pralatih tersedia untuk model 9M, 136M, dan 270M
  • Notebook analisis perilaku model dapat digunakan untuk menjalankan analisis seperti menghitung tingkat kemenangan semua langkah legal

Instalasi dan dependensi

  • Lingkungan eksekusi membutuhkan Python 3.10
  • Dependensi yang diperlukan dipasang dengan pip install -r requirements.txt
  • Jika ada GPU, disarankan memasang JAX dengan dukungan CUDA untuk pelatihan yang lebih cepat
    • Contohnya menggunakan perintah instalasi jax[cuda12_pip] untuk CUDA 12
    • Versi JAX harus sesuai dengan instalasi CUDA yang digunakan
  • Perlu memasang engine dan alat eksternal

Evaluasi dan cara pakai

  • Pelatihan lokal dijalankan dari src dengan python train.py
    • Checkpoint disimpan di /checkpoints/local
  • Evaluasi puzzle dijalankan dalam bentuk python puzzles.py --num_puzzles 10 --agent=local
  • Agen yang didukung puzzles.py adalah sebagai berikut
    • model hasil pelatihan lokal: local
    • model pralatih: 9M, 136M, 270M
    • Stockfish: stockfish, stockfish_all_moves
    • Lc0: leela_chess_zero_depth_1, leela_chess_zero_policy_net, leela_chess_zero_400_sims
  • Perhitungan Elo dilakukan dengan membuat permainan lewat python tournament.py --num_games=200, lalu membacakan data/tournament.pgn ke BayesElo untuk menghasilkan rating

Lisensi dan batasan

  • Perangkat lunak didistribusikan di bawah Apache License 2.0
  • Bobot model mengikuti lisensi Creative Commons Attribution 4.0
  • Sebagian dataset mengikuti lisensi Creative Commons CC0 public domain dari lichess.org, dan sisanya mengikuti lisensi CC-BY
  • Distribusi diberikan dengan basis "AS IS", tanpa jaminan tersurat maupun tersirat
  • Proyek ini bukan produk Google resmi

Bacaan terkait

1 komentar

 
GN⁺ 2024-10-19
Opini Hacker News

  • Sedikit off-topic, tapi saya penasaran catur komputer di level non-GM sekarang sudah sampai sejauh mana
    Kadang saya ingin bermain melawan lawan yang kemampuannya mirip dengan saya, atau untuk latihan melawan lawan yang rating-nya sekitar 100 poin lebih tinggi dari saya
    Sebagian besar engine bisa dibuat lebih lemah dengan mengurangi kedalaman pencarian, tetapi biasanya itu tidak bekerja dengan baik. Kalau dikurangi cukup banyak, memang akhirnya saya bisa menang kira-kira separuhnya, tetapi di sebagian besar permainan rasanya saya terus terdesak lalu menang karena engine membuat satu-dua blunder besar
    Yang saya inginkan adalah lawan komputer yang bermain pada level yang saya pilih, tetapi terasa seperti pemain manusia tipikal di rentang rating itu. Saya penasaran apakah engine seperti ini ada

    • Maia cukup bagus. Bisa dicoba dilawan di Lichess
      Ada beberapa momen yang benar-benar terasa “seperti manusia”, misalnya jatuh ke jebakan yang mudah dihindari algoritma pencarian tradisional, tetapi manusia mungkin akan terkena
      Tidak bisa disetel, tetapi ada beberapa versi dengan rating berbeda. Namun rentangnya tidak terlalu luas
      https://www.maiachess.com/
      https://lichess.org/@/maia1
    • Saya pernah membuat sesuatu yang mirip: chessmate.ai. Bekerja dengan baik kalau rating pemainnya tidak terlalu tinggi
      Semakin tinggi rating pemain, prediksi langkah berikutnya makin sulit karena bukan hanya perlu memilih langkah secara intuitif, tetapi juga harus memodelkan proses pencarian itu sendiri
      Dimungkinkan juga membuatnya lebih personal dengan melatihnya hanya memakai rekaman permainan pemain tertentu
      Pendekatannya mirip Maia, tetapi memakai jaringan saraf berbeda sehingga performa kecocokan langkahnya sedikit lebih baik, lalu saya menambahkan algoritma pemaksimalan nilai harapan agar bot mengeksploitasi kesalahan saya
    • Pada akhirnya, menang dalam catur memang seperti itu. Meminimalkan kesalahan
    • Dulu sekali saya memakai engine Fritz dari ChessBase, dan ada fitur sparring. Kalau bermain solid, di tengah permainan ia akan memberi peluang seperti puzzle taktik, dan peringatannya bisa dinyalakan atau dimatikan
      Kalau tidak bermain cukup stabil, saya kalah begitu saja
      Menurut saya fitur ini sepertinya sudah hilang. Karena terasa seperti membuat kesalahan manusiawi saat berada di bawah tekanan, ini satu-satunya komputer yang benar-benar terasa seperti lawan sungguhan, berbeda dari komputer yang bermain seperti mesin lalu secara acak memainkan langkah bodoh
    • Itu sebabnya saya tidak terlalu suka menang di game multipemain. Biasanya kalau menang, rasanya lawan bermain buruk secara konyol beberapa kali, atau lawan bermain bagus tetapi saya menang karena beberapa kali terlalu beruntung
      Sangat jarang ada perasaan bahwa lawan juga bermain bagus, tetapi saya secara keseluruhan sedikit lebih baik sehingga menang secara layak
      Hampir selalu terlihat bukan saya yang menang, melainkan lawan yang kalah. Ini bukan masalah khusus AI
      Kalau ada yang bisa membuat AI yang kalah dengan memuaskan dalam game simetris, sekaligus membuat kekalahan terasa memuaskan untuk dipelajari, itu akan menjadi bisnis bernilai 1 miliar dolar. Saya rasa sulit tanpa riset psikologi yang serius

  • Saya pernah memberi presentasi tentang topik ini, dan juga menuliskan isi presentasinya[1]. Makalah ini adalah contoh bagus dari distilasi pengetahuan
    Dibanding makalah tentang catur itu sendiri, ini lebih seperti makalah yang menunjukkan bahwa fungsi pencarian nonlinier kompleks yang disetel para pakar dapat didistilasi, untuk input yang terstandardisasi seperti catur, menjadi model Transformer yang hampir linear
    [1]: https://hlfshell.ai/posts/deepmind-grandmaster-chess-without...

    • Menurut saya hasil melawan manusia perlu dilihat dengan cukup hati-hati. Ini adalah permainan blitz, dan Elo engine ini jauh lebih tinggi saat melawan manusia dibanding saat melawan bot lain
      Jadi kemungkinan besar waktu adalah faktor. Manusia lebih mungkin kehabisan waktu sampai flag jatuh, atau membuat kesalahan saat waktunya sedikit
      Tetap keren bahwa ia mempelajari fungsi evaluasi yang sangat bagus tanpa pencarian. Namun saya berharap permainan ketika fallback Stockfish aktif dikeluarkan dari perhitungan. Bagi manusia juga, mate dalam 2 langkah dan mate dalam 10 langkah adalah perbedaan antara menang dan remis/kalah dari sudut pandang kalah waktu
      Saya juga ingin melihat duel langsung melawan Stockfish dengan kedalaman pencarian terbatas. Dengan begitu kita kira-kira bisa tahu seberapa banyak pohon pencarian yang telah didistilasi oleh fungsi evaluasi ini

  • Untuk orang yang ingin mulai mempelajari jaringan saraf catur, saya sangat merekomendasikan repositori ini: https://github.com/sgrvinod/chess-transformers
    Kodenya PyTorch yang mudah dibaca, mengikuti pola implementasi umum, dan arsitekturnya juga mirip dengan jaringan saraf catur yang saat ini berperforma bagus

  • https://lczero.org/blog/2024/02/how-well-do-lc0-networks-com...
    Ini adalah tulisan para penulis engine catur jaringan saraf terbaik tentang makalah DeepMind ini

    • Sejak Stockfish menambahkan NNUE pada 2020, LC0 bukan lagi engine catur jaringan saraf terbaik

  • Dataset sintetis raksasa yang dipakai untuk pelatihan pada akhirnya dibuat dengan banyak pencarian tradisional. Jadi ada sisi yang agak lucu, tetapi tetap keren

    • Ini adalah distilasi pengetahuan. Setelah itu, model yang lebih kecil dan efisien bisa dipakai sebagai pengganti model besar
    • Justru ini menunjukkan keterbatasan jaringan saraf. Otak manusia bisa belajar dari contoh yang jauh lebih sedikit
    • Pencarian hanya dilakukan sekali. Kalau efisiensi ini bisa diterapkan pada pengetahuan lain, itu berarti ada sesuatu yang menjanjikan

  • Saya ingat GM sekaligus penulis catur Matthew Sadler, untuk permainan latihan, pernah mengatur Leela Zero agar praktis bermain hanya dengan intuisi, dengan pencarian yang nyaris tidak ada atau sama sekali tidak ada
    Biasanya ia menang, tetapi tidak selalu. Sepertinya itu ada di The Silicon Road to Chess Improvement

    • Ia juga mengunggah video yang sangat menarik di YouTube. Ia menunjukkan penemuan pembukaan aneh seperti apa yang dibuat Leela ketika contempt disetel sangat tinggi agar sebisa mungkin menghindari remis, lalu menambahkan komentar level 2700+ untuk itu
    • Kalau lczero, cukup setel kedalaman maksimum misalnya ke 1 ply

  • Jika data pelatihan dibuat dengan menjalankan Stockfish untuk setiap posisi papan di semua permainan, bukankah pada akhirnya itu berarti mengenkode pohon pencarian ke dalam model Transformer?
    Kalau begitu, semakin banyak jumlah parameter model, semakin banyak pohon pencarian yang bisa dimuat dan performanya akan meningkat; tetapi itu tidak terlihat terlalu menarik

    • Saya tidak tahu bagaimana mungkin mengenkode pohon pencarian dengan cara seperti ini

  • Repositori ini menyediakan implementasi makalah kami Grandmaster-Level Chess Without Search: https://arxiv.org/abs/2402.04494
    Terobosan terbaru dalam machine learning terutama berasal dari skala, yaitu arsitektur berbasis attention berskala besar dan dataset dengan skala yang belum pernah ada sebelumnya. Makalah ini meneliti dampak pembelajaran berskala besar pada catur
    Berbeda dari engine catur tradisional yang mengandalkan heuristik kompleks, pencarian eksplisit, atau kombinasi keduanya, kami melatih secara supervised sebuah model Transformer 270 juta parameter dengan dataset 10 juta permainan catur
    Setiap papan dalam dataset diberi anotasi nilai aksi yang disediakan oleh engine Stockfish 16 yang kuat, sehingga menghasilkan sekitar 15 miliar data point
    Model terbesar mencapai Elo blitz Lichess 2895 melawan manusia, dan memecahkan puzzle catur yang sulit tanpa penyetelan khusus domain maupun algoritma pencarian eksplisit
    Selain itu, model ini melampaui jaringan policy dan value AlphaZero tanpa MCTS serta GPT-3.5-turbo-instruct. Hasil investigasi sistematis terhadap ukuran model dan dataset menunjukkan bahwa performa catur yang kuat hanya muncul pada skala yang memadai. Kami juga melakukan eksperimen ablasi ekstensif atas pilihan desain dan hyperparameter

    • Namun Elo blitz Lichess melawan bot sekitar 700 poin lebih rendah daripada melawan manusia

  • Akan menyenangkan jika ada engine yang berpikir lebih seperti manusia. Karena pendekatan ini memakai notasi permainan beranotasi Stockfish, pada dasarnya sepertinya ia akan berpikir seperti komputer
    Jika ia berpikir seperti manusia, dalam review permainan ia akan sangat berguna untuk menunjukkan, sesuai Elo saya, apa yang perlu diperhatikan di setiap posisi

    • Atau model yang mengukur performa sebagai efisiensi belajar juga akan bagus. Dengan kata lain, melihat berapa banyak permainan yang harus dimainkan untuk mencapai level X
      Alasan Magnus Carlsen luar biasa adalah karena, dibandingkan komputer, ia mencapai kemampuan catur saat ini di bawah batasan waktu dan komputasi yang sangat besar. Efisiensi belajarnya luar biasa dibandingkan engine catur mana pun
    • Sebaliknya, ada juga ujung spektrum yang lain. Ketika memori, ukuran program, dan waktu komputasi sangat dibatasi: https://rlc-chess.com/
      Rasanya seperti program demoscene. Bahkan ada program catur 1KB yang benar-benar berjalan

  • Jika catur dipecahkan sepenuhnya, akan muncul pohon yang terlalu besar untuk dihitung saat ini. Seingat saya kira-kira 10^80, tetapi bisa saja saya salah
    Jika pohon itu diberi anotasi menang/kalah/seri, pemain optimal dapat dibuat tanpa pencarian
    Dua pendekatan yang jelas untuk kompresi dan optimisasi adalah mengaproksimasi pohonnya, atau mengaproksimasi anotasinya. Seberapa baik kedua metode ini bekerja sangat bergantung pada struktur pohon
    Hasil ini tampaknya lebih banyak menunjukkan seberapa cocok pohon permainan catur untuk kedua pendekatan tersebut, daripada kekuatan absolut pendekatan pembelajaran itu sendiri. Kesimpulan yang saya dapat adalah bahwa aproksimasi yang masuk akal atas pohon tersebut dimungkinkan dengan data berukuran 270 juta kata