मैं Minimax एल्गोरिथ्म के बारे में एक साधारण सवाल है: टिक टीएसी को पैर की अंगुली खेल के लिए उदाहरण के लिए, मैं कैसे तय करते हैं उपयोगिता समारोह के प्रत्येक खिलाड़ी को नाटकों के लिए? यह स्वचालित रूप से ऐसा नहीं करता है, है ना? मुझे खेल में मूल्यों को कड़ी-कोड करना चाहिए, यह उन्हें स्वयं से नहीं सीख सकता है, है ना?Minimax एल्गोरिथ्म
नहीं, मिनीमैक्स नहीं सीखता है। यह एक ब्रूट-बल पेड़ खोज का एक बेहतर संस्करण है।
टिक-टैक-पैर की अंगुली काफी छोटा अंत करने के लिए खेल चलाने के लिए और खो के लिए ड्रॉ के लिए जीत के लिए 1, 0 और -1 आवंटित करने के लिए है।
अन्यथा आपको एक ऐसा कार्य प्रदान करना होगा जो एक स्थिति के मूल्य को निर्धारित करता है। शतरंज में उदाहरण के लिए एक बड़ा कारक सामग्री का मूल्य है, लेकिन यह भी केंद्र को नियंत्रित करता है या टुकड़े कितनी आसानी से स्थानांतरित कर सकते हैं।
सीखने के लिए के रूप में, आप स्थिति के विभिन्न पहलुओं को वजन कारकों जोड़ सकते हैं और बार-बार गेम खेलने से उन अनुकूलन करने के लिए कोशिश कर सकते हैं।
प्रत्येक नाटक के लिए उपयोगिता फ़ंक्शन कैसे निर्धारित करें?
सावधानी से ;-) यह article दिखाता है कि थोड़ा सा दोषपूर्ण मूल्यांकन कार्य (पूर्व में से एक जो या तो संभावित प्लीज के पेड़ में आगे देखने में पर्याप्त "गहरा" नहीं जाता है, या जो कैप्चर करने में विफल रहता है कुछ बोर्ड पदों के सापेक्ष स्ट्रेन्ग) परिणामस्वरूप एक कमजोर कमजोर एल्गोरिदम (जो अक्सर अधिक खो देता है)।
यह अपने आप में उन्हें नहीं सीख सकते हैं, करता है यह?
नहीं, यह नहीं करता है। हालांकि, कंप्यूटर को बोर्ड की स्थिति की सापेक्ष ताकत सीखने के तरीके हैं। उदाहरण के लिए Donald Mitchie and his MENACE program पर देखकर आप देखेंगे कि बिना किसी किसी पूर्व ज्ञान के बिना बोर्ड सीखने के लिए एक स्टोकास्टिक प्रक्रिया का उपयोग किया जा सकता है लेकिन गेम के नियम। मजाकिया हिस्सा यह है कि यह कंप्यूटरों में लागू किया जा सकता है, जबकि कुछ सौ रंगीन मोती और मैच बॉक्स आवश्यक हैं, खेल अंतरिक्ष के अपेक्षाकृत छोटे आकार के लिए धन्यवाद, और विभिन्न समरूपता के लिए भी धन्यवाद।
कंप्यूटर कैसे खेलने के लिए शिक्षण के इस तरह के एक अच्छा तरीका सीखने के बाद, हम इतनी के रूप में टिक-टैक-पैर की अंगुली करने के लिए लागू वापस MinMax के लिए जा रहा में कोई दिलचस्पी नहीं हो सकता है। सभी के बाद मिनमैक्स एक निर्णय पेड़ काटने का अपेक्षाकृत सरल तरीका है, जिसे टिक-टैक-टो के छोटे गेम स्पेस के साथ शायद ही जरूरी है। लेकिन, अगर हमें जरूरी है ;-) [मिनमैक्स पर वापस जाएं] ...
हम अगले खेल (यानी गहरे नहीं जा रहे हैं) से जुड़े "मैचबॉक्स" में देख सकते हैं, और जुड़े मोतियों के प्रतिशत का उपयोग कर सकते हैं एक अतिरिक्त कारक के रूप में, प्रत्येक वर्ग के साथ। इसके बाद हम एक पारंपरिक पेड़ का मूल्यांकन कर सकते हैं, लेकिन केवल जा रहे हैं, 2 या 3 गहराई से चलें (एक उथली दिखने वाली गहराई जो आम तौर पर आमतौर पर घाटे या ड्रॉ में समाप्त होती है) और सरल -1 के आधार पर प्रत्येक अगले कदम को रेट करें (नुकसान), 0 (ड्रा/अज्ञात), +1 (जीत) रेटिंग। इसके बाद मोतियों के प्रतिशत और सरल रेटिंग को जोड़कर (निश्चित रूप से, गुणा द्वारा निश्चित रूप से नहीं), हम प्रभावी रूप से एक फैशन में मिनमैक्स का उपयोग करने में सक्षम हैं जो कि मामलों में उपयोग किए जाने के तरीके के समान होता है जब मूल्यांकन करना संभव नहीं होता है इसके पेड़ के लिए खेल पेड़।
नीचे पंक्ति: टिक-टैक-टो के मामले में, मिनमैक्स केवल अधिक दिलचस्प हो जाता है (उदाहरण के लिए हम किसी विशेष उपयोगिता फ़ंक्शन की प्रभावशीलता का पता लगाने में हमारी सहायता करने के लिए) जब हम खेल की निर्धारक प्रकृति को हटाते हैं, पूर्ण पेड़ का आसान मूल्यांकन। खेल [गणितीय] दिलचस्प बनाने का एक और तरीका एक प्रतिद्वंद्वी के साथ खेलना है जो गलती करता है ...
आमतौर पर आप सीधे उपयोगिता फ़ंक्शन को लागू करेंगे। इस मामले में एल्गोरिदम खेल को खेलना सीख नहीं पाएगा, यह उस सूचना का उपयोग करेगा जिसे आपने कार्यान्वयन में स्पष्ट रूप से कड़ी-कोडित किया था।
हालांकि, genetic programming (जीपी) या स्वचालित रूप से उपयोगिता फ़ंक्शन प्राप्त करने के लिए कुछ समकक्ष तकनीक का उपयोग करना संभव होगा। इस मामले में आपको किसी भी स्पष्ट रणनीति को एन्कोड नहीं करना पड़ेगा। इसके बजाय विकास खेल को अच्छी तरह से खेलने का अपना तरीका खोजेगा।
आप या तो अपने मिनीमैक्स कोड और जीपी कोड को एक एकल (शायद बहुत धीमी) अनुकूली प्रोग्राम में जोड़ सकते हैं, या आप पहले जीपी चला सकते हैं, एक अच्छा उपयोगिता फ़ंक्शन ढूंढ सकते हैं और फिर इस फ़ंक्शन को अपने मिनीमैक्स कोड में जोड़ सकते हैं आप किसी भी हाथ से कोडित समारोह होगा।
चूंकि यह एक ब्रूट-फोर्स एल्गोरिदम है क्योंकि अल्फा-बीटा प्रुनिंग जैसे कुछ का उपयोग करके इसे अनुकूलित करना महत्वपूर्ण है। http://en.wikipedia.org/wiki/Alpha-beta_pruning –
बेरिक: हां, ज़ाहिर है। लेकिन अल्फा/बीटा आमतौर पर निंदा की जाती है, निश्चित रूप से जब negamax के बारे में बात करते हैं। –