Hry omalovánky map - Map-coloring games
Několik zbarvení mapy hry jsou studovány v kombinatorická teorie her. Obecná myšlenka je, že dostaneme mapu s nakreslenými regiony, ale ne všechny regiony zbarvené. Dva hráči, Vlevo, odjet a Že jo, střídejte barvení v jedné nezbarvené oblasti za kolo, s různými omezeními. Omezení pohybu a podmínky výhry jsou vlastnosti konkrétní hry.
Pro některé hráče je snazší vymalovat vrcholy duální graf, jako v Čtyřbarevná věta. V tomto způsobu hraní jsou regiony reprezentovány malými kruhy a kruhy pro sousední regiony jsou spojeny úsečkami nebo křivkami. Výhodou této metody je, že na turnu musí být vyznačena pouze malá plocha a že reprezentace obvykle zabírá méně místa na papíře nebo obrazovce. První výhoda je při hraní s počítačovým rozhraním místo tužky a papíru méně důležitá. Je také možné hrát si s Jít kameny nebo dáma.
Přesunout omezení
Inherentní omezení v každé hře je sada barev, která je k dispozici hráčům v barvících oblastech. Li Vlevo, odjet a Že jo mají stejné barvy k dispozici, hra je nestranný; jinak hra je partyzán. Sada barev může také záviset na stavu hry; může například být požadováno, aby použitá barva byla odlišná od barvy použité v předchozím tahu.
Omezení založená na mapě při pohybu jsou obvykle založena na oblasti, která má být zbarvena, a jejích sousedech, zatímco v problém s barvením mapy, regiony jsou považovány za sousedy, když se setkají podél hranice delší než jeden bod. Klasický problém s barvením mapy vyžaduje, aby žádné dva sousední regiony neměly stejnou barvu. The klasický omezení pohybu to vynutí tím, že zakáže zbarvení oblasti se stejnou barvou jako některý z jejích sousedů. The antiklasický omezení zakazuje vybarvení oblasti barvou, která se liší od barvy jednoho z jejích sousedů.
Dalším omezením je obviňování, ve kterém každý tah po prvním musí vybarvit souseda regionu zabarveného na předchozím tahu. Protiúnos je další možné omezení.
Jsou možné i jiné druhy omezení, například požadavek, aby oblasti, které sousedí se sousedy, používaly různé nebo stejné barvy. Tuto koncepci lze považovat za aplikovatelnou na regiony v vzdálenost grafu dvě a lze je zobecnit na větší vzdálenosti.
Vítězné podmínky
Vítězem je obvykle poslední hráč, který se pohybuje. Tomu se říká normální hra konvence. The misere hra konvence považuje posledního hráče, který se přestěhoval, aby hru prohrál. Jsou možné i další možné podmínky výhry a prohry, například počítání území, například v Jít.
Monochromatický a varianty
Všechny tyto hry, které se objevily v (Silverman, 1971), využívají omezení klasického pohybu. V nestranná hra Černobílý je k dispozici pouze jedna barva, takže každý pohyb odstraní barevnou oblast a její sousedy ze hry. v Bichrome oba hráči mají na výběr ze dvou barev, s výhradou klasických podmínek. Oba hráči si vybírají ze stejných dvou barev, takže hra je nestranný. Trichrom rozšiřuje to na tři barvy pro hráče. Podmínku lze rozšířit na libovolný pevný počet barev, čímž se získají další hry. Jak uvádí Silverman, ačkoli Čtyřbarevná věta ukazuje, že libovolná planární mapa může být obarvena čtyřmi barvami, nevztahuje se na mapy, ve kterých byly vyplněny některé barvy, takže přidání více než čtyř barev může mít na hry vliv.
Col a Snort
v Plk existují dvě barvy podléhající klasickému omezení, ale Vlevo, odjet je povoleno pouze barevné oblasti Blue, zatímco Že jo je povoleno je pouze obarvit Rvyd. Jedná se tedy o partyzánská hra, protože pro Vlevo, odjet a Že jo v průběhu hry.
Šňupat používá podobné partyzánské přiřazení dvou barev, ale s antiklasickým omezením: sousedním regionům není povoleno přidělit různé barvy. Zbarvení oblastí je vysvětleno jako přiřazení polí býkům a kravám, kde sousední pole nemusí obsahovat dobytek opačného pohlaví, aby nebyl vyrušen z pastvy.
Tyto hry byly prezentovány a analyzovány v (Conway, 1976). Názvy jsou mnemotechnické pro rozdíl v omezeních (klasický zbarvení mapy versus zvuky zvířat), ale Conway je také připisuje svým kolegům Colinovi Voutovi a Simonovi Nortonovi.
Ostatní hry
The nestranná hra Kontakt (Silverman, 1971) používá jedinou barvu s omezením uváznutí: všechny tahy po první barvě souseda naposledy zbarvené oblasti. Silverman také poskytuje příklad Misère Kontakt.
Koncept hry s barvením map lze rozšířit i na hry jako Andělé a ďáblové, kde jsou pravidla pro barvení trochu odlišná v chuti.
Reference
- Conway, John Horton (1976). O číslech a hrách. Akademický tisk. ISBN 0-12-186350-6. Revidováno a přetištěno jako
- --- (2000). O číslech a hrách. A K Peters. ISBN 1-56881-127-6.CS1 maint: číselné názvy: seznam autorů (odkaz)
- Silverman, David L. (1971). Tvůj pohyb. McGraw-Hill. Revidováno a přetištěno jako
- --- (1991). Your Move: logické, matematické a slovní hádanky pro nadšence. Dover Press. ISBN 0-486-26731-8.CS1 maint: číselné názvy: seznam autorů (odkaz)