شرح تفصيلي لمعادلة PUCT

في المقال السابق، استعرضنا دمج MCTS مع الشبكات العصبية. الآن، دعونا نتعمق في جوهر مرحلة الاختيار في MCTS — معادلة PUCT.

هذه المعادلة تبدو بسيطة، لكنها من مفاتيح نجاح AlphaGo. إنها توازن بأناقة بين هدفين يبدوان متناقضين: "استغلال الحركات الجيدة المعروفة" و"استكشاف الحركات التي قد تكون أفضل".

---

معادلة PUCT

تعريف المعادلة

معادلة PUCT (Predictor Upper Confidence Trees) المستخدمة في AlphaGo:

$a^* = \arg\max_a \left[ Q(s,a) + U(s,a) \right]$

حيث:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$

التوسيع الكامل:

$a^* = \arg\max_a \left[ Q(s,a) + c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$

شرح الرموز

الرمز	المعنى	المصدر
$Q(s,a)$	متوسط قيمة الإجراء $a$	إحصائيات MCTS
$P(s,a)$	الاحتمالية المسبقة للإجراء $a$	Policy Network
$N(s)$	عدد زيارات العقدة الأب	إحصائيات MCTS
$N(s,a)$	عدد زيارات العقدة الابن	إحصائيات MCTS
$c_{\text{puct}}$	ثابت الاستكشاف	معامل فائق

الفهم الحدسي

معادلة PUCT يمكن تقسيمها إلى جزئين:

الدرجة الكلية = Q(s,a)        + U(s,a)
               ↓              ↓
             عنصر الاستغلال    عنصر الاستكشاف
           "ما مدى جودة هذه الحركة؟"   "هل تستحق مزيداً من الاستكشاف؟"

عنصر الاستغلال Q(s,a):

• الأداء المتوسط السابق لهذه الحركة
• كلما زادت الزيارات، زادت دقة التقدير
• يشجع على اختيار الحركات "المعروفة بأنها جيدة"

عنصر الاستكشاف U(s,a):

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

---

معنى كل عنصر

Q(s,a): متوسط القيمة

$Q(s,a)$ هو متوسط نتائج جميع المحاكاات من العقدة $(s,a)$:

$Q(s,a) = \frac{W(s,a)}{N(s,a)} = \frac{\sum_i z_i}{N(s,a)}$

حيث $z_i \in \{-1, +1\}$ هي نتيجة المحاكاة $i$.

الخصائص:

• النطاق: $[-1, +1]$
• القيمة الأولية: غير محددة (تحتاج زيارة واحدة على الأقل)
• تستقر مع زيادة عدد الزيارات

التفسير:

• $Q = 0.6$: نسبة فوز هذه الحركة حوالي 80% (لأن $Q = 2 \times \text{نسبة الفوز} - 1$)
• $Q = 0$: تعادل الفوز والخسارة
• $Q = -0.3$: نسبة فوز هذه الحركة حوالي 35%

P(s,a): الاحتمالية المسبقة

$P(s,a)$ تأتي من إخراج Policy Network:

$P(s,a) = \pi_\theta(a|s)$

الخصائص:

• النطاق: $[0, 1]$، و $\sum_a P(s,a) = 1$
• تُحسب عند أول توسيع للعقدة
• تعكس حكم الشبكة العصبية على "مدى جودة هذه الحركة"

الدور:

• الإجراءات ذات الاحتمالية العالية تُستكشف أولاً
• حتى لو كان عدد الزيارات 0، هناك دافع للاستكشاف
• توجه البحث للتركيز على الحركات "التي تبدو منطقية"

N(s) و N(s,a): عدد الزيارات

$N(s)$ هو إجمالي عدد زيارات العقدة الأب:

$N(s) = \sum_a N(s,a)$

دور عنصر الاستكشاف:

$\frac{\sqrt{N(s)}}{1 + N(s,a)}$

سلوك هذا الكسر:

• عندما $N(s,a) = 0$، الدرجة = $\sqrt{N(s)}$ (أقصى دافع للاستكشاف)
• مع زيادة $N(s,a)$، الدرجة تنخفض
• عندما $N(s,a) \gg \sqrt{N(s)}$، الدرجة تقترب من 0

هذا يضمن:

1. كل إجراء يُستكشف مرة واحدة على الأقل (إذا كان $P(s,a) > 0$)
2. دافع الاستكشاف يتناقص مع الزيارات
3. الاختيار النهائي تهيمن عليه قيمة $Q$

c_puct: ثابت الاستكشاف

$c_{\text{puct}}$ يتحكم في التوازن بين الاستكشاف والاستغلال:

قيمة $c_{\text{puct}}$	التأثير
صغيرة (مثل 0.5)	ميل أكثر للاستغلال، تركيز سريع على الحركات الجيدة
متوسطة (مثل 1-2)	توازن الاستكشاف والاستغلال
كبيرة (مثل 5)	ميل أكثر للاستكشاف، تجربة المزيد من الاحتمالات

القيمة المستخدمة في AlphaGo: $c_{\text{puct}} = 1.5$ (حسب الورقة البحثية).

---

العلاقة مع UCB1

مراجعة معادلة UCB1

معادلة UCB1 المستخدمة في MCTS التقليدي:

$\text{UCB1}(s,a) = \bar{X}_{s,a} + c \sqrt{\frac{\ln N(s)}{N(s,a)}}$

حيث $\bar{X}_{s,a}$ هو متوسط العائد.

المقارنة

الجانب	UCB1	PUCT
عنصر الاستغلال	$\bar{X}_{s,a}$ (متوسط العائد)	$Q(s,a)$ (متوسط القيمة)
عنصر الاستكشاف	$\sqrt{\frac{\ln N}{n}}$ (حدود الثقة)	$P \cdot \frac{\sqrt{N}}{1+n}$ (إرشاد مسبق)
معلومات مسبقة	لا يوجد	يستخدم Policy Network
تناقص الاستكشاف	تناقص لوغاريتمي	تناقص خطي

مزايا PUCT

1. استخدام المعرفة المسبقة: $P(s,a)$ من Policy Network تجعل البحث يركز من البداية على الحركات المنطقية

2. تقارب أسرع: التناقص الخطي ($1/(1+n)$) أسرع من التناقص اللوغاريتمي ($1/\sqrt{\ln N / n}$) في تركيز البحث

3. استكشاف قابل للتحكم: $P(s,a)$ و $c_{\text{puct}}$ توفران وسائل أكثر للتحكم في الاستكشاف

الخلفية النظرية

UCB1 لها ضمانات نظرية صارمة (حدود الندم)، لكن هذه الضمانات تفترض:

• كل ذراع (إجراء) مستقل
• لا توجد معلومات مسبقة

في الغو، لدينا معرفة مسبقة قوية (Policy Network)، وPUCT تستطيع استغلال هذه المعلومات بشكل أفضل.

---

الاشتقاق الرياضي

بدءاً من مشكلة اللصوص متعددي الأذرع

إلهام PUCT يأتي من مشكلة اللصوص متعددي الأذرع (Multi-Armed Bandit).

تخيل أن أمامك $K$ ماكينة قمار، كل واحدة لها احتمالية فوز مختلفة لكن غير معروفة. هدفك هو تعظيم إجمالي عدد الفوز. الاستراتيجية هي:

• الاستغلال: سحب الماكينة التي تبدو الأفضل
• الاستكشاف: تجربة ماكينات أخرى، قد تجد أفضل

UCB1 هو الحل الكلاسيكي لهذه المشكلة، وPUCT هي تنويعة منها.

الأساس النظري لـ UCB

للمتغير العشوائي $X$، من متراجحة هوفدينج:

$P(|\bar{X}_n - \mu| \geq \epsilon) \leq 2 \exp(-2n\epsilon^2)$

إذا أردنا الخطأ باحتمال $1/t^4$، نحتاج:

$\epsilon = \sqrt{\frac{2 \ln t}{n}}$

هذا هو مصدر عنصر الاستكشاف في UCB1.

تعديلات PUCT

PUCT تجري عدة تعديلات على UCB الكلاسيكي:

1. إضافة الاحتمالية المسبقة

$U(s,a) \propto P(s,a) \cdot (\text{عنصر الاستكشاف})$

هذا يركز الاستكشاف على الإجراءات ذات الاحتمالية العالية.

2. تغيير شكل عنصر الاستكشاف

من $\sqrt{\frac{\ln N}{n}}$ إلى $\frac{\sqrt{N}}{1+n}$

هذا يسرّع التقارب:

المقارنة (بفرض N = 1000, n = 10):

UCB1:  sqrt(ln(1000) / 10) = sqrt(0.69) ≈ 0.83
PUCT:  sqrt(1000) / 11 ≈ 2.87

PUCT تعطي مكافأة استكشاف أكثر، لكنها تتناقص أسرع

3. معرفة مسبقة قابلة للتعلم

$P(s,a)$ تأتي من الشبكة العصبية، وتتحسن مع التدريب. هذا يجعل MCTS والشبكة العصبية تشكلان دورة إيجابية.

لماذا هذا الشكل فعال؟

التفسير الحدسي:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$

1. $P(s,a)$: "الخبير يقول هذه الحركة بهذا المستوى من الجودة"
2. $\sqrt{N(s)}$: "كم نعرف عن هذا الوضع"
3. $1/(1 + N(s,a))$: "كم نعرف عن هذه الحركة"

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

---

الفهم البصري

تغير عنصر الاستكشاف

دعونا نتصور كيف يتغير عنصر الاستكشاف مع عدد الزيارات:

U(s,a) = c_puct × P(s,a) × √N(s) / (1 + N(s,a))

بفرض P(s,a) = 0.1, c_puct = 1.5, N(s) = 1600

N(s,a)  |  U(s,a)
--------|----------
   0    |  6.00      ← غير مزار، أقصى مكافأة استكشاف
   1    |  3.00
   5    |  1.00
  10    |  0.55
  50    |  0.12
 100    |  0.06
 400    |  0.015     ← بعد زيارات كثيرة، مكافأة الاستكشاف صغيرة جداً

تأثير الاحتماليات المسبقة المختلفة

بفرض c_puct = 1.5, N(s) = 1600, N(s,a) = 0

P(s,a)  |  U(s,a)
--------|----------
  0.30  |  18.00     ← الإجراءات ذات الاحتمالية العالية لها دافع استكشاف أكبر
  0.10  |   6.00
  0.03  |   1.80
  0.01  |   0.60
  0.001 |   0.06     ← الإجراءات ذات الاحتمالية المنخفضة تكاد لا تُستكشف

الاستكشاف التفاعلي

جرب ضبط معامل $c_{\text{puct}}$ أدناه، وراقب كيف يؤثر على اختيار MCTS:

載入中...

---

التنفيذ الفعلي في AlphaGo

تنفيذ AlphaGo Fan/Lee

النسخة الأصلية من AlphaGo تستخدم معادلة مختلفة قليلاً:

$U(s,a) = c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s,a)}$

وحساب $Q(s,a)$ يأخذ الخسارة الافتراضية بعين الاعتبار:

def get_ucb_score(node, action, c_puct=1.5):
    Q = node.W[action] / (node.N[action] + 1)  # تجنب القسمة على صفر
    P = node.prior[action]
    N_parent = sum(node.N.values())
    N_child = node.N[action]

    U = c_puct * P * math.sqrt(N_parent) / (1 + N_child)

    return Q + U

تنفيذ AlphaGo Zero

AlphaGo Zero يستخدم تنفيذاً أبسط:

def select_action(node, c_puct=1.5):
    """اختيار الإجراء ذي أعلى درجة PUCT"""
    N_parent = sum(node.visit_count.values())

    def puct_score(action):
        Q = node.value_sum[action] / (node.visit_count[action] + 1)
        P = node.prior[action]
        U = c_puct * P * math.sqrt(N_parent) / (1 + node.visit_count[action])
        return Q + U

    return max(node.legal_actions, key=puct_score)

معالجة العقد غير المزارة

عندما $N(s,a) = 0$، $Q(s,a)$ غير محدد. طرق المعالجة الشائعة:

الطريقة 1: استخدام قيمة العقدة الأب

Q = parent_value if N[action] == 0 else W[action] / N[action]

الطريقة 2: استخدام قيمة أولية

Q = 0 if N[action] == 0 else W[action] / N[action]

الطريقة 3: استخدام FPU (First Play Urgency)

# العقد غير المزارة تستخدم قيمة Q منخفضة
fpu_value = parent_Q - fpu_reduction
Q = fpu_value if N[action] == 0 else W[action] / N[action]

AlphaGo Zero يستخدم FPU، مما يجعل البحث يميل أكثر لتجربة العقد التي تمت زيارتها أولاً.

---

خبرة ضبط المعاملات العملية

اختيار c_puct

$c_{\text{puct}}$ هو أهم معامل فائق. مبادئ توجيهية عملية:

1. علاقتها بجودة الشبكة

• الشبكة قوية (دقة عالية): يمكن استخدام $c_{\text{puct}}$ أصغر
• الشبكة ضعيفة: تحتاج $c_{\text{puct}}$ أكبر لتصحيح الأخطاء

2. علاقتها بميزانية البحث

• عدد محاكاات كثير: يمكن استخدام $c_{\text{puct}}$ أكبر (وقت كافٍ للاستكشاف)
• عدد محاكاات قليل: استخدام $c_{\text{puct}}$ أصغر (تركيز سريع)

3. علاقتها بخصائص اللعبة

• الألعاب التكتيكية القوية: قد تحتاج استكشافاً أكثر
• الألعاب الاستراتيجية القوية: يمكن الوثوق أكثر بالمعرفة المسبقة

القيم النموذجية

المشروع	$c_{\text{puct}}$
AlphaGo	1.5
AlphaGo Zero	1.0 - 2.0
AlphaZero	1.25
KataGo	0.5 - 1.0 (ضبط ديناميكي)
Leela Zero	1.5 - 2.0

الضبط الديناميكي

بعض التنفيذات المتقدمة تستخدم $c_{\text{puct}}$ ديناميكي:

def dynamic_cpuct(visit_count):
    """ضبط ثابت الاستكشاف حسب عدد الزيارات"""
    base = 1.0
    init = 1.5
    log_base = 19652  # معامل الضبط

    return math.log((visit_count + log_base + 1) / log_base) + init

هذا يجعل البحث يميل للاستكشاف في البداية، وللاستغلال في النهاية.

تحليل الحساسية

تأثير $c_{\text{puct}}$ على قوة اللعب:

تجربة (ظروف أخرى ثابتة، تغيير c_puct):

c_puct | Elo النسبي
-------|----------
  0.5  |   -50     ← استغلال مفرط، تفويت حركات جيدة
  1.0  |   +20
  1.5  |    0      ← الأساس
  2.0  |   -10
  3.0  |   -30     ← استكشاف مفرط، إهدار البحث
  5.0  |   -80

القيمة المثلى عادةً بين 1.0-2.0، لكنها تعتمد على جودة الشبكة وميزانية البحث.

---

المتغيرات المتقدمة

متغيرات PUCT

1. PUCT متعددة الحدود (Polynomial PUCT / P-UCT)

$U(s,a) = c \cdot P(s,a) \cdot \frac{N(s)^\alpha}{1 + N(s,a)}$

حيث $\alpha$ معامل قابل للضبط (عادةً $\alpha = 0.5$).

2. PUCT مع الضوضاء

إضافة ضوضاء ديريكليه في العقدة الجذرية:

$P'(s,a) = (1-\varepsilon) P(s,a) + \varepsilon \cdot \eta_a$

حيث $\eta \sim \text{Dir}(\alpha)$. هذا يزيد تنوع الاستكشاف.

3. PUCT شبيهة بـ UCT

$U(s,a) = c \cdot P(s,a) \cdot \sqrt{\frac{\ln(1 + N(s) + c_{\text{base}})}{1 + N(s,a)}}$

هذه تجمع بين الشكل اللوغاريتمي لـ UCT والإرشاد المسبق لـ PUCT.

تحسينات KataGo

KataGo أجرت عدة تحسينات على PUCT:

1. $c_{\text{puct}}$ ديناميكي الضبط حسب تعقيد الوضع وتقدم البحث.

2. عدم اليقين في توقع القيمة الأخذ بعين الاعتبار ثقة Value Network في تنبؤاتها.

3. تعلم هدف السياسة التعلم المباشر لتوزيع زيارات MCTS، وليس فقط إخراج رأس السياسة.

صيغ اختيار أخرى

بجانب PUCT، هناك صيغ اختيار أخرى:

RAVE (Rapid Action Value Estimation)

$Q_{\text{RAVE}}(s,a) = (1-\beta) Q(s,a) + \beta Q_{\text{AMAF}}(s,a)$

تستخدم إحصائيات "All Moves As First" لتسريع التعلم.

GRAVE (Generalized RAVE)

متغيرة من RAVE، تستخدم إحصائيات العقد السلفية.

---

التحليل النظري

التقارب

هل تضمن PUCT التقارب إلى الحل الأمثل؟

بشكل صارم: لا يوجد ضمان نظري مثل UCB1.

عملياً: بعد محاكاات كافية، تتقارب PUCT إلى حل عالي الجودة، لأن:

1. عنصر الاستكشاف يقترب من الصفر في النهاية
2. جميع الإجراءات تُزار في النهاية
3. قيم $Q$ تتقارب إلى القيمة الحقيقية

تحليل التعقيد

تعقيد الوقت (لكل محاكاة):

• الاختيار: $O(\log N)$ (عمق الشجرة)
• التوسيع: $O(A)$ (عدد الإجراءات القانونية، يحتاج استنتاج شبكة عصبية)
• التقييم: $O(1)$ (Value Network) أو $O(T)$ (Rollout، $T$ طول اللعبة)
• الانتشار العكسي: $O(\log N)$

تعقيد المساحة:

• كل عقدة: $O(A)$ (تخزين المعرفة المسبقة وإحصائيات الزيارات)
• الشجرة كاملة: $O(N \cdot A)$ ($N$ عدد العقد)

العلاقة مع Minimax

عندما $c_{\text{puct}} \to 0$ وعدد المحاكاات $\to \infty$، MCTS + PUCT يقترب من بحث Minimax.

لكن في ميزانية محدودة، PUCT عادةً أكثر كفاءة من Minimax + Alpha-Beta، لأنها تستطيع استغلال المعرفة المسبقة بشكل أفضل.

---

الأسئلة الشائعة

س: لماذا لا نستخدم إخراج Policy Network مباشرة كاختيار؟

ج: Policy Network قد تخطئ. بحث MCTS يستطيع:

1. التحقق من حكم الشبكة العصبية
2. اكتشاف حركات جيدة تجاهلتها الشبكة العصبية
3. تصحيح التحيزات المنهجية للشبكة العصبية

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

س: في أي مواقف يكون أداء PUCT ضعيفاً؟

1. الاحتمالية المسبقة خاطئة تماماً: إذا قيّمت Policy Network حركة جيدة باحتمالية منخفضة، PUCT تحتاج محاكاات كثيرة لتصحيحها

2. التكتيكات طويلة المدى: PUCT قد تجد صعوبة في اكتشاف تسلسلات تكتيكية طويلة تتطلب حساباً دقيقاً

3. غياب نموذج الخصم: PUCT تفترض أن الخصم يستخدم أيضاً الاستراتيجية المثلى، قد لا تكون الأمثل أمام خصم غير منطقي

س: كيف نتعامل مع فضاءات الإجراءات الضخمة؟

بعض التقنيات:

1. تصفية Policy Network: فقط النظر في الإجراءات حيث $P(s,a) > \epsilon$
2. التوسيع التدريجي: توسيع عدد قليل من الإجراءات أولاً، ثم التوسيع عند الحاجة
3. التقليم الديناميكي: إزالة الإجراءات الواضحة السيئة

---

تطابق الرسوم المتحركة

المفاهيم الأساسية في هذه المقالة ورقم الرسوم المتحركة المقابل:

الرقم	المفهوم	التطابق الفيزيائي/الرياضي
🎬 E4	الاستكشاف والاستغلال	اللصوص متعددي الأذرع
🎬 C3	اختيار PUCT	حدود الثقة

---

الملخص

معادلة PUCT هي جوهر MCTS في AlphaGo، تعلمنا:

1. هيكل المعادلة: $Q + U$، عنصر الاستغلال زائد عنصر الاستكشاف
2. معنى كل عنصر: $Q$ هي قيمة الخبرة، $P$ هي الاحتمالية المسبقة، $N$ يتحكم في تناقص الاستكشاف
3. العلاقة مع UCB1: PUCT تضيف معرفة مسبقة وتستخدم شكل عنصر استكشاف مختلف
4. الاشتقاق الرياضي: من اللصوص متعددي الأذرع إلى اختيار MCTS
5. ضبط المعاملات العملي: اختيار وتأثير $c_{\text{puct}}$
6. المتغيرات المتقدمة: الضبط الديناميكي، الضوضاء، تحسينات KataGo

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

---

قراءة موسعة

• المقال التالي: نظرة عامة على AlphaGo Zero — الاختراق من الصفر
• المقال السابق: دمج MCTS مع الشبكات العصبية — البنية الكلية
• ذو صلة: حدود الطرق التقليدية — لماذا نحتاج طرقاً جديدة

---

المراجع

1. Rosin, C. D. (2011). "Multi-armed bandits with episode context." Annals of Mathematics and Artificial Intelligence, 61(3), 203-230.
2. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489.
3. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." Nature, 550, 354-359.
4. Kocsis, L., & Szepesvári, C. (2006). "Bandit based Monte-Carlo Planning." ECML.
5. Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). "Finite-time analysis of the multiarmed bandit problem." Machine Learning, 47(2), 235-256.
6. Wu, D., et al. (2019). "Accelerating Self-Play Learning in Go." arXiv preprint (تقرير تقني KataGo).

---

الملحق: مثال تنفيذ كامل

import math
import numpy as np
from typing import Dict, List, Optional

class MCTSNode:
    """عقدة MCTS"""
    def __init__(self, prior: float = 0.0):
        self.prior = prior          # P(s,a)
        self.visit_count = 0        # N(s,a)
        self.value_sum = 0.0        # W(s,a)
        self.children: Dict[int, 'MCTSNode'] = {}

    @property
    def q_value(self) -> float:
        """حساب Q(s,a)"""
        if self.visit_count == 0:
            return 0.0
        return self.value_sum / self.visit_count


class MCTS:
    """باحث MCTS، يستخدم PUCT"""

    def __init__(
        self,
        policy_network,
        value_network,
        c_puct: float = 1.5,
        num_simulations: int = 800
    ):
        self.policy_network = policy_network
        self.value_network = value_network
        self.c_puct = c_puct
        self.num_simulations = num_simulations

    def search(self, root_state) -> Dict[int, float]:
        """تنفيذ بحث MCTS، إرجاع توزيع زيارات الإجراءات"""
        root = MCTSNode()

        # توسيع العقدة الجذرية
        policy = self.policy_network(root_state)
        for action, prob in enumerate(policy):
            if is_legal(root_state, action):
                root.children[action] = MCTSNode(prior=prob)

        # تنفيذ المحاكاات
        for _ in range(self.num_simulations):
            self._simulate(root, root_state)

        # إرجاع توزيع الزيارات
        total_visits = sum(
            child.visit_count for child in root.children.values()
        )
        return {
            action: child.visit_count / total_visits
            for action, child in root.children.items()
        }

    def _simulate(self, node: MCTSNode, state) -> float:
        """تنفيذ محاكاة واحدة"""

        # إذا كانت حالة نهائية
        if is_terminal(state):
            return get_result(state)

        # إذا كانت عقدة ورقية، توسيع وتقييم
        if not node.children:
            policy = self.policy_network(state)
            value = self.value_network(state)

            for action, prob in enumerate(policy):
                if is_legal(state, action):
                    node.children[action] = MCTSNode(prior=prob)

            return value

        # الاختيار: اختيار الإجراء ذي أعلى درجة PUCT
        action = self._select_action(node)
        child = node.children[action]
        next_state = apply_action(state, action)

        # محاكاة تكرارية
        value = -self._simulate(child, next_state)

        # الانتشار العكسي: تحديث الإحصائيات
        child.visit_count += 1
        child.value_sum += value

        return value

    def _select_action(self, node: MCTSNode) -> int:
        """استخدام معادلة PUCT لاختيار الإجراء"""
        total_visits = sum(
            child.visit_count for child in node.children.values()
        )

        def puct_score(action: int, child: MCTSNode) -> float:
            # Q(s,a): متوسط القيمة
            q = child.q_value

            # U(s,a): مكافأة الاستكشاف
            u = (
                self.c_puct
                * child.prior
                * math.sqrt(total_visits)
                / (1 + child.visit_count)
            )

            return q + u

        return max(
            node.children.keys(),
            key=lambda a: puct_score(a, node.children[a])
        )


# مثال الاستخدام
def play_game():
    policy_net = PolicyNetwork()
    value_net = ValueNetwork()

    mcts = MCTS(
        policy_network=policy_net,
        value_network=value_net,
        c_puct=1.5,
        num_simulations=1600
    )

    state = initial_state()

    while not is_terminal(state):
        # تنفيذ بحث MCTS
        visit_distribution = mcts.search(state)

        # اختيار الإجراء ذي أكثر عدد زيارات
        action = max(visit_distribution.keys(),
                     key=lambda a: visit_distribution[a])

        # تنفيذ الإجراء
        state = apply_action(state, action)
        print(f"Selected action {action} with visit ratio "
              f"{visit_distribution[action]:.2%}")

    print(f"Game result: {get_result(state)}")

هذا التنفيذ يوضح الدور الأساسي لمعادلة PUCT في MCTS. تنفيذ AlphaGo الفعلي يتضمن أيضاً:

• البحث المتوازي (الخسارة الافتراضية)
• تقييم الشبكة العصبية الدفعي
• إعادة استخدام الشجرة
• ضوضاء ديريكليه
• التحكم في درجة الحرارة وغيرها من الوظائف