Monte Carlo Grafik Aramasının Temel İlkeleri
- Monte Carlo Ağaç Araması (MCTS), ağaç yerine yönlü grafiklere uygulanan "Monte Carlo Grafik Araması" ("MCGS") biçiminde, zaman zaman uygulanması zor görülen bir yöntemdir.
- Mevcut akademik referanslar, ağaçlar için MCTS'nin "standart" açıklamasını izlediği için bunu grafiklere genelleştirmeyi kavramsal olarak anlamak zordur.
- Bu belge, daha sezgisel olduğu düşünülen, özünde eşdeğer ama daha temiz bir açıklama sunar ve grafik aramasının neden bu şekilde çalışması gerektiğini temel ilkelerden türetir.
Giriş / Arka Plan
- Oyun ağacı araması veya diğer ağaç araması uygulamalarında, aynı duruma götüren birden fazla olası hamle ya da eylem dizisi bulunabilir.
- Örneğin satrançta
1. d4 d5 2. Nf3, 1. Nf3 d5 2. d4 ile aynı konuma götürür.
- Oyunlarda bu tür durumlar mümkün olduğunda, arama derinliğiyle birlikte olası durum sayısı geometrik olarak artar ve derin aramayı gereğinden pahalı hale getirir.
- İdeal olarak, aramanın bu dallarının hesaplamayı paylaşmasını isteriz.
- Ancak standart MCTS uygulamaları oyunu dallanan bir ağaç olarak ele alır ve ağaç içindeki yinelenen konumları verimsiz biçimde yeniden arar.
MCTS'nin Genel Açıklaması - Çalışan İstatistiklerin Ağacı
- MCTS, genellikle ağacın düğümlerinden geçen playout'ların çalışan istatistiklerini izleyen bir algoritma olarak açıklanır.
- Her düğüm oyunun tek bir durumunu temsil eder ve ziyaret sayısını (N) ile playout'lar tarafından örneklenen fayda değerlerinin çalışan ortalamasını (Q) izler.
- MCTS'nin tek bir yinelemesi veya playout'u, ağaç boyunca aşağı inerek keşfedilecek bir sonraki eylemi örnekleme, yeni bir duruma ulaşıldığında ağacı genişletme, yeni durumun faydası U'yu tahmin etme ve sonra ağaçta geri yukarı çıkarak her düğümde N'yi artırıp ortalama Q'yu örneklenen yeni fayda U ile güncelleme sürecinden oluşur.
Grafikte Ne Yanlış Gider?
- Yukarıdaki algoritma ağaç yerine doğrudan yönlü çevrimsiz bir grafe uygulanırsa, algoritma hatalı hale gelebilir.
- Bunun nedeni, MCTS'nin çok kollu haydut temelli yöntemlerin bir uzantısı olarak genellikle playout'ların çalışan istatistikleri açısından açıklanmasıdır.
- Czech, Korus ve Kersting bu sorunu çözüp sağlam bir algoritmaya ulaşmıştır, ancak MCTS'ye çevrimiçi politika öğrenimi açısından yaklaşan alternatif bir yöntem de vardır.
- Bu alternatif açıklamada, grafiğe genelleme nispeten doğal biçimde ortaya çıkar.
MCTS'yi Düzenlileştirilmiş Politika Optimizasyonu Olarak Yeniden Görmek
- MCTS, farklı düğümlerde istatistikleri güncellediğinde, aslında çevrimiçi politika öğreniminin bir biçimini yürütmektedir.
- MCTS'nin ziyaret dağılımı, sinir ağındaki ön politika P'yi beklenen faydayı en üst düzeye çıkaran "sonradan oluşan" bir politikaya doğru kademeli olarak iyileştirir.
Doğru Monte Carlo Grafik Araması Yapmak
- MCTS'yi grafiğe genişletirken ortaya çıkan tüm sorunlar, yalnızca ebeveyn düğümlerden gelen çocuk düğüm ziyaretlerinin varsayılmasından kaynaklanır.
- Teori, PUCT tarafından seçilen kümülatif eylem sayılarının, optimize edilmiş politika π'yi yaklaşık olarak veren sonradan oluşan bir politika sağladığını garanti eder; bu yüzden izlenmesi gereken budur.
- Bir düğümün rapor ettiği Q değerinin, sonradan oluşan politikanın beklenen değeri olduğu yorumunu kullanırsak, tek tek playout'ların nasıl hesaplanacağına girmeden özyinelemeli Q formülünü uygulayabiliriz.
Uygulama Tercihleri Üzerine Tartışma
- Bu belgede sunulan algoritma, Czech, Korus ve Kersting'in algoritmasına çok benzer, ancak birkaç uygulama tercihi ve bazı küçük farklar içerir.
- Q değerlerinin "bayatlığını" azaltmaya yönelik stratejiler veya artımlı güncelleme yerine aynı güncellemeyi kullanmak gibi, uygulamayı basitleştirmek adına seçilebilecek çeşitli yöntemler vardır.
GN⁺'nün Görüşü
- Bu yazı, Monte Carlo Grafik Aramasının (MCGS) karmaşıklığını ve onu anlamak için yeni bir yaklaşımı ortaya koyarak yapay zeka ve oyun teorisi alanına ilgi duyan kişiler için ilgi çekici olabilir.
- MCTS gibi algoritmalar, satranç ve Go gibi karmaşık strateji oyunlarında önemli bir rol oynar ve bu oyunlar için yapay zeka geliştirilmesine katkı sağlar.
- Ancak bu yazıda ele alınan içerik, başlangıç seviyesindeki yazılım mühendisleri için biraz zor olabilir ve kuramsal arka plan bilgisi gerektirir.
- MCGS'yi uygularken dikkate alınması gereken noktalardan biri, algoritmanın verimliliği ile doğruluğu arasında nasıl denge kurulacağıdır; bu, gerçek oyun ortamlarındaki performansı büyük ölçüde etkileyebilir.
- Benzer işlev sunan diğer proje veya ürünler arasında DeepMind'ın AlphaZero'su bulunur; bu sistem satranç, Go ve shogi'de insan dünya şampiyonlarını aşan bir seviyeye ulaşmıştır.
1 yorum
Hacker News görüşleri
Grafik araması, yapay zekanın akıl yürütme alanında ilerlemesi için gerekli; yalnızca basit LLM'ler başarısız olacaktır. Bağlantıda, oyun tabloları için Zobrist hashing dahil pek çok iyi referans var. Grafik aramasının hesaplama açısından patlamaması için dil tabanlı durum açıklamaları adına iyi bir hashing yöntemi bulmak gerekiyor. Ağaç araması hakkında iyi okumalar arasında 'Thinking Fast and Slow' ve 'Teaching Large Language Models to Reason with Reinforcement Learning' yer alıyor; bunlar MCTS yaklaşımını güncel diğer RL stratejileriyle karşılaştırıyor.
HN URL'sinden doğrudan KataGo'nun dahi geliştiricisini tanıdım. Reddit'teki cbaduk gönderileri sürekli olarak mükemmel.
"Monte-Carlo Tree Search" adı konusunda, okurların söz edilen algoritmada aslında "Monte-Carlo" olmadığını ve bunun tamamen deterministik olduğunu fark etmesi gerekir. MCTS'nin genellikle deterministik olarak uygulanması tuhaf. Örneklemede rastgelelik olduğunu varsaymıştım.
Bahsedilen makale, MCTS'yi incelerken radarımın tamamen dışında kalmıştı. Bir dahaki fırsatta bu değişikliği denemek çok eğlenceli olacak.
Arka plan bilgisi: