MCTS

مقدمة عن Monte Carlo Tree Search (MCTS) :

تُعتبر ال (Monte Carlo Tree Search) من أقوى Algorithms في الذكاء الاصطناعي، خاصة في الألعاب . زي الشطرنج، جو (Go)، والألعاب الاستراتيجية الأخرى. ال Algorithm ده بيعتمد على الدمج بين statistical approaches مع Tree Search، وده بيجعلها فعّالة في اتخاذ القرارات في بيئات معقدة وغير مؤكدة.

في هذه المقالة، هنعرف كيفية عمل ال Algorithm، مكوناته الرئيسية، وتطبيقه العملي مع مثال برمجي مبسط.

الفكرة العامة لـ MCTS

تعتمد خوارزمية MCTS على بناء شجرة تمثّل الحركات الممكنة في اللعبة أو القرارات في المشكلة قيد الدراسة. بدلاً من استكشاف الشجرة بالكامل كما يحدث في ال algorithms التقليدية زي (MiniMax)، تستخدم MCTS تقنيات Sampling لاختيار المسارات الأكثر واعدًا.

وتتألف الخوارزمية من أربع خطوات رئيسية:

1.الاختيار(Selection) :

• بيبدأ الalgorithm من ال Root وتنتقل خلال الشجرة لاختيار العقدة التي بتحتاج لمزيد من الاستكشاف.
• يتم ذلك باستخدام استراتيجيات زي UCT (Upper Confidence Bound for Trees) الي بتحقق توازنًا بين الExploration وال Exploitation

2.التوسّع (Expansion) :

• ⦁ بمجرد الوصول إلى العقدة المناسبة، بتُضاف عقدة جديدة زي خطوة جديدة أو حركة ممكنة في المشكلة.

3.المحاكاة (Expansion) :

• ال algorithm بتُجري محاكاة عشوائية من العقدة الجديدة حتى تصل إلى نهاية اللعبة أو نقطة قرار نهائية.
• يتم استخدام نتائج المحاكاة لتقييم جودة هذه العقدة

4.الارتداد(Backpropagation) :

⦁ يتم تحديث القيم في الشجرة من العقدة المضافة حديثًا وحتى الجذر، بناءً على نتائج المحاكاة

مميزات MCTS

⦁ توازن بين الExploration وال Exploitation : بيتيح للalgorithm استكشاف الخيارات غير المعروفة وفي نفس الوقت الاستفادة من الخيارات الواعدة.
⦁ مرونة: يمكن استخدامها في مشاكل ذات نطاق كبير بدون الحاجة إلى تقييم دقيق لكل خطوة.
⦁ كفاءة: فعّالة في الألعاب التي تكون فيها قواعد التقييم معقدة أو غير واضحة.

مثال برمجي باستخدام Python

1.تعريف العقدة (Node)

شرح:

1. العقدة (Node) هي العنصر الأساسي في شجرة البحث.
2. تحتوي على معلومات عن:
   • الحالة المرتبطة بها.
   • العقدة الأب (Parent) التي تشير إليها.
   • العقد الفرعية (Children) التي يتم توسيعها من هذه العقدة.
   • عدد المرات التي تمت زيارة العقدة.
   • القيمة المحققة لهذه العقدة.

2.التحقق من التوسع الكامل واختيار أفضل عقدة
التوسع الكامل:

• الوظيفة: تتحقق مما إذا كانت كل الحركات الممكنة قد تم توسيعها لهذه العقدة.
• الاستخدام: يُستخدم هذا التحقق قبل القيام بخطوة التوسع (Expansion).

اختيار أفضل عقدة:

الوظيفة: تختار أفضل عقدة بناءً على التوازن بين الاستغلال والاستكشاف:

⦁ الاستغلال (Exploit) يتمثل في القيمة المتوسطة للعقدة (عدد الانتصارات / عدد الزيارات).
⦁ الاستكشاف (Explore) يحفّز استكشاف العقد التي تم زيارتها عدد مرات أقل.

3.تمثيل الحالة State

شرح:

• الحالة (State) :هي تمثيل لحالة اللعبة في أي نقطة زمنية.
• الدوال المهمة:
  • get_possible_moves: تُرجع قائمة الحركات الممكنة من هذه الحالة.
  • perform_move : تُنفذ حركة معينة وتُرجع حالة جديدة.
  • is_terminal :تتحقق إذا كانت اللعبة قد انتهت (فوز/تعادل/خسارة).
  • get_reward : تُحدد المكافأة النهائية للحالة (قيم مثل 1 للفوز، -1 للخسارة، 0 للتعادل).
    

4.MCTS
الخوارزمية الرئيسية:

شرح الخطوات:

• اختيار (Selection):
  • تبدأ من الجذر وتنتقل عبر الشجرة لاختيار العقدة الأكثر واعدًا باستخدام best_child
• توسّع (Expansion):
  • عند الوصول إلى عقدة تحتاج إلى التوسع، تُضاف عقدة جديدة لكل حركة ممكنة.
• محاكاة (Simulation):
  • من العقدة الجديدة، يتم تنفيذ محاكاة عشوائية حتى الوصول إلى حالة نهائية.
• ارتداد (Backpropagation):
  • يتم تحديث العقدة الحالية وكل أسلافها بناءً على نتيجة المحاكاة (القيمة + عدد الزيارات).

5. المحاكاة العشوائية

شرح:

⦁ تُنفذ محاكاة عشوائية للحركات من العقدة المحددة حتى تصل إلى نهاية اللعبة.
⦁ يتم إرجاع المكافأة النهائية بناءً على النتيجة.

تطبيق MCTS على لعبة (Tic Tac Toe):

شرح:

⦁ يتم تعريف حالة اللعبة (Tic Tac Toe) بطرق محددة.
⦁ يتم استخدام خوارزمية MCTS لتحديد أفضل حركة من الحالة الأولية.

الكود يمثل مثالًا عامًا ل (Monte Carlo Tree Search)

يمكن تعديل الكود ليتناسب مع ألعاب أو مشاكل أخرى عن طريق تحديد:
⦁ كيفية تمثيل الحالة (State)
⦁ قواعد اللعبة (get_possible_moves, perform_move)
⦁ تقييم المكافأة (get_reward)

التطبيقات العملية:

تُستخدم MCTS في العديد من المجالات:
⦁ الألعاب الاستراتيجية: مثل Go، حيث تُستخدم لتحليل ملايين الحركات.
⦁ التخطيط: في الروبوتات أو اتخاذ قرارات معقدة.
⦁ حل المشاكل الغامضة: مثل تحسين الشبكات أو التنبؤ.

الخاتمة:

تُعتبر ال Monte Carlo Tree Search نقلة نوعية في الذكاء الاصطناعي. الجمع بين التحليل الإحصائي واستراتيجيات البحث يجعلها أداة قوية لحل المشاكل ذات الطبيعة غير المحددة. إذا كنت مهتمًا بتطوير ألعاب أو حل مشاكل معقدة، فإن MCTS هي تقنية يجب أن تتعلمها.