Wetenschappelijk bewezen: Tetris is ingewikkeld

Wie denkt dat Tetris in dit tijdperk van 3D-games niet meer interessant is, heeft het mis. Wetenschappers hebben zich namelijk gebogen over de wiskundige achtergronden van het beroemde spel. Gebleken is dat de op het eerste gezicht eenvoudig lijkende opbouw toch ingenieuzer is dan je wellicht zou denken. Men heeft namelijk bewezen dat Tetris voldoet aan de eisen van een 'NP-compleet probleem'. Dit houdt in dat er geen algoritme te geven is dat een efficiënte manier van spelen berekent.

Zowel het maximaliseren van het aantal weggespeelde rijen, het aantal geplaatste stenen voordat het spel afgelopen is en het aantal tetrises (vier rijen tegelijk wegspelen), als het zo laag mogelijk houden van het bouwwerk, zijn niet wetenschappelijk te bereiken. Bovenstaande beweringen gelden zelfs indien de speler van tevoren al zou weten welke bouwstenen er allemaal aan staan te komen, zodat het echte spel - waarbij dit niet het geval is - zelfs nog moeilijker is:

The researchers further found that Tetris is an NP-hard problem, which means it is as least as difficult to solve as any other NP problem. "While you're playing Tetris, you're really solving hard problems," Demaine says. Interestingly, another seemingly simple but highly addictive game, Minesweeper, is also an NP-hard problem. So the next time you lose at either, take comfort in the fact that a computer may not have been able to do much better.

Lees het hele artikel bij Scientific American.

Reacties (71)

[Anoniem: 52488]

Is er nu al een oplossing voor het "traveling salesman"-probleem? (ook een NP-hard probleem)

Maareuh... so what? Er zijn zo veel problemen die NP-hard zijn, dat Tetris daar ook toe behoort verbaast mij wel enigzins maar om nu te zeggen dat het revolutionair is...

[En voor diegene die zich nu afvragen wat NP-hard betekent:
NP-hard wil zeggen Non Polynomial Hard.
Een rijtje van N cijfers sorteren van klein naar groot kan bijvoorbeeld in N^2 stappen, en als je een beetje je best doet lukt het ook nog in N*log(N) stappen.
Maar er zijn dus problemen die naarmate je de breedte van je speelveld (of de hoogte, of het aantal vormpjes van de blokken, of het aantal blokken dat gestapelt moet worden, of ...) vergroot niet in N^2, N^3, N^4, N^heelveel kunnen worden opgelost. In plaats daarvan stijgt het aantal benodigde stappen exponentieel (en da's veel en veel harder van N^heelveel).
Andere voorbeelden zijn bijvoorbeeld het op optimale wijze compileren van een programma, het op optimale wijze indelen van de layout van een chip of een print (lijkt dus op tetris), een optimale route plannen van A naar B.
Toch is voor veel van deze problemen wel een oplossing gevonden die voldoet, maar die is dus niet in alle gevallen "optimaal".]

[Cameleon73]

NP betekent niet Non Polynomial, maar Non-Deterministic Polynomial. Wist ik trouwens ook pas na het lezen van 't artikel achter de link die Dr_Distortion gaf... ('Popular article authored by Ian Stewart')

The problems involved here are said to have 'nondeterministic polynomial' running time: type NP.

NP is not the same as non-P.

Edit: spelfout en niet werkende tags verwijderd (heeft UBB geen onderstreep tags?)

[General_Failure]

In plaats daarvan stijgt het aantal benodigde stappen exponentieel (en da's veel en veel harder van N^heelveel).

En om preciezer te zijn met 2^N, 3^N, of iets dergelijks. Als N niet zo heel groot is, kan dus best de optimale oplossing gevonden worden, maar op een gegeven moment worden deze getallen heel snel hoger. Iedere keer dat N 1 hoger wordt verdubbelt de rekentijd.

[Anoniem: 68816]

Er is nog geen oplossing voor het "traveling salesman" oftwel handelsreiziger probleem gevonden. Dit zou trouwens ook meteen alle NP-compleet problemen oplossen omdat alle NP-complete problemen namelijk verbonden zijn en in elkaar zijn "over te schrijven". Dit betekent dat als je 1 NP-compleet probleem in polynomiale tijd op kunt lossen, dat je ze allemaal op kunt lossen.

De wetenschap is nog niet geslaagd in het vinden van een polynomiaal algoritme te vinden voor NP-complete problemen, maar heeft ook nog niet kunnen bewijzen dat zo'n oplossing niet bestaat. Er bestaan alleen wel sterke aanwijzingen dat zo'n oplossing er niet is.

[Janoz]

Daarnaast is het ook wel handig waneer dat nog ff duurt. Zo ongeveer alle fatsoenlijke coderings en security algoritmen zijn op NPC gebaseerd. In theorie komt het er dus op neer dat iemand die TSP oplost alle huidige coderings algoritmen overbodig maakt (En dus ook DPC)

[Anoniem: 27334]

zo zie je maar, Human Brains is tot nu toe de beste processor die er is

[Anoniem: 61698]

En hoe weet jij dat zo zeker?

Wie weet wonnen er ergens op een andere planeet wel huisdieren die slimmer zijn als wij. Met baasjes die nog veel slimmer zijn en die huisdieren maar stomme wezens vinden }

Maar goed even weet to the point of this topic

Ik weet zeker dat ik een programma kan schrijven dat de best haalbare score met tetris kan halen. Er moet dan alleen afgestapt worden van het hopeloos verouderen idee dat alles maar wiskundig opgelost moet worden.

Met de rekenkracht van de huidige computers kan gewoon ieder mogelijk spelverloop gesimuleerd worden en vervolgens kan met behulp van een beetje basis-school kansberekenen iederekeer de statistisch beste zet gedaan worden. P.S. wat ik hier zeg spreekt het artiekel maar voor een klein deel tegen.

Om weet terug te komen op dat brein van die human erectus . Onze hersent kunnen dan wel complex zijn, maar om iedere situatie te gaan simuleren zie ik ze nig niet doen ....... hi hi

[Sardia]

Ja, dolfijnen en witte muizen ;-)

Trouwens, de oplossing voor dit tetris probleem is 42.

[Anoniem: 62211]

daartegenover staat natuurlijk wel dat marvin (the paranoid android) dit binnen no-time zou hebben opgelost alleen zou hij het ook vertellen?

maar goed, 42 was ook niet het antwoord op het synthetiseren van een kopje thee

maar goed, ben wel benieuwd hoe goed dolfijnen zouden zijn in teris als het ze aan te leren was...

[Anoniem: 32714]

Heeft iemand Tetris al uitgespeeld?

[Rene59]

In die richting zat ik dus ook te denken.

Betekent dit bewijs nou dat Tetris niet tot in het oneindige vol te houden is, oftewel, dat je hoe dan ook (snel of langzaam) zal verliezen?

[Anoniem: 47648]

yeps

[a.prinsen]

Ik herriner me nog het oude spel Block-out. Dat was tetris van bovenaf en met 3D speelstukjes. Vraag me af hoe lastig dat is om voor een PC te verwerken

[Macros]

De bewoording is allemaal nogal jammer gekozen. Het had beter kunnen zijn: het is bewezen dat er geen efficient algoritme is dat het spel het beste speelt. Er is wel een algoritme maar dat is inefficient (daarom is het een NP-hard probleem)

[Ricochet]

Het gaat er niet om of het voor een pc moeilijk te verwerken is. Het gaat erom dat er simpelweg niet via een algoritme te bepalen is wat de meest efficiente manier van spelen is.

[T.T.]

Het gaat er niet om of het voor een pc moeilijk te verwerken is. Het gaat erom dat er simpelweg niet via een algoritme te bepalen is wat de meest efficiente manier van spelen is.

Dat is niet helemaal waar. In het algemeen kan van een NP-compleet probleem niet de optimale oplossing gevonden worden, maar voor kleine problemen kan dat natuurlijk wel.
Het belangrijkste punt wat mij echter opvalt is de zin:

So the next time you lose at either, take comfort in the fact that a computer may not have been able to do much better

Het mag dan onmogelijk zijn om de optimale oplossing te bepalen voor Tetris (vanwege zijn NP-complete eigenschappen), dat wil niet zeggen dat je geen algoritme kunt maken dat niet erg goede oplossingen kan genereren.
Je hebt meestal niet de beste oplossing nodig om te winnen, maar een goede oplossing (die voldoet aan bepaalde randvoorwaarden).

[jvo]

Even een kleine aanvulling.

Dat een probleem NP-compleet is wil niet zeggen dat er geen algoritme is die de optimale oplossing berekent. Het wil zeggen dat dit algoritme niet efficient is. Dit heeft te maken met de tijd dat het algoritme nodig heeft om een probleem op te lossen en het is inderdaad zo dat het kleine problemen nog steeds best snel op zou kunnen lossen. (Een klein probleem als een gewoon tetrisveld bijvoorbeeld)

[memphis]

Wat nou, de computer kan je al voorspellen wat het volgende blok moet gaan worden, vanaf dat moment dan de PC al goed rekenen lijkt mij
Het is gewoon de oppervlakte van de rijen afscannen waar het huidige blok eventueel in combinatie met het volgende blok het beste kan passen.

Met schaakprogramma's berekent de computer met elke zet ook de volgende mogelijke zetten, dat is denk ik zijn voordeel.

Maar de computer kan altijd met zichzelf cheaten

[0rbit]

Dat volgende blok heeft geen reet met de blokken die er al zijn te maken toch? Dat gaat gewoon random.

[violator_]

U snapt het niet helemaal, mr_atheist

Wat mempis zegt, klopt inderdaad, alleen spreek je dan niet meer van een algoritme maar van een functie oid schijnbaar.

Ik vinnet eerlijk gezegd nou ook niet echt heel bijzonder, wat deze 'wetenschappers' lopen te verkondigen.
Dat is toch bij de meeste puzzelspelletjes het geval.

[Anoniem: 61999]

Een freeware versie:
http://www.uwm.edu/~foxmj/glTetris3D.htm

[websurfman]

De games van tegenwoordig worden steeds groter, mooier en beter. Maar na verloop van tijd heb je de game opgelost en start je een dergelijk spel vrijwel nooit meer op.

Wat ik zo grappig vind aan spelletjes zoals tetris en minesweeper, is dat ik deze om de zoveel tijd weer ga spelen! ( totdat het weer mijn neus uitkomt! )

De levensloop is daarom best lang van dergelijke games volgens mij!

[HellPunk]

Groter en mooier, okay, maar beter? De houdbaarheid van de huidige spellen is zeer beperkt, een enkele uitzondering niet te na gelaten. Vroeger kampeerde ik maanden aan m'n PC met spellen als Civilization, Wolfenstein, Doom en Betrayal at Krondor en ik kon ze niet vaak genoeg herspelen. Tegenwoordig is het uitspelen en hop aan het volgende beginnen...

[Goodielover]

Dat komt omdat de uitdaging bij die spellen niet puur in jouw denkvermogen liggen. Als het wel daar zou liggen, maakt de presentatievorm niet veel uit.

Of je bijvoorbeeld een spel als schaken op een mooi gepresenteerd 3d bord op je pc ziet of je ziet een simpelle representatie met letters op een 8x8 zwart-wit hokjes veld, maakt voor het plezier niet uit. Het gaat om de intellectuele uitdaging die het spel je biedt.

[Anoniem: 53572]

Dit bewijst voor mij dan toch vooral dat het menselijk brein toch oneindig veel straffer is dan de nieuwste pc's. We functioneren trager maar o zo efficiënter.

[jvo]

Uh, niet dus. Je rekent met je hersenen niet de optimale oplossing uit. Alleen een goede oplossing en dat kan de PC echt veel sneller, geloof me

[Anoniem: 52829]

mwao toch werkt volgens mij de techniek het best door de rijen zo klaag mogelijk te houden en snel rijen te scoren, zo verminder je de kans dat als je een fout maakt deze je ook de das om doet, iets wat eerder gebeurt als je 4 x zo hoog zit

[Anoniem: 63091]

En als er iemand is die dat probleem kan oplossen...

http://www.claymath.org/prizeproblems/pvsnp.htm

dan kun je er nog goed aan verdienen ook!

Off-topic?! Ik denk toch dat de link die ik hier post absoluut relevant is voor deze draad...

[Anoniem: 62211]

[off-topic]
ik kan het mis hebben, maar als je begint met de 1e 100 mensen (waarmee het gebrekkige aantal atomen van het universum omzeild is) en zodra je een paar tegenkomt dat niet mag voorkomen schrap je 1 van de 2 en voeg je er de eerstvolgende op de lijst bij. na de eerste run-over doe je 1 voor 1 de mensen erin die je in de eerst runover eruit gehaald hebt en haal je hun tegenhanger eruit... volgens mij heb je dan zo een goeie oplossing.
alleen voor alle mogelijk oplossingen zal je wel een aantal (statistiek is te lang geleden, en ben lui maar geloof dat het iets met 400! en 100! moet zijn) keer deze algoritme moeten doorlopen...

een andere aanpak is om te beginnen met de namen te schrappen die het vaakst in de paren voorkomen, maar dat biedt niet voor 100% zekerheid

[Anoniem: 66786]

Zo zie je maar weer, dat het beste en meest verslavende spel ooit nog beter is geworden. Je kunt zelfs niet berekenen hoe je de stenen neer moet zetten. Dat zegt toch wel weer iets over de uitvinder, die zal nou trouwens wel zwemmen in het geld...

[Mayco]

dus als je goed in tetris bent, ben je dan een wiskundig genie?
* 786562 Mayco