Monte Carlo Tree Search (MCTS)
Monte Carlo Ağaç Araması (MCTS), umut vadeden hamlelere odaklanarak benzetimli oyunlarla bir arama ağacını genişletip eylemleri seçer. AlphaGo'da ve robotlarda kullanılır.
Monte Carlo ağaç araması (MCTS), çok sayıda simüle edilmiş oyun turundan olası geleceklerin ağacını büyüterek bir sonraki eylemi seçen ve bütçesinin daha büyük kısmını en umut verici görünen hamlelere ayıran bir planlama algoritmasıdır. Yasal hamleler ve sonuçlar üretmenin bir yoluna, örneğin bir oyunun kurallarına ya da bir simülatöre ihtiyaç duyar; elle yazılmış bir değerlendirme işlevi gerektirmez. Ayrıca herhangi bir zamanda durdurulabilen bir algoritmadır: ne zaman durdurulursa durdurulsun o ana kadar bulunan en iyi hamleyi döndürür; daha fazla süre daha iyi bir yanıt sağlar. Rémi Coulom yönteme 2006'da adını verdi; aynı yıl Levente Kocsis ve Csaba Szepesvári, yöntemin standart biçimi hâline gelen seçim kuralı UCT'yi yayımladı. MCTS birkaç yıl içinde bilgisayarlı Go'yu dönüştürdü, daha sonra AlphaGo ve AlphaZero'ya güç verdi; bugün robot ve araç davranışını planlamak ve büyük dil modellerindeki (LLM'lerde) muhakeme adımlarını aramak için kullanılıyor.
MCTS Nasıl Çalışır#
Arama, kökü mevcut konum olan ve düğümlerinde ziyaret sayısı ile bu ziyaretlerin kaçının zaferle sonuçlandığı tutulan bir ağacı sürdürür. Her yineleme dört aşamadan oluşur:
- Seçim: Kökten başlayarak, tamamen araştırılmış düğümlerde ilerle ve yüksek kazanma oranlarını nadiren denenmiş hamlelere karşı dengeleyen UCT puanı en yüksek çocuğu seç.
- Genişletme: Denenmemiş bir hamlenin bulunduğu ilk düğüme, bu hamleyi yeni bir çocuk olarak ekle.
- Simülasyon: Sonuç elde etmek için yeni çocuktan oyunun sonuna kadar, klasik yöntemde rastgele hamlelerle, oynat.
- Geri yayılım: Yol boyunca geriye ilerle ve sonucu kullanarak her düğümün ziyaret sayısını ve toplam galibiyet sayısını güncelle.
Bütçe tükendiğinde algoritma, kökün en çok ziyaret edilen çocuğunu oynar; bu, ortalaması en yüksek olanı seçmekten daha istikrarlı bir tercihtir.
Keşif ve Sömürü Arasındaki Denge#
UCT, her düğümdeki seçimi bir çok kollu haydut problemi olarak ele alır ve UCB1 formülünü uygular: bir çocuğun puanı, kazanma oranı w/n ile c·√(ln N / n) toplamıdır; burada n çocuğun, N ebeveyninin ziyaret sayısıdır ve c keşif sabitidir; teoride √2 olan c, pratikte ayarlanır. İkinci terim bir hamle daha sık denendikçe küçülür; böylece birkaç şanslı galibiyet alan bir hamle diğerlerini gölgede bırakamaz ve ihmal edilen bir hamle sonunda yeniden değerlendirilir.
Bu Python örneği küçük bir oyunda MCTS çalıştırır: oyuncular 10 taşlık bir yığından bir ila üç taş alır ve son taşı alan kazanır.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")İki taş almak 2.000 ziyaretin 1.889'unu alır ve simülasyonlarının %91'ini kazanır; bir taş almak 68, üç taş almak ise 43 ziyaret alır. Kazandıran hamle budur: 8 taş, yani 4'ün katı kalması, yığın boşalana kadar ilk oyuncunun her yanıta 4'ün katını bırakarak karşılık vermesini sağlar. Arama, kodlanmış bir strateji olmaksızın yalnızca rastgele oyun turları ve ziyaret istatistiklerinden bu hamleyi buldu.
AlphaGo'dan AlphaZero ve MuZero'ya#
Go'da yaklaşık 250 olan ortalama yasal hamle sayısı, satrançtaki yaklaşık 35 hamleye kıyasla, oyunu kapsamlı aramanın ötesine taşıdı; MCTS, 2000'lerin sonlarından itibaren bilgisayarlı Go'daki güç artışını sağladı. DeepMind'ın AlphaGo sistemi, olası hamleleri öneren bir politika ağı, konumları değerlendiren bir değer ağı ve hızlı oyun turlarıyla MCTS'yi yönlendirdi; Mart 2016'da Lee Sedol'ü 4–1 yendi. AlphaZero ve MuZero daha da ileri gitti. AlphaZero oyun turlarını tamamen bıraktı, yaprak konumları bir değer ağıyla puanladı ve bu ağı kendi kendine oynadığı oyunlarla eğitti; her aramadaki ziyaret sayılarını politika ağı için hedef olarak kullanması, MCTS'yi pekiştirmeli öğrenme içinde bir politika iyileştirme adımına dönüştürdü. MuZero aynı aramayı öğrenilmiş bir ortam modeli içinde çalıştırdı; böylece kuralları kendisine verilmeden Go, satranç, şogi ve Atari oyunlarını oynadı.
Planlama ve Muhakeme için MCTS#
Robotlar ve otonom araçlar, trafiğe katılma gibi belirsiz durumlarda planlama yapmak için MCTS kullanır. POMCP gibi çeşitler, gizli durumlar üzerinde bir inanç dağılımı tutarak yöntemi kısmen gözlemlenebilir Markov karar süreçlerine genişletir. Kamera girdisinden planlama yapan bir aramanın kökü için bir duruma ihtiyacı vardır: örneğin satranç oynayan bir robot kolu, tahta görüntüleriyle eğitilmiş bir Ultralytics YOLO26 modelini kullanarak her taşı bulabilir; elde edilen konum aramanın kökü olur.
LLM akıl yürütmesinde her düğüm kısmi bir çözüm, her kenar ise bir akıl yürütme adımıdır; dallara bir süreç ödül modeli veya yanıt kontrolü puan verir. Microsoft'un rStar-Math modeli, süreç tercih modeliyle MCTS kullanarak Qwen2.5-Math-7B'nin MATH kıyaslamasındaki puanını %58,8'den %90,0'a yükseltti. Düşünce Ağacı ise akıl yürütme adımlarını genişlik öncelikli veya derinlik öncelikli aramayla tarar. MCTS'yi eğitim sırasında kullanmak daha zor olmuştur: DeepSeek, DeepSeek-R1 için başarısız denemeleri arasında MCTS'yi de saymıştır; bunun nedeni, token dizileri uzayının bir masa oyununun uzayından çok daha büyük olması ve aramaya rehberlik eden değer modelinin eğitilmesinin zor olmasıdır. Bunun yerine modeli doğrulanabilir ödüllerle pekiştirmeli öğrenme kullanarak eğitmiştir.










