कार्ड गेम (डोमिनियन)

Question

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

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

def play(hand, totalDeck): 
    if hand contains Smithy then use Smithy 
    if hand contains enough coins for Province then buy Province 
    if more than 30% of the totalDeck is Smithy, then buy coins 

मैं प्रत्येक कार्ड के लिए कुल डेक का लक्ष्य भागों का एक वेक्टर के मामले में एक रणनीति का वर्णन करने का सोच रहा था:: फिर

[Smithy, Province, Copper, ...] 
[.3, .2, .1, ...] 

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

क्या यह समझ में आता है? क्या मैं सही रास्ते पर जा रहा हूं?

Answer 1

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

आप एक सह विकासवादी दृष्टिकोण ले सकता है:

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

या आप एक निश्चित मानक के खिलाफ प्रशिक्षण दे सकते:

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

Answer 2

के खिलाफ

ट्रेन मैं वेक्टर वास्तव में अच्छे परिणाम के लिए नेतृत्व नहीं करेंगे जब तक कि खेल बहुत रैखिक है लगता है।मैं निम्नलिखित नियम-आधारित दृष्टिकोण का सुझाव दूंगा:

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

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

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

Answer 3

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

डोमिनियन के पास एक बेहतर दृष्टिकोण, मुझे लगता है, या तो एक सीधे अनुमानी (नियम आधारित) दृष्टिकोण या, बहुत दिलचस्प है, मोंटे कार्लो खोजें (उदाहरण के लिए देखते हैं,, http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext) होगा। मोंटो कार्लो खोज ठीक से आकर्षक है क्योंकि:

• डोमिनियन में चाल के यादृच्छिक-लेकिन-कानूनी अनुक्रम उत्पन्न करना आसान है।
• यह है कम से कम इस तरह के एक दृश्य के "मूल्य" (वीपी में वृद्धि) "सबसे अच्छा खेलने" नियमों की
• ए-प्रायोरी इमारत का न्याय करने के लिए सीधी-सपाट कठिन है (कि क्या खेल इतना अच्छा बनाता है)

यह एक बहुत अच्छी चुनौती है - आपको अपने अनुभवों को ब्लॉग करना चाहिए।