Map-coloring games
कई मानचित्र-रंग खेलों का अध्ययन संयोजन खेल सिद्धांत में किया जाता है। सामान्य विचार यह है कि हमें एक नक्शा दिया जाता है जिसमें क्षेत्र बनाए जाते हैं लेकिन सभी क्षेत्र रंगीन नहीं होते हैं। दो खिलाड़ी, बाएँ और दाएँ, बारी-बारी से एक बिना रंग वाले क्षेत्र में रंग लेते हैं, जो विभिन्न बाधाओं के अधीन होता है, जैसा कि मानचित्र-रंग की समस्या में होता है। चाल की बाधाएं और जीतने की स्थिति विशेष खेल की विशेषताएं हैं। कुछ खिलाड़ियों को दोहरे ग्राफ के शीर्षों को रंगना आसान लगता है, जैसा कि चार रंग प्रमेय में है। खेल की इस विधि में, क्षेत्रों को छोटे वृत्तों द्वारा दर्शाया जाता है, और पड़ोसी क्षेत्रों के लिए वृत्त रेखा खंडों या वक्रों द्वारा जुड़े होते हैं। इस विधि के फायदे यह हैं कि केवल एक छोटे से क्षेत्र को मोड़ पर चिह्नित करने की आवश्यकता होती है, और यह कि प्रतिनिधित्व आमतौर पर कागज या स्क्रीन पर कम जगह लेता है। पेंसिल और कागज के बजाय कंप्यूटर इंटरफेस के साथ खेलते समय पहला लाभ कम महत्वपूर्ण होता है। गो स्टोन्स या चेकर्स के साथ खेलना भी संभव है। प्रत्येक खेल में एक अंतर्निहित बाधा रंग क्षेत्रों में खिलाड़ियों के लिए उपलब्ध रंगों का समूह है। यदि बाएँ और दाएँ के लिए समान रंग उपलब्ध हैं, तो खेल निष्पक्ष है; अन्यथा खेल पक्षपातपूर्ण है। रंगों का सेट खेल की स्थिति पर भी निर्भर कर सकता है; उदाहरण के लिए यह आवश्यक हो सकता है कि उपयोग किया गया रंग पिछली चाल में उपयोग किए गए रंग से अलग हो। एक चाल पर मानचित्र-आधारित बाधाएं आमतौर पर रंगीन होने वाले क्षेत्र और उसके पड़ोसियों पर आधारित होती हैं, जबकि मानचित्र-रंग की समस्या में, क्षेत्रों को पड़ोसी माना जाता है जब वे एक बिंदु से अधिक लंबी सीमा के साथ मिलते हैं। शास्त्रीय मानचित्र-रंग समस्या के लिए आवश्यक है कि किसी भी दो पड़ोसी क्षेत्रों को एक ही रंग न दिया जाए। शास्त्रीय चाल बाधा किसी क्षेत्र को उसके पड़ोसी के समान रंग से रंगने पर प्रतिबंध लगाकर इसे लागू करती है। शास्त्रीय विरोधी बाधा किसी क्षेत्र को उस रंग से रंगने से रोकती है जो उसके पड़ोसियों में से किसी एक के रंग से अलग हो। एक अन्य प्रकार की बाधा प्रवेश है, जिसमें पहले के बाद प्रत्येक चाल को पिछले चाल पर रंगीन क्षेत्र के पड़ोसी को रंगना चाहिए। एंटी-एंटेलमेंट एक और संभावित बाधा है। अन्य प्रकार की बाधाएं संभव हैं, जैसे कि उन क्षेत्रों की आवश्यकता जो पड़ोसियों के पड़ोसी हैं, अलग या समान रंगों का उपयोग करने के लिए। इस अवधारणा को ग्राफ दूरी दो पर क्षेत्रों पर लागू होने के रूप में माना जा सकता है, और अधिक दूरी के लिए सामान्यीकृत किया जा सकता है। जीतने की स्थिति विजेता आमतौर पर आगे बढ़ने वाला अंतिम खिलाड़ी होता है। इसे सामान्य खेल परंपरा कहा जाता है। मिसेरे प्ले कन्वेंशन खेल को हारने के लिए आगे बढ़ने वाले अंतिम खिलाड़ी को मानता है। जीतने और हारने की अन्य संभावित परिस्थितियाँ संभव हैं, जैसे कि क्षेत्र की गिनती, जैसा कि गो में है। मोनोक्रोम और प्रकार ये खेल, जो (सिल्वरमैन, 1971) में दिखाई दिए, सभी शास्त्रीय चाल बाधा का उपयोग करते हैं। निष्पक्ष खेल "मोनोक्रोम" में केवल एक ही रंग उपलब्ध होता है, इसलिए प्रत्येक चाल रंगीन क्षेत्र और उसके पड़ोसियों को खेल से हटा देती है। "बाइक्रोम" में दोनों खिलाड़ियों के पास दो रंगों का विकल्प होता है, जो शास्त्रीय स्थिति के अधीन होता है। दोनों खिलाड़ी एक ही दो रंगों में से चुनते हैं, इसलिए खेल निष्पक्ष है। "ट्राइक्रोम" खिलाड़ियों के लिए इसे तीन रंगों तक विस्तारित करता है। शर्त को किसी भी निश्चित संख्या में रंगों तक बढ़ाया जा सकता है, जिससे आगे के खेल प्राप्त हो सकते हैं। जैसा कि सिल्वरमैन ने उल्लेख किया है, हालांकि चार रंग प्रमेय से पता चलता है कि किसी भी समतल मानचित्र को चार रंगों से रंगा जा सकता है, यह उन मानचित्रों पर लागू नहीं होता है जिनमें कुछ रंग भरे गए हैं, इसलिए चार से अधिक रंग जोड़ने से खेल पर प्रभाव पड़ सकता है। "कोल" में शास्त्रीय बाधा के अधीन दो रंग हैं, लेकिन बाएँ को केवल बी "एल" यूई क्षेत्रों को रंगने की अनुमति है, जबकि दाएँ को केवल उन्हें "आर" एड रंगने की अनुमति है। इस प्रकार यह एक पक्षपातपूर्ण खेल है, क्योंकि खेल के दौरान बाएं और दाएं के लिए अलग-अलग चालें उपलब्ध हो जाती हैं। "स्नोर्ट" दो रंगों के समान पक्षपातपूर्ण कार्य का उपयोग करता है, लेकिन शास्त्रीय बाधा के साथः पड़ोसी क्षेत्रों को अलग-अलग रंग देने की अनुमति नहीं है। क्षेत्रों को रंग देने को बैलों और गायों को खेत सौंपने के रूप में समझाया गया है, जहां पड़ोसी खेतों में विपरीत लिंग के मवेशी नहीं हो सकते हैं, ऐसा न हो कि वे अपने चराई से विचलित हो जाएं। इन खेलों को (कॉनवे, 1976) में प्रस्तुत और विश्लेषण किया गया था। नाम बाधाओं में अंतर (शास्त्रीय मानचित्र रंग बनाम पशु शोर) के लिए स्मरणीय हैं, लेकिन कॉनवे उन्हें अपने सहयोगियों कॉलिन वाउट और साइमन नॉर्टन को भी श्रेय देते हैं। अन्य खेल निष्पक्ष खेल "संपर्क" (सिल्वरमैन, 1971) प्रवेश बाधा के साथ एक ही रंग का उपयोग करता हैः सभी पहले रंग के बाद सबसे हाल के रंगीन क्षेत्र के पड़ोसी के साथ चलते हैं। सिल्वरमैन "मिसेरे कॉन्टैक्ट" का एक उदाहरण भी प्रदान करते हैं। मानचित्र-रंग खेल की अवधारणा को एंजेल्स और डेविल्स जैसे खेलों को शामिल करने के लिए विस्तारित किया जा सकता है, जहां रंग के नियम स्वाद में कुछ अलग हैं। संदर्भ संशोधित और संशोधित के रूप में पुनर्मुद्रित और संयुक्त खेल सिद्धांत गणितीय खेलों के रूप में पुनर्मुद्रित