Úžasné figúrky
Legendárny Tetris vytvoril v 80. rokoch minulého storočia Alexey Pajitnov. matematik
Pajitnov vydal jednu z prvých verzií hry na sovietskom mikropočítači "Electronics-60"
Cieľom Tetrisu je pohybovať sa a otáčať pri pádegeometrické tvary na vytvorenie úplných radov v spodnej časti hracieho poľa, ktoré získavajú body. Z praktického hľadiska ide o hru na rýchlosť reakcie a koncentráciu, no matematici sa na to pozerajú z iného uhla. Vedci analyzovali výpočtovú zložitosť algoritmu Tetris a určili, že patrí do triedy NP-úplný - nedeterministický polynóm; pre takéto veci neexistujú žiadne účinné algoritmy riešenia.
Kľúčovým problémom je, že množstvopre nájdenie riešenia výpočtu rastie exponenciálne s nárastom počtu premenných (veľkosť problému). Napríklad, ak existujú štyri parametre, potom je potrebných 16 iterácií, a ak 100, potom 2 ^ 100, čo je viac ako atómov vo vesmíre (!). Typický počítač, keď je správne vyladený, dokáže vykonať niekoľko miliárd týchto iterácií za sekundu. V súlade s tým môže ľahko vyriešiť malé NP-problémy pomocou enumerácie, a keď sa počet premenných výrazne zvýši ako 15, prestane riešiť.
Čo sa týka Tetrisu.Veľkosť úlohy klasickej hry je malá: v samostatnom kroku je aktuálna krajina v skle (hracom poli) - to je parameter, ktorý výrazne neovplyvňuje množstvo výpočtov. Sú tam informácie o aktuálnom a nasledujúcom obrazci - to sú dve skupiny premenných: pre každý obrazec sú maximálne štyri (hoci pre štvorec - iba jedna) orientácia v priestore a maximálne 10 súradníc "pristátia" postavy. Každý ťah má 40 stavov, dva majú 1600, viac informácií nie je, toto je malý NP problém. Hoci Tetris môže byť komplikovaný: zvýšte počet buniek na 100 a uistite sa, že hráč vie nielen to, aká bude ďalšia figúrka, ale aj sto ďalších, potom by nastali problémy.
Nepoznáte ani iné NP-kompletné hryz počutia: hľadanie mín, sudoku, tag a dokonca aj nekomerčná verzia Super Maria. Napriek jednoduchosti ich pravidiel, za určitých podmienok sa ich rozmer zväčšuje, počítač nemôže ponúknuť ideálne riešenie. Prečo to matematikov zaujíma? Pretože výber najlepšej trasy, optimalizácia procesu alebo harmonogramu sú tiež problémy triedy NP.
Klasický „Mario“ vyzeral takto
Logické hry sú mimoriadne pohodlné testovacie prostredietestovacie algoritmy a ich softvérová implementácia. Hádanky sú najčastejšie „čisté“, bez rôznych druhov výnimiek z pravidiel, ktoré sú vlastné praktickým problémom. Stavový priestor takýchto problémov má nastaviteľný rozmer a vlastnosti sa pri škálovaní nemenia (napríklad tagy 2x2, 4x4, 3x6). Všetky stavy sú opísané rovnakým spôsobom. Matematický popis hádaniek spravidla tiež nie je taký zložitý ako popis životných problémov.
Doba „kvantových“ hračiek
Rovnaký problém s batohom (ako sa tam zmestí viac vecív obmedzenom priestore) dosť pripomína hru Tetris a efektívny výsledok bude užitočný pre logistické spoločnosti, pretože im umožní neplytvať zdrojmi. Ak sa pre ktorýkoľvek z týchto problémov alebo hier nájde „polynomiálne rýchly“ algoritmus, potom môže byť akýkoľvek iný problém z triedy NP vyriešený rovnako „rýchlo“. Teoreticky s tým pomôžu kvantové počítače, no zatiaľ existujú len prototypy týchto počítačov budúcnosti. V roku 2018 bol dokonca vynájdený nový koncept popisujúci súčasný stav výroby kvantových procesorov – éra NISQ (hlučná kvantová éra stredného rozsahu), alebo doba subkvantových technológií.
Zatiaľ čo vedci pracujú na zlepšení kvantprocesov, vedúci spoločnosti hľadajú moderné analógy, ktoré pomáhajú optimalizovať prácu výroby. Takouto „náhradou“ sa stali kvantovo inšpirované algoritmy, ktoré na konvenčných počítačoch nachádzajú 95 – 99 % optimálne riešenie. V Rusku to robí QuSolve – úlohy, na ktorých spoločnosť pracuje, patria do triedy NP a matematici vyvíjajú a zlepšujú algoritmy na riešenie obchodných problémov. V QuSolve na testovanie vlastného riešiča (solvera) použili značky, ktoré pomohli nájsť pár chýb v algoritme a doplniť rozhranie softvérového balíka.
Súčasní vedci naozaj nerobia nič inéRozmýšľate, ako všetko vylepšiť a optimalizovať? Samozrejme, že nie. Vo voľnom čase pokračujú vo vymýšľaní hier. Vývojári už dokázali premeniť väčšinu hier na NP a pridali trochu kúzla kvantových fyzikálnych javov.
Takto sa kvantové technológie objavili za posledných 10 rokov.dáma, kvantová námorná bitka a kvantové tic-tac-toe. Osobitnú obľubu si získal kvantový šach, v ktorom sa dokonca konajú turnaje a šampión získava titul veľmajstra. Väčšina nových „kvantových hier“ je postavená na základnom princípe kvantovej mechaniky – superpozícii.
Napríklad šachové figúrky môžu byť inniekoľko miest na hracej ploche súčasne, čo znamená, že je ťažšie brániť sa a útočiť - to robí hru nepredvídateľnou a veľkolepou. V roku 2016 dokonca nakrútili krátky film, ktorý ukázal partiu kvantového šachu medzi Stephenom Hawkingom a Paulom Ruddom, hercom známym z role Ant-Mana v Marvel Cinematic Universe.
Snímka obrazovky hry. Takto vyzeral online board v hre medzi Hawkingom a Ruddom. Potom herec legendárneho fyzika porazil
Nevieme, či tieto hry budú takéto aj v budúcnostisú také bežné ako obyčajné piškvorky, tetris a tagy, ale určite inšpirujú matematikov k vytvoreniu jedinečných algoritmov na riešenie praktických obchodných problémov a vývoj technológií. O tom niet pochýb.
Čítaj viac:
Vedci zistili, že tvar Mliečnej dráhy vôbec nie je taký, ako sme si celý čas mysleli
Dve superzeme nachádzajúce sa na okraji obývateľnej zóny: jedna z nich má príjemnú teplotu
Našli čiernu dieru, ktorá ničí hviezdny záznam blízko Zeme