Jako dítě z 90. let jsem se nemohl vyhnout nejlepšímu sellerovi Tetris. Tetris, který byl zahájen v roce 1984 ruským programátorem Alexey Pajitnov, se rychle stal trhákem a v průběhu let měl stovky milionů hráčů. Já sám jsem strávil hodiny na svém herním chlapci a snažil se umístit padající cihly tak, aby vyplnili podmínky co nejvíce. V průběhu hry tyto bloky klesly rychleji a rychleji a moje palce mohly sotva držet krok s ovládacími prvky.
V zásadě všechny hry – dokonce i ty, které se lišily Candy Crush Saga, Kouzlo: Shromáždění a Wordle– může být prozkoumán z matematického hlediska. Tetris však má mnoho zvláštních spojení s matematikou. Například cíl hry silně připomíná problémy s geometriíve kterém určíte, zda můžete pokrýt oblast nekonečně velkou sadou dlaždic bez jakýchkoli mezer.
Ale Tetris je obzvláště zajímavý pro matematiky z hlediska jeho složitosti. Přesněji řečeno, vědci přemýšleli o výpočetním výkonu, který je zapotřebí k určení, jak nebo zda může někdo skutečně „vyřešit“ Tetris, za předpokladu podmínek, jako je konečný počet cihel a schopnost znát pořadí, ve kterém se objeví různé tvary. Ukazuje se, že toto konkrétní rámování umístí Tetris mezi nejvyšších her.
O podpoře vědecké žurnalistiky
Pokud se vám tento článek líbí, zvažte podporu naší oceněné žurnalistiky předplatné. Zakoupením předplatného pomáháte zajistit budoucnost působivých příběhů o objevech a myšlenkách, které dnes formují náš svět.
Definování složitosti
V oblasti teorie složitosti se matematici a počítačoví vědci snaží charakterizovat obtížné řešení problémů. Definovali více tříd složitosti nebo kategorie, včetně problémů P a NP. Jednoduše řečeno, problémy P jsou pro konvenční počítače snadné vyřešit, zatímco problémy NP jsou obtížnější, ale v případě, že máte možné řešení, snadno se kontrolují. (Problémy s NP lze považovat za puzzle Sudoku: Vyplnění polí může trvat hodiny, ale zjištění, zda je řešení správné.)
Abychom určili složitost úkolu, musíme porovnat různé problémy mezi sebou. Pokud každý algoritmus, který řeší úkol A Může také vyřešit úkol B, Například tedy A je složitější než B. Nebo jak to uvedli matematici: B je „redukovatelný“ na A. To znamená, že porovnáním Tetris s jiným známým problémem P nebo NP lze určit jeho složitost.
Jak si tedy vybereme dobrý bod srovnání? Počítačoví vědci se mohou obrátit na tzv. NP-kompletní problémy, na které lze snížit všechny ostatní problémy NP. Jedním z nich je problém se třemi děleními.
Tetris na Nintendo Gameboy v muzeu počítačových her Berlin.
Imago/Eibner Press Photo/Jonas Lohrmann/Alamy Reklamní fotografie
Problém se třemi děleními se zabývá otázkou, zda daná sada celých čísel, například {1, 2, 5, 6, 7, 9}, lze rozdělit do podmnožin se třemi prvky, že součet čísel je vždy stejný. Pro {1, 2, 5, 6, 7, 9} by byla divize {1, 5, 9} a {2, 6, 7}. Obsah každé podmnožiny se zvyšuje až 15. Taková rozdělení není možné pro každou danou sadu. Zjištění, zda to existuje nebo ne, se ukáže jako nesmírně obtížné: problém se třemi děleními je kompletní.
V roce 2003 počítačoví vědci na technologickém institutu Massachusetts prokázali, že otázka, zda může být deska Tetris v dané herní situaci vyčištěna samo o sobě může být mapován do problému se třemi děleními. Za tímto účelem vědci srovnávali mezery ve hře Tetris s podmnožinami problému a padajícími cihly s čísly, která musí být rozdělena.
Tímto způsobem vědci ukázali, že pokud lze soubor čísel rozdělit do tří prvkových podskupin se stejnou součtem, pak může být hrací pole Tetris také zcela vyprázdněno. Přitom dokázali, že otázky „lze sadu rozdělit na tří dělení?“ a „mohou být hřiště Tetris vyprázdněno?“ jsou identické z matematického hlediska.
Tento vhled znamená, že puzzle toho, zda dané cihly lze uspořádat vhodně, spadá do kategorie problémů s NP-dokončením, díky čemuž je Tetris velmi složitá hra. Čím delší je posloupnost cihel, které hra obsahuje, tím časově náročnější je, aby počítač určil rozpovolitelnost. A skutečně, konvenční počítače budou velmi rychle ohromeny: neexistuje žádný algoritmus, který by problém mohl efektivně vyřešit.
Tetris dosáhne limitů vypočítatelnosti
Tetris má ještě složitější vlastnosti, Jako počítačoví vědci Hendrik Jan Hoogeboom a Walter Kosters, oba na Leiden University v Nizozemsku, V příspěvku z roku 2004. Podívali se na trochu odlišnou otázku. Předpokládejme, že pozorujete hru Tetris, která má pouze protáhlé cihly ve tvaru I. Kdybych vám dal předem určený počet způsobů, řekněme, 40 dlaždic ve tvaru I, aby padly na prázdnou tetrisovou desku, mohli byste se rozhodnout, zda mezi těmito osmi způsoby existuje jeden, pro které rada skončí prázdná?
Hoogeboom a Kosters prokázali, že tato otázka je ve skutečnosti nerozhodnutelná, a to i s nekonečným množstvím výpočetního výkonu. Je to proto, že výše uvedená otázka může být zmapována na problém, který se týká neslavných vět o neúplnosti Kurta Gödela. Ty uvádějí, že v matematice budou vždy existovat prohlášení, která mohou Nebyl to prokázán ani nevyvráceno.
Tyto otázky samozřejmě pravděpodobně nemají žádný vliv na váš úspěch v Tetris. S rychlostí, při které kousky padají, není těžko přemýšlet o matematických problémech.
Přesto je pozoruhodné, že po více než 40 letech se ocenění Tetris stále roste a vyvíjí se, i když hra zůstává v podstatě nezměněna. Například technika hraní známé jako „válcování“ (která umožňuje provést velmi rychlé vstupy) umožnila postupovat dále než kdykoli předtím. V minulosti byla 29. úroveň považována za nepřekonatelný limit. Ale v roce 2023 tehdy třináctiletý zlomil všechny předchozí záznamy válcováním až na úroveň 157způsobuje havárii hry. Můžeme jen počkat a zjistit, co překvapí, že Tetris v budoucnu má v obchodě.
Tento článek se původně objevil v Spektrum vědy a byl reprodukován se svolením.
