Úžasné figurky
Legendární Tetris vytvořil v 80. letech minulého století Alexey Pajitnov. Matematik
Pajitnov vydal jednu z prvních verzí hry na sovětském mikropočítači "Electronics-60"
Cílem Tetrisu je pohybovat se a otáčet pádemgeometrické tvary k vytvoření úplných řad ve spodní části hracího pole, které získávají body. Z praktického hlediska jde o hru na rychlost reakce a koncentraci, ale matematici se na to dívají z jiného úhlu. Vědci analyzovali výpočetní složitost algoritmu Tetris a určili, že patří do třídy NP-úplný - nedeterministický polynom; pro takové věci neexistují žádné efektivní algoritmy řešení.
Klíčovým problémem je, že množstvípro nalezení řešení výpočtu roste exponenciálně s nárůstem počtu proměnných (velikost problému). Například, pokud existují čtyři parametry, pak je potřeba 16 iterací, a pokud 100, pak 2 ^ 100, což je více než atomů ve vesmíru (!). Typický počítač, když je správně vyladěn, dokáže provést několik miliard těchto iterací za sekundu. V souladu s tím může snadno řešit malé NP-problémy výčtem, a když proměnné znatelně překročí 15, přestane řešit.
Co se týče Tetrisu.Velikost úkolu klasické hry je malá: v samostatném kroku je ve skle (hracím poli) aktuální krajina - to je parametr, nijak výrazně neovlivňuje množství výpočtů. Jsou zde informace o aktuálním a následujícím obrazci - to jsou dvě skupiny proměnných: pro každý obrazec jsou maximálně čtyři (i když u čtverce pouze jedna) orientace v prostoru a maximálně 10 souřadnic "přistání" postavy. Každý tah má 40 stavů, dva mají 1600, více informací není, to je malý NP problém. Přestože Tetris může být komplikovaný: zvyšte počet buněk na 100 a ujistěte se, že hráč ví nejen to, jaká bude další figurka, ale i stovka dalších, pak by nastaly problémy.
Neznáte ani jiné NP-complete hryz doslechu: hledání min, sudoku, tag a dokonce i nekomerční verze Super Maria. Přes jednoduchost jejich pravidel, za určitých podmínek se jejich rozměr zvětšuje, počítač nemůže nabídnout ideální řešení. Proč to matematiky zajímá? Protože výběr nejlepší trasy, optimalizace procesu nebo harmonogramu jsou také problémy třídy NP.
Klasický "Mario" vypadal takto
Logické hry jsou extrémně pohodlným testovacím prostředímtestovací algoritmy a jejich softwarová implementace. Hádanky jsou nejčastěji „čisté“, bez různých druhů výjimek z pravidel, které jsou vlastní praktickým problémům. Stavový prostor takových problémů má nastavitelný rozměr a vlastnosti se při škálování nemění (například tagy 2x2, 4x4, 3x6). Všechny stavy jsou popsány stejným způsobem. Matematický popis hádanek také zpravidla není tak složitý jako popis životních problémů.
Doba „kvantových“ hraček
Stejný problém s batohem (jak se do něj vejde více věcív omezeném prostoru) dost připomíná hru Tetris a efektivní výsledek se bude hodit logistickým společnostem, protože jim umožní neplýtvat zdroji. Pokud se pro některý z těchto problémů nebo her najde „polynomiálně rychlý“ algoritmus, lze stejně „rychle“ vyřešit jakýkoli jiný problém z třídy NP. Teoreticky s tím pomohou kvantové počítače, ale zatím existují pouze prototypy těchto počítačů budoucnosti. V roce 2018 byl dokonce vynalezen nový koncept popisující současný stav výroby kvantových procesorů – éra NISQ (noisy medium-scale quantum era), neboli doba subkvantových technologií.
Zatímco vědci pracují na zlepšení kvantprocesů, vedoucí společnosti hledají moderní analogy, které pomáhají optimalizovat práci výroby. Takovou „náhradou“ se staly kvantově inspirované algoritmy, které na konvenčních počítačích nacházejí 95-99% optimální řešení. V Rusku to dělá QuSolve – úkoly, na kterých společnost pracuje, patří do třídy NP a matematici vyvíjejí a vylepšují algoritmy pro řešení obchodních problémů. V QuSolve k testování vlastního řešiče (řešiče) použili značky, které pomohly najít pár chyb v algoritmu a doplnit rozhraní softwarového balíku.
Opravdu moderní vědci nedělají nic jiného nežPřemýšlíte, jak vše vylepšit a optimalizovat? Samozřejmě že ne. Ve volném čase pokračují ve vymýšlení her. Vývojáři již dokázali většinu her proměnit v NP a přidali trochu kouzla kvantově fyzikálních jevů.
Takto se objevily kvantové technologie za posledních 10 let.dáma, kvantová námořní bitva a kvantové tic-tac-toe. Obzvláště oblibu si získaly kvantové šachy, ve kterých se dokonce konají turnaje a šampionovi se uděluje titul velmistra. Většina nových „kvantových her“ je postavena na základním principu kvantové mechaniky – superpozici.
Například šachové figurky mohou být inněkolik míst na herním plánu současně, což znamená, že je obtížnější bránit a útočit - díky tomu je hra nepředvídatelná a velkolepá. V roce 2016 dokonce natočili krátký film, který ukazoval partii kvantových šachů mezi Stephenem Hawkingem a Paulem Ruddem, hercem známým díky roli Ant-Mana v Marvel Cinematic Universe.
Snímek obrazovky hry. Takto vypadal online board ve hře mezi Hawkingem a Ruddem. Poté herec legendárního fyzika porazil
Nevíme, zda tyto hry budou v budoucnu takovéstejně běžné jako obyčejné piškvorky, tetris a tagy, ale rozhodně budou inspirovat matematiky k vytvoření jedinečných algoritmů pro řešení praktických obchodních problémů a vývoj technologií. O tom není pochyb.
Přečtěte si více:
Vědci zjistili, že tvar Mléčné dráhy vůbec není takový, jaký jsme si celou dobu mysleli
Dvě superzemě nalezené na okraji obyvatelné zóny: jedna z nich má příjemnou teplotu
Nalezena černá díra, která ničí hvězdný záznam blízko Země