- Monte-Carlo Graph Search (MCGS), birden fazla hamle dizisinin aynı duruma geçtiği oyunlarda, MCTS’yi ağaç yerine yönlü bir grafiğe uygulayarak yinelenen aramayı paylaşmaya çalışan bir yaklaşımdır
- Mevcut MCTS’nin ziyaret sayısı N ve ortalama değer Q değerleri DAG’ye aynen taşınırsa, paylaşılan çocuğun ziyaret sayısı ebeveynin politika ve değer tahminiyle uyuşmayabilir ve algoritma sağlamlığını yitirebilir
- MCTS’ye düzenlileştirilmiş politika optimizasyonu olarak bakıldığında, PUCT’nin ürettiği eylem başına ziyaret dağılımı sonradan elde edilen politika, Q ise bu politikanın beklenen faydası olarak yorumlanır
- Doğru MCGS, çocuk düğüm ziyaret sayısından ayrı olarak kenar ziyaret sayısı N(n,a) değerini izler ve Q’yu
U(n) ile çocuk Q’larının ağırlıklı toplamı olarak yeniden hesaplayarak grafikte de politika ve değer anlamını korur
- Gerçek uygulamada stale Q, artımlı güncelleme, geçiş yapılan çocukta playout’a devam edilip edilmeyeceği, hash çakışmaları ve oyun içi döngülerin ele alınması gibi seçenekler kalır; KataGo şu anda idempotent güncelleme kullanır
Ağaç aramanın kaçırdığı geçiş durumları
- Oyun ağacı aramasında, farklı hamle dizilerinin aynı duruma geçiş (transposition) yaptığı durumlar olabilir
- Satrançta
1. d4 d5 2. Nf3 ile 1. Nf3 d5 2. d4 aynı pozisyona ulaşır
- Geçişlerin mümkün olduğu oyunlarda arama derinliği arttıkça yinelenen durumlar üstel olarak artabilir; bu nedenle aynı duruma ait hesaplamaları paylaşmak tercih edilir
- Yaygın MCTS uygulamaları oyunu dallanan bir ağaç olarak ele alır ve aynı pozisyonun birden fazla örneğini yeniden arar
- Tekrarlanan pozisyonlar için sinir ağı değerlendirmelerini cache’lemek gibi düşük seviyeli optimizasyonlar maliyeti azaltabilir
- Ancak bir örnekte önemli bir taktik keşfedilip değerlendirme düzeltilse bile bunun diğer örneklere yayılmaması sorunu devam eder
- Durum uzayı yönlü çevrimsiz grafik (DAG) olarak modellenirse, birden fazla yol aynı duruma ulaştığında o durum tek bir düğümle temsil edilebilir
- Gerçek döngüleri olan oyunların ele alınması çoğunlukla kapsam dışında bırakılır; odak, MCTS’nin DAG üzerinde nasıl çalışması gerektiğidir
Standart MCTS: Çalıştırma istatistikleri biriktiren ağaç
- Standart MCTS, oyunun aranan kısmını bellekte bir düğüm ağacı olarak saklar
- Her düğüm genellikle şu değerleri izler
N: Şimdiye kadar bu düğümden geçen veya bu düğümde biten playout sayısıQ: Bu playout’ların örneklediği fayda değerlerinin çalışan ortalaması
- Tek bir playout şu sırayla ilerler
- Kökten başlar ve keşif formülüne göre sonraki eylemi seçerek aşağı iner
- Henüz aranmamış bir duruma ulaştığında yeni bir düğüm ekler
- Yeni durumun faydası
U elde edilir. Örnekte bu, sinir ağının value head’ine yapılan sorgudur
- Ağaçta geriye doğru çıkarken her düğümün
N değeri artırılır ve Q ortalaması güncellenir
- AlphaZero tarzı MCTS’de eylem seçimi için PUCT formülü kullanılır
N(a): a eyleminin denenme sayısıdır; ağaçta bu, eylemin işaret ettiği çocuk düğümün N değeriyle aynıdırQ(a): a eyleminin ortalama faydasıdır; çocuk düğümün Q değeriyle aynıdırPlayerToMove: Sıradaki oyuncunun maksimize mi minimize mi ettiğini yansıtırP(a): Sinir ağı politika tahmini gibi ön olasılıkc_PUCT: Ayarlanabilir sabit
- “PUCT”, tahmine dayalı ön dağılım kullanan Predictor UCT/UCB ailesinden gelir; AlphaZero varyantı özgün biçimden ve fonksiyon şeklinden farklıdır
- Modern MCTS, sinir ağı değerlendirmesi kullanıldığında deterministik olabilir; ancak adındaki “Monte Carlo”, geçmişte faydayı tahmin etmek için rastgele rollout’ların sona kadar yürütüldüğü yöntemden gelir
- Turun hesaplama bütçesi bitene kadar playout tekrarlanır; ardından kökte son eylem olarak
Q değil, ziyaret sayısı N en büyük olan çocuk seçilir
- Yüksek
Q ve düşük N değerine sahip bir çocuk, sığ aramada gürültü nedeniyle yüksek görünmüş bir hata olabilir
- Kökteki ziyaret dağılımı
N(a) / ΣN(b), AlphaZero eğitim döngüsünde politika öğrenme hedefi olarak kullanılabilir
DAG’ye safça uygulandığında ortaya çıkan sorun
- Ağaç MCTS kodu neredeyse aynen bırakılıp, yeni oyun durumu zaten
nodes_by_hash içinde varsa mevcut düğüme işaret edecek şekilde düzenlenebilir
- Bu yöntem, çocuk düğüm ziyaret sayısının ebeveynde seçilen eylem ziyaret sayısıyla aynı olduğu yönündeki ağaç varsayımını koruyamaz
- Örnek durum
- A düğümü C düğümüne giden eylemi tercih eder ve A’nın
Q değeri çoğunlukla C’yi arayan yaklaşık 30 playout tarafından belirlenmiştir
- C başka geçiş yollarından da yaklaşık 40 kez ziyaret edilmiştir
- Daha sonra C başka geçiş yollarından daha fazla ziyaret edilir, derinlerde bir taktik keşfedilir ve C’nin fayda tahmini
0.39 → 0.51 yükselir
- C’yi güncelleyen playout A’dan geçmediği için, A’nın
Q değeri C’nin yeni değerlendirmesini yansıtmaz
- Daha sonra A yeniden playout alsa bile PUCT, ziyaret sayısı yüksek olan C yerine ziyaret sayısı düşük olan başka eylemleri keşfedebilir
- Çünkü C “zaten yeterince aranmış” gibi görünür
- Sonuçta A’nın
Q değeri tersine düşebilir
- Saf grafik genişletmesi, geçiş yolları üstte tercih edilen hamleyi daha çok ziyaret ettikçe ebeveynin başka hamleleri daha fazla aramasına yol açar ve playout ortalamasında yapay bir yanlılık oluşturabilir
- Sonsuz aramada bile en iyi hamleye yakınsayıp yakınsamayacağı belirsiz olacak kadar sağlam olmayan bir algoritma hâline gelir
Tüm ebeveynleri güncellemek de çözmez
- Bir düğüm bir playout ile güncellendiğinde, bu playout’un gerçekten geçtiği ebeveynlerin yanı sıra tüm ebeveynlere ve atalara da yansıtılması düşünülebilir
- Bu yöntem, önceki A-C örneğinde A’nın faydasını da birlikte güncelleyebilir
- Ancak başka bir örnekte ebeveyn D, kendisinin tercih etmediği geçiş çocuğu F’nin çok sayıda ziyareti yüzünden kirlenir
- D’nin en iyi çocuğu E için
Q = 0.56 ve D’nin Q = 0.55 değeri bununla uyumludur
- D, F’yi yalnızca bir kez aramıştır, fakat F başka yollardan zaten 9 kez ziyaret edilerek toplam 10 ziyaretlik duruma gelmiştir
- Daha sonra F başka yollardan 100 kez daha ziyaret edilip düşük faydayı korursa, tüm ebeveynleri güncelleme yöntemi D’nin
Q değerini 0.35 seviyesine kadar çekebilir
- D açısından F’ye bu kadar çok playout ayırmak istenmediğinden, tüm ebeveynleri güncellemek de politika anlamını bozan bir yöntemdir
MCTS’ye politika optimizasyonu olarak bakmak
π’nin maksimize ettiği değer:
Σ π(a) Q(a) - λ_N D_KL(P || π)
- Bileşenlerin anlamı
Σ π(a) Q(a): π politikasını izlerken tahmini beklenen faydaD_KL(P || π): Ön politika P ile sonradan elde edilen politika π arasındaki farkı ölçen ters yönlü KL sapmasıλ_N: KL teriminin gücünü belirleyen katsayıdır ve ziyaret sayısı arttıkça azalır
- Ziyaret dağılımı, sinir ağının ön politikası
Pyi başlangıç noktası alıp, daha fazla ziyaretle eylem faydasına dair kanıt biriktikçe iyileşen sonradan elde edilen politika olarak görülebilir
- Dolayısıyla MCTS, ağacın her düğümünde küçük bir çevrimiçi politika öğrenmesini eşzamanlı yürüten bir algoritma olarak yorumlanır
- Bu bakış açısı, ziyaret dağılımının güçlü bir ajanın politikası gibi görünmesini ve AlphaZero’da politika öğrenme hedefi olarak kullanılma nedenini açıklar
- Optimizasyon probleminin tam çözümünü hesaplayıp politika olarak kullanmak da mümkündür; fakat pratikte az ziyaret edilmiş ve tesadüfen
Q değeri yüksek görünen hamlelere büyük ağırlık verebilir
- Ziyaret dağılımı sonradan elde edilen politika olarak kullanıldığında, bir hamlenin yüksek ağırlık alması için gerçekten çok aranmış olması gerekir; bu nedenle daha sağlamdır
Q’nun yeniden yorumlanması: playout ortalamasından politika beklentisine
- Standart tanımda
n düğümünün Q(n) değeri, nyi ziyaret eden playout’ların fayda ortalamasıdır
Q(n) = (1 / N(n)) Σ U(p)
- Bu, çocuklar temelinde yeniden yazılırsa şöyledir
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
- Burada
U(n), n düğümünün ham sinir ağı fayda tahminidir; N(c) Q(c) ise çocuk başına ziyaret sayısıyla ağırlıklandırılmış çocuk değeridir
- Dolayısıyla
Q, çocuk Q’larının ziyaret dağılımıyla ağırlıklandırılmış ortalaması olarak yorumlanabilir
- Ziyaret dağılımı MCTS’nin optimize ettiği sonradan elde edilen politikaysa,
Q(n) bu sonradan elde edilen politikayı izlerken düzenlileştirilmiş beklenen faydadır
- Bu yorumda her düğüm, çocuklarının bildirdiği
Q değerlerini maksimize edecek şekilde politikasını sürekli optimize eder ve kendi Q değerini bu politikayla ulaşılabilecek beklenen faydanın güncel tahmini olarak günceller
- Çocuk düğümün
Q değeri oyun kuramsal optimum değere yakınsarsa, ebeveynin politikası ve Q değeri de özyinelemeli olarak optimum değere yakınsar
Doğru MCGS: Kenar ziyareti ile çocuk ziyaretini ayırmak
- Grafikte ortaya çıkan sorun, ebeveynin çocuk ziyaretlerinin yalnızca o ebeveyn üzerinden gerçekleştiğinin varsayılmasından kaynaklanır
- Geçiş yolları varsa çocuk düğüm ziyaret sayısı, PUCT’nin ilgili ebeveynde ayırmak istediği ziyaret sayısından keyfî biçimde farklılaşabilir
- Çözüm, PUCT’nin belirli bir düğümde seçtiği eylemin kümülatif sayısını ayrı izlemektir
- Her
n düğümü şu değerleri izler
N(n): Bu düğümün toplam ziyaret sayısıN(n,a): n düğümünde PUCT’nin a eylemini seçme sayısı, yani kenar ziyaret sayısıQ(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
- Burada
Q(n,a), a eylemi oynanarak ulaşılan çocuk düğüm cnin Q(c) değeriyle aynıdır
- PUCT hesabında da çocuk ziyaret sayısı değil, kenar ziyaret sayısı kullanılır
argmax_a PlayerToMove(n) * Q(n,a)
+ c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
- Temel algoritma, playout yolundaki eylemleri seçer; geçiş yapılan durum zaten varsa mevcut düğümü bağlar; geri dönerken kenar ziyaret sayısını artırır ve ardından
N ile Q değerlerini çocuk değerlerinin fonksiyonu olarak yeniden hesaplar
- Bu yöntem, Czech, Korus ve Kersting’in Monte-Carlo Graph Search for AlphaZero çalışmasına üst düzeyde benzerdir; ancak çalıştırma istatistikleri yerine politika optimizasyonu bakış açısından türetilmiştir
Uygulama seçenekleri: stale Q ve güncelleme yöntemi
- Sunulan sözde kod yalnızca playout’un gerçekten geçtiği yoldaki düğümleri günceller
- Bu nedenle geçilmeyen yollardaki düğümlerin
Q değerleri stale Q hâline gelebilir
- Yine de teorik olarak sağlamdır
- PUCT gibi standart keşif formülleri limitte tüm eylemleri sonsuz kez dener
- Düğüm yeniden ziyaret edildiğinde, o andaki çocuk
Q değerleri ve kenar ziyaret sayıları kullanılarak doğru Q doğrudan hesaplanır
- DAG’de, limitte oyun kuramsal optimum değere yakınsayabilir
- stale Q arama verimliliğini düşürebilir
- Doğrudan ebeveyn işaretçileri tutulup ebeveyn Q’ları da güncellenebilir
- Tüm atalar topolojik sıralama düzeninde güncellenerek stale durumlar ortadan kaldırılabilir
- Yalnızca playout yolunu güncellerken, ayrı bir paralel thread’in stale düğümleri bulup güncellemesi sağlanabilir
- Sözde kod idempotent güncelleme kullanır
- Daha önce hangi ara güncellemeler yapılmış olursa olsun, bir düğüm bir kez ziyaret edildiğinde çocukların mevcut değerlerine göre
N ve Q doğru hâle gelir
- Artımlı güncelleme de mümkündür; fakat grafikte bunu eşdeğer veya limitte eşdeğer yapmak daha zordur
- Czech ve diğerleri çalıştırma istatistikleri perspektifinden yaklaştıkları için daha artımlı bir formül kullanır
- Kenar ziyaret sayısının yanı sıra kenarın Q değeri de saklanır
- stale Q’nun güncel değeri kademeli olarak yakalamasını sağlayan bir mekanizma ve hata toleransı hiperparametresi bulunur
- Sunulan sözde kod, yeni bir hata toleransı parametresi veya kenar Q saklama olmadan da MCGS’nin çalıştırılabileceğini gösterir
- KataGo şu anda idempotent formül kullanır
Geçiş yapılan çocukta playout’a devam edilip edilmeyeceği
- Ağaç MCTS’de kenar ziyaret artışı ile çocuk ziyaret artışı aynı olaydır
- Grafikte geçiş nedeniyle çocuk düğüm ilgili kenardan zaten daha fazla ziyaret edilmiş olabilir
- Bu durumda çocuk düğümün zaten yeterince ziyaret edildiği varsayılarak playout durdurulabilir; yalnızca kenar ziyareti artırılıp ebeveynler ve atalar güncellenebilir
- Durdurmayı tercih etme nedeni
- Kenar ziyareti düşük, çocuk ziyareti yüksekse, ilgili çocuğa ek ziyaret vermenin marjinal bilgi miktarı düşük olabilir
- Devam etmeyi tercih etme nedeni
- Çocuk ziyareti kenar ziyaretinden yüksek olan düğümlerin, birçok ebeveynin geçiş yaptığı düğümler olma olasılığı yüksektir; daha fazla ebeveyni etkiledikleri için doğru değerlendirme önemli olabilir
- Bu seçim deneysel bir alan olarak kalır
- Yalnızca çocuk ziyaret sayısı kenar ziyaret sayısından yeterince büyük olduğunda durduran eşik tabanlı bir yöntem de mümkündür
- KataGo varsayılan olarak playout’u durdurur; ancak devam etme veya olasılıksal olarak yalnızca bir kısmını durdurma yapılandırma seçenekleri sunar
- Sözde kod playout’u durdurmaz; gerekirse
child.N <= edge_visits koşuluyla tek satırlık bir kontrol eklenebilir
Hash, terminal düğümler ve gerçek oyun döngüleri
- Oyun sonu düğümleri sözde kodda ziyaret sayısından bağımsız olarak
N = 1, U = Q = oyun sonucu faydası şeklinde yeniden hesaplanır
- Ebeveynin ilgili kenar ziyaret sayısı normal şekilde arttığından bu yöntem de mümkündür
- Oyun sonucu olasılıksalsa ve beklenen fayda doğrudan hesaplanamıyorsa, her terminal düğüm ziyaretinde
N değerini artırıp örneklenen sonucu ortalamak önemli olabilir
- Oyun sonu faydasını daha geniş biçimde ele alarak kanıtlanabilir değerleri grafikte yukarı daha hızlı yaymak da mümkündür
- Sıradan MCTS/MCGS kesin fayda değerlerini tanıyacak bir mekanizmaya sahip olmadığından, terminal durumlar önemli olduğunda optimum değere alpha-beta gibi klasik arama kadar düşük maliyetle yakınsamaz
- Geçişleri bulmak için oyun durumunun benzersiz hash değerine sahip olduğu varsayılır
- Karmaşık oyun durumları için gerçekten çakışmasız hash üretmek zor ve maliyetli olabilir
- 128 bit veya 192 bit büyüklüğünde yeterince büyük bir Zobrist hash, düşmanca hazırlanmış durumlar olmadığı sürece pratikte çakışmaları fiilen engellemek için genellikle yeterlidir
- Hash çakışması nedeniyle döngü oluştuğunda sonsuz özyinelemeden kaçınmak için döngü tespiti eklenebilir
- Go’daki superko, satrançtaki üç kez tekrar gibi gerçek oyun kurallarından kaynaklanan döngüler ayrıntılı olarak ele alınmaz
- 2024-03-10 tarihli ek, tekrarlar ve döngü ele alma hakkında daha kaba düşünceler içeren bir Google Docs bağlantısı sunar; oyuna özgü sezgisel yöntemlerle deney gerekebilir
- KataGo’nun Go ele alışında, belirli bir hamleden sonra özgün pozisyona geri dönmek için en az
S + E - 1 hamle gerektiğini söyleyen Go’ya özgü bir teoremden yararlanılarak, döngüyle ilgili durumlarda düğüm paylaşımı kararlı şekilde sınırlandırılır
1 yorum
Hacker News görüşleri
Bu tür graf aramasının yapay zeka muhakemesini geliştirmek için gerekli olduğunu düşünüyorum. Yalnızca basit LLM’lerle başarıya ulaşmak zor görünüyor
Bağlantıda oyun tahtaları için Zobrist hashing de dahil olmak üzere çok sayıda iyi kaynak var: https://en.wikipedia.org/wiki/Zobrist_hashing
Grafik aramasının hesaplama maliyetinin patlamaması için, dil tabanlı durum açıklamalarına uygun iyi bir hashing yöntemi bulmak gerekiyor
Ağaç aramasıyla ilgili olarak Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 ve MCTS yaklaşımını güncel diğer pekiştirmeli öğrenme stratejileriyle karşılaştıran Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 da okunmaya değer
Bir adım ileri gitmenin yolu, durum gösterimi ile arama algoritmasını birlikte öğrenmek olabilir. Yani arama algoritmasının, üzerinde maliyet elde edebildiği bir sinir ağının durum gösterimi üzerinde arama yapması gibi
https://sites.google.com/view/genie-2024/
DeepMind’in Genie’si, ayrık durumların modellenmesine iyi bir örnek. Sinir ağı çarpışma tespiti ve eylemler dahil çok karmaşık temsilleri öğreniyor. Bu durumları piksellere decode etmek yerine, muhtemelen doğrudan bu durumların üzerinde arama yapılabilir
Elbette bu yapı pratikte oldukça farklı olabilir
Mantıksal argümanlardan oluşan bir küme alıp her argümana bir hash atamanın yolunu bulmak ve bu argüman hash’lerini ilk ilkeler temelinde iç içe geçmiş bir Merkle ağacı olarak temsil etmek
Herhangi bir argüman başarıyla çürütülürse, o argümanın hash’i değişir ve alt argümanların hash’leri de geçersiz hale gelir
HN URL’sindeki yazara bakıp bunun KataGo’yu yapan dahi olduğunu hemen anladım: https://github.com/lightvector/KataGo
https://www.reddit.com/r/cbaduk/ üzerine yazdıkları da sürekli çok kaliteli oluyor
Satranç deneyimim çok fazla değil ama arama ağacı içinde aynı pozisyonun önemli olacak kadar sık tekrarlandığı iddiasına şüpheyle yaklaşıyorum. Leela Zero ile gerçek ölçümleri görmek isterdim
Üçlü tekrar ve 50 hamle kuralını da duruma dahil ederseniz tekrar olasılığı çok daha düşer diye düşünüyorum; bunu hesaba katmasak bile öyle görünüyor
Adı “Monte-Carlo Tree Search” olmasına rağmen, yukarıdaki algoritmada Monte Carlo kısmının hiç olmaması ve tamamen deterministik olması garip geldi. Genelde uygulanan MCTS’nin deterministik olması şaşırtıcı; ben örneklemede rastgelelik olduğunu sanıyordum
Günümüzde benzer projelerde bunun yerini daha yüksek kaliteli sinir ağı değerlendirmeleri aldı. Rastgele hamleler oynayıp kimin kazandığına bakmak pek iyi bir yöntem değil ama o zamanlar bilinen en iyi strateji buydu
Sonuçta Monte Carlo kısmı, bugün hâlâ MCTS diye adlandırılan şeyin özsel bir parçası değildi; daha çok ikinci en iyi çözümdü. Bu yüzden isim biraz talihsiz kalıyor
İlginç olan şu ki çoğu Monte Carlo yöntemi gerçek rastgele sayı üreteçlerine değil, sözde rastgele sayı üreteçlerine dayanır; dolayısıyla aynı seed ve aynı girdi verildiğinde her zaman aynı sonucu üreten deterministik yöntemlerdir
Bu algoritma, genel amaçlı bir sözde rastgele sayı üreteci ve ayrı sezgisel yöntemler kullanmak yerine bir sinir ağına sorgu gönderiyor. Sinir ağı, devasa arama uzayı üzerinde bir sezgisel işlev görüyor; eğitimine bağlı olarak belirli sonuçlara güçlü şekilde kaymış çok kötü bir sözde rastgele sayı üreteci gibi davranıyor ve sonuçta sezgisel uygulanmış bir sözde rastgele sayı üreteci gibi görünüyor
Önemli nokta, bunun MCTS’nin özelleşmiş bir biçimi olması; dolayısıyla teknik olarak her kullanım senaryosuna uymaz
MCTS’yi araştırırken yazıda bahsedilen makale tamamen radarımın dışında kalmıştı. Bir sonraki fırsatta bu değiştirilmiş yöntemi bizzat çalıştırmak oldukça eğlenceli olabilir
Kısa bir giriş olması iyi olurdu
Aynı duruma birden fazla yoldan ulaşılabilen oyunlarda, farklı dallarda aynı durum düğümünü tekrar tekrar kaydetmek ciddi bellek israfına yol açabilir
Bu yazı, graf araması denilen yaklaşımı iyi inceliyor. Özünde, oyun durumlarını hash’leyip daha önce ziyaret edilip edilmediklerini kontrol etmek için ek hesaplama yaparak bellekten tasarruf etme fikri var
Daha önce görülmüş düğümleri yeniden kaydetmeye gerek kalmadığından, döngüsüz bir ağaç yönlendirilmiş çevrimsiz bir grafa dönüşür
Bu yüzden doğru sonuç almak için ağaç aramasını biraz uyarlamak gerekir. Özellikle optimizasyon birimini düğümlere, yani durumlara değil; kenarlara, yani eylem veya hamlelere daha uygun hale getirmek gerekir
Konuyu iyi anlayan biri tarafından yazılmış, edebi programlama tarzında kaleme alınmış iyi bir teknik deneme