किसी गेम के लिए एक अच्छा मूल्यांकन फ़ंक्शन कैसे बनाएं?

Question

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

हालांकि, अब मैं एक बिल्कुल नया बोर्ड गेम खेलने के लिए एक प्रोग्राम लिख रहा हूं। मैं एक अच्छा या यहां तक ​​कि सभ्य मूल्यांकन समारोह कैसे चुनूं?

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

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

Answer 1

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

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

देर से संपादित करें: उस समय एक अधिक स्वीकार्य, अध्ययन, समझने का दृष्टिकोण जिसे मैं नहीं जानता था "विभेदक विकास" कहा जाता है। संतान 2 के बजाय 3 माता-पिता से बनाए जाते हैं, इस तरह से औसत की ओर समयपूर्व अभिसरण की समस्या से बचा जाता है।

Answer 2

मैं सुदृढ़ीकरण सीखने जैसे पर्यवेक्षित मशीन लर्निंग एल्गोरिदम को देखता हूं। Reinforcement learning in board games देखें। मुझे लगता है कि आपको देखने के लिए कुछ अच्छे दिशानिर्देश दिए जाएंगे।

इसके अलावा, Strategy Acquisition for the Game Othello Based on Reinforcement Learning (पीडीएफ लिंक) देखें जहां गेम के नियम दिए गए हैं, एक अच्छा "पेऑफ फ़ंक्शन" सीखा जा सकता है। यह बारीकी से TD-Gammon से संबंधित है ...

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

Answer 3

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

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

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

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

अपने गेम के बारे में और जानने के बिना मुझे आपको यह बताने के लिए कड़ी मेहनत होगी कि फ़ंक्शन कैसे बनाया जाए। क्या कुछ ऐसे स्पष्ट मूल्य हैं जो जीत या नुकसान का संकेत देते हैं? क्या आपके पास अंतर को बंद करने के लिए न्यूनतम लागत का अनुमान लगाने का कोई तरीका है?

यदि आप अधिक जानकारी प्रदान करते हैं, तो मुझे और अधिक अंतर्दृष्टि प्रदान करने में खुशी होगी। इस विषय पर बहुत सारी उत्कृष्ट किताबें भी हैं।

याकूब

Answer 4

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

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

मुझे लगता है कि गेम को समझने के लिए कोई रास्ता नहीं है और स्टार्टर्स के लिए, अज्ञात को मूल्यांकन फ़ंक्शन पर यादृच्छिक रूप से छोड़ दें (या अज्ञात को ज्ञात होने तक चित्र से बाहर)।

बेशक, यदि आप गेम के बारे में अधिक जानकारी साझा करेंगे तो आप समुदाय से बेहतर विचार प्राप्त कर सकते हैं।

Answer 5

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

च (board1)> च (board2)

तो यह सच है कि board1 कंप्यूटर के लिए बेहतर है होना चाहिए board2 की तुलना में (यह अंततः जीतने के लिए और अधिक संभावना है)। बेशक, सभी बोर्डों के लिए कोई स्थिर कार्य कभी भी सही नहीं होता है।

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

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

Answer 6

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

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

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

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

मैं अत्यधिक these slides देख रहा हूं।

Answer 7

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

Answer 8

मैं कुछ मूलभूत बातें शुरू करूंगा और बाद में कठिन सामग्री में जाऊंगा।

बेसिक एजेंट और एक परीक्षण ढांचे

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

x   -0.01  -1.484 | -1.485 
0.01   x   -1.29 | -1.483 
1.484  1.29   x  | 2.774 

उदाहरण के लिए यहाँ मैं एक जीत के लिए 2 अंक का उपयोग करें, ड्रा स्कोरिंग के लिए 1 अंक समारोह, और अंत में बस फिटनेस खोजने के लिए सब कुछ संक्षेप में। यह तालिका तुरंत मुझे बताती है कि agent3 सबसे अच्छा है, और agent1agent2 से वास्तव में अलग नहीं है।

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

---

के चयन करने सुविधाओं

1. तुम सब not a terrible मूल्यांकन कार्य बनाने की जरूरत पहले से शुरू करते हैं। इसके द्वारा मेरा मतलब है कि इस कार्य को सही ढंग से 3 महत्वपूर्ण पहलुओं (जीत/ड्रा/हानि) की पहचान करनी चाहिए। यह स्पष्ट लगता है, लेकिन मैंने बॉट्स की महत्वपूर्ण मात्रा देखी है, जहां निर्माता इन 3 पहलुओं को सही ढंग से स्थापित करने में सक्षम नहीं थे।

2. फिर आप खेल की कुछ विशेषताओं को खोजने के लिए अपने मानव चालाकी का उपयोग करते हैं। करने के लिए पहली बात यह है कि एक गेम विशेषज्ञ से बात करें और उससे पूछें कि वह कैसे स्थिति तक पहुंचता है।

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

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

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

के संयोजन और सरल सुविधाओं भार से बेहतर मूल्यांकन का निर्माण। कुछ मानक दृष्टिकोण हैं।

1. अपनी सुविधाओं के विभिन्न संयोजनों के आधार पर एक uber फ़ंक्शन बनाएं। यह रैखिक eval = f_1 * a_1 + ... f_n * a_n (f_i विशेषताएं, a_i गुणांक) हो सकता है, लेकिन यह कुछ भी हो सकता है। फिर इस मूल्यांकन समारोह के लिए बिल्कुल यादृच्छिक भार वाले कई एजेंटों को तुरंत चालू करें और आनुवांशिक एल्गोरिदम का उपयोग एक दूसरे को फिर से खेलने के लिए करें। परीक्षण ढांचे का उपयोग करके परिणामों की तुलना करें, कुछ स्पष्ट हारने वालों को छोड़ दें और कुछ विजेताओं को बदल दें। एक ही प्रक्रिया जारी रखें। (यह एक मोटा रूपरेखा है, जीए के बारे में और पढ़ें)

2. अपने नेटवर्क के वजन को अद्यतन करने के लिए गेम के अंत से त्रुटि को प्रसारित करने के लिए एक तंत्रिका नेटवर्क से बैक-प्रोपेगेशन विचार का उपयोग करें। आप backgammon के साथ यह कैसे पढ़ सकते हैं (मैंने कुछ भी लिखा नहीं है, इसलिए शॉर्टनेस के लिए खेद है)।

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