🎤 👨‍👧 👋🏾 जापानी शतरंज खेलने के लिए AI के निर्माण में मशीन लर्निंग का उपयोग (शोगी) 🌇 👩‍❤️‍💋‍👩 🧔🏼

शुभ दिन।

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

अल्फा बीटा क्लिपिंग के बारे में या क्यों यह चालों को क्रमबद्ध करना महत्वपूर्ण है

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

वर्गों में संख्या चाल के अनुरूप अनुक्रम बनाने के बाद स्थिति के मूल्यांकन का संकेत देती है।

इस उदाहरण में, नोड को क्लिप किया गया है, जिसके मूल्य को प्रश्न चिह्न के साथ चिह्नित किया गया है।
आप एक अभिव्यक्ति की रचना करके ऐसे कट-ऑफ की वैधता को सत्यापित कर सकते हैं जिसके द्वारा नोड b पर मूल्य की गणना की जाती है:

बी = मिनट (सी, डी) = मिनट (अधिकतम 4,6), अधिकतम (7, एक्स))

जाहिर है, इस अभिव्यक्ति का मूल्य एक्स पर निर्भर नहीं करता है, क्योंकि अभिव्यक्ति अधिकतम (7, एक्स) निश्चित रूप से 7 के बराबर या उससे अधिक है, इसलिए, यह अधिकतम (4,6) से अधिक है और बी का मूल्य बी = 6 के बराबर होगा।

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

परिकल्पना

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

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

यह वह जगह है जहां पहले से खेले जाने वाले खेलों से होनहार चालों के बारे में जानकारी प्राप्त करने की संभावना का विचार स्वचालित रूप से आता है। मशीन सीखने के तरीकों का उपयोग इस मामले में उचित है कि परिकल्पना इसी तरह के मापदंडों के साथ चलती है (उनके बारे में नीचे) एक समान परिणाम देते हैं।

प्रशिक्षण का नमूना

पहला सवाल जो मशीन लर्निंग का उपयोग करते समय हल किया जाना चाहिए, एक प्रशिक्षण नमूना प्राप्त कर रहा है, जिसके द्वारा चालों की गुणवत्ता निर्धारित की जाएगी।
विचित्र रूप से पर्याप्त, यह नियमित शतरंज की तुलना में शोगी की हीन लोकप्रियता के बावजूद, सबसे कम समस्या थी।

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

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

स्क्रिप्ट जो playok.com से बैच डाउनलोड करती है और उन्हें डेटाबेस में दर्ज करती है, साथ ही स्क्रिप्ट जो डेटा तैयार करती है (अर्थात, वे कार्य जिनके निष्पादन का समय महत्वपूर्ण नहीं है), रूबी में लिखे गए हैं, क्योंकि यह भाषा लेखन कोड की उच्च गति प्रदान करती है, और डेटाबेस के साथ काम करने के लिए सभी आवश्यक घटक भी हैं। स्रोत कोड के लिंक लेख के अंत में दिए गए हैं।

चाल के विवरण के बारे में

संभव होने के लिए मशीन सीखने के तरीकों के आवेदन के लिए, सुविधाओं के एक सेट का उपयोग करके प्रत्येक चाल का वर्णन करना आवश्यक है। अजीब जैसा कि लग सकता है, इस तरह के विवरण को ऑब्जेक्ट का एक फीचर विवरण कहा जाता है।

एक विशेषता विवरण मूल्यों का एक वेक्टर है, जो बदले में, विशेषता अंतरिक्ष में एक बिंदु के निर्देशांक है।
उदाहरण के लिए, बॉक्स के आयाम और वजन एक सूचक विवरण के रूप में काम कर सकते हैं। तो एक बॉक्स में 2 को 3 से 1 मीटर की दूरी पर और 10 किलोग्राम वजन के साथ संकेतों के चार-आयामी स्थान में एक विशेषता विवरण (2,3,1,10) होगा ।

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

विशेषता विवरण के उपयोग किए गए प्रकार में निम्नलिखित पैरामीटर होते हैं:

लंबी सूची

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

वर्गीकरण एल्गोरिदम की पसंद के बारे में

समस्या के बयान का तात्पर्य है कि होनहारों और अक्रोधी (अच्छे और बुरे) में चालों का एक वर्गीकरण, लेकिन कुछ अतिरिक्त स्थितियों को भी एल्गोरिथ्म पर लगाया जाता है:

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

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

इस समस्या को हल करने का एक तरीका क्लस्टरिंग का उपयोग करना है।
बिंदुओं के सेट के साथ शुरुआती बिंदुओं के सेट को प्रतिस्थापित करना जो कि समूहों के केंद्र हैं, हम ऑब्जेक्ट को वर्गीकृत करने के लिए आवश्यक संचालन की संख्या को काफी कम कर देंगे। ऐसा प्रतिस्थापन स्पष्ट रूप से वर्गीकरण की गुणवत्ता को नीचा दिखाएगा, और आउटपुट सेट में जितने कम क्लस्टर होंगे, गुणवत्ता उतनी ही खराब होगी। इस प्रकार, समूहों की संख्या एक मूल्य है जो सटीकता और गति के बीच एक समझौता को दर्शाता है।

चाल की पसंद के बारे में

पार्टियों के प्रसंस्करण के लिए आगे बढ़ने से पहले, यह तय करना आवश्यक है कि किन चालों को अच्छा माना जाता है और जो हमारे आधार के रूप में खराब हैं। कई विकल्प तुरंत दिमाग में आते हैं:

चालें जो एक भौतिक लाभ का कारण बनीं।
वह चाल जो चटाई तक ले जाती थी।
उच्च रेटेड खिलाड़ी चलता है।

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

वर्तमान कार्यान्वयन में, निम्नानुसार चाल का चयन किया जाता है:

निचले और ऊपरी रेटिंग थ्रेसहोल्ड सेट हैं।
प्रत्येक गेम में, विजेता की रेटिंग ऊपरी सीमा से अधिक होती है, विजेता की चालों के अंतिम 2/3 को अच्छे के रूप में चुना जाता है।
प्रत्येक गेम में, जिसकी रेटिंग निचली दहलीज के बराबर से कम है, हारने वाले के अंतिम 2/3 चालों को चयनित और खराब के रूप में चिह्नित किया जाता है।

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

क्लस्टरिंग के बारे में

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

क्लस्टरिंग कार्य स्वयं स्पष्ट रूप से तैयार नहीं है, जो इसकी व्याख्या के लिए कई विकल्प देता है। हम निम्नलिखित परिभाषा का उपयोग करेंगे:

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

औपचारिक रूप से, इस परिभाषा को इस प्रकार लिखा जा सकता है:

जहां K _y - संख्या y के साथ क्लस्टर
p (x, y) एक फ़ंक्शन है जो किसी दिए गए मीट्रिक में दूरी निर्धारित करता है
μ _y संख्या y के साथ क्लस्टर का केंद्र है
x _i - संख्या i के साथ ऑब्जेक्ट

मेरे कार्यान्वयन में, मैंने k- साधन क्लस्टरिंग एल्गोरिथ्म का उपयोग किया; एक विस्तृत विवरण पाया जा सकता है, उदाहरण के लिए, विकिपीडिया पर।
एल्गोरिथ्म की ख़ासियत इस तथ्य में निहित है कि यह समूहों में प्रारंभिक विभाजन के रूप में यादृच्छिक मूल्यों का उपयोग करता है, जिनमें से विकल्प आगे के विभाजन के परिणाम को दृढ़ता से प्रभावित करता है, जिससे बेहतर परिणाम प्राप्त करने के लिए बार-बार क्लस्टरिंग करना संभव हो जाता है, और हम इस स्तर पर निष्पादन समय तक सीमित नहीं हैं।

उदाहरण के लिए, दो-आयामी अंतरिक्ष में यादृच्छिक बिंदुओं को क्लस्टर करना इस तरह दिखता है:

रूबी कार्यान्वयन

def midle(cluster) # "" res = [0]*cluster[0].size(); cluster.each do |e| i = 0; e.each do |x| res[i] += x; i+=1; end end res.map! {|x| x/cluster.size.to_f} return res; end def dist(x1,x2) if(x1.size != x2.size) raise "WrongSizeException"; end mode = 1 if mode ==1 then #     dist = 0; for i in 0..x1.size-1 dist += (x1[i]-x2[i])**2 end return dist; end if mode == 2 then #   dist = 0; x1_s = 0; x2_s = 0; for i in 0..x1.size-1 dist += x1[i]*x2[i] x1_s += x1[i]**2; x2_s += x2[i]**2; end dist =1 - dist / Math.sqrt(x1_s) / Math.sqrt(x2_s) end end def quality1 (clusters) #    ( ,    - ) sum = 0; clusters.each do |cluster| center = midle(cluster) local_sum = 0 cluster.each do |vector| local_sum += dist(vector, center); end sum += local_sum / cluster.size.to_f; end return sum; end def quality2 (clusters) #    centers = []; clusters.each do |cl| centers += [midle(cl)]; end sum = 0 centers.each do |c1| centers.each do |c2| sum += dist(c1,c2) end end return sum; end def quality (clusters) #    return quality1(clusters)/quality2(clusters); end def find_nearest(vectors, point) min = Float::INFINITY imin = 0 i = 0 vectors.each do |vector| d = dist(vector, point) if(d < min) then min = d; imin = i; end i += 1; end return imin end def k_means(vectors, k) len = vectors.size; clusters = []; centers_index = []; if len < k then raise "count of clusters more than objects"; end while centers_index.size != k do #    k   centers_index = (1..k).map { Random.rand(len)}; #  k   centers_index.uniq! end centers = centers_index.map{ |e| vectors[e] } clusters_new = [] begin #       clusters = clusters_new; clusters_new = k.times.map {[]}; vectors.each do |vector| clusters_new[find_nearest(centers, vector)] += [vector]; end #    centers = []; clusters_new.each do |cluster| return nil if cluster == nil; #  ,  -    return nil if cluster.size == 0; centers += [midle(cluster)] end end until clusters_new == clusters return clusters_new end

क्लस्टरिंग के परिणामस्वरूप, हमें N (I N = 20 चुना गया) अंक मिलते हैं जो फ़ीचर स्पेस में अच्छे और बुरे मूव्स के क्लस्टर के केंद्र हैं।
चाल देखने के क्रम को छांटने पर इन बिंदुओं की दूरी का उपयोग किया जाएगा।

वर्गीकरण के बारे में

अब जब हमारे पास मूल आधार की तुलना में काफी कम अंक हैं, तो हम इन बिंदुओं के निकटता के आधार पर छँटाई कर सकते हैं।

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

स्पष्टता के लिए चित्र:

यूक्लिडियन मीट्रिक दो-आयामी अंतरिक्ष में।

महालनोबिस मीट्रिक दो-आयामी अंतरिक्ष में। एलिप्सस मूल्यों के विचरण को दर्शाते हैं।

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

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

जावा कार्यान्वयन से टुकड़ा

  public static double euclidian(ArrayList<Double> p1, ArrayList<Double> p2) { Double sum = 0.0; for (int i = 0; i < p1.size(); i++) { sum += (p1.get(i) - p2.get(i)) * (p1.get(i) - p2.get(i)); } return sum; } public static double getMinDist(ArrayList<Double> point, ArrayList<ArrayList<Double>> clusters) { Double min = Double.MAX_VALUE; for (ArrayList<Double> cluster : clusters) { min = Math.min(min, euclidian(cluster, point)); } return min; } private void sortMoves(CMovesList movesList) { // (   ) - (  ) for (CMove move : movesList.Moves) { ArrayList<Double> move_params = CDataMining.getFeature(localBoard, move).toArray(); //   //  Double good_dist = CAdviser.getMinDist(move_params, clusters_good); //    Double bad_dist = CAdviser.getMinDist(move_params, clusters_bad); move.H = bad_dist - good_dist; } movesList.sortH(); } /** * -  * * @param color    * @param D  * @param A * @param B * @return */ public int AB(boolean color, int D, int A, int B) { ABtimes++; if ((D == 0) || Math.abs(localBoard.Evaluate(color)) >= 15000) return localBoard.Evaluate(color); CMovesList ML; ML = localBoard.getAllMoves(color); if (D == MaxD) { //    sortMoves(ML); // < -----       . } else { ML.sortH(); } while ((ML.getMovesCount() > 0) && (A < B)) { CMove Move = ML.getMoveByIndex(0); CFigure previousFigure = localBoard.makeMove(Move); int tmp = -AB(!color, D - 1, -B, -A); localBoard.unmakeMove(Move, previousFigure); if (tmp > A) { A = tmp; if (D == MaxD) BestMove.cp(Move); } ML.removeByIndex(0); } return A; }

परिणाम

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

काम के उदाहरण (स्पष्टता के लिए, परिणाम BCDGames प्रोग्राम का उपयोग करके दिखाया गया है):

अधिकतम प्रतिपादन गहराई: 4 आधा-पास।

एक वास्तविक बैच से लिया गया एक यादृच्छिक स्थिति।

सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 22027

पहली बार के लिए मशीन लर्निंग का उपयोग करने वाली सांख्यिकी, बाद की चालों के लिए - एक सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 18719

किए गए चाल अलग-अलग हैं, क्योंकि निर्मित पेड़ में, अधिकतम गहराई पर गेम की रेटिंग समान है।

सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 32561

पहली बार के लिए मशीन लर्निंग का उपयोग करने वाली सांख्यिकी, बाद की चालों के लिए - एक सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 28524

एक कृत्रिम स्थिति जिसमें बोर्ड पर बहुत सारे टुकड़े होते हैं और हाथ में कई टुकड़े होते हैं।
(माणिक देखना - 3 अर्ध-पास)

सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 379376

पहली बार के लिए मशीन लर्निंग का उपयोग करने वाली सांख्यिकी, बाद की चालों के लिए - एक सरल अनुमानी:
पुनरावर्ती कॉल की संख्या - 541866

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

विधि का नुकसान

एक लंबा समय।

निकटतम बिंदुओं की गणना करने की प्रक्रिया में, वास्तविक संख्याओं के साथ संचालन का उपयोग किया जाता है, जो गेम ट्री के देखने के समय को काफी बढ़ाता है।

सीमित आवेदन।

जैसा कि ऊपर उल्लेख किया गया है, कुछ स्थितियों के लिए, मशीन सीखने की विधि सरल उत्तराधिकारियों की तुलना में खराब परिणाम ला सकती है।

सुधार के संभव तरीके

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

मशीन सीखने की सांख्यिकी की प्रयोज्यता की समस्या को हल करने के लिए, निम्नलिखित सुधार संभव हैं:

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

सन्दर्भ और साहित्य

मशीन लर्निंग पर, के.वी. वोर्त्सोव द्वारा एक अद्भुत व्याख्यान पाठ्यक्रम है, जहां से मुझे इस्तेमाल किए गए तरीकों के बारे में जानकारी मिली। उनके व्याख्यान हाल ही में हैबर पर पोस्ट किए गए थे।
बॉट के साथ रिपोजिटरी, जावा में लिखा: https://github.com/gorkoff/Shogi/tree/DataMining
रूबी लिपियों के समर्थन के साथ भंडार: https://github.com/generall/ScriptsForShogi

आपका ध्यान देने के लिए धन्यवाद।

जापानी शतरंज खेलने के लिए AI के निर्माण में मशीन लर्निंग का उपयोग (शोगी)