💾 👃🏻 🤷 होमोकू के उदाहरण का उपयोग करके तार्किक खेलों में समाधान खोजें 🤳🏾 💂🏼 🤸

प्रविष्टि

सामान्य तौर पर, हम क्लासिक होमोक के बारे में बात नहीं कर रहे हैं, लेकिन रूसी भिन्नता के बारे में "एक पंक्ति में पांच"। आपके पास बॉक्स में एक कागज का टुकड़ा है। खेल के नियम टिक-टैक-टो में जैसे ही हैं। एकमात्र अंतर यह है कि 5 तत्वों की एक पंक्ति का निर्माण करना आवश्यक है।

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

क्रूर बल

विचार यह है कि हमारे पास कोई मूल्यांकन कार्य नहीं है, कोई अनुमान नहीं है। हम केवल एक पंक्ति में पांच तक पहुंचने तक तत्वों को मैदान पर रखते हैं। यह तुरंत स्पष्ट हो जाता है कि ऐसी कोई विधि उपयुक्त नहीं है। प्रत्येक चाल औसतन average० नए स्थान उत्पन्न करती है। 6 चालों से, विकल्पों की संख्या बढ़कर 80 ^ 6 = 2 ^ 37 विकल्प हो जाती है, जो बहुत अधिक है।

अल्फा बीटा कतरन

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

अंत से निर्णय

विचार पैटर्न को पहचानना है जो जीत की ओर ले जाता है। शतरंज कार्यक्रमों के साथ समानता एंडगेम बेस है।

यह खेल "एक पंक्ति में 5" के लिए किया जा सकता है

खेल हमेशा 5 तत्वों की एक पंक्ति के साथ समाप्त होता है। यदि हम एक कदम पीछे जाते हैं, तो हमें निम्नलिखित संयोजन मिलते हैं:
जीत का कदम

यदि आप दो कदम पीछे जाते हैं, तो हमें यह मिलता है:
जीत के लिए दो कदम

लाइनों को जोड़ा जा सकता है:

संयोजनों के पूरे सेट को एक खोज ट्री में इकट्ठा किया जा सकता है जिसे खोज बिंदु के आसपास तैनात किया जाता है।

यह समाधान लागू किया गया था, लेकिन इसने धीरे-धीरे काम किया। इतना धीमा कि मैं कोड को डिबग नहीं कर सका। समस्या बहुत सारे संयोजनों की है। दो कदम पीछे वह सब है जो अभी भी स्मृति में संग्रहीत किया जा सकता है।

गणना बनाम भंडारण

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

गहरा या चौड़ा

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

मूल्यांकन समारोह

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

खेल का मूल्यांकन समारोह "एक पंक्ति में 5"

ऐसी पंक्तियाँ हैं जिन पर प्रतिकूल प्रतिक्रिया करने की आवश्यकता है।

चार खोलें। जीत की गारंटी अगर प्रतिद्वंद्वी अगली बारी नहीं जीतता है।

बंद चार। जीत के लिए एक कदम।

ट्रिपल खोलें। जीतने के लिए दो चाल।

उस क्रम में लाइनों की प्राथमिकता। यदि विभिन्न दिशाओं की कई पंक्तियाँ एक बिंदु पर परिवर्तित हो जाती हैं, तो पाठ्यक्रम स्कोर बढ़ जाता है। इसके अलावा, दुश्मन की रेखाओं और उन पर रक्षात्मक चाल को ध्यान में रखा जाता है।

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

श्री एलिस और ट्रीट-स्पेस सर्च

1992 में श्री ऑलिस ने 10 SUN SPARC वर्कस्टेशन का उपयोग करते हुए, 15X15 क्षेत्र के साथ क्लासिक होमोकू के लिए साबित किया जो हमेशा जीतता है। स्टेशनों में 64 और 128 एमबी रैम, 200 एमबी स्वैप थे। क्योंकि उन्होंने एम्स्टर्डम में व्रीजे यूनिवर्सिट स्टेशनों का उपयोग किया, उनकी प्रक्रिया केवल रात में शुरू हुई। रात में समाप्त नहीं होने वाली प्रक्रियाओं को सुबह में मार दिया गया था। इसमें 1000 सीपीयू / घंटे और एक सप्ताह का समय लगा।

उसने यह कैसे किया?

मूल लेख से थोड़ा सा सिद्धांत। गोमोकू पूरी जानकारी और अचानक मौत के साथ एक गोताखोर खेल है।

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

राज्यों की संख्या की ऊपरी सीमा ( राज्य-अंतरिक्ष जटिलता ) 3 ²²⁵ ~ = 10 ¹⁰⁵ । 10 ⁷⁰ - निर्णय पेड़ की जटिलता ( गेम-ट्री जटिलता ) यदि एक धारणा है कि औसत गेम 30 चालों तक रहता है और इसमें i-th चाल पर 225 - संभव कदम हैं।
पेशेवर खिलाड़ियों को देखते हुए, ऐलिस ने निष्कर्ष निकाला कि एक व्यक्ति मुख्य रूप से खतरों की एक श्रृंखला ( खतरा अनुक्रम ) की तलाश कर रहा है, जिससे जीत हो सकती है। इसी समय, प्रतिद्वंद्वी के प्रतिशोधी कदमों को लगभग पूरी तरह से नजरअंदाज कर दिया जाता है। केवल एक उपयुक्त श्रृंखला मिलने पर ही पलटवार करना संभव है।
ह्यूरिस्टिक ट्रीट-स्पेस सर्च इसी तथ्य पर बनाया गया है। एक हमले सेल ( लाभ ) के साथ प्रत्येक हमले की रेखा के लिए , जो पहले से मौजूद बाकी वर्गों पर आधारित है , हम तुरंत सभी रक्षात्मक चाल ( लागत वर्ग ) के साथ प्रतिक्रिया करते हैं । उसके बाद, हम जांचते हैं कि क्या अभी भी खतरों की एक श्रृंखला का निर्माण संभव है जो जीत की ओर ले जाती है।

खतरों की श्रृंखला और उसके विकास की शुरुआत

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

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

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

शून्य-स्ट्रोक हेयुरिस्टिक

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

दुर्भाग्य से, मुझे यह पता नहीं चला है कि इसे सुरक्षित और प्रभावी रूप से कैसे लागू किया जाए, इसलिए मैं इसे अभी तक लागू नहीं करता हूं।

जीत और निर्णय के पेड़ को पार करता है

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

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

सीमा के बिना होमोकू के लिए एक आदर्श खेल के साथ सबसे लंबी श्रृंखला

प्रतिबंधों के साथ होमोकु के लिए एक आदर्श खेल में सबसे लंबी श्रृंखला

सिद्धांत के अनुसार, क्षेत्र 19X19 क्रॉस को 15X15 से अधिक लाभ देता है, इसलिए असीमित क्षेत्र के लिए सब कुछ और भी आसान होना चाहिए।

घुटने पर वितरित कंप्यूटिंग

यह तुरंत स्पष्ट हो जाता है कि यह एक मशीन पर गिना नहीं जा सकता। दूसरी ओर, कार्य बहुत अच्छी तरह समानता रखता है।

इसलिए, हमें वितरित कंप्यूटिंग के लिए बुनियादी ढांचे को बढ़ाने की आवश्यकता है।

जल्दी से nginx, php-fastcgi, wget, script और मेरे कार्यक्रमों के आधार पर एक सर्वर अंधा कर दिया।
मुझे आधार के साथ टिंकर करना था, इसका आकार बहुत बड़ा होना चाहिए था और तत्वों तक पहुंच बहुत आम है। मुझे PostgreSQL के साथ महत्वपूर्ण अनुभव था, लेकिन यह मुझे सूट नहीं करता था, क्योंकि भले ही डेटा डिस्क पर एक ही स्थान पर फिट बैठता हो, लेकिन यह डीबीएमएस अभी भी लेनदेन के कारण तालिका के अंत में रखता है। इस प्रकार, यदि कोई तत्व बार-बार बदलता है, तो तालिका जल्दी से सूज जाती है। इसे वैक्यूम करना आवश्यक है, लेकिन एक लोड किए गए सर्वर पर यह समस्याग्रस्त है। इसके बजाय, मैंने अपनी बाइक को जन्म दिया, जिसमें आधार के रूप में एवीएल-ट्री और डायरेक्टरी संरचना का मिश्रण था। जब एक पेड़ एक निश्चित सीमा से अधिक हो जाता है, तो यह अलग-अलग निर्देशिकाओं में दो में विभाजित हो जाता है। यह ऐसे हैश ट्री से निकलता है। व्यवहार में, यह एक बुरा निर्णय था। सबसे पहले, AVL पेड़ एक डिस्क के साथ काम करने के लिए एक बुरा विकल्प है। अलग होने के समय, डेटा एक नए पेड़ में क्रमबद्ध क्रम में आता है - यह संतुलन के लिए सबसे खराब विकल्प है। दूसरे, अभ्यास से पता चला है कि इस तरह के कई कंप्यूटिंग संसाधनों को जमा करना ताकि डेटाबेस एक अड़चन बन जाए, काफी समस्याग्रस्त है, और PostgeSQL मुझे पूरी तरह से सूट करेगा।
कंप्यूटिंग नोड्स के रूप में, मैंने "सस्ती" क्लाउड सेवाओं का उपयोग करने की योजना बनाई है। मैंने Scalaxy और Amazon दोनों का इस्तेमाल किया। अचानक, मुझे एहसास हुआ कि कंप्यूटिंग असली पैसे के लायक थी । स्कैलेक्सी ने सर्वर को 16 कोर दिए, इससे मुझे लागत आई, ऐसा लगता है, $ 10 / दिन। इसी समय, 16 प्रक्रियाओं ने किसी तरह बहुत कठिन काम किया। अमेज़ॅन पर, मैंने 8 कोर के 2 उदाहरण लॉन्च करने की कोशिश की, और यह भी एक महत्वपूर्ण राशि खर्च हुई। मैंने भी मात्रा में लेने और 50 माइक्रो-इंस्टेंस का उपयोग करने की कोशिश की, जिसकी लागत मुझे प्रति दिन $ 40 थी। मेरी भावनाओं के अनुसार, उन्होंने 8 कोर के साथ 2 सर्वर से भी बदतर काम किया। इससे मुझे आश्चर्य हुआ कि गणनाओं की वास्तव में कितनी लागत थी। उस समय, मुझे 10,000 कोर की आवश्यकता थी। मान लीजिए कि हमें मुफ्त में लोहा मिला। मान लें कि हमारे पास हाइपर ट्रेडिंग के साथ 2-प्रोसेसर 8-कोर एक्सोन है। कुल हमें 10000 / (2 * 8 * 2) = 312.5 सर्वर चाहिए। मान लीजिए कि ऐसा सर्वर 200W खाता है। कुल प्रति दिन हमें 312.5 * 200W * 24h = 1.5MW * h * 0.11875 $ / (kW / h) = 178.125 $ / दिन का भुगतान करने की आवश्यकता है।
इसलिए, मैं मुक्त इंटरनेट समुदाय के लिए चालू ~~की गई गेंद पर कंप्यूटिंग संसाधन प्राप्त करना चाहता था~~ । एक साल पहले, RSDN समुदाय के लिए धन्यवाद, एक ट्रायल रन शुरू किया गया था।
जैसा कि मैंने देखा, निजी मशीनों पर समान कॉन्फ़िगरेशन के वर्चुअल सर्वर की तुलना में गणना बहुत तेज है। इसलिए, ऐसा लगता है कि ~~क्लाउड सेवाएं हमें थोड़ा बेवकूफ बना रही~~ हैं, इसके वर्चुअलाइजेशन को बढ़ा दिया गया है।
BOINC का उपयोग नहीं करने के सवाल का अनुमान लगाते हुए, मैं इस तरह से उत्तर दूंगा: मेरे लिए अपने प्रोजेक्ट के साथ वहां जाना बस असुविधाजनक है। लोग कैंसर का इलाज ढूंढ रहे हैं, हिग्स बोसोन की तलाश कर रहे हैं, और यहां मैं कुछ अस्पष्ट कार्य के साथ हूं।
सिद्धांत के अनुसार, विकल्पों की संख्या पहले फैलती है, फिर हल की गई शाखाओं को काटने के कारण संकीर्ण होने लगती है। 7 वीं चाल से स्थिति पर विचार किया गया था। गणना यह थी कि 8 वें कदम से, यदि विकल्पों की संख्या कम नहीं होती है, तो कम से कम इस वृद्धि की दर धीमी हो जाएगी।

गणना लगभग एक महीने तक चली। दुर्भाग्य से, एक चमत्कार नहीं हुआ। विकल्पों की संख्या में लगातार वृद्धि हुई है। गणना रोकनी पड़ी। यहां तक कि 17-35 चाल वाले राज्यों में, निर्णय वृक्ष भी लगातार विस्तार कर रहा है।
इसका कारण पहली-पहली खोज में निहित है। हमने अनभिज्ञ समाधान खोजने के लिए पहले-पहल खोज शुरू की।

ऐसा करने के लिए, आपको सभी विकल्पों को दरकिनार करना होगा, यहां तक कि सबसे मूर्खतापूर्ण भी।

चींटी कॉलोनी एल्गोरिथ्म

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

पड़ोसी से जीत के बारे में पूछें

ईमानदारी से, मुझे नहीं पता कि इस अनुमान को क्या कहा जाता है। यह इस तथ्य पर आधारित है कि कई मामलों में प्रतिद्वंद्वी के प्रतिशोधात्मक कदम जीत को प्रभावित नहीं कर सकते हैं।

हम शून्य पर एक "आशाजनक" कदम रखते हैं। जल्द ही हम पाते हैं कि वह 17 चालों में हार का सामना कर रहा है

हम उसी राज्य से अगले "आशाजनक" कदम को पैर की अंगुली बनाते हैं। हम पाते हैं कि क्रॉस फिर से उसी चाल के साथ जीते हैं

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

डेब्यू बेस और मैन

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

और चलो इसे कोडांतरक को फिर से लिखें

किसी भी परियोजना में मैंने बहुत अधिक अनुकूलन करने की कोशिश नहीं की और इतनी निराशा महसूस नहीं की।
तथ्य अक्षम हैं: एल्गोरिथ्म की समग्र जटिलता की तुलना में निरंतर का कोई अर्थ नहीं है। आपको याद दिला दूं कि औसतन प्रत्येक पद 80 नए पदों को देता है। एक कदम और गहरा करने के लिए, हमें कार्यक्रम की गति को 80 गुना बढ़ाना होगा !!!

इसलिए, मैंने जो कुछ किया है उसकी एक नमूना सूची:

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

अविश्वसनीय चाल के माध्यम से और कोड को जटिल करते हुए, मैंने गति को 2.5 गुना बढ़ाने में कामयाब रहा। त्वरण के बीच का अंतर 2.5 गुना और 80 गुना महसूस करें?
अक्सर वे CUDA का उपयोग करके वीडियो कार्ड पर गणना करने का प्रस्ताव रखते हैं। समस्या यह है कि GPUs SIMD आर्किटेक्चर पर बनाए गए हैं, और वे वास्तव में ब्रांचिंग को नापसंद करते हैं, और ब्रांचिंग वास्तव में, जिस तरह से एक पेड़ खोज का काम करता है। केवल एक चीज जिसके लिए उन्हें लागू किया जा सकता है वह है एक या कई पदों से एक साथ लाइनों को धमकी देने की खोज। इसका व्यावहारिक प्रभाव अब तक संदिग्ध है।

हालाँकि एल्गोरिथम अनुकूलन अभी तक समाप्त नहीं हुआ है। और यह बहुत संभव है कि इस तरह के जटिलता के कार्य के लिए एक आधुनिक स्मार्टफोन पर्याप्त है।
इसलिए एल्गोरिदम नियम!

धन्यवाद

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

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

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

होमोकू के उदाहरण का उपयोग करके तार्किक खेलों में समाधान खोजें