एआई (मिनिमैक्स एल्गोरिथम) के साथ Arduino पर टिक टीएसी को पैर की अंगुली: 3 कदम

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

इस निर्देशयोग्य में मैं आपको दिखाने जा रहा हूं कि एक Arduino का उपयोग करके AI के साथ एक टिक टैक टो गेम कैसे बनाया जाए। आप या तो Arduino के खिलाफ खेल सकते हैं या Arduino को अपने खिलाफ खेलते हुए देख सकते हैं।

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

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

चरण 1: बनाएं और खेलें

टिक टीएसी को पैर की अंगुली खेल बनाने के लिए आपको निम्नलिखित घटकों की आवश्यकता होगी:

• एक Arduino Uno
• 9 WS2812 RGB LED
• 9 पुश बटन
• कुछ तार और जम्पर केबल

फ्रिट्ज़िंग स्केच में दिखाए गए अनुसार घटकों को तार दें। फिर कोड को अपने Arduino पर अपलोड करें।

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

आप सीरियल मॉनिटर को खोलकर Arduino "थिंक" देख सकते हैं। हर संभव कदम के लिए, एल्गोरिथ्म एक रेटिंग की गणना करता है जो इंगित करता है कि क्या इस कदम से Arduino के लिए जीत (10 का मान) या हानि (-10 का मान) या ड्रॉ (0 का मान) होगा।

आप स्केच की शुरुआत में "#define DEMO_MODE" लाइन को अनकम्मेंट करके Arduino को अपने खिलाफ खेलते हुए भी देख सकते हैं। यदि आप संशोधित स्केच अपलोड करते हैं, तो Arduino पहली चाल को बेतरतीब ढंग से बनाता है और फिर प्रत्येक मोड़ में प्रत्येक खिलाड़ी के लिए सर्वोत्तम चाल निर्धारित करने के लिए मिनिमैक्स एल्गोरिथम का उपयोग करता है।

ध्यान दें कि आप Arduino के खिलाफ नहीं जीत सकते। यदि आप कोई गलती करते हैं तो प्रत्येक गेम या तो ड्रॉ पर समाप्त होगा या आप हार जाएंगे। ऐसा इसलिए है क्योंकि एल्गोरिथ्म हमेशा सर्वोत्तम संभव चाल को चुनता है। जैसा कि आप जानते होंगे कि टिक टीएसी को पैर की अंगुली का खेल हमेशा ड्रॉ में समाप्त होता है यदि दोनों खिलाड़ी कोई गलती नहीं करते हैं। डेमो मोड में, प्रत्येक गेम ड्रॉ में समाप्त होता है, क्योंकि जैसा कि हम सभी जानते हैं, कंप्यूटर कभी गलती नहीं करते;-)

चरण 2: मिनिमैक्स एल्गोरिथम

एल्गोरिथ्म में दो घटक होते हैं: एक मूल्यांकन फ़ंक्शन और एक खोज रणनीति। मूल्यांकन फ़ंक्शन एक ऐसा फ़ंक्शन है जो बोर्ड पदों के लिए एक संख्यात्मक मान प्रदान करता है। यदि स्थिति एक अंतिम स्थिति है (यानी, ऐसी स्थिति जहां या तो नीला खिलाड़ी या लाल खिलाड़ी जीता है या जहां कोई भी खिलाड़ी नहीं जीता है), मूल्यांकन कार्य बहुत सरल है: मान लीजिए कि Arduino नीला खेलता है और मानव खिलाड़ी लाल खेलता है. यदि स्थिति नीले रंग के लिए जीतने वाली स्थिति है, तो फ़ंक्शन उस स्थिति के लिए 10 का मान निर्दिष्ट करता है; यदि यह लाल रंग के लिए जीतने की स्थिति है, तो फ़ंक्शन स्थिति को -10 का मान निर्दिष्ट करता है; और यदि स्थिति एक ड्रा है, तो फ़ंक्शन 0 का मान निर्दिष्ट करता है।

जब यह Arduino की बारी है, तो यह एक ऐसा कदम चुनना चाहता है जो मूल्यांकन फ़ंक्शन के मूल्य को अधिकतम करता है, क्योंकि मूल्य को अधिकतम करने का मतलब है कि यह ड्रॉ पर जीत को पसंद करेगा (10 से अधिक है) और हारने पर ड्रॉ को बेहतर बनाता है (0 -10 से बड़ा है)। एक समान तर्क से, प्रतिद्वंद्वी इस तरह से खेलना चाहता है कि वह मूल्यांकन समारोह के मूल्य को कम कर दे।

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

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

चरण 3: समस्या निवारण और आगे के चरण

यदि आप एक बटन और एक अलग एलईडी को बटन रोशनी से संबंधित एक से दबाते हैं, तो शायद आपके पास या तो पिन ए0-ए 2 या 4-6 मिश्रित तारों पर मिला है, या आपने एलईडी को गलत क्रम में जोड़ा है।

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

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

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