Pencarian Graf Monte Carlo yang Berangkat dari Prinsip Dasar

• Monte-Carlo Graph Search (MCGS) adalah pendekatan yang menerapkan MCTS pada graf berarah alih-alih pohon untuk berbagi eksplorasi yang duplikat dalam game di mana banyak urutan langkah berpindah ke keadaan yang sama
• Jika jumlah kunjungan N dan nilai rata-rata Q dari MCTS lama dipindahkan begitu saja ke DAG, jumlah kunjungan anak yang dibagi dapat tidak selaras dengan estimasi kebijakan dan nilai induk sehingga algoritme bisa menjadi tidak sehat
• Jika MCTS dipandang sebagai optimisasi kebijakan yang diregularisasi, distribusi kunjungan per aksi yang dibentuk PUCT dapat ditafsirkan sebagai kebijakan posterior, dan Q sebagai utilitas ekspektasian dari kebijakan itu
• MCGS yang benar melacak jumlah kunjungan edge N(n,a) secara terpisah dari jumlah kunjungan node anak, lalu menghitung ulang Q sebagai jumlah berbobot dari U(n) dan Q anak agar makna kebijakan dan nilai tetap terjaga juga di graf
• Dalam implementasi nyata masih ada pilihan seperti stale Q, pembaruan inkremental, apakah playout dilanjutkan dari anak hasil transposisi, serta penanganan tabrakan hash dan siklus dalam game, dan saat ini KataGo memakai pembaruan idempoten

---

Keadaan transposisi yang terlewat oleh pencarian pohon

• Dalam pencarian pohon game, bisa terjadi transposisi ketika urutan langkah yang berbeda mencapai keadaan yang sama
  • Dalam catur, 1. d4 d5 2. Nf3 dan 1. Nf3 d5 2. d4 mencapai posisi yang sama
• Pada game yang memungkinkan transposisi, semakin dalam eksplorasi, semakin banyak keadaan duplikat yang dapat bertambah secara eksponensial, sehingga lebih diinginkan untuk berbagi perhitungan atas keadaan yang sama
• Implementasi MCTS umum memperlakukan game sebagai pohon percabangan sehingga beberapa instans dari posisi yang sama dieksplorasi ulang
  • Optimasi tingkat rendah seperti cache evaluasi jaringan saraf untuk posisi berulang dapat mengurangi biaya
  • Namun, masalahnya tetap ada: meskipun taktik penting ditemukan pada satu instans dan evaluasinya diperbaiki, hal itu tidak menyebar ke instans lain
• Jika ruang keadaan dimodelkan sebagai directed acyclic graph (DAG), satu keadaan dapat direpresentasikan sebagai satu node ketika banyak jalur mencapai keadaan yang sama
• Penjelasan ini sebagian besar mengecualikan penanganan game yang benar-benar memiliki siklus, dan berfokus pada bagaimana MCTS seharusnya bekerja di DAG

MCTS standar: pohon yang menumpuk statistik eksekusi

• MCTS standar menyimpan sebagian game yang telah dieksplorasi sebagai pohon node di memori
• Tiap node biasanya melacak nilai berikut
  • N: jumlah playout yang sejauh ini melewati node ini atau berakhir di node ini
  • Q: rata-rata berjalan dari nilai utilitas yang disampel oleh playout tersebut
• Satu playout berjalan dengan urutan berikut
  • Mulai dari root, turun sambil memilih aksi berikutnya menurut rumus eksplorasi
  • Saat mencapai keadaan yang belum dieksplorasi, tambahkan node baru
  • Dapatkan utilitas U dari keadaan baru itu. Contohnya adalah kueri ke value head jaringan saraf
  • Naik kembali melalui pohon sambil menaikkan N tiap node dan memperbarui rata-rata Q
• Dalam MCTS bergaya AlphaZero, pemilihan aksi memakai rumus PUCT
  • N(a): jumlah kali aksi a dicoba, dan dalam pohon ini sama dengan N dari node anak yang dituju aksi tersebut
  • Q(a): utilitas rata-rata dari aksi a, dan ini sama dengan Q dari node anak
  • PlayerToMove: mencerminkan apakah pemain saat ini memaksimalkan atau meminimalkan
  • P(a): probabilitas prior seperti prediksi kebijakan jaringan saraf
  • c_PUCT: konstanta yang dapat disetel
• “PUCT” berasal dari keluarga Predictor UCT/UCB yang memakai distribusi prior prediktif, dan varian AlphaZero berbeda dari bentuk aslinya dalam bentuk fungsi
• MCTS modern bisa bersifat deterministik bila memakai evaluasi jaringan saraf, tetapi istilah “Monte-Carlo” berasal dari pendekatan lama yang menjalankan rollout acak sampai akhir untuk mengestimasi utilitas
• Setelah playout diulang sampai anggaran komputasi untuk giliran itu habis, aksi akhir dipilih dari root bukan berdasarkan Q, tetapi anak dengan jumlah kunjungan N terbesar
  • Anak dengan Q tinggi dan N rendah bisa saja hanya kesalahan yang tampak tinggi karena noise pada eksplorasi dangkal
• Distribusi kunjungan di root N(a) / ΣN(b) dapat dipakai sebagai target pembelajaran kebijakan dalam loop pelatihan AlphaZero

Masalah yang muncul bila diterapkan ke DAG secara naif

• Kita bisa hampir menyalin kode MCTS pohon apa adanya, lalu jika keadaan game baru sudah ada di nodes_by_hash, cukup arahkan ke node yang sudah ada
• Pendekatan ini gagal mempertahankan asumsi pohon bahwa jumlah kunjungan node anak sama dengan jumlah kunjungan aksi yang dipilih dari induknya
• Contoh situasi
  • Node A lebih menyukai aksi menuju node C, dan Q milik A sebagian besar ditentukan oleh sekitar 30 playout yang mengeksplorasi C
  • C juga dikunjungi sekitar 40 kali melalui jalur transposisi lain
  • Setelah itu, C lebih sering dikunjungi dari jalur transposisi lain dan taktik di kedalaman lebih jauh ditemukan sehingga estimasi utilitas C naik dari 0.39 → 0.51
• Karena playout yang memperbarui C tidak melewati A, Q milik A tidak mencerminkan evaluasi baru dari C
• Bahkan jika A nanti menerima playout lagi, PUCT bisa memilih mengeksplorasi aksi lain yang kunjungannya rendah alih-alih C yang kunjungannya tinggi
  • Ini karena C terlihat “sudah cukup dieksplorasi”
  • Akibatnya Q milik A justru bisa turun
• Perluasan graf yang naif dapat membuat induk lebih banyak mengeksplorasi langkah lain ketika jalur transposisi banyak mengunjungi langkah yang sebenarnya lebih disukai di atas, sehingga menghasilkan bias buatan dalam rata-rata playout
• Algoritme ini menjadi tidak sehat, sampai tidak jelas apakah ia akan konvergen ke langkah optimal bahkan dengan eksplorasi tak hingga

Memperbarui semua induk juga tidak menyelesaikan masalah

• Ketika sebuah node diperbarui oleh suatu playout, kita juga bisa membayangkan cara yang memantulkan hasilnya bukan hanya ke induk yang benar-benar dilalui playout itu, tetapi ke semua induk dan leluhur
• Dalam kasus A-C sebelumnya, pendekatan ini memang bisa memperbarui utilitas A juga
• Tetapi pada contoh lain, induk D tercemar oleh banyaknya kunjungan pada anak transposisi F yang sebenarnya tidak disukai D
  • Anak terbaik D adalah E dengan Q = 0.56, dan Q = 0.55 milik D konsisten dengan itu
  • D sendiri hanya mengeksplorasi F satu kali, tetapi F sudah dikunjungi 9 kali dari jalur lain sehingga totalnya 10 kunjungan
  • Setelah itu F dikunjungi 100 kali lagi dari jalur lain dan tetap mempertahankan utilitas rendah, pendekatan pembaruan semua induk bisa menarik Q milik D turun hingga 0.35
• Dari sudut pandang D, ia tidak ingin mengalokasikan sebanyak itu playout ke F, jadi pembaruan semua induk juga merusak makna kebijakan

Memandang MCTS sebagai optimisasi kebijakan

• Monte-Carlo Tree Search as Regularized Policy Optimization menafsirkan MCTS dari sudut pandang machine learning
• Di setiap node, distribusi kunjungan kumulatif yang dibentuk PUCT melalui pemilihan berulang mendekati dan konvergen ke solusi dari masalah optimisasi berikut

nilai yang dimaksimalkan π:
Σ π(a) Q(a) - λ_N D_KL(P || π)

• Makna komponennya
  • Σ π(a) Q(a): utilitas ekspektasian terestimasi saat mengikuti kebijakan π
  • D_KL(P || π): divergensi KL terbalik yang mengukur perbedaan antara kebijakan prior P dan kebijakan posterior π
  • λ_N: koefisien yang menentukan kekuatan suku KL, dan nilainya menurun seiring bertambahnya jumlah kunjungan
• Distribusi kunjungan dapat dipandang sebagai kebijakan posterior yang berangkat dari kebijakan prior P milik jaringan saraf, lalu membaik seiring lebih banyak bukti utilitas aksi terkumpul lewat kunjungan tambahan
• Karena itu, MCTS dapat ditafsirkan sebagai algoritme yang sekaligus menjalankan pembelajaran kebijakan online kecil di setiap node pohon
• Sudut pandang ini menjelaskan mengapa distribusi kunjungan tampak seperti kebijakan agen yang kuat, dan mengapa ia dipakai sebagai target pembelajaran kebijakan di AlphaZero
• Secara teori, kita juga bisa menghitung solusi tepat dari masalah optimisasi itu lalu memakainya langsung sebagai kebijakan, tetapi dalam praktik langkah yang kunjungannya sedikit namun kebetulan Q-nya tampak tinggi bisa diberi bobot terlalu besar
  • Jika distribusi kunjungan dipakai sebagai kebijakan posterior, sebuah langkah harus benar-benar banyak dieksplorasi untuk mendapat bobot tinggi, sehingga lebih tangguh

Reinterpretasi Q: dari rata-rata playout ke nilai harapan kebijakan

• Dalam definisi standar, Q(n) dari node n adalah rata-rata utilitas playout yang mengunjungi n

Q(n) = (1 / N(n)) Σ U(p)

• Jika ditulis ulang berdasarkan anak, hasilnya menjadi sebagai berikut

Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )

• Di sini, U(n) adalah estimasi utilitas mentah dari jaringan saraf untuk node n itu sendiri, dan N(c) Q(c) adalah nilai anak yang dibobot dengan jumlah kunjungan masing-masing anak
• Karena itu, Q dapat ditafsirkan sebagai rata-rata berbobot distribusi kunjungan dari Q anak-anak
• Jika distribusi kunjungan adalah kebijakan posterior yang dioptimalkan MCTS, maka Q(n) adalah utilitas ekspektasian yang diregularisasi saat mengikuti kebijakan posterior tersebut
• Dalam interpretasi ini, tiap node terus mengoptimalkan kebijakannya agar memaksimalkan Q yang dilaporkan anak-anaknya, lalu memperbarui Q miliknya sendiri sebagai estimasi terkini atas utilitas ekspektasian yang dapat dicapai dengan kebijakan itu
• Jika Q dari node anak konvergen ke nilai optimal game-theoretic, maka kebijakan dan Q milik induk juga secara rekursif konvergen ke nilai optimal

MCGS yang benar: memisahkan kunjungan edge dan kunjungan anak

• Masalah di graf muncul karena diasumsikan bahwa kunjungan anak dari suatu induk hanya terjadi melalui induk itu
• Jika ada jalur transposisi, jumlah kunjungan node anak dapat berbeda secara arbitrer dari jumlah kunjungan yang sebenarnya ingin dialokasikan PUCT dari induk tersebut
• Solusinya adalah melacak secara terpisah jumlah kumulatif pemilihan aksi oleh PUCT di node tertentu
• Tiap node n melacak nilai berikut
  • N(n): total jumlah kunjungan ke node ini
  • N(n,a): jumlah kali PUCT memilih aksi a dari node n, yaitu jumlah kunjungan edge
  • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
• Di sini Q(n,a) sama dengan Q(c) dari node anak c yang dicapai dengan memainkan aksi a
• Dalam perhitungan PUCT, yang dipakai juga jumlah kunjungan edge, bukan jumlah kunjungan anak

argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))

• Algoritme dasarnya memilih aksi pada jalur playout, menghubungkan ke keadaan transposisi yang sudah ada bila ditemukan, lalu saat kembali menaikkan jumlah kunjungan edge dan menghitung ulang N serta Q sebagai fungsi dari nilai anak
• Pendekatan ini serupa pada tingkat tinggi dengan Monte-Carlo Graph Search for AlphaZero karya Czech, Korus, dan Kersting, tetapi diturunkan dari sudut pandang optimisasi kebijakan alih-alih statistik eksekusi

Pilihan implementasi: stale Q dan cara pembaruan

• Pseudocode yang diajukan hanya memperbarui node pada jalur yang benar-benar dilalui playout
• Karena itu, Q pada node di jalur yang tidak dilalui dapat menjadi stale Q
• Meski demikian, secara teori pendekatan ini tetap sehat
  • Rumus eksplorasi standar seperti PUCT pada batasnya akan mencoba semua aksi tanpa batas
  • Saat sebuah node dikunjungi lagi, Q yang benar dapat dihitung langsung memakai Q anak dan jumlah kunjungan edge pada saat itu
  • Di DAG, pendekatan ini pada akhirnya dapat konvergen ke nilai optimal game-theoretic
• Stale Q dapat menurunkan efisiensi pencarian
  • Kita bisa menyimpan pointer induk agar Q induk juga segera diperbarui
  • Semua leluhur bisa diperbarui dalam urutan topological sort untuk menghilangkan keadaan stale
  • Bisa juga hanya memperbarui jalur playout sambil menjalankan thread paralel terpisah yang mencari dan memperbarui node stale
• Pseudocode tersebut memakai pembaruan idempoten
  • Terlepas dari pembaruan antara apa pun yang mungkin telah terjadi sebelumnya, sekali node dikunjungi, N dan Q-nya akan cocok dengan nilai terkini dari anak-anaknya
• Pembaruan inkremental juga memungkinkan, tetapi di graf lebih sulit untuk membuatnya setara atau setara pada batasnya
• Czech dkk. memakai rumus yang lebih inkremental karena mereka mendekatinya dari sudut pandang statistik eksekusi
  • Mereka menyimpan bukan hanya jumlah kunjungan edge, tetapi juga Q pada edge
  • Mereka juga menambahkan mekanisme agar stale Q secara bertahap mengejar nilai terbaru, beserta hyperparameter toleransi galat
• Pseudocode yang diajukan menunjukkan bahwa MCGS dapat bekerja tanpa parameter toleransi galat baru maupun penyimpanan Q pada edge
• Saat ini KataGo memakai rumus idempoten

Apakah playout dilanjutkan dari anak hasil transposisi

• Dalam MCTS pohon, kenaikan kunjungan edge dan kenaikan kunjungan anak adalah kejadian yang sama
• Dalam graf, karena transposisi, node anak bisa saja sudah jauh lebih sering dikunjungi daripada edge tersebut
• Dalam situasi ini, kita bisa menganggap node anak sudah cukup dikunjungi, menghentikan playout, hanya menaikkan kunjungan edge, lalu memperbarui induk dan leluhur
• Alasan memilih berhenti
  • Jika kunjungan edge rendah tetapi kunjungan anak tinggi, informasi marjinal dari menambah kunjungan lagi ke anak itu mungkin kecil
• Alasan memilih lanjut
  • Node yang kunjungan anaknya lebih besar daripada kunjungan edge kemungkinan adalah node yang dituju banyak induk lewat transposisi, sehingga evaluasinya penting karena memengaruhi lebih banyak induk
• Pilihan ini masih menjadi area eksperimen
  • Pendekatan berbasis ambang juga dimungkinkan, misalnya hanya berhenti jika jumlah kunjungan anak cukup jauh lebih besar daripada jumlah kunjungan edge
• KataGo secara default menghentikan playout, tetapi menyediakan opsi konfigurasi untuk melanjutkan, atau hanya menghentikan sebagian secara probabilistik
• Pseudocode tidak menghentikan playout, dan bila perlu pemeriksaan satu baris child.N <= edge_visits dapat ditambahkan

Hash, node terminal, dan siklus game yang nyata

• Node terminal game dalam pseudocode dihitung ulang sebagai N = 1, U = Q = utilitas hasil game tanpa memandang jumlah kunjungan
  • Jumlah kunjungan edge pada induknya tetap dinaikkan secara normal, sehingga pendekatan ini juga memungkinkan
  • Jika hasil game bersifat stokastik dan utilitas ekspektasian tidak bisa dihitung langsung, maka mungkin penting untuk menaikkan N pada setiap kunjungan ke node terminal dan merata-ratakan hasil sampelnya
• Utilitas terminal game juga bisa ditangani lebih luas agar nilai yang dapat dibuktikan menyebar lebih cepat ke atas graf
  • MCTS/MCGS umum tidak punya mekanisme untuk mengenali nilai utilitas yang pasti, sehingga ketika keadaan terminal penting, ia tidak dapat konvergen ke nilai optimal semurah pencarian klasik seperti alpha-beta
• Untuk menemukan transposisi diasumsikan adanya hash unik untuk keadaan game
  • Membuat hash yang benar-benar bebas tabrakan untuk keadaan game yang kompleks bisa sulit dan mahal
  • Zobrist hash 128-bit atau 192-bit yang cukup besar biasanya sudah memadai dalam praktik untuk secara efektif mencegah tabrakan, selama keadaannya tidak dibuat secara adversarial
  • Untuk menghindari rekursi tak hingga saat tabrakan hash menciptakan siklus, deteksi siklus dapat ditambahkan
• Penanganan siklus yang muncul dari aturan game nyata, seperti superko di Go atau pengulangan tiga kali di catur, tidak dibahas secara rinci
• Lampiran 2024-03-10 menyediakan tautan Google Docs berisi gagasan yang lebih kasar tentang penanganan pengulangan dan siklus, dan mungkin diperlukan eksperimen heuristik per game
• Dalam penanganan Go di KataGo, dipakai teorema khusus Go bahwa untuk kembali ke posisi semula setelah langkah tertentu dibutuhkan setidaknya S + E - 1 langkah, sehingga pembagian node dapat dibatasi secara stabil dalam situasi terkait siklus

[GN⁺]

Pendapat di Hacker News

• Menurut saya pencarian graf seperti ini diperlukan untuk memajukan penalaran AI. LLM saja kemungkinan besar akan gagal
  Tautan tersebut memuat banyak referensi bagus, termasuk Zobrist hashing untuk tabel permainan https://en.wikipedia.org/wiki/Zobrist_hashing
  Agar beban komputasi pencarian graf tidak meledak, perlu ditemukan hashing yang baik untuk deskripsi keadaan berbasis bahasa
  Terkait pencarian pohon, Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 dan Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642, yang membandingkan pendekatan MCTS dengan strategi reinforcement learning lain saat ini, juga layak dibaca

  • Ini terlihat terlalu level rendah
    Satu langkah lebih maju bisa berupa pendekatan yang mempelajari representasi keadaan dan algoritma pencarian secara bersamaan. Algoritma pencarian menjelajah di atas representasi keadaan dari jaringan saraf yang dapat memberinya biaya
    https://sites.google.com/view/genie-2024/
    Genie dari DeepMind adalah contoh yang bagus untuk pemodelan keadaan diskret. Jaringan saraf mempelajari representasi yang sangat kompleks, termasuk deteksi tabrakan dan aksi. Alih-alih mendekode keadaan itu menjadi piksel, kemungkinan kita bisa mencari langsung di atas keadaan tersebut
    Tentu saja, dalam praktiknya struktur ini bisa cukup berbeda
  • Ini memang terlalu disederhanakan, tetapi menurut saya pendekatan yang layak dieksplorasi kira-kira seperti ini
    Ambil sekumpulan argumen logis, cari cara memberi hash pada tiap argumen, lalu representasikan hash argumen itu sebagai Merkle tree yang ditumpuk berdasarkan prinsip pertama
    Jika suatu argumen berhasil dibantah, hash argumen itu berubah, dan hash argumen-argumen turunannya juga menjadi tidak valid
  • Saya bertanya-tanya apakah keduanya tidak bisa digabungkan dengan cara tertentu. Sulit membayangkan otak hanya memakai satu teknik untuk segala hal; tampaknya lebih mungkin ada beberapa alat dan sebuah pemilih di atasnya yang menentukan alat mana dipakai kapan

• Dari penulis di URL HN, saya langsung mengenalinya sebagai orang jenius yang membuat KataGo: https://github.com/lightvector/KataGo
  Tulisan-tulisannya di https://www.reddit.com/r/cbaduk/ juga konsisten sangat bagus

  • URL-nya secara harfiah berada di dalam repositori KataGo

• Saya tidak punya pengalaman catur yang sangat banyak, tetapi saya skeptis terhadap klaim bahwa posisi yang sama cukup sering berulang di dalam pohon pencarian hingga menjadi penting. Saya ingin melihat pengukuran nyata dengan Leela Zero
  Jika tiga kali pengulangan dan aturan 50 langkah juga dimasukkan ke dalam keadaan, kemungkinan pengulangan akan jauh lebih rendah; bahkan tanpa mempertimbangkan bagian itu pun saya rasa demikian

  • Dalam Go, ko sangat umum. Mengulang posisi papan secara persis tidak boleh, tetapi jika pencarian pohon tidak bisa mengevaluasi posisi ko dengan benar, mudah membuat situasi di mana AI memainkan langkah buruk

• Aneh bahwa, meski bernama “Monte-Carlo Tree Search”, algoritma di atas sama sekali tidak memiliki unsur Monte Carlo dan sepenuhnya deterministik. Saya kira MCTS yang biasa diimplementasikan itu deterministik, dan sampling-nya mengandung keacakan

  • MCTS awalnya memang memiliki keacakan. Sepertinya artikel itu juga menyebutkannya: bentuknya melakukan playout untuk mengevaluasi posisi di akhir
    Dalam proyek-proyek serupa saat ini, hal itu digantikan oleh evaluasi jaringan saraf yang kualitasnya lebih baik. Cara memainkan langkah acak untuk melihat siapa yang menang tidak terlalu bagus, tetapi saat itu itulah strategi terbaik yang diketahui
    Pada akhirnya, bagian Monte Carlo bukanlah unsur esensial dari apa yang sekarang masih disebut MCTS, malah lebih merupakan pilihan yang kurang optimal. Jadi namanya agak kurang beruntung
  • Secara ketat, itu adalah algoritma lain di bawah nama “monte carlo” yang sama
    Hal menariknya, sebagian besar metode Monte Carlo bergantung pada pembangkit bilangan pseudorandom, bukan pembangkit bilangan acak sejati, sehingga jika seed dan input-nya sama, hasilnya selalu sama secara deterministik
    Alih-alih memakai pembangkit bilangan pseudorandom umum dan heuristik terpisah, algoritma ini melakukan kueri ke jaringan saraf. Jaringan saraf adalah heuristik di atas ruang pencarian yang sangat besar, sehingga bergantung pada pelatihannya ia bertindak seperti pembangkit bilangan pseudorandom yang sangat buruk dan sangat condong ke hasil tertentu, dan akhirnya tampak seperti pembangkit bilangan pseudorandom yang diberi heuristik
    Poin pentingnya, ini adalah spesialisasi dari MCTS, sehingga secara teknis tidak cocok untuk semua kasus penggunaan
  • Jika ada keacakan, saya penasaran apakah ia konvergen, dan berapa banyak sumber daya-waktu yang dibutuhkan. Itu juga bisa berbeda untuk CPU, RAM, GPU, TPU, dan QPU

• Saat meneliti MCTS, makalah yang disebut di artikel ini benar-benar luput dari radar saya. Pada kesempatan berikutnya, sepertinya akan cukup menarik untuk menjalankan sendiri metode modifikasi ini

• Akan bagus kalau ada pengantar singkat

  • Saat membuat AI untuk bermain gim—dan secara luas, bisa dibilang untuk semua AI—salah satu teknik yang paling menjanjikan adalah pencarian pohon. Caranya adalah memberi peringkat pada langkah saat ini berdasarkan langkah-langkah lanjutan
    Dalam gim di mana keadaan yang sama bisa dicapai lewat banyak jalur, banyak memori bisa terbuang karena node keadaan yang sama dicatat berulang di cabang yang berbeda
    Artikel ini membahas dengan baik pendekatan yang disebut pencarian graf. Pada dasarnya, pendekatan ini melakukan komputasi tambahan untuk melakukan hashing pada keadaan gim guna memeriksa apakah node tersebut sudah pernah dikunjungi, dan sebagai gantinya menghemat memori
    Karena node yang sudah pernah dilihat tidak perlu dicatat lagi, pohon tanpa siklus berubah menjadi graf berarah asiklik
    Karena itu, agar mendapatkan hasil yang benar, pencarian pohon perlu sedikit disesuaikan. Khususnya, unit optimisasi harus lebih diarahkan ke edge—yakni aksi atau langkah—bukan vertex, yakni keadaan
    Ini adalah esai teknis yang ditulis dengan baik dalam gaya literate programming, oleh seseorang yang benar-benar memahami topiknya