بحث شجرة مونت كارلو

لا يحاول بحث شجرة مونت كارلو، ويُختصر إلى MCTS، فحص كل تفرع إلى العمق نفسه. بل ينمي شجرة تدريجيا ويستخدم النتائج المتراكمة ليقرر إلى أي فرع يوجه الدفعة التالية من الحساب. ولا تكون النقلة كثيرة الزيارات جيدة تلقائيا، لكن تقديرها يستند عادة إلى بحث أكثر.

دورة واحدة من MCTS

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

يوازن تكرار هذه الدورة بين الاستغلال والاستكشاف. فالاستغلال يعني تخصيص جهد أكبر حيث تكون الأدلة مواتية بالفعل. والاستكشاف يعني اختبار البدائل غير المؤكدة كي لا تُرفض مفاجأة في وقت مبكر. وتعتمد قاعدة الموازنة الدقيقة على التطبيق.

بخلاف مينيماكس، يقرر MCTS عادة مقدار فحص فرع استنادا إلى الأدلة المجمعة أثناء البحث، لا إلى عمق موحد وحده. وفي بعض برامج الشطرنج القائمة على الشبكات العصبية، توفر الشبكة سياسة تقترح النقلات المرجحة، وقيمة تقدر النتيجة. وللقيمة دور مرتبط بـدالة التقييم، مع أن عملية البحث الكاملة مختلفة.