ترخيص YOLO
العودة إلى مسرد Ultralytics

Monte Carlo Tree Search (MCTS)

يختار البحث الشجري بمونت كارلو (MCTS) الإجراءات عبر توسيع شجرة بحث انطلاقًا من محاكاة مسارات اللعب، مع التركيز على الحركات الواعدة. يُستخدم في AlphaGo والروبوتات.

البحث الشجري بمونت كارلو (MCTS) خوارزمية تخطيط تختار الإجراء التالي ببناء شجرة للاحتمالات المستقبلية انطلاقاً من عمليات محاكاة عديدة، وتخصص مزيداً من ميزانيتها للحركات التي تبدو واعدة. ولا تحتاج إلا إلى وسيلة لتوليد الحركات والنتائج القانونية، مثل قواعد لعبة أو محاكي، ولا تتطلب دالة تقييم مكتوبة يدوياً. وهي أيضاً خوارزمية ذات نتيجة متاحة في أي وقت: إذ تعيد أفضل حركة عُثر عليها حتى تلك اللحظة عند إيقافها، وتؤدي زيادة الوقت إلى تحسين النتيجة. وأطلق ريمي كولوم اسم الطريقة عليها عام 2006، وهو العام نفسه الذي نشر فيه ليفينتي كوتشيس وتشابا سيبفسفاري قاعدة UCT للاختيار، التي أصبحت الصيغة القياسية للطريقة. وخلال سنوات قليلة، أحدث MCTS تحولاً في لعبة غو الحاسوبية، ثم أسهم في تشغيل AlphaGo وAlphaZero، ويُستخدم الآن لتخطيط سلوك الروبوتات والمركبات والبحث في خطوات الاستدلال ضمن النماذج اللغوية الكبيرة (LLMs).

آلية عمل MCTS#

يحافظ البحث على شجرة تمثل عقدة جذرها الوضع الحالي، وتخزّن كل عقدة عدد مرات زيارتها وعدد المرات التي انتهت فيها تلك الزيارات بالفوز. وتتألف كل دورة من أربع مراحل:

  1. الاختيار: بدءاً من الجذر، انتقل عبر العقد المستكشفة بالكامل باختيار الابن ذي أعلى نتيجة UCT، التي توازن بين معدلات الفوز المرتفعة والحركات التي نادراً ما جُرّبت.
  2. التوسيع: أضف الحركة غير المجرّبة إلى أول عقدة تحتوي عليها بوصفها عقدة فرعية جديدة.
  3. المحاكاة: العب انطلاقاً من العقدة الجديدة حتى نهاية المباراة، عادةً بحركات عشوائية، للحصول على نتيجة.
  4. التمرير العكسي: ارجع صعوداً على طول المسار وحدّث عدد زيارات كل عقدة وإجمالي انتصاراتها باستخدام النتيجة.

عند نفاد الميزانية، تنفّذ الخوارزمية الحركة الأكثر زيارة من أبناء الجذر، وهي خيار أكثر ثباتاً من الحركة ذات أعلى متوسط.

الموازنة بين الاستكشاف والاستغلال#

تتعامل 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 بدلًا من ذلك باستخدام التعلّم المعزز بمكافآت قابلة للتحقق.

استكشف الحلول

الرؤية الحاسوبية في الرياضة

الرؤية الحاسوبية في الرياضة

اكتشف كيف يعزّز Ultralytics YOLO الرؤية الحاسوبية الرياضية عبر تتبّع اللاعبين والكرة، وتحليلات الأداء، ورؤى التدريب، وإعادة تأهيل الرياضيين.
معرفة المزيد
الرؤية الحاسوبية للصور الجوية

الرؤية الحاسوبية للصور الجوية

حوّل صور الطائرات المسيّرة والصور الجوية إلى رؤى آنية للزراعة وتربية الأحياء المائية والحفاظ على البيئة والتحليل الجغرافي المكاني باستخدام Ultralytics YOLO.
معرفة المزيد
الرؤية الحاسوبية في قطاع الطيران والفضاء

الرؤية الحاسوبية في قطاع الطيران والفضاء

طبّق الرؤية الحاسوبية في مجال الطيران والفضاء باستخدام Ultralytics YOLO لفحص الطائرات، واكتشاف الأجسام الغريبة على المدارج (FOD)، والعمليات الأرضية في المطارات، واكتشاف عيوب المواد المركّبة.
معرفة المزيد
الرؤية الحاسوبية في مجال الأمن

الرؤية الحاسوبية في مجال الأمن

احمِ كل موقع باستخدام نماذج Ultralytics YOLO. يدعم الذكاء الاصطناعي البصري مراقبة المحيط، واكتشاف التهديدات، والتعرف على لوحات المركبات، والسلامة في مكان العمل.
معرفة المزيد
الرؤية الحاسوبية في الروبوتات

الرؤية الحاسوبية في الروبوتات

عزّز أداء الآلات الذكية باستخدام نماذج Ultralytics YOLO. يدعم الذكاء الاصطناعي البصري في الروبوتات الملاحة الذاتية والإدراك وتعقب الأجسام والتحكم الآني.
معرفة المزيد
الرؤية الحاسوبية في الخدمات اللوجستية

الرؤية الحاسوبية في الخدمات اللوجستية

بسّط العمليات اللوجستية باستخدام نماذج Ultralytics YOLO. يتيح الذكاء الاصطناعي البصري فحص الطرود وفرزها وتتبع المركبات ومراقبة سلامة المستودعات في الوقت الفعلي.
معرفة المزيد
الرؤية الحاسوبية في تجارة التجزئة

الرؤية الحاسوبية في تجارة التجزئة

أعِد تصور تجارة التجزئة باستخدام نماذج Ultralytics YOLO. يتيح الذكاء الاصطناعي البصري تتبع المخزون ومراقبة الرفوف وإدارة الطوابير واستخلاص رؤى أذكى عن العملاء.
معرفة المزيد
الرؤية الحاسوبية في الرعاية الصحية

الرؤية الحاسوبية في الرعاية الصحية

أنشئ حلولًا للرعاية الصحية باستخدام نماذج Ultralytics YOLO. يعزز الذكاء الاصطناعي البصري في الرعاية الصحية سرعة التصوير الطبي، وكفاءة التشخيص، ومراقبة المرضى.
معرفة المزيد
الرؤية الحاسوبية في التصنيع

الرؤية الحاسوبية في التصنيع

حسّن التصنيع باستخدام نماذج Ultralytics YOLO. يعزز الذكاء الاصطناعي للرؤية مراقبة الجودة واكتشاف العيوب والالتزام بمعدات الوقاية الشخصية وأتمتة خطوط التجميع.
معرفة المزيد
الرؤية الحاسوبية في قطاع السيارات

الرؤية الحاسوبية في قطاع السيارات

طبّق الرؤية الحاسوبية في قطاع السيارات باستخدام نماذج Ultralytics YOLO. يعزز الذكاء الاصطناعي للرؤية سلامة الطرق ومساعدة السائق وأتمتة المركبات لإنشاء طرق أكثر ذكاءً.
معرفة المزيد
الرؤية الحاسوبية في الزراعة

الرؤية الحاسوبية في الزراعة

أدخل الذكاء الاصطناعي البصري إلى الزراعة الذكية باستخدام نماذج Ultralytics YOLO. عزّز مراقبة المحاصيل وتتبع الماشية والزراعة الدقيقة لزيادة الإنتاجية وتحسينها.
معرفة المزيد

لنبنِ مستقبل الذكاء الاصطناعي معًا!

ابدأ رحلتك نحو مستقبل تعلّم الآلة