🤖 machine learning

Monte Carlo Permutation Search

تقدم هذه الورقة البحثية خوارزمية "البحث عن التبديل بطريقة مونت كارلو" (MCPS)، وهي خوارزمية MCTS عامة الغرض تتفوق على خوارزمية GRAVE في ألعاب مثل Hex وGo من خلال دمج إحصائيات اللعب على مستوى المسار في حد الاستكشاف واشتقاق صيغة وزن جديدة تلغي الحاجة إلى معلم التحييز الخاص بخوارزمية GRAVE.

المؤلفون الأصليون: Tristan Cazenave

نُشر 2026-05-27

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Tristan Cazenave

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول حل لغز معقد، مثل لعبة "جو" (Go) أو "هيكس" (Hex)، ولكن ليس لديك سوثير كمبيوتر أو ذكاء اصطناعي مدرب ليخبرك بالخطوة الأفضل. بدلاً من ذلك، عليك الاعتماد على "التخمين والتحقق" عن طريق تجربة آلاف السيناريوهات المستقبلية العشوائية في مخيلتك. هكذا يعمل برنامج حاسوبي يسمى بحث شجرة مونت كارلو (MCTS).

لفترة طويلة، كانت أفضل طريقة لهذا التخمين هي خوارزمية تسمى GRAVE. كانت جيدة في النظر إلى الماضي للتنبؤ بالمستقبل، لكن مؤلف هذه الورقة البحثية، تريستان كازينيف، فكر قائلاً: "يمكننا القيام بعمل أفضل".

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

الطرق الثلاث للنظر إلى الماضي

لتحديد الخطوة التالية التي يجب اتخاذها، ينظر MCPS إلى تاريخ ألعابه العشوائية (التي تسمى "المحاكاة") بثلاث طرق مختلفة. فكر في هذه الطرق كأنها ثلاث عدسات مختلفة لكاميرا:

عدسة "المسار الدقيق" (الرؤية القياسية):
هذه العدسة تنظر إلى الألعاب التي قام فيها اللاعب بنفس تسلسل الحركات بالضبط للوصول إلى الوضع الحالي، ثم قام بالخطوة المحددة التي نختبرها.
- مثال توضيوي: "مشيت في شارع الرئيسي، ثم انعطفت يساراً، ثم اشتريت قهوة. كيف سارت تلك التجربة؟"
عدسة "الترتيب لا يهم" (تطوير GRAVE):
هذه العدسة تنظر إلى الألعاب التي قام فيها اللاعب بنفس الحركات للوصول إلى تلك النقطة، ولكن الترتيب كان مختلفاً قليلاً، وظهرت الخطوة المحددة التي نختبرها في مرحلة لاحقة من اللعبة.
- مثال توضيوي: "اشتريت قهوة، ثم مشيت في الشارع الرئيسي، ثم انعطفت يساراً. إنها نفس المكونات، فقط بترتيب وصفة مختلف. هل كان الطعم جيداً رغم ذلك؟"
- لماذا يساعد هذا: في العديد من الألعاب، لا يغير ترتيب وضع قطع اللعب من الحالة النهائية للوحة. لذا، تسمح هذه العدسة للكمبيوتر بالتعلم من المزيد من الألعاب، وليس فقط من تلك التي طابقت الترتيب المحدد.
عدسة "التبديل" (السر الجديد لـ MCPS):
هذه هي الإضافة الجديدة. فهي تنظر إلى أي لعبة استخدم فيها اللاعب نفس مجموعة الحركات (المسار للوصول إلى الوضع الحالي + الخطوة الجديدة)، بغض النظر عن الترتيب الذي حدثت به.
- مثال توضيوي: "استخدمت مطرقة، ومفك براغي، ومسماراً لبناء رف. لا يهم إذا طرقت أولاً أو ربطت المسمار أولاً؛ إذا استخدمت تلك الأدوات الثلاث، فقد تم بناء الرف. كيف نجحت تلك المجموعة؟"
- العقبة: في بعض الألعاب (مثل أتاري جو - AtariGo)، يفرق الترتيب لأن اللعبة يمكن أن تنتهي مبكراً (مثل التقاط حجر). يتعامل MCPS مع هذا الأمر بذكاء من خلال كيفية تجميع هذه الحركات.

"المعادلة السحرية"

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

فكر في الأمر كصنع "سموذي". لديك ثلاث فواكه (الإحصائيات الثلاث). استخدم GRAVE وصفة ثابتة كانت تبدو أحياناً غير متوازنة. أما MCPS فيستخدم وصفة مثالية رياضياً تضبط كميات الفواكه تلقائياً بناءً على مقدار البيانات المتوفرة لكل منها. والأفضل من ذلك؟ هو أنه لا يحتاج إلى "اختبار تذوق" (أي ضبط بشري لمعامل الانحياز) ليحصل على النتيجة الصحيحة؛ فالرياضيات تقوم بذلك تلقائياً.

كيف كان أداؤه في العالم الحقيقي

اختبر المؤلف MCPS مقابل البطل القديم (GRAVE) في خمسة أنواع مختلفة من الألعاب:

هيكس (المطابقة المثالية): في هذه اللعبة، لا يغير ترتيب الحركات الوضع النهائي أبداً. كان MCPS فائزاً كبيراً هنا، خاصة في اللوحات الكبيرة. كان الأمر كأنه يمتلك خريطة تظهر كل المسارات الممكنة، وليس فقط المسار الذي سلكته.
جو (المفكر العميق): في اللوحات الصغيرة، كانا متساويين تقريباً. ولكن في اللوحات الكبيرة، ومع منح الكمبيوتر مزيداً من الوقت للتفكير، تفوق MCPS. لقد كان أفضل في استخدام ذلك الوقت الإضافي للتعمق في أكثر خطوط اللعب واعداً، بينما ظل الأسلوب القديم عالقاً في استكشاف خيارات سطحية.
أتاري جو (المنهي السريع): هذه لعبة حيث الفوز يكون بأول عملية التقاط. هنا، الترتيب يفرق. ومن المثير للدهشة أن MCPS لا يزال فائزاً، لكن ميزته كانت أكبر في اللوحات الصغيرة حيث تنتهي اللعبة بسرعة. في اللوحات الكبيرة، تصبح اللعبة طويلة جداً بحيث لا تساعد خدعة "الترتيب لا يهم" كثيراً.
نو جو (الفائز المستمر): هذه لعبة تخسر فيها إذا قمت بالالتقاط. فاز MCPS في كل مكان تقريباً، متفوقاً على الطريقة القديمة بفارق ملموس.
لعبة الحرب (شيطان السرعة): في هذه اللعبة الاستراتيجية المخصصة، لم يلعب MCPS بشكل أفضل فحسب، بل لعب بسرعة أكبر أيضاً. لقد قام بمحاكاة ألعاب انتهت في وقت أقصر ووجد استراتيجية الفوز بسرعة أكبر، مما سمح له بإجراء المزيد من عمليات المحاكاة في نفس الفترة الزمنية.

الخلاصة

تزعم الورقة البحثية أن MCPS هو طريقة أذكى وأكثر كفاءة لجعل الحواسيب تلعب الألعاب دون الحاجة إلى تعلم عميق أو تدريب هائل.

فهو يعمل من خلال إدراك أنه في العديد من الألعاب، تكون مجموعة الحركات التي تقوم بها أكثر أهمية من ترتيب قيامك بها. ومن خلال حساب عدد المرات التي ظهرت فيها مجموعة محددة من الحركات في الألعاب العشوائية، يبني MCPS "حدساً" أفضل حول ماهية الحركات الجيدة. إنه يشبه المحقق الذي يدرك أنه حتى لو وصل المشتبه بهم بترتيب مختلف، فإن حقيقة وجودهم جميعاً في مسرح الجريمة هي الدليل الحقيقي.

والنتيجة هي أداة عامة الغرض تتفوق على أفضل طريقة سابقة في معظم السيناريوهات التي تم اختبارها، مما يجعلها معياراً جديداً قوياً لذكاء الألعاب الاصطناعي عندما لا يكون لديك سوبر كمبيوتر تحت تصرفك.

ملخص تقني: بحث التبديل بنموذج مونت كارلو (MCPS)

بيان المشكلة

تعد خوارزمية البحث في شجرة مونت كارلو (MCTS) خوارزمية مهيمنة في ألعاب التنافس واتخاذ القرار، لا سيما في المجالات التي يكون فيها التعلم المعزز العميق غير ممكن بسبب نقص بيانات التدريب أو القيود الحسابية (مثل الألعاب العامة - General Game Playing). وبينما نجحت متغيرات MCTS مثل GRAVE (التي تعتمد على Generalized RAVE) في تحسين خوارزمية UCT القياسية عبر الاستفادة من الإحصائيات من العقد السلفية وهيورستيك "كل الحركات كأول حركة" (AMAF)، إلا أنها تعتمد على مصدرين أساسيين للمعلومات: إحصائيات عمليات اللعب (playouts) التي تبدأ بحركة محددة، وإحصائيات عمليات اللعب التي تظهر فيها الحركة في مرحلة لاحقة.

تحدد الورقة البحثية قصوراً في النهج الحالي: فهي لا تستغل بشكل كامل المعلومات الإحصائية الواردة في عمليات اللعب التي يظهر فيها تسلسل الحركات المؤدية إلى عقدة ما بترتيب مختلف. في الألعاب ذات الخصائص التبادلية (مثل لعبة Hex)، يؤدي أي تبديل في ترتيب الحركات إلى نفس الحالة. أما في الألعاب غير التبادلية (مثل AtariGo)، فقد تؤدي التبديلات إلى حالات مختلفة، ومع ذلك تفترض الورقة أن القيمة الإحصائية للحركات تظل غنية بالمعلومات. الهدف هو تطوير خوارزمية MCTS عامة الأغراض تعمل على تحسين GRAVE دون الحاجة إلى ضبط خاص بالمشكلة، أو تدريب نموذج، أو معاملات انحياز (bias hyperparameters).

المنهجية

المفهوم الجوهري: بحث التبديل بنموذج مونت كارلو (MCPS)

يقدم MCPS مصدراً ثالثاً للإحصائيات لعملية تقييم العقدة. لتقييم إجراء $a$ عند عقدة $s$ تم الوصول إليها عبر مسار $(a_0, a_1, \dots, a_d)$ ، يقوم MCPS بتجميع البيانات من ثلاث مجموعات متميزة من عمليات اللعب:

الإحصائيات المباشرة ( $Q$ ): عمليات اللعب التي تبدأ بالمسار المؤدي إلى $s$ متبوعاً مباشرة بالإجراء $a$ .
إحصائيات AMAF ( $\tilde{Q}$ ): عمليات اللعب التي تبدأ بالمسار المؤدي إلى $s$ ، حيث تظهر الحركة $a$ لاحقاً في التسلسل (نهج GRAVE القياسي).
إحصائيات التبديل ( $\hat{Q}$ ): عمليات اللعب التي تحتوي على مجموعة الحركات $\{a_0, a_1, \dots, a_d, a\}$ بأي ترتيب وفي أي موضع.

الاشتقاق الرياضي للأوزان

تقدم الورقة اشتقاقاً رياضياً لدمج هذه المقدرات الثلاثة. بافتراض أن الإحصائيات مستقلة، استنتج المؤلفون الأوزان التي تقلل من تباين المقدر (variance).
لتكن $n$ و $\tilde{n}$ و $\hat{n}$ هي أعداد العينات للإحصائيات الثلاثة. الأوزان المثلى ( $\beta, \tilde{\beta}, \hat{\beta}$ ) تتناسب مع أعداد عيناتهم:
$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$
هذا الجمع المحدب (convex combination) يلغي الحاجة إلى معامل الانحياز المستخدم في خوارزمية GRAVE، مما يوفر نظام وزن خالٍ من المعاملات (parameter-free).

التنفيذ الخوارزمي

الاختيار (Selection): يتم حساب قيمة الحركة كمتوسط مرجح للمقدرات الثلاثة.
حساب إحصائيات التبديل: لحساب $\hat{Q}$ بكفاءة، تستخدم الخوارزمية نافذة منزلقة من عمليات اللعب الأخيرة (الافتراضي $W=10,000$ ) ممثلة كـ bitsets. بالنسبة لعقدة $s$ ، تقوم الخوارزمية بتقاطع الـ bitsets لجميع الحركات الموجودة في المسار المؤدي إلى $s$ لتحديد عمليات اللعب التي تحتوي على تسلسل المسار الكامل. ثم تتقاطع هذه النتيجة مع الـ bitset للحركة المرشحة $a$ لعزل عمليات اللعب ذات الصلة. يتم تنفيذ ذلك باستخدام عمليات الكلمات ذات الـ 64 بت (POPCOUNT و bit-scan) لضمان الكفاءة.
التجميد (Freezing): بمجرد أن تجمع العقدة عدداً معيناً من الزيارات ( $\rho=30$ )، يتم حساب إحصائيات التبديل الخاصة بها و"تجميدها". تعمل هذه العقدة بعد ذلك كمرجع لشجرتها الفرعية بأكملها، مما يسمح للأحفاد بوراثة هذه الإحصائيات دون إعادة حسابها.
ترميز الحركات (Move Coding): لتمكين نقل المعرفة بين مواضع اللوحة المختلفة، يتم رسم خرائط للحركات إلى أكواد عددية بناءً على سمات اللعبة ذات الصلة (مثل اللاعب، الخلية المستهدفة، محفز القتال) بدلاً من الإحداثيات الدقيقة.

المساهمات الرئيسية

التوسيع الخوارزمي: اقتراح MCPS، الذي يدمج إحصائيات التبديل في قاعدة اختيار MCTS، مما يعد توسيعاً لخوارزمية GRAVE.
التحسين النظري: اشتقاق صيغ الوزن التي تقلل تباين المقدر تحت فرضيات الاستقلال، مما يلغي الحاجة لمعامل انحياز GRAVE.
التنفيذ الفعال: طريقة لحساب إحصائيات التبديل باستخدام bitsets ونوافذ منزلقة، مما يسمح للخوارزمية بالتعامل مع الانفجار التوليفي لترتيب الحركات بكفاءة.
القابلية العامة للتطبيق: إثبات أن الخوارزمية تعمل عبر أنواع متنوعة من الألعاب (التبادلية وغير التبادلية) دون تعديلات خاصة بالمشكلة أو ضبط للمعاملات.

النتائج التجريبية

اختبر المؤلفون MCPS مقابل GRAVE عبر خمس ألعاب: Hex، و Go، و AtariGo، و NoGo، ولعبة حرب (Wargame) غير متماثلة مخصصة. في جميع الحالات، لُعبت 800 مباراة لكل تكوين (400 مباراة لكل خوارزمية تلعب أولاً) تحت ميزانيات زمنية متطابقة.

Hex: يتفوق MCPS على GRAVE في لوحات $7\times7$ أو أكبر، حيث تصل معدلات الفوز إلى 70-76% في اللوحات الأكبر. في $5\times5$ ، يؤدي العبء الإضافي للـ bitsets إلى إضعاف أداء MCPS قليلاً. تزداد الميزة مع حجم اللوحة لأن MCPS يبني أشجاراً أعمق.
Go: يتفوق MCPS على GRAVE في لوحات $7\times7$ أو أكبر. والجدير بالذكر أنه في اللوحات الأكبر ( $13\times13$ ، $15\times15$ )، تتسع فجوة معدل الفوز بشكل كبير مع زيادة الميزانية الزمنية (تصل إلى 63.75% عند 2 ثانية). يبني MCPS باستمرار أشجاراً أعمق مع توفر المزيد من الوقت، بينما غالباً ما يستقر عمق شجرة GRAVE أو ينخفض.
AtariGo: يتفوق MCPS على GRAVE في جميع التكوينات، مع تحقيق أكبر المكاسب في اللوحات الصغيرة ( $5\times5$ ، $7\times7$ ). تتضاءل الميزة في اللوحات الأكبر لأن اللعبة غالباً ما تنتهي قبل أن يصل البحث إلى الحالة النهائية، مما يحد من فائدة الأشجار الأعمق.
NoGo: يظهر MCFS تحسناً أكثر اتساقاً، حيث يتفوق على GRAVE في كل خلية بمعدلات فوز تتراوح بين 57% و 69%. التحسن ثابت عبر أحجام اللوحات والميزانيات الزمنية.
Wargame: يتفوق MCPS على GRAVE في لوحات $9\times9$ أو أكبر. تعمل الخوارزمية بشكل أسرع بنسبة 15-33% (عمليات لعب أكثر في الثانية) بسبب قصر طول المحاكاة وتصل إلى حالات اللعبة الحاسمة بشكل أسرع.

الأهمية والادعاءات

تدعي الورقة أن MCPS يمثل تحسيناً كبيراً لتطبيقات MCTS عامة الأغراض، خاصة في السيناريوهات التي لا يتوفر فيها التعلم العميق. الآلية الأساسية للنجاح هي "قاعدة الاختيار الأكثر دقة"، والتي تسمح للخوارزمية بـ:

بناء أشجار بحث أعمق.
تقليل عمل المحاكاة لكل دورة (في بعض الألعاب).
الوصول إلى حالات أقرب للنهاية (في ألعاب مثل AtariGo).
تحويل وقت الحساب الإضافي إلى استكشاف أعمق للخطوط الواعدة (كما لوحظ في Go).

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