माइंड गेम्स में AI के बारे में

बहुत पहले नहीं, मुझे शोगी खेलने का शौक था। दुर्भाग्य से, यह अद्भुत खेल रूस में व्यावहारिक रूप से अज्ञात है, इसलिए जब तक मैंने अपने दोस्तों को खेलना नहीं सिखाया, मुझे कार्यक्रम के साथ खेलना था। बेशक, मैं सोच रहा था कि यह कार्यक्रम कैसे काम करता है।
नीचे बौद्धिक गेम में उपयोग किए जाने वाले कंप्यूटर एल्गोरिदम के बारे में एक छोटी कहानी है।

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


जैसा कि आप आंकड़े से देख सकते हैं, खेल का पेड़ बहुत तेजी से बढ़ता है। यदि इस तरह से पेड़ बढ़ता रहा, तो पूरे पेड़ में 9! = 362880 पत्ते होंगे।

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


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

वास्तविकता में चीजें कैसे हैं (चेकर्स और शतरंज)

यहां तक ​​कि एक स्कूली छात्र टिक-टैक-टो में एक पेड़ को पूरी तरह से सुलझा सकता है। चेकर्स में, संभावित पदों की संख्या 10 ²⁰ की संख्या से अनुमानित है। यह बहुत, बहुत अधिक है, लेकिन 2007 में सुपर कंप्यूटर सभी संभावित चालों की गणना करने में कामयाब रहा। यानी, 2007 से शुरू होकर, कोई व्यक्ति (यहां तक ​​कि सैद्धांतिक रूप से) कंप्यूटर के खिलाफ जीत नहीं सकता है।
शतरंज के साथ, निकट भविष्य में एक पूर्ण हलचल शायद ही संभव है। सभी संभावित शतरंज पदों की संख्या 10 ⁴⁶ अनुमानित है। यह संख्या इतनी बड़ी है कि इन पदों के माध्यम से छाँटने के लिए भी एक सुपर कंप्यूटर को खगोलीय समय की आवश्यकता होगी। फिर भी, शतरंज में कुछ प्रगति हुई है। हालांकि सभी पदों के माध्यम से छांटना असंभव है, लेकिन आंकड़े और स्थिति के आधार बहुत प्रभावी साबित होते हैं। यदि आपने कभी शतरंज खेलना सीखा, तो आपने शायद शाही, रानी के गामित, फिलिडोर की रक्षा या पुरानी भारतीय रक्षा के बारे में बात की। ये सभी उद्घाटन खेल की शुरुआत में लगाए जाते हैं। बात यह है कि उनकी गणना लंबे समय तक और काफी गहराई से (20 वीं चाल तक) की गई है। शतरंज में एंडगेम की गणना भी बहुत अच्छी तरह से की जाती है। एक के लिए केवल इंटरनेट की खोज करना है: "एक प्रकाश टुकड़े के खिलाफ एक किश्ती का अंत", "एक रानी के खिलाफ दो बदमाशों का एंडगेम" आदि, यह सुनिश्चित करने के लिए। यह पता चला है कि खेल के केवल मध्य भाग की गणना करने की आवश्यकता है, और वहां, जैसा कि ऊपर उल्लेख किया गया है, हेयुरेटिक्स बहुत प्रभावी हैं।
1990 के दशक के मध्य में, ऐसे कार्यक्रम बनाए गए जो विश्व चैंपियन को हरा सकते थे। एक शानदार उदाहरण मैच डीप ब्लू - कास्परोव है। अगर 1996 में कास्पारोव केवल एक गेम हार गया, लेकिन मैच जीत गया, तो 1997 में डीप ब्लू ने कास्परोव को एक अलग गेम में नहीं, बल्कि पूरे मैच में हराया।

वास्तविकता में चीजें कैसी हैं (शोगी और जाओ)

शोगी और शतरंज के बीच मुख्य अंतर यह है कि लिए गए टुकड़े खेल को नहीं छोड़ते हैं, लेकिन किसी भी समय मैदान के किसी भी वर्ग में वापस आ सकते हैं। यह सुविधा, एक बड़े क्षेत्र के आकार और आंकड़ों के एक बड़े सेट के साथ मिलकर, शोगी को अविश्वसनीय रूप से कठिन खेल बनाती है। पार्टियों की संख्या में तेजी से संख्या 10 ²²⁶ तक बढ़ जाती है, विनिमय हेयुरिस्टिक (सबसे आम) पूरी तरह से अप्रभावी हो जाता है, चूंकि एक्सचेंज केवल खेल को जटिल करते हैं, शोगी के लिए पार्टियों का आधार बनाना भी लगभग असंभव है, उनकी संख्या को देखते हुए।
कार्यक्रमों के विशाल बहुमत ऊपर वर्णित न्यूनतम रणनीति का उपयोग करते हैं और कार्यक्रमों में मुख्य अंतर स्थिति अनुमान और अनुमानी एल्गोरिदम है। कार्यक्रमों और पेशेवरों के बीच मैच अब निषिद्ध हैं ताकि पेशेवर खिलाड़ियों की गरिमा कम न हो, लेकिन समय-समय पर शोगी एसोसिएशन मैचों की अनुमति देता है। इस खेल में एआई की सबसे बड़ी उपलब्धि महिलाओं की सबसे मजबूत जीत है। इचियो शिमिज़ु ने अकारा कार्यक्रम के खिलाफ खेला। कड़ाई से बोलते हुए, अकारा एक कार्यक्रम नहीं है, लेकिन 4 स्वतंत्र इंजन हैं। सबसे अच्छे कदम पर निर्णय साधारण वोट द्वारा किया जाता है। एआई के क्षेत्र में महत्वपूर्ण प्रगति के बावजूद, कार्यक्रम का शोगी अभी तक सबसे मजबूत खिलाड़ी को हरा नहीं पा रहा है।
खेल के खेल में चीजें और भी दिलचस्प हैं। 10 वीं ¹⁷¹ में अंतिम पदों की संख्या, यह सभी विकल्पों की प्रत्यक्ष गणना को समाप्त करता है।
दुर्भाग्य से, न्यूनतम खोज पेड़ भी काफी खराब काम करता है। तथ्य यह है कि जाने में संभावित पदों की संख्या बहुत तेज़ी से बढ़ रही है और यहां तक ​​कि सुपर कंप्यूटर भी पर्याप्त गति के साथ चाल को हल नहीं कर सकते हैं। 12 चालों के लिए सबसे अच्छे कार्यक्रम "भविष्य में देख सकते हैं"। प्राप्त पदों का मूल्यांकन किया जाता है और सबसे अच्छे विकल्प चुने जाते हैं। इन विकल्पों के लिए, कार्यक्रम फिर से खेल अंतर्देशीय का विश्लेषण करना शुरू करता है, सबसे अच्छा विकल्प चुनने की कोशिश कर रहा है। और ऐसा कई बार। जाने की एक विशेषता यह है कि इस खेल में सामरिक सोच सामरिक से कहीं अधिक महत्वपूर्ण है। और भले ही कार्यक्रम एक स्थानीय सामरिक लाभ प्राप्त करता है, असली मास्टर अभी भी जीतता है।
फिर भी, प्रोग्रामरों ने एक बहुत ही मूल एल्गोरिथ्म पाया है जो कार्यक्रमों को पेशेवर स्तर पर खेलने की अनुमति देता है (सबसे मजबूत खिलाड़ियों पर जीत की कोई बात नहीं है, साथ ही साथ शोग भी)।
मुख्य विचार मोंटे कार्लो पेड़ में खोज एल्गोरिदम का उपयोग करना है। नाम से यह स्पष्ट है कि यह एक यादृच्छिक एल्गोरिदम है। जाने में इसका उपयोग कैसे किया जाता है? कार्यक्रम बेतरतीब ढंग से कई मिलियन खेलों के माध्यम से हल किया गया था जो वर्तमान स्थिति से खेला जा सकता है। इसके अलावा, प्रत्येक खेल को अंत तक खेला जाता है, कार्यक्रम चाल की लाभप्रदता की गणना करता है, केवल सीमा नियमों का पालन कर रहा है।
अंत तक लाखों गेम हारने के बाद, कार्यक्रम को पहली चाल के बाद जीतने की संभावना के बारे में कुछ आंकड़े प्राप्त होते हैं। इन आंकड़ों के अनुसार, कार्यक्रम यह तय करता है कि इस तरह के और इस तरह के कदम से 5% की संभावना के साथ एक जीत होगी, जैसे और - 3%, और इसी तरह। अगला, प्रोग्राम केवल जीतने की उच्चतम संभावना के साथ चाल का चयन करता है और एल्गोरिथ्म को दोहराता है। नतीजतन, कार्यक्रम एक ऐसी चाल चलता है जो जीत की ओर ले जाने की सबसे अधिक संभावना है।
इस पद्धति का उपयोग करके कार्यक्रम को सबसे मजबूत खिलाड़ी को हराने की अनुमति दी, हालांकि 7 पत्थरों के एक बाधा के साथ।
जल्दी या बाद में, वह क्षण आएगा जब कार्यक्रम 100% खेलों में लोगों को पीटना शुरू कर देंगे? बेशक, हम हमेशा एक बोतल है!