Gry w kolorowanie map
Kombinatoryczna teoria gier bada kilka gier polegających na kolorowaniu map . Ogólna idea polega na tym, że otrzymujemy mapę z narysowanymi regionami, ale nie wszystkie regiony są pokolorowane. Dwóch graczy, Lewy i Prawy , na zmianę koloruje jeden niekolorowany region na turę, z zastrzeżeniem różnych ograniczeń. Ograniczenia ruchu i warunek wygranej są cechami konkretnej gry.
Niektórym graczom łatwiej jest pokolorować wierzchołki grafu dualnego , jak w twierdzeniu o czterech kolorach . W tej metodzie gry regiony są reprezentowane przez małe kółka, a okręgi sąsiednich regionów są połączone odcinkami linii lub krzywymi. Zaletą tej metody jest to, że na zakręcie trzeba zaznaczyć tylko niewielki obszar, a reprezentacja zwykle zajmuje mniej miejsca na papierze lub ekranie. Pierwsza zaleta jest mniej istotna, gdy gra się interfejsem komputerowym zamiast ołówkiem i papierem. Możliwa jest również gra Go lub warcabami .
Ograniczenia ruchu
Nieodłącznym ograniczeniem w każdej grze jest zestaw kolorów dostępnych dla graczy w regionach do kolorowania. Jeśli lewy i prawy mają do dyspozycji te same kolory, gra jest bezstronna ; w przeciwnym razie gra jest stronnicza . Zestaw kolorów może również zależeć od stanu gry; na przykład może być wymagane, aby użyty kolor różnił się od koloru użytego w poprzednim ruchu.
Ograniczenia ruchu oparte na mapie są zwykle oparte na regionie, który ma być pokolorowany, i jego sąsiadach, podczas gdy w problemie z kolorowaniem mapy regiony są uważane za sąsiadów, gdy stykają się wzdłuż granicy dłuższej niż pojedynczy punkt. Klasyczny problem kolorowania mapy wymaga, aby żadne dwa sąsiednie regiony nie miały tego samego koloru. Klasyczne ograniczenie ruchu wymusza to, zabraniając kolorowania regionu tym samym kolorem, co jeden z jego sąsiadów . Ograniczenie antyklasyczne zabrania kolorowania regionu kolorem, który różni się od koloru jednego z jego sąsiadów.
Innym rodzajem ograniczenia jest wynikanie , w którym każdy ruch po pierwszym musi pokolorować sąsiada regionu pokolorowanego w poprzednim ruchu. Innym możliwym ograniczeniem jest przeciwdziałanie powiązaniu .
Możliwe są inne rodzaje ograniczeń, takie jak wymaganie, aby regiony sąsiadujące z sąsiadami używały różnych lub identycznych kolorów. Koncepcję tę można uznać za odnoszącą się do regionów w odległości wykresu dwa i można ją uogólnić na większe odległości.
Zwycięskie warunki
Zwycięzcą jest zwykle ostatni gracz, który się poruszy. Nazywa się to normalną konwencją gry . Konwencja gry misère uważa, że ostatni gracz, który się poruszy, przegrywa grę. Istnieją inne możliwe warunki wygranej i przegranej, takie jak liczenie terytorium, jak w Go .
Monochromatyczne i warianty
Wszystkie te gry, które pojawiły się w (Silverman, 1971), wykorzystują klasyczne ograniczenie ruchu. W bezstronnej grze Monochrome dostępny jest tylko jeden kolor, więc każdy ruch usuwa kolorowy region i jego sąsiadów z gry. W Bichrome obaj gracze mają do wyboru dwa kolory, z zastrzeżeniem warunku klasycznego. Obaj gracze wybierają z tych samych dwóch kolorów, więc gra jest bezstronna . Trichrome rozszerza to do trzech kolorów dla graczy. Warunek można rozszerzyć na dowolną ustaloną liczbę kolorów, uzyskując dalsze gry. Jak wspomina Silverman, chociaż Twierdzenie o czterech kolorach pokazuje, że każdą planarną mapę można pokolorować czterema kolorami, nie dotyczy to map, w których niektóre kolory zostały wypełnione, więc dodanie więcej niż czterech kolorów może mieć wpływ na gry.
Kol i Snort
W Col są dwa kolory podlegające klasycznemu ograniczeniu, ale Lewy może pokolorować tylko regiony na niebiesko , podczas gdy Prawy może tylko pokolorować je na czerwono . Jest to więc gra partyzancka , ponieważ w trakcie gry różne ruchy stają się dostępne dla lewej i prawej strony .
Snort używa podobnego partyzanckiego przypisania dwóch kolorów, ale z antyklasycznym ograniczeniem: sąsiadującym regionom nie wolno nadawać różnych kolorów. Kolorowanie regionów jest wyjaśnione jako przypisywanie pól bykom i krowom, przy czym sąsiednie pola nie mogą zawierać bydła przeciwnej płci, aby nie odwracało ich uwagi od wypasu.
Gry te zostały przedstawione i przeanalizowane w (Conway, 1976) . Nazwy są mnemoniczne ze względu na różnice w ograniczeniach (klasyczna kolorystyka mapy w porównaniu z odgłosami zwierząt), ale Conway przypisuje je również swoim kolegom Colinowi Voutowi i Simonowi Nortonowi.
Inne gry
Bezstronna gra Kontakt (Silverman, 1971) używa jednego koloru z ograniczeniem implikacji: wszystkie poruszają się po pierwszym kolorze sąsiada z ostatnio kolorowanego regionu. Silverman podaje również przykład Misère Contact .
Koncepcję gry polegającej na kolorowaniu map można rozszerzyć na gry takie jak Anioły i diabły , w których zasady kolorowania mają nieco inny smak.
- Conway, John Horton (1976). O liczbach i grach . Prasa akademicka . ISBN 0-12-186350-6 . Poprawione i przedrukowane jako
- — (2000). O liczbach i grach . AK Peters . ISBN 1-56881-127-6 .
- Silverman, David L. (1971). Twój Ruch . McGraw-Hill . Poprawione i przedrukowane jako
- — (1991). Your Move: logiczne, matematyczne i słowne łamigłówki dla entuzjastów . Dover Press . ISBN 0-486-26731-8 .