Underbara figurer
Den legendariska Tetris skapades på 80-talet av förra seklet av Alexey Pajitnov. Matematiker
Pajitnov släppte en av de första versionerna av spelet på den sovjetiska mikrodatorn "Electronics-60"
Målet med Tetris är att flytta och rotera fallandegeometriska former för att bilda kompletta rader längst ner på spelplanen och få poäng. Ur praktisk synvinkel är detta ett spel med reaktionshastighet och koncentration, men matematiker ser på det från en annan vinkel. Forskare analyserade beräkningskomplexiteten hos Tetris-algoritmen och fastställde att den tillhör klassen av NP-komplett - icke-deterministiskt polynom; det finns inga effektiva lösningsalgoritmer för sådana saker.
Det viktigaste problemet är att mängdenför att hitta en lösning på beräkningen växer exponentiellt med en ökning av antalet variabler (problemstorlek). Till exempel, om det finns fyra parametrar, behövs 16 iterationer, och om 100, då 2 ^ 100, vilket är mer än atomer i universum (!). En typisk dator kan, när den är rätt inställd, göra flera miljarder av dessa iterationer per sekund. Följaktligen kan han enkelt lösa små NP-problem genom uppräkning, och när variablerna blir märkbart fler än 15 kommer han att sluta lösa.
När det gäller Tetris.Uppgiftsstorleken för det klassiska spelet är liten: i ett separat steg finns det ett aktuellt landskap i glaset (spelfältet) - det här är en parameter, den påverkar inte nämnvärt mängden beräkningar. Det finns information om den nuvarande och nästa figur - det här är två grupper av variabler: för varje figur finns det maximalt fyra (även om för en kvadrat - bara en) orienteringar i rymden och maximalt 10 koordinater för "landningen" av figurerna. Varje drag har 40 tillstånd, två har 1 600, det finns ingen mer information, detta är ett litet NP-problem. Även om Tetris kan vara komplicerat: öka antalet celler till 100 och se till att spelaren inte bara vet vad nästa siffra kommer att bli, utan också hundra av de nästa, då skulle det bli problem.
Du känner inte till andra NP-kompletta spel hellerfrån hörsägen: minsvepare, sudoku, tagg och till och med en icke-kommersiell version av Super Mario. Trots de enkla reglerna, under vissa förhållanden, ökar deras dimensioner, datorn kan inte erbjuda en idealisk lösning. Varför bryr sig matematiker? Eftersom att välja den bästa rutten, optimera en process eller ett schema är också NP-klassproblem.
Klassiska "Mario" såg ut så här
Logikspel är en extremt bekväm testplats förtestalgoritmer och deras mjukvaruimplementering. Pussel är oftast "rena", utan olika typer av undantag från de regler som är inneboende i praktiska problem. Tillståndsutrymmet för sådana problem har en justerbar dimension, och egenskaperna ändras inte vid skalning (till exempel taggar 2x2, 4x4, 3x6). Alla stater beskrivs på samma sätt. Den matematiska beskrivningen av pussel är som regel inte heller lika komplex som livsproblemen.
Tiden för "kvantleksaker".
Samma problem med en ryggsäck (hur man får plats med fler sakeri ett begränsat utrymme) påminner ganska mycket om ett spel Tetris, och det effektiva resultatet kommer att vara användbart för logistikföretag, eftersom det kommer att tillåta dem att inte slösa med resurser. Om en "polynomiellt snabb" algoritm hittas för något av dessa problem eller spel, kan alla andra problem från NP-klassen lösas lika "snabbt". I teorin kommer kvantdatorer att hjälpa till med detta, men än så länge finns det bara prototyper av dessa framtidsdatorer. Under 2018 uppfanns till och med ett nytt koncept för att beskriva det nuvarande produktionsläget för kvantprocessorer - NISQ:s era (bullrig mellanskalig kvantera), eller tiden för sub-kvantteknologier.
Medan forskare arbetar för att förbättra kvantprocesser, företagsledare letar efter moderna analoger som hjälper till att optimera produktionsarbetet. En sådan "ersättning" har blivit kvantinspirerade algoritmer som hittar en 95-99% optimal lösning på konventionella datorer. I Ryssland gör QuSolve detta - uppgifterna som företaget arbetar med tillhör NP-klassen, och matematiker utvecklar och förbättrar algoritmer för att lösa affärsproblem. I QuSolve, för att testa sin egen lösare (lösare), använde de taggar, vilket hjälpte till att hitta ett par fel i algoritmen och göra tillägg till mjukvarupaketets gränssnitt.
Gör moderna vetenskapsmän verkligen inget annat änFunderar du på hur du kan förbättra och optimera allt? Självklart inte. På fritiden fortsätter de att hitta på spel. Utvecklarna har redan kunnat förvandla de flesta spel till NP och lagt till lite magi av kvantfysiska fenomen.
Så här har kvantteknologier sett ut under de senaste 10 åren.pjäser, quantum sea battle och quantum tic-tac-toe. Kvantschack har vunnit särskild popularitet, där turneringar till och med hålls, och mästaren tilldelas titeln stormästare. De flesta av de nya "kvantspelen" är byggda på kvantmekanikens grundläggande princip - superposition.
Till exempel kan schackpjäser vara iflera platser på spelplanen samtidigt, vilket gör att det är svårare att försvara och attackera – detta gör spelet oförutsägbart och spektakulärt. 2016 filmade de till och med en kortfilm som visade ett parti kvantschack mellan Stephen Hawking och Paul Rudd, en skådespelare känd för sin roll som Ant-Man i Marvel Cinematic Universe.
Spelskärmdump. Så här såg onlinetavlan ut i spelet mellan Hawking och Rudd. Sedan slog skådespelaren den legendariska fysikern
Vi vet inte om dessa spel kommer att vara så här i framtidenlika vardagligt som vanlig tic-tac-toe, tetris och tag, men de kommer definitivt att inspirera matematiker att skapa unika algoritmer för att lösa praktiska affärsproblem och utveckla teknik. Det råder ingen tvekan om det.
Läs mer:
Formen på Vintergatan är inte alls vad vi trodde hela tiden, har forskare funnit
Två superjordar finns på kanten av den beboeliga zonen: en av dem har en behaglig temperatur
Hittade ett svart hål som förstör ett stjärnrekord nära jorden