Slashdot Mirror
Tetris AI System
You've probably always wanted a system that reads a Tetris game via a webcam, decides the optimum move, and then inputs the commands to make that move, right? Well, now your prayers are answered.
← Back to Stories (view on slashdot.org)
Being NP-hard means there are no existing polynomial-time algorithms to find the *optimal* solution. That doesn't mean it is impossible to write a program that can find *good* solutions. Moreover, NP-Hard problems get really impossible for higher instances. For small instances of NP-Hard problems, brute force search is still feasible.
Another point is that the article you mentioned discusses a restricted version of Tetris.
getSexySig();
Great post.
No Microsoft bashing, no debates about IP, distributions, no whining.
Serious, hard-core, geek shit.
Geek takes computer, does something incredible, writes up an wonderful web page, perfect.
Actually, I think Tetris has been proven to be impossible to win (where "win" is defined as being able to play forever). There's a research paper that explains why.
I read the internet for the articles.
That arguement doesn't *prove* that it's impossible, because that arguement hinges on there being a long series of only S and Z pieces. The only way you could prove that that issue would always cause a loss is if you could prove that an impossible to place series _necessarily must_ occur. Unfortunately, because the piece order is by definition random, you can only say that it is very likely that an impossible to place piece order would occur eventually, not that it must occurr. Therefore, a perfect game of Tetris could be played (based on this problem alone; there may be others), but success is not entirely based on the skill of the player!
That's a very interesting result to say the least! Well I guess it's interesting if you're a math geek like myself at least......
Ben
If you watch the video linked on the site, you'll notice that the computer has the tendency to leave a long empty row on the side(s), just like pretty much every human player I've encountered. Seems like that temptation transgresses all boundaries. ...
Damn skinny pieces. Always my downfall.
if(!toilet_paper) roll.replace(new roll);