Poset game
संयोजी खेल सिद्धांत में, पोजेट खेल रणनीति के गणितीय खेल हैं, जो निम और चोम्प जैसे कई प्रसिद्ध खेलों को सामान्यीकृत करते हैं। इस तरह के खेलों में, दो खिलाड़ी एक पोजेट (एक आंशिक रूप से क्रमबद्ध सेट) के साथ शुरुआत करते हैं, और पोजेट में एक अंक चुनते हुए, उसे और उससे अधिक के सभी अंकों को हटा देते हैं। जिस खिलाड़ी के पास चुनने के लिए कोई बिंदु नहीं बचा है, वह हार जाता है। खेल खेल एक आंशिक रूप से क्रमबद्ध सेट (पी, <) को देखते हुए, पी से एक्स को हटाकर बनाए गए पोजेट को दर्शाते हैं। पी पर एक पोजेट गेम, जो पारंपरिक रूप से एलिस और बॉब नाम के दो खिलाड़ियों के बीच खेला जाता है, इस प्रकार हैः एलिस एक बिंदु x ω पी चुनती है; इस प्रकार पी को पीएक्स से प्रतिस्थापित करती है, और फिर बॉब को मोड़ देती है जो पीएक्स पर खेलता है, और एलिस को मोड़ देता है। एक खिलाड़ी हार जाता है अगर उसकी बारी होती है और चुनने के लिए कोई अंक नहीं होते हैं। उदाहरण यदि पी एक परिमित पूरी तरह से क्रमबद्ध समूह है, तो पी में खेल खेलना बिल्कुल निम के खेल के समान है जिसका आकार |P। के ढेर के साथ होता है। क्योंकि, दोनों खेलों में, एक ऐसी चाल चुनना संभव है जो एक ही प्रकार के खेल की ओर ले जाए जिसका आकार |P। से छोटी कोई भी संख्या हो। इसी तरह, कुल आदेशों के असंबद्ध संघ के साथ एक पॉज़ेट गेम निम के खेल के बराबर है जिसमें पॉज़ेट में जंजीरों के बराबर आकार के कई ढेर होते हैं। हैकनबुश का एक विशेष मामला, जिसमें सभी किनारे हरे होते हैं (किसी भी खिलाड़ी द्वारा काटे जा सकते हैं) और प्रत्येक विन्यास एक जंगल का रूप लेता है, इसे एक स्थिति पर एक स्थिति खेल के रूप में व्यक्त किया जा सकता है, जिसमें प्रत्येक तत्व x के लिए, अधिक से अधिक एक तत्व y होता है जिसके लिए x y को कवर करता है। यदि x, y को कवर करता है, तो y उस जंगल में x का मूल है जिस पर खेल खेला जाता है। चोम्प को कुल आदेशों के उत्पाद पर एक स्थिति खेल के रूप में समान रूप से व्यक्त किया जा सकता है, जिसमें से अनंत को हटा दिया गया है। ग्रंडी वैल्यू पॉसेट गेम निष्पक्ष गेम हैं, जिसका अर्थ है कि एलिस के लिए उपलब्ध हर चाल बॉब के लिए भी उपलब्ध होगी यदि एलिस को पास करने की अनुमति दी गई थी, और इसके विपरीत। इसलिए, स्प्रेग-ग्रंडी प्रमेय के अनुसार, एक स्थिति खेल में प्रत्येक स्थिति का एक ग्रंडी मान होता है, एक संख्या जो निम के खेल में एक समकक्ष स्थिति का वर्णन करती है। एक स्थिति के ग्रान्डी मान की गणना सबसे कम प्राकृतिक संख्या के रूप में की जा सकती है जो किसी भी पी. एक्स., एक्स. पी. का ग्रान्डी मान नहीं है अर्थात इस संख्या का उपयोग स्थिति खेल में इष्टतम खेल का वर्णन करने के लिए किया जा सकता है। विशेष रूप से, ग्रंडी मान शून्य नहीं होता है जब खिलाड़ी की जीत की रणनीति होती है, और शून्य होता है जब वर्तमान खिलाड़ी अपने प्रतिद्वंद्वी के इष्टतम खेल के खिलाफ नहीं जीत सकता है। खेल में एक जीतने की रणनीति में एक ऐसी स्थिति में जाना शामिल है जिसका ग्रंडी मूल्य शून्य है, जब भी यह संभव हो। रणनीति चोरी एक रणनीति-चोरी तर्क से पता चलता है कि ग्रंडी मूल्य प्रत्येक स्थिति के लिए गैर-शून्य है जिसमें सर्वोच्चता है। अगर, दूसरी ओर, Px का गैर-शून्य ग्रंडी मान है, तो Px में एक विजयी चाल y होनी चाहिए, जैसे कि (Px) y का ग्रंडी मान शून्य है। लेकिन इस धारणा से कि x एक सर्वोच्च है, x> y और (Px) y = Py, इसलिए जीतने वाली चाल y भी P में उपलब्ध है और फिर से P का एक गैर-शून्य ग्रंडी मान होना चाहिए। अधिक तुच्छ कारणों से एक असीम के साथ एक स्थिति का एक गैर-शून्य ग्रंडी मूल्य भी होता हैः अनंत की ओर बढ़ना हमेशा एक विजयी चाल होती है। जटिलता एक मनमाने ढंग से सीमित स्थिति वाले खेल के विजेता का फैसला करना पी. एस. पी. ए. सी. ई.-पूर्ण है। इसका मतलब है कि जब तक पी = पी. एस. पी. ए. सी. ई. नहीं है, तब तक एक मनमाने पोजेट गेम के ग्रंडी मान की गणना करना कम्प्यूटेशनल रूप से मुश्किल है। संदर्भ संयुक्त खेल सिद्धांत गणितीय खेल