कंप्यूटर गो: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 50: Line 50:


;बोर्ड का आकार
;बोर्ड का आकार
बड़े बोर्ड (19×19, 361 चौराहे) को अक्सर प्राथमिक कारणों में से के रूप में जाना जाता है कि मजबूत कार्यक्रम बनाना कठिन क्यों है। बड़े बोर्ड का आकार अल्फा-बीटा प्रूनिंग|अल्फा-बीटा खोजकर्ता को महत्वपूर्ण खोज ्सटेंशन या [[प्रूनिंग (निर्णय वृक्ष)]] अनुमान के बिना गहराई से आगे देखने से रोकता है।
बड़े बोर्ड (19×19, 361 इंटेरसेक्शन्स) को अधिकांशतः प्राथमिक कारणों के रूप में जाना जाता है कि स्ट्रांग प्रोग्राम क्रिएट करना कठिन क्यों है। बड़े बोर्ड का आकार अल्फा-बीटा प्रूनिंग को महत्वपूर्ण सर्च एक्सटेंशन अथवा [[प्रूनिंग (निर्णय वृक्ष)|प्रूनिंग (डिसीजन ट्री)]] अनुमान के बिना डीप लुक-अहेड प्राप्त करने से अवरोधित करता है।


2002 में, MIGOS (MIni GO सॉल्वर) नामक कंप्यूटर प्रोग्राम ने 5×5 बोर्ड के लिए गो गेम को पूरी तरह से हल कर दिया। ब्लैक जीतता है, पूरे बोर्ड पर कब्ज़ा कर लेता है।<ref>{{cite web|url=http://erikvanderwerf.tengen.nl/5x5/5x5solved.html|title=5x5 Go is solved|access-date=28 January 2016}}</ref>
2002 में, मिगोस (मिनी गो सॉल्वर) नामक कंप्यूटर प्रोग्राम ने 5×5 बोर्ड के लिए गो गेम को पूर्ण रूप से सॉल्व कर दिया। ब्लैक विजय प्राप्त करता है, पूर्ण बोर्ड पर अधिकार कर लेता है।<ref>{{cite web|url=http://erikvanderwerf.tengen.nl/5x5/5x5solved.html|title=5x5 Go is solved|access-date=28 January 2016}}</ref>
;स्थानांतरण विकल्पों की संख्या
;मूव विकल्पों की संख्या
शतरंज से तुलना जारी रखते हुए, गो चालें खेल के नियमों द्वारा सीमित नहीं हैं। शतरंज में पहली चाल के लिए खिलाड़ी के पास बीस विकल्प होते हैं। गो खिलाड़ी समरूपता को ध्यान में रखते हुए 55 अलग-अलग कानूनी चालों के विकल्प के साथ शुरुआत करते हैं। समरूपता टूटने पर यह संख्या तेज़ी से बढ़ती है, और जल्द ही बोर्ड के लगभग सभी 361 बिंदुओं का मूल्यांकन किया जाना चाहिए।
चैस से उपमा प्रारम्भ रखते हुए, गो मूव्स गेम के नियमों द्वारा सीमित नहीं हैं। चैस में प्रथम मूव के लिए प्लेयर के निकट बीस विकल्प होते हैं। गो प्लेयर समरूपता को ध्यान में रखते हुए 55 भिन्न-भिन्न लीगल मूव्स के विकल्प के साथ प्रारम्भ करते हैं। समरूपता के खंडित होने पर इस संख्या में तीव्रता से वृद्धि होती है, और शीघ्र ही बोर्ड के प्रायः सभी 361 पॉइंट्स को इवैल्यूऐट करना चाहिए।


;मूल्यांकन समारोह
;इवैल्यूएशन फंक्शन
खेल में सबसे बुनियादी कार्यों में से बोर्ड की स्थिति का आकलन करना है: किस पक्ष का पक्ष लिया जाता है, और कितना? शतरंज में, पेड़ में भविष्य की कई स्थितियाँ पक्ष के लिए सीधी जीत होती हैं, और बोर्डों के पास सरल सामग्री गिनती में मूल्यांकन के लिए उचित अनुमान होता है, साथ ही प्यादे की संरचना जैसे कुछ निश्चित कारक भी होते हैं। ऐसा भविष्य जहां पक्ष ने बिना किसी लाभ के अपनी रानी को खो दिया है, वह स्पष्ट रूप से दूसरे पक्ष के पक्ष में है। इस प्रकार के स्थितिगत मूल्यांकन नियमों को गो पर कुशलतापूर्वक लागू नहीं किया जा सकता है। गो स्थिति का मूल्य यह निर्धारित करने के लिए जटिल विश्लेषण पर निर्भर करता है कि समूह जीवित है या नहीं, कौन से पत्थरों को दूसरे से जोड़ा जा सकता है, और मजबूत स्थिति का किस हद तक प्रभाव है, या किस हद तक कमजोर स्थिति का अनुमान है। स्थिति पर हमला किया जा सकता है. रखे गए पत्थर का तत्काल प्रभाव नहीं हो सकता है, किन्तु कई कदमों के बाद पूर्व-निरीक्षण में अत्यधिक महत्वपूर्ण हो सकता है क्योंकि बोर्ड के अन्य क्षेत्र आकार लेते हैं।
गेम का सबसे मूल कार्य बोर्ड की स्थिति का आकलन करना है: किस साइड का पक्ष लिया जाता है, और कितना? चैस में, ट्री में भविष्य की कई स्थितियाँ पक्ष के लिए प्रत्यक्ष विजय होती है, और बोर्डों के निकट सिंपल मटेरियल काउंटिंग में इवैल्यूएशन के लिए उचित अनुमान होता है, साथ ही पौन स्ट्रक्चर जैसे कुछ निश्चित कारक भी होते हैं। ऐसा भविष्य जहां पक्ष ने बिना किसी लाभ के अपनी रानी को लुप्त कर दिया है, वह स्पष्ट रूप से दूसरे साइड के पक्ष में है। इस प्रकार के पोज़िशनल इवैल्यूएशन नियमों को गो पर कुशलतापूर्वक प्रस्तावित नहीं किया जा सकता है। गो पोज़िशन का मान यह निर्धारित करने के लिए समष्टि विश्लेषण पर निर्भर करता है कि समूह जीवित है अथवा नहीं, कौन से स्टोन्स को एक-दूसरे से संयोजित किया जा सकता है, और अनुमान लगाया जा सकता है कि स्ट्रांग पोज़िशन का कितना प्रभाव है, या कितना वीक पोज़िशन का प्रभाव हो सकता है जिससे अटैक किया जा सकता है। प्लेस्ड स्टोन्स का शीघ्र प्रभाव नहीं हो सकता है, किन्तु कई मूव्स के पश्चात पूर्व-निरीक्षण में अत्यधिक महत्वपूर्ण हो सकता है क्योंकि बोर्ड के अन्य क्षेत्र आकार लेते हैं।


बोर्ड राज्यों के खराब मूल्यांकन के कारण एआई को उन पदों की ओर काम करना पड़ेगा जो गलत तरीके से मानते हैं कि वे इसके पक्ष में हैं, किन्तु वास्तव में ऐसा नहीं है।
बोर्ड स्टेट्स के पुअर इवैल्यूएशन के कारण एआई को उन पदों की ओर कार्य करना होता है जो अनुचित प्रकार से मानते हैं कि वे इसके पक्ष में हैं, किन्तु वास्तव में ऐसा नहीं है।


;[[जीवन और मृत्यु]]
;[[जीवन और मृत्यु|लाइफ और डेथ]]
गो खिलाड़ी के लिए मुख्य चिंताओं में से यह है कि पत्थरों के किन समूहों को जीवित रखा जा सकता है और किसे पकड़ा जा सकता है। समस्याओं के इस सामान्य वर्ग को जीवन और मृत्यु के रूप में जाना जाता है। ज्ञान-आधारित एआई सिस्टम ने कभी-कभी बोर्ड पर समूहों के जीवन और मृत्यु की स्थिति को समझने का प्रयास किया। सबसे सीधा तरीका उन चालों पर पेड़ की खोज करना है जो संभावित रूप से संबंधित पत्थरों को प्रभावित करते हैं, और फिर खेल की मुख्य पंक्ति के अंत में पत्थरों की स्थिति को रिकॉर्ड करना है। यद्यपि, समय और स्मृति बाधाओं के भीतर, पूरी सटीकता के साथ यह निर्धारित करना सामान्यतः संभव नहीं है कि कौन सी चाल पत्थरों के समूह के 'जीवन' को प्रभावित कर सकती है। इसका तात्पर्य यह है कि किन कदमों पर विचार करना है, इसका चयन करने के लिए कुछ अनुमान लागू किया जाना चाहिए। कुल प्रभाव यह है कि किसी भी कार्यक्रम के लिए, खेलने की गति और जीवन और मृत्यु पढ़ने की क्षमताओं के बीच व्यापार-बंद होता है।
गो प्लेयर के लिए मुख्य चिंताओं में से यह है कि पत्थरों के किन समूहों को जीवित रखा जा सकता है और किसे पकड़ा जा सकता है। समस्याओं के इस सामान्य वर्ग को जीवन और मृत्यु के रूप में जाना जाता है। ज्ञान-आधारित एआई सिस्टम ने कभी-कभी बोर्ड पर समूहों के जीवन और मृत्यु की स्थिति को समझने का प्रयास किया। सबसे सीधा तरीका उन चालों पर पेड़ की खोज करना है जो संभावित रूप से संबंधित पत्थरों को प्रभावित करते हैं, और फिर खेल की मुख्य पंक्ति के अंत में पत्थरों की स्थिति को रिकॉर्ड करना है। यद्यपि, समय और स्मृति बाधाओं के भीतर, पूरी सटीकता के साथ यह निर्धारित करना सामान्यतः संभव नहीं है कि कौन सी चाल पत्थरों के समूह के 'जीवन' को प्रभावित कर सकती है। इसका तात्पर्य यह है कि किन कदमों पर विचार करना है, इसका चयन करने के लिए कुछ अनुमान लागू किया जाना चाहिए। कुल प्रभाव यह है कि किसी भी कार्यक्रम के लिए, खेलने की गति और जीवन और मृत्यु पढ़ने की क्षमताओं के बीच व्यापार-बंद होता है।


== राज्य का प्रतिनिधित्व ==
== राज्य का प्रतिनिधित्व ==
मुद्दा जिससे सभी गो कार्यक्रमों को निपटना चाहिए वह यह है कि खेल की वर्तमान स्थिति का प्रतिनिधित्व कैसे किया जाए। बोर्ड का प्रतिनिधित्व करने का सबसे सीधा तरीका या दो-आयामी सरणी के रूप में है, जहां सरणी में तत्व बोर्ड पर बिंदुओं का प्रतिनिधित्व करते हैं, और सफेद पत्थर, काले पत्थर या खाली चौराहे के अनुरूप मान ले सकते हैं। . यह संग्रहीत करने के लिए अतिरिक्त डेटा की आवश्यकता है कि कितने पत्थरों पर कब्जा कर लिया गया है, किसकी बारी है, और को नियम के कारण कौन से चौराहे अवैध हैं। सामान्यतः, मशीन लर्निंग प्रोग्राम इस सरलतम रूप में रुक जाते हैं और ऑर्गेनिक एआई को बोर्ड के अर्थ की अपनी समझ में आने देते हैं, संभवतः किसी खिलाड़ी के लिए बोर्ड को अच्छा या बुरा स्कोर करने के लिए मोंटे कार्लो प्लेआउट का उपयोग करते हैं। हालांकि, क्लासिक एआई कार्यक्रम जो सीधे मानव की रणनीति को मॉडल करने का प्रयास करते हैं, आगे बढ़ सकते हैं, जैसे कि डेटा पर परतें जैसे कि मृत माने जाने वाले पत्थर, बिना शर्त जीवित पत्थर, आपसी जीवन की सेकी अवस्था में पत्थर, इत्यादि। खेल की स्थिति का प्रतिनिधित्व.
मुद्दा जिससे सभी गो कार्यक्रमों को निपटना चाहिए वह यह है कि खेल की वर्तमान स्थिति का प्रतिनिधित्व कैसे किया जाए। बोर्ड का प्रतिनिधित्व करने का सबसे सीधा तरीका या दो-आयामी सरणी के रूप में है, जहां सरणी में तत्व बोर्ड पर बिंदुओं का प्रतिनिधित्व करते हैं, और सफेद पत्थर, काले पत्थर या खाली चौराहे के अनुरूप मान ले सकते हैं। . यह संग्रहीत करने के लिए अतिरिक्त डेटा की आवश्यकता है कि कितने पत्थरों पर कब्जा कर लिया गया है, किसकी बारी है, और को नियम के कारण कौन से चौराहे अवैध हैं। सामान्यतः, मशीन लर्निंग प्रोग्राम इस सरलतम रूप में रुक जाते हैं और ऑर्गेनिक एआई को बोर्ड के अर्थ की अपनी समझ में आने देते हैं, संभवतः किसी प्लेयर के लिए बोर्ड को अच्छा या बुरा स्कोर करने के लिए मोंटे कार्लो प्लेआउट का उपयोग करते हैं। हालांकि, क्लासिक एआई कार्यक्रम जो सीधे मानव की रणनीति को मॉडल करने का प्रयास करते हैं, आगे बढ़ सकते हैं, जैसे कि डेटा पर परतें जैसे कि मृत माने जाने वाले पत्थर, बिना शर्त जीवित पत्थर, आपसी जीवन की सेकी अवस्था में पत्थर, इत्यादि। खेल की स्थिति का प्रतिनिधित्व.


== सिस्टम डिज़ाइन ==
== सिस्टम डिज़ाइन ==
Line 77: Line 77:


=== [[अल्पमहिष्ठ]] ट्री सर्च ===
=== [[अल्पमहिष्ठ]] ट्री सर्च ===
गेम प्लेइंग सॉफ़्टवेयर बनाने के लिए [[प्रतीकात्मक एआई]] तकनीक मिनिमैक्स ट्री सर्च का उपयोग करना है। इसमें निश्चित बिंदु तक बोर्ड पर सभी काल्पनिक चालें चलाना, फिर वर्तमान खिलाड़ी के लिए उस स्थिति के मूल्य का अनुमान लगाने के लिए मूल्यांकन फ़ंक्शन का उपयोग करना सम्मिलित है। सर्वोत्तम काल्पनिक बोर्ड की ओर ले जाने वाली चाल का चयन किया जाता है, और प्रक्रिया प्रत्येक मोड़ पर दोहराई जाती है। जबकि कंप्यूटर शतरंज में पेड़ की खोज बहुत प्रभावी रही है, उन्हें कंप्यूटर गो कार्यक्रमों में कम सफलता मिली है। यह आंशिक रूप से इसलिए है क्योंकि परंपरागत रूप से गो बोर्ड के लिए प्रभावी मूल्यांकन फ़ंक्शन बनाना कठिन रहा है, और आंशिक रूप से क्योंकि प्रत्येक पक्ष द्वारा बड़ी संख्या में संभावित चालें उच्च शाखा कारक की ओर ले जा सकती हैं। इससे यह तकनीक कम्प्यूटेशनल रूप से बहुत महंगी हो जाती है। इस वजह से, कई प्रोग्राम जो बड़े पैमाने पर सर्च ट्री का उपयोग करते हैं, वे पूरे 19×19 बोर्ड के बजाय केवल छोटे 9×9 बोर्ड पर ही चल सकते हैं।
गेम प्लेइंग सॉफ़्टवेयर बनाने के लिए [[प्रतीकात्मक एआई]] तकनीक मिनिमैक्स ट्री सर्च का उपयोग करना है। इसमें निश्चित बिंदु तक बोर्ड पर सभी काल्पनिक चालें चलाना, फिर वर्तमान प्लेयर के लिए उस स्थिति के मूल्य का अनुमान लगाने के लिए मूल्यांकन फ़ंक्शन का उपयोग करना सम्मिलित है। सर्वोत्तम काल्पनिक बोर्ड की ओर ले जाने वाली चाल का चयन किया जाता है, और प्रक्रिया प्रत्येक मोड़ पर दोहराई जाती है। जबकि कंप्यूटर चैस में पेड़ की खोज बहुत प्रभावी रही है, उन्हें कंप्यूटर गो कार्यक्रमों में कम सफलता मिली है। यह आंशिक रूप से इसलिए है क्योंकि परंपरागत रूप से गो बोर्ड के लिए प्रभावी मूल्यांकन फ़ंक्शन बनाना कठिन रहा है, और आंशिक रूप से क्योंकि प्रत्येक पक्ष द्वारा बड़ी संख्या में संभावित चालें उच्च शाखा कारक की ओर ले जा सकती हैं। इससे यह तकनीक कम्प्यूटेशनल रूप से बहुत महंगी हो जाती है। इस वजह से, कई प्रोग्राम जो बड़े पैमाने पर सर्च ट्री का उपयोग करते हैं, वे पूरे 19×19 बोर्ड के बजाय केवल छोटे 9×9 बोर्ड पर ही चल सकते हैं।


ऐसी कई तकनीकें हैं, जो गति और मेमोरी दोनों के संदर्भ में खोज पेड़ों के प्रदर्शन में काफी सुधार कर सकती हैं। अल्फा-बीटा प्रूनिंग, [[ प्रमुख विविधता खोज |प्रमुख विविधता खोज]] और [[एमटीडी(एफ)]] (एफ) जैसी प्रूनिंग तकनीकें ताकत के नुकसान के बिना प्रभावी शाखा कारक को कम कर सकती हैं। जीवन और मृत्यु जैसे सामरिक क्षेत्रों में, गो विशेष रूप से [[स्थानान्तरण तालिका]] जैसी कैशिंग तकनीकों के लिए उत्तरदायी है। ये बार-बार किए जाने वाले प्रयास की मात्रा को कम कर सकते हैं, खासकर जब इसे पुनरावृत्तीय गहनता दृष्टिकोण के साथ जोड़ा जाए। ट्रांसपोज़िशन टेबल में पूर्ण आकार के गो बोर्ड को तुरंत संग्रहीत करने के लिए, गणितीय रूप से सारांशित करने के लिए [[हैश फंकशन]] तकनीक सामान्यतः आवश्यक होती है। ज़ोब्रिस्ट हैशिंग गो कार्यक्रमों में बहुत लोकप्रिय है क्योंकि इसमें टकराव की दर कम है, और स्क्रैच से गणना करने के बजाय इसे केवल दो ्सओआर के साथ प्रत्येक चाल पर पुनरावृत्त रूप से अपडेट किया जा सकता है। इन प्रदर्शन-बढ़ाने वाली तकनीकों का उपयोग करते हुए भी, पूर्ण आकार के बोर्ड पर पूर्ण ट्री सर्च अभी भी बेहद धीमी है। बड़ी मात्रा में डोमेन विशिष्ट प्रूनिंग तकनीकों का उपयोग करके खोजों को तेज किया जा सकता है, जैसे कि उन चालों पर विचार न करना जहां आपका प्रतिद्वंद्वी पहले से ही मजबूत है, और चयनात्मक ्सटेंशन जैसे हमेशा पत्थरों के समूहों के आगे की चालों पर विचार करना जो गो शब्द #अटारी हैं। यद्यपि, ये दोनों विकल्प महत्वपूर्ण कदम पर विचार न करने का महत्वपूर्ण जोखिम पेश करते हैं जिसने खेल के पाठ्यक्रम को बदल दिया होगा।
ऐसी कई तकनीकें हैं, जो गति और मेमोरी दोनों के संदर्भ में खोज पेड़ों के प्रदर्शन में काफी सुधार कर सकती हैं। अल्फा-बीटा प्रूनिंग, [[ प्रमुख विविधता खोज |प्रमुख विविधता खोज]] और [[एमटीडी(एफ)]] (एफ) जैसी प्रूनिंग तकनीकें ताकत के नुकसान के बिना प्रभावी शाखा कारक को कम कर सकती हैं। जीवन और मृत्यु जैसे सामरिक क्षेत्रों में, गो विशेष रूप से [[स्थानान्तरण तालिका]] जैसी कैशिंग तकनीकों के लिए उत्तरदायी है। ये बार-बार किए जाने वाले प्रयास की मात्रा को कम कर सकते हैं, खासकर जब इसे पुनरावृत्तीय गहनता दृष्टिकोण के साथ जोड़ा जाए। ट्रांसपोज़िशन टेबल में पूर्ण आकार के गो बोर्ड को तुरंत संग्रहीत करने के लिए, गणितीय रूप से सारांशित करने के लिए [[हैश फंकशन]] तकनीक सामान्यतः आवश्यक होती है। ज़ोब्रिस्ट हैशिंग गो कार्यक्रमों में बहुत लोकप्रिय है क्योंकि इसमें टकराव की दर कम है, और स्क्रैच से गणना करने के बजाय इसे केवल दो ्सओआर के साथ प्रत्येक चाल पर पुनरावृत्त रूप से अपडेट किया जा सकता है। इन प्रदर्शन-बढ़ाने वाली तकनीकों का उपयोग करते हुए भी, पूर्ण आकार के बोर्ड पर पूर्ण ट्री सर्च अभी भी बेहद धीमी है। बड़ी मात्रा में डोमेन विशिष्ट प्रूनिंग तकनीकों का उपयोग करके खोजों को तेज किया जा सकता है, जैसे कि उन चालों पर विचार न करना जहां आपका प्रतिद्वंद्वी पहले से ही मजबूत है, और चयनात्मक ्सटेंशन जैसे हमेशा पत्थरों के समूहों के आगे की चालों पर विचार करना जो गो शब्द #अटारी हैं। यद्यपि, ये दोनों विकल्प महत्वपूर्ण कदम पर विचार न करने का महत्वपूर्ण जोखिम पेश करते हैं जिसने खेल के पाठ्यक्रम को बदल दिया होगा।
Line 84: Line 84:


=== ज्ञान-आधारित प्रणालियाँ ===
=== ज्ञान-आधारित प्रणालियाँ ===
मानव नौसिखिया अक्सर मास्टर खिलाड़ियों द्वारा खेले गए पुराने खेलों के खेल रिकॉर्ड से सीखते हैं। 1990 के दशक में एआई कार्य में अक्सर गो ज्ञान के एआई मानव-शैली के अनुमान सिखाने का प्रयास सम्मिलित होता था। 1996 में, टिम क्लिंगर और डेविड मेचनर ने सर्वश्रेष्ठ एआई की शुरुआती स्तर की ताकत को स्वीकार किया और तर्क दिया कि यह हमारा विश्वास है कि गो ज्ञान का प्रतिनिधित्व करने और बनाए रखने के लिए बेहतर उपकरणों के साथ, मजबूत गो कार्यक्रमों को विकसित करना संभव होगा।<ref name="klinger-mechner">Klinger, Tim and Mechner, David. ''[https://web.archive.org/web/20070928015006/http://mechner.com/david/compgo/acg/ An Architecture for Computer Go]'' (1996)</ref> उन्होंने दो तरीके प्रस्तावित किए: पत्थरों के सामान्य विन्यास और उनकी स्थिति को पहचानना और स्थानीय लड़ाइयों पर ध्यान केंद्रित करना। 2001 में, पेपर ने निष्कर्ष निकाला कि गो कार्यक्रमों में अभी भी ज्ञान की गुणवत्ता और मात्रा दोनों की कमी है, और इसे ठीक करने से गो एआई प्रदर्शन में सुधार होगा।<ref name="Muller" />
मानव नौसिखिया अधिकांशतः मास्टर खिलाड़ियों द्वारा खेले गए पुराने खेलों के खेल रिकॉर्ड से सीखते हैं। 1990 के दशक में एआई कार्य में अधिकांशतः गो ज्ञान के एआई मानव-शैली के अनुमान सिखाने का प्रयास सम्मिलित होता था। 1996 में, टिम क्लिंगर और डेविड मेचनर ने सर्वश्रेष्ठ एआई की शुरुआती स्तर की ताकत को स्वीकार किया और तर्क दिया कि यह हमारा विश्वास है कि गो ज्ञान का प्रतिनिधित्व करने और बनाए रखने के लिए बेहतर उपकरणों के साथ, मजबूत गो कार्यक्रमों को विकसित करना संभव होगा।<ref name="klinger-mechner">Klinger, Tim and Mechner, David. ''[https://web.archive.org/web/20070928015006/http://mechner.com/david/compgo/acg/ An Architecture for Computer Go]'' (1996)</ref> उन्होंने दो तरीके प्रस्तावित किए: पत्थरों के सामान्य विन्यास और उनकी स्थिति को पहचानना और स्थानीय लड़ाइयों पर ध्यान केंद्रित करना। 2001 में, पेपर ने निष्कर्ष निकाला कि गो कार्यक्रमों में अभी भी ज्ञान की गुणवत्ता और मात्रा दोनों की कमी है, और इसे ठीक करने से गो एआई प्रदर्शन में सुधार होगा।<ref name="Muller" />


सिद्धांत रूप में, विशेषज्ञ ज्ञान के उपयोग से गो सॉफ़्टवेयर में सुधार होगा। मजबूत खेल के लिए सैकड़ों दिशानिर्देश और सामान्य नियम उच्च-स्तरीय शौकीनों और पेशेवरों दोनों द्वारा तैयार किए गए हैं। प्रोग्रामर का कार्य इन अनुमानों को लेना, उन्हें कंप्यूटर कोड में औपचारिक रूप देना और इन नियमों के लागू होने पर पहचानने के लिए पैटर्न मिलान और पैटर्न पहचान एल्गोरिदम का उपयोग करना है। इन अनुमानों को स्कोर करने में सक्षम होना भी महत्वपूर्ण है ताकि जब वे परस्पर विरोधी सलाह दें, तो सिस्टम के पास यह निर्धारित करने के तरीके हों कि कौन सा अनुमान अधिक महत्वपूर्ण है और स्थिति पर लागू होता है। अधिकांश अपेक्षाकृत सफल परिणाम गो में प्रोग्रामर के व्यक्तिगत कौशल और गो के बारे में उनके व्यक्तिगत अनुमानों से आते हैं, किन्तु औपचारिक गणितीय दावों से नहीं; वे कंप्यूटर को गो खेलने के तरीके की नकल बनाने की कोशिश कर रहे हैं। 2001 के आसपास के प्रतिस्पर्धी कार्यक्रमों में 50-100 मॉड्यूल सम्मिलित हो सकते हैं जो खेल के विभिन्न पहलुओं और रणनीतियों से निपटते हैं, जैसे कि जोसेकी।<ref name="Muller" />
सिद्धांत रूप में, विशेषज्ञ ज्ञान के उपयोग से गो सॉफ़्टवेयर में सुधार होगा। मजबूत खेल के लिए सैकड़ों दिशानिर्देश और सामान्य नियम उच्च-स्तरीय शौकीनों और पेशेवरों दोनों द्वारा तैयार किए गए हैं। प्रोग्रामर का कार्य इन अनुमानों को लेना, उन्हें कंप्यूटर कोड में औपचारिक रूप देना और इन नियमों के लागू होने पर पहचानने के लिए पैटर्न मिलान और पैटर्न पहचान एल्गोरिदम का उपयोग करना है। इन अनुमानों को स्कोर करने में सक्षम होना भी महत्वपूर्ण है ताकि जब वे परस्पर विरोधी सलाह दें, तो सिस्टम के पास यह निर्धारित करने के तरीके हों कि कौन सा अनुमान अधिक महत्वपूर्ण है और स्थिति पर लागू होता है। अधिकांश अपेक्षाकृत सफल परिणाम गो में प्रोग्रामर के व्यक्तिगत कौशल और गो के बारे में उनके व्यक्तिगत अनुमानों से आते हैं, किन्तु औपचारिक गणितीय दावों से नहीं; वे कंप्यूटर को गो खेलने के तरीके की नकल बनाने की कोशिश कर रहे हैं। 2001 के आसपास के प्रतिस्पर्धी कार्यक्रमों में 50-100 मॉड्यूल सम्मिलित हो सकते हैं जो खेल के विभिन्न पहलुओं और रणनीतियों से निपटते हैं, जैसे कि जोसेकी।<ref name="Muller" />
Line 92: Line 92:
'''मोंटे-कार्लो विधियाँ'''
'''मोंटे-कार्लो विधियाँ'''
{{Main|मोंटे-कार्लो ट्री सर्च}}
{{Main|मोंटे-कार्लो ट्री सर्च}}
हाथ से कोडित ज्ञान और खोजों का उपयोग करने का प्रमुख विकल्प मोंटे कार्लो विधियों का उपयोग है। यह संभावित चालों की सूची तैयार करके और प्रत्येक चाल के लिए परिणामी बोर्ड पर रैंडम रूप से हजारों गेम खेलकर किया जाता है। वह चाल जो वर्तमान खिलाड़ी के लिए रैंडम खेलों के सर्वोत्तम सेट की ओर ले जाती है, उसे सर्वश्रेष्ठ चाल के रूप में चुना जाता है। किसी संभावित रूप से त्रुटिपूर्ण ज्ञान-आधारित प्रणाली की आवश्यकता नहीं है। यद्यपि, क्योंकि मूल्यांकन के लिए उपयोग की जाने वाली चालें रैंडम रूप से उत्पन्न होती हैं, इसलिए यह संभव है कि चाल जो विशिष्ट प्रतिद्वंद्वी प्रतिक्रिया को छोड़कर उत्कृष्ट होगी, उसे गलती से अच्छी चाल के रूप में मूल्यांकन किया जाएगा। इसका परिणाम ऐसे कार्यक्रम हैं जो समग्र रणनीतिक दृष्टि से मजबूत हैं, किन्तु सामरिक रूप से अपूर्ण हैं।{{Citation needed|date=January 2015}} मूव जनरेशन में कुछ डोमेन ज्ञान और रैंडम विकास के शीर्ष पर खोज की गहराई का बड़ा स्तर जोड़कर इस समस्या को कम किया जा सकता है। कुछ प्रोग्राम जो मोंटे-कार्लो तकनीकों का उपयोग करते हैं वे हैं फ़्यूगो,<ref name="sourceforge.net">{{cite web|url=http://fuego.sourceforge.net/|title=Fuego}}</ref> गो v12 के कई चेहरे,<ref name="davidfotland">{{cite web|url=http://www.smart-games.com/manyfaces.html|title=Dan Level Go Software – Many Faces of Go|author=David Fotland}}</ref> लीला,<ref name="sjeng.org">{{cite web|url=http://www.sjeng.org/leela|title=Sjeng – chess, audio and misc. software}}</ref> मोगो,<ref name="lri.fr">{{Cite web |url=http://www.lri.fr/~teytaud/mogo.html |title=संग्रहीत प्रति|access-date=2008-06-03 |archive-url=https://web.archive.org/web/20080810222849/http://www.lri.fr/~teytaud/mogo.html |archive-date=2008-08-10 |url-status=dead }}</ref> क्रेजी स्टोन (सॉफ्टवेयर), MyGoFriend,<ref name="mygofriend.com">{{cite web|url=http://www.mygofriend.com/|title=MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)|url-status=dead|archive-url=https://web.archive.org/web/20101208200028/http://mygofriend.com/|archive-date=2010-12-08}}</ref> और ज़ेन.
हाथ से कोडित ज्ञान और खोजों का उपयोग करने का प्रमुख विकल्प मोंटे कार्लो विधियों का उपयोग है। यह संभावित चालों की सूची तैयार करके और प्रत्येक चाल के लिए परिणामी बोर्ड पर रैंडम रूप से हजारों गेम खेलकर किया जाता है। वह चाल जो वर्तमान प्लेयर के लिए रैंडम खेलों के सर्वोत्तम सेट की ओर ले जाती है, उसे सर्वश्रेष्ठ चाल के रूप में चुना जाता है। किसी संभावित रूप से त्रुटिपूर्ण ज्ञान-आधारित प्रणाली की आवश्यकता नहीं है। यद्यपि, क्योंकि मूल्यांकन के लिए उपयोग की जाने वाली चालें रैंडम रूप से उत्पन्न होती हैं, इसलिए यह संभव है कि चाल जो विशिष्ट प्रतिद्वंद्वी प्रतिक्रिया को छोड़कर उत्कृष्ट होगी, उसे गलती से अच्छी चाल के रूप में मूल्यांकन किया जाएगा। इसका परिणाम ऐसे कार्यक्रम हैं जो समग्र रणनीतिक दृष्टि से मजबूत हैं, किन्तु सामरिक रूप से अपूर्ण हैं।{{Citation needed|date=January 2015}} मूव जनरेशन में कुछ डोमेन ज्ञान और रैंडम विकास के शीर्ष पर खोज की गहराई का बड़ा स्तर जोड़कर इस समस्या को कम किया जा सकता है। कुछ प्रोग्राम जो मोंटे-कार्लो तकनीकों का उपयोग करते हैं वे हैं फ़्यूगो,<ref name="sourceforge.net">{{cite web|url=http://fuego.sourceforge.net/|title=Fuego}}</ref> गो v12 के कई चेहरे,<ref name="davidfotland">{{cite web|url=http://www.smart-games.com/manyfaces.html|title=Dan Level Go Software – Many Faces of Go|author=David Fotland}}</ref> लीला,<ref name="sjeng.org">{{cite web|url=http://www.sjeng.org/leela|title=Sjeng – chess, audio and misc. software}}</ref> मोगो,<ref name="lri.fr">{{Cite web |url=http://www.lri.fr/~teytaud/mogo.html |title=संग्रहीत प्रति|access-date=2008-06-03 |archive-url=https://web.archive.org/web/20080810222849/http://www.lri.fr/~teytaud/mogo.html |archive-date=2008-08-10 |url-status=dead }}</ref> क्रेजी स्टोन (सॉफ्टवेयर), MyGoFriend,<ref name="mygofriend.com">{{cite web|url=http://www.mygofriend.com/|title=MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)|url-status=dead|archive-url=https://web.archive.org/web/20101208200028/http://mygofriend.com/|archive-date=2010-12-08}}</ref> और ज़ेन.


2006 में, नई खोज तकनीक, पेड़ों पर लागू ऊपरी आत्मविश्वास सीमा (यूसीटी),<ref>{{cite web|url=http://senseis.xmp.net/?UCT|title=UCT}}</ref> इसे उत्कृष्ट परिणामों के साथ कई 9x9 मोंटे-कार्लो गो कार्यक्रमों में विकसित और लागू किया गया था। यूसीटी खेल की अधिक सफल लाइनों के साथ खोज को निर्देशित करने के लिए अब तक त्र किए गए प्ले आउट के परिणामों का उपयोग करता है, जबकि अभी भी वैकल्पिक लाइनों का पता लगाने की अनुमति देता है। बड़े 19x19 बोर्ड पर खेलने के लिए कई अन्य अनुकूलन के साथ यूसीटी तकनीक ने MoGo को सबसे मजबूत अनुसंधान कार्यक्रमों में से बना दिया है। 19x19 गो में यूसीटी विधियों के सफल प्रारंभिक अनुप्रयोगों में मोगो, क्रेज़ी स्टोन और मैंगो सम्मिलित हैं।<ref>{{cite web|url=http://www.cs.unimaas.nl/go4go/mango/|title=आम|url-status=dead |archive-url=https://web.archive.org/web/20071103202224/http://www.cs.unimaas.nl/go4go/mango/|archive-date=2007-11-03}}</ref> MoGo ने 2007 [[कंप्यूटर ओलंपियाड]] जीता और बहुत कम जटिल 9x9 गो में गुओ जुआन, 5वें डैन प्रो के खिलाफ (तीन में से) ब्लिट्ज गेम जीता। गो के कई चेहरे<ref>{{cite web|url=http://www.smart-games.com|title=स्मार्ट गेम्स|author=David Fotland}}</ref> अपने पारंपरिक ज्ञान-आधारित इंजन में यूसीटी खोज को जोड़ने के बाद 2008 कंप्यूटर ओलंपियाड जीता।
2006 में, नई खोज तकनीक, पेड़ों पर लागू ऊपरी आत्मविश्वास सीमा (यूसीटी),<ref>{{cite web|url=http://senseis.xmp.net/?UCT|title=UCT}}</ref> इसे उत्कृष्ट परिणामों के साथ कई 9x9 मोंटे-कार्लो गो कार्यक्रमों में विकसित और लागू किया गया था। यूसीटी खेल की अधिक सफल लाइनों के साथ खोज को निर्देशित करने के लिए अब तक त्र किए गए प्ले आउट के परिणामों का उपयोग करता है, जबकि अभी भी वैकल्पिक लाइनों का पता लगाने की अनुमति देता है। बड़े 19x19 बोर्ड पर खेलने के लिए कई अन्य अनुकूलन के साथ यूसीटी तकनीक ने MoGo को सबसे मजबूत अनुसंधान कार्यक्रमों में से बना दिया है। 19x19 गो में यूसीटी विधियों के सफल प्रारंभिक अनुप्रयोगों में मोगो, क्रेज़ी स्टोन और मैंगो सम्मिलित हैं।<ref>{{cite web|url=http://www.cs.unimaas.nl/go4go/mango/|title=आम|url-status=dead |archive-url=https://web.archive.org/web/20071103202224/http://www.cs.unimaas.nl/go4go/mango/|archive-date=2007-11-03}}</ref> MoGo ने 2007 [[कंप्यूटर ओलंपियाड]] जीता और बहुत कम जटिल 9x9 गो में गुओ जुआन, 5वें डैन प्रो के खिलाफ (तीन में से) ब्लिट्ज गेम जीता। गो के कई चेहरे<ref>{{cite web|url=http://www.smart-games.com|title=स्मार्ट गेम्स|author=David Fotland}}</ref> अपने पारंपरिक ज्ञान-आधारित इंजन में यूसीटी खोज को जोड़ने के बाद 2008 कंप्यूटर ओलंपियाड जीता।


मोंटे-कार्लो आधारित गो इंजनों की प्रतिष्ठा है कि वे मानव खिलाड़ियों की तुलना में टेनुकी खेलने के लिए अधिक इच्छुक हैं, स्थानीय लड़ाई जारी रखने के बजाय बोर्ड पर कहीं और चलते हैं। इन कार्यक्रमों के अस्तित्व की शुरुआत में इसे अक्सर कमजोरी के रूप में देखा जाता था।<ref>{{Cite news|url=https://www.bbc.com/news/technology-35419141|title=Facebook trains AI to beat humans at Go board game – BBC News|work=BBC News|date=27 January 2016|language=en-GB|access-date=2016-04-24}}</ref> जैसा कि कहा गया है, यह प्रवृत्ति प्रमुख परिणामों के साथ अल्फ़ागो की खेल शैली में बनी हुई है, इसलिए यह कमजोरी से अधिक विचित्रता हो सकती है।<ref name="ggg">{{cite web |url=https://gogameguru.com/alphago-shows-true-strength-3rd-victory-lee-sedol/ |title=AlphaGo shows its true strength in 3rd victory against Lee Sedol |first=David |last=Ormerod |publisher=Go Game Guru |date=12 March 2016 |access-date=12 March 2016 |archive-url=https://web.archive.org/web/20160313032049/https://gogameguru.com/alphago-shows-true-strength-3rd-victory-lee-sedol/ |archive-date=13 March 2016 |url-status=dead |df=dmy-all }}</ref>
मोंटे-कार्लो आधारित गो इंजनों की प्रतिष्ठा है कि वे मानव खिलाड़ियों की तुलना में टेनुकी खेलने के लिए अधिक इच्छुक हैं, स्थानीय लड़ाई जारी रखने के बजाय बोर्ड पर कहीं और चलते हैं। इन कार्यक्रमों के अस्तित्व की शुरुआत में इसे अधिकांशतः कमजोरी के रूप में देखा जाता था।<ref>{{Cite news|url=https://www.bbc.com/news/technology-35419141|title=Facebook trains AI to beat humans at Go board game – BBC News|work=BBC News|date=27 January 2016|language=en-GB|access-date=2016-04-24}}</ref> जैसा कि कहा गया है, यह प्रवृत्ति प्रमुख परिणामों के साथ अल्फ़ागो की खेल शैली में बनी हुई है, इसलिए यह कमजोरी से अधिक विचित्रता हो सकती है।<ref name="ggg">{{cite web |url=https://gogameguru.com/alphago-shows-true-strength-3rd-victory-lee-sedol/ |title=AlphaGo shows its true strength in 3rd victory against Lee Sedol |first=David |last=Ormerod |publisher=Go Game Guru |date=12 March 2016 |access-date=12 March 2016 |archive-url=https://web.archive.org/web/20160313032049/https://gogameguru.com/alphago-shows-true-strength-3rd-victory-lee-sedol/ |archive-date=13 March 2016 |url-status=dead |df=dmy-all }}</ref>


'''मशीन लर्निंग'''
'''मशीन लर्निंग'''
Line 107: Line 107:
== कंप्यूटर गो और अन्य फ़ील्ड ==
== कंप्यूटर गो और अन्य फ़ील्ड ==
कंप्यूटर गो अनुसंधान परिणाम अन्य समान क्षेत्रों जैसे संज्ञानात्मक विज्ञान, पैटर्न पहचान और मशीन लर्निंग पर लागू किए जा रहे हैं।<ref name="Muhammad Mohsin">Muhammad, Mohsin. [https://web.archive.org/web/20200128091728/https://revolveurdu.blogspot.com/2020/01/thinking-games.html ''Thinking games''], Artificial Intelligence 134 (2002): p150</ref> [[कॉम्बिनेटोरियल गेम थ्योरी]], अनुप्रयुक्त गणित की शाखा, कंप्यूटर गो के लिए प्रासंगिक विषय है।<ref name="Muller">{{cite journal|last=Müller|first=Martin |title=कंप्यूटर जाओ|journal=[[Artificial Intelligence (journal)|Artificial Intelligence]] |volume=134|date=January 2002|issue=1–2 |pages=148–151|doi=10.1016/S0004-3702(01)00121-7|doi-access=free}}</ref> जॉन एच. कॉनवे ने गो में एंडगेम के विश्लेषण के लिए असली संख्याओं को लागू करने का सुझाव दिया। इस विचार को एल्विन आर. बर्लेकैंप और [[डेविड वोल्फ (गणितज्ञ)]] ने अपनी पुस्तक मैथमैटिकल गो में और विकसित किया है।<ref>{{cite book |last1=Berlekamp |first1=Elwyn |author-link=Elwyn Berlekamp |last2=Wolfe |first2=David |author2-link=David Wolfe (mathematician) |date=1994 |title=Mathematical Go: Chilling Gets the Last Point |url= |location= |publisher= |page= |isbn=978-1-56881-032-4}}</ref> गो एंडगेम्स को पीएसपीएसीई-कठिन साबित किया गया है, यदि पूर्ण सर्वोत्तम चाल की गणना मनमाने ढंग से अधिकतर भरे हुए बोर्ड पर की जानी चाहिए। ट्रिपल को, क्वाड्रपल को, मोलासेस को और मूनशाइन लाइफ जैसी कुछ जटिल परिस्थितियाँ इस समस्या को कठिन बना देती हैं।<ref>{{ubl|{{cite web|url=http://senseis.xmp.net/?TripleKo|title=Triple Ko}}|{{cite web|url=http://senseis.xmp.net/?QuadrupleKo|title=Quadruple Ko}} |{{cite web|url=http://senseis.xmp.net/?MolassesKo|title=Molasses Ko}} |{{cite web|url=http://senseis.xmp.net/?MoonshineLife|title=Moonshine Life}}}}</ref> (व्यवहार में, मजबूत मोंटे कार्लो एल्गोरिदम अभी भी सामान्य गो एंडगेम स्थितियों को काफी अच्छी तरह से संभाल सकते हैं, और जीवन और मृत्यु एंडगेम समस्याओं की सबसे जटिल कक्षाएं उच्च-स्तरीय गेम में आने की संभावना नहीं है।)<ref>{{cite web|url=http://senseis.xmp.net/?ComputerGoProgramming|title=Computer Go Programming}}</ref>
कंप्यूटर गो अनुसंधान परिणाम अन्य समान क्षेत्रों जैसे संज्ञानात्मक विज्ञान, पैटर्न पहचान और मशीन लर्निंग पर लागू किए जा रहे हैं।<ref name="Muhammad Mohsin">Muhammad, Mohsin. [https://web.archive.org/web/20200128091728/https://revolveurdu.blogspot.com/2020/01/thinking-games.html ''Thinking games''], Artificial Intelligence 134 (2002): p150</ref> [[कॉम्बिनेटोरियल गेम थ्योरी]], अनुप्रयुक्त गणित की शाखा, कंप्यूटर गो के लिए प्रासंगिक विषय है।<ref name="Muller">{{cite journal|last=Müller|first=Martin |title=कंप्यूटर जाओ|journal=[[Artificial Intelligence (journal)|Artificial Intelligence]] |volume=134|date=January 2002|issue=1–2 |pages=148–151|doi=10.1016/S0004-3702(01)00121-7|doi-access=free}}</ref> जॉन एच. कॉनवे ने गो में एंडगेम के विश्लेषण के लिए असली संख्याओं को लागू करने का सुझाव दिया। इस विचार को एल्विन आर. बर्लेकैंप और [[डेविड वोल्फ (गणितज्ञ)]] ने अपनी पुस्तक मैथमैटिकल गो में और विकसित किया है।<ref>{{cite book |last1=Berlekamp |first1=Elwyn |author-link=Elwyn Berlekamp |last2=Wolfe |first2=David |author2-link=David Wolfe (mathematician) |date=1994 |title=Mathematical Go: Chilling Gets the Last Point |url= |location= |publisher= |page= |isbn=978-1-56881-032-4}}</ref> गो एंडगेम्स को पीएसपीएसीई-कठिन साबित किया गया है, यदि पूर्ण सर्वोत्तम चाल की गणना मनमाने ढंग से अधिकतर भरे हुए बोर्ड पर की जानी चाहिए। ट्रिपल को, क्वाड्रपल को, मोलासेस को और मूनशाइन लाइफ जैसी कुछ जटिल परिस्थितियाँ इस समस्या को कठिन बना देती हैं।<ref>{{ubl|{{cite web|url=http://senseis.xmp.net/?TripleKo|title=Triple Ko}}|{{cite web|url=http://senseis.xmp.net/?QuadrupleKo|title=Quadruple Ko}} |{{cite web|url=http://senseis.xmp.net/?MolassesKo|title=Molasses Ko}} |{{cite web|url=http://senseis.xmp.net/?MoonshineLife|title=Moonshine Life}}}}</ref> (व्यवहार में, मजबूत मोंटे कार्लो एल्गोरिदम अभी भी सामान्य गो एंडगेम स्थितियों को काफी अच्छी तरह से संभाल सकते हैं, और जीवन और मृत्यु एंडगेम समस्याओं की सबसे जटिल कक्षाएं उच्च-स्तरीय गेम में आने की संभावना नहीं है।)<ref>{{cite web|url=http://senseis.xmp.net/?ComputerGoProgramming|title=Computer Go Programming}}</ref>
विभिन्न कठिन संयोजक समस्याओं (किसी भी [[ एनपी कठिन |एनपी कठिन]] समस्या) को पर्याप्त बड़े बोर्ड पर गो-जैसी समस्याओं में परिवर्तित किया जा सकता है; यद्यपि, शतरंज और [[माइनस्वीपर (वीडियो गेम)]] सहित अन्य अमूर्त बोर्ड गेम के लिए भी यही सच है, जब मनमाने आकार के बोर्ड के लिए उपयुक्त रूप से सामान्यीकृत किया जाता है। एनपी-पूर्ण समस्याएँ अपने सामान्य मामले में उपयुक्त रूप से प्रोग्राम किए गए कंप्यूटरों की तुलना में बिना सहायता प्राप्त मनुष्यों के लिए आसान नहीं होती हैं: बिना सहायता प्राप्त मनुष्य हल करने में कंप्यूटर की तुलना में बहुत खराब हैं, उदाहरण के लिए, सबसेट योग समस्या के उदाहरण।<ref name="Go-Demaine-Hearn">On page 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) {{cite arXiv |author=Erik D. Demaine, Robert A. Hearn |title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory |date=2008-04-22 |eprint=cs/0106019}}</ref><ref name="Go-Crasmaru">{{cite book |author=Marcel Crasmaru |title=कंप्यूटर और खेल|chapter=On the complexity of Tsume-Go |volume=1558 |doi=10.1007/3-540-48957-6_15 |pages= 222–231 | location=London, UK |publisher=[[Springer-Verlag]] |year=1999 |series=Lecture Notes in Computer Science |isbn=978-3-540-65766-8}}</ref>
विभिन्न कठिन संयोजक समस्याओं (किसी भी [[ एनपी कठिन |एनपी कठिन]] समस्या) को पर्याप्त बड़े बोर्ड पर गो-जैसी समस्याओं में परिवर्तित किया जा सकता है; यद्यपि, चैस और [[माइनस्वीपर (वीडियो गेम)]] सहित अन्य अमूर्त बोर्ड गेम के लिए भी यही सच है, जब मनमाने आकार के बोर्ड के लिए उपयुक्त रूप से सामान्यीकृत किया जाता है। एनपी-पूर्ण समस्याएँ अपने सामान्य मामले में उपयुक्त रूप से प्रोग्राम किए गए कंप्यूटरों की तुलना में बिना सहायता प्राप्त मनुष्यों के लिए आसान नहीं होती हैं: बिना सहायता प्राप्त मनुष्य हल करने में कंप्यूटर की तुलना में बहुत खराब हैं, उदाहरण के लिए, सबसेट योग समस्या के उदाहरण।<ref name="Go-Demaine-Hearn">On page 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) {{cite arXiv |author=Erik D. Demaine, Robert A. Hearn |title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory |date=2008-04-22 |eprint=cs/0106019}}</ref><ref name="Go-Crasmaru">{{cite book |author=Marcel Crasmaru |title=कंप्यूटर और खेल|chapter=On the complexity of Tsume-Go |volume=1558 |doi=10.1007/3-540-48957-6_15 |pages= 222–231 | location=London, UK |publisher=[[Springer-Verlag]] |year=1999 |series=Lecture Notes in Computer Science |isbn=978-3-540-65766-8}}</ref>


== गो-प्लेइंग कंप्यूटर प्रोग्राम की सूची ==
== गो-प्लेइंग कंप्यूटर प्रोग्राम की सूची ==
Line 145: Line 145:
यद्यपि दो अलग-अलग कार्यक्रमों के लिए इस पर बात करने और संघर्ष को हल करने का कोई सामान्य तरीका नहीं है, फिर भी अधिकांशतः इस समस्या को रूल्स ऑफ गो#चाइनीज रूल्स, रूल्स ऑफ गो#बेसिक रूल्स|ट्रॉम्प-टेलर, या अमेरिकन गो का उपयोग करके टाला जाता है। एसोसिएशन (एजीए) के नियम जिसमें बोर्ड पर किसी भी पत्थर की स्थिति पर कोई और असहमति न होने तक खेल जारी रखना (दंड के बिना) आवश्यक है। व्यवहार में, जैसे कि केजीएस गो सर्वर पर, सर्वर दो क्लाइंट प्रोग्रामों को विशेष जीटीपी कमांड भेजकर विवाद में मध्यस्थता कर सकता है, जो यह दर्शाता है कि उन्हें तब तक पत्थर लगाना जारी रखना चाहिए जब तक कि किसी विशेष समूह (सभी मृत पत्थर) की स्थिति के बारे में कोई सवाल न हो पकड़ लिया गया है)। सीजीओएस गो सर्वर आमतौर पर प्रोग्राम को गेम के स्कोरिंग चरण तक पहुंचने से पहले ही रिजाइन कर देता है, किन्तु फिर भी ट्रॉम्प-टेलर नियमों के संशोधित संस्करण का समर्थन करता है जिसके लिए पूर्ण प्ले आउट की आवश्यकता होती है।
यद्यपि दो अलग-अलग कार्यक्रमों के लिए इस पर बात करने और संघर्ष को हल करने का कोई सामान्य तरीका नहीं है, फिर भी अधिकांशतः इस समस्या को रूल्स ऑफ गो#चाइनीज रूल्स, रूल्स ऑफ गो#बेसिक रूल्स|ट्रॉम्प-टेलर, या अमेरिकन गो का उपयोग करके टाला जाता है। एसोसिएशन (एजीए) के नियम जिसमें बोर्ड पर किसी भी पत्थर की स्थिति पर कोई और असहमति न होने तक खेल जारी रखना (दंड के बिना) आवश्यक है। व्यवहार में, जैसे कि केजीएस गो सर्वर पर, सर्वर दो क्लाइंट प्रोग्रामों को विशेष जीटीपी कमांड भेजकर विवाद में मध्यस्थता कर सकता है, जो यह दर्शाता है कि उन्हें तब तक पत्थर लगाना जारी रखना चाहिए जब तक कि किसी विशेष समूह (सभी मृत पत्थर) की स्थिति के बारे में कोई सवाल न हो पकड़ लिया गया है)। सीजीओएस गो सर्वर आमतौर पर प्रोग्राम को गेम के स्कोरिंग चरण तक पहुंचने से पहले ही रिजाइन कर देता है, किन्तु फिर भी ट्रॉम्प-टेलर नियमों के संशोधित संस्करण का समर्थन करता है जिसके लिए पूर्ण प्ले आउट की आवश्यकता होती है।


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


उपरोक्त प्रणाली का मुख्य दोष यह है कि गो#नियमसेट के कुछ नियम (जैसे कि पारंपरिक जापानी नियम) खिलाड़ियों को इन अतिरिक्त चालों के लिए दंडित करते हैं, जिससे दो कंप्यूटरों के लिए अतिरिक्त प्लेआउट का उपयोग बंद हो जाता है। फिर भी, अधिकांश आधुनिक गो प्रोग्राम मनुष्यों के विरुद्ध जापानी नियमों का समर्थन करते हैं।
उपरोक्त प्रणाली का मुख्य दोष यह है कि गो#नियमसेट के कुछ नियम (जैसे कि पारंपरिक जापानी नियम) खिलाड़ियों को इन अतिरिक्त चालों के लिए दंडित करते हैं, जिससे दो कंप्यूटरों के लिए अतिरिक्त प्लेआउट का उपयोग बंद हो जाता है। फिर भी, अधिकांश आधुनिक गो प्रोग्राम मनुष्यों के विरुद्ध जापानी नियमों का समर्थन करते हैं।
Line 152: Line 152:


== यह भी देखें ==
== यह भी देखें ==
* कंप्यूटर शतरंज
* कंप्यूटर चैस
* [[कंप्यूटर ओथेलो]]
* [[कंप्यूटर ओथेलो]]
* [[कंप्यूटर शोगी]]
* [[कंप्यूटर शोगी]]

Revision as of 04:17, 11 August 2023

This article is about आर्टिफिशियल इंटेलिजेंस में गो (गेम) का अध्ययन. For कंप्यूटर प्रोग्रामिंग लैंग्वेज, see गो (प्रोग्रामिंग लैंग्वेज).
Not to be confused with गो सॉफ्टवेयर.
Part of a series on
Go
Go board part.jpg
Game specifics
History and culture
Players and organizations
Computers and mathematics

कंप्यूटर गो आर्टिफिशियल इंटेलिजेंस (एआई) का क्षेत्र है जो कंप्यूटर प्रोग्राम बनाने के लिए समर्पित है तथा पारंपरिक विशेष प्रकार का बोर्ड गेम गो प्ले करता है। यह क्षेत्र स्पष्ट रूप से दो युगों में विभाजित है। 2015 से पूर्व उस समय के प्रोग्राम वीक थे। 1980 और 1990 के दशक के सर्वोत्तम प्रयासों से केवल ऐसे एआई उत्पन्न हुए जिन्हें प्रारंभिक व्यक्तियों द्वारा पराजित किया जा सकता था, और 2000 के दशक के प्रारम्भ के एआई सर्वोत्तम रूप से मध्यवर्ती स्तर के थे। एआई के पक्ष में 10+ स्टोन्स के हैंडीकैप्स होने पर भी प्रोफेशनल्स इन प्रोग्राम्स को डिफीट कर सकते हैं। अल्फा-बीटा मिनिमैक्स जैसे कई एल्गोरिदम, जो चेकर्स और चैस के लिए एआई के रूप में उत्तम प्रदर्शन करते थे, गो के 19x19 बोर्ड पर विफल हो गए, क्योंकि विचार करने के लिए अधिक ब्रांचिंग संभावनाएं थीं। उस समय की तकनीकों और हार्डवेयर के साथ ह्यूमन प्रोफेशनल क्वालिटी प्रोग्राम का निर्माण पहुंच से बाहर था। कुछ एआई शोधकर्ताओं ने अनुमान लगाया कि आर्टिफिशियल जनरल इंटेलिजेंस के निर्माण के बिना प्रॉब्लम को सॉल्व नहीं किया जा सकता है।

गो एल्गोरिदम में मोंटे कार्लो ट्री सर्च के एप्लीकेशन ने 2000 के दशक के उत्तरार्ध में उल्लेखनीय संशोधन प्रदान किया, जिसके साथ प्रोग्राम अंततः एडवांस्ड ऐमटर के गो रैंक और रेटिंग्स को प्राप्त करने में सक्षम हुए। हाई-डैन के ऐमटर्स और प्रोफेशनल्स अभी भी इन प्रोग्रामों की वीकनेस का लाभ प्राप्त कर सकते हैं और निरंतर विजय प्राप्त कर सकते हैं, किन्तु कंप्यूटर का प्रदर्शन मध्यवर्ती (एकल-अंक क्यू) स्तर से उन्नत हो गया है। अधिक समय से अप्राप्य माने जाने वाले सर्वश्रेष्ठ ह्यूमन प्लेयर्स को बिना किसी हैंडीकैप के डिफीट करने के अपूर्ण लक्ष्य ने नए सिरे से रूचि उत्पन्न की। मुख्य इनसाइट मशीन लर्निंग और डीप लर्निंग के एप्लीकेशन सिद्ध हुए। डीपमाइंड, गूगल अधिग्रहण है जो एआई अनुसंधान के लिए समर्पित है, जिसने 2015 में अल्फ़ागो का उत्पादन किया और 2016 में संसार के समक्ष इसकी घोषणा की। अल्फ़ागो ने 2016 में नो-हैंडीकैप मैच में 9 डैन प्रोफेशनल ली सेडोल को डिफीट किया, तत्पश्चात 2017 में के जी को डिफीट किया, जो उस समय निरंतर दो वर्षों तक विश्व नंबर 1 रैंकिंग पर अधिकारी थे। जिस प्रकार 1995 में चेकर्स और 1997 में चैस मशीनों से पराजित हो गए थे, उसी प्रकार कंप्यूटर प्रोग्राम ने अंततः 2016-2017 में मानवता के ग्रेट गो चैंपियन को प्राप्त कर लिया था। डीपमाइंड ने अल्फ़ागो को सार्वजनिक उपयोग के लिए प्रस्तावित नहीं किया, किन्तु डीपमाइंड द्वारा अल्फ़ागो और उसके वेरिएंट का वर्णन करते हुए प्रस्तावित किए गए जर्नल लेखों के आधार पर विभिन्न प्रोग्राम बनाए गए हैं।

अवलोकन और इतिहास

प्रोफेशनल गो प्लेयर गेम को अंतर्ज्ञान, रचनात्मक और रणनीतिक विचार की आवश्यकता के रूप में देखते हैं।[1][2] इसे अधिक समय से आर्टिफिशियल इंटेलिजेंस (एआई) के क्षेत्र में समष्टि चैलेंज माना जाता रहा है और चैस के सादृश्य में इसे सॉल्व करना अत्यंत कठिन होता है।[3] इस क्षेत्र के कई व्यक्तियों का मानना ​​है कि गो को चैस के सादृश्य में मानवीय विचारों की प्रतिकृति करने वाले अधिक एलिमेंट्स की आवश्यकता होती है।[4] गणितज्ञ आई. जे. गुड ने 1965 में लिखा:[5]

कंप्यूटर पर गो?- कंप्यूटर को केवल लीगल गेम के अतिरिक्त गो का उचित गेम प्ले करने के लिए तथा प्रोग्राम करने के लिए, उत्तम रणनीति के सिद्धांतों को औपचारिक बनाना, या लर्निंग प्रोग्राम डिजाइन करना आवश्यक है। चैस के सादृश्य में सिद्धांत अधिक गुणात्मक और रहस्यमय हैं, और निर्णय पर अधिक निर्भर करते हैं। इसलिए मुझे लगता है कि चैस के सादृश्य में गो का उचित गेम प्ले करने के लिए कंप्यूटर को प्रोग्राम करना और भी कठिन होगा।

2015 से पूर्व, सर्वश्रेष्ठ गो प्रोग्राम केवल गो रैंक और रेटिंग स्तर तक पहुंचने में सफल रहे।[6][7] छोटे 9×9 बोर्ड पर, कंप्यूटर ने श्रेष्ठ प्रदर्शन किया, और कुछ प्रोग्राम प्रोफेशनल प्लेयर्स के विरुद्ध अपने 9×9 गेम का अंश प्राप्त करने में सफल रहे। अल्फ़ागो से पूर्व, कुछ शोधकर्ताओं ने आशय किया था कि कंप्यूटर गो में शीर्ष मनुष्यों को कभी डिफीट नहीं कर पाएंगे।[8]

प्रारंभिक दशक

प्रथम गो प्रोग्राम अल्बर्ट लिंडसे ज़ोब्रिस्ट द्वारा 1968 में पैटर्न रिकग्निशन पर उनकी थीसिस के अंश के रूप में लिखा गया था।[9] इसने क्षेत्र का अनुमान लगाने के लिए प्रभाव फ़ंक्शन (सांख्यिकी) और गो नियम को ज्ञात करने के लिए ज़ोब्रिस्ट हैशिंग को प्रारम्भ किया था।

अप्रैल 1981 में, जोनाथन के मिलन ने बाइट (पत्रिका) में लेख प्रकाशित किया, जिसमें 15x15 बोर्ड के साथ गो प्रोग्राम वैली पर विचार किया गया, जो KIM-1 माइक्रो कंप्यूटर के 1K रैम के भीतर फिट होता है।[10] ब्रूस एफ. वेबस्टर ने नवंबर 1984 में पत्रिका में लेख प्रकाशित किया था जिसमें मैकफोर्थ सोर्स सहित एप्पल मैकिंटोश के लिए लिखे गए गो प्रोग्राम पर विचार किया गया था।[11] गो के प्रोग्राम वीक थे; 1983 के लेख में अनुमान लगाया गया था कि वे अधिकतम 20 क्यू के समान थे, जो अनुभवहीन नोविस प्लेयर की रेटिंग है, और अधिकांशतः स्वयं को छोटे बोर्डों तक ही सीमित रखते थे।[12] हार्डवेयर में पर्याप्त संशोधन के पश्चात, 2003 में 19x19 आकार के बोर्ड पर इंटरनेट गो सर्वर (आईजीएस) पर प्ले करने वाले एआई की स्ट्रेंथ लगभग 20-15 क्यू थी।[13]

1998 में, स्ट्रांग प्लेयर्स 25-30 स्टोन्स का हैंडीकैप देकर कंप्यूटर प्रोग्राम को बीट करने में सक्षम थे, ऐसे बड़े हैंडीकैप्स जो कुछ ह्यूमन प्लेयर्स ने कभी भी देखे नहीं होंगे। 1994 विश्व कंप्यूटर गो चैंपियनशिप में यह स्थिति थी जहां विनिंग प्रोग्राम, गो इंटेलेक्ट, 15-स्टोन हैंडीकैप प्राप्त करते हुए युवा प्लयेरों के विरुद्ध सभी तीनों गेम में पराजित हो गया था।[14] सामान्यतः, जो प्लयेर किसी प्रोग्राम की वीकनेस को समझते हैं और उनका लाभ प्राप्त करते हैं, वे बड़े हैंडीकैप्स के पश्चात भी विजयी हो सकते हैं।[15]

2007-2014: मोंटे कार्लो ट्री सर्च

2006 में (2007 में प्रकाशित लेख के साथ), रेमी कूलॉम ने नया एल्गोरिदम प्रस्तुत किया जिसे उन्होंने मोंटे कार्लो ट्री सर्च कहा।[16] इसमें, सदैव की भाँति संभावित भविष्य का गेम ट्री बनाया जाता है जो प्रत्येक चाल के साथ ब्रांच देता है। यद्यपि, कंप्यूटर रिपीटेड रैंडम प्लेआउट (अन्य समस्याओं के लिए मोंटे कार्लो रणनीतियों के समान) द्वारा ट्री की टर्मिनल लीफ को स्कोर करते हैं। इससे लाभ यह है कि ऐसे रैंडम प्लेआउट अतिशीघ्र किए जा सकते हैं। सहज आपत्ति यह है कि रैंडम प्लेआउट किसी स्थिति के वास्तविक मूल्य के अनुरूप नहीं हैं तथा यह प्रक्रिया के लिए उतनी घातक नहीं निकली जितनी अपेक्षित थी; एल्गोरिदम के ट्री सर्च पक्ष को भविष्य के उचित गेम ट्री को फाइंड करने के लिए पर्याप्त रूप से व्यवस्थित किया गया है। इस पद्धति पर आधारित MoGo और Fuego जैसे प्रोग्रामों में पूर्व क्लासिक एआई के सादृश्य में श्रेष्ठ प्रदर्शन देखा गया है। सर्वश्रेष्ठ प्रोग्राम विशेष रूप से छोटे 9x9 बोर्ड पर उत्तम प्रदर्शन कर सकते हैं, जिसमें अन्वेषण करने की संभावनाएं कम होती हैं। 2009 में, प्रथम ऐसा प्रोग्राम आया जो 19x19 बोर्ड पर केजीएस गो सर्वर पर निम्न गो रैंक और रेटिंग्स तक पहुंच सकता था और उसे बनाए रख सकता था।

2010 में, फ़िनलैंड में 2010 यूरोपीय गो कांग्रेस में, मोगोटीडब्ल्यू ने कैटालिन तारनु (5p) के विरुद्ध 19x19 गो गेम प्ले किया था। मोगोटीडब्ल्यू को सेवेन-स्टोन का हैंडीकैप प्राप्त हुआ और जिससे उसकी विजय हुई।[17]

2011 में, ज़ेन (सॉफ़्टवेयर) प्रति चाल 15 सेकंड के गेम को प्ले करके, सर्वर केजीएस पर 5 डैन तक पहुंच गया। जो अकाउंट उस रैंक तक पहुंच गया वह 26-कोर मशीन पर रन करने वाले ज़ेन के क्लस्टर संस्करण का उपयोग करता है।[18]

2012 में, ज़ेन ने मसाकी ताकेमिया (9p) को फाइव स्टोन्स हैंडीकैप में 11 अंकों से बीट किया, इसके पश्चात फोर स्टोन्स हैंडीकैप में 20 अंकों से विजय प्राप्त की।[19]

2013 में, क्रेजी स्टोन (सॉफ्टवेयर) ने फोर स्टोन्स हैंडीकैप में 19×19 गेम में योशियो इशिदा (9पी) को बीट किया।[20]

2014 कोडसेंट्रिक गो चैलेंज, सम 19x19 गेम में सर्वश्रेष्ठ पांच मैच, क्रेज़ी स्टोन और फ्रांज-जोज़ेफ़ डिकहुट (6d) के मध्य खेला गया था। इससे पूर्व कोई भी स्ट्रांग प्लेयर समान स्थितियों पर गो प्रोग्राम के विरुद्ध गंभीर प्रतियोगिता खेलने के लिए सहमत नहीं हुआ था। फ्रांज-जोज़ेफ़ डिकहुत ने विजय प्राप्त की, यद्यपि क्रेज़ी स्टोन ने प्रथम मैच में 1.5 अंकों से विजय प्राप्त की थी।[21]

2015 के बाद: गहन शिक्षण युग

Further information: अल्फ़ागो, अल्फ़ागो के प्रति फैन हुई, अल्फ़ागो के प्रति ली सेडोल, and अल्फ़ागो के प्रति के जी

गूगल डीपमाइंड द्वारा विकसित अल्फ़ागो, पूर्व गो प्रोग्राम के सादृश्य में कंप्यूटर की स्ट्रेंथ में महत्वपूर्ण प्रगति थी। इसमें ऐसी तकनीकों का उपयोग किया गया जो डीप लर्निंग और मोंटे कार्लो ट्री सर्च को संयोजित करती हैं।[22] अक्टूबर 2015 में, इसने यूरोपीय गो चैंपियन फैन हुई को टूर्नामेंट की परिस्थितियों में फाइव आउट ऑफ़ फाइव टाइम्स डिफीट किया था।[23] मार्च 2016 में, अल्फ़ागो ने पांच में से प्रथम तीन मैचों में ली सेडोल को डिफीट किया था।[24] यह प्रथम स्थिति थी कि 9-डैन मास्टर ने बिना किसी हैंडीकैप के कंप्यूटर के विरुद्ध प्रोफेशनल गेम प्ले किया था।[25] ली ने चौथे मैच में सफलता प्राप्त की और अपनी सफलता को "अमूल्य" बताया।[26] अल्फ़ागो ने दो दिन पश्चात फ़ाइनल मैच में विजय प्राप्त की थी।[27][28] इस सफलता के साथ, अल्फ़ागो पूर्ण आकार के बोर्ड पर बिना किसी हैंडीकैप वाले गेम में 9 डैन ह्यूमन प्रोफेशनल को डिफीट करने वाला प्रथम प्रोग्राम बन गया।

मई 2017 में, अल्फ़ागो ने फ़्यूचर ऑफ़ गो समिट के समय तीन-गेम मैच में के जी को बीट किया, जो उस समय विश्व में शीर्ष स्थान पर था।[29][30][31]

अक्टूबर 2017 में, डीपमाइंड ने अल्फ़ागो का नया संस्करण प्रस्तुत किया, जिसे केवल सेल्फ प्ले के माध्यम से प्रशिक्षित किया गया था, जिसने 100 में से 89 गेम में के जी संस्करण को बीट करते हुए सभी पूर्व संस्करणों को पीछे कर दिया था।[32]

अल्फ़ागो के मूल सिद्धांत नेचर जर्नल में प्रकाशित होने के पश्चात, अन्य टीमें हाई-लेवल प्रोग्राम्स प्रस्तुत करने में सक्षम हो गई हैं। गो एआई पर कार्य में बड़े स्तर पर अल्फ़ागो के निर्माण के लिए उपयोग की जाने वाली तकनीकों का अनुकरण सम्मिलित है, जो अन्य सभी वस्तुओं के सादृश्य में अत्यधिक प्रबल सिद्ध हुआ है। 2017 तक, ज़ेन (सॉफ़्टवेयर) और टेनसेंट के प्रोजेक्ट फाइन आर्ट (सॉफ़्टवेयर) दोनों कुछ समय के लिए हाई-लेवल प्रोफेशनल्स को डिफीट करने में सक्षम थे। इसके साथ ही ओपन सोर्स लीला जीरो इंजन भी बनाया गया था।

क्लासिक एआई के लिए स्ट्रेटेजी और प्रदर्शन के चैलेंजेज

अधिक समय तक, यह व्यापक रूप से माना जाता था कि कंप्यूटर गो कंप्यूटर चैस से वास्तविक रूप से भिन्न समस्या उत्पन्न करता है। कई लोगों ने स्ट्रांग गो-प्लेइंग प्रोग्राम पर विचार किया जिसे सामान्य आर्टिफिशियल इंटेलिजेंस प्रौद्योगिकी में मूलभूत प्रगति के परिणामस्वरूप केवल सुदूर भविष्य में ही प्राप्त किया जा सकता है। जिन लोगों ने समस्या को व्यवहार्य माना, उनका मानना ​​था कि मानव विशेषज्ञों के विरुद्ध प्रभावी होने के लिए डोमेन ज्ञान की आवश्यकता होगी। इसलिए, उस समय के कंप्यूटर गो विकास प्रयास का बड़ा भाग मानव-जैसे विशेषज्ञ ज्ञान का प्रतिनिधित्व करने और सामरिक प्रकृति के प्रश्नों के उत्तर देने के लिए इसे लोकल सर्च के साथ संयोजित करने पर केंद्रित था। इसका परिणाम ऐसे प्रोग्राम थे जिन्होंने कई विशिष्ट स्थितियों को उत्तम प्रकार से संभाला किन्तु गेम के समग्र ऑपरेशन में उनकी वीकनेस अधिक स्पष्ट थीं। इसके अतिरिक्त, इन क्लासिकल प्रोग्रामों को उपलब्ध कंप्यूटिंग पावर में वृद्धि से प्रायः कुछ भी प्राप्त नहीं हुआ। इस प्रकार क्षेत्र में प्रगति सामान्यतः मंद थी।

बोर्ड का आकार

बड़े बोर्ड (19×19, 361 इंटेरसेक्शन्स) को अधिकांशतः प्राथमिक कारणों के रूप में जाना जाता है कि स्ट्रांग प्रोग्राम क्रिएट करना कठिन क्यों है। बड़े बोर्ड का आकार अल्फा-बीटा प्रूनिंग को महत्वपूर्ण सर्च एक्सटेंशन अथवा प्रूनिंग (डिसीजन ट्री) अनुमान के बिना डीप लुक-अहेड प्राप्त करने से अवरोधित करता है।

2002 में, मिगोस (मिनी गो सॉल्वर) नामक कंप्यूटर प्रोग्राम ने 5×5 बोर्ड के लिए गो गेम को पूर्ण रूप से सॉल्व कर दिया। ब्लैक विजय प्राप्त करता है, पूर्ण बोर्ड पर अधिकार कर लेता है।[33]

मूव विकल्पों की संख्या

चैस से उपमा प्रारम्भ रखते हुए, गो मूव्स गेम के नियमों द्वारा सीमित नहीं हैं। चैस में प्रथम मूव के लिए प्लेयर के निकट बीस विकल्प होते हैं। गो प्लेयर समरूपता को ध्यान में रखते हुए 55 भिन्न-भिन्न लीगल मूव्स के विकल्प के साथ प्रारम्भ करते हैं। समरूपता के खंडित होने पर इस संख्या में तीव्रता से वृद्धि होती है, और शीघ्र ही बोर्ड के प्रायः सभी 361 पॉइंट्स को इवैल्यूऐट करना चाहिए।

इवैल्यूएशन फंक्शन

गेम का सबसे मूल कार्य बोर्ड की स्थिति का आकलन करना है: किस साइड का पक्ष लिया जाता है, और कितना? चैस में, ट्री में भविष्य की कई स्थितियाँ पक्ष के लिए प्रत्यक्ष विजय होती है, और बोर्डों के निकट सिंपल मटेरियल काउंटिंग में इवैल्यूएशन के लिए उचित अनुमान होता है, साथ ही पौन स्ट्रक्चर जैसे कुछ निश्चित कारक भी होते हैं। ऐसा भविष्य जहां पक्ष ने बिना किसी लाभ के अपनी रानी को लुप्त कर दिया है, वह स्पष्ट रूप से दूसरे साइड के पक्ष में है। इस प्रकार के पोज़िशनल इवैल्यूएशन नियमों को गो पर कुशलतापूर्वक प्रस्तावित नहीं किया जा सकता है। गो पोज़िशन का मान यह निर्धारित करने के लिए समष्टि विश्लेषण पर निर्भर करता है कि समूह जीवित है अथवा नहीं, कौन से स्टोन्स को एक-दूसरे से संयोजित किया जा सकता है, और अनुमान लगाया जा सकता है कि स्ट्रांग पोज़िशन का कितना प्रभाव है, या कितना वीक पोज़िशन का प्रभाव हो सकता है जिससे अटैक किया जा सकता है। प्लेस्ड स्टोन्स का शीघ्र प्रभाव नहीं हो सकता है, किन्तु कई मूव्स के पश्चात पूर्व-निरीक्षण में अत्यधिक महत्वपूर्ण हो सकता है क्योंकि बोर्ड के अन्य क्षेत्र आकार लेते हैं।

बोर्ड स्टेट्स के पुअर इवैल्यूएशन के कारण एआई को उन पदों की ओर कार्य करना होता है जो अनुचित प्रकार से मानते हैं कि वे इसके पक्ष में हैं, किन्तु वास्तव में ऐसा नहीं है।

लाइफ और डेथ

गो प्लेयर के लिए मुख्य चिंताओं में से यह है कि पत्थरों के किन समूहों को जीवित रखा जा सकता है और किसे पकड़ा जा सकता है। समस्याओं के इस सामान्य वर्ग को जीवन और मृत्यु के रूप में जाना जाता है। ज्ञान-आधारित एआई सिस्टम ने कभी-कभी बोर्ड पर समूहों के जीवन और मृत्यु की स्थिति को समझने का प्रयास किया। सबसे सीधा तरीका उन चालों पर पेड़ की खोज करना है जो संभावित रूप से संबंधित पत्थरों को प्रभावित करते हैं, और फिर खेल की मुख्य पंक्ति के अंत में पत्थरों की स्थिति को रिकॉर्ड करना है। यद्यपि, समय और स्मृति बाधाओं के भीतर, पूरी सटीकता के साथ यह निर्धारित करना सामान्यतः संभव नहीं है कि कौन सी चाल पत्थरों के समूह के 'जीवन' को प्रभावित कर सकती है। इसका तात्पर्य यह है कि किन कदमों पर विचार करना है, इसका चयन करने के लिए कुछ अनुमान लागू किया जाना चाहिए। कुल प्रभाव यह है कि किसी भी कार्यक्रम के लिए, खेलने की गति और जीवन और मृत्यु पढ़ने की क्षमताओं के बीच व्यापार-बंद होता है।

राज्य का प्रतिनिधित्व

मुद्दा जिससे सभी गो कार्यक्रमों को निपटना चाहिए वह यह है कि खेल की वर्तमान स्थिति का प्रतिनिधित्व कैसे किया जाए। बोर्ड का प्रतिनिधित्व करने का सबसे सीधा तरीका या दो-आयामी सरणी के रूप में है, जहां सरणी में तत्व बोर्ड पर बिंदुओं का प्रतिनिधित्व करते हैं, और सफेद पत्थर, काले पत्थर या खाली चौराहे के अनुरूप मान ले सकते हैं। . यह संग्रहीत करने के लिए अतिरिक्त डेटा की आवश्यकता है कि कितने पत्थरों पर कब्जा कर लिया गया है, किसकी बारी है, और को नियम के कारण कौन से चौराहे अवैध हैं। सामान्यतः, मशीन लर्निंग प्रोग्राम इस सरलतम रूप में रुक जाते हैं और ऑर्गेनिक एआई को बोर्ड के अर्थ की अपनी समझ में आने देते हैं, संभवतः किसी प्लेयर के लिए बोर्ड को अच्छा या बुरा स्कोर करने के लिए मोंटे कार्लो प्लेआउट का उपयोग करते हैं। हालांकि, क्लासिक एआई कार्यक्रम जो सीधे मानव की रणनीति को मॉडल करने का प्रयास करते हैं, आगे बढ़ सकते हैं, जैसे कि डेटा पर परतें जैसे कि मृत माने जाने वाले पत्थर, बिना शर्त जीवित पत्थर, आपसी जीवन की सेकी अवस्था में पत्थर, इत्यादि। खेल की स्थिति का प्रतिनिधित्व.

सिस्टम डिज़ाइन

ऐतिहासिक रूप से, गो एआई की समस्या से निपटने के लिए प्रतीकात्मक आर्टिफिशियल इंटेलिजेंस तकनीकों का उपयोग किया गया है। 2000 के दशक में कृत्रिम तंत्रिका नेटवर्क को वैकल्पिक दृष्टिकोण के रूप में आज़माया जाने लगा, क्योंकि उन्हें अत्यधिक कंप्यूटिंग शक्ति की आवश्यकता थी जो कि पहले के दशकों में पहुँचना महंगा से असंभव था। ये दृष्टिकोण उच्च शाखा कारक वाले गो गेम की समस्याओं और कई अन्य कठिनाइयों को कम करने का प्रयास करते हैं।

किसी कार्यक्रम को मात्र विकल्प यह चुनना होता है कि अपना अगला पत्थर कहाँ रखा जाए। यद्यपि, यह निर्णय पत्थर के पूरे बोर्ड पर पड़ने वाले प्रभावों की विस्तृत श्रृंखला और विभिन्न पत्थरों के समूहों की दूसरे के साथ होने वाली जटिल अंतःक्रियाओं के कारण कठिन हो जाता है। इस समस्या से निपटने के लिए विभिन्न वास्तुकलाएँ सामने आई हैं। लोकप्रिय तकनीकों और डिज़ाइन दर्शन में सम्मिलित हैं:

  • ट्री सर्च का कुछ रूप,
  • पैटर्न मिलान और ज्ञान-आधारित प्रणाली,
  • मोंटे कार्लो विधियों का अनुप्रयोग,
  • मशीन लर्निंग का उपयोग.

अल्पमहिष्ठ ट्री सर्च

गेम प्लेइंग सॉफ़्टवेयर बनाने के लिए प्रतीकात्मक एआई तकनीक मिनिमैक्स ट्री सर्च का उपयोग करना है। इसमें निश्चित बिंदु तक बोर्ड पर सभी काल्पनिक चालें चलाना, फिर वर्तमान प्लेयर के लिए उस स्थिति के मूल्य का अनुमान लगाने के लिए मूल्यांकन फ़ंक्शन का उपयोग करना सम्मिलित है। सर्वोत्तम काल्पनिक बोर्ड की ओर ले जाने वाली चाल का चयन किया जाता है, और प्रक्रिया प्रत्येक मोड़ पर दोहराई जाती है। जबकि कंप्यूटर चैस में पेड़ की खोज बहुत प्रभावी रही है, उन्हें कंप्यूटर गो कार्यक्रमों में कम सफलता मिली है। यह आंशिक रूप से इसलिए है क्योंकि परंपरागत रूप से गो बोर्ड के लिए प्रभावी मूल्यांकन फ़ंक्शन बनाना कठिन रहा है, और आंशिक रूप से क्योंकि प्रत्येक पक्ष द्वारा बड़ी संख्या में संभावित चालें उच्च शाखा कारक की ओर ले जा सकती हैं। इससे यह तकनीक कम्प्यूटेशनल रूप से बहुत महंगी हो जाती है। इस वजह से, कई प्रोग्राम जो बड़े पैमाने पर सर्च ट्री का उपयोग करते हैं, वे पूरे 19×19 बोर्ड के बजाय केवल छोटे 9×9 बोर्ड पर ही चल सकते हैं।

ऐसी कई तकनीकें हैं, जो गति और मेमोरी दोनों के संदर्भ में खोज पेड़ों के प्रदर्शन में काफी सुधार कर सकती हैं। अल्फा-बीटा प्रूनिंग, प्रमुख विविधता खोज और एमटीडी(एफ) (एफ) जैसी प्रूनिंग तकनीकें ताकत के नुकसान के बिना प्रभावी शाखा कारक को कम कर सकती हैं। जीवन और मृत्यु जैसे सामरिक क्षेत्रों में, गो विशेष रूप से स्थानान्तरण तालिका जैसी कैशिंग तकनीकों के लिए उत्तरदायी है। ये बार-बार किए जाने वाले प्रयास की मात्रा को कम कर सकते हैं, खासकर जब इसे पुनरावृत्तीय गहनता दृष्टिकोण के साथ जोड़ा जाए। ट्रांसपोज़िशन टेबल में पूर्ण आकार के गो बोर्ड को तुरंत संग्रहीत करने के लिए, गणितीय रूप से सारांशित करने के लिए हैश फंकशन तकनीक सामान्यतः आवश्यक होती है। ज़ोब्रिस्ट हैशिंग गो कार्यक्रमों में बहुत लोकप्रिय है क्योंकि इसमें टकराव की दर कम है, और स्क्रैच से गणना करने के बजाय इसे केवल दो ्सओआर के साथ प्रत्येक चाल पर पुनरावृत्त रूप से अपडेट किया जा सकता है। इन प्रदर्शन-बढ़ाने वाली तकनीकों का उपयोग करते हुए भी, पूर्ण आकार के बोर्ड पर पूर्ण ट्री सर्च अभी भी बेहद धीमी है। बड़ी मात्रा में डोमेन विशिष्ट प्रूनिंग तकनीकों का उपयोग करके खोजों को तेज किया जा सकता है, जैसे कि उन चालों पर विचार न करना जहां आपका प्रतिद्वंद्वी पहले से ही मजबूत है, और चयनात्मक ्सटेंशन जैसे हमेशा पत्थरों के समूहों के आगे की चालों पर विचार करना जो गो शब्द #अटारी हैं। यद्यपि, ये दोनों विकल्प महत्वपूर्ण कदम पर विचार न करने का महत्वपूर्ण जोखिम पेश करते हैं जिसने खेल के पाठ्यक्रम को बदल दिया होगा।

कंप्यूटर प्रतियोगिताओं के नतीजे बताते हैं कि तेजी से स्थानीयकृत सामरिक खोजों (ऊपर समझाया गया) के साथ संयुक्त उचित चालों को चुनने के लिए पैटर्न मिलान तकनीक प्रतिस्पर्धी कार्यक्रम तैयार करने के लिए पर्याप्त थीं। उदाहरण के लिए, जीएनयू गो 2008 तक प्रतिस्पर्धी था।

ज्ञान-आधारित प्रणालियाँ

मानव नौसिखिया अधिकांशतः मास्टर खिलाड़ियों द्वारा खेले गए पुराने खेलों के खेल रिकॉर्ड से सीखते हैं। 1990 के दशक में एआई कार्य में अधिकांशतः गो ज्ञान के एआई मानव-शैली के अनुमान सिखाने का प्रयास सम्मिलित होता था। 1996 में, टिम क्लिंगर और डेविड मेचनर ने सर्वश्रेष्ठ एआई की शुरुआती स्तर की ताकत को स्वीकार किया और तर्क दिया कि यह हमारा विश्वास है कि गो ज्ञान का प्रतिनिधित्व करने और बनाए रखने के लिए बेहतर उपकरणों के साथ, मजबूत गो कार्यक्रमों को विकसित करना संभव होगा।[34] उन्होंने दो तरीके प्रस्तावित किए: पत्थरों के सामान्य विन्यास और उनकी स्थिति को पहचानना और स्थानीय लड़ाइयों पर ध्यान केंद्रित करना। 2001 में, पेपर ने निष्कर्ष निकाला कि गो कार्यक्रमों में अभी भी ज्ञान की गुणवत्ता और मात्रा दोनों की कमी है, और इसे ठीक करने से गो एआई प्रदर्शन में सुधार होगा।[35]

सिद्धांत रूप में, विशेषज्ञ ज्ञान के उपयोग से गो सॉफ़्टवेयर में सुधार होगा। मजबूत खेल के लिए सैकड़ों दिशानिर्देश और सामान्य नियम उच्च-स्तरीय शौकीनों और पेशेवरों दोनों द्वारा तैयार किए गए हैं। प्रोग्रामर का कार्य इन अनुमानों को लेना, उन्हें कंप्यूटर कोड में औपचारिक रूप देना और इन नियमों के लागू होने पर पहचानने के लिए पैटर्न मिलान और पैटर्न पहचान एल्गोरिदम का उपयोग करना है। इन अनुमानों को स्कोर करने में सक्षम होना भी महत्वपूर्ण है ताकि जब वे परस्पर विरोधी सलाह दें, तो सिस्टम के पास यह निर्धारित करने के तरीके हों कि कौन सा अनुमान अधिक महत्वपूर्ण है और स्थिति पर लागू होता है। अधिकांश अपेक्षाकृत सफल परिणाम गो में प्रोग्रामर के व्यक्तिगत कौशल और गो के बारे में उनके व्यक्तिगत अनुमानों से आते हैं, किन्तु औपचारिक गणितीय दावों से नहीं; वे कंप्यूटर को गो खेलने के तरीके की नकल बनाने की कोशिश कर रहे हैं। 2001 के आसपास के प्रतिस्पर्धी कार्यक्रमों में 50-100 मॉड्यूल सम्मिलित हो सकते हैं जो खेल के विभिन्न पहलुओं और रणनीतियों से निपटते हैं, जैसे कि जोसेकी।[35]

कार्यक्रमों के कुछ उदाहरण जो विशेषज्ञ ज्ञान पर बहुत अधिक निर्भर हैं, वे हैं हैंडटॉक (जिसे बाद में गोएमेट के नाम से जाना गया), द मेनी फेसेस ऑफ गो, गो इंटेलेक्ट और गो++, जिनमें से प्रत्येक को किसी समय दुनिया का सबसे अच्छा गो प्रोग्राम माना गया है। यद्यपि, इन तरीकों से अंततः कम रिटर्न मिला, और वास्तव में पूर्ण आकार के बोर्ड पर कभी भी मध्यवर्ती स्तर से आगे नहीं बढ़ पाया। विशेष समस्या समग्र खेल रणनीति थी। भले ही विशेषज्ञ प्रणाली पैटर्न को पहचानती है और जानती है कि स्थानीय झड़प को कैसे खेलना है, यह भविष्य में उभरती गहरी रणनीतिक समस्या से चूक सकती है। परिणाम ऐसा कार्यक्रम है जिसकी ताकत उसके भागों के योग से कम है; जबकि चालें व्यक्तिगत सामरिक आधार पर अच्छी हो सकती हैं, कार्यक्रम को धोखा दिया जा सकता है और बदले में बहुत अधिक देने के लिए चालाकी की जा सकती है, और खुद को समग्र रूप से खोने की स्थिति में पाया जा सकता है। जैसा कि 2001 के सर्वेक्षण में कहा गया था, केवल बुरा कदम अच्छे खेल को बर्बाद कर सकता है। पूरे गेम में प्रोग्राम का प्रदर्शन मास्टर स्तर से काफी कम हो सकता है।[35]

मोंटे-कार्लो विधियाँ

Main article: मोंटे-कार्लो ट्री सर्च

हाथ से कोडित ज्ञान और खोजों का उपयोग करने का प्रमुख विकल्प मोंटे कार्लो विधियों का उपयोग है। यह संभावित चालों की सूची तैयार करके और प्रत्येक चाल के लिए परिणामी बोर्ड पर रैंडम रूप से हजारों गेम खेलकर किया जाता है। वह चाल जो वर्तमान प्लेयर के लिए रैंडम खेलों के सर्वोत्तम सेट की ओर ले जाती है, उसे सर्वश्रेष्ठ चाल के रूप में चुना जाता है। किसी संभावित रूप से त्रुटिपूर्ण ज्ञान-आधारित प्रणाली की आवश्यकता नहीं है। यद्यपि, क्योंकि मूल्यांकन के लिए उपयोग की जाने वाली चालें रैंडम रूप से उत्पन्न होती हैं, इसलिए यह संभव है कि चाल जो विशिष्ट प्रतिद्वंद्वी प्रतिक्रिया को छोड़कर उत्कृष्ट होगी, उसे गलती से अच्छी चाल के रूप में मूल्यांकन किया जाएगा। इसका परिणाम ऐसे कार्यक्रम हैं जो समग्र रणनीतिक दृष्टि से मजबूत हैं, किन्तु सामरिक रूप से अपूर्ण हैं।[citation needed] मूव जनरेशन में कुछ डोमेन ज्ञान और रैंडम विकास के शीर्ष पर खोज की गहराई का बड़ा स्तर जोड़कर इस समस्या को कम किया जा सकता है। कुछ प्रोग्राम जो मोंटे-कार्लो तकनीकों का उपयोग करते हैं वे हैं फ़्यूगो,[36] गो v12 के कई चेहरे,[37] लीला,[38] मोगो,[39] क्रेजी स्टोन (सॉफ्टवेयर), MyGoFriend,[40] और ज़ेन.

2006 में, नई खोज तकनीक, पेड़ों पर लागू ऊपरी आत्मविश्वास सीमा (यूसीटी),[41] इसे उत्कृष्ट परिणामों के साथ कई 9x9 मोंटे-कार्लो गो कार्यक्रमों में विकसित और लागू किया गया था। यूसीटी खेल की अधिक सफल लाइनों के साथ खोज को निर्देशित करने के लिए अब तक त्र किए गए प्ले आउट के परिणामों का उपयोग करता है, जबकि अभी भी वैकल्पिक लाइनों का पता लगाने की अनुमति देता है। बड़े 19x19 बोर्ड पर खेलने के लिए कई अन्य अनुकूलन के साथ यूसीटी तकनीक ने MoGo को सबसे मजबूत अनुसंधान कार्यक्रमों में से बना दिया है। 19x19 गो में यूसीटी विधियों के सफल प्रारंभिक अनुप्रयोगों में मोगो, क्रेज़ी स्टोन और मैंगो सम्मिलित हैं।[42] MoGo ने 2007 कंप्यूटर ओलंपियाड जीता और बहुत कम जटिल 9x9 गो में गुओ जुआन, 5वें डैन प्रो के खिलाफ (तीन में से) ब्लिट्ज गेम जीता। गो के कई चेहरे[43] अपने पारंपरिक ज्ञान-आधारित इंजन में यूसीटी खोज को जोड़ने के बाद 2008 कंप्यूटर ओलंपियाड जीता।

मोंटे-कार्लो आधारित गो इंजनों की प्रतिष्ठा है कि वे मानव खिलाड़ियों की तुलना में टेनुकी खेलने के लिए अधिक इच्छुक हैं, स्थानीय लड़ाई जारी रखने के बजाय बोर्ड पर कहीं और चलते हैं। इन कार्यक्रमों के अस्तित्व की शुरुआत में इसे अधिकांशतः कमजोरी के रूप में देखा जाता था।[44] जैसा कि कहा गया है, यह प्रवृत्ति प्रमुख परिणामों के साथ अल्फ़ागो की खेल शैली में बनी हुई है, इसलिए यह कमजोरी से अधिक विचित्रता हो सकती है।[45]

मशीन लर्निंग

ज्ञान-आधारित प्रणालियों का कौशल स्तर उनके प्रोग्रामर और संबंधित डोमेन विशेषज्ञों के ज्ञान से निकटता से जुड़ा हुआ है। इस सीमा ने वास्तव में मजबूत एआई को प्रोग्राम करना कठिन बना दिया है। मशीन लर्निंग तकनीकों का उपयोग करना अलग रास्ता है। इनमें, केवल चीज जिसे प्रोग्रामर्स को प्रोग्राम करने की आवश्यकता होती है वह है किसी पद के मूल्य का विश्लेषण करने के नियम और सरल स्कोरिंग एल्गोरिदम। इसके बाद सॉफ्टवेयर स्वचालित रूप से सिद्धांत रूप में पैटर्न, अनुमान और रणनीतियों की अपनी समझ उत्पन्न करेगा।

यह सामान्यतः कृत्रिम तंत्रिका नेटवर्क या आनुवंशिक एल्गोरिदम को पेशेवर खेलों के बड़े डेटाबेस की समीक्षा करने, या स्वयं या अन्य लोगों या कार्यक्रमों के खिलाफ कई गेम खेलने की अनुमति देकर किया जाता है। ये एल्गोरिदम तब इस डेटा का उपयोग अपने प्रदर्शन को बेहतर बनाने के साधन के रूप में करने में सक्षम होते हैं। मशीन लर्निंग तकनीकों का उपयोग कम महत्वाकांक्षी संदर्भ में कार्यक्रमों के विशिष्ट मापदंडों को ट्यून करने के लिए भी किया जा सकता है जो मुख्य रूप से अन्य तकनीकों पर निर्भर होते हैं। उदाहरण के लिए, क्रेजी स्टोन (सॉफ्टवेयर) एलो रेटिंग प्रणाली के सामान्यीकरण का उपयोग करके कई सौ नमूना खेलों से चाल पीढ़ी पैटर्न सीखता है।[46] इस दृष्टिकोण का सबसे प्रसिद्ध उदाहरण अल्फ़ागो है, जो पिछले एआई की तुलना में कहीं अधिक प्रभावी साबित हुआ है। इसके पहले संस्करण में, इसकी परत थी जिसने आगे के विश्लेषण के योग्य प्राथमिकता देने के लिए संभावित चालों को निर्धारित करने के लिए लाखों मौजूदा स्थितियों का विश्लेषण किया था, और दूसरी परत जिसने पहली परत से सुझाए गए संभावित चालों का उपयोग करके अपनी जीत की संभावनाओं को अनुकूलित करने का प्रयास किया था। अल्फ़ागो ने परिणामी स्थिति प्राप्त करने के लिए मोंटे कार्लो ट्री खोज का उपयोग किया। अल्फ़ागो के बाद के संस्करण, अल्फ़ागोज़ीरो ने मौजूदा गो गेम से सीखना छोड़ दिया, और इसके बजाय केवल बार-बार खेलने से ही सीखा। तंत्रिका जाल का उपयोग करने वाले अन्य पुराने कार्यक्रमों में न्यूरोगो और विनहोंटे सम्मिलित हैं।

कंप्यूटर गो और अन्य फ़ील्ड

कंप्यूटर गो अनुसंधान परिणाम अन्य समान क्षेत्रों जैसे संज्ञानात्मक विज्ञान, पैटर्न पहचान और मशीन लर्निंग पर लागू किए जा रहे हैं।[47] कॉम्बिनेटोरियल गेम थ्योरी, अनुप्रयुक्त गणित की शाखा, कंप्यूटर गो के लिए प्रासंगिक विषय है।[35] जॉन एच. कॉनवे ने गो में एंडगेम के विश्लेषण के लिए असली संख्याओं को लागू करने का सुझाव दिया। इस विचार को एल्विन आर. बर्लेकैंप और डेविड वोल्फ (गणितज्ञ) ने अपनी पुस्तक मैथमैटिकल गो में और विकसित किया है।[48] गो एंडगेम्स को पीएसपीएसीई-कठिन साबित किया गया है, यदि पूर्ण सर्वोत्तम चाल की गणना मनमाने ढंग से अधिकतर भरे हुए बोर्ड पर की जानी चाहिए। ट्रिपल को, क्वाड्रपल को, मोलासेस को और मूनशाइन लाइफ जैसी कुछ जटिल परिस्थितियाँ इस समस्या को कठिन बना देती हैं।[49] (व्यवहार में, मजबूत मोंटे कार्लो एल्गोरिदम अभी भी सामान्य गो एंडगेम स्थितियों को काफी अच्छी तरह से संभाल सकते हैं, और जीवन और मृत्यु एंडगेम समस्याओं की सबसे जटिल कक्षाएं उच्च-स्तरीय गेम में आने की संभावना नहीं है।)[50] विभिन्न कठिन संयोजक समस्याओं (किसी भी एनपी कठिन समस्या) को पर्याप्त बड़े बोर्ड पर गो-जैसी समस्याओं में परिवर्तित किया जा सकता है; यद्यपि, चैस और माइनस्वीपर (वीडियो गेम) सहित अन्य अमूर्त बोर्ड गेम के लिए भी यही सच है, जब मनमाने आकार के बोर्ड के लिए उपयुक्त रूप से सामान्यीकृत किया जाता है। एनपी-पूर्ण समस्याएँ अपने सामान्य मामले में उपयुक्त रूप से प्रोग्राम किए गए कंप्यूटरों की तुलना में बिना सहायता प्राप्त मनुष्यों के लिए आसान नहीं होती हैं: बिना सहायता प्राप्त मनुष्य हल करने में कंप्यूटर की तुलना में बहुत खराब हैं, उदाहरण के लिए, सबसेट योग समस्या के उदाहरण।[51][52]

गो-प्लेइंग कंप्यूटर प्रोग्राम की सूची

See also: गो सॉफ्टवेयर
  • अल्फ़ागो, गूगल डीपमाइंड द्वारा मशीन लर्निंग प्रोग्राम, और 9-डैन ह्यूमन गो प्लेयर के विरुद्ध नो-हैंडीकैप मैचों में जीतने वाला पहला कंप्यूटर प्रोग्राम
  • बडुजीआई, जोयॉन्ग ली का कार्यक्रम[53]
  • क्रेजी स्टोन (सॉफ्टवेयर), रेमी कूलॉम द्वारा (जापान में सैक्यो नो इगो के रूप में बेचा गया)
  • अंधकारमय जंगल, फेसबुक द्वारा
  • ललित कला (सॉफ्टवेयर), Tencent द्वारा
  • फ़्यूगो, खुला स्रोत सॉफ्टवेयर मोंटे कार्लो प्रोग्राम[36]* गोबन, सेन:टे द्वारा मैकिंटोश गो प्रोग्राम (मुफ्त गोबन ्सटेंशन की आवश्यकता है)[54]
  • जीएनयू गो, खुला स्रोत शास्त्रीय गो कार्यक्रम
  • काटागो, डेविड वू द्वारा।
  • लीला (सॉफ्टवेयर), जनता के लिए बिक्री के लिए पहला मोंटे कार्लो कार्यक्रम[38]* लीला ज़ीरो, अल्फ़ागो ज़ीरो पेपर में वर्णित प्रणाली का पुनः कार्यान्वयन[38]* द मेनी फेसेस ऑफ गो, डेविड फ़ोटलैंड द्वारा (जापान में एआई इगो के रूप में बेचा गया)[37]* MyGoFriend, फ्रैंक कार्गर का कार्यक्रम[40]* सिल्वेन जेली द्वारा MoGo; कई लोगों द्वारा समानांतर संस्करण।[55][39]* पाची, पेट्र बॉडिश द्वारा खुला स्रोत मोंटे कार्लो कार्यक्रम[56]
  • स्मार्ट गेम प्रारूप के आविष्कारक एंडर्स कीरल्फ़ द्वारा स्मार्ट गो[57]
  • स्टोन ईटर, एरिक वैन डेर वेर्फ़ द्वारा[58]
  • ज़ेन, योजी ओजिमा अकायामातो द्वारा (जापान में टेनचो नो इगोइन के रूप में बेचा गया);[59]


कंप्यूटर गो कार्यक्रमों के बीच प्रतिस्पर्धा

गो कंप्यूटर प्रोग्रामों के बीच कई वार्षिक प्रतियोगिताएं होती हैं, जिनमें कंप्यूटर ओलंपियाड में गो कार्यक्रम भी सम्मिलित हैं। केजीएस गो सर्वर पर कार्यक्रमों के बीच नियमित, कम औपचारिक प्रतियोगिताएं होती थीं[60] (मासिक) और कंप्यूटर गो सर्वर[61] (निरंतर)।

कई प्रोग्राम उपलब्ध हैं जो कंप्यूटर गो इंजनों को -दूसरे के विरुद्ध खेलने की अनुमति देते हैं; वे लगभग हमेशा गो टेक्स्ट प्रोटोकॉल (जीटीपी) के माध्यम से संचार करते हैं।

इतिहास

पहली कंप्यूटर गो प्रतियोगिता बलूत का फल द्वारा प्रायोजित थी,[62] और USENIX द्वारा पहला नियमित। वे 1984 से 1988 तक चले। इन प्रतियोगिताओं में नेमेसिस, ब्रूस विलकॉक्स का पहला प्रतिस्पर्धी गो कार्यक्रम और डेविड फोटलैंड द्वारा जी2.5 पेश किया गया, जो बाद में कॉसमॉस और द मेनी फेसेस ऑफ गो में विकसित हुआ।

कंप्यूटर गो अनुसंधान के शुरुआती चालकों में से इंग पुरस्कार था, जो ताइवानी बैंकर चांग-की में द्वारा प्रायोजित अपेक्षाकृत बड़ा धन पुरस्कार था, जो 1985 और 2000 के बीच विश्व कंप्यूटर गो कांग्रेस (या इंग कप) में सालाना पेश किया जाता था। इस टूर्नामेंट के विजेता को छोटे मैच में युवा खिलाड़ियों को चुनौती देने की अनुमति दी गई थी। यदि कंप्यूटर मैच जीत जाता है, तो पुरस्कार दिया जाता था और नए पुरस्कार की घोषणा की जाती थी: कम बाधा वाले खिलाड़ियों को हराने के लिए बड़ा पुरस्कार। आईएनजी पुरस्कारों की श्रृंखला या तो 1) वर्ष 2000 में समाप्त होने वाली थी या 2) जब कोई कार्यक्रम 40,000,000 नया ताइवान डॉलर के लिए बिना किसी बाधा के 1-डैन पेशेवर को हरा सकता था। आखिरी विजेता 1997 में हैंडटॉक था, जिसने तीन 11-13 साल के शौकिया 2-6 डैन के खिलाफ 11-स्टोन हैंडीकैप मैच जीतने के लिए 250,000 एनटी डॉलर का दावा किया था। 2000 में पुरस्कार समाप्त होने के समय, नौ-स्टोन हैंडीकैप मैच जीतने के लिए लावारिस पुरस्कार 400,000 एनटी डॉलर था।[63] कई अन्य बड़े क्षेत्रीय गो टूर्नामेंट (कांग्रेस) में संलग्न कंप्यूटर गो इवेंट था। यूरोपीय गो कांग्रेस ने 1987 से कंप्यूटर टूर्नामेंट को प्रायोजित किया है, और USENIX कार्यक्रम यूएस/उत्तरी अमेरिकी कंप्यूटर गो चैम्पियनशिप में विकसित हुआ, जो 1988-2000 तक यूएस गो कांग्रेस में प्रतिवर्ष आयोजित किया जाता था।

जापान ने 1995 में कंप्यूटर गो प्रतियोगिताओं को प्रायोजित करना शुरू किया। FOST कप 1995 से 1999 तक प्रतिवर्ष टोक्यो में आयोजित किया जाता था। उस टूर्नामेंट को गिफू चैलेंज द्वारा प्रतिस्थापित कर दिया गया था, जो 2003 से 2006 तक ओगाकी, गिफू में प्रतिवर्ष आयोजित किया जाता था। कंप्यूटर गो यूईसी कप 2007 से प्रतिवर्ष आयोजित किया जाता है।

कंप्यूटर-कंप्यूटर गेम में स्कोरिंग औपचारिकता

जब दो कंप्यूटर -दूसरे के विरुद्ध गेम खेलते हैं, तो आदर्श यह है कि वास्तविक मनुष्यों के किसी भी हस्तक्षेप से बचते हुए गेम को दो इंसानों के समान तरीके से खेला जाए। यद्यपि, गेम के अंत में स्कोरिंग के समय यह मुश्किल हो सकता है। मुख्य समस्या यह है कि गो प्लेइंग सॉफ़्टवेयर, जो आमतौर पर मानकीकृत गो टेक्स्ट प्रोटोकॉल (जीटीपी) का उपयोग करके संचार करता है, हमेशा पत्थरों की जीवित या मृत स्थिति के संबंध में सहमत नहीं होगा।

यद्यपि दो अलग-अलग कार्यक्रमों के लिए इस पर बात करने और संघर्ष को हल करने का कोई सामान्य तरीका नहीं है, फिर भी अधिकांशतः इस समस्या को रूल्स ऑफ गो#चाइनीज रूल्स, रूल्स ऑफ गो#बेसिक रूल्स|ट्रॉम्प-टेलर, या अमेरिकन गो का उपयोग करके टाला जाता है। एसोसिएशन (एजीए) के नियम जिसमें बोर्ड पर किसी भी पत्थर की स्थिति पर कोई और असहमति न होने तक खेल जारी रखना (दंड के बिना) आवश्यक है। व्यवहार में, जैसे कि केजीएस गो सर्वर पर, सर्वर दो क्लाइंट प्रोग्रामों को विशेष जीटीपी कमांड भेजकर विवाद में मध्यस्थता कर सकता है, जो यह दर्शाता है कि उन्हें तब तक पत्थर लगाना जारी रखना चाहिए जब तक कि किसी विशेष समूह (सभी मृत पत्थर) की स्थिति के बारे में कोई सवाल न हो पकड़ लिया गया है)। सीजीओएस गो सर्वर आमतौर पर प्रोग्राम को गेम के स्कोरिंग चरण तक पहुंचने से पहले ही रिजाइन कर देता है, किन्तु फिर भी ट्रॉम्प-टेलर नियमों के संशोधित संस्करण का समर्थन करता है जिसके लिए पूर्ण प्ले आउट की आवश्यकता होती है।

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

उपरोक्त प्रणाली का मुख्य दोष यह है कि गो#नियमसेट के कुछ नियम (जैसे कि पारंपरिक जापानी नियम) खिलाड़ियों को इन अतिरिक्त चालों के लिए दंडित करते हैं, जिससे दो कंप्यूटरों के लिए अतिरिक्त प्लेआउट का उपयोग बंद हो जाता है। फिर भी, अधिकांश आधुनिक गो प्रोग्राम मनुष्यों के विरुद्ध जापानी नियमों का समर्थन करते हैं।

ऐतिहासिक रूप से, इस समस्या को हल करने का अन्य तरीका अंतिम बोर्ड में विशेषज्ञ मानव न्यायाधीश को नियुक्त करना था। यद्यपि, यह परिणामों में व्यक्तिपरकता का परिचय देता है और जोखिम यह है कि विशेषज्ञ कार्यक्रम में देखी गई किसी चीज़ को चूक जाएगा।

यह भी देखें

संदर्भ

  1. ↑ Metz, Cade (9 March 2016). "Google के AI ने गो चैंपियन के साथ ऐतिहासिक मैच में पहला गेम जीता". WIRED.
  2. ↑ "अल्फ़ागो एक बार फिर विजयी". 10 March 2016.
  3. ↑ Bouzy, Bruno; Cazenave, Tristan (9 August 2001). "Computer Go: An AI oriented survey". Artificial Intelligence. 132 (1): 39–103. doi:10.1016/S0004-3702(01)00127-8.
  4. ↑ Johnson, George (1997-07-29), "To Test a Powerful Computer, Play an Ancient Game", The New York Times, retrieved 2008-06-16
  5. ↑ "Go, Jack Good".
  6. ↑ Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "गहरे तंत्रिका नेटवर्क और वृक्ष खोज के साथ गो के खेल में महारत हासिल करना". Nature. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.closed access
  7. ↑ Wedd, Nick. "मानव-कंप्यूटर गो चुनौतियाँ". computer-go.info. Retrieved 2011-10-28.
  8. ↑ "'Huge leap forward': Computer that mimics human brain beats professional at game of Go".
  9. ↑ Albert Zobrist (1970), Feature Extraction and Representation for Pattern Recognition and the Game of Go. Ph.D. Thesis (152 pp.), University of Wisconsin. Also published as technical report
  10. ↑ Millen, Jonathan K (April 1981). "गो गेम की प्रोग्रामिंग". Byte. p. 102. Retrieved 18 October 2013.
  11. ↑ Webster, Bruce (November 1984). "मैकिंटोश के लिए एक गो बोर्ड". Byte. p. 125. Retrieved 23 October 2013.
  12. ↑ Campbell, J A (1983). "Part III: Go Introduction". In Bramer, M A (ed.). Computer Game-Playing: Theory and Practice. Ellis Horwood Limited. p. 138. ISBN 0-85312-488-4.
  13. ↑ Shotwell, Peter (2003). जाना! एक खेल से अधिक. Tuttle Publishing. p. 164. ISBN 0-8048-3475-X.
  14. ↑ "CS-TR-339 Computer Go Tech Report". Archived from the original on 4 February 2014. Retrieved 28 January 2016.
  15. ↑ See for instance intgofed.org Archived May 28, 2008, at the Wayback Machine
  16. ↑ Rémi Coulom (2007). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search". Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. pp. 72–83. CiteSeerX 10.1.1.81.6817. ISBN 978-3-540-75537-1.
  17. ↑ "EGC 2010 Tampere News". Archived from the original on 14 August 2009. Retrieved 28 January 2016.
  18. ↑ "केजीएस खेल अभिलेखागार". Retrieved 28 January 2016.
  19. ↑ "Zen computer Go program beats Takemiya Masaki with just 4 stones!". Go Game Guru. Archived from the original on 2016-02-01. Retrieved 28 January 2016.
  20. ↑ "「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる 初の公式戦". MSN Sankei News. Archived from the original on 24 March 2013. Retrieved 27 March 2013.
  21. ↑ "codecentric go challenge – Just another WordPress site". Retrieved 28 January 2016.
  22. ↑ "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.
  23. ↑ Gibney, Elizabeth (2016). "Google AI एल्गोरिदम गो के प्राचीन गेम में महारत हासिल करता है". Nature News & Comment. 529 (7587): 445–446. Bibcode:2016Natur.529..445G. doi:10.1038/529445a. PMID 26819021. S2CID 4460235.
  24. ↑ "Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol". BBC News Online. 12 March 2016. Retrieved 12 March 2016.
  25. ↑ "Google के डीपमाइंड ने ऐतिहासिक जीत में प्रसिद्ध गो खिलाड़ी ली से-डोल को हराया". www.theverge.com. 9 March 2016. Retrieved 9 March 2016.
  26. ↑ "Artificial intelligence: Go master Lee Se-dol wins against AlphaGo program". BBC News Online. 13 March 2016. Retrieved 13 March 2016.
  27. ↑ "Google's AlphaGo AI beats Lee Se-dol again to win Go series 4-1". The Verge. 15 March 2016. Retrieved 15 March 2016.
  28. ↑ Metz, Cade (2017-05-27). "चीन में जीत के बाद, अल्फ़ागो के डिज़ाइनरों ने नई एआई की खोज की". Wired.
  29. ↑ "विश्व की गो प्लेयर रेटिंग". May 2017.
  30. ↑ "柯洁迎19岁生日 雄踞人类世界排名第一已两年" (in 中文). May 2017.
  31. ↑ Metz, Cade (2017-05-25). "Google की AlphaGo ने चीन में दूसरी जीत के साथ अपना दबदबा कायम रखा". Wired.
  32. ↑ Silver, David; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja; Guez, Arthur; Hubert, Thomas; Baker, Lucas; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fan, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis (19 October 2017). "मानव ज्ञान के बिना गो के खेल में महारत हासिल करना" (PDF). Nature. 550 (7676): 354–359. Bibcode:2017Natur.550..354S. doi:10.1038/nature24270. ISSN 0028-0836. PMID 29052630. S2CID 205261034.closed access
  33. ↑ "5x5 Go is solved". Retrieved 28 January 2016.
  34. ↑ Klinger, Tim and Mechner, David. An Architecture for Computer Go (1996)
  35. ↑ 35.0 35.1 35.2 35.3 Müller, Martin (January 2002). "कंप्यूटर जाओ". Artificial Intelligence. 134 (1–2): 148–151. doi:10.1016/S0004-3702(01)00121-7.
  36. ↑ 36.0 36.1 "Fuego".
  37. ↑ 37.0 37.1 David Fotland. "Dan Level Go Software – Many Faces of Go".
  38. ↑ 38.0 38.1 38.2 "Sjeng – chess, audio and misc. software".
  39. ↑ 39.0 39.1 "संग्रहीत प्रति". Archived from the original on 2008-08-10. Retrieved 2008-06-03.
  40. ↑ 40.0 40.1 "MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)". Archived from the original on 2010-12-08.
  41. ↑ "UCT".
  42. ↑ "आम". Archived from the original on 2007-11-03.
  43. ↑ David Fotland. "स्मार्ट गेम्स".
  44. ↑ "Facebook trains AI to beat humans at Go board game – BBC News". BBC News (in British English). 27 January 2016. Retrieved 2016-04-24.
  45. ↑ Ormerod, David (12 March 2016). "AlphaGo shows its true strength in 3rd victory against Lee Sedol". Go Game Guru. Archived from the original on 13 March 2016. Retrieved 12 March 2016.
  46. ↑ "गो गेम में मूव पैटर्न की एलो रेटिंग की गणना करना". Retrieved 28 January 2016.
  47. ↑ Muhammad, Mohsin. Thinking games, Artificial Intelligence 134 (2002): p150
  48. ↑ Berlekamp, Elwyn; Wolfe, David (1994). Mathematical Go: Chilling Gets the Last Point. ISBN 978-1-56881-032-4.
  49. ↑
  50. ↑ "Computer Go Programming".
  51. ↑ On page 11: "Crasmaru shows that it is NP-complete to determine the status of certain restricted forms of life-and-death problems in Go." (See the following reference.) Erik D. Demaine, Robert A. Hearn (2008-04-22). "Playing Games with Algorithms: Algorithmic Combinatorial Game Theory". arXiv:cs/0106019.
  52. ↑ Marcel Crasmaru (1999). "On the complexity of Tsume-Go". कंप्यूटर और खेल. Lecture Notes in Computer Science. Vol. 1558. London, UK: Springer-Verlag. pp. 222–231. doi:10.1007/3-540-48957-6_15. ISBN 978-3-540-65766-8.
  53. ↑ BaduGI
  54. ↑
  55. ↑ "सिल्वेन जेली का होम पेज". Archived from the original on 2006-11-28. Retrieved 2007-02-21.
  56. ↑ "Pachi – Board Game of Go / Weiqi / Baduk".
  57. ↑ Anders Kierulf. "स्मार्टगो".
  58. ↑ "STEENVRETER".
  59. ↑ "Zen (go program)".
  60. ↑ "Computer Go Tournaments on KGS".
  61. ↑ "9x9 Go Server". Archived from the original on 2007-01-19. Retrieved 2007-03-25.
  62. ↑ "Acorn 1984 The First Computer Go Tournament". computer-go.info.
  63. ↑ David Fotland. "विश्व कंप्यूटर गो चैंपियनशिप". Retrieved 28 January 2016.


अग्रिम पठन


बाहरी संबंध

Wikibooks has a book on the topic of: Computer Go
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कंप्यूटर_गो&oldid=249767’