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

खेल "हरे और भेड़ियों"

एक शतरंज की बिसात पर 4 भेड़िये शीर्ष पर (काली कोशिकाओं पर), और 1 हेक्टेयर नीचे (काले लोगों में से एक पर) हैं। हरे पहले चलता है। आप केवल एक वर्ग तिरछे चल सकते हैं, जबकि भेड़िये केवल नीचे जा सकते हैं, और किसी भी दिशा में घास। जब यह ऊपरी कोशिकाओं में से किसी एक पर पहुंचता है, और भेड़िये, जब वे घेर लेते हैं या दबाते हैं, तो हार जीत जाता है (जब खरगोश कहीं नहीं जाता है)।

पढ़ना जारी रखने से पहले, मैं खेलने की सलाह देता हूं, यह समझना आसान होगा।

अनुमानी

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

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

एक मूल्यांकन समारोह का उदाहरण 1 । जितनी अधिक ऊँचाई, उतने अधिक मौके उसे जीतने होंगे। इस तरह का एक अनुमान गति (O (1)) के दृष्टिकोण से प्रभावी है, लेकिन यह पूरी तरह से अनुपयुक्त एल्गोरिदम है। हार की "ऊंचाई" जीत की संभावना के साथ संबंधित है, लेकिन जीत के मुख्य लक्ष्य को विकृत करती है - जीतने के लिए। यह मूल्यांकन कार्य हर्रे को ऊपर ले जाने के लिए कहता है, लेकिन गणना की एक छोटी गहराई के साथ यह बाधा को ऊपर की ओर ले जाएगा, बाधाओं की परवाह किए बिना, और जाल में गिर जाएगा।

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


चेतावनी। लेख में दिए गए स्रोतों को संशोधित किया गया है ताकि पाठक मुख्य अनुप्रयोग के संदर्भ के बाहर उनके सार को समझ सकें। लेख के अंत में विश्वसनीय स्रोतों की तलाश करें।

वह कोड जो चौड़ाई-प्रथम खोज करता है, या नक्शे को "दूरी" के बराबर मान के साथ भरता है:

this->queue.enqueue(this->rabbitPosition); while (!this->queue.empty()) { QPoint pos = this->queue.dequeue(); for (int i = 0; i < 4; i++) if (canMove(pos + this->possibleMoves[i])) { QPoint n = pos + this->possibleMoves[i]; this->map[ny()][nx()] = this->map[pos.y()][pos.x()] + 1; this->queue.enqueue(n); } } 

मूल्यांकन समारोह का परिणाम निकटतम ऊपरी सेल के लिए "दूरी" या 254 के बराबर मान होना चाहिए, अगर उन तक पहुंचना असंभव है। उन कमियों के बावजूद जिनका मैं नीचे वर्णन करूंगा, यह इस हेयुरिस्टिक है जिसका उपयोग खेल में किया जाता है।

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

अल्पमहिष्ठ

हम कुछ अवधारणाओं और संकेतन का परिचय देते हैं:

• राज्य, यह निर्णय वृक्ष का नोड भी है - बोर्ड पर आंकड़े का स्थान।
• टर्मिनल राज्य वह राज्य है जहां से अधिक चालें (कोई जीता / ड्रा) नहीं है।
  
• वी आई - वें राज्य है।
• विक वह अवस्था है जिसे वीआई राज्य से एक चाल में पहुँचा जा सकता है। फैसले के पेड़ के संदर्भ में, यह वीआई का एक बच्चा नोड है।
• f (Vi) राज्य Vi के लिए जीत की संभावना का एक अनुमानित अनुमान है।
• जी (वीआई) - राज्य वी के लिए जीत की संभावना का अनुमानी अनुमान।

f (vi) g (Vi) से भिन्न होता है उस g (Vi) में केवल Vi के बारे में जानकारी का उपयोग किया जाता है, और f (Vi) विक और अन्य राज्यों का भी पुनरावर्ती उपयोग करता है।

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

• एफ (वीआई) = जी (वीआई) , अगर वीआई एक टर्मिनल राज्य है, या गणना गहराई की सीमा तक पहुंच गया है।
• f (Vi) = मैक्स (f (Vi1), f (Vi2) ... f (Vik)) , अगर Vi वह राज्य है जिसमें खिलाड़ी अधिकतम स्कोर की तलाश में है।
• f (Vi) = min (f (Vi1), f (Vi2) ... f (Vik)) यदि Vi वह अवस्था है जिसमें खिलाड़ी न्यूनतम स्कोर खोजने के लिए साथ चलता है।

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

यह एक उदाहरण देने का समय है:


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

यदि नीचे से देखा जाए तो इस उदाहरण को समझना आसान होगा। दूसरे स्तर पर, हमारे पास ऐसे राज्य हैं जिनके लिए हम एक अनुमान अनुमान प्राप्त करते हैं (यह संख्याओं में लिखा गया है)। दूसरे स्तर के लिए, पहले को अपने ग्रेड मिलते हैं, क्रमशः उन लोगों से न्यूनतम मान चुनते हैं जिन्हें अगले स्तर पर जांचा जाता है। खैर, शून्य स्तर, अधिकतम रेटिंग का चयन करता है, उनमें से जो उसे पहले स्तर से दिया जाता है।

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

एल्गोरिथम कार्यान्वयन उदाहरण:

  //    f(Vi) int Game::runMinMax(MonsterType monster, int recursiveLevel) { int test = NOT_INITIALIZED; //    ( )     if (recursiveLevel >= this->AILevel * 2) return getHeuristicEvaluation(); //  . 0-7 -   , 8-11 -    int bestMove = NOT_INITIALIZED; bool isWolf = (monster == MT_WOLF); int MinMax = isWolf ? MIN_VALUE : MAX_VALUE; //      for (int i = (isWolf ? 0 : 8); i < (isWolf ? 8 : 12); i++) { int curMonster = isWolf ? i / 2 + 1 : 0; QPoint curMonsterPos = curMonster == 0 ? rabbit : wolfs[curMonster - 1]; QPoint curMove = possibleMoves[isWolf ? i % 2 : i % 4]; if (canMove(curMonsterPos + curMove)) { //...,     temporaryMonsterMovement(curMonster, curMove); //,   ,    test = runMinMax(isWolf ? MT_RABBIT : MT_WOLF, recursiveLevel + 1); //   ,     - ,    if ((test > MinMax && monster == MT_WOLF) || (test <= MinMax && monster == MT_RABBIT)) { MinMax = test; bestMove = i; } //...     temporaryMonsterMovement(curMonster, -curMove); } } if (bestMove == NOT_INITIALIZED) return getHeuristicEvaluation(); //  , ,      if (recursiveLevel == 0 && bestMove != NOT_INITIALIZED) { if (monster == MT_WOLF) wolfs[bestMove / 2] += possibleMoves[bestMove % 2]; else rabbit += possibleMoves[bestMove % 4]; } return MinMax; } 

चेतावनी! यहाँ, BestMove वैरिएबल बहुत सारे अर्थों को संलग्न करता है (मैं इसे अनुरोध पर निर्दिष्ट करूंगा), मैं आपसे आग्रह करता हूं कि 4 बिट्स में कभी भी इतनी समझदारी से निवेश न करें यदि आप सुनिश्चित नहीं हैं कि आप सब कुछ सही तरीके से कर रहे हैं।

साक्षर और शिक्षित लोग होने के नाते, आप पहले से ही अनुमान लगा चुके हैं कि जहाँ निर्णय वृक्ष हैं, वहाँ अनुकूलन का खजाना भी है। यह उदाहरण कोई अपवाद नहीं है।

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

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

मोटे तौर पर, अनुकूलन दो अतिरिक्त चर अल्फा और बीटा का परिचय देता है, जहां अल्फा वर्तमान अधिकतम मूल्य है, इससे कम पर जो अधिकतमकरण खिलाड़ी (भेड़ियों) कभी नहीं चुनेगा, और बीटा वर्तमान न्यूनतम मूल्य है, इससे अधिक नहीं कि न्यूनतमकरण खिलाड़ी (हर) कभी नहीं चुनेंगे। प्रारंभ में, वे क्रमशः -∞, + respectively पर सेट होते हैं, और जैसा कि वे अनुमान प्राप्त करते हैं f (Vi) संशोधित हैं:

• अल्फा = अधिकतम (अल्फा, एफ (वीआई)); अधिकतमकरण के स्तर के लिए।
• बीटा = मिनट (बीटा, एफ (वीआई)); न्यूनतमकरण के स्तर के लिए।

जैसे ही स्थिति अल्फा> बीटा सही हो जाती है, जिसका अर्थ है उम्मीदों का संघर्ष, हम विक के विश्लेषण को बाधित करते हैं और इस स्तर के अंतिम प्राप्त अनुमान को वापस करते हैं।

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


उदाहरण में पदनाम:

• Vi फैसले के पेड़ के नोड्स हैं, मैं किसी भी तरह से पेड़ की कटाई के आदेश के साथ संबंध नहीं रखता हूं।
• Vi [अल्फा, बीटा] - अल्फा, बीटा के संकेतित वर्तमान मूल्यों के साथ नोड्स।
• सी आई-अल्फा अल्फा क्लिपिंग है।
• न्यूनतम, अधिकतम - क्रमशः अधिकतमकरण और न्यूनता के स्तर। सावधान रहें, अधिकतम स्तर पर राज्य अगले स्तर के राज्यों से अपने मैक्सिमम को चुनेंगे जिस पर न्यूनतम संकेत दिया गया है, और इसके विपरीत। यही है, अधिकतम उन लोगों से चुना जाता है जिन पर MIN लिखा जाता है, और उन पर न्यूनतम जिस पर MAX लिखा गया है, भ्रमित न करें।

कतरन पर विचार करें 1. नोड V3 के साथ संस्करण के बाद नोड V1 के लिए पूरी तरह से संसाधित किया गया है और इसका अनुमान f (V3) = 6 प्राप्त किया गया है, एल्गोरिथ्म इस नोड (V1) के लिए अल्फा मान को अद्यतन करता है और इसके मूल्य को अगले नोड - V4 में स्थानांतरित करता है। । अब V4 के सभी चाइल्ड नोड्स के लिए, न्यूनतम अल्फ़ा = 6. V4 नोड के V5 नोड के साथ वेरिएंट को संसाधित करने और अनुमान f (V5) = 5 प्राप्त करने के बाद, एल्गोरिथ्म V4 नोड के लिए बीटा मान को परिष्कृत करता है। अपडेट के बाद, V4 नोड के लिए हमें एक ऐसी स्थिति मिली जिसमें अल्फा> बीटा, और इसलिए V4 नोड के लिए अन्य विकल्प आवश्यक नहीं हैं। और यह हमारे लिए कोई बात नहीं है कि कट-ऑफ नोड में क्या ग्रेड होगा:

• यदि क्लैप्ड नोड का मान 5 (बीटा) से कम या बराबर है, तो नोड वी 4 में 5 से अधिक का अनुमान नहीं चुना जाएगा, और तदनुसार, नोड वी 4 के साथ नोड वी 4 के साथ विकल्प कभी नहीं चुना जाएगा, क्योंकि नोड वी 3 का मूल्यांकन बेहतर है।
• यदि क्लैप्ड नोड का मान 6 (बीटा + 1) से अधिक या बराबर है, तो नोड को और अधिक नहीं माना जाएगा, क्योंकि V4 नोड वी 5 नोड के साथ विकल्प का चयन करेगा, क्योंकि इसकी रेटिंग कम (बेहतर) है।

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

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

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

अल्फ़ा-बीटा क्लिपिंग (स्पष्टता के लिए, मिनिमैक्स अल्गोरिथम को संशोधित करने का उदाहरण, टिप्पणी की गई है, लेकिन याद रखें कि यह एक महत्वपूर्ण कोड है, टिप्पणी नहीं):

 int Game::runMinMax(MonsterType monster, int recursiveLevel/*, int alpha, int beta*/) { int test = NOT_INITIALIZED; if (recursiveLevel >= this->AILevel * 2) return getHeuristicEvaluation(); int bestMove = NOT_INITIALIZED; bool isWolf = (monster == MT_WOLF); int MinMax = isWolf ? MIN_VALUE : MAX_VALUE; for (int i = (isWolf ? 0 : 8); i < (isWolf ? 8 : 12); i++) { int curMonster = isWolf ? i / 2 + 1 : 0; QPoint curMonsterPos = curMonster == 0 ? this->rabbit : this->wolfs[curMonster - 1]; QPoint curMove = this->possibleMoves[isWolf ? i % 2 : i % 4]; if (canMove(curMonsterPos + curMove)) { temporaryMonsterMovement(curMonster, curMove); test = runMinMax(isWolf ? MT_RABBIT : MT_WOLF, recursiveLevel + 1, alpha, beta); temporaryMonsterMovement(curMonster, -curMove); if ((test > MinMax && monster == MT_WOLF) || (test <= MinMax && monster == MT_RABBIT)) { MinMax = test; bestMove = i; } /* if (isWolf) alpha = qMax(alpha, test); else beta = qMin(beta, test); if (beta < alpha) break; */ } } if (bestMove == NOT_INITIALIZED) return getHeuristicEvaluation(); if (recursiveLevel == 0 && bestMove != NOT_INITIALIZED) { if (monster == MT_WOLF) this->wolfs[bestMove / 2] += this->possibleMoves[bestMove % 2]; else this->rabbit += this->possibleMoves[bestMove % 4]; } return MinMax; } 

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

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

बारीकियों

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

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

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

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

संशोधनों की एक बड़ी संख्या कंप्यूटर को शतरंज खेलने की अनुमति देती है, और यहां तक ​​कि एक व्यक्ति को भी हरा देती है। ऐसे संशोधनों के बिना, न्यूनतम सुपर व्यावहारिक रूप से शतरंज पर लागू नहीं होता है, यहां तक ​​कि आधुनिक सुपर कंप्यूटरों पर भी। अनुकूलन के बिना, तीन चालों के लिए शतरंज में लगभग 30 ^ 6 चाल (729 बिलियन) की जाँच करना आवश्यक होगा, और हमें एक गहरी गणना की गहराई होनी चाहिए ...

सुखद अंत

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