खेल

Question

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

टावर्स और शहरों में केवल जमीन पर रखा जा सकता है उच्च आबादी के साथ

• शहरों, हार एक रक्षा टॉवर एक झटका है
• की रक्षा के लिए अधिक महत्वपूर्ण हैं

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

मुझे आश्चर्य है कि टावरों के प्लेसमेंट को निर्धारित करने के लिए किस प्रकार के एल्गोरिदम का उपयोग किया जा सकता है?

Answer 1

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

यहाँ एक नज़र डालें: हालांकि defcon के लिए एक जीए चल दुर्भाग्य से एक छोटे से logistically मुश्किल होगा http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf

Answer 2

बस एक उपयोगिता फ़ंक्शन को परिभाषित करें जो इनपुट के रूप में संभावित निर्माण स्थिति लेता है और उस स्थिति के लिए "रेटिंग" देता है। मुझे लगता है यह कुछ ऐसा दिखाई देगा:

utility(position p) = k1 * population_of_city_at_p + 
         k2 * new_area_covered_if_placed_at_p + 
         k3 * number_of_nearby_defences 

(k1, k2, और k3 मनमाना स्थिरांक है कि आप धुन करने की आवश्यकता होगी रहे हैं)

फिर, बस बेतरतीब ढंग से विभिन्न बिंदुओं का गुच्छा का नमूना, p और उच्चतम उपयोगिता वाला एक चुनें।

Answer 3

मैं एक समारोह को परिभाषित करता हूं कि उस स्थिति में रखे गए टावर के मूल्य को निर्धारित करता है। फिर उस समारोह में अधिकतमता की खोज करें और वहां एक टावर रखें।

समारोह के लिए एक संक्षिप्त वर्णन ऐसा दिखाई दे सकता:

if water return 0 

popsum = sum for all city over (population/distance) // it's better to have towers close by 

towersum = - sum for all existing towers (1/distance) // you want you towers spread somewhat evenly 

return popsum + towersum*f // f adjusts the relative importance of spreading towers equally and protecting the population centers with many towers 

एक उचित एल्गोरिथ्म के साथ शुरू करने के लिए देना चाहिए। सुधार के लिए आप तेजी से या धीमी बूंद पाने के लिए 1/दूरी फ़ंक्शन को कुछ अलग कर सकते हैं।

Answer 4

मैं एक फिटनेस फ़ंक्शन को लागू करने के साथ शुरू करूंगा जो किसी दिए गए मानचित्र पर टावरों के सेट द्वारा प्रदान की गई अपेक्षित सुरक्षा की गणना करता है।

आप "संरक्षित" क्षेत्र के अंदर आबादी की मात्रा की गणना करेंगे जहां दो टावरों द्वारा कवर किए गए क्षेत्रों को केवल एक टावर द्वारा कवर क्षेत्र से थोड़ा अधिक रेट किया गया है (सटीक स्केलिंग कारक गेम मैकेनिक्स पर बहुत निर्भर करता है, ' हालांकि)।

फिर आप नियुक्तियों के विभिन्न सेटों के साथ प्रयोग करने के लिए genetic algorithm का उपयोग कर सकते हैं और इसे कई (हुंडर्ड?) पुनरावृत्तियों के लिए चला सकते हैं।

यदि आपका फिटनेस फ़ंक्शन प्लेसमेंट की वास्तविक गुणवत्ता के लिए उपयुक्त है और आनुवंशिक एल्गोरिदम का कार्यान्वयन सही है, तो आपको उचित परिणाम प्राप्त करना चाहिए।

और एक बार जब आप ऐसा कर लेंगे तो आप एक हमले की योजना विकसित करना शुरू कर सकते हैं जो किसी भी रक्षा टावर प्लेसमेंट के किसी भी सेट के लिए हताहतों को अनुकूलित करने का प्रयास करता है।एक बार जब आप एक बार के खिलाफ दो आबादी सेट कर सकते हैं और इस तरह बेहतर रक्षा योजनाओं तक पहुंच सकते हैं (यह artificial life के मूल विचारों में से एक है)।