mcts

البرنامج التعليمي لخوارزمية Monte Carlo Tree Search (MCTS) باستخدام كود Python. تطبيق MCTS لإنشاء الذكاء الاصطناعي للعبة بسيطة.

سنشرح في هذا البرنامج التعليمي خوارزمية Monte Carlo Tree Search وكل جزء من الكود. قمنا مؤخرًا بتطبيق MCTS لتطوير لعبتنا.

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

هذا هو رابط متجر الألعاب للعبة: Sudo Tic Tac Toe.

قواعد لعبتنا (الوضع 1) هي كما يلي:

1. يتم لعب اللعبة على شبكة 9 × 9 مثل سودوكو.
2. هذه الشبكة الكبيرة 9 × 9 مقسمة إلى 9 شبكات أصغر 3 × 3 (لوحة محلية).
3. الهدف من اللعبة هو الفوز بأي لوحة محلية واحدة من الـ 9 المتاحة.
4. تحدد حركتك أي لوحة محلية يجب على الذكاء الاصطناعي أن يتحرك فيها، والعكس صحيح.
5. على سبيل المثال، قمت بإجراء حركة في الموضع 1 من اللوحة المحلية رقم 5. وهذا سيجبر الذكاء الاصطناعي على القيام بخطوة في اللوحة المحلية رقم 1.
6. يتم تطبيق قواعد تيك تاك تو العادية على اللوحة المحلية.

لماذا ام سي تي اس؟

كما كنت قد رأيت هذه اللعبة لديها عامل تفرع عالي جدًا. بالنسبة للخطوة الأولى، تكون اللوحة بأكملها فارغة. إذن هناك 81 نقطة فارغة. للدورة الأولى لديها 81 حركة محتملة. للدورة الثانية من خلال تطبيق القاعدة 4 لديها 8 أو 9 حركات محتملة.

بالنسبة لأول حركتين، ينتج عن ذلك 81*9 = 729 مجموعة محتملة. وبالتالي فإن عدد المجموعات الممكنة يزداد مع تقدم اللعبة، مما يؤدي إلى ارتفاع عامل التفرع. بالنسبة لكلا الوضعين في لعبتنا، يكون عامل التفرع مرتفعًا جدًا. بالنسبة للألعاب ذات عامل التفرع العالي، ليس من الممكن تطبيق خوارزمية الحد الأدنى. تعمل خوارزمية MCTS مع هذا النوع من الألعاب.

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

نعرض أدناه رمز MCTS في بايثون. نحتاج أولاً إلى استيراد numpy و defaultdict.

 import numpy as np
from collections import defaultdict

حدد فئة MCTS كما هو موضح أدناه.

 class MonteCarloTreeSearchNode ():
    def __init__ ( self , state , parent = None , parent_action = None ):
        self . state = state
        self . parent = parent
        self . parent_action = parent_action
        self . children = []
        self . _number_of_visits = 0
        self . _results = defaultdict ( int )
        self . _results [ 1 ] = 0
        self . _results [ - 1 ] = 0
        self . _untried_actions = None
        self . _untried_actions = self . untried_actions ()
        return

يتم استخدام المنشئ لتهيئة المتغيرات التالية.

• الحالة : بالنسبة للعبتنا فهي تمثل حالة اللوحة. بشكل عام، يتم تمثيل حالة اللوحة بواسطة مصفوفة. بالنسبة لـ Tic Tac Toe العادي، فهو عبارة عن مصفوفة 3 × 3.
• الأصل : لا يوجد بالنسبة للعقدة الجذرية وبالنسبة للعقد الأخرى فهو يساوي العقدة المشتقة منها. بالنسبة للدورة الأولى كما رأيت من اللعبة، فهي لا شيء.
• الأطفال : يحتوي على جميع الإجراءات الممكنة من العقدة الحالية. للدورة الثانية في لعبتنا، هذه هي 9 أو 8 حسب المكان الذي تقوم فيه بحركتك.
• parent_action : لا شيء بالنسبة للعقدة الجذرية وبالنسبة للعقد الأخرى فهو يساوي الإجراء الذي نفذته العقدة الأم.
• _number_of_visits : عدد مرات زيارة العقدة الحالية
• النتائج : إنه قاموس
• _untried_actions : يمثل قائمة بجميع الإجراءات الممكنة
• الإجراء : التحرك الذي يجب تنفيذه.

تتكون الفئة من وظائف الأعضاء التالية. جميع الوظائف أدناه هي وظيفة عضو باستثناء الوظيفة الرئيسية ().

 def untried_actions ( self ):

    self . _untried_actions = self . state . get_legal_actions ()
    return self . _untried_actions

إرجاع قائمة الإجراءات التي لم تتم تجربتها من حالة معينة. في الجولة الأولى من لعبتنا هناك 81 إجراءً محتملاً. للجولة الثانية تكون 8 أو 9. وهذا يختلف في لعبتنا.

 def q ( self ):
    wins = self . _results [ 1 ]
    loses = self . _results [ - 1 ]
    return wins - loses

إرجاع الفرق بين الانتصارات والخسائر

 def n ( self ):
    return self . _number_of_visits

إرجاع عدد مرات زيارة كل عقدة.

 def expand ( self ):
	
    action = self . _untried_actions . pop ()
    next_state = self . state . move ( action )
    child_node = MonteCarloTreeSearchNode (
		next_state , parent = self , parent_action = action )

    self . children . append ( child_node )
    return child_node 

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

 def is_terminal_node ( self ):
    return self . state . is_game_over ()

يُستخدم هذا للتحقق مما إذا كانت العقدة الحالية طرفية أم لا. يتم الوصول إلى العقدة الطرفية عند انتهاء اللعبة.

 def rollout ( self ):
    current_rollout_state = self . state
    
    while not current_rollout_state . is_game_over ():
        
        possible_moves = current_rollout_state . get_legal_actions ()
        
        action = self . rollout_policy ( possible_moves )
        current_rollout_state = current_rollout_state . move ( action )
    return current_rollout_state . game_result ()

من الحالة الحالية، تتم محاكاة اللعبة بأكملها حتى تكون هناك نتيجة للعبة. يتم إرجاع هذه النتيجة من اللعبة. على سبيل المثال، إذا أدى الأمر إلى فوز، تكون النتيجة 1. وإلا ستكون -1 إذا أدى إلى خسارة. ويكون 0 إذا كان التعادل. إذا تمت محاكاة اللعبة بأكملها بشكل عشوائي، أي أنه عند كل دور يتم تحديد الحركة بشكل عشوائي من بين مجموعة من الحركات المحتملة، ويسمى ذلك اللعب الخفيف.

 def backpropagate ( self , result ):
    self . _number_of_visits += 1.
    self . _results [ result ] += 1.
    if self . parent :
        self . parent . backpropagate ( result )

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

 def is_fully_expanded ( self ):
    return len ( self . _untried_actions ) == 0

يتم إخراج جميع الإجراءات من _untried_actions واحدًا تلو الآخر. وعندما يصبح فارغًا، أي عندما يكون الحجم صفرًا، يتم توسيعه بالكامل.

 def best_child ( self , c_param = 0.1 ):
    
    choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
    return self . children [ np . argmax ( choices_weights )]

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

 def rollout_policy ( self , possible_moves ):
    
    return possible_moves [ np . random . randint ( len ( possible_moves ))]

يختار بشكل عشوائي خطوة للخروج من التحركات المحتملة. هذا مثال على التشغيل العشوائي.

 def _tree_policy ( self ):

    current_node = self
    while not current_node . is_terminal_node ():
        
        if not current_node . is_fully_expanded ():
            return current_node . expand ()
        else :
            current_node = current_node . best_child ()
    return current_node

تحديد العقدة لتشغيل الطرح.

 def best_action ( self ):
    simulation_no = 100
	
	
    for i in range ( simulation_no ):
		
        v = self . _tree_policy ()
        reward = v . rollout ()
        v . backpropagate ( reward )
	
    return self . best_child ( c_param = 0. )

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

 def get_legal_actions ( self ): 
    '''
    Modify according to your game or
    needs. Constructs a list of all
    possible states from current state.
    Returns a list.
    ''' 

 def is_game_over ( self ):
    '''
    Modify according to your game or 
    needs. It is the game over condition
    and depends on your game. Returns
    true or false
    ''' 

 def game_result ( self ):
    '''
    Modify according to your game or 
    needs. Returns 1 or 0 or -1 depending
    on your state corresponding to win,
    tie or a loss.
    ''' 

 def move ( self , action ):
    '''
    Modify according to your game or 
    needs. Changes the state of your 
    board with a new value. For a normal
    Tic Tac Toe game, it can be a 3 by 3
    array with all the elements of array
    being 0 initially. 0 means the board 
    position is empty. If you place x in
    row 2 column 3, then it would be some 
    thing like board[2][3] = 1, where 1
    represents that x is placed. Returns 
    the new state after making a move.
    ''' 

 def main ():
    root = MonteCarloTreeSearchNode ( state , None , action )
    selected_node = root . best_action ()
    return 

هذه هي الوظيفة الرئيسية (). قم بتهيئة العقدة الجذرية واستدعاء الدالة best_action للحصول على أفضل عقدة. هذه ليست وظيفة عضو في الفصل. جميع الوظائف الأخرى هي وظيفة عضو في الفصل.

تتكون MCTS من 4 خطوات:

اختيار

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

	wi/ni + c*sqrt(t)/ni

wi = عدد مرات الفوز بعد النقلة i
ni = عدد عمليات المحاكاة بعد الحركة i
ج = معلمة الاستكشاف (تساوي نظريًا √2)
t = إجمالي عدد عمليات المحاكاة للعقدة الأصلية

توسع:

عندما لم يعد بإمكانه تطبيق UCT للعثور على العقدة اللاحقة، فإنه يقوم بتوسيع شجرة اللعبة عن طريق إلحاق جميع الحالات الممكنة من العقدة الطرفية.

محاكاة:

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

الانتشار العكسي:

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

تصميم لعبتك:

إذا كنت تخطط لإنشاء لعبتك الخاصة، فسيتعين عليك التفكير في الأسئلة التالية.

1. كيف ستمثل حالة لعبتك؟ فكر في الحالة الأولية في لعبتنا.
2. ماذا ستكون حالة اللعبة النهائية للعبتك؟ قارنها بحالة نهاية اللعبة في لعبتنا.
3. كيف ستحصل على الإجراءات القانونية في لعبتك؟ حاول الحصول على الإجراءات القانونية للخطوة الأولى في لعبتنا.

سودو تيك تاك تو

إذا كان لديك أي أسئلة أو اقتراحات، فلا تتردد في الاتصال بنا على [email protected]