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)
But can it play DooM?
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.
If they overcame the Clumsy-Ass Thumbs problem, this thing'll kick all our asses at 2-player! :)
You are not the customer.
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.
Sure would be easier to write an AI for an Open Source Tetris implementation.
But if it's not ridiculously convoluted, converted to analog and back to digital data along the way, and (relatively) expensive, it's not fun, right?
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.
The future is facing us now!, i dont think i could take an AIRCUH (AI remote controlled undetectable hack) for Counter Strike, life wont have a meaning anymore, damn hax0rs.
Sigs are for morons... Wait a minute...
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
it would be about 30 times faster to make the code IN the game, instead of using a webcam and relays and stuff... but still, a very cool project indeed.
My potato gun was confiscated by the United Nations. They said I wasn't allowed to have weapons of mash destruction.
"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.
that site is a true hack, with a complete analysis of tetris and its clone... good job
Jon Bardin
... 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.
getSexySig();
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
What I want is a multiplayer Tetris where I view the game from the tile's point of view. "You are looking down a deep chute, falling towards an irregular field of colored squares ...."
-kgj
Tetris visual perception and AI decision making
Stage 3:
PROFIT!
perl -e 'print $i=pack(c5, (41*2), sqrt(7056), (unpack(c,H)-2), oct(115), 10)'
I dont think so. Just a lot of caculations. Its not like its trying to guess what move a human is going to do next then place a piece. This is nothing more than caculating the best possible placement of an object from a limited set of objects. Card counters do this thing all the time and so do machines. Why this even made any type of news outside of it being mildly unique befuddles me.
Mod me to troll of you like but this is not AI.
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.
I'm no expert, but re: your sig, I think Boromir was son of the Denethor II, Steward of Gondor. Faramir was Boromir's brother. Neither Boromir, Faramir, nor Denethor were ever Kings of Gondor. Just an observation.
sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it.
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...
I have one of those, it's called my friend DJ!
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.
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.
Now if you really want to play tetris, but can't be bothered, here's your system!
Why though??!??!?!?!?!
Tetris is about using your brain to figure out everything... Is this "Tetris for dummies" ?
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.
Nerds!
/me kisses his karma goodbye
Nerds nerds nerds!!!
...people will boast about how many days their AI has been playing without loosing, instead of their box's uptime.
We actually need them in this article!!
You slashdotters posted ZERO comments when the business partner of the creator of tetris died.
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
You've probably always wanted a system that reads a Tetris game via a webcam
Yes.
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
... In Soviet Russia! =)
or is it, in Soviet Russia, Tetris plays you?
no, the KGB playes you in Soviet Russia...
hmm...
This is my sig. Its pathetic.
Prolog solution to find if any give pack of cards is solvable - but I thought that this, too, was NP-Hard... grrr
... 1000 monkies writing Shakespeare etc. - He wishes!
I can well imagine a Prof. giving us some of his research to solve
Don't know why it didn't occur to me at the time but you could just do screen caps and write your recognition software based on that. Question is can you screen cap and make decisions fast enough.
I'm the big fish in the big pond bitch.
Yup, that's what I have in mind!
-kgj
unfortunately, their website sucks badly. May be they need some help building one. That was a really fabulous place to work at, with scores of smart people.
Please tell me more. It was an interesting post.
If you read the slashbox, it says:
Therefore, he original poster is precisely correct. Good attempt to discredit, though.
Seriously though, this makes me want to get back to the good ol' days of making cool projects for EE classes.
The parent might be off-topic, but how can the /. crowd take someone with such a sig seriously?
Ah, the spastic utterings of a former tetris champ, angry at having spent hundreds of youthful hours becoming good at something only to be made redundant.
Note "two-handed home row" mapping of game controls, once thought to be optimal (oh! the irony). This one was good. For a human.
Go with our sympathies, brave filler of lines.
ok, ok, so he probably just forgot that it was a Plus or an SE...
But one part sounded a bit wrong to me. I may be wrong myself, but...
I don't know if thats accurate. I mean, Pajitnov (and the other guy) was in the Soviet Union,[1] after all. I don't know if "selling" computer games would have been so easy. I thought it went that the game was written and then handed around the "Computer Center of the Russian Academy of Sciences." Then it got past the Iron Curtain, and then was distributed as freeware for a while until big companies (Microsoft, Nintendo) realized that they could make big bucks releasing a legal version of the game.--
[1] In SOVIET RUSSIA, Robot controls Tetris! [2]
[2] Shut up. It was revalent. Now, if I had said the Simpsons quote: "In Soviet Russia, stage for actors only!" It would not have been.
"Never attribute to malice that which can be adequately explained by stupidity." -- Hanlon's Razor
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!
First I lose my programming job to some starving dweeb in India.
Now my "filler" brick-laying job is being replaced by a web-cam.
Even McD's is having financial troubles and closing stores.
Well at least that janitorial job at Sadam's Presidential Palace is still open....
Table-ized A.I.
yet I'm so jealous.
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
The same guy is now retrofitting his contraption by pointing his webcam at his wife, and having Leisure Suit Larry's AI instruct him how to seduce her.
Fortunately, for the gene pool, he's finding that this problem has no solution, but mostly due to personal limitations.
This is a really cool (and must've been fun) project! Very impressive!
One really cool thing would be if the program were capable of looking at the entire screen (not just the middle of the top two rows) and identify the falling object as well as identify the stacked area and shape it needs to conform the falling piece to (instead of relying on it's flawless memory.)
near the end of the page there's a shot of the camera looking at his tetris game. when looking at it the wallpaper caught my eye, so i immediately wondered where i can get my own like that. upon closer inspection, i realized there was no wallpaper at all, but THE ENTIRE DESKTOP WAS COVERED IN ICONS!
no, not half the screen, not just the borders, not even an obnoxiously gross amount, but the whole screen! what could drive a person so mad? hasn't anyone ever shown this guy what a 'folder' is?
maybe he flunked too many classes, he never figured out how to write an algorithm to make desktops. holy icons batman, my eye wanders.
What's with all the rubber bands on the relay board?
All he needs to do now is to hook it up to a tetrinet session.
I've been searching for a way to be able to have screen movies in linux. Not just screen shots.
Such a way would make this engineers team much easier.
But I think that given the simple nature of this tetris game, that you could have actually relied on the "import" (part of imagemagick) command to accomplish this.
So...tetris dorks--
-- -- --
Help my mini cause: My journal
...don't you see it! then Skynetbecomes self-aware!
I don't care about the webcam: it can directly read memory video, or take snapshots of windows and then parse the pixel matrix. But I want good pattern recognition, possibly learning by examples, automatic control over mouse keybord and a way to define/intercept game events.And of course a programming language to glue all toghether.
Ciao
----
FB
Ah, but you see THIS time, there's an answer!
Stage 2: Play tetris for money
I hear they have a very harsh anti-cheating policy there (i.e. they'll freeze all the money in your account and ban you if they even suspect you of cheating) but hey, it's still tetris for money.
nlh
Ferrari and other exotic car rentals in New York
I have. That original DOS Tetris used different coloured spaces. I played it on a Hercules monitor. I wrote a TSR to intercept int 10 and replace spaces with characters. I cheated. I put an extra delay in to every one too. P.S. I lied this time too. But hey, -32K isn't too bad!
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!
record attempt
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);
how far someone will go to cheat at tetrinet
I agree that some of my comment was received as being vague. I understand it is vague and would've only been received as being vague had you not actually understood my concept. And so I explain:
Programmers are all trying to re-invent a form of (pseudo) artificial intelligence that is oultined specifically for their application. The idea I propose(d) is for a distributed artificial intelligence network for all software to interact upon via data links. I agree I may yet not be understandable at this point, so I continue...
Rather than build an AI specifically for your software, programmers *should* plan on builing their software to interact with a general AI that is not application-specific in its implementation. To understand this, you must have experience with programming and look at "AI" as a network-oriented service. AI, as a service that can be re-enterant to other applications as well as contribute to its own entropy to improve (think of it as learning) its operation.
Now, you are either a 1) naturally-born sentient individual human being (like me), 2) a gorilla that was taught chinese or sign language and will sooner-or-later ask me for a bannana, or 3) a simulated sentient human being capable of responding to abstracted stimulus through the FORM layout on slashdot's forums.
What are you and can you be a re-usable software interface (cloned) to interact with other human beings as a distributed application service? Are you planning on being maried to Alice(Bot)? I thought so...
But I'm sure you already Gnu that.
I've been pondering creating a programmable video game controller for a while now. Basically, what I want is a computer program running on a PC that can control a video game console as a standard joystick. I'm envisioning a daemon that runs and just sends the appropriate button-pressed command out whenever it receives data packets. This could be used both for AI/Vision-type situations like this, or as a simple programmable pad (you could, for example, write a program that outputs a certain string of button-presses whenever a keyboard key is pressed; useful for fighting games.)
:)
My roommate already has (basically) a universal arcade stick that he made himself -- has interfaces for connecting to PCs, Sega Dreamcast, Playstation, PS2, Nintendo 64, etc. I figure all I need is a way of controlling the device by basically pressing switches.
My problem is that I don't know any way of doing this cheaply (the piece of hardware used by the guy in this story is over $100). I was thinking of maybe using the parallel port, which has 8 data lines, but that's not enough lines for newer systems and I'm not sure it would work anyways.
Does anyone have any ideas on how this might be achieved? It's kinda coincidental that this article popped up today since I just thought about this for the first time in months earlier today.
... what would happen if you moved the camera a bit while it is playing. Would that take 'I' out of 'AI'?
Respect the nerds!
;-)
I can say that, i think. I connected my tv's on/off to the rs232 of my computer.
Why? Ths choise was simple. I had no remote on my tv, so this was a practical solition
Privacy is terrorism.
I saw a Japanese guy is also trying to do similar things, called VArashi, an automated solver of PuyoPuyo (tetris like puzzle game, which is very popular in Japan) in Ruby language. See http://varashi.jp/. They were doing demos in LinuxExpo right now.
Hey that's not bad.
From what I got outa that, a computer hosts a virtual entity, lets say Jerry Rice for example, and Jerry Rice can interact with its(or his, if that trait applies to software) pre-defined characteristics onto any game that accepts him as the computer/AI-player? And he(the AI::Jerry_Rice I mean) improves (its/him)self? That rocks! Maybe "You don't know jack about football" just might be a better game in the future! And soon Bo Jackson can be {hosted} and everyone knows "Bo don't know chess" and I'll teach that brute howto be a loser on chess! All the while it is a hosted virtual entity that improves itself some how. I want to play Battlefield-1942 alongside or against George Patton or Rommel! Or Doom2 against John Romero!
ROFLMFAO!
Mod the grandparent down!
If you consider "win" to be "never lose, no matter how long you go," then you can't assume that you won't at some point run into a certain combination of pieces, because then you are winning only until you hit those pieces, not for as long as you play. No matter how long you go without hitting those pieces, there's always the chance that you will eventually hit them, which means that your strategy is not a guaranteed win. If there is no strategy that's a guaranteed non-loss (for ANY sequence of pieces, not just most of them), then the game can't be "beaten." There is nothing else to prove.
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"?
The random number generator has 32 bits of entropy. You get the number mod 7~=2^3 so after 11 blocks or so (11*3=33), you can uniquely determine the internal state of the RNG. After that, you know every block that will drop; at that point, you no longer need significant video processing, and can devote all the processing to working out where to put the next piece.
Geez, do you think this guy has enough desktop icons? Clearly he spends too much time on his hobbies!
Do, vi estis la homo kun la malodora fisxo! Via skemo ne povas esti sukcesa.
Well... tetris isn't hard to play, it might be hard to solve (i'm not a mathemetician so i can't tell you for sure) but i am a programer. Not a very good one (i'm still in college) but i did write my own little tetris agent.
.exe to try it out.
I used a very simple algorithim, not really even using any advanced AI techniques, but it plays fairly well. Actually i can't tell you about how good it is, because it plays so well it now takes several hours to play through a single game (even with no graphics). From the best i can estimate, it plays at least 200,000 lines a good majority of the time. I've recorded a game over 600,000 lines, and that wasn't even the max, i had to stop it. That's probably more lines in one game than most tetris players even come close to in a lifetime. If anyone's interested i can put a link to the
The Infinite Monkeys factoid (An infinite number of monkeys typing randomly on typewriters would eventually produce a copy of Hamlet (at least that's how I originally heard it)) is a gross understatement.
Given that Monkeys would take a fixed amount of time per keystroke (one second, for example), and that Hamlet is N characters long, you would get an *infinite* number of copies of Hamlet at exactly the N second mark, and an infinite number of copies again *each second* thereafter.
But these monkeys would certainly not be limited to Hamlet... you would also get infinite copies of every edition of every thing that has ever or *could* ever be written down.
My brain hurts.
Stupid evil monkeys.
Keep your Eye on the Ball,
Your Shoulder to the Wheel,
Your Nose to the Grindstone,
Your Feet on the Ground,
Your Head on your Shoulders.
Now... try to get something DONE!
- this post brought to you by the Automated Last Post Generator...