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.

Comments

Oh but...

[RPoet]

I thought Tetris was NP-hard ;)

Re:Oh but...

[Atrahasis]

Just because there is no ideal solution does not mean there is no way an AI-agent can do it.

Re:Oh but...

[Minna Kirai]

Most all school projects are "extra work", since students can rarely forge new ground that hasn't been investigated before. Instead, they learn to correctly duplicate known experiments, to get up to SOTA before following their own ideas.

In this case, the machine-vision problem of recognizing blocks with a camera (which inserts distortion and uncertainty to the image) is an interesting challenge on its own.

While viewing a computer screen is easier than most MV problems (the target is self-illuminated, so variable lightsource angles are less of a problem), it could have useful future applications. Especially if someday we're beset by hardened DRM computers that don't allow you to interact programatically- mouse input and LCD output only!
Then the practice of watching a screen with the camera of your PDA might become the only way to take controlled files off those machines.

(Watch the "Ghost in the Shell" movie for bizarre examples of this)

amazing

[Boromir son of Faram]

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.

Re:amazing

[BitHive]

A Doom-playing version of this system would probably require AI-complete machine vision, and sniping on eBay (not to mention document reformatting and data entry) is better accomplished with, say, a Perl script. While this is a cool little project, the piece detection has a pretty narrow range of operation wrt to contrast and flicker, and in no way is extensible enough to be a "universal, playform-independent macro system".

Robotic

[Rosonowski]

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.

Next generation of cheats

[natslovR]

Once secure computing hits town, this will be the next generation of cheats.

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.

The begining...

[Washizu]

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.

Artificial Intelligence

[AnonymousCowheard]

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?

I am not as impressed...

[Conspiracy_Of_Doves]

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.

Re:AI?

[BillFarber]

>> Just a lot of caculations Thus far, that is all AI. In fact, the vast majority of AI today is simply some variation of a search tree looking for the best choice.

Recognition is key... to card counting

[unfortunateson]

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?

Re:Tetris AI Madness

[Anonymous Coward]

There was a rather malevolent tetris variant out there a few years back called Birdris-- instead of randomly selecting a piece, it would analyze your current stack and give you the worst possible piece-- sadly, I haven't been able to find it in years.

I seem to recall that the record score was 12 lines.

Anyone tried a programmable game controller?

[Falkkin]

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. :)

Re:Anyone tried a programmable game controller?

[Chris Canfield]

There are lots of ways that you could make a computer-controlled controller... Not all of them cheap. You could, for example, dedicate a section of the screen to I/O, and use a series of photogates to open / close the bridge across the controller pads. You don't get analog sensitivity, but it works. I was sketching out ideas for ways of recording to standard audio tape, using pitch in and pitch out filters for the line... or a simple big-ass array of tape decks connected together by common buttons. This would allow for playback of controller imputs, which would be a boon to testing.

However, I'm not so sure that simple playback of keyboard combinations would be good for anything but leveling. The dedicated programmable pads in vogue several years back were quite gimmocky, and was less responsive than was acceptable for fighting games at the time. Since then, fighters have gotten significantly faster, and even more picky about timing issues. It's easier just to imput the gamepad commands yourself.

This is not to say that programmable controllers don't have their place... a programmable controller took my Castlevania: SOTN character to level 92 in just under a week. Programmable controllers continue to exist, and can had for a reasonable amount of money.

But the problem with visual recognition on modern 3d games is staggering... MIT has entire departments devoted to similar topics. You might be able to do it if you could convince the game to output stereoscopic images, (there was an article recently on a stereoscopic voxel technology), but a subsection of this sort of problem is what you would write your doctorate on. If you can get your hands on the base textures for the game, and redo the graphics engine to give depth and object clues along color lines, you could do it. But not as it stands, and not to a remote box.

But a little controller hacking is always fun. Good luck!

Re:AI?

[sholden]

AI is merely working on a problem that has no known solution (in reasonable time). As soon as the problem becomes 'easy' and solved it's no longer AI and becomes a mere algorithm...

So once natural language processing becomes 'easy' it won't be AI any more, but will be just another algorithm.

At least that's what my AI lecturer used to claim :)

Wait a minute, something doesn't look right!

[Flakeloaf]

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.