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)
I thought Tetris was NP-hard ;)
"Oppression and harassment is a small price to pay to live in the land of the free." -- Montgomery Burns.
1. A robot may not injure a human being, or, through inaction, allow a human being to come to harm.
2. A robot must obey the orders given it by human beings except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.
4. A robot must never place the long skinny ones horizontally, unless it leads to a long skinny vertical hole so 4 rows can be cleared at once the next time a long skinny one comes around.
I'm much funnier now that I'm a subscriber.
Now THAT's some serious nerding...too bad a feat like this does nothing to impress the ladies
Now if they would just adapt this to playing Solitare, I'd never have to come to work again! The computer could do my "job" for me.
That is until he beats you 27 times in a row and you throw your controller at his camera-head and cause him to crash.
Someone get this guy a Desktop Cleanup Wizard!. And I thought I had too many icons on my desktop...
The speed of time is one second per second.
This could be generalized into a system that completely replaces a computer user in any context, not just Tetris. Someone's already mentioned a Doom player, but you could do the same thing with Ebay auctions (the Ultimate Sniper?) or tedious reformatting in a word process, data entry.
It's all just recognizing an on-screen situation and responding to it with key presses and mouse movements. Best of all, it doesn't rely on application developers to build scripting into their programs. It's a universal, platform-independent macro system.
My people could put such a power to heroic use.
Boromir, son of Faramir, King of Gondor and Minas Tirith
"Holy Crap!!! You mean I don't ever have to think again! Sweeeet!!"
see the new shape of fear this summer 2004
Of course, you're also telling me to pick up a halibut and run through the workplace smacking coworkers upside the head as way of instructing them in Esperanto. I think I'll try and ignore those instructions, this time.
... but, quite frankly, I'm more impressed that his page with 1.22MB of data sent per hit is still loading fine after an old-fashioned Slashdotting!
*nix.org - Featuring BSD, Linux, OS X, Solaris, & More
Reply or e-mail; don't vaguely moderate. Ex-O'Reilly/MIT employee, now a full-time Google employee.
I've seen a lot of people commenting on how this would be easier if it all stayed digital, but upon seeing the diagram he had, the first thing that came to mind was pattern recognition, perhaps in use for robots.
This is the kind of thing that people spend a lot of money on, and even if it is kind of crude, visual sensors combined with logic that works is a Good Thing(tm) indeed.
01101001 01100001 01101101 01101110 01101111 01110100 01100001 01101100 01100001 01110111 01111001 01100101 01110010
It may be cute seeing a second computer play Tetris now, but so was the first time someone had a bot improve their aiming in Quake.
I've read speculation before that equipment like this would probably eventually be used to cheat on systems like Xbox Live - It's a bit too soon for that, but in the years to come this could very well be the way cheating is done.
There's a difference between being able to play well and solve the game. If you read the article, the machine was able to complete about 600 rows per game. (Which is pretty damn impressive!)
I'm not really sure how you'd use Tetris to prove P=NP, but it probably has something to do with making an AI that could play forever and never lose, and further be able to prove that you could never lose, which is probably even harder than making the AI!
Thank you! Thank you! Thank you!
Making trouble today for a better tomorrow...
People here have already speculated about the possibilites of an ebay sniping, Doom playing machine. Think about the Man vs AI possibilities. Imagine playing your favorite FPS (Quake, Unreal, Counter Strike, Battlefield 1942) and being hunted by a squad of these machines. Unlike in game bots, they're subject to the same limitations you are (lag, poor visibility on screen, the strength of their hardware). If you have to ditch them, run into a cave or turn out the lights. Given an equal interface the struggle between a thinking man and a thinking machine would be a lot more interesting.
OddManIn: A Game of guns and game theory.
your light has gone out...
;beer;
if you move downward any fartheryou will be eaten by a grue
you were eaten by a grue, please try again.
(yes, mod me down, but it's still damn funny!)
There is no such thing as modern AI. To be accurate, AI is the ability to learn; not the pre-set ability to react in an environment it was programmed for. For this "Tetris AI System" to be considered "AI", it would need to adapt to more than just Tetris; such as Duke Nukem3D.
Whoever wrote the artificial intelligence algorithms for 3DRealms' Duke Nukem3D multiplayer-mode "Fake Duke" deserves more recognition than anyone.
Those of you, like me, that were stranded to play by yourself and had no internetwork-ed access to deathmatch with others, know what I am talking about in Duke Nukem3D. How it worked was the game simulated a multiplayer game and was pre-set to "spawn" fake players. The AI system was in effect actually more "unforgiving" than say Unreal Tournament or Quake3. The "Fake Duke" was intelligent to hunt you down based on line-of-sight and quite naturally if he had to run through a laser beam or a lava pit he'll do it all while keeping his "+" (cross-hairs) painted on the center of your forehead. The AI was limited and I think a more accurate project for AI would be to actually host an AI service that offered network-accessed primitives for supreme entropy to contribute to a work of data; such centralized AI system would allow gamers as well as scientific computing to benefit from a verry good entropy pool of numbers as well as improve the funfactor of gaming.
Instead of this, we have many skilled people having to roll-their-own; not implying they are effectivly wasint their time/resources, yet let's keep our eyes on the prize on what a real system of "sharing" (distributed) can do for the many simulations upon computers that can benefit by a shared resource (thinking AI and entropy) as well as contribute to a centralized AI generator. I know SETI would benefit from such a noble cause, rather having to role-their-own client (software) and have their client (software) wastfully "leech" idle resources of computers around the world. It comes to that conclusion of efficiency, in a sense. Perhaps distributed computing across the internet is a real plan that would benefit from being re-thought. Don't let me fool you: Microsoft is attempting this feat; maybe someone has already started working on this! Doh! Someone recognize the inherent corruption that can ensue if a corrupt organization was holding licenses for your obligation to use their distributed resources as being a client for an applications service provider!
Am I the only one to confirm these truths or forever does everyone hold their peace?
But I'm sure you already Gnu that.
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.
We actually need them in this article!!
The laws of Physics?
Never mind. It may not be that great of an idea
"You are looking down a deep chute, falling towards an irregular field of colored squares ...."
Is 3D Block for NES, 3D Tetris for Virtual Boy, or Geom Cube for PS1 close enough to what you want?
Will I retire or break 10K?
I am not as impressed with the AI's ability to make decisions about what to do in the game as I am with its ability to dicern the shapes and locations of the pieces on the screen! Now THAT is cool.
Technoli
Very, very impressive.
If I may humbly suggest a few design improvements as you continue to develop the item:
1) Remove the electrical connections, and have it physically press the keys of the keyboard with a robotic arm of some sort.
2) Make it mobile, so it could, for instance, go in search of a tetris game, if it gets bored.
3) If it sees a tetris game being played, but doesn't have access to the keyboard, it can verbally (with synthesis) tell the player what to do. "left! left! rotate! rotate! drop!"
4) Trash talking. "I can't believe you dropped that there! What are you -- a carbon-based unit? go back to playing pong, you binary digit."
4) Global Thermonuclear War.
Software Wars
There's two types of AI, practical AI, and a sentient type (or one that pretends to be sentient I guess).
"Practical" AI is having a piece of machinery that has been programmed to take a limited set of input, perform some action, then repeat to infinity. The robots that manufacture cars do this, and this tetris bot does this.
"Sentient" AI is probably more what you're talking about. It handles language processing, making inferences, stuff like that.
It is intelligent in that it can do a task without human interaction, so yes it qualifies as "AI".
If this robot can respond to Tetris' higher levels at reasonable speed, then the next project ought to be a glasses-mounted camera with bluetooth to an iPod-camoflaged CPU that can count cards at Blackjack.
A wide-angle lens ought to be able to pick up the whole table. Watching cards being laid down is relatively easy -- surely no harder than seeing pieces fall down the screen. Then just ID the cards, keep a running total, and put a piezo buzzer in the glasses' arms to let you know when to bet big and when to get the heck out of there.
Maybe a camera in the rear also, to spot pit bosses?
Design for Use, not Construction!
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
When I saw the title, I thought they finally revealed that Tetris has a massively advanced and evil AI designed to frustrate the player. It analyses your gameplay and knows exactly what pieces you want and don't want...
Even my tinfoil hat can't stop it from reading my mind.
Prescriptive grammar:linguistics
The problem isn't so much how to count cards -- it's how to count them without letting your betting patterns get noticed. Presumably you're spending money and time on a card-counting hardware/software system with the intention of using it semi-regularly, so this is an important consideration if you want to win more than a few dollars here and there without getting attention from the eyes above and the eyes on the floor.
Let's say you're using a well-established counting method like hi-lo, or something like it of your own devising. Given that this is Slashdot, the latter is probably more likely, regardless of whether or not it's actually any better.
So whatever your system is, you have a hot shoe at this table. Your computer is buzzing your arm or shocking your ass or whatever it does to get your attention, and you want to abruptly drop a set of big bets to cash in on the improved but fleeting odds your computer has identified. You're going to get some unwanted attention if over the course of a few hours you "randomly" drop a big pile of chips in the center of the table a bunch of times. Particularly when you keep jerking up from the table as if you've been shocked in the ass.
That is, unless your system has some method of wager management that lets you blend in while reacting quickly to good odds. That seems pretty tough.
Maybe the computer could establish what appears to the casual observer/dealer as an idiotic, repeating pattern of wager quantities, thereby identifying you to all around as a grade-A moron and eliminating alarm when you change your betting quantities abruptly. Many easily recognized patterns would suffice. By changing these patterns in only moderate ways, it could be possible to eke out smaller but still positive expected returns than in elementary, obvious-to-keen-eyes card counting. You'd have to stick around the tables for a long time, though, to take advantage of a razor-thin advantage.
Oh, wait, that's how I do it. Albeit without computer assistance or the anal probe. So I guess I shouldn't have posted this.
Anyway, good luck building the glasses!
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);
Check out the very end of the movie. With 29 seconds gone in the AVI file, there is an L-shaped piece ready to go. The AI decides to rotate it once clockwise and drop it on the far right, eliminating three lines.
The only problem is the red square is in the way. There's no way you can drop that piece into that space and make three lines disappear. Something's fishy.
What I'm talking about is illustrated here.
Am I the only one who heard Roxette to sing "I'm gonna get blitzed for some sex"?