بحث شجرة مونتي كارلو: الخوارزمية وراء AlphaGo

الخطوات الأربع

1. الاختيار

اجتَز الشجرة من الجذر، مختاراً الأبناء باستخدام UCB1:

UCB1 = win_rate + C * sqrt(ln(parent_visits) / node_visits)

C هو ثابت الاستكشاف (عادةً √2).

2. التوسّع

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

3. المحاكاة (Rollout)

العب حركات عشوائية حتى انتهاء اللعبة. أعِد فوز/خسارة/تعادل.

4. النشر الخلفي

حدّث عدّادات الفوز والزيارات وصولاً إلى الجذر.

التنفيذ للعبة 2048

class MCTSNode:
    def __init__(self, state, parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action
        self.children = []
        self.wins = 0
        self.visits = 0
    
    @property
    def ucb1(self):
        if self.visits == 0: return float('inf')
        return self.wins/self.visits + 1.414*np.sqrt(np.log(self.parent.visits)/self.visits)