2048 a slučovací hlavolamy
Mocniny dvou, strategie rohu, pravděpodobnost
a počítač, který hraje lépe než my
Na pozadí hraje počítač na desce 4 × 4. Každý tah vybírá prohledáváním o dva kroky dopředu (expectimax z kapitoly 9) a u každého napíše, kterou technikou z průvodce byl: Roh, Hadí řada, Sloučit hned, Volná pole, nebo Nouzový tah. Věže rostou po patrech – dvojka má jedno patro, 2048 jedenáct. Oranžově jsou věže, které právě vznikly sloučením, modře nová věž. Když postaví věž 4096, nebo když hra skončí, začne znovu.
Jak průvodce používat
Posuvné slučovací hlavolamy mají jednoduchá pravidla: tahem posunete všechny kameny na desce jedním směrem, dva stejné se spojí v jeden větší a po každém tahu přibude nový. Nejznámější z nich, hra 2048 z jara 2014, se za pár týdnů rozšířila po celém světě. Pod jednoduchostí se skrývá kus matematiky – mocniny dvou, pravděpodobnost, prohledávání stromu hry, strojové učení i teorie složitosti. Průvodce vede od pravidel a první věže 2048 přes strategii rohu a hadí řady, krizové pozice a pravděpodobnost až k tomu, jak hraje počítač a co o hře dokázali matematici. Je pro hráče, kteří chtějí dosáhnout 2048 spolehlivě, pro rodiče a děti, které si při tom procvičí násobení dvěma, i pro studenty matematiky a informatiky.
Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra na vlastní desce, kde si věc vyzkoušíte tahem prstu nebo šipkami. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, odvození, řešené příklady a procvičení s řešením. Teorie bývá o úroveň náročnější než úvod kapitoly. Barevná tečka v obsahu ukazuje úroveň. Postup se ukládá jen ve vašem prohlížeči.
Hned za úvodem najdete sekci Dvojkové věže ve 3D: vlastní hru stejného žánru, ve které místo plochých kamenů rostou věže ze skleněných pater. Má pět obtížností, denní výzvu, prostorovou krychli 3 × 3 × 3, třicet hlavolamů bez náhody a režim pro děti. Trenér v ní ukáže další tah a pojmenuje techniku s odkazem na kapitolu, kde se vykládá.
Mapa průvodce
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Pravidla, pojmy a historie | základy | deska, tah, sloučení od stěny a nejvýš jednou, nová věž, konec hry a cíl; Threes, 1024 a 2048 z jara 2014 |
| 2 Mocniny dvou a skóre | základy | 2048 = 2¹¹, dvojková soustava, kolik nových věží a tahů je potřeba, proč věž 2ⁿ z dvojek dá (n − 1) · 2ⁿ bodů |
| 3 Roh | základy | proč největší věž patří do rohu, dva hlavní směry, kdy třetí, proč se vyhnout čtvrtému; minihra Který tah? |
| 4 Hadí řada | základy | monotónní řada u stěny, had přes dvě řady, žebřík hodnot k rohu, jak řadu plnit |
| 5 Sloučit hned a volná pole | pokročilí | řetězová sloučení, prostor na desce, malé věže daleko od rohu, kolik polí potřebuje věž 2ⁿ |
| 6 Krize a nouzový tah | pokročilí | roh utekl, zablokovaná řada, který nouzový tah zvolit, jak se vrátit, kdy obětovat |
| 7 Dlouhá hra | pokročilí | 4096, 8192 a dál, největší možná věž 131 072, rytmus dlouhé hry, zdravé hraní |
| 8 Pravděpodobnost a riziko | pokročilí | kam padne nová věž, šance na čtyřku, očekávaná hodnota, riziko tahu, simulace strategií s nejistotou |
| 9 Počítač hraje I: expectimax | mistr a věda | strom hry, minimax a expectimax, heuristiky (volná pole, monotónnost, hladkost, roh), hloubka a ořezávání |
| 10 Počítač hraje II: učení z her | mistr a věda | zpětnovazební učení, metoda TD, n-tuple sítě, co dokázaly výzkumné týmy |
| 11 Matematika a složitost | mistr a věda | počet stavů, Markovův řetězec, přesný výpočet na malé desce, NP-úplnost, krychle 3 × 3 × 3 |
| 12 Hlavolamy a tvorba | mistr a věda | úlohy bez nových věží, prohledávání do šířky, generátor, zlomyslná nová věž, varianty žánru |
Co budete potřebovat
Nic než prst na displeji nebo šipky na klávesnici – všechny desky v průvodci jsou interaktivní. Pro první část stačí umět násobit dvěma a sčítat. Od kapitoly 8 se hodí pojem pravděpodobnosti a průměru, v kapitolách 9 až 11 trocha algoritmického myšlení; co je potřeba, průvodce vysvětlí na místě.
Navazující látku najdete v sousedních průvodcích: prohledávání stromu hry, minimax a hodnocení pozice u hry dvou soupeřů v průvodci Šachy, náhodné veličiny, očekávanou hodnotu, Monte Carlo a intervaly spolehlivosti v průvodci Statistika a modely, důkaz sporem a výrokovou logiku (základ úlohy 3SAT) v průvodci Logika a kritické myšlení, algoritmy, složitost a strojové učení obecně v průvodci Informatika, mocniny, dvojkovou soustavu a geometrické řady v průvodci Matematika. Příbuzné logické hry s počítačovým řešitelem rozebírají průvodci Sudoku a Hledání min.
Značení a předpoklady
Pole se značí ř3s2 = 3. řádek shora, 2. sloupec zleva. Deska se v textu zapisuje po řádcích shora, řádky odděluje lomítko a tečka je prázdné pole: . . . . / . 2 . . / 4 8 . . / 64 32 16 8. Tahy jsou šipky ← → ↑ ↓. Věž 2ⁿ má n pater; v laboratořích má každá věž vlevo proužek pater a barvu podle patra, číslo je uprostřed. Kde se mluví o rohu, je to roh vlevo dole: hlavní směry ↓ a ←, třetí směr →, čtvrtý ↑. Pro jiný roh stačí desku otočit nebo zrcadlit. Nové věže jsou, není-li řečeno jinak, dvojky s pravděpodobností 90 % a čtyřky s 10 % jako v původní hře.
| Technika | Kdy ji počítač ohlásí | Kapitola |
|---|---|---|
| Roh | běžný tah k rohu nebo podél jeho stěny, největší věž zůstane v rohu | 3 |
| Hadí řada | spodní řada je plná a od rohu klesá a tah ↓ nebo ← ji drží | 4 |
| Sloučit hned | tah slučuje a žádný jiný tah nesloučí víc | 5 |
| Volná pole | tah nechá nejvíc „prostoru“ – volných polí a sousedních dvojic stejných věží | 5 |
| Nouzový tah | ↓ ani ← nejdou, nebo tah vytáhne největší věž z rohu | 6 |
Čtyři druhy rámečků
Konkrétní pozice nebo výpočet, který si můžete ověřit v laboratoři.
Jak hry vznikly, kdo je napsal a co o nich zjistili výzkumníci.
Rychlé pravidlo nebo návyk, který používají zkušení hráči.
Častá chyba, mýtus nebo past, do které se snadno spadne.
Studijní materiál o hře. Hrajte pro radost a s mírou – bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje aplikace či obchody s aplikacemi; historické údaje a výsledky výzkumu mají v příloze C zdroj a datum ověření (9. 11. 2026). Pozice, tabulky, simulace a počty v textu jsou spočítané skriptem nad stejným kódem, jaký běží v laboratořích; u simulací je vždy uveden počet her.
Rozsahem odpovídá: matematika – mocniny a dvojková soustava, geometrické řady, kombinatorika a pravděpodobnost (doplněk jevu, očekávaná hodnota, Markovovy řetězce) na úrovni úvodních vysokoškolských kurzů; informatika – úvod do umělé inteligence a algoritmů prohledávání (strom hry, minimax, expectimax, prohledávání do šířky, dynamické programování), zpětnovazební učení metodou TD a základy teorie složitosti (NP-úplnost, převod z 3SAT); pravidla – původní hra 2048 podle jejího zveřejněného zdrojového kódu (příloha C).
Dvojkové věže ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
Vlastní hra stejného žánru jako 2048, ne její kopie. Na dřevěné desce na kamenném stole stojí věže ze skleněných pater: dvojka má jedno patro, čtyřka dvě a věž 2048 jedenáct. Každé patro má vlastní barvu od chladných po teplé a číslo je na vrcholu věže. Tahem posunete všechny věže jedním směrem; dvě stejné věže se srazí, jedna vyskočí na druhou, splynou a krátce zazáří. Po každém platném tahu vyroste z desky nová věž. Na výběr je Klasické (obtížnosti 1 až 5), Denní výzva (v daný den stejná řada nových věží pro všechny, deska 4 × 4, cíl 2048, bez kroku zpět), Krychle 3 × 3 × 3 (tři desky nad sebou a tahy v šesti směrech, cíl 1024; souvislosti v kapitole 11), Úlohy (30 hlavolamů bez nových věží: dosáhnout cílové věže v nejvýš N tazích, kde N je nejmenší počet ověřený prohledáváním do šířky jako v kapitole 12) a Pro děti (deska 4 × 4, cíl 128, nové věže jen dvojky, neomezený krok zpět a velké popisky). Nápověda trenéra pojmenuje techniky z průvodce: Roh, Hadí řada, Sloučit hned a Volná pole a Nouzový tah. Ovládání v kostce: přejetí prstem, šipky nebo W A S D, u krychle tlačítka ⤒/⤓ nebo klávesy Q a E (nahoru a dolů), Z krok zpět, T nápověda a F celá obrazovka. V nastavení zvolíte popisky čísla (2048), mocniny (2¹¹), nebo patra (11) a Pohled 3D / 2D shora.
Pravidla, pojmy a historiezáklady
Hraje se na desce 4 × 4 polí. Na některých polích stojí věže s hodnotami 2, 4, 8, 16 … – samé mocniny dvou. Tahem posunete všechny věže najednou jedním ze čtyř směrů až ke stěně. Dvě stejné věže, které se při tom potkají, se sloučí v jednu o patro vyšší: 2 a 2 dají 4, 4 a 4 dají 8. Po každém platném tahu vyroste na náhodném volném poli nová věž, dvojka nebo vzácněji čtyřka. Hodnota každé sloučené věže se přičte ke skóre. Cílem je postavit věž 2048; hra končí, když žádný tah nic nezmění.
Představte si kufry na pásu letištního dopravníku, který se rozjede ke zdi. Kufry se namačkají ke stěně a dva stejné, které do sebe narazí, se „spojí“ v jeden větší. Ten nový ale už v tomtéž rozjezdu s ničím nesplyne – musí počkat na další. Právě tohle pravidlo, slučování od stěny a nejvýš jednou za tah, dělá z jednoduché hry hlavolam.
+Teorie: tah krok za krokem, nová věž, konec hry, historie od Threes po 2048
1.1Deska, věž a tah
Deska má 16 polí. Věž s hodnotou 2ⁿ má v průvodci n pater: dvojka jedno, čtyřka dvě, 2048 jedenáct. Tah ← posune každou řadu zvlášť k levé stěně, tah → k pravé, ↑ a ↓ posouvají sloupce. Řady se navzájem neovlivňují – tah na desce 4 × 4 jsou vlastně čtyři nezávislé tahy čtyř řad.board, tile, move, swipe
Tah je platný, když se po něm aspoň jedna věž pohne nebo sloučí. Neplatný tah se nepočítá a nová věž po něm nepadá. V simulacích průvodce bylo v průměrné pozici platných 3,5 až 3,6 tahu ze čtyř, podle toho, jak dobře se hrálo.
1.2Sloučení: od stěny a nejvýš jednou
Posun jedné řady ke stěně jde popsat třemi kroky. (1) Věže se přisunou ke stěně, mezery zmizí. (2) Od stěny se procházejí sousední dvojice: jsou-li dvě věže stejné, sloučí se v jednu o patro vyšší a obě z dalšího porovnávání vypadnou. (3) Výsledek se znovu přisune ke stěně. Ke skóre se přičte hodnota každé nově vzniklé věže.merge, slide
| Před tahem | Po tahu ← | Body | Proč |
|---|---|---|---|
| 2 2 2 2 | 4 4 . . | 8 | dvě dvojice, každá věž nejvýš jednou |
| 2 2 4 . | 4 4 . . | 4 | nová čtyřka se se starou nespojí |
| 4 4 4 . | 8 4 . . | 8 | slučuje se dvojice u stěny, třetí čtyřka zůstane |
| 2 . 2 4 | 4 4 . . | 4 | mezera nevadí, nejdřív se přisune |
| 8 8 16 16 | 16 32 . . | 48 | dvě různé dvojice v jednom tahu |
| 2 2 4 4 | 4 8 . . | 12 | ne 16: sloučení se neřetězí |
| . 2 2 2 | 4 2 . . | 4 | u stěny jsou první dvě dvojky |
Nejčastější omyl začátečníků je „řetězové“ slučování: [2 2 4 .] ← nedá 8, ale [4 4 . .]. Druhý omyl je slučování od nesprávné stěny: [4 4 4 .] ← dá [8 4 . .], ne [4 8 . .]. Minihra výše obě chyby nabízí jako špatné možnosti.
1.3Nová věž, začátek, konec a cíl
Po každém platném tahu vyroste na náhodně zvoleném volném poli (každé volné pole se stejnou pravděpodobností) nová věž: dvojka s pravděpodobností 90 %, čtyřka s 10 %. Tak to dělá zveřejněný zdrojový kód původní hry (příloha C). Hra začíná dvěma novými věžemi na prázdné desce. Různých začátků je 120 dvojic polí × 4 kombinace hodnot = 480 a aspoň jednu čtyřku obsahuje 1 − 0,9² = 19 % z nich.spawn, start position
Konec hry nastane, když žádný ze čtyř tahů nic nezmění: deska je plná a žádné dvě sousední věže (vodorovně ani svisle) nejsou stejné. Cílem je věž 2048 = 2¹¹. Původní hra po ní nabídne pokračovat a ve 3D hře průvodce se po ohňostroji také hraje dál.
Deska 2 4 2 4 / 4 2 4 2 / 2 4 2 4 / 4 2 4 8 je plná a žádné dvě sousední věže nejsou stejné – to je konec hry. Kdyby ve spodní řadě místo 8 stála 4, tah ← by spojil poslední dvě čtyřky a hra by pokračovala.
1.4Historie: od Threes k 2048
Žánr odstartovala hra Threes, která vyšla 6. února 2014. Navrhl ji Asher Vollmer, grafiku nakreslil Greg Wohlwend a hudbu složil Jimmy Hinson. Slučovala se v ní 1 a 2 ve 3 a dál stejné násobky tří; kameny se posouvaly jen o jedno pole. Během několika týdnů vznikly napodobeniny, mezi nimi hra 1024. Hru, kterou dnes zná každý, 2048, napsal italský webový vývojář Gabriele Cirulli, tehdy devatenáctiletý. Zveřejnil ji 9. března 2014, napsal ji v JavaScriptu a CSS za jeden víkend a uvolnil s otevřeným zdrojovým kódem pod licencí MIT. V popisu projektu sám uvádí, že jde o klon hry 1024 založený na dřívějším 2048 jiného autora a „nepřímo inspirovaný“ hrou Threes.
Otevřený kód měl velký vliv: brzy vznikla řada upravených verzí – větší a menší desky, tematické obrázky místo čísel i prostorová verze. Autor podle citace v článku Szuberta a Jaśkowského (2014) uvedl, že za první tři týdny hráči ve hře strávili dohromady přes 3 000 let a že z mnoha set milionů odehraných her skončilo vítězstvím jen zhruba 1 %. Tato dvě čísla známe jen z této citace, ne z vlastního zdroje autora.
Když nevíte, co tah udělá s řadou, čtěte ji od stěny, ke které táhnete: první dvě věže, jsou-li stejné, splynou; pak se pokračuje od třetí. Kdo si to v hlavě zautomatizuje, přestane být překvapený tahem, který „sloučil jinak“.
1.5Varianty v kostce
Stejný princip „posuň a slouč“ snese mnoho obměn: desky 3 × 3, 5 × 5 nebo obdélníkové, prostorová krychle, Fibonacciho čísla místo mocnin dvou, trojky jako v Threes, úlohy bez nových věží i soupeř, který nové věže pokládá schválně tam, kde škodí. Některé z nich najdete ve 3D hře průvodce a podrobněji v kapitole 12.
1.6Procvičení
- Tah posune všechny věže ke stěně; slučuje se od stěny a každá věž nejvýš jednou za tah.
- Po platném tahu vyroste nová věž: 2 s pravděpodobností 90 %, 4 s 10 %. Konec hry je, když žádný tah nic nezmění.
- 2048 zveřejnil Gabriele Cirulli 9. 3. 2014 jako otevřený kód (MIT); navázal na 1024 a nepřímo na Threes z února 2014.
Mocniny dvou a skórezáklady
Každé sloučení zdvojnásobí hodnotu věže a přidá jí jedno patro. Na desce proto stojí jen mocniny dvou: 2 = 2¹, 4 = 2², 8 = 2³ … a 2048 = 2¹¹. Z toho plyne překvapivě mnoho: kolik dvojek je ve věži 2048 (1 024), kolik nových věží je potřeba (zhruba 931), kolik tahů nejméně (510) a kolik bodů skóre stavba věže přinese (20 480, jsou-li všechny nové věže dvojky). Kapitola tato čísla odvodí a kalkulačka je spočítá pro libovolné patro.
Stará pověst o vynálezci šachu prý žádala za odměnu jedno zrnko na první pole šachovnice, dvě na druhé, čtyři na třetí a tak dál. Zdvojování roste nečekaně rychle. Věž 2048 je teprve jedenácté pole takové šachovnice – a přesto se na ni v průměru čeká skoro tisíc tahů.
+Teorie: patra a dvojková soustava, součet desky, odvození skóre, identita pro celou hru
2.1Patra a mocniny
Věž 2ⁿ vznikne sloučením dvou věží 2ⁿ⁻¹, ty ze čtyř věží 2ⁿ⁻² a tak dál až ke dvojkám. Ve věži 2ⁿ je tedy „schováno“ 2ⁿ⁻¹ dvojek a patro n říká, kolikrát se zdvojovalo. Proto ve 3D hře průvodce roste věž po patrech a v nastavení si můžete přepnout popisky na čísla, mocniny nebo patra (obr. 2.1).power of two, exponent
| Patro n | Věž 2ⁿ | Ve dvojkové soustavě | Dvojek ve věži | Skóre jen z dvojek | Nových věží (p = 0,1) |
|---|---|---|---|---|---|
| 3 | 8 | 1000 | 4 | 16 | 3,6 |
| 5 | 32 | 100000 | 16 | 128 | 14,5 |
| 7 | 128 | 10000000 | 64 | 768 | 58,2 |
| 8 | 256 | 100000000 | 128 | 1 792 | 116,4 |
| 9 | 512 | 1000000000 | 256 | 4 096 | 232,7 |
| 10 | 1 024 | 10000000000 | 512 | 9 216 | 465,5 |
| 11 | 2 048 | 100000000000 | 1 024 | 20 480 | 930,9 |
| 12 | 4 096 | 1000000000000 | 2 048 | 45 056 | 1 861,8 |
| 13 | 8 192 | 10000000000000 | 4 096 | 98 304 | 3 723,6 |
| 17 | 131 072 | 100000000000000000 | 65 536 | 2 097 152 | 59 578,2 |
2.2Součet desky roste jen novými věžemi
Sloučení součet desky nemění: 2ⁿ + 2ⁿ = 2ⁿ⁺¹. Součet tedy roste jen novými věžemi, o 2 nebo 4 za každý platný tah. Průměrná nová věž má hodnotu 0,9 · 2 + 0,1 · 4 = 2,2. Aby na desce mohla stát věž 2048, musí součet dorůst aspoň na 2 048; to chce zhruba 2 048 / 2,2 ≈ 931 nových věží, tedy asi 929 tahů po dvou startovních věžích.board sum
Ve skutečnosti trvá cesta k 2048 o něco déle, protože na desce stojí i další věže. Ve 100 hrách počítače (expectimax s hloubkou 3, kapitola 9) vznikla první věž 2048 průměrně v 997. tahu a součet desky byl v tu chvíli průměrně 2 198 (nejméně 2 080, nejvíc 2 768). Nejmenší možný počet tahů je 510: kdyby hra začala dvěma čtyřkami a padaly jen čtyřky, součet by rostl o 4 a 8 + 4 · 510 = 2 048.
2.3Kolik bodů dá věž postavená z dvojek
Označme S(n) skóre za stavbu věže 2ⁿ, když jsou všechny nové věže dvojky. Dvojka nové věže body nedává, takže S(1) = 0. Věž 2ⁿ⁺¹ vznikne ze dvou věží 2ⁿ (každá za S(n) bodů) a poslední sloučení přidá 2ⁿ⁺¹:score derivation
Ověření dosazením: 2 · (n − 1) · 2ⁿ + 2ⁿ⁺¹ = n · 2ⁿ⁺¹ = ((n + 1) − 1) · 2ⁿ⁺¹. Názorně: každá dvojka ve věži prošla n − 1 sloučeními a v každém z nich „zaplatila“ svůj podíl. Pro 2048 je to 10 · 2 048 = 20 480 bodů.
2.4Čtyřky skóre snižují
Nová čtyřka nahradí sloučení dvou dvojek, za které by bylo 4 body. Každá čtyřka, která do hry spadla, tedy ubere právě 4 body. Pro celou hru platí přesná identita skóre, kde se sčítá přes všechny věže na desce a F je počet nových čtyřek (včetně startovních):score identity
Identitu jsme ověřili na všech 27 600 hrách simulací průvodce (náhodné tahy, pevné pořadí, chamtivá heuristika a expectimax s hloubkou 1, 2 a 3) – sedí přesně v každé hře. Při podílu čtyřek p je mezi novými věžemi průměrně podíl p čtyřek a jejich počet při stavbě věže 2ⁿ je asi p · 2ⁿ / (2 + 2p). Očekávané skóre za věž 2ⁿ tedy je
Na konci hry stojí na desce mimo jiné 2048, 1024 a 512 a během hry padlo 120 čtyřek. Jen tyto tři věže znamenají 10 · 2 048 + 9 · 1 024 + 8 · 512 = 20 480 + 9 216 + 4 096 = 33 792 bodů; menší věže přidají další a čtyřky uberou 4 · 120 = 480. Skóre tedy zhruba prozradí, jak velké věže hráč postavil, a nic víc – žádné body „za styl“ hra nedává.
Vyšší skóre při stejné nejvyšší věži neznamená lepší hru v tom smyslu, že by hráč „víc slučoval“. Body jsou dané věžemi na desce. Hráč, kterému padlo méně čtyřek, má o něco víc bodů za stejnou desku – rozdíl je ale nejvýš pár set bodů.
Pamatujte si 2¹⁰ = 1 024 ≈ tisíc. Pak 2¹¹ ≈ 2 tisíce, 2¹⁴ ≈ 16 tisíc, 2¹⁷ ≈ 131 tisíc. A skóre za věž je „patro minus jedna krát věž“: za 4096 to je 11 · 4 096 = 45 056.
2.5Procvičení
- Věže jsou mocniny dvou: 2048 = 2¹¹ má 11 pater a „obsahuje“ 1 024 dvojek.
- Součet desky roste jen novými věžemi, průměrně o 2,2 za tah: k první 2048 vede zhruba tisíc tahů, nejméně 510.
- Věž 2ⁿ z dvojek dá (n − 1) · 2ⁿ bodů, každá nová čtyřka ubere 4 body.
Rohzáklady
První a nejdůležitější technika: největší věž držte stále v jednom rohu. Hrajte hlavně dvěma směry, které tlačí k rohu – pro roh vlevo dole ↓ a ←. Třetí směr (→) jen tehdy, když se spodní řada nepohne, a čtvrtému (↑) se vyhýbejte, dokud to jde. Velká věž v rohu nepřekáží, menší věže k ní „stékají“ a slučují se po cestě. Simulace ukazuje sílu té jediné myšlenky: počítač, který jen zkouší směry v pevném pořadí ↓ ← → ↑, má průměrně 2,3krát vyšší skóre než náhodné tahy.
Ve stěhovacím autě patří nejtěžší skříň do rohu u kabiny, ne doprostřed. Kolem ní se pak dají skládat menší kusy a nic se nepřesouvá. Skříň uprostřed by překážela v každé uličce. S největší věží na desce je to stejné: v rohu sousedí jen se dvěma poli, uprostřed se čtyřmi.
+Teorie: proč roh, hlavní, třetí a čtvrtý směr, typické omyly, simulace
3.1Proč právě roh
Velká věž se sloučí jen s jinou stejně velkou a ta vzniká dlouho. Celou tu dobu věž zabírá pole a dělí řadu i sloupec, ve kterých stojí. Uprostřed desky má čtyři sousedy, kteří se s ní nesloučí, a rozdělí dvě řady na kratší kusy. U stěny má sousedy tři, v rohu jen dva a obě její linie zůstanou souvislé. Navíc v rohu stojí věž „na konci“ řady i sloupce, takže ji tahy k rohu nikdy nepohnou.corner strategy
3.2Hlavní, třetí a čtvrtý směr
Pro roh vlevo dole jsou hlavní směry ↓ a ←. Věž v rohu stojí u spodní i u levé stěny, takže ji žádný z nich nepohne. Třetí směr → je bezpečný jen tehdy, když je spodní řada plná a nic se v ní nesloučí – pak se nepohne a roh zůstane obsazený. Čtvrtý směr ↑ je nejhorší: pokud levý sloupec není plný, odvede největší věž z rohu a na uvolněné místo může padnout dvojka.
Jak často se jednotlivé směry hrají, ukazuje simulace pevného pořadí ↓ ← → ↑ (10 000 her): ↓ v 70,3 % tahů, ← v 25,0 %, → ve 4,6 % a ↑ jen v 0,1 % – tedy jen když nic jiného nešlo.
Tah → je bezpečný jen při plné spodní řadě bez stejných sousedů. Řada 128, 32, 16, 16 je sice plná, ale tah → v ní sloučí šestnáctky od pravé stěny a vznikne [. 128 32 32] – největší věž opustí roh. V takové pozici je správný tah ←, který šestnáctky sloučí směrem k rohu.
3.3Typické omyly
- Honba za sloučením kdekoli. Tah, který sloučí dvě dvojky na druhé straně desky, ale vytáhne velkou věž z rohu, se nevyplatí.
- Kroužení všemi směry. Střídání ← ↑ → ↓ dokola je skoro totéž co náhodné tahy – a ty drží největší věž v rohu jen v 11 % tahů.
- Díra ve spodní řadě. Když spodní řada není plná, tah → ji posune. Kdo ji zaplní, má třetí směr k dispozici bez rizika.
- Přepnutí rohu. Když velká věž utekla, hráč často „začne znovu v jiném rohu“. Bývá lepší vrátit ji co nejdřív zpět (kapitola 6).
3.4Co říká simulace
| Strategie | Her | Průměrné skóre | Tahů | Věž ≥ 256 | Věž ≥ 512 | Největší věž v rohu |
|---|---|---|---|---|---|---|
| náhodné tahy | 10 000 | 1 099 ± 11 | 119 | 8,0 % | 0,02 % | 11,1 % tahů |
| pevné pořadí ↓ ← → ↑ | 10 000 | 2 542 ± 24 | 225 | 51,2 % | 4,4 % | 76,7 % tahů |
| chamtivě podle heuristiky (1 tah) | 5 000 | 4 651 ± 56 | 359 | 89,1 % | 31,9 % | 98,5 % tahů |
| expectimax, hloubka 2 | 500 | 32 741 ± 1 609 | 1 657 | 99,8 % | 97,4 % | 98,7 % tahů |
Deska . . . . / . . . . / 2 . . . / 256 64 16 8: dvojka stojí v ř3s1 přímo nad 256. Tah ↓ ji nepohne (pod ní je věž) a ← také ne (je u levé stěny); spodní řada se nepohne ani jedním. Hlavní směry tedy nejdou. Tah → posune jen dvojku doprava – spodní řada je plná a bez stejných sousedů, takže stojí. Tah ↑ by posunul celý levý sloupec a 256 by opustila roh. Správně je →. Kdyby dvojka stála v ř3s2, šel by ← a hrálo by se jím.
Než táhnete jiným směrem než dvěma hlavními, zeptejte se: „Pohne se spodní řada?“ Pokud ne, → je bezpečný. Pokud ano, hledejte jiný tah – i za cenu, že teď nic nesloučíte.
3.5Procvičení
- Největší věž patří do jednoho rohu; hraje se hlavně dvěma směry k němu.
- Třetí směr jen při plné spodní řadě bez stejných sousedů, čtvrtý jen z nouze.
- Samotné pevné pořadí ↓ ← → ↑ zvýší průměrné skóre z 1 099 na 2 542 (10 000 her).
Hadí řadazáklady
Roh říká, kde stojí největší věž. Hadí řada říká, kde stojí ty ostatní: od rohu podél stěny klesají, a když řada skončí, pokračují o patro výš opačným směrem – jako had, který se vine po desce. Hodnota tak vždy „teče“ k rohu: každá věž sousedí s o něco menší, se kterou se brzy sloučí, a vzniklá věž dorůstá do sousedky směrem k rohu. Ideálem je žebřík, kde věže klesají přesně o jedno patro: 1024, 512, 256, … Jediná dvojka na konci pak spustí řetěz sloučení až k rohu.
Myslete na frontu u pokladny, která se v sále vine tam a zpátky mezi páskami. Nejdál vpředu stojí ten, kdo čeká nejdéle, a každý další je o kousek „mladší“. Nikdo nepředbíhá a nikdo nestojí stranou. Když fronta postoupí, celá se posune o jedno místo a pořadí se nezmění.
+Teorie: monotónní řada, had přes dvě řady, žebřík, jak řadu plnit
4.1Monotónní řada u stěny
Řada je monotónní, když věže od rohu jen klesají (nebo jsou stejné). V monotónní spodní řadě [256 64 16 8] má každá věž za sousedku menší věž ve směru od rohu. Až z menší věže dorůstáním vznikne stejně velká, sloučí se tahem ← s větší sousedkou a nová věž zase dorůstá do další. Nemonotónní řada [256 8 64 16] má osmičku „uvězněnou“ mezi dvěma většími věžemi: aby se sloučila, musí z ní vyrůst 64 přímo na místě, a to trvá dlouho a blokuje řadu.monotonic row
4.2Had přes dvě řady
Když je spodní řada plná, nejmenší věž v ní stojí u pravé stěny (ř4s4). Další, ještě menší věž hada proto patří nad ni, do ř3s4, a třetí řada pokračuje doleva. Tah ↓ pak sloučí věž z ř3s4 do ř4s4, jakmile jsou stejné, a uvolněné místo se zaplní posunem třetí řady. Pořadí polí je jako stopa pluhu na poli – tam a zpátky.snake pattern, boustrophedon
4.3Žebřík
Had, ve kterém věže klesají přesně o jedno patro, se nazývá žebřík. Žebřík 1024, 512, …, 4, 2 zabírá 10 polí a jeho součet je 2¹¹ − 2 = 2 046 (geometrická řada). Jakmile se na konec hada přisune další dvojka, vznikne řetěz: 2 + 2 = 4, 4 + 4 = 8, … až 1024 + 1024 = 2048. Každé sloučení ale potřebuje vlastní tah, protože nová věž se v tahu už neslučuje (kapitola 1). V předvolbě „Žebřík a dvojka navíc“ najde prohledávání do šířky cestu k 2048 za 10 tahů a projde přitom 351 různých pozic.
Délka hada není všechno. Had z obr. 4.2 je krátký kvůli jediné malé věži na nesprávném místě. Nejhorší je „uvězněná“ dvojka nebo čtyřka mezi velkými věžemi v hadovi: nedá se sloučit tahem ↓ ani ←, a dokud tam je, had za ní neroste. Dlouhodobě je lepší takovou věž co nejdřív „vyrůst“ – ostatní tahy směřovat tak, aby k ní dorostla stejně velká.
4.4Jak řadu plnit
- Spodní řadu držte plnou. Plná a monotónní spodní řada se při tahu → nepohne, takže máte třetí směr bez rizika (kapitola 3).
- Nové věže chytejte daleko od rohu. Dokud jsou volná pole hlavně vpravo nahoře, padají malé věže tam, kde nepřekážejí.
- Doplňujte konec hada. Nejmenší věž hada je jeho „ocas“; slučujte k ní věže stejné velikosti a had se zkrátí zezadu – celý řetěz se posune k rohu.
- Druhá řada dorůstá k první. Věž v ř3s4 by měla být stejná nebo o patro menší než věž pod ní v ř4s4.
Předvolba „Žebřík“ má hada délky 10 a žebřík: 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2. Předvolba „Žebřík a dvojka navíc“ má hada délky 11 (dvě dvojky na konci, tedy už ne čistý žebřík) a cestu k 2048 za 10 tahů. „Zlomený had“ má délku 5, láme se na věži 32 v ř3s3. „Rozházená deska“ má hada délky 1: hned vedle 32 v rohu stojí větší 128.
Než táhnete, přejeďte očima hada od rohu: kde se láme? Tah, který zlom opraví nebo aspoň nezhorší, je téměř vždy lepší než tah, který něco sloučí jinde. Trenér ve 3D hře takový tah ohlásí jako Hadí řada.
4.5Procvičení
- Věže od rohu klesají podél stěny a pokračují hadem o řadu výš opačným směrem.
- Žebřík klesá přesně o patro; jedna dvojka na konci spustí řetěz – ale každé sloučení je samostatný tah.
- Malá věž uvězněná mezi velkými láme hada; spodní řadu držte plnou a monotónní.
Sloučit hned a volná polepokročilí
Dvě techniky pro chvíle, kdy je hlavních tahů víc a roh je v bezpečí. Sloučit hned: zvolte tah, který slučuje, když uvolní pole nebo připraví řetěz sloučení k rohu – nové pole je nový tah do zásoby. Volná pole: zvolte tah, který nechá desce nejvíc prostoru – volných polí a dvojic stejných sousedů, které půjde sloučit příště. Obojí míří k tomu samému: deska nesmí zahltit malými věžemi, protože každá věž zabírá pole a bez volných polí hra končí.
Když skládáte prádlo do skříně, vyplatí se nejdřív spárovat ponožky – z každého páru je jeden kus místo dvou a na polici zbude místo. Ale nejlepší tah není vždycky ten, který spáruje nejvíc ponožek najednou: někdy je lepší skládat tak, aby se příště párovalo snadno.
+Teorie: proč slučovat, řetěz k rohu, prostor, malé věže, kolik polí potřebuje věž 2ⁿ
5.1Každé sloučení je pole navíc
Tah bez sloučení počet věží nezmění a nová věž ho zvýší o jednu. Tah s m sloučeními sníží počet věží o m a nová věž přidá jednu. Volných polí tedy po tahu a nové věži přibude m − 1. Hra, ve které se v průměru slučuje méně než jednou za tah, se nevyhnutelně zaplní. Proto se vyplatí slučovat hned, když to jde a když tah zároveň drží roh.merge now
5.2Řetěz sloučení k rohu
Nejcennější sloučení je to, po kterém může následovat další – vzniklá věž je stejná jako její sousedka blíž k rohu. V předvolbě „Řetěz“ stojí ve spodní řadě 128, 64, 32, 16 a nad šestnáctkou další 16. Tah ↓ sloučí šestnáctky a vznikne 32 vedle 32; tři tahy ← pak postaví 64, 128 a nakonec 256 v rohu.merge chain, cascade
V předvolbě „Dvě sloučení“ (deska . . . . / 4 2 2 . / 8 8 4 . / 256 32 8 4) sloučí tah ← i tah → po dvou dvojicích (2 + 2 a 8 + 8) a oba dají 20 bodů. Tah ← ale věže posune k levé stěně, kde je roh, a nechá vlevo dole 256; tah → je přesune doprava. Počítač dává ← hodnocení 100 a → nižší – a trenér oba ohlásí jako Sloučit hned. Technika říká, že se slučuje; kam se slučuje, rozhoduje roh.
5.3Prostor místo počtu sloučení
Volné pole je jasná zásoba. Dvojice stejných sousedních věží je zásoba skrytá: příští tah z ní udělá volné pole. Průvodce proto měří prostor jako součet obojího. V předvolbě „Volná pole“ sloučí tah ↓ dvě dvojice a tah ← jen jednu, ale po ← zůstane prostor 10, po ↓ jen 8. Expectimax volí ← (obr. 5.2).space, mobility
Kdo hraje dobře, nemá v průměru víc volných polí – má jich méně, protože hraje déle a na desce stojí větší věže. V simulacích bylo průměrně 4,80 volného pole při náhodných tazích, 4,22 při pevném pořadí, 3,23 u expectimaxu s hloubkou 2 a 2,82 s hloubkou 3. Rozhoduje, aby volná pole nedošla v kritické chvíli, ne jejich průměrný počet.
5.4Malé věže daleko od rohu
Nová věž padá jen na volná pole. Když jsou volná pole daleko od rohu (vpravo nahoře), dvojky a čtyřky vznikají tam, kde nepřekážejí, a dorůstají postupně k hadovi. Když se volné pole otevře uprostřed hada, dvojka do něj spadne a had se zlomí (kapitola 4). Dobrý tah tedy nejen vytváří volná pole, ale vytváří je na správném místě.
5.5Kolik polí potřebuje věž 2ⁿ
Těsně před posledním řetězem musí na desce stát věže 2ⁿ⁻¹, 2ⁿ⁻², …, 4, 2 a ještě jedna 2 – dohromady n věží a n − 1 různých pater. Se šťastnou čtyřkou na konci místo dvou dvojek stačí n − 1 polí. Pro 2048 to je 11 polí a na desce 4 × 4 zbude 5; pro 65 536 = 2¹⁶ je potřeba všech 16 polí a pro 131 072 = 2¹⁷ všech 16 a čtyřka (kapitola 7).
| Věž | Polí (jen dvojky) | Se šťastnou čtyřkou | Volných polí navíc |
|---|---|---|---|
| 2 048 | 11 | 10 | 5 |
| 4 096 | 12 | 11 | 4 |
| 8 192 | 13 | 12 | 3 |
| 16 384 | 14 | 13 | 2 |
| 32 768 | 15 | 14 | 1 |
| 65 536 | 16 | 15 | 0 |
Spočítejte si „rozpočet polí“: kolik různých pater stojí na desce mimo hada? Každé takové patro je věž, která se zatím nemá s čím sloučit. Když jich je víc než volných polí, je čas přestat stavět a začít uklízet – slučovat malé věže, i když to roh na chvíli zkomplikuje.
5.6Procvičení
- Každé sloučení je pole navíc; bez sloučení se deska plní o jedno pole za tah.
- Nejcennější je sloučení, které připraví řetěz k rohu. Víc sloučení najednou není vždy lepší – počítejte prostor.
- Věž 2ⁿ potřebuje v kritické chvíli n polí; pro 2048 na desce 4 × 4 zbude rozpočet pěti polí.
Krize a nouzový tahpokročilí
I dobrá hra se dostane do úzkých: ↓ ani ← nejdou, největší věž opustila roh nebo se had zasekl o malou věž. Pak přichází nouzový tah – tah od rohu, když nic jiného nejde. Kapitola ukáže, jak mezi nouzovými tahy vybrat ten méně škodlivý (rozhoduje hlavně, co se stane se spodní řadou), jak se z nouzového tahu co nejrychleji vrátit a kdy je lepší roh obětovat a začít stavět znovu. Laboratoř to měří simulací: z každého tahu nechá dohrát 300 her o 25 tahů dál.
Na dálnici je uzavírka a navigace hlásí objížďku. Jsou dvě: jedna vede po okresce kousek vedle dálnice a za vesnicí se na ni vrací, druhá míří úplně jinam. Dobrý řidič volí tu, po které se vrátí nejdřív. Nouzový tah je objížďka: nevyhneme se mu, ale můžeme zvolit ten, po kterém se roh dá rychle obnovit.
+Teorie: tři druhy krize, výběr nouzového tahu, návrat, kdy obětovat
6.1Tři druhy krize
- Zablokované hlavní směry. Věže stojí u levé stěny a na sobě tak, že ↓ ani ← nic nepohnou. Zbývají → a ↑. Ze 19 krizových pozic minihry je takových 12.
- Roh utekl. Největší věž je mimo roh, obvykle po vynuceném ↑ nebo po neopatrném →. Na její místo může padnout dvojka.
- Zaseknutý had. Malá věž uvězněná mezi velkými, nebo spodní řada s dírou, do které padají dvojky (kapitola 4).
Podle definice průvodce je tah nouzový, když hlavní směry nejdou, nebo když tah vytáhne největší věž z rohu. Ostatní tahy jsou Roh, Hadí řada, Sloučit hned nebo Volná pole.emergency move
6.2Který nouzový tah
Když nejde ↓ ani ←, zbývá → (podél spodní stěny) a ↑ (od ní). Rozhoduje, co tah udělá se spodní řadou a s levým sloupcem. Tah → nepohne plnou spodní řadou bez stejných sousedů, ale posune všechno nad ní doprava. Tah ↑ nepohne plným levým sloupcem, ale každou věž spodní řady, nad kterou je volno, vytáhne nahoru – a pod ní zůstane díra.
| Pozice | Tah | Hra běží | Největší věž vlevo dole | Body za 25 tahů |
|---|---|---|---|---|
| Ucpaná deska A | → | 96,3 % | 100 % | 212 |
| ↑ | 99,7 % | 100 % | 215 | |
| Ucpaná deska B | → | 95,0 % | 100 % | 192 |
| ↑ | 60,7 % | 99,7 % | 190 | |
| Skoro plná deska | → | 86,3 % | 100 % | 409 |
| ↑ | 98,0 % | 96,0 % | 1 191 |
Je spodní řada plná a bez stejných sousedů? Pak je → bezpečný pro spodní řadu – zkontrolujte jen, co posune nad ní. Je levý sloupec plný? Pak ↑ nepohne rohem – zkontrolujte, kolik věží vytáhne ze spodní řady. Vyberte tah, který poškodí méně: na desce B ↑ vytáhne tři věže ze spodní řady, → žádnou.
6.3Návrat do rohu
Po nouzovém tahu hned hrajte hlavními směry, aby se věže vrátily. Po ↑ obvykle stačí ↓: co vyjelo nahoru, sjede zpět – pokud mezitím nová věž nepadla do díry pod ním. Pravděpodobnost, že padne do konkrétního pole, je 1 / (počet volných polí); při pěti volných polích 20 %. Proto je ↑ tím horší, čím víc děr ve spodní řadě po sobě nechá.
Když po nouzovém tahu padne dvojka přímo do rohu, nespěchejte s dalším nouzovým tahem. Často je lepší dvojku „vyrůst“: slučovat k ní malé věže, dokud nebude stejná jako sousedka, nebo ji zapracovat do spodní řady. Velkou věž tahat sem a tam přes celou desku vede k dalším dírám.
6.4Kdy zachraňovat a kdy obětovat
Zachraňovat se vyplatí, dokud je největší věž u stěny se starým rohem a návrat stojí jeden dva tahy. Když se roh zablokoval malými věžemi a velká věž stojí v jiném rohu, bývá lepší přijmout nový roh a stavět hada odtud – stará spodní řada se pak stane bočním sloupcem. A když je deska plná malých věží a největší věž je uprostřed, bývá rozumné rezignovat na pořádek a několik tahů jen slučovat, kde to jde, než vznikne prostor pro nový roh. Průvodce pro tato rozhodnutí nemá jednoduché číslo; pomůže laboratoř: když dva tahy dají podobné procento „hra běží“, rozhoduje to, který nechá velkou věž blíž rohu.
Krizi předcházejte: když vidíte, že po příštím tahu nepůjde ↓ ani ←, hledejte už teď tah, který nechá jeden z hlavních směrů volný – třeba ← s jediným sloučením místo ↓ se dvěma. Nouzový tah, kterému jste se vyhnuli, je nejlepší nouzový tah.
6.5Procvičení
- Nouzový tah je nevyhnutelný, když ↓ ani ← nejdou; vybírejte ten, který nechá spodní řadu a roh v pořádku.
- Tah ↑ vytáhne ze spodní řady každou věž, nad kterou je volno – a do děr padají dvojky.
- Po nouzovém tahu se vracejte hlavními směry; když je roh ztracený, přijměte nový a stavějte znovu.
Dlouhá hrapokročilí
Věží 2048 hra nekončí. Kdo pokračuje, staví 4096, 8192 a dál – a s každým patrem se hra prodlužuje na dvojnásobek a zbývá o pole méně. Kapitola spočítá, jak dlouhá cesta to je, proč na desce 4 × 4 nikdy nevznikne věž větší než 131 072 = 2¹⁷, jak vypadá rytmus dlouhé hry a jak hrát, aby hra zůstala zábavou: s přestávkami a bez „ještě jedné“ do noci.
Horolezci říkají, že vrchol je jen polovina cesty – druhá polovina je sestup. V dlouhé hře 2048 je to podobné: každá další věž je „vyšší vrchol“, ke kterému vede dvakrát delší cesta než k předchozímu, a místa na desce je čím dál méně. Kdo nezná svoji mez, končí vyčerpaný v pozici, kterou by odpočatý zvládl.
+Teorie: cesta za 2048, největší možná věž, rytmus dlouhé hry, rekordy, zdravé hraní
7.1Za hranicí 2048
Věž 4096 potřebuje druhou 2048 vedle první. Ta se staví ze stejného žebříku jako první, jen o pole užší, protože první 2048 už jedno pole zabírá. Každé další patro zdvojnásobí potřebný počet tahů a ubere pole. Jak to vypadá v číslech, ukazuje simulace počítače, který prohledává o tři tahy dopředu (kapitola 9):
| Věž | Hloubka 3: her s věží | Hloubka 2: her s věží | Průměrný tah vzniku (hloubka 3) | Odhad 2ⁿ / 2,2 |
|---|---|---|---|---|
| 512 | 100 % | 97,4 % | 263 | 233 |
| 1 024 | 100 % | 90,8 % | 518 | 465 |
| 2 048 | 94 % | 70,0 % | 997 | 931 |
| 4 096 | 75 % | 20,6 % | 1 943 | 1 862 |
| 8 192 | 16 % | 0,2 % | 3 764 | 3 724 |
7.2Největší možná věž: 131 072
Kolik polí potřebuje věž 2ᵐ? Těsně předtím, než vznikne, musí na desce stát dvě věže 2ᵐ⁻¹. Ta druhá vznikla z dvou 2ᵐ⁻², zatímco první už stála – a tak dál dolů. V kritické chvíli tedy stojí současně 2ᵐ⁻¹, 2ᵐ⁻², …, 2² a nakonec buď dvě dvojky, nebo jedna nová čtyřka. To je m věží, se šťastnou čtyřkou m − 1. Na desce s N poli proto vznikne nejvýš 2ᴺ, když padají jen dvojky, a 2ᴺ⁺¹ s čtyřkami.maximum tile
Přesný výpočet na malých deskách (kapitola 11) to potvrzuje: na desce 2 × 2 jde s čtyřkami postavit 32 = 2⁵, ale ne 64, na desce 2 × 3 jde 128 = 2⁷, ale ne 256. Že je největší možná věž na desce 4 × 4 právě 131 072, uvádí i encyklopedické heslo o hře (příloha C). Je to ale věž teoretická: vyžaduje šťastnou čtyřku na posledním poli a bezchybnou hru přes zhruba 60 tisíc tahů.
| Deska | Polí N | Jen dvojky | I čtyřky |
|---|---|---|---|
| 2 × 2 | 4 | 16 | 32 |
| 3 × 3 | 9 | 512 | 1 024 |
| 4 × 4 | 16 | 65 536 | 131 072 |
| 5 × 5 | 25 | 33 554 432 | 67 108 864 |
| krychle 3 × 3 × 3 | 27 | 134 217 728 | 268 435 456 |
7.3Kolik je to času
Součet desky roste průměrně o 2,2 za tah, takže věž 2ⁿ trvá zhruba 2ⁿ / 2,2 tahů. Při jednom tahu za sekundu je 2048 asi čtvrthodinka (931 s ≈ 16 min), 8192 hodina, 65 536 přes osm hodin a 131 072 přes 16 hodin čistého hraní (59 578 tahů). Skutečný hráč přemýšlí v kritických chvílích déle, takže dlouhé hry se natahují na mnoho večerů.
7.4Rytmus dlouhé hry
- Úklid. Po velkém sloučení (třeba 1024 + 1024) zbude deska skoro prázdná a stojí na ní pár velkých věží. Teď se staví nový žebřík vedle starého.
- Stavba. Dlouhá klidná fáze: hlavní směry, plná spodní řada, malé věže daleko od rohu (kapitola 5).
- Kritická chvíle. Než se uzavře další patro, je deska skoro plná – rozpočet polí z tab. 5.1. Tady se hraje pomalu a s rozmyslem; právě tady počítač nejvíc přemýšlí.
Hranice, kam až se dá v 2048 dojít, posouvaly počítačové programy. Expectimax R. Xiaa z března 2014 postavil 16 384 ve 94 % ze 100 her a 32 768 ve 36 %. Práce Yeha a kol. (2017) popisuje první zaznamenanou věž 65 536, které program dosáhl v jedné hře. Jaśkowski (2018) s učenou sítí a prohledáváním postavil 32 768 v 70 % her. Podrobnosti v kapitolách 9 a 10, zdroje v příloze C.
7.5Zdravé hraní
Hra nemá konec ani přirozenou přestávku – po každém tahu následuje další a po každé věži větší. Právě proto se snadno hraje „ještě jednu“ dlouho do noci. Pár pravidel, která pomáhají:
- Cíl předem. Rozhodněte se, kdy skončíte: po věži 2048, po půlhodině, po třech hrách. 3D hra průvodce si rozehranou hru uloží, takže přerušení nic nestojí.
- Přestávka v kritické chvíli. Unavený hráč dělá nouzové tahy, kterým by se odpočatý vyhnul. Když se deska zaplní, vstaňte, napijte se, protáhněte se.
- Ne před spaním. Svítící obrazovka a napětí z poslední věže nejsou dobrá příprava na spánek.
- Bez sázek a peněz. Hra je pro radost; nehraje se o nic, co by bolelo ztratit.
Pocit „teď už to vyjde“ je u náhodných her klamný. Další nová věž nezávisí na předchozích – nic se „nevyrovná“. Když se několik her po sobě nedaří, je to signál k přestávce, ne k další hře.
V dlouhé hře si po každém uzavřeném patře udělejte krátkou kontrolu: kde je roh, jak dlouhý je had, kolik různých pater stojí mimo něj. Na desce se po velkém sloučení „vyčistí“ místo – je to nejlepší chvíle naplánovat další žebřík.
7.6Procvičení
- Každé další patro znamená dvakrát delší cestu a o pole menší rezervu: 2048 asi 1 000 tahů, 8192 asi 3 800.
- Na N polích vznikne nejvýš 2ᴺ⁺¹; na desce 4 × 4 je to 131 072 a jen s velkým štěstím.
- Hrajte s předem daným cílem a s přestávkami – hra přestávku sama nenabídne.
Pravděpodobnost a rizikopokročilí
Náhoda v 2048 má jen dvě podoby: kam padne nová věž (na každé volné pole se stejnou pravděpodobností) a jaká (dvojka s 90 %, čtyřka s 10 %). Z těchto dvou pravidel jde spočítat překvapivě mnoho: jak často začíná hra čtyřkou, jaká je očekávaná hodnota pozice, jaké riziko nese tah, po kterém zbudou dvě volná pole. A tam, kde vzorec nestačí, pomůže simulace – s počtem her a s poctivě uvedenou nejistotou.
Předpověď „30 % šance na déšť“ neříká, že bude pršet třetinu dne. Říká, že ze sta takových dnů prší asi ve třiceti. Riziko tahu je stejné: tah s rizikem 10 % neprohraje desetinu hry, ale v jedné z deseti podobných pozic skončí špatně. Kdo hraje stovky tahů, potká obě strany té pravděpodobnosti.
+Teorie: kam padá nová věž, čtyřky, očekávaná hodnota, riziko tahu, simulace a nejistota
8.1Kam padne nová věž
Je-li po tahu E volných polí, padne nová věž na každé z nich s pravděpodobností 1/E. Při jednom volném poli je místo jisté, při osmi je šance na konkrétní pole 12,5 %. Hodnota je na poli nezávislá: dvojka 0,9, čtyřka 0,1. Pravděpodobnost, že na konkrétní pole padne čtyřka, je tedy 0,1/E.spawn distribution
8.2Jak často padá čtyřka
Mezi m novými věžemi je aspoň jedna čtyřka s pravděpodobností 1 − 0,9ᵐ (doplněk jevu „samé dvojky“). Na první čtyřku se čeká průměrně 10 nových věží (geometrické rozdělení); 22 věží po sobě bez čtyřky přijde jen s pravděpodobností 0,9²² ≈ 9,9 %. V simulacích průvodce byl podíl čtyřek mezi novými věžemi 9,96 % až 10,03 % – přesně podle pravidla.geometric distribution
| m | 1 | 2 | 5 | 10 | 20 | 50 |
|---|---|---|---|---|---|---|
| 1 − 0,9ᵐ | 10 % | 19 % | 40,95 % | 65,13 % | 87,84 % | 99,48 % |
8.3Očekávaná hodnota pozice
Má-li pozice po tahu a nové věži hodnotu V (třeba šanci na výhru nebo hodnocení heuristikou), je hodnota tahu průměr přes všechny možné nové věže, vážený jejich pravděpodobností. Tak hodnotí tahy expectimax (kapitola 9). Očekávaná hodnota ale skrývá rozptyl: tah s průměrem 90 může mít 10 % šanci na katastrofu, tah s průměrem 85 žádnou.expected value
8.4Riziko tahu
Průvodce měří riziko tahu přesně: projde všechna volná pole po tahu a pro dvojku i čtyřku zjistí, zda pak půjde hlavní směr, jen nouzový tah, nebo nic. Součet pravděpodobností špatných případů je riziko. Na obr. 8.1 jsou tři tahy z pozice „Riziko proti riziku“.move risk
V pozici 4 2 4 2 / 32 2 2 4 / 128 32 8 2 / 512 128 64 16 sloučí každý ze čtyř tahů aspoň jednu dvojici a po každém zbude jediné volné pole. Po ↓ ale nová dvojka (90 %) ukončí hru, kdežto po ← nebo → zůstane hra v chodu v každém případě. Tah k rohu tu je ten nejhorší – riziko 90 %.
Nízké riziko teď neznamená dobrý tah. Riziko se dívá jen o jednu novou věž dopředu. Tah s nulovým rizikem, který vytáhne největší věž z rohu, může prohrát za deset tahů. Proto počítač kombinuje riziko s hodnocením pozice a dívá se hlouběji.
8.5Simulace a nejistota
Mnoho otázek („která strategie je lepší?“) se vzorcem vyřešit nedá. Pak pomůže Monte Carlo: odehrát mnoho her a spočítat průměr. Každý výsledek simulace je ale jen odhad. Průvodce u každého čísla uvádí počet her a 95% interval spolehlivosti; dvě strategie považuje za odlišné, jen když se jejich intervaly nepřekrývají.Monte Carlo, confidence interval
| Strategie | Her | Skóre | Věž ≥ 256 | Věž ≥ 512 | Věž ≥ 1 024 |
|---|---|---|---|---|---|
| náhodné tahy | 10 000 | 1 099 ± 11 | 8,0 ± 0,5 % | 0,02 % | 0 % |
| pevné pořadí ↓ ← → ↑ | 10 000 | 2 542 ± 24 | 51,2 ± 1,0 % | 4,4 ± 0,4 % | 0,01 % |
| chamtivě podle heuristiky | 5 000 | 4 651 ± 56 | 89,1 ± 0,9 % | 31,9 ± 1,3 % | 1,3 ± 0,3 % |
Když máte na výběr dva tahy a jeden nechá tři volná pole a druhý jen jedno, spočítejte, co hrozí na jediném poli. Stačí otázka: „Kdyby sem padla dvojka, půjde ↓ nebo ←?“ Je-li odpověď „ne“, má tah riziko aspoň 90 %.
8.6Procvičení
- Nová věž padá na každé volné pole stejně pravděpodobně; čtyřka je v 10 % případů, v průměru každá desátá.
- Riziko tahu je součet pravděpodobností polí, na kterých nová věž způsobí nouzový tah nebo konec hry.
- Simulace je odhad: uvádějte počet her a interval spolehlivosti, srovnávejte jen nepřekrývající se intervaly.
Počítač hraje I: expectimaxmistr a věda
Počítač neví, jak hrát 2048 – ale umí rychle zkoušet. Projde všechny čtyři tahy, po každém všechny možné nové věže, po nich zase všechny tahy… a vznikne strom hry. Na jeho konci pozice ohodnotí heuristikou: počítá volná pole, sousední stejné věže a to, jak monotónně věže v řadách klesají. Protože novou věž neklade soupeř, ale náhoda, nepočítá s nejhorším případem (minimax), ale s průměrem váženým pravděpodobností – to je expectimax. S hloubkou 3 postavil ve 100 hrách průvodce věž 2048 v 94 % a 4096 v 75 % her.
Před výletem se díváte na předpověď: „Když půjdeme přes kopec a začne pršet, schováme se na chatě; když nezačne, bude výhled…“ Každá volba se větví podle počasí. Nevíte, co přijde, ale víte, jak je to pravděpodobné, a volíte trasu, která v průměru dopadne nejlépe. Přesně tak „přemýšlí“ expectimax.
+Teorie: strom hry, minimax a expectimax, heuristiky, hloubka, ořezávání, jak dobře to hraje
9.1Strom hry
Strom má dva druhy uzlů, které se střídají. V uzlu MAX volí hráč jeden ze čtyř tahů. V uzlu náhody „volí“ příroda: pole a hodnotu nové věže. Hloubka 1 znamená jeden tah hráče a jednu novou věž, pak se pozice ohodnotí. Hloubka 2 pod každým listem znovu rozvine čtyři tahy a nové věže – strom roste zhruba s mocninou 4 · 2 · E na hloubku.game tree, chance node
| Pozice | Volná pole | Hloubka 1 | Hloubka 2 | Hloubka 3 | Expectimax | Minimax |
|---|---|---|---|---|---|---|
| A | 3 | 32 | 650 | 7 256 | ← | ↑ |
| B | 5 | 37 | 1 431 | 21 474 | ↑ | → |
| C | 5 | 48 | 1 608 | 23 008 | ← | → |
| D | 3 | 32 | 701 | 6 918 | ↓ | ← |
9.2Minimax, nebo expectimax?
Minimax je algoritmus her dvou soupeřů (šachy): v uzlu soupeře počítá s jeho nejlepší odpovědí, tedy pro nás s nejhorší. V 2048 by to znamenalo předpokládat, že nová věž padne vždy na nejhorší pole. Expectimax místo minima počítá očekávanou hodnotu: průměr přes volná pole, na každém 0,9 · (hodnota s dvojkou) + 0,1 · (hodnota se čtyřkou).minimax, expectimax
| Tah | Sloučení | Průměr (expectimax) | Nejhorší list (minimax) |
|---|---|---|---|
| ← | 1 | −3 486 | −5 718 |
| → | 1 | −5 438 | −6 423 |
| ↑ | 0 | −5 251 | −5 547 |
| ↓ | 0 | −6 299 | −6 502 |
Minimax není „bezpečnější expectimax“. Kdyby nová věž opravdu padala na nejhorší pole, hrálo by se úplně jinou hru – v kapitole 12 taková zlomyslná nová věž srazí průměrné skóre chamtivé strategie ze 4 446 na 987. Proti náhodě je minimax zbytečně opatrný a vzdává dobré tahy kvůli málo pravděpodobným katastrofám.
9.3Heuristika: jak ohodnotit pozici
Strom nejde prohledat až do konce hry, a tak se v listech pozice ohodnotí odhadem. Průvodce používá heuristiku ve tvaru, který zveřejnil R. Xiao ve svém programu z roku 2014 (příloha C). Pro každý řádek a sloupec spočítá:evaluation function
- Volná pole (270): každé prázdné pole v řadě je zásoba tahů (kapitola 5).
- Sloučení (700): sousední stejné věže, tedy prostor do příštího tahu.
- Monotónnost (47): trest za „zuby“ v řadě, kde věže stoupají i klesají. Měří se v obou směrech a bere se menší trest – řada má být monotónní kterýmkoli směrem. Čtvrtá mocnina pater způsobí, že zub u velké věže bolí mnohem víc než u malé (kapitola 4).
- Součet (11): trest za velké věže mimo jiné – drží desku „uklizenou“.
Všimněte si, co v heuristice není: žádný roh ani had. Přesto hráč s ní drží největší věž v rohu v 98 až 99 % tahů (tab. 3.1). Monotónnost ve všech řádcích i sloupcích zároveň se nejlépe splní tak, že největší věž stojí v rohu a hodnoty od ní klesají – roh i had z heuristiky „vyplynou“. Laboratoř nabízí i přímý bonus za roh; vyzkoušejte, jak změní rozhodnutí.
Další možná složka je hladkost: trest za velký rozdíl pater mezi sousedy. Věže, které se liší o jedno patro, se brzy sloučí; 2 vedle 512 ne. V heuristice průvodce hladkost zastupuje člen sloučení (stejní sousedé) a monotónnost (pozvolné klesání).
9.4Hloubka, paměť a ořezávání
Čím hlouběji počítač hledá, tím lépe hraje – a tím déle. Simulace průvodce (semínko 2026): hloubka 1 (2 000 her) průměr 4 221 bodů a věž 2048 nikdy; hloubka 2 (500 her) 32 741 bodů a 2048 v 70 % her; hloubka 3 (100 her) 70 988 bodů a 2048 v 94 % her. Každá hloubka navíc ale znásobí čas – hloubka 3 hrála v průvodci asi 7 sekund na hru, hloubka 1 setiny sekundy.search depth, pruning
Dva triky šetří čas. Paměť (transpoziční tabulka): stejná pozice vzniká různými cestami a stačí ji vyhodnotit jednou. Ořezávání málo pravděpodobných větví: program R. Xiaa nerozvíjí uzly, ke kterým vede cesta s pravděpodobností pod 0,0001, a ušetřený čas věnuje hlubšímu hledání tam, kde na tom záleží. Xiao navíc ukládá celou desku do jednoho 64bitového čísla (4 bity na pole) a hodnoty řad počítá dopředu do tabulky – jedna řada má jen 16⁴ = 65 536 možností.
V březnu 2014, pár týdnů po vydání hry, zveřejnil R. Xiao program s expectimaxem, bitovou deskou a heuristikou s volnými poli, monotónností a sloučeními; váhy vyladil evoluční metodou CMA-ES. Podle jeho popisu ve 100 hrách postavil 2048, 4096 i 8192 v každé hře, 16 384 v 94 % a 32 768 v 36 % her; medián skóre byl 387 222, nejlepší hra 794 076.
Člověk nedokáže prohledat strom, ale může si osvojit heuristiku: před tahem „spočítat“ volná pole, stejné sousedy a zuby v řadách. Tah, který přidá zub ve spodní řadě, je skoro vždy horší než tah, který jen nesloučí.
9.5Procvičení
- Počítač střídá uzly hráče (maximum) a uzly náhody (průměr) – expectimax. Minimax by počítal s nejhorší novou věží a byl zbytečně opatrný.
- Listy hodnotí heuristika: volná pole, sloučení, monotónnost a součet; roh z ní vyplyne sám.
- Hloubka rozhoduje: 2048 v 0 %, 70 % a 94 % her pro hloubku 1, 2 a 3.
Počítač hraje II: učení z vlastních hermistr a věda
Expectimax potřebuje heuristiku, kterou vymyslel člověk. Jde to i bez ní: program začne s prázdnou „pamětí“ a hraje. Po každém tahu porovná, jak dobře pozici odhadl, s tím, co přišlo potom, a odhad trochu opraví. Tomu se říká učení s časovým rozdílem (TD, temporal difference). Paměť je obří tabulka: pro každou skupinu polí – řádek, sloupec, čtverec 2 × 2 – a pro každou kombinaci pater v ní jedno číslo. Takové síti se říká n-tuple síť. V roce 2014 ukázali Marcin Szubert a Wojciech Jaśkowski, že se tak program naučí postavit 2048 ve více než 97 % her, aniž by se díval víc než jeden tah dopředu.
Nikdo se nenaučil jezdit na kole z knihy. Dítě jede, zakymácí se, opraví řídítka a příště to zkusí jinak. Každý pokus trochu posune odhad „co se stane, když se nakloním“. Program, který se učí 2048 metodou TD, dělá totéž – jen místo stovek pokusů odehraje desítky tisíc her.
+Teorie: zpětnovazební učení, stav po tahu, pravidlo TD, n-tuple síť, výsledky výzkumu
10.1Učení z odměny
Zpětnovazební učení (reinforcement learning) zná jen odměny: body za sloučení. Program se má naučit funkci V, která každé desce přiřadí, kolik bodů z ní ještě průměrně získá. Kdyby V znal přesně, stačilo by v každé pozici zvolit tah s nejvyšším součtem „body teď + V pozice po tahu“ – bez prohledávání.reinforcement learning, value function
10.2Stav po tahu a pravidlo TD
V 2048 se vyplatí hodnotit desku po tahu hráče a před novou věží (afterstate). Je deterministická – víme ji přesně – a náhoda přijde až potom. Po dalším tahu program zjistí, co z ní skutečně vzešlo: odměnu r dalšího tahu a novou desku po tahu s′. Rozdíl mezi „co jsem čekal“ a „co přišlo“ je chyba TD a odhad se o kousek posune jejím směrem.afterstate, TD error
Program přitom nemusí zkoušet náhodné tahy „pro průzkum“: náhoda nových věží ho sama zavádí do různých pozic. Tak to popsali i Szubert a Jaśkowski a tak se učí síť v laboratoři.
10.3N-tuple síť
Desek 4 × 4 je příliš mnoho, než aby měla každá svou hodnotu (kapitola 11). N-tuple síť proto hodnotu skládá z částí. Vybere pevné skupiny polí (n-tice) a pro každou si drží tabulku: jedno číslo pro každou kombinaci pater v těch polích. Hodnota desky je součet čísel ze všech tabulek. Učení upraví jen ta čísla, která se na desce právě použila.n-tuple network, lookup table
| Deska | N-tic / vah | Prvních 100 her | Průměr po blocích 500 her | Posledních 500 her |
|---|---|---|---|---|
| 3 × 3, 5 000 her | 10 / 286 720 | 323 | 454, 765, 929, 961, 1 037, 1 064, 1 112, 1 090, 1 146, 1 134 | věž ≥ 128 v 84,6 %, ≥ 256 v 6,4 % |
| 4 × 4, 3 000 her | 17 / 1 114 112 | 2 720 | 5 030, 7 972, 9 543, 9 925, 10 366, 10 806 | věž ≥ 1 024 v 42,4 %, 2048 v 1,8 % |
Křivka učení kolísá. Blok 500 her je náhodný vzorek a se semínkem se mění; pokles z 1 112 na 1 090 neznamená, že se síť „odnaučila“. Trend je vidět až na delším úseku – a v laboratoři si to vyzkoušíte tlačítkem „Nová síť“.
10.4Co dokázal výzkum
Szubert a Jaśkowski (2014) na konferenci IEEE CIG v Dortmundu ukázali, že síť učená metodou TD na stavech po tahu postaví 2048 ve více než 97 % her bez jakéhokoli prohledávání. Jejich nejlepší síť měla dvě přímé čtveřice a dva obdélníky po šesti polích, vzorkované se všemi souměrnostmi desky – celkem 22 882 500 vah (autoři počítají 15 stavů pole: 2 · 15⁴ + 2 · 15⁶). V milionu her měla míru výher 0,9781, průměrné skóre 100 178 a nejlepší hru 261 526. Hraje přitom velmi rychle, protože každý tah znamená jen několik pohledů do tabulek.
- Yeh, Wu, Hsueh, Chang, Liang, Chiang (2017) učili síť ve více etapách (pro různé fáze hry zvlášť) a s prohledáváním o tři tahy dopředu dosáhli 32 768 v 18,31 % her; po vyladění v 31,75 % z 10 000 her. Jedna hra dosáhla 65 536 – podle autorů poprvé zaznamenaná.
- Jaśkowski (2018) přidal zpožděné učení, víceetapové sítě a další triky. S expectimaxem a sekundou na tah měl průměrné skóre 609 104, věž 16 384 v 97 % a 32 768 v 70 % ze 100 her.
- Guei, Chen a Wu (2021) s „optimistickým“ TD učením uvádějí průměr 625 377 a věž 32 768 v 72 % her.
Encyklopedické heslo o hře zmiňuje i novější nadšenecké programy (2022 a 2025), které uvádějí 32 768 ve více než 75 %, resp. 86,1 % her a 65 536 v jednotkách procent. Jde o výsledky zveřejněné autory programů, ne o recenzované práce, a průvodce je uvádí jen pro představu.
Deska otočená o 90° nebo zrcadlená má stejnou hodnotu. Síť, která vyhodnotí každou n-tici v osmi polohách (4 otočení × zrcadlení) a sdílí pro ně jednu tabulku, se učí osmkrát rychleji ze stejného počtu her. Síť v laboratoři to pro jednoduchost nedělá – místo toho má n-tice na všech místech desky.
Hráč se učí podobně jako síť: po hře si projděte, kde se pokazila (kdy roh utekl, kde se zlomil had), a příště v podobné pozici zkuste jiný tah. Jedna hra je málo – trend uvidíte po desítkách her.
10.5Procvičení
- Učení TD opravuje odhad hodnoty desky po tahu podle toho, co přišlo potom; žádná ruční heuristika není potřeba.
- N-tuple síť skládá hodnotu z tabulek pro skupiny polí; v laboratoři 17 čtveřic a 1 114 112 vah.
- Výzkum: přes 97 % výher bez prohledávání (2014), 32 768 v 70 % her s prohledáváním (2018).
Matematika a složitostmistr a věda
Kolik různých desek může v 2048 vzniknout? Jde spočítat, jakou šanci na výhru má dokonalý hráč? A jak těžké je hru „vyřešit“? Na desce 4 × 4 je možných pozic tolik, že je počítač nikdy neprojde. Na malých deskách 2 × 2 a 2 × 3 to ale jde – a laboratoř tam spočítá přesnou pravděpodobnost výhry nejlepší možné hry. Pro obecné desky pak matematici dokázali, že i hra bez nových věží je NP-úplná: patří mezi nejtěžší úlohy, pro které nikdo nezná rychlý obecný algoritmus.
Hod kostkou spočítáte na papíře: šestka padne s pravděpodobností jedna šestina. Partii šachů nespočítáte – možností je příliš mnoho. 2048 leží mezi nimi: na desce 2 × 2 se dá projít každá pozice, na 4 × 4 už ne. Malé desky jsou okno, kterým je vidět, jak by vypadala dokonalá hra.
+Teorie: počet stavů, Markovův řetězec, přesné výsledky, NP-úplnost, krychle 3 × 3 × 3
11.1Kolik je desek
Každé pole desky 4 × 4 je prázdné, nebo nese věž s patrem 1 až 17 (víc nejde, kapitola 7). To je 18 možností na pole a nejvýš 18¹⁶ ≈ 1,21 · 10²⁰ desek. Skutečně dosažitelných je méně – deska se dvěma věžemi 131 072 nikdy nevznikne – ale i hrubý odhad ukazuje, že je nelze projít jednu po druhé. Pro srovnání: 10²⁰ sekund je asi 3 · 10¹² let.state space
| Deska | Polí | Možností na pole | Horní odhad |
|---|---|---|---|
| 2 × 2 | 4 | 6 | 6⁴ = 1 296 |
| 2 × 3 | 6 | 8 | 8⁶ = 262 144 |
| 3 × 3 | 9 | 11 | 11⁹ = 2 357 947 691 |
| 4 × 4 | 16 | 18 | 18¹⁶ ≈ 1,21 · 10²⁰ |
| 5 × 5 | 25 | 27 | 27²⁵ ≈ 6,08 · 10³⁵ |
| krychle 3 × 3 × 3 | 27 | 29 | 29²⁷ ≈ 3,05 · 10³⁹ |
11.2Markovův řetězec a rozhodovací proces
Hraje-li hráč podle pevného pravidla (třeba „první platný z ↓ ← → ↑“), závisí další deska jen na současné desce a na náhodě. To je Markovův řetězec: z každého stavu vedou šipky do dalších stavů s danými pravděpodobnostmi. Když hráč volí, vznikne Markovův rozhodovací proces. Jeho nejlepší strategii najde dynamické programování: hodnota každého stavu je maximum přes tahy z průměru přes nové věže.Markov chain, Markov decision process
V 2048 je výpočet jednodušší než obvykle, protože hra se nikdy nevrací do stejné pozice: součet desky po každém tahu vzroste o 2 nebo 4. Stavy se tedy dají seřadit podle součtu a hodnoty počítat od konce. Konec hry bez cíle má hodnotu 0.
11.3Přesné výsledky na malých deskách
| Deska | Cíl | Nejlepší hra | Pevné pořadí | Náhodné tahy | Pozic |
|---|---|---|---|---|---|
| 2 × 2 | 8 | 100 % | 92,57 % | 65,56 % | 70 |
| 2 × 2 | 16 | 96,25 % | 23,55 % | 12,18 % | 214 |
| 2 × 2 | 32 | 8,29 % | 0 % | 0,05 % | 422 |
| 2 × 3 | 32 | 99,99 % | 26,26 % | 9,21 % | 11 222 |
| 2 × 3 | 64 | 93,93 % | 0,0137 % | 0,0167 % | 27 022 |
| 2 × 3 | 128 | 5,70 % | 0 % | 0 % | 52 486 |
Na desce 2 × 3 dosáhne nejlepší hra věže 64 v 93,93 % her. Pevné pořadí, které na desce 4 × 4 tolik pomáhá, tu má jen 0,0137 % – horší než náhodné tahy. Malá deska trestá jakoukoli strnulost: s šesti poli nejde držet roh a zároveň slučovat. Přesný výpočet tak ukazuje, že „roh“ není zákon, ale dobrá heuristika pro desku, na které je dost místa.
11.4Jak těžká je hra: NP-úplnost
Teorie složitosti se ptá, jak roste čas výpočtu s velikostí úlohy. Úlohy z třídy NP mají řešení, které jde rychle ověřit; NP-úplné úlohy jsou mezi nimi nejtěžší – kdyby jednu z nich šlo řešit rychle (v polynomiálním čase), šly by rychle všechny. To se považuje za velmi nepravděpodobné, ale nikdo to nevyvrátil ani nedokázal.NP-completeness
Abdelkader, Acharya a Dasler v článku 2048 Without New Tiles Is Still Hard (konference FUN 2016) zkoumali variantu bez nových věží na obdélníkové desce m × n. Dokázali, že rozhodnout, zda jde postavit věž 2ᵏ (pro pevné k, třeba 2048), je NP-úplné; převedli na ni klasickou NP-úplnou úlohu 3SAT. NP-úplné jsou podle nich i otázky, zda jde dosáhnout daného počtu tahů a daného skóre. Ve stejném sborníku Langerman a Uno ukázali, že hry Threes!, Fives, 1024! a 2048 jsou NP-těžké v modelu, kde hráč zná všechny budoucí nové věže předem. Starší práce Mehty (2014) tvrdila dokonce PSPACE-úplnost; Abdelkader a kol. ale v jejím převodu upozorňují na několik problémů.
Co to znamená pro hráče? Nic pro desku 4 × 4 – na ní je úloha konečná a malá. Výsledky platí pro desky libovolné velikosti a říkají, že obecný rychlý postup „jak vždy najít řešení“ neexistuje, pokud neplatí P = NP. Proto se počítače učí heuristikám a prohledávání, ne vzorci (kapitoly 9 a 10). A proto i úlohy bez nových věží v kapitole 12 řeší průvodce prohledáváním.
NP-úplnost se týká nejhoršího případu na velkých deskách. Neříká, že každá úloha je těžká – většina úloh z generátoru v kapitole 12 má řešení za 1 až 3 tahy. Ani neříká nic o tom, jak těžké je postavit 2048 v obyčejné hře s náhodou.
11.5Vyšší dimenze: krychle 3 × 3 × 3
Ve 3D hře průvodce je režim Krychle: tři desky 3 × 3 nad sebou, celkem 27 polí. Tahy jsou v šesti směrech (čtyři vodorovné a nahoru a dolů) a každý posune 9 linií po třech polích; celkem má krychle 3 · 9 = 27 linií. Největší možná věž je 2²⁸ = 268 435 456, horní odhad počtu pozic 29²⁷ ≈ 3 · 10³⁹. Protože jsou linie krátké (jen tři pole), je těžké držet dlouhého hada; cílem režimu je proto „jen“ 1024.3D variant
V krychli funguje roh ve třech rozměrech: největší věž do jednoho rohu krychle a hlavní směry tři – dva vodorovné k rohu a jeden svislý. Had pak vede po spodní desce a pokračuje na desku nad ní.
11.6Procvičení
- Desek 4 × 4 je až 18¹⁶ ≈ 10²⁰ – nejde je projít; na malých deskách ale jde spočítat dokonalou hru přesně.
- Hra s pevnou strategií je Markovův řetězec, s volbou tahů Markovův rozhodovací proces; součet desky roste, takže nemá cykly.
- 2048 bez nových věží na desce m × n je NP-úplné (Abdelkader, Acharya, Dasler 2016).
Hlavolamy a tvorbamistr a věda
Když z 2048 odstraníte náhodu, zbude čistý hlavolam: zadaná deska, žádné nové věže, postavte věž 64 nejvýš ve 4 tazích. Takové úlohy má režim Úlohy ve 3D hře a laboratoř níže. Kapitola ukáže, jak je počítač vyrábí a ověřuje – prohledáváním do šířky, které najde nejmenší počet tahů –, jak se ladí obtížnost (včetně zlomyslné nové věže, která padá tam, kde nejvíc škodí) a jaké varianty žánru existují: trojky, Fibonacciho čísla, šestiúhelníky a krychle.
Šachové úlohy „mat ve dvou tazích“ jsou starší než většina šachových turnajů. Nejsou to partie, ale miniatury: pevná pozice, jasný cíl a právě jedno krátké řešení. Úlohy bez nových věží jsou totéž pro 2048 – místo hledání matu hledáte řetěz sloučení.
+Teorie: úloha bez náhody, prohledávání do šířky, generátor, ladění obtížnosti, varianty žánru
12.1Úloha bez náhody
Úloha je trojice: deska, cílová věž 2ᵍ a limit N tahů. Tahy fungují jako v kapitole 1, jen po nich nepadá nic. Bez nových věží je každý tah deterministický a celou úlohu jde prohledat. Úloha je dobrá, když N je nejmenší počet tahů, kterým se cíl dá postavit – pak má hráč jistotu, že řešení existuje, a nedá se „vyhrát náhodou“ s rezervou.puzzle without spawns
12.2Prohledávání do šířky
Prohledávání do šířky (BFS) projde nejdřív všechny pozice po 1 tahu, pak všechny po 2 tazích a tak dál; pozice, která už byla, se znovu nerozvíjí. První nalezená pozice s cílovou věží leží v nejmenším možném počtu tahů, protože všechny kratší posloupnosti už byly vyzkoušeny. Cestu zpět k zadání najde podle zapamatovaných předchůdců.breadth-first search
Každá vrstva má nejvýš čtyřnásobek předchozí, takže po d tazích je pozic nejvýš 4ᵈ (pro 8 tahů 65 536). Ve skutečnosti je jich mnohem méně, protože různé posloupnosti vedou ke stejné desce: v úloze z obr. 12.1 jen 28.
12.3Generátor úloh
Generátor rozmístí 7 až 10 věží na náhodná pole, největší z nich 32, 64 nebo 128, a cíl je o patro výš. Pak úlohu vyřeší prohledáváním. Většina náhodných desek je ale příliš snadná, nebo neřešitelná. Ze 1 000 pokusů (semínko 99) mělo 43 desek menší součet než cílová věž (nemůže ji postavit nic), 4 nešly vyřešit do 14 tahů a zbylé potřebovaly takto tahů:
| Tahů | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 až 14 |
|---|---|---|---|---|---|---|---|---|---|
| Desek | 426 | 221 | 123 | 67 | 38 | 30 | 23 | 13 | 12 |
Úloha se 4 tahy, kterou vyřeší skoro každá náhodná posloupnost, není hlavolam. Generátor proto pro každou kandidátku zahraje 400 náhodných posloupností tahů délky N a úlohu zahodí, když uspěje víc než čtvrtina. V bance vyšla nejvyšší úspěšnost náhodných tahů 8,5 % – úlohy se musí opravdu řešit.
12.4Ladění obtížnosti a zlomyslná nová věž
Obtížnost úlohy roste s počtem tahů, s počtem věží, které „překážejí“, a s tím, jak málo náhodných posloupností uspěje. U hry s náhodou se ladí jinak: velikostí desky (5 × 5 je snazší), poměrem čtyřek, počtem kroků zpět – a umístěním nové věže. Nejtvrdší je zlomyslná nová věž, která padá jako soupeř: na pole a s hodnotou, po kterých je nejlepší odpověď hráče co nejhorší. Takovou má obtížnost 5 ve 3D hře.adversarial spawn
| Strategie | Nová věž | Průměrné skóre | Tahů | Nejčastější nejvyšší věž |
|---|---|---|---|---|
| chamtivá heuristika | náhodná | 4 446 | 350 | 256 (23 ze 40 her) |
| zlomyslná | 987 | 80 | 128 (15 ze 40) | |
| expectimax, hloubka 1 | náhodná | 4 408 | 348 | 256 (22 ze 40) |
| zlomyslná | 512 | 54 | 32 (24 ze 40) |
„Hra mě nenávidí, čtyřka padla zrovna tam, kde vadí“ – v obyčejné hře to není pravda. Nová věž padá na každé volné pole se stejnou pravděpodobností (původní zdrojový kód, příloha C). Zlomyslnou věž má jen obtížnost 5 ve 3D hře průvodce a pozná se snadno: hra s ní trvá desítky tahů, ne stovky.
12.5Varianty žánru
- Trojky. V Threes (únor 2014) se 1 a 2 slučují ve 3, pak stejné násobky tří (3 + 3 = 6, 6 + 6 = 12 …) a kameny se posouvají jen o jedno pole. Hra je pomalejší a víc taktická.
- Fibonacciho čísla. Varianta známá jako 2584 (otevřený kód pod licencí MIT) slučuje sousední Fibonacciho čísla: 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13. Stejné věže se tu (s výjimkou 1 + 1) neslučují.
- Šestiúhelníky. Na šestiúhelníkové desce má každé pole šest sousedů a nabízí se šest směrů tahu. Existují volně šířené hexagonální varianty; jejich pravidla se liší a průvodce je podrobně neověřoval.
- Krychle a jiné desky. Desky 3 × 3, 5 × 5, obdélníky a prostorová krychle mění rozpočet polí (kapitola 7) a tím obtížnost. Krychli 3 × 3 × 3 najdete ve 3D hře (kapitola 11).
- Dvojkové věže ve 3D. Vlastní hra průvodce: stejná pravidla tahu, ale věže z pater místo plochých kamenů, popisky čísla / mocniny / patra, denní výzva se stejnou řadou nových věží pro všechny, úlohy bez nových věží a režim pro děti.
Úlohy řešte od cíle: kde musí stát dvě věže 2ᵍ⁻¹, aby se sloučily? A odkud se vezme ta druhá? Řetěz sloučení si projděte pozpátku a teprve pak hledejte tahy, které věže na ta místa dopraví.
12.6Procvičení
- Úloha bez nových věží je deterministická; prohledávání do šířky najde nejmenší počet tahů a ten je limitem úlohy.
- Generátor zahazuje snadné, neřešitelné a náhodou řešitelné desky; dobrou úlohu dá jen asi každý šestý pokus.
- Zlomyslná nová věž srazí skóre chamtivé strategie ze 4 446 na 987; v obyčejné hře padá nová věž rovnoměrně.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky
| Technika | Pravidlo, podle kterého ji trenér ohlásí | Kapitola |
|---|---|---|
| Nouzový tah | ↓ ani ← nejdou, nebo tah vytáhne největší věž z rohu | 6 |
| Sloučit hned | tah slučuje a žádný jiný tah nesloučí víc | 5 |
| Hadí řada | tah ↓ nebo ←, po něm je spodní řada plná, od rohu neroste a roh drží největší věž | 4 |
| Volná pole | po tahu zůstane nejvíc prostoru (volná pole + sousední stejné dvojice) a žádný jiný tah ho nemá stejně | 5 |
| Roh | všechny ostatní platné tahy | 3 |
Vzorce na jednom místě
Počty na jednom místě
| Údaj | Hodnota | Kde |
|---|---|---|
| různé začátky hry / s aspoň jednou čtyřkou | 480 / 19 % | kap. 1 |
| skóre věže 2048 jen z dvojek / očekávané s čtyřkami | 20 480 / 20 107,6 | kap. 2 |
| nových věží k 2048 (odhad) / nejméně tahů | 931 / 510 | kap. 2 |
| první 2048 ve hře počítače (hloubka 3, 100 her): tah / součet desky | 997 / 2 198 | kap. 2, 7 |
| největší věž v rohu: náhodně / pevné pořadí / heuristika | 11,1 / 76,7 / 98,5 % tahů | kap. 3 |
| průměrné skóre: náhodně / pevné pořadí / heuristika (10 000 / 10 000 / 5 000 her) | 1 099 / 2 542 / 4 651 | kap. 3, 8 |
| expectimax hloubka 1 / 2 / 3: věž 2048 | 0 / 70 / 94 % her | kap. 7, 9 |
| největší možná věž na 4 × 4: jen dvojky / i čtyřky | 65 536 / 131 072 | kap. 7 |
| síť TD v laboratoři 4 × 4: vah / skóre po 3 000 hrách | 1 114 112 / 10 806 | kap. 10 |
| přesně: nejlepší hra 2 × 2, cíl 16 / 32 | 96,25 / 8,29 % | kap. 11 |
| horní odhad počtu desek 4 × 4 | 18¹⁶ ≈ 1,21 · 10²⁰ | kap. 11 |
| náhodné desky generátoru s úlohou na 4 až 8 tahů | 171 z 1 000 | kap. 12 |
| zlomyslná nová věž: skóre chamtivé strategie | 4 446 → 987 | kap. 12 |
Zdroje a předpoklady
Historické údaje, pravidla původní hry a výsledky výzkumu byly ověřeny na uvedených zdrojích. Ověřeno 9. 11. 2026.
Hra 2048 a její předchůdci
- Cirulli, G.: 2048 – veřejný repozitář se zdrojovým kódem hry (github.com/gabrielecirulli/2048). Popis projektu: klon hry 1024 založený na 2048 od autora Saming, „nepřímo inspirovaný“ hrou Threes; licence MIT. Zdrojový kód (game_manager.js, grid.js): start se dvěma věžemi, nová věž
Math.random() < 0.9 ? 2 : 4na náhodně zvoleném volném poli, každá věž se v tahu slučuje nejvýš jednou, ke skóre se přičítá hodnota sloučené věže, výhra při věži 2048. Ověřeno 9. 11. 2026. - Encyklopedické heslo 2048 (video game) (Wikipedie, anglická verze) a prameny v něm citované – Gabriele Cirulli, italský webový vývojář, 19 let, vydání 9. března 2014, napsáno za víkend v JavaScriptu a CSS, licence MIT; největší možná věž 131 072; upravené verze (větší a menší desky, prostorová verze); výsledky nadšeneckých programů z let 2022 a 2025. Ověřeno 9. 11. 2026.
- Encyklopedické heslo Threes (Wikipedie, anglická verze) – autoři Asher Vollmer (návrh), Greg Wohlwend (grafika), Jimmy Hinson (hudba), vydání 6. února 2014; pravidla (1 + 2 = 3, slučování stejných násobků tří, posun o jedno pole); napodobeniny 1024 a Fives během několika týdnů a rozšíření 2048 v březnu 2014. Ověřeno 9. 11. 2026.
- 2584 – veřejný repozitář Fibonacciho varianty (github.com/oxguy3/2584): slučují se čísla sousední ve Fibonacciho posloupnosti, licence MIT, odvozeno od 2048. Ověřeno 9. 11. 2026.
Počítačoví hráči a učení
- Xiao, R. (2014): popis a zdrojový kód expectimax hráče 2048 (repozitář nneonneo/2048-ai a autorův text z března 2014) – bitová deska v 64bitovém čísle, tabulky řad, heuristika s volnými poli, sloučeními, monotónností a součtem (konstanty 200 000, 270, 700, 47 s mocninou 4, 11 s mocninou 3,5), práh pravděpodobnosti 0,0001 pro ořezávání, ladění CMA-ES; výsledky ve 100 hrách: 2048, 4096 a 8192 ve 100 %, 16 384 v 94 %, 32 768 v 36 %, medián skóre 387 222, nejméně 124 024, nejvíc 794 076. Ověřeno 9. 11. 2026.
- Szubert, M.; Jaśkowski, W. (2014): Temporal Difference Learning of N-Tuple Networks for the Game 2048. In: IEEE Conference on Computational Intelligence and Games (CIG 2014), Dortmund – TD učení na stavech po tahu, výhra ve více než 97 % her bez prohledávání, nejlepší síť 22 882 500 vah, míra výher 0,9781 v 1 000 000 her, průměr 100 178, nejvíc 261 526; citace autora hry o podílu výher a odehraném čase. Ověřeno 9. 11. 2026.
- Yeh, K.-H.; Wu, I-C.; Hsueh, C.-H.; Chang, C.-C.; Liang, C.-C.; Chiang, H. (2017): Multistage Temporal Difference Learning for 2048-like Games. IEEE Transactions on Computational Intelligence and AI in Games 9(4); preprint arXiv:1606.07374 – 32 768 v 18,31 % her s prohledáváním do hloubky 3, po vyladění v 31,75 % z 10 000 her, jedna hra s věží 65 536. Ověřeno 9. 11. 2026.
- Jaśkowski, W. (2018): Mastering 2048 With Delayed Temporal Coherence Learning, Multistage Weight Promotion, Redundant Encoding, and Carousel Shaping. IEEE Transactions on Computational Intelligence and AI in Games 10(1), 3–14, DOI 10.1109/TCIAIG.2017.2651887 – s 1 s na tah průměr 609 104, 16 384 v 97 % a 32 768 v 70 % ze 100 her. Ověřeno 9. 11. 2026.
- Guei, H.; Chen, L.-P.; Wu, I-C. (2021): Optimistic Temporal Difference Learning for 2048. IEEE Transactions on Games, DOI 10.1109/TG.2021.3109887 (přijato 3. 9. 2021) – průměr 625 377, 32 768 v 72 % her. Ověřeno 9. 11. 2026 (bez čísla ročníku a stran).
Složitost
- Abdelkader, A.; Acharya, A.; Dasler, P. (2016): 2048 Without New Tiles Is Still Hard. In: 8th International Conference on Fun with Algorithms (FUN 2016), LIPIcs 49, 1:1–1:14, DOI 10.4230/LIPIcs.FUN.2016.1 – varianta bez nových věží na desce m × n; NP-úplnost rozhodnutí o dosažení věže 2ᵏ (převod z 3SAT), také o počtu tahů a skóre; poznámky k převodu v práci Mehty. Ověřeno 9. 11. 2026.
- Langerman, S.; Uno, Y. (2016): Threes!, Fives, 1024!, and 2048 are Hard. In: FUN 2016, LIPIcs 49, 22:1–22:14; preprint arXiv:1505.04274 – NP-těžkost v modelu se známými budoucími věžemi. Ověřeno 9. 11. 2026.
- Mehta (2014): 2048 is (PSPACE) Hard, but Sometimes Easy. Preprint arXiv:1408.6315 – tvrzení o PSPACE-úplnosti. Ověřeno 9. 11. 2026 (název a tvrzení).
Modelové předpoklady laboratoří
Všechna čísla, pozice, tabulky a simulace v průvodci počítá stejný kód jako laboratoře (tah, sloučení, nová věž podle zdrojového kódu původní hry). Simulace strategií: deska 4 × 4, semínko 2026; náhodné tahy a pevné pořadí 10 000 her, chamtivá heuristika 5 000, expectimax hloubky 1, 2 a 3 postupně 2 000, 500 a 100 her. Heuristika má tvar podle programu R. Xiaa (kap. 9), bez bonusu za roh; expectimax prohledává všechna volná pole bez ořezávání, s pamětí v rámci jednoho rozhodnutí. Pozice minihry „Který tah?“ (24) a „Nouzový tah“ (19) pocházejí z her expectimaxu s hloubkou 2 a strategie pevného pořadí, jsou otočené tak, aby největší věž byla vlevo dole, a ohodnocené expectimaxem s hloubkou 3; správně je každý tah do 5 % rozpětí hodnot od nejlepšího. Monte Carlo v kapitole 6 hraje chamtivou heuristikou. Síť TD v kapitole 10 je zjednodušená (n-tice na všech místech desky bez souměrností, 16 stavů pole, α = 0,05). Přesné výpočty v kapitole 11 jsou úplné (bez simulace). Úlohy v kapitole 12 ověřilo prohledávání do šířky. Pole se značí ř (řádek shora) a s (sloupec zleva).
Co zůstává nejisté
Data vzniku her 1024 a 2048 od autora Saming průvodce nezjistil; jejich pořadí uvádí jen popis Cirulliho projektu a encyklopedické heslo. Údaje o tom, že ve hře za první tři týdny hráči strávili přes 3 000 let a že vyhráno bylo jen asi 1 % her, známe jen z citace v článku Szuberta a Jaśkowského, ne z vlastního zdroje autora hry. Výsledky nadšeneckých programů z let 2022 a 2025 známe jen z encyklopedického hesla, nejsou recenzované a průvodce je neověřoval u autorů. Výsledky R. Xiaa a výzkumných týmů jsou výsledky uvedené autory, průvodce je nepřepočítával. U článku Gueie, Chena a Wua jsme neověřili ročník a strany. Pravidla hexagonálních variant se liší a průvodce je podrobně neověřoval. Výsledky simulací průvodce jsou náhodné odhady; u každého je uveden počet her a kde je to podstatné, i interval spolehlivosti.