मुख्य कंटेंट तक स्किप करें

गो कठिन क्यों है?

AlphaGo के आने से पहले, गो को आर्टिफिशियल इंटेलिजेंस का "अंतिम गढ़" माना जाता था। दशकों से, शोधकर्ताओं ने विभिन्न तरीके आजमाए, लेकिन कंप्यूटर को पेशेवर खिलाड़ियों के स्तर तक नहीं पहुंचा पाए।

यह इसलिए नहीं था कि शोधकर्ताओं ने पर्याप्त प्रयास नहीं किया, बल्कि इसलिए कि गो अपने स्वभाव से एक अत्यंत कठिन कम्प्यूटेशनल समस्या है।

यह लेख गहराई से जांचेगा: गो वास्तव में कहां कठिन है? इसे "AI का पवित्र कटोरा" क्यों कहा जाता है?


स्टेट स्पेस का विस्फोट: 10^170 का अर्थ

स्टेट स्पेस क्या है?

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

गो के लिए, यह संख्या है:

गो स्टेट स्पेस ≈ 10^170

यह कितना है? आइए कुछ तुलना करें।

ब्रह्मांड के परमाणुओं की संख्या से तुलना

भौतिकविदों के अनुमान के अनुसार, अवलोकन योग्य ब्रह्मांड में परमाणुओं की कुल संख्या लगभग है:

ब्रह्मांड के परमाणु ≈ 10^80

इसका मतलब है:

गो की संभावित स्थितियों की संख्या, ब्रह्मांड के परमाणुओं की संख्या से 10^90 गुना है।

यदि आप ब्रह्मांड के हर परमाणु को एक सुपरकंप्यूटर मान लें, प्रत्येक कंप्यूटर प्रति सेकंड 1 अरब स्थितियों को प्रोसेस कर सके, बिग बैंग से अब तक (लगभग 13.8 अरब वर्ष) भी सभी स्थितियों को पूरा करना असंभव है।

संख्याओं की सहज समझ

संख्याअर्थ
10^9एक अरब, मानव जनसंख्या का क्रम
10^12एक ट्रिलियन, विश्व में चींटियों की संख्या
10^23एक मोल में अणुओं की संख्या
10^80ब्रह्मांड में परमाणुओं की संख्या
10^120चेस का स्टेट स्पेस
10^170गो का स्टेट स्पेस

गो का स्टेट स्पेस इतना बड़ा क्यों है?

गो के विशाल स्टेट स्पेस के कई कारण हैं:

1. बोर्ड का आकार

गो 19×19 के बोर्ड का उपयोग करता है, कुल 361 इंटरसेक्शन पॉइंट। तुलना में:

  • चेस: 8×8 = 64 वर्ग
  • चीनी शतरंज: 9×10 = 90 इंटरसेक्शन पॉइंट
  • गोमोकू: 15×15 = 225 इंटरसेक्शन पॉइंट

2. प्रत्येक बिंदु पर तीन स्थितियां

प्रत्येक इंटरसेक्शन पॉइंट हो सकता है:

  • खाली (कोई पत्थर नहीं)
  • काला पत्थर
  • सफेद पत्थर

मोटा अनुमान, संभावित संयोजन 3^361 ≈ 10^172 है। गो के नियमों (जैसे को, लिबर्टी की सीमाएं) को ध्यान में रखते हुए, वास्तविक वैध स्थितियां लगभग 10^170 हैं।

3. पत्थर हिलते नहीं

चेस के विपरीत, गो में पत्थर एक बार रखे जाने के बाद हिलते नहीं (जब तक कैप्चर न हों)। इसका मतलब है प्रत्येक चाल एक पत्थर जोड़ती है, मौजूदा पत्थरों को हिलाती नहीं, जिससे संभावित पथ और अधिक हो जाते हैं।

कोड उदाहरण: स्टेट स्पेस अनुमान

import math

# बोर्ड का आकार
BOARD_SIZE = 19
TOTAL_POINTS = BOARD_SIZE ** 2 # 361

# प्रत्येक बिंदु पर तीन स्थितियां (खाली, काला, सफेद)
# मोटी ऊपरी सीमा
upper_bound = 3 ** TOTAL_POINTS
print(f"मोटी ऊपरी सीमा: 3^{TOTAL_POINTS} ≈ 10^{math.log10(upper_bound):.0f}")
# आउटपुट: मोटी ऊपरी सीमा: 3^361 ≈ 10^172

# नियम सीमाओं को ध्यान में रखते हुए वास्तविक अनुमान
# Tromp-Taylor की सटीक गणना लगभग 2.08 × 10^170 देती है
actual_estimate = 2.08e170
print(f"वास्तविक अनुमान: {actual_estimate:.2e}")

# ब्रह्मांड के परमाणुओं से तुलना
universe_atoms = 1e80
ratio = actual_estimate / universe_atoms
print(f"गो स्थितियां / ब्रह्मांड के परमाणु = 10^{math.log10(ratio):.0f}")
# आउटपुट: गो स्थितियां / ब्रह्मांड के परमाणु = 10^90

ब्रांचिंग फैक्टर का अभिशाप: औसतन 250 विकल्प

ब्रांचिंग फैक्टर क्या है?

ब्रांचिंग फैक्टर (Branching Factor) किसी खेल में किसी भी चाल पर औसतन कितनी वैध चालें हैं, इसे संदर्भित करता है। यह संख्या सर्च ट्री की चौड़ाई निर्धारित करती है।

खेलऔसत ब्रांचिंग फैक्टर
टिक-टैक-टो~4
चेस~35
चीनी शतरंज~38
ओथेलो~10
गो~250

सर्च ट्री की विस्फोटक वृद्धि

मान लें हम ट्री सर्च एल्गोरिदम का उपयोग करके N चालें आगे देखना चाहते हैं। विचार करने योग्य स्थितियों की संख्या लगभग है:

नोड्सbN\text{नोड्स} \approx b^N

जहां b ब्रांचिंग फैक्टर है।

आइए चेस और गो की तुलना करें:

N चालें आगेचेस (b=35)गो (b=250)अंतर
1 चाल35250
2 चालें1,22562,50051×
4 चालें15 लाख3.9 अरब2,600×
6 चालें1.8 अरब2.4×10^141.3 करोड़×
10 चालें2.8×10^159.5×10^2334 करोड़×

10 चालें आगे देखने पर, गो को चेस से 34 करोड़ गुना अधिक स्थितियों पर विचार करना पड़ता है।

डीप ब्लू की विधि गो में क्यों विफल रही

1997 में कास्पारोव को हराने वाले डीप ब्लू की मुख्य तकनीक थी:

  1. अल्फा-बीटा प्रूनिंग: सर्च नोड्स को कम करना
  2. हार्डवेयर त्वरण: प्रति सेकंड 20 करोड़ स्थितियों का मूल्यांकन
  3. मैन्युअल मूल्यांकन फ़ंक्शन: विशेषज्ञ-डिज़ाइन किया गया स्थिति मूल्यांकन

लेकिन यदि वही विधि उपयोग करें:

  • चेस: 12-14 चालें आगे देखने के लिए लगभग 10^18 नोड्स का मूल्यांकन आवश्यक
  • गो: 12 चालें आगे देखने के लिए लगभग 10^29 नोड्स का मूल्यांकन आवश्यक

अंतर 1 अरब अरब गुना है। कोई भी हार्डवेयर इस अंतर को नहीं पाट सकता।

शुरुआती चालों के विकल्प और भी विशाल

गो की शुरुआत में, ब्रांचिंग फैक्टर और भी अधिक है:

  • पहली चाल: 361 विकल्प
  • दूसरी चाल: 360 विकल्प
  • तीसरी चाल: 359 विकल्प
  • ...

केवल पहली 10 चालें देखें:

361×360×359×...×3525.5×1025361 \times 360 \times 359 \times ... \times 352 \approx 5.5 \times 10^{25}

यही कारण है कि "ओपनिंग जोसेकी" इतने महत्वपूर्ण हैं — मानव खिलाड़ियों को बड़ी संख्या में ओपनिंग वेरिएशन याद रखने पड़ते हैं, क्योंकि तत्काल गणना असंभव है।


मूल्यांकन की कठिनाई: कोई सरल पीस वैल्यू नहीं

चेस में मटीरियल एडवांटेज

चेस में, स्थिति का मूल्यांकन अपेक्षाकृत सहज है:

पीसमूल्य (पारंपरिक)
प्यादा1
घोड़ा3
बिशप3
रूक5
रानी9

हालांकि वास्तविक मूल्यांकन अधिक जटिल है (स्थिति, संरचना, आदि), "पीस गिनना" एक अच्छा प्रारंभिक बिंदु है। प्रतिद्वंद्वी की रानी को कैप्चर करना लगभग निश्चित रूप से अच्छा है।

गो: प्रत्येक पत्थर बराबर है

गो में, प्रत्येक पत्थर का आंतरिक मूल्य पूर्णतः समान है — सभी बस पत्थर हैं।

एक पत्थर का मूल्य पूरी तरह से निर्भर करता है:

  • बोर्ड पर उसकी स्थिति
  • अन्य पत्थरों के साथ उसका संबंध
  • समग्र स्थिति पर उसका प्रभाव

यह मूल्यांकन को अत्यंत कठिन बना देता है।

मोटाई और प्रभाव की अमूर्तता

गो में कई अमूर्त अवधारणाएं हैं:

मोटाई (Thickness)

"मोटाई" एक समूह को संदर्भित करती है जो ठोस, स्थिर और प्रभावशाली है। लेकिन "मोटाई" को मापना कठिन है:

  • एक मोटे आकार की कितने पॉइंट्स की कीमत है?
  • मोटाई का उपयोग आक्रमण के लिए कब करना चाहिए?
  • मोटाई कब "भारी आकार" (अकुशल आकार) बन जाती है?

शीर्ष खिलाड़ी कह सकते हैं: "यह समूह बहुत मोटा है, लगभग 15 पॉइंट्स के बराबर।" लेकिन यह दशकों के अनुभव पर आधारित अंतर्ज्ञान है, सटीक गणना नहीं।

प्रभाव (Influence)

गो में प्रभाव आसपास के स्थान पर पत्थरों के संभावित नियंत्रण को संदर्भित करता है। यह नियंत्रण "वर्चुअल" है — यह क्षेत्र में बदल सकता है, आक्रमण-रक्षा में भूमिका निभा सकता है, या अंततः कुछ भी नहीं बन सकता।

"संभावित" मूल्य का मूल्यांकन कैसे करें? यह कंप्यूटर के लिए अत्यंत कठिन है।

आजी (Aji)

"आजी" गो की सबसे अमूर्त अवधारणाओं में से एक है। यह बोर्ड पर किसी स्थान की संभावित संभावनाओं को संदर्भित करता है।

एक "मृत समूह" में "उपयोग मूल्य" हो सकता है — हालांकि इसे बचाया नहीं जा सकता, लेकिन भविष्य की लड़ाई में हस्तक्षेप पैदा कर सकता है। इस "संभावित संभावना" को संख्यात्मक रूप से व्यक्त करना लगभग असंभव है।

मैन्युअल मूल्यांकन फ़ंक्शन क्यों विफल रहे

डीप ब्लू से पहले की कंप्यूटर चेस में, मानव विशेषज्ञों द्वारा डिज़ाइन किए गए मूल्यांकन फ़ंक्शन का उपयोग होता था:

मूल्यांकन = मटीरियल स्कोर + पोज़िशन स्कोर + किंग सेफ्टी + पॉन स्ट्रक्चर + ...

इन आइटम्स को मापा जा सकता था, वेट एडजस्ट किए जा सकते थे, और परिणाम अच्छे थे।

लेकिन गो में?

शोधकर्ताओं ने विभिन्न फीचर्स आजमाए:

  • नियंत्रित इंटरसेक्शन पॉइंट्स की संख्या
  • पत्थरों की "स्वतंत्रता" (लिबर्टीज़)
  • कनेक्शन की मजबूती
  • आई फॉर्मेशन की पूर्णता
  • ...

लेकिन इन फीचर्स का कोई भी संयोजन कभी भी अमेच्योर हाई-डैन स्तर तक नहीं पहुंच पाया।

मूल समस्या: गो का स्थिति मूल्यांकन एक उच्च गैर-रैखिक, वैश्विक समस्या है।

एक पत्थर का मूल्य पूरे बोर्ड की स्थिति पर निर्भर करता है, न कि स्थानीय फीचर्स के सरल योग पर।


दीर्घकालिक योजना की आवश्यकता: एक खेल में 150 चालें

गो के तीन मुख्य चरण

एक मानक गो मैच आमतौर पर तीन चरणों से गुजरता है:

चरणचालें (लगभग)विशेषताएं
ओपनिंग1-50क्षेत्र लेना, फ्रेमवर्क बनाना, वैश्विक दिशा स्थापित करना
मिडगेम50-200लड़ाई, आक्रमण-रक्षा, स्थानीय और वैश्विक का संतुलन
एंडगेम200-300समापन, गणना, सटीकता

औसतन एक खेल में लगभग 250-300 चालें होती हैं, जिनमें पहली 150 चालें जीत-हार की बड़ी तस्वीर निर्धारित करती हैं।

ओपनिंग: 30 चालों बाद की योजना

ओपनिंग चरण की प्रत्येक चाल, दर्जनों या सैकड़ों चालों बाद के लिए तैयारी करती है।

उदाहरण के लिए, "सैनरेनसेई" (तीन स्टार) ओपनिंग:

. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . ● . . . . . ● . . . . . ● . . .
. . . . . . . . . . . . . . . . . . .
...

ये तीन काले पत्थर "प्रभाव-प्रकार" ओपनिंग बनाते हैं, जिसका इरादा है:

  1. क्षेत्र घेरने की जल्दी नहीं
  2. सफेद के प्रवेश करने पर आक्रमण
  3. आक्रमण के माध्यम से क्षेत्र या प्रभाव प्राप्त करना
  4. अंततः एंडगेम में लाभ प्राप्त करना

इस "योजना" के लिए 50-100 चालों बाद की स्थिति का पूर्वानुमान आवश्यक है। कोई भी सर्च एल्गोरिदम इतना दूर नहीं देख सकता।

मिडगेम: स्थानीय और वैश्विक का संतुलन

मिडगेम लड़ाई गो का सबसे जटिल हिस्सा है। खिलाड़ियों को प्रत्येक चाल पर विचार करना होता है:

  1. स्थानीय गणना: यह लड़ाई कौन जीतेगा?
  2. वैश्विक निर्णय: क्या यहां लड़ना उचित है?
  3. क्रम का चयन: कहां पहले खेलना सबसे कुशल है?
  4. त्याग का निर्णय: कब पत्थर छोड़कर दूसरी जगह जाना चाहिए?

एक विशिष्ट मिडगेम निर्णय:

"यदि मैं यहां काटता हूं, प्रतिद्वंद्वी जवाबी हमला करेगा, मुझे एक समूह जीवित करना होगा, इससे प्रतिद्वंद्वी को बड़े बिंदु पर पहले जाने का मौका मिलेगा...अंततः मैं लगभग 5 पॉइंट्स खोऊंगा। लेकिन यदि मैं पहले मजबूत करके फिर काटूं, हालांकि सेंटे खोऊंगा, लेकिन..."

इस प्रकार की बहु-स्तरीय, बहु-आयामी सोच के लिए स्थानीय और वैश्विक, अल्पकालिक और दीर्घकालिक को एक साथ संभालना आवश्यक है।

एंडगेम: सटीक गणना और उलटफेर

एंडगेम चरण सरल लगता है — बस समापन। लेकिन वास्तव में:

  • प्रत्येक चाल के "पॉइंट वैल्यू" की सटीक गणना आवश्यक
  • सेंटे-गोटे का अंतर जीत-हार निर्धारित कर सकता है
  • "को फाइट" पूरी स्थिति बदल सकती है

पेशेवर खिलाड़ी एंडगेम में 0.5 पॉइंट की सटीकता तक गणना कर सकते हैं, जबकि एक खेल की जीत-हार 1 पॉइंट से हो सकती है।

दूर न देख पाना घातक क्यों है

आइए एक सरल गणना करें:

  • एक खेल में औसतन 250 चालें
  • परिणाम का पूर्ण पूर्वानुमान करने के लिए, सैद्धांतिक रूप से सभी 250 चालें देखनी होंगी
  • यदि ब्रांचिंग फैक्टर 100 तक गिर भी जाए (एंडगेम), सर्च स्पेस 100^250 ≈ 10^500 है

यह किसी भी कंप्यूटर की क्षमता से बहुत परे है।

यही कारण है कि गो AI को स्थिति का "मूल्यांकन" सीखना होगा, केवल "गणना" पर निर्भर नहीं रह सकता।


अंतर्ज्ञान का महत्व: "यह चाल सही लगती है"

मानव खिलाड़ी कैसे सोचते हैं

शीर्ष गो खिलाड़ी अपनी सोच प्रक्रिया का वर्णन करते समय अक्सर ऐसे शब्दों का उपयोग करते हैं:

"यह चाल सही लगती है।"

"यह आकार बहुत आरामदायक है।"

"उसके उस समूह की आजी खराब है।"

"यहां एक अव्यक्त खतरे की भावना है।"

यह काव्यात्मक वर्णन नहीं है, बल्कि वास्तविक संज्ञानात्मक प्रक्रिया है। मानव खिलाड़ी गो की जटिलता को संभालने के लिए पैटर्न रिकग्निशन और अंतर्ज्ञान निर्णय का उपयोग करते हैं।

पैटर्न रिकग्निशन: एक सेकंड में मुख्य बिंदु देखना

प्रयोग दिखाते हैं कि पेशेवर खिलाड़ी एक नज़र में बोर्ड देखकर (1 सेकंड से कम), कर सकते हैं:

  1. मुख्य क्षेत्रों की पहचान करना
  2. संभावित "अच्छी चालें" खोजना
  3. स्थिति की सामान्य प्रवृत्ति को समझना

यह क्षमता हज़ारों खेलों के अनुभव से आती है, "सेंस" बनाती है।

AlphaGo से पहले की कंप्यूटर गो में, सबसे बड़ी कठिनाई इस अंतर्ज्ञान को दोहराना थी।

अंतर्ज्ञान का गणितीय विवरण

मशीन लर्निंग के दृष्टिकोण से, मानव गो अंतर्ज्ञान को इस प्रकार समझा जा सकता है:

P(अच्छी चालबोर्ड स्थिति)P(\text{अच्छी चाल} | \text{बोर्ड स्थिति})

एक प्रशिक्षित मस्तिष्क, बोर्ड स्थिति के आधार पर, तुरंत प्रत्येक स्थान के "अच्छी चाल" होने की संभाव्यता वितरण आउटपुट कर सकता है।

यही Policy Network को सीखना है — और इसके लिए डीप न्यूरल नेटवर्क की आवश्यकता है।


इसे "AI का पवित्र कटोरा" क्यों कहा जाता है

बोर्ड गेम के मील के पत्थर

आर्टिफिशियल इंटेलिजेंस के इतिहास में, बोर्ड गेम हमेशा महत्वपूर्ण मील के पत्थर रहे हैं:

वर्षघटनामहत्व
1951पहला चेकर्स प्रोग्रामसबसे प्रारंभिक गेम AI
1997डीप ब्लू ने कास्पारोव को हरायाब्रूट फोर्स सर्च की जीत
2007चेकर्स पूरी तरह हल हुआपरफेक्ट इंफॉर्मेशन गेम की सीमा
2016AlphaGo ने ली सेडोल को हरायाडीप लर्निंग की जीत

गो विशेष क्यों है

गो को "AI का पवित्र कटोरा" कहा जाता है, क्योंकि इसमें सभी कठिन विशेषताएं एक साथ हैं:

विशेषतागोचेस
स्टेट स्पेस10^17010^120
ब्रांचिंग फैक्टर~250~35
औसत चालें~250~40
मूल्यांकन कठिनाईअत्यंत उच्चमध्यम
अंतर्ज्ञान निर्भरताबहुत अधिकउच्च

यदि AI गो को हल कर सकता है, इसका अर्थ है:

  1. अत्यंत बड़े सर्च स्पेस को संभाल सकता है
  2. अमूर्त मूल्यांकन सीख सकता है
  3. दीर्घकालिक योजना बना सकता है
  4. "अंतर्ज्ञान" विकसित कर सकता है

ये क्षमताएं "गेम खेलने" से बहुत आगे हैं, जनरल इंटेलिजेंस की मुख्य विशेषताएं हैं।

अकादमिक जगत की भविष्यवाणी

2016 से पहले, "AI कब मानव गो चैंपियन को हरा सकेगा" पर अकादमिक जगत की सामान्य भविष्यवाणी थी:

"कम से कम 10-20 वर्ष और।"

— अधिकांश AI शोधकर्ता (2015)

यह भविष्यवाणी तत्कालीन तकनीकी प्रगति की गति पर आधारित थी। गो प्रोग्राम प्रति वर्ष लगभग 1-2 डैन सुधर रहे थे, और मानव पेशेवर नौ-डैन से 18 डैन का अंतर था। इस गति से, वास्तव में 10-20 वर्ष लगते।

किसी ने उम्मीद नहीं की थी कि डीप लर्निंग छलांग वाली सफलता लाएगी।


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

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

नंबरअवधारणाभौतिकी/गणित संबंध
🎬 B2स्टेट स्पेस विस्फोटकॉम्बिनेटोरिक्स, एक्सपोनेंशियल ग्रोथ
🎬 B8कॉम्बिनेटोरियल एक्सप्लोज़नफैक्टोरियल ग्रोथ, सर्च ट्री
🎬 A3ब्रांचिंग फैक्टर तुलनाग्राफ थ्योरी, ट्री स्ट्रक्चर
🎬 B5इवैल्युएशन फ़ंक्शन दुविधानॉन-लीनियर मैपिंग

मुख्य बिंदुओं का सारांश

गो को "AI का पवित्र कटोरा" इसलिए कहा जाता है क्योंकि यह तीन बड़ी चुनौतियों को जोड़ता है:

1. स्पेस का अभिशाप

  • 10^170 संभावित स्थितियां, ब्रह्मांड के परमाणुओं से बहुत अधिक
  • ब्रांचिंग फैक्टर ~250, सर्च ट्री विस्फोटक वृद्धि
  • ब्रूट फोर्स सर्च भौतिक रूप से असंभव

2. मूल्यांकन की कठिनाई

  • प्रत्येक पत्थर का मूल्य समान, कोई मटीरियल एडवांटेज नहीं
  • "मोटाई" "प्रभाव" "आजी" जैसी अमूर्त अवधारणाओं को मापना कठिन
  • स्थिति मूल्यांकन उच्च गैर-रैखिक, वैश्विक समस्या

3. समय की चुनौती

  • एक खेल ~250 चालें, दीर्घकालिक योजना आवश्यक
  • ओपनिंग निर्णय 50-100 चालों बाद की स्थिति प्रभावित करते हैं
  • स्थानीय लड़ाई और वैश्विक संतुलन पर एक साथ विचार आवश्यक

इन्हीं चुनौतियों के संयोजन ने पारंपरिक AI विधियों (ब्रूट फोर्स सर्च + मैन्युअल मूल्यांकन) को गो में पूरी तरह विफल कर दिया।

और AlphaGo की सफलता इसलिए हुई क्योंकि इसने डीप न्यूरल नेटवर्क से मूल्यांकन समस्या हल की, मोंटे कार्लो ट्री सर्च से योजना समस्या हल की, और रीइन्फोर्समेंट लर्निंग से मानव को पार करने की समस्या हल की।


आगे पढ़ें


संदर्भ सामग्री

  1. Tromp, J. (2016). "Number of legal Go positions." — गो स्टेट स्पेस की सटीक गणना
  2. Allis, L.V. (1994). "Searching for Solutions in Games and Artificial Intelligence." PhD thesis, University of Limburg. — गेम जटिलता का सैद्धांतिक विश्लेषण
  3. Müller, M. (2002). "Computer Go." Artificial Intelligence, 134(1-2), 145-179. — कंप्यूटर गो के प्रारंभिक शोध का सारांश
  4. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489. — AlphaGo का मूल पेपर