Nuostabios figūrėlės
Legendinį „Tetris“ praėjusio amžiaus 80-aisiais sukūrė Aleksejus Pajitnovas. Matematikas
Pajitnovas išleido vieną iš pirmųjų žaidimo versijų sovietiniame mikrokompiuteryje „Electronics-60“
Tetris tikslas yra judėti ir suktis krintantgeometrines figūras, kad būtų suformuotos ištisos eilės žaidimo lauko apačioje, skaičiuojant taškus. Praktiniu požiūriu tai yra reakcijos greičio ir koncentracijos žaidimas, tačiau matematikai į tai žiūri kitu kampu. Mokslininkai išanalizavo Tetris algoritmo skaičiavimo sudėtingumą ir nustatė, kad jis priklauso NP pilno – nedeterministinio daugianario klasei; veiksmingų tokių dalykų sprendimo algoritmų nėra.
Pagrindinė problema yra ta, kad kiekisieškant sprendimo, skaičiavimas auga eksponentiškai didėjant kintamųjų skaičiui (problemos dydis). Pavyzdžiui, jei yra keturi parametrai, tada reikia 16 pakartojimų, o jei 100, tada 2 ^ 100, tai yra daugiau nei atomų Visatoje (!). Įprastas kompiuteris, tinkamai sureguliuotas, gali atlikti kelis milijardus šių iteracijų per sekundę. Atitinkamai, jis gali nesunkiai išspręsti mažas NP problemas surašydamas, o kai kintamieji tampa pastebimai daugiau nei 15, jis nustos spręsti.
Kalbant apie Tetris.Klasikinio žaidimo užduoties dydis yra nedidelis: atskirame žingsnyje stikle (žaidimo lauke) yra dabartinis kraštovaizdis - tai parametras, jis neturi didelės įtakos skaičiavimų kiekiui. Yra informacijos apie esamą ir kitą figūrą - tai dvi kintamųjų grupės: kiekvienai figūrai yra ne daugiau kaip keturios (nors kvadratui - tik viena) orientacijos erdvėje ir daugiausia 10 "nusileidimo" koordinačių. figūras. Kiekvienas judesys turi 40 būsenų, dviejose – 1600, daugiau informacijos nėra, tai nedidelė NP problema. Nors Tetris gali būti sudėtingas: padidinkite ląstelių skaičių iki 100 ir įsitikinkite, kad žaidėjas žino ne tik, koks bus kitas skaičius, bet ir šimtą kitų, tada kiltų problemų.
Jūs taip pat nežinote kitų NP pilnų žaidimųiš nuogirdų: minosvaidis, sudoku, žyma ir net nekomercinė Super Mario versija. Nepaisant jų taisyklių paprastumo, tam tikromis sąlygomis jų matmenys didėja, kompiuteris negali pasiūlyti idealaus sprendimo. Kodėl matematikai rūpi? Nes pasirinkti geriausią maršrutą, optimizuoti procesą ar tvarkaraštį taip pat yra NP klasės problemos.
Klasikinis „Mario“ atrodė taip
Loginiai žaidimai yra itin patogus išbandymo poligonastestavimo algoritmai ir jų programinė įranga. Dėlionės dažniausiai yra „grynos“, be įvairių taisyklių išimčių, kurios būdingos praktinėms problemoms. Tokių problemų būsenos erdvė turi reguliuojamą matmenį, o savybės nesikeičia keičiant mastelį (pvz., žymos 2x2, 4x4, 3x6). Visos būsenos aprašomos vienodai. Matematinis galvosūkių aprašymas, kaip taisyklė, taip pat nėra toks sudėtingas kaip gyvenimo problemų.
„Kvantinių“ žaislų metas
Ta pati problema dėl kuprinės (kaip sutalpinti daugiau daiktųribotoje erdvėje) gana primena Tetris žaidimą, o efektyvus rezultatas bus naudingas logistikos įmonėms, nes leis nešvaistyti resursų. Jei kuriai nors iš šių problemų ar žaidimų randamas „polinominis greitas“ algoritmas, tai bet kuri kita NP klasės problema gali būti išspręsta taip pat „greitai“. Teoriškai kvantiniai kompiuteriai tam padės, tačiau kol kas yra tik šių ateities kompiuterių prototipai. 2018 metais netgi buvo sugalvota nauja koncepcija, nusakanti dabartinę kvantinių procesorių gamybos būklę – NISQ (triukšmingo tarpinio masto kvantinės eros) erą arba subkvantinių technologijų laiką.
Kol mokslininkai stengiasi pagerinti kvantinįprocesus, įmonių vadovai ieško modernių analogų, padedančių optimizuoti gamybos darbą. Toks „pakaitalas“ tapo kvantinio įkvėpimo algoritmais, kurie įprastuose kompiuteriuose randa 95–99% optimalų sprendimą. Rusijoje tai daro „QuSolve“ – užduotys, kurias įmonė dirba, priklauso NP klasei, o matematikai kuria ir tobulina verslo problemų sprendimo algoritmus. QuSolve, norėdami išbandyti savo sprendiklį (solver), jie naudojo žymas, kurios padėjo rasti keletą algoritmo klaidų ir papildyti programinės įrangos paketo sąsają.
Ar tikrai šiuolaikiniai mokslininkai nedaro nieko kito, kaip tikAr galvojate, kaip viską patobulinti ir optimizuoti? Žinoma ne. Laisvalaikiu jie ir toliau kuria žaidimus. Kūrėjai jau sugebėjo daugumą žaidimų paversti NP, pridėdami šiek tiek kvantinių fizinių reiškinių magijos.
Taip per pastaruosius 10 metų atsirado kvantinės technologijos.šaškės, kvantinis jūrų mūšis ir kvantinis „tic-tac-toe“. Ypač išpopuliarėjo kvantiniai šachmatai, kuriuose netgi rengiami turnyrai, o čempionui suteikiamas didmeistrio vardas. Dauguma naujų „kvantinių žaidimų“ sukurti remiantis pagrindiniu kvantinės mechanikos principu – superpozicija.
Pavyzdžiui, gali būti šachmatų figūrėlėskelios vietos lentoje vienu metu, o tai reiškia, kad gintis ir atakuoti yra sunkiau – dėl to žaidimas tampa nenuspėjamas ir įspūdingas. 2016 m. jie netgi nufilmavo trumpametražį filmą, kuriame buvo parodytas Stepheno Hawkingo ir Paulo Ruddo, aktoriaus, žinomo dėl skruzdėlytės vaidmens filme „Marvel Cinematic Universe“, žaidimas kvantiniais šachmatais.
Žaidimo ekrano kopija. Taip atrodė internetinė lenta žaidime tarp Hawkingo ir Ruddo. Tada aktorius įveikė legendinį fiziką
Nežinome, ar tokie žaidimai bus ir ateityjetokie pat įprasti kaip ir paprasti „tic-tac-toe“, „tetris“ ir „tag“, tačiau jie tikrai įkvėps matematikus sukurti unikalius praktinių verslo problemų sprendimo ir technologijų kūrimo algoritmus. Dėl to nėra jokių abejonių.
Skaityti daugiau:
Mokslininkai nustatė, kad Paukščių Tako forma visai ne tokia, kokią manėme visą laiką
Dvi superžemės, rastos gyvenamosios zonos pakraštyje: viena iš jų turi patogią temperatūrą
Rasta juodoji skylė, kuri sunaikina žvaigždės rekordą netoli Žemės