PUCT सूत्र का विस्तृत विवरण

पिछले लेख में, हमने MCTS और न्यूरल नेटवर्क के संयोजन का अवलोकन किया। अब, आइए MCTS के चयन चरण के मुख्य भाग—PUCT सूत्र का गहन अन्वेषण करें।

यह सूत्र सरल दिखता है, लेकिन यह AlphaGo की सफलता की एक कुंजी है। यह "ज्ञात अच्छी चालों का उपयोग" और "संभावित बेहतर चालों का अन्वेषण"—इन दो प्रतीत होने वाले विरोधाभासी लक्ष्यों को सुंदर ढंग से संतुलित करता है।

---

PUCT सूत्र

सूत्र परिभाषा

AlphaGo द्वारा उपयोग किया जाने वाला PUCT (Predictor Upper Confidence Trees) सूत्र:

$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)}$, स्कोर शून्य के करीब पहुंचता है

यह सुनिश्चित करता है:

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 सूत्र की समीक्षा

पारंपरिक MCTS द्वारा उपयोग किया जाने वाला UCB1 सूत्र:

$\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. प्रायर ज्ञान का उपयोग: Policy Network द्वारा प्रदान $P(s,a)$ खोज को शुरू से ही तार्किक चालों पर केंद्रित करता है

2. तेज़ कन्वर्जेंस: रैखिक क्षय ($1/(1+n)$) लॉगरिदमिक क्षय ($1/\sqrt{\ln N / n}$) से तेज़ी से खोज को केंद्रित करता है

3. अधिक नियंत्रणीय एक्सप्लोरेशन: $P(s,a)$ और $c_{\text{puct}}$ एक्सप्लोरेशन को नियंत्रित करने के अधिक साधन प्रदान करते हैं

सैद्धांतिक पृष्ठभूमि

UCB1 की कठोर सैद्धांतिक गारंटी (regret bound) है, लेकिन ये गारंटी मानती हैं:

• प्रत्येक आर्म (एक्शन) स्वतंत्र है
• कोई प्रायर जानकारी नहीं है

Go में, हमारे पास शक्तिशाली प्रायर (Policy Network) है, PUCT इस जानकारी का बेहतर उपयोग कर सकता है।

---

गणितीय व्युत्पत्ति

मल्टी-आर्म्ड बैंडिट से शुरू

PUCT की प्रेरणा मल्टी-आर्म्ड बैंडिट (Multi-Armed Bandit) समस्या से आती है।

कल्पना करें कि आपके सामने $K$ स्लॉट मशीनें हैं, प्रत्येक की जीत संभाव्यता अलग लेकिन अज्ञात है। आपका लक्ष्य कुल जीत को अधिकतम करना है। रणनीति है:

• एक्सप्लॉइट: सबसे अच्छी दिखने वाली मशीन खींचें
• एक्सप्लोर: अन्य मशीनें आज़माएं, हो सकता है बेहतर मिल जाए

UCB1 इस समस्या का क्लासिक समाधान है, PUCT इसका एक प्रकार है।

UCB का सैद्धांतिक आधार

यादृच्छिक चर $X$ के लिए, Hoeffding असमानता से:

$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. 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

रूट नोड पर Dirichlet नॉइज़ जोड़ें:

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

जहां $\eta \sim \text{Dir}(\alpha)$। यह एक्सप्लोरेशन की विविधता बढ़ाता है।

3. UCT-जैसा PUCT

$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$ मान वास्तविक मूल्य में कन्वर्ज होता है

जटिलता विश्लेषण

समय जटिलता (प्रति सिमुलेशन):

• Selection: $O(\log N)$ (ट्री की गहराई)
• Expansion: $O(A)$ (वैध एक्शन्स की संख्या, न्यूरल नेटवर्क इन्फरेंस की आवश्यकता)
• Evaluation: $O(1)$ (Value Network) या $O(T)$ (Rollout, $T$ गेम की लंबाई है)
• Backpropagation: $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 से अधिक कुशल है, क्योंकि यह प्रायर ज्ञान का बेहतर उपयोग कर सकता है।

---

सामान्य प्रश्न

Q: Policy Network आउटपुट को सीधे चयन के लिए क्यों नहीं उपयोग करते?

A: Policy Network गलत हो सकता है। MCTS खोज कर सकता है:

1. न्यूरल नेटवर्क के निर्णय को सत्यापित करना
2. न्यूरल नेटवर्क द्वारा अनदेखी अच्छी चालें खोजना
3. न्यूरल नेटवर्क के व्यवस्थित पूर्वाग्रहों को ठीक करना

प्रयोग दिखाते हैं कि मजबूत न्यूरल नेटवर्क के साथ भी, खोज जोड़ने से खेल क्षमता में काफी सुधार होता है।

Q: PUCT किन स्थितियों में अच्छा प्रदर्शन नहीं करता?

1. प्रायर संभाव्यता पूरी तरह गलत: यदि Policy Network अच्छी चाल को कम संभाव्यता देता है, PUCT को सुधार के लिए कई सिमुलेशन चाहिए

2. दीर्घकालिक रणनीति: PUCT को सटीक गणना की आवश्यकता वाले लंबे अनुक्रमों की खोज में कठिनाई हो सकती है

3. प्रतिद्वंद्वी मॉडल की कमी: PUCT मानता है कि प्रतिद्वंद्वी भी सर्वोत्तम रणनीति का उपयोग करता है, अतार्किक प्रतिद्वंद्वी के सामने यह सर्वोत्तम नहीं हो सकता

Q: बहुत बड़े एक्शन स्पेस को कैसे संभालें?

कुछ तकनीकें:

1. Policy Network फ़िल्टरिंग: केवल $P(s,a) > \epsilon$ वाले एक्शन्स पर विचार
2. क्रमिक विस्तार: पहले केवल कुछ एक्शन्स का विस्तार, आवश्यकता पर विस्तार
3. गतिशील प्रूनिंग: स्पष्ट रूप से खराब एक्शन्स हटाएं

---

एनिमेशन संदर्भ

इस लेख में शामिल मुख्य अवधारणाएं और एनिमेशन नंबर:

नंबर	अवधारणा	भौतिकी/गणित समकक्ष
E4	एक्सप्लोरेशन और एक्सप्लॉइटेशन	मल्टी-आर्म्ड बैंडिट
C3	PUCT चयन	विश्वास सीमा

---

सारांश

PUCT सूत्र AlphaGo MCTS का मुख्य है, हमने सीखा:

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., & Szepesvari, 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

        # Selection: उच्चतम PUCT स्कोर वाला एक्शन चुनें
        action = self._select_action(node)
        child = node.children[action]
        next_state = apply_action(state, action)

        # पुनरावर्ती सिमुलेशन
        value = -self._simulate(child, next_state)

        # Backpropagation: सांख्यिकी अपडेट करें
        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)}")

यह कार्यान्वयन MCTS में PUCT सूत्र की मुख्य भूमिका दिखाता है। वास्तविक AlphaGo कार्यान्वयन में शामिल हैं:

• समानांतर खोज (वर्चुअल लॉस)
• बैच न्यूरल नेटवर्क मूल्यांकन
• ट्री का पुन: उपयोग
• Dirichlet नॉइज़
• तापमान नियंत्रण आदि कार्यक्षमता