مرجع
آخر الزيارات

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

2٬411 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في علوم الكمبيوتر ، تعتبر شجرة البحث مونت كارلو ( MCTS ) خوارزمية بحث استدلالية لبعض أنواع عمليات اتخاذ القرار ، وأبرزها تلك المستعملة في البرامج التي تلعب ألعاب الطاولة . في هذه المقالة 6 أقسام: «الاستكشاف والاستغلال»، «البحث عن لعبة مونت كارلو النقية» و«التحسينات» وغيرها.
المحتويات
  1. الاستكشاف والاستغلال
  2. البحث عن لعبة مونت كارلو النقية
  3. التحسينات
  4. مبدأ التشغيل
  5. الإيجابيات والسلبيات
  6. طريقة مونت كارلو

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

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

تاريخ

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

كذلك، stands for the total number of simulations after the -th move run by the parent node of the one considered

من جانب آخر، stands for the number of wins for the node considered after the -th move

من جانب آخر، is the exploration parameter—theoretically equal to ; in practice usually chosen empirically

في هذا الإطار، تعتمد أغلب التطبيقات المعاصرة لبحث شجرة مونت كارلو على بعض المتغيرات من UCT التي ترجع جذورها إلى خوارزمية تحسين محاكاة AMS لتقدير دالة القيمة في عمليات اتخاذ القرار ماركوف ذات الأفق المحدود (MDPs) ) قدمها تشانج وآخرون (2005) في بحوث العمليات . (كان AMS هو أول عمل يستكشف فكرة الاستكشاف والاستغلال القائم على UCB في بناء الأشجار المأخوذة من العينات/المحاكاة (مونت كارلو) وكان البذرة الرئيسية لـ UCT. )

وفي هذا الصدد، المكون الأول من الصيغة أعلاه يتوافق مع الاستغلال؛ وهو مرتفع بالنسبة للتحركات ذات نسبة الفوز المتوسطة العالية. المكون الثاني يتوافق مع الاستكشاف؛ وهو مرتفع بالنسبة للتحركات ذات المحاكاة القليلة.

وفي السياق ذاته، stands for the number of simulations for the node considered after the -th move

من جانب آخر، تكمن الصعوبة الرئيسية في اختيار العقد الفرعية في الحفاظ على بعض التوازن بين استغلال المتغيرات العميقة بعد التحركات ذات معدل الفوز المتوسط المرتفع واستكشاف التحركات ذات المحاكاة القليلة. تم تقديم الصيغة الأولى لموازنة الاستغلال والاستكشاف في الألعاب، والتي تسمى UCT ( الحد الأعلى للثقة 1 المطبق على الأشجار )، بواسطة Levente Kocsis وCsaba Szepesvári . يعتمد UCT على صيغة UCB1 المستمدة من Auer و Cesa-Bianchi و Fischer وخوارزمية AMS (العينة متعددة المراحل التكيفية) المتقاربة على الأرجح والتي تم تطبيقها لأول مرة على نماذج صنع القرار متعددة المراحل (على وجه التحديد، عمليات اتخاذ القرار ماركوف ) بواسطة Chang و Fu و Hu و Marcus. يوصي Kocsis و Szepesvári باختيار الحركة التي سيتم التعبير عنها في كل عقدة من شجرة اللعبة لها أعلى قيمة. في هذه الصيغة:

البحث عن لعبة مونت كارلو النقية

وفي السياق ذاته، يمكن تطبيق هذا الإجراء الأساسي على أي لعبة حيث تحتوي مواقفها بالضرورة على عدد محدود من التحركات وطول محدود. بالنسبة لكل موقف، تُحدد كامل التحركات الممكنة: تُلعب k لعبة عشوائية حتى النهاية، وتسجل النتائج. تُختار الحركة المؤدية إلى أفضل نتيجة. تُكسر العلاقات عن طريق رمي العملة العادلة . تؤدي نتائج البحث في لعبة Monte Carlo الصرفة إلى لعب قوي في الكثير من الألعاب التي تحتوي على عناصر عشوائية، كما هو الحال في لعبة EinStein würfelt nicht! . يتقارب هذا مع اللعب الأمثل (حيث يميل k إلى اللانهاية) في ألعاب ملء اللوحة بترتيب أدوار عشوائي، مثلًا في لعبة Hex بترتيب أدوار عشوائي. يستبدل ألفازيرو من DeepMind خطوة المحاكاة بتقييم يعتمد على الشبكة العصبية.

التحسينات

في هذا الإطار، عند استخدام RAVE، تحدد خطوة التحديد العقدة التي سيتم تطبيق صيغة UCB1 المعدلة عليها لها أعلى قيمة. في هذه الصيغة، و يمثل عدد مرات اللعب الفائزة التي تحتوي على الحركة وعدد جميع مرات اللعب التي تحتوي على الحركة ، و يجب أن تكون الدالة قريبة من واحد ومن الصفر بالنسبة و n i الصغيرة نسبيًا والكبيرة نسبيًا ، على التوالى. واحدة من الكثير من الصيغ ل ، الذي اقترحه د. سيلفر، يقول أنه في المواقف المتوازنة يمكن للمرء أن يتخذ حيث هو ثابت تم اختياره تجريبيا.

ومن جهة أخرى، التوازي الورقي ، أي التنفيذ المتوازي للعديد من عمليات التشغيل من ورقة واحدة من شجرة اللعبة.

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

وعلى صعيد آخر، تجمع شجرة مونت كارلو الأساسية معلومات كافية للعثور على التحركات الأكثر إيجابية فقط بعد عدة جولات؛ وحتى ذلك الحين تكون تحركاتها عشوائية بشكل أساسي. قد يتم تقليص مرحلة الاستكشاف هذه إلى حدّ كبير في فئة معينة من الألعاب التي تستعمل RAVE ( تقدير قيمة العمل السريع ). في هذه الألعاب، تؤدي تبديلات تسلسل الحركات إلى نفس الموضع. عادةً ما تكون هذه ألعابًا لوحية تتضمن الحركة فيها وضع قطعة أو حجر على اللوحة. في مثل هذه الألعاب، غالبًا ما تتأثر قيمة كل حركة بالحركات الأخرى بشكل طفيف فقط.

وفي هذا الصدد، يمكن تنفيذ بحث شجرة مونت كارلو في وقت واحد بواسطة الكثير من الخيوط أو العمليات . هناك عدة طرق مختلفة جوهريًا لتنفيذها بالتوازي :

كذلك، التوازي الشجري ، أي البناء المتوازي لنفس شجرة اللعبة، وحماية البيانات من عمليات الكتابة المتزامنة إما باستخدام متزامن عالمي واحد، أو مع المزيد من المتزامنات، أو باستخدام المزامنة غير الحظرية .

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

وفي هذا الصدد، التوازي الجذري ، أي بناء أشجار ألعاب مستقلة بالتوازي والقيام بالحركة بناءً على فروع مستوى الجذر لجميع هذه الأشجار.

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

في هذا الإطار، تحتاج الأساليب المستعملة في البحث الشجري إستعمال طريقة مونت كارلو في كثير من الأحيان الكثير من المعلمات. توجد طرق آلية لضبط المعلمات لتحقيق أقصى قدر من معدل الفوز.

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

مبدأ التشغيل

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

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

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

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

إضافةً إلى ذلك، إذا خسر الأبيض المحاكاة، فإن جميع العقد على طول التحديد تزيد من عدد المحاكاة الخاصة بها (المقام)، ولكن من بينها فقط العقد السوداء هي التي تم احتساب انتصاراتها (البسط). إذا فاز الأبيض بدلاً من ذلك، فإن جميع العقد على طول التحديد ستظل تزيد من عدد المحاكاة الخاصة بها، ولكن من بينها فقط العقد البيضاء هي التي ستُحسب لها انتصارات. في الألعاب التي يكون فيها التعادل ممكنًا، يؤدي التعادل إلى زيادة البسط لكل من الأسود والأبيض بمقدار 0.5 والمقام بمقدار 1. ويضمن هذا أنه أثناء الاختيار، تتوسع خيارات كل لاعب نحو التحركات الأكثر إيجابية بالنسبة لهذا اللاعب، وهو ما يعكس هدف كل لاعب في تعظيم قيمة تحركه.

ومن جهة أخرى، الطريقة الأساسية لاستخدام اللعبات هي تطبيق نفس عدد اللعبات بعد كل حركة قانونية للاعب الحالي، ثم اختيار الحركة التي أدت إلى أكبر عدد من الانتصارات. غالبًا ما تزداد كفاءة هذه الطريقة - والتي تسمى Pure Monte Carlo Game Search - مع الوقت حيث يتحدد المزيد من عمليات التشغيل للحركات التي أدت بشكل متكرر إلى انتصار اللاعب الحالي بحسب عمليات التشغيل السابقة. تتكون كل جولة من البحث في شجرة مونت كارلو من أربع خطوات:

كذلك، يوضح هذا الرسم البياني الخطوات المتبعة في اتخاذ قرار واحد، حيث يوضح كل عقدة نسبة الانتصارات إلى إجمالي مرات اللعب من تلك النقطة في شجرة اللعبة للاعب الذي تمثله العقدة. في مخطط الاختيار، اللون الأسود على وشك التحرك. تظهر العقدة الجذرية أن هناك 11 فوزًا من أصل 21 مباراة للأبيض من هذا الموقف حتى الآن. وهو يكمل إجمالي 10/21 انتصارات سوداء تظهر على طول العقد السوداء الثلاث الموجودة أسفله، حيث يمثل كل منها حركة سوداء محتملة. لاحظ أن هذا الرسم البياني لا يتبع خوارزمية UCT الموضحة أدناه.

ومن ناحية أخرى، تتكرر جولات البحث طالما بقي الوقت المخصص للخطوة. ثم يتم اختيار الحركة التي تحتوي على أكبر عدد من المحاكاة (أي أعلى مقام) باعتبارها الإجابة النهائية.

إضافةً إلى ذلك، الانتشار العكسي : استعمل نتيجة التشغيل لتحديث المعلومات في العقد الموجودة على المسار من إلى

الإيجابيات والسلبيات

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

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

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

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

طريقة مونت كارلو

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

وفي هذا الصدد، في 2006، مستوحى من سابقاتها، وصف ريمي كولوم تطبيق طريقة مونت كارلو على البحث في شجرة اللعبة وابتكر اسم البحث في شجرة مونت كارلو، L. Kocsis وCs. قام Szepesvári بتطوير خوارزمية UCT (حدود الثقة العليا المطبقة على الأشجار)، وقام S. Gelly وآخرون بتنفيذ UCT في برنامجهم MoGo. في سنة 2008، حقق فريق MoGo مستوى دان (الماجستير) في لعبة 9×9 جو، وبدأ برنامج Fuego في الفوز ضد لاعبين هواة أقوياء في لعبة 9×9 جو.

ومن ناحية أخرى، في يناير 2012، فاز برنامج زين بنتيجة 3:1 في مباراة غو على لوحة 19×19 مع لاعب هاوٍ من مستوى 2 دان . طورت شركة ديب مايند برنامج ألفا غو ، والذي أصبح في أكتوبر 2015 أول برنامج غو حاسوبي يتغلب على لاعب غو بشري محترف دون أي إعاقات على لوحة بحجم 19 × 19. في مارس 2016، حصل ألفا غو على مستوى فخري 9 دان (ماجستير) في لعبة 19×19 غو بعد هزيمته لـ لي سيدرول في مباراة مكونة من خمس مباريات بنتيجة نهائية أربع مباريات مقابل مباراة واحدة. يمثل ألفا غو تحسنًا كبيرًا مقارنة ببرامج غو السابقة فضلًا عن كونه علامة فارقة في التعلم الآلي لأنه يستعمل بحث شجرة مونت كارلو مع الشبكات العصبية الاصطناعية (طريقة التعلم العميق ) للسياسة (اختيار الحركة) والقيمة، مما يمنحه كفاءة تتجاوز البرامج السابقة بكثير.

ومن جهة أخرى، في عام 1992، استعملها ب. بروجمان لأول مرة في برنامج لعب غو . في سنة 2002، اقترح تشانج وآخرون فكرة "الطرح المتكرر والتتبع العكسي" مع خيارات أخذ العينات "التكيفية" في خوارزمية أخذ العينات متعددة المراحل التكيفية (AMS) لنموذج عمليات اتخاذ القرار ماركوف . كان AMS أول عمل يستكشف فكرة الاستكشاف والاستغلال القائم على UCB في بناء الأشجار المأخوذة من العينات/المحاكاة (مونت كارلو) وكان البذرة الرئيسية لأشجار الثقة العليا (UCT).

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

من جانب آخر، تم لاحقًا استكشاف مثل هذه الأساليب وتطبيقها بنجاح على البحث الاستدلالي في مجال إثبات النظريات الآلية بواسطة W. Ertel و J. Schumann و C. Suttner في عام 1989، وبالتالي تحسين أوقات البحث الأسيّة لخوارزميات البحث غير المستنيرة مثل البحث بالعرض أولاً، أو البحث بالعمق أولاً أو التعميق التكراري .

في هذا الإطار، استخدامت خوارزمية الMCTS كذلك في البرامج التي تلعب ألعاب لوحية أخرى (مثلًا Hex ، Havannah ، Game of the Amazons ، و أريما )، وألعاب الفيديو في الوقت الفعلي (مثلًا Ms. Pac-Man و فيبل ليجيندز )، والألعاب غير الحتمية (مثل skat ، بوكر ، ماجيك: ذا غاثرينغ ، أو Settlers of Catan ).

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.