बोर्ड गेम आर्टिफिशियल इंटेलिजेंस: मिनिमैक्स एल्गोरिथम: 8 कदम

2024 लेखक: John Day | [email protected]. अंतिम बार संशोधित: 2024-01-30 09:21

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

इस निर्देशयोग्य में, मैं आपको अजगर में ओथेलो (AKA रिवर्सी) के लिए AI बनाने के चरणों के बारे में बताऊंगा। इस परियोजना से निपटने से पहले आपको पाइथन में कोड करने की मध्यवर्ती समझ होनी चाहिए। इस निर्देश के लिए आपको तैयार करने के लिए यहां कुछ अच्छी वेबसाइटें दी गई हैं: w3schools या Learningpython। इस निर्देश के अंत में, आपके पास एक AI होना चाहिए जो गणना की गई चालें करेगा और अधिकांश मनुष्यों को हराने में सक्षम होना चाहिए।

चूंकि यह निर्देश मुख्य रूप से एआई बनाने के तरीके से निपटेगा, इसलिए मैं यह नहीं समझाऊंगा कि अजगर में गेम कैसे डिजाइन किया जाए। इसके बजाय, मैं उस गेम के लिए कोड दूंगा जहां एक इंसान दूसरे इंसान के खिलाफ खेल सकता है और इसे संशोधित कर सकता है ताकि आप ऐसा गेम खेल सकें जहां एक इंसान एआई के खिलाफ खेलता है।

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

अब जब हमें लॉजिस्टिक्स रास्ते से हट गया है, तो चलिए कोडिंग शुरू करते हैं!

(मैंने छवियों में कुछ नोट्स डाले हैं, इसलिए उन्हें देखना सुनिश्चित करें)

आपूर्ति

यह आसान है:

1) एक अजगर वातावरण वाला कंप्यूटर जैसे स्पाइडर या आईडीएलई

२) मेरे GitHub से ओथेलो गेम के लिए फ़ाइलें डाउनलोड करें

3) आपका दिमाग धैर्य के साथ स्थापित

चरण 1: आवश्यक फ़ाइलें डाउनलोड करें

जब आप मेरे GitHub में जाते हैं, तो आपको 5 फाइलें देखनी चाहिए। सभी 5 डाउनलोड करें और उन सभी को एक ही फ़ोल्डर में रखें। इससे पहले कि हम गेम चलाएं, स्पाइडर वातावरण में सभी फाइलें खोलें।

यहाँ फ़ाइलें क्या करती हैं:

1) ohello_gui.py यह फ़ाइल खिलाड़ियों के खेलने के लिए गेम बोर्ड बनाती है (चाहे मानव हो या कंप्यूटर)

2) ohello_game.py यह फ़ाइल गेमबोर्ड के बिना दो कंप्यूटरों को एक दूसरे के विरुद्ध चलाती है और केवल स्कोर और चाल की स्थिति दिखाती है

3) ai_template.py यह वह जगह है जहाँ आप अपना AI बनाने के लिए अपना सारा कोड डालेंगे

4) randy_ai.py यह एक पूर्वनिर्मित एआई है जो अपनी चालों को बेतरतीब ढंग से चुनता है

5) ohello_shared.py पूर्व-निर्मित कार्यों का एक समूह जिसका उपयोग आप अपना AI बनाने के लिए कर सकते हैं जैसे कि उपलब्ध चाल, स्कोर या बोर्ड स्थिति की जांच करना

6) तीन अन्य फाइलें: Puma.py, erika_5.py, और nathan.py, मेरे द्वारा बनाई गई, एरिका, और नाथन क्रमशः SHAPE प्रोग्राम से, ये अद्वितीय कोड वाले तीन अलग-अलग AI हैं

चरण 2: पायथन ओथेलो को कैसे खोलें और चलाएं

एक बार जब आप सभी फाइलें खोल लेते हैं, तो स्क्रीन के निचले दाएं कोने में, "run ohello_gui.py" टाइप करें और IPython कंसोल में एंटर दबाएं। या मैक टर्मिनल में, "पायथन othello_gui.py" टाइप करें (जब आप पाठ्यक्रम के सही फ़ोल्डर में हों)। फिर आपकी स्क्रीन पर एक बोर्ड पॉप अप होना चाहिए। यह विधा मानव बनाम मानव विधा है। प्रकाश दूसरे स्थान पर जाता है और अंधेरा पहले। अगर आप भ्रमित हैं तो मेरा वीडियो देखें। iAt शीर्ष पर, प्रत्येक रंग टाइल का स्कोर होता है। खेलने के लिए, वहां एक टाइल लगाने के लिए एक वैध चाल स्थान पर क्लिक करें और फिर अपने प्रतिद्वंद्वी को कंप्यूटर दें जो ऐसा ही करेगा और दोहराएगा।

यदि आप ओथेलो खेलना नहीं जानते हैं, तो अल्ट्रा बोर्ड वेबसाइट से इन नियमों को पढ़ें:

काला हमेशा पहले चलता है। खिलाड़ी के रंग की डिस्क को बोर्ड पर ऐसी स्थिति में रखकर एक चाल चली जाती है कि प्रतिद्वंद्वी की एक या अधिक डिस्क "बाहर-बाहर" हो जाती है। एक डिस्क या डिस्क की पंक्ति बाहर निकल जाती है जब यह विपरीत रंग की डिस्क से सिरों पर घिरी होती है। एक डिस्क किसी भी दिशा (क्षैतिज, लंबवत, विकर्ण) में एक या अधिक पंक्तियों में कितनी भी डिस्क को पछाड़ सकती है…। (उनकी वेबसाइट पर पढ़ना समाप्त करें)

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

अब जब आप किसी मित्र के साथ गेम खेल सकते हैं, तो चलिए एक ऐसा AI बनाते हैं जिससे आप खेल सकते हैं।

चरण 3: मिनिमैक्स एल्गोरिथम: परिदृश्य उत्पन्न करना

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

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

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

चरण 4: मिनिमैक्स: बोर्ड कॉन्फ़िगरेशन का मूल्यांकन

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

अब हम प्रत्येक बोर्ड राज्य बोर्ड के लिए पदों के लिए मान निर्दिष्ट कर सकते हैं। जब एआई के हिस्से पर एक स्थिति का कब्जा होता है, तो आप स्थिति के आधार पर एक निश्चित संख्या में अंक देते हैं। उदाहरण के लिए, एक बोर्ड राज्य जहां एआई का टुकड़ा कोने में है, आप 50 अंक का बोनस दे सकते हैं, लेकिन यदि यह प्रतिकूल स्थान पर था, तो टुकड़े का मान 0 हो सकता है। के सभी मूल्यों को ध्यान में रखते हुए पदों, आप बोर्ड को एक मान निर्दिष्ट करते हैं। उदाहरण के लिए, यदि एआई के कोने में एक टुकड़ा है, तो बोर्ड राज्य का स्कोर 50 हो सकता है, जबकि बीच में एआई के टुकड़े के साथ एक अन्य बोर्ड राज्य का स्कोर 10 हो सकता है।

ऐसा करने के कई तरीके हैं, और बोर्ड के टुकड़ों का मूल्यांकन करने के लिए मेरे पास तीन अलग-अलग अनुमान हैं। मैं आपको अपने खुद के प्रकार का अनुमानी बनाने के लिए प्रोत्साहित करता हूं। मैंने तीन अलग-अलग निर्माताओं द्वारा अपने जीथब पर तीन अलग-अलग एआई अपलोड किए, तीन अलग-अलग अनुमान के साथ: Puma.py, erika5.py, nathanh.py।

चरण 5: मिनिमैक्स एल्गोरिथम: सर्वश्रेष्ठ चाल चुनना

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

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

परिभाषाएँ: पैरेंट नोड - एक नोड जो इसके नीचे नोड बनाता है या बनाता है; बच्चों के नोड्स की उत्पत्ति - एक ही पैरेंट नोड से आने वाले नोड्स

खाली नोड्स प्रतिनिधित्व करते हैं कि एआई सर्वश्रेष्ठ बोर्ड राज्य में जाने के लिए कौन सा कदम उठाएगा। यह सबसे बाएं नोड के बच्चों की तुलना करने के साथ शुरू होता है: 10, -3, 5। चूंकि अधिकतम खिलाड़ी चाल करेगा, वह उस चाल का चयन करेगा जो इसे सबसे अधिक अंक देगा: 10. तो, हम फिर उसे चुनते हैं और संग्रहीत करते हैं बोर्ड स्कोर के साथ आगे बढ़ें और इसे पैरेंट नोड में लिखें। अब जबकि 10 पैरेंट नोड में है, अब मिनिमाइज़िंग प्लेयर्स की बारी है। हालाँकि, जिस नोड की हम 10 से तुलना करेंगे, वह खाली है, इसलिए न्यूनतम खिलाड़ी चुनने से पहले हमें पहले उस नोड का मूल्यांकन करना होगा। तो हम अधिकतम खिलाड़ी की बारी पर वापस जाते हैं और आसन्न नोड के बच्चों की तुलना करते हैं: 8, -2। मैक्सिमाइज़िंग 8 का चयन करेगा और हम इसे खाली पैरेंट नोड में लिखते हैं। अब जबकि एल्गोरिथम ने इसके ऊपर एक नोड के बच्चों के लिए रिक्त स्थान भरना समाप्त कर दिया है, छोटा करने वाला खिलाड़ी उन बच्चों की तुलना कर सकता है - 10 और 8 और 8 चुनें। एल्गोरिथ्म तब तक इस प्रक्रिया को दोहराता है जब तक कि पूरा पेड़ भर नहीं जाता। इस उदाहरण के अंत में, हमारे पास स्कोर 8 है। यह उच्चतम बोर्ड स्थिति है जिसे एआई यह मानने के लिए खेल सकता है कि प्रतिद्वंद्वी बेहतर खेल रहा है। तो एआई पहली चाल का चयन करेगा जो 8 बोर्ड राज्य की ओर जाता है, और यदि प्रतिद्वंद्वी बेहतर तरीके से खेलता है, तो एआई को बोर्ड राज्य 8 तक पहुंचने के लिए सभी चाल चलनी चाहिए। (मेरे चित्रों पर नोट्स का पालन करें)

मुझे पता है कि बहुत कुछ था। यदि आप उन प्रकारों में से एक हैं जिन्हें किसी को कुछ समझने के लिए आपसे बात करने की आवश्यकता है, तो यहां कुछ वीडियो हैं जिन्हें मैंने इसके पीछे के विचार को समझने में मदद करने के लिए देखा है: 1, 2, 3।

चरण 6: मिनिमैक्स एल्गोरिथम: स्यूडोकोड

मिनिमैक्स एल्गोरिथ्म के पीछे के तर्क को समझने के बाद, विकिपीडिया से इस छद्म कोड (सभी कोड के लिए सार्वभौमिक कार्य) पर एक नज़र डालें:

फंक्शन मिनिमैक्स (नोड, डेप्थ, मैक्सिमाइजिंगप्लेयर) है

यदि गहराई = 0 या नोड एक टर्मिनल नोड है तो

नोड का अनुमानी मान लौटाएं

अगर मैक्सिमाइज़िंगप्लेयर तो

मान:= −∞

नोड के प्रत्येक बच्चे के लिए do

मान: = अधिकतम (मान, न्यूनतम (बच्चा, गहराई -1, FALSE))

प्रतिलाभ की मात्रा

अन्य (* खिलाड़ी को छोटा करना *)

मूल्य:= +∞

नोड के प्रत्येक बच्चे के लिए do

मान: = न्यूनतम (मान, न्यूनतम (बच्चा, गहराई -1, TRUE))

प्रतिलाभ की मात्रा

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

यह छद्म कोड उस प्रक्रिया को पुन: प्रस्तुत कर रहा है जिसे मैंने पिछले दो चरणों में समझाया था। अब इसे एक कदम आगे बढ़ाते हैं और इसे पायथन कोड में ठीक करते हैं।

चरण 7: अपने AI को Ai_template.py. के साथ बनाना

मेरे मिनिमैक्स एआई कोड पर एक नज़र डालने से पहले, ai_template.py फ़ाइल और अंतिम चरण में हमने जिस छद्म कोड के बारे में बात की थी, उसके साथ अपना AI बनाने का प्रयास करें। एआई टेम्पलेट में दो कार्य हैं जिन्हें कहा जाता है: def minimax_min_node (बोर्ड, रंग) और def minimax_max_node (बोर्ड, रंग)। मिनीमैक्स फ़ंक्शन को स्वयं को पुनरावर्ती रूप से कॉल करने के बजाय, हमारे पास दो अलग-अलग फ़ंक्शन हैं, जो एक दूसरे को कॉल करते हैं। बोर्ड राज्यों का मूल्यांकन करने के लिए अनुमानी बनाने के लिए, आपको अपना स्वयं का कार्य बनाना होगा। ohello_shared.py फ़ाइल में एक पूर्वनिर्मित कार्य होता है जिसका उपयोग आप अपना AI बनाने के लिए कर सकते हैं।

एक बार जब आप अपना AI प्राप्त कर लें, तो इसे randy_ai.py के विरुद्ध चलाने का प्रयास करें। दो ais को एक दूसरे के विरुद्ध चलाने के लिए, मैक टर्मिनल में "python othello_gui.py (insert ai file name).py (insert file name.py") टाइप करें या "run othello_gui.py (insert ai file name).py टाइप करें। (फ़ाइल नाम डालें).py" और सुनिश्चित करें कि आप सही निर्देशिका में हैं। इसके अलावा, सटीक चरणों के लिए मेरा वीडियो देखें।

चरण 8: AI से लड़ने का समय

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