Monte Carlo Tree Search (MCTS)
يختار البحث الشجري بمونت كارلو (MCTS) الإجراءات عبر توسيع شجرة بحث انطلاقًا من محاكاة مسارات اللعب، مع التركيز على الحركات الواعدة. يُستخدم في AlphaGo والروبوتات.
البحث الشجري بمونت كارلو (MCTS) خوارزمية تخطيط تختار الإجراء التالي ببناء شجرة للاحتمالات المستقبلية انطلاقاً من عمليات محاكاة عديدة، وتخصص مزيداً من ميزانيتها للحركات التي تبدو واعدة. ولا تحتاج إلا إلى وسيلة لتوليد الحركات والنتائج القانونية، مثل قواعد لعبة أو محاكي، ولا تتطلب دالة تقييم مكتوبة يدوياً. وهي أيضاً خوارزمية ذات نتيجة متاحة في أي وقت: إذ تعيد أفضل حركة عُثر عليها حتى تلك اللحظة عند إيقافها، وتؤدي زيادة الوقت إلى تحسين النتيجة. وأطلق ريمي كولوم اسم الطريقة عليها عام 2006، وهو العام نفسه الذي نشر فيه ليفينتي كوتشيس وتشابا سيبفسفاري قاعدة UCT للاختيار، التي أصبحت الصيغة القياسية للطريقة. وخلال سنوات قليلة، أحدث MCTS تحولاً في لعبة غو الحاسوبية، ثم أسهم في تشغيل AlphaGo وAlphaZero، ويُستخدم الآن لتخطيط سلوك الروبوتات والمركبات والبحث في خطوات الاستدلال ضمن النماذج اللغوية الكبيرة (LLMs).
آلية عمل MCTS#
يحافظ البحث على شجرة تمثل عقدة جذرها الوضع الحالي، وتخزّن كل عقدة عدد مرات زيارتها وعدد المرات التي انتهت فيها تلك الزيارات بالفوز. وتتألف كل دورة من أربع مراحل:
- الاختيار: بدءاً من الجذر، انتقل عبر العقد المستكشفة بالكامل باختيار الابن ذي أعلى نتيجة UCT، التي توازن بين معدلات الفوز المرتفعة والحركات التي نادراً ما جُرّبت.
- التوسيع: أضف الحركة غير المجرّبة إلى أول عقدة تحتوي عليها بوصفها عقدة فرعية جديدة.
- المحاكاة: العب انطلاقاً من العقدة الجديدة حتى نهاية المباراة، عادةً بحركات عشوائية، للحصول على نتيجة.
- التمرير العكسي: ارجع صعوداً على طول المسار وحدّث عدد زيارات كل عقدة وإجمالي انتصاراتها باستخدام النتيجة.
عند نفاد الميزانية، تنفّذ الخوارزمية الحركة الأكثر زيارة من أبناء الجذر، وهي خيار أكثر ثباتاً من الحركة ذات أعلى متوسط.
الموازنة بين الاستكشاف والاستغلال#
تتعامل UCT مع الاختيار عند كل عقدة بوصفه مسألة لصوص متعددي الأذرع، وتطبّق صيغة UCB1: نتيجة العقدة الفرعية هي معدل فوزها w/n مضافاً إليه c·√(ln N / n)، حيث n عدد زيارات العقدة الفرعية، وN عدد زيارات والدها، وc ثابت الاستكشاف، وقيمته √2 نظرياً ويُضبط عملياً. ويتناقص الحد الثاني كلما زاد اختبار الحركة، فلا تستطيع حركة حققت بضعة انتصارات محظوظة إقصاء البقية، وتحصل الحركة المهملة في نهاية المطاف على فرصة أخرى.
يشغّل مثال Python التالي MCTS على لعبة صغيرة: يأخذ اللاعبون حجراً إلى ثلاثة أحجار من كومة فيها 10 أحجار، ويفوز من يأخذ الحجر الأخير.
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}")تحصل حركة أخذ حجرين على 1,889 زيارة من أصل 2,000، وتفوز في 91% من محاكاةاتها، مقابل 68 زيارة لأخذ حجر واحد و43 زيارة لأخذ ثلاثة أحجار. إنها الحركة الرابحة: فترك 8 أحجار، وهو عدد من مضاعفات 4، يتيح للاعب الأول الرد على كل حركة بإعادة الكومة إلى عدد من مضاعفات 4 حتى تفرغ. عثر البحث عليها بالاعتماد على المحاكاة العشوائية وإحصاءات الزيارات وحدهما، من دون ترميز أي استراتيجية.
من AlphaGo إلى AlphaZero وMuZero#
بلغ متوسط عدد الحركات القانونية المتفرعة في لعبة غو نحو 250، مقابل 35 تقريباً في الشطرنج، ما جعل البحث الشامل غير ممكن، ودفع MCTS القفزة في قوة لعب غو حاسوبياً منذ أواخر العقد الأول من الألفية. ووجّه AlphaGo من DeepMind خوارزمية MCTS باستخدام شبكة سياسة تقترح الحركات المرجحة وتقيّم الأوضاع بشبكة قيمة ومحاكاة سريعة، وفي مارس 2016 تغلب على لي سيدول بنتيجة 4–1. وتجاوز AlphaZero وMuZero ذلك. فقد استغنى AlphaZero عن المحاكاة تماماً، وقيّم الأوضاع الطرفية بشبكة قيمة، ودرّب تلك الشبكة على مباريات خاضها ضد نفسه، مستخدماً أعداد الزيارات من كل عملية بحث أهدافاً لشبكة السياسة، ما يجعل MCTS خطوة لتحسين السياسة ضمن التعلّم المعزز. وشغّل MuZero البحث نفسه ضمن نموذج متعلّم للبيئة، لذا لعب غو والشطرنج والشوغي وألعاب Atari من دون تزويده بقواعدها.
MCTS للتخطيط والاستدلال#
تستخدم الروبوتات والمركبات ذاتية القيادة MCTS للتخطيط في مواقف غير مؤكدة مثل الاندماج في حركة المرور، وتوسّع أشكال مثل POMCP استخدامها لتشمل عمليات اتخاذ القرار لماركوف ذات الرصد الجزئي، وذلك بتتبّع اعتقاد حول الحالات المخفية. ويحتاج البحث الذي يخطط انطلاقاً من مدخلات الكاميرا إلى حالة للجذر: فمثلاً، يمكن لذراع روبوتية تلعب الشطرنج استخدام نموذج Ultralytics YOLO26 مدرّب على صور اللوح لـتحديد موقع كل قطعة، ويصبح الوضع المستعاد جذر البحث.
في استدلال LLM، تمثل كل عقدة حلًا جزئيًا وكل حافة خطوة استدلال، ويقيّم الفروعَ نموذج مكافأة العملية أو فحص الإجابة. واستخدم rStar-Math من Microsoft بحث MCTS مع نموذج تفضيل للعملية، ليرفع أداء Qwen2.5-Math-7B من 58.8% إلى 90.0% في معيار MATH. ويبحث شجر الأفكار في خطوات الاستدلال باستخدام البحث بعرض الشجرة أو بعمقها بدلًا من ذلك. وكان استخدام MCTS أثناء التدريب أصعب: إذ أدرجته DeepSeek ضمن محاولاتها غير الناجحة لـDeepSeek-R1، لأن فضاء تسلسلات الرموز أكبر بكثير من فضاء لعبة لوحية، ولأن تدريب نموذج القيمة الذي يوجّه البحث صعب؛ ودُرّب R1 بدلًا من ذلك باستخدام التعلّم المعزز بمكافآت قابلة للتحقق.










