Карта бояу ойындары мен комбинаторлық ойын теориясы
Map-coloring games
Ойын теориясындағы карта бояу ойындары зерттеледі. Екі ойыншы кезегімен аймақтарды бояйды, ережелер мен жеңіс шарттары әртүрлі. Двойной граф та қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ойын теориясындағы ойындар
Games in game theory
Комбинаторлық ойын теориясында бірнеше карта бояу ойындары зерттеледі. Басты идея – бізге аймақтары сызылған, бірақ барлық аймақтары боялмаған карта беріледі. Екі ойыншы, Сол және Оң, карта бояу мәселесіндегідей, түрлі шектеулерге сәйкес кезекпен бір боялмаған аймақты бояйды. Ойынның қозғалыс шектеулері мен жеңіс шарты осы ойынның ерекшеліктері болып табылады. Кейбір ойыншылар төрт түс теоремасындағыдай, қос графтың төбелерін бояуды ыңғайлырақ деп санайды. Осы ойын тәсілінде аймақтар кішкентай шеңберлермен көрсетіледі, ал көршілес аймақтардың шеңберлері сызық сегменттерімен немесе қисық сызықтармен байланыстырылады. Бұл тәсілдің артықшылығы – әр қадамда тек кішкентай аумақты белгілеу қажет, сондай-ақ бейнелеу әдетте қағаз немесе экранда аз орын алады. Компьютерлік интерфейспен қарындаш пен қағаздың орнына ойнағанда бірінші артықшылықтың маңызы азаяды. Го тастарымен немесе шашкамен ойнау да мүмкін.
Several map coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints, as in the map coloring problem. The move constraints and the winning condition are features of the particular game. Some players find it easier to color vertices of the dual graph, as in the Four color theorem. In this method of play, the regions are represented by small circles, and the circles for neighboring regions are linked by line segments or curves. The advantages of this method are that only a small area need be marked on a turn, and that the representation usually takes up less space on the paper or screen. The first advantage is less important when playing with a computer interface instead of pencil and paper. It is also possible to play with Go stones or Checkers.
Жылжыту шектеулері
Әр ойынның өзіндік шектеулері – ойыншылардың аймақтарды түстеу үшін қолда бар түстер жиынтығы. Егер сол және оң жақтағы ойыншылардың қолда бар түстері бірдей болса, ойын бейтарап; әйтпесе, ойын партиялық болады. Түстер жиынтығы ойынның күйіне байланысты да болуы мүмкін; мысалы, қолданылған түс алдыңғы қадамда қолданылған түстен өзгеше болуы керек. Картаға негізделген қадамдардағы шектеулер әдетте түстелмелі аймаққа және оның көршілеріне негізделген, ал картаны түстеу мәселесінде аймақтар, егер олар бір нүктеден ұзақ шекарада жанасса, көршілер саналады. Классикалық картаны түстеу мәселесі екі көрші аймақтың бірдей түспен боялмауын талап етеді. Классикалық қадам шектеуі осыны көрші аймақтың түсімен бояуға тыйым салу арқылы қамтамасыз етеді. Антиклассикалық шектеу аймақты көршілерінің бірінен өзгеше түспен бояуға тыйым салады. Тағы бір шектеу – тікелей байланыс, онда бірінші қадамнан кейінгі әрбір қадам алдыңғы қадамда түстелген аймақтың көршісін түстеуі керек. Анти-тікелей байланыс – тағы бір мүмкін шектеу. Көрші аймақтардың көршілеріне әртүрлі немесе бірдей түстерді қолдануды талап ету сияқты басқа да шектеулер болуы мүмкін. Бұл ұғымды екі қашықтықтағы аймақтарға қатысты қарастыруға болады және оны одан да үлкен қашықтықтарға жалпылауға болады.
An inherent constraint in each game is the set of colors available to the players in coloring regions. If Left and Right have the same colors available to them, the game is impartial; otherwise the game is partisan. The set of colors could also depend on the state of the game; for instance it could be required that the color used be different from the color used on the previous move. The map based constraints on a move are usually based on the region to be colored and its neighbors, whereas in the map coloring problem, regions are considered to be neighbors when they meet along a boundary longer than a single point. The classical map coloring problem requires that no two neighboring regions be given the same color. The classical move constraint enforces this by prohibiting coloring a region with the same color as one of its neighbor. The anticlassical constraint prohibits coloring a region with a color that differs from the color of one of its neighbors. Another kind of constraint is entailment, in which each move after the first must color a neighbor of the region colored on the previous move. Anti entailment is another possible constraint. Other sorts of constraints are possible, such as requiring regions that are neighbors of neighbors to use different or identical colors. This concept can be considered as applying to regions at graph distance two, and can be generalized to greater distances.
Жеңіс шарттары
Әдетте жеңімпаз соңғы қозғалыс жасаған ойыншы болады. Бұл – қалыпты ойын шарты деп аталады. Misère шарты бойынша соңғы қозғалыс жасаған ойыншы ойында жеңіліп қалады. Го сияқты, аумақты санау сияқты, жеңіс пен жеңіліс үшін басқа да шарттар болуы мүмкін.
The winner is usually the last player to move. This is called the normal play convention. The misère play convention considers the last player to move to lose the game. There are other possible winning and losing conditions possible, such as counting territory, as in Go.
Монохром және нұсқалары
(Silverman, 1971) жылғы еңбекте пайда болған бұл ойындардың бәрі классикалық қимыл шектеуін қолданады. "Монохром" атты тең мүмкіндікті ойында тек бір түс қана қол жетімді, сондықтан әр қимыл түсті аймақты және оның көршілес бөліктерін ойыннан шығарады. "Бихром" ойынында екі ойыншының әрқайсы классикалық шарттарға сәйкес екі түс таңдау мүмкіндігі бар. Екі ойыншы да бірдей екі түс арасынан таңдайды, демек ойын тең мүмкіндікті. "Трихром" ойынында ойыншыларға үш түс ұсынылады. Бұл шартты кез келген белгілі бір түс санына дейін кеңейтуге болады, соның нәтижесінде жаңа ойындар туындайды. Сильверман атап өткендей, төрт түстің теоремасы кез келген жазық картаны төрт түспен бояуға болатынын көрсетсе де, ол кейбір түстермен толықтырылған карталарға қатысты емес, сондықтан төрт түстен артық түс қосу ойындарға әсер етіп қалуы мүмкін.
These games, which appeared in (Silverman, 1971), all use the classical move constraint. In the impartial game "Monochrome" there is only one color available, so every move removes the colored region and its neighbors from play. In "Bichrome" both players have a choice of two colors, subject to the classical condition. Both players choose from the same two colors, so the game is impartial. "Trichrome" extends this to three colors to the players. The condition can be extended to any fixed number of colors, yielding further games. As Silverman mentions, although the Four color theorem shows that any planar map can be colored with four colors, it does not apply to maps in which some of the colors have been filled in, so adding more than four colors may have an effect on the games.
Коль және Снорт
"Col" ойынында классикалық шектеуге бағынатын екі түс бар, бірақ Сол жаққа тек "B" және "L" аймақтарын көк түспен бояуға рұқсат етіледі, ал Оң жаққа тек "R" аймақтарын қызыл түспен бояуға рұқсат етіледі. Осылайша, бұл партиялық ойын, себебі ойын барысында Сол және Оң жаққа әртүрлі мүмкіндіктер ашылады. "Snort" ойыны да екі түсті ұқсас партиялық түрде бөледі, бірақ антиклассикалық шектеумен: көршілес аймақтарға әртүрлі түстер беруге болмайды. Аймақтарды бояу – бұл бұқалар мен сиырларға арналған жайылымдық жерлерді бөлу ретінде түсіндіріледі, мұнда көршілес жайылымдарда қарама-қарсы жынысты мал болмауы керек, әйтпесе олар жайылымнан алаңдап, көңілі аууы мүмкін. Бұл ойындар (Конвей, 1976) жұмысында сипатталған және талданған. Атаулар шектеулердегі айырмашылықты есте сақтауға көмектеседі (классикалық карта бояуына қарсы жануарлардың дыбыстары), бірақ Конвей оларды өз әріптестері Колин Воут пен Саймон Нортонға да жатқызады.
In "Col" there are two colors subject to the classical constraint, but Left is only allowed to color regions B"l"ue, while Right is only allowed to color them "R"ed. Thus this is a partisan game, because different moves become available to Left and Right in the course of play. "Snort" uses a similar partisan assignment of two colors, but with the anticlassical constraint: neighboring regions are not allowed to be given different colors. Coloring the regions is explained as assigning fields to bulls and cows, where neighboring fields may not contain cattle of the opposite sex, lest they be distracted from their grazing. These games were presented and analyzed in (Conway, 1976). The names are mnemonic for the difference in constraints (classical map coloring versus animal noises), but Conway also attributes them to his colleagues Colin Vout and Simon Norton.
Басқа ойындар
"Contact" (Silverman, 1971) бейтарап ойыны бір түс қолданады, онда бірінші түстің барлық келесі қадамдары ең соңғы боялған аймаққа жақын болуы керек. Сильверман "Misère Contact" мысалын да келтіреді. Карта бояу ойынының түсінігі "Періштелер мен Шайтандар" сияқты, бояу ережелері аздап өзгеше болатын ойындарды да қамтуы мүмкін.
The impartial game "Contact" (Silverman, 1971) uses a single color with the entailment constraint: all moves after the first color a neighbor of the most recently colored region. Silverman also provides an example of "Misère Contact". The concept of a map coloring game may be extended to cover games such as Angels and Devils, where the rules for coloring are somewhat different in flavor.