😟 ✊🏽 🍰 खेल थ्योरी और स्प्राग-ग्रैंड फंक्शन 🖕🏾 🛕 👩🏻‍🤝‍👨🏾

अच्छा दिन, प्रिय हेब्रोसोसिटी।

हाल ही में, ओलंपियाड प्रोग्रामिंग अधिक से अधिक व्यापक हो गई है, जिसका एक अभिन्न अंग एल्गोरिदम का ज्ञान है (और निश्चित रूप से, उनका उपयोग करने की क्षमता)।

मैं आपको गेम थ्योरी की मूल बातें बताना चाहता हूं, स्प्रा-ग्रैंड फंक्शन को साबित करने के लिए, कुछ क्लासिक निष्पक्ष समस्याओं को पार्स करने और उन्हें पायथन कोड के साथ चित्रित करने के लिए।

इसके बजाय एक अग्रदूत

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

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

खेल परिमित है
खेल में कोई ड्रॉ संभव नहीं
खिलाड़ी प्रतिद्वंद्वी की स्थिति के बारे में सभी जानकारी देखते हैं

ऐसे गेम के उदाहरणों में गेम निम्स , बाचे और अन्य गेम शामिल हैं। हम उनके बारे में थोड़ी देर बाद बात करेंगे, लेकिन अब हम चर्चा करेंगे कि शर्तों से क्या होगा।

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

इस प्रकार, "बराबर" खेलों से संबंधित खेलों के सिद्धांत में समस्याओं का समाधान खेल के राज्य ग्राफ का अध्ययन करने और अंतिम परिणाम का निर्धारण करने के लिए कम किया जा सकता है।

निम का खेल

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

प्रमेय # 1:

वर्तमान खिलाड़ी के लिए, रणनीति जीत रही है अगर और केवल अगर ¹ ढेर आकार का xor-positive सकारात्मक है।

आइए हम इसे साबित करते हैं।
मान लें कि हमारे पास मूल्यों की दो सरणियाँ हैं ([पहले] से पहले [] के बाद], जिनमें से एक में ([]) ढेर के आकार खिलाड़ी के कदम से पहले और दूसरे में ([] के बाद) संग्रहीत किए जाते हैं - खिलाड़ी के कदम के बाद।
हम खिलाड़ी की चाल से पहले और बाद में चर-खंड में xor-sums संग्रहीत करेंगे (जहां "^" xor ऑपरेशन है):
bf = [0] ^ से पहले [1] ^ ... ^ से पहले [एन - 1] ^ से पहले [एन]
af = के बाद [0] ^ के बाद [1] ^ ... ^ के बाद [N - 1] ^ के बाद [N]
फिर, xor गुणों के कोरोलरी का उपयोग करते हुए, हम लिख सकते हैं:
af = bf ^ से पहले [i] ^ के बाद [i], जहां "i" हीप की संख्या है, जहां से उस खिलाड़ी ने कदम उठाया था, जिसमें पत्थर लग गए।

उपरोक्त के आधार पर, हम प्रमेय सिद्ध करते हैं प्रमेय # 1 (हम दो मामलों पर विचार करते हैं: bf == 0 और bf! - 0:!
यदि bf == 0 है, तो वर्तमान स्थिति या तो पहले से ही खो रही है (यानी, इसमें कोई परिवर्तन नहीं हैं), या संक्रमण हैं, लेकिन समानता af == bf [i] ^ af [i] उनके लिए है, लेकिन इससे पहले [i]! = [i] के बाद, तब af! = 0, जिसका अर्थ है कि संक्रमण प्रेरण द्वारा विजयी अवस्था की ओर ले जाता है।
यदि bf! = 0 है, तो आपको यह निर्धारित करने की आवश्यकता है कि किस कदम के परिणामस्वरूप एक खोई हुई स्थिति होगी (यानी af == 0):
संख्या bf के बिट रिकॉर्ड पर विचार करें। सबसे महत्वपूर्ण नोनजरो बिट लें, क्यू द्वारा इसकी संख्या को दर्शाते हुए। आज्ञा देना एक संख्या से पहले संख्या [] जिसका qth बिट नॉनजरो है (दूसरे शब्दों में, वांछित ढेर की संख्या)।
मान लीजिए कि [k] के बाद [k] ^ bf से पहले (यह माना जाता है कि यह वांछित चाल है)। वह सही क्यों है? क्योंकि [k] के बाद [k] से पहले। यह इस तथ्य से निम्नानुसार है कि [k] और [k] से पहले qth से पुराने सभी बिट समान हैं, और qth बिट में, [k] से पहले एक है, और [k] के बाद शून्य है।
फिर हम गणना करते हैं:
af = bf ^ से पहले [k] ^ के बाद [k] = bf ^ से पहले [k] ^ (bf ^ से पहले [k] = 0
चूंकि इस कदम के दौरान एक्सर-राशि शून्य के बराबर है, इसलिए प्रमेय साबित होता है।

प्रमेय # 1 से क्या होता है? यह अनुसरण करता है कि किसी भी राज्य की तरह एक नीम-जैसा ("बराबर") खेल को एक समकक्ष से बदला जा सकता है, लेकिन एक ढेर से मिलकर, जिसका आकार पुराने राज्य में ढेर के आकार के XOR- योग के बराबर है।

स्प्राग-दादी समारोह

किसी भी "बराबर" खेल की स्थिति को ढेर के रूप में दर्शाया जा सकता है। यदि ढेर का आकार शून्य है, तो राज्य खो रहा है। अगर बराबर नहीं - जीत।
मान लीजिए कि हमारे पास एक निश्चित अवस्था G [] आकार के एक निश्चित ढेर X के बराबर है। यह संख्या प्रेरण द्वारा पाई जा सकती है। अगर हम जानते हैं कि राज्य G [i] m [i] से मेल खाता है, तो m [] इस प्रकार होगा:
m = मेक्सिको {m [1], ..., m [k]} ^२ ।

ठीक यही स्पैग-ग्रैडी का कार्य है: यदि हमें "समान" गेम के विजेता को निर्धारित करने की आवश्यकता है, तो हम इसे कम करते हैं-हीप्स, प्रत्येक ढेर के लिए जी () पर विचार करें और उनकी एक्स-राशि खोजें।
दूसरे शब्दों में, जी (के, एन, एम) = जी (के) ^ जी (एन) ^ जी (एम)।

कार्य

अब हम ओलंपियाड समस्या के उदाहरण से स्प्राग-ग्रैंड फंक्शन का विश्लेषण करेंगे जो मुझे समर कंप्यूटर स्कूल के क्वालीफाइंग दौर में मिला था। समस्या की स्थिति इस प्रकार थी:

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

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

कोड उदाहरण पर विचार करें। हम मानते हैं कि हमारे पास किनारों के साथ एक आसन्न मैट्रिक्स है (अगर शहर बी को शहर से पहले जला देता है तो हम किनारे a -> b को हटा देंगे)।
फिर इस कार्य के लिए स्प्राग-दादी समारोह की गणना निम्नानुसार की जाएगी:

def Grundy(): for i in range(N): if matrix[v][i] == 1: if Grundy(i) == 0: return 1 exit return 0

यदि फ़ंक्शन "1" देता है, तो एक इष्टतम गेम के साथ, व्लादिमीर जीतता है।

अब उसके साथ खेल की तरह स्थिति पर विचार करें, लेकिन कई स्थितियों के साथ। वहां मुट्ठी भर पत्थर रखें, जिनकी संख्या विषम है। एक बार में, आप ढेर से चार से अधिक पत्थर नहीं ले सकते। खेल तब तक जारी रहता है जब तक कि पत्थर खत्म नहीं हो जाते। जो पत्थर की एक समान संख्या लेता था वह जीत नहीं पाता है।
पहली नज़र में, इस खेल का अब स्प्राग-ग्रैंड फंक्शन का उपयोग करके विश्लेषण नहीं किया जा रहा है। क्यों? क्योंकि खेल की स्थिति न केवल मुट्ठी भर पत्थरों की संख्या निर्धारित करती है - खिलाड़ियों के पत्थर भी महत्वपूर्ण हैं। लेकिन यह विचार करना आसान है कि क्या आप खेल की स्थिति लेते हैं
संख्याओं के G () n, m और p, जहां n ढेर में पत्थरों की संख्या है, और m और p खिलाड़ियों के लिए पत्थरों की समता है (0 एक विषम संख्या है, 1 एक सम संख्या है)।

खेल समाप्त होने पर दो संभावित स्थितियां होती हैं, जिसमें n == 0:
जी (0, 0, 1) और जी (0, 1, 0)।
साधारण निम खेलों के लिए पहली स्थिति थोड़ी अचूक है - खिलाड़ी एक चाल नहीं बना सकता है, लेकिन चूंकि उसके पत्थरों की संख्या समान है, इसलिए वह हार नहीं गया। इसे ग्राफ़ पर चित्रित करने के लिए, एक संक्रमण जोड़ें:
(0, 0, 1) -> (0, 1, 0)
यदि हम अब ग्राफ को दर्शाते हैं, तो हम निम्नलिखित आवृत्ति को नोट कर सकते हैं:
जी (एन, एम, पी) = जी (ए, एम, पी),
जहाँ a = n mod 6
यह हमें क्या देता है? ढेर में पत्थरों को 27 होने दें। फिर जी (27, 0, 0) = जी (3, 0, 0) = 3. शुरुआती जीतता है, और जीतने की स्थिति बनाने वाली चाल का अनुवाद करना होगा (3, 0, 0) -> ( १, ०, ०)। इसलिए, जीत के लिए, शुरुआतकर्ता को दो पत्थर लेने की जरूरत है।

संक्षेप में कहना

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

नोट

⁰ इस मुद्दे के विवाद के बावजूद, शून्य को भी एक प्राकृतिक संख्या माना जाएगा।
संख्याओं का ¹ xor-a [N] अभिव्यक्ति है [1] ^ [a] [2] ^ ... ^ [a [N]।
संख्याओं के एक सेट के ² मेक्सिको इस सेट (अंग्रेजी न्यूनतम अपवर्तक से) में नहीं मिला सबसे छोटा गैर-नकारात्मक नंबर है।

साहित्य

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

स्व-अध्ययन के लिए कार्य

यदि आप इस विषय पर समस्याओं को हल करना चाहते हैं, तो मैं इस एक और अन्य समान कार्यों की सलाह देता हूं।

सौभाग्य!

UPD : "स्पोर्ट्स प्रोग्रामिंग" में चले गए।

खेल थ्योरी और स्प्राग-ग्रैंड फंक्शन