Dominuese

Sample game of Domineering played on a 5x5 board, with the horizontal player ("H" or "Right") making the first move, and losing in the 13th round of play.
Genres	tile-based game
Players	2
Chance	none
Skills	strategy

Dominimi (i quajtur edhe Stop-Gate ose Crosscram) është një lojë matematikore që mund të luajtur në çdo koleksion katrorësh në një fletë grafiku. Për shembull, mund të luajtur në një katror 6×6, një drejtkëndësh, një poliomino tërësisht të parregullt, ose një kombinim i çdo numri përbërësish të tillë. Dy lojtarë kanë një koleksion domino të cilat i vendosin në rrjet me radhë, duke mbuluar katrorët. Një lojtar vendos pllakat vertikalisht, ndërsa tjetri i vendos ato horizontalisht. (Tradicionalisht, këta lojtarë quhen përkatësisht "Majtas" dhe "Djathtas", ose "V" dhe "H". Të dyja konventat përdoren në këtë artikull.) Si në shumicën e lojërave në teorinë e lojës kombinuese, lojtari i parë që nuk mund të lëvizë humbet.

Dominimi është një lojë partizane, në atë që lojtarët përdorin pjesë të ndryshme: versioni i paanshëm i lojës është Cram .

Shembuj bazë

Kuti e vetme

Përveç lojës boshe, ku nuk ka rrjet, loja më e thjeshtë është një kuti e vetme.

Në këtë lojë, është e qartë se asnjë lojtar nuk mund të lëvizë. Meqenëse është një fitore e lojtarit të dytë, kështu që kjo është një lojë zero.

Rreshtat horizontale

Kjo lojë është një rrjet 2-nga-1. Ekziston një konventë për t'i caktuar lojës një numër pozitiv kur fiton lojtari majtas dhe një numër negativ kur fiton lojtari djathtas. Në këtë rast, lojtari majtas nuk ka lëvizje, ndërsa lojtari djathtas mund të luajë një domino për të mbuluar të gjithë tabelën, duke mos lënë asgjë, gjë që është padyshim një lojë zero. Kështu, në shënimin e numrave surrealë, kjo lojë është {| 0} = -1. Kjo ka kuptim, pasi ky rrjet është një avantazh me 1 lëvizje për lojtarin Djathtas.

Kjo lojë është gjithashtu {| 0} = −1, sepse një kuti e vetme nuk mund të luhet.

Ky rrjet është rasti i parë i zgjedhjes. Lojtari djathtas mund të luajë dy kutitë majtas, duke lënë -1. Kutitë më të djathta gjithashtu lënë -1. Ai gjithashtu mund të luajë dy kutitë e mesme, duke lënë dy kuti të vetme. Ky opsion rezulton në 0+0 = 0. Kështu, kjo lojë mund të shprehet si {| 0,−1}. Kjo është -2. Nëse kjo lojë luhet së bashku me lojëra të tjera, kjo jep dy lëvizje falas për lojtarin Djathtas.

Rreshtat vertikale

Kolonat vertikale vlerësohen në të njëjtën mënyrë. Nëse ka një rresht me 2n ose 2n +1 kuti, ai llogaritet si −n. Një kolonë me madhësi të tillë llogaritet si +n.

Rrjete më komplekse

Kjo është një lojë më komplekse. Nëse lojtari majtas fillon, çdo lëvizje lë një rrjet 1×2, që është +1. Lojtari djathtas, nga ana tjetër, mund të shkojë në -1. Kështu, shënimi i numrave surreal është {1|−1}. Megjithatë, ky nuk është një numër surreal sepse 1 > -1. Kjo është një lojë, por jo një numër. Shënimi për këtë është ±1, dhe është një lojë e nxehtë, sepse çdo lojtar dëshiron të lëvizë këtu.

Ky është një rrjet 2×3, i cili është edhe më kompleks, por, ashtu si çdo lojë Dominuese, mund të zbërthehet duke parë se cilat janë lëvizjet e ndryshme për Majtas dhe Djathtas. Lojtari majtas mund të marrë kolonën e majtë (ose, në mënyrë ekuivalente, kolonën e djathtë) dhe të shkojë në ±1, por është qartësisht një ide më e mirë të ndahet në mes, duke lënë dy lojëra të veçanta, secila me vlerë +1. Kështu, lëvizja më e mirë e Majtas është +2. Lojtari djathtas ka katër lëvizje "të ndryshme", por të gjitha ato lënë formën e mëposhtme në disa rrotullime:

Kjo lojë nuk është një lojë e nxehtë (e quajtur edhe një lojë e ftohtë ), sepse çdo lëvizje dëmton lojtarin që e bën atë, siç mund ta shohim duke ekzaminuar lëvizjet. Majtas mund të lëvizë në -1, djathtas mund të lëvizë në 0 ose +1. Kështu kjo lojë është {−1|0,1} = {−1|0} = −¹⁄₂ .

Rrjeti ynë 2×3, pra, është {2|−¹⁄₂ }, e cila gjithashtu mund të përfaqësohet nga vlera mesatare,³⁄₄, së bashku me bonusin për lëvizje ("temperatura"),1+¹⁄₄, pra: $\textstyle \left\{2\left|-{\frac {1}{2}}\right.\right\}={\frac {3}{4}}\pm {\frac {5}{4}}$

Lojë e nivelit të lartë

Instituti i Kërkimeve të Shkencave Matematikore organizoi një turne të lojës Dominues, me një çmim prej 500 dollarësh për fituesin. Kjo lojë u zhvillua në një tabelë me dimensione 8×8. Fituesi i turneut ishte matematikani Dan Calistrate, i cili triumfoi në finale ndaj David Wolfe. Detajet e këtij turneu janë të përshkruara në librin "Lojërat e pa shans" të Richard J. Nowakowski (faqja 85).

Strategjia fituese

Përshkrim i pemës së lojës për një lojë Dominimi të luajtur mbi një tabelë 4x4, me lojtarin horizontal ("H") duke filluar dhe dy lëvizje të luajtura tashmë. Pema është krasitur me krasitje alfa-beta dhe janë përfshirë vlerat minimale që tregojnë se H ka një strategji fituese që nga rrënja.

Një problem rreth lojës Dominues është llogaritja e strategjisë fituese për dërrasat e mëdha, veçanërisht për dërrasat katrore. Në vitin 2000, Dennis Breuker, Jos Uiterwijk dhe Jaap van den Herik llogaritën dhe publikuan zgjidhjen për një tabelë 8x8. Bordi 9x9 u zgjidh menjëherë pas disa përmirësimeve të programit të tyre. Më pas, në vitin 2002, Nathan Bullock zgjidhi tabelën 10x10, si pjesë e tezës së tij mbi Dominuesin. Tabela 11x11 u zgjidh nga Jos Uiterwijk në 2016.

Dominimi është një fitore e lojtarit të parë për tabelat katrore 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 dhe 11x11, ndërsa është një fitore e lojtarit të dytë për tabelat 1x1 dhe 5x5. Disa vlera të tjera të njohura për dërrasat drejtkëndore mund të gjenden në faqen e Nathan Bullock.

Cram

Cram është versioni i paanshëm i Domineering. Dallimi i vetëm në rregulla është se çdo lojtar mund të vendosë domino në secilin orientim. Duket si një ndryshim i vogël në rregulla, por rezulton në një lojë krejtësisht të ndryshme që mund të analizohet me teoremën e Sprague-Grundy.

Referime

• Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters, Ltd. ISBN 978-1-56881-277-9.
• Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for Your Mathematical Plays. A K Peters, Ltd. ISBN 978-0-12-091150-9.
• Gardner, Martin (1974). "Mathematical Games: Cram, crosscram and quadraphage: new games having elusive winning strategies". Scientific American. 230 (2): 106–108. doi:10.1038/scientificamerican0374-102.

Linqe te jashtme

• Playable version at Pencil and Paper Games