First place in Tetris 99 using computer vision, classical AI, a lot of free time

https://bpinzone.github.io/TetrisAI/

by sschul • 1 year ago

65 46 1 year ago

bpinzone.github.io

excalibur• 1 year ago

Welp there it is, I've been replaced by AI.

MisterTea• 1 year ago

Relax, it's not an AI. Instead, you were replaced by a depth first search algo.

Kapura• 1 year ago

I am not impressed that a computer can beat a human at a computer game. i am more pissed that i may have been playing tetris 99 against unbeatable ai.

HenryBemis• 1 year ago

Especially for a game like tetris that has a limited (many but finite) options, it comes down to how fast is the eye-hand coordination/reflexes. "The Flash" should have no point beating the game for that very reason.

ultimafan• 1 year ago

100%, can we not normalize this kind of thing in multiplayer games played by humans?

My friends and I have quit a number of multiplayer computer games when they've become infested with cheaters and developers couldn't or wouldn't keep up with the arms race of banning them. This is really not that different from someone writing and using an aimbot in a public lobby for a shooter.

If you're going to be writing and testing cheats or AI or bots do it in single player games or private multiplayer lobbies so normal players aren't affected.

GuB-42• 1 year ago

It is not unbeatable. The author says it doesn't always get first place, far from it, and the video is one if its best games. He deliberately stopped working on the project before it would become unbeatable by a human.

dankwizard• 1 year ago

Even if it isn't winning, I'm choosing multiplayer to play against others. If I wanted to verse machine code, I'd play single player.

gildas2• 1 year ago

No T-spins [1], impressive!

[1] https://harddrop.com/wiki/T-Spin_Guide

charlieyu1• 1 year ago

No T-spins, disappointed.

It looks like the bot just beat humans because they react faster

gildas2• 1 year ago

I must admit I'm a little disappointed that the bot isn't able to do this. It would be much more efficient.

foobaw• 1 year ago

yes but this aligns with the initial statement in the post that top 1 doesn't happen as much and top 15 is more common.

tobyhinloopen2• 1 year ago

Alternative title: How I cheated in an online multiplayer game.

mizzao• 1 year ago

TK that needs updating:

mention graph search for vision correction? https://github.com/bpinzone/TetrisAI/blob/master/tetris_ai_e... do we still use this?

soganess2• 1 year ago

This is really cool! Plus I like the ramification that the 'hard bits' of playing a game like tetris might be contained in the vision/recognition phase.

My only gotcha is with calling DFS 'classical AI'. I get they have a fancy hand-tuned cost function, but if that is AI, then I guess all approximate optimization algorithms are AI? Maybe in 60s that kinda of classification would have been fine, but not now, right?

Either way, that is a minor nerd-gripe with the messaging and does not, at all, detract from an otherwise rad project.

Retric• 1 year ago

Maybe in 60s that kinda of classification would have been fine, but not now, right?

Thus classical, as a reference to the idea that:

As Soon As It Works, No One Calls It AI Anymore: https://quoteinvestigator.com/2024/06/20/not-ai/

It’s kind of surprising to me we still call feedforward neural networks AI.

soganess2• 1 year ago

I can totally see where you are coming from and I like the wink and nod to the article!

I guess...hrm... if someone asked me what classical AI was today... I would answer with something like A*, decision trees, or Markov model-style algorithms (but never DFS). All of these have 'worked' for a long time but still feel like classical (ie no back-prop) AI.

To your second point, I'd be the first to admit I'm no expert (I don't do any ML professionally). In my limited understanding, it feels odd to separate MLPs from 'modern' AI. It's all still back-prop, yeah? I get that universal approximators and (idealized) Turing machine approximators like LSTMs are old hat. But Attention-based (key, value) query models just seem like the next step on the same ladder of "increasingly complex computing paradigms we've figured out a way to back-prop through." Not something uniquely separate. First, we could do functions, then we could do Turing machines, and now we can do data queries.

But again, I'm probably just showing how green I am. I would, time permitting, honestly appreciate clarification/correction.

robertclaus• 1 year ago

A bit into the article I reframed "AI" to mean "bot".

minimaxir• 1 year ago

Given the computer vision approach, I'm surprised they didn't try different themes other than the Fire Emblem: Three Houses theme. There are many other themes for Tetris 99 with likely better visual clarity for the tetriminos.

speff2• 1 year ago

I read the article, but I didn't find a reason as to why they picked the multiplayer Tetris game as opposed to the myriad of singleplayer ones. I think this is a neat beginner project, but can't help but think of the handful of times I tried T99 just to quickly quit again because I got stomped on every time.

How much unnecessary frustration was caused by testing this out in prod? I know they said they only got a handful of wins, but how many people did it knock out over the course of testing it?

Waterluvian• 1 year ago

Feels like feeling slighted by a drop of rain in a storm.

speff2• 1 year ago

Your point's not lost on me, but if you allow me to modify the analogy to: Feels like feeling slighted by a water hose in a storm. I think that's more accurate. Yea I'm still drenched, but it would feel (irrationally) worse if someone sprayed me in the rain

chefandy• 1 year ago

It’s weird that caring about people impacted by the training of a hobby NN model feels anachronistic. Well those people were ALL the way at the other end of the internet tube, and it was only a game so their time doesn’t really matter, and think about how many people “weren’t” impacted!

It seems like tech has gotten so dang self-absorbed.

hsisfullofbots2• 1 year ago

The only positive thing we can say is that the bot appears to be - at best - slightly above average with Tetris 99 compared to an average human. Which makes it pathetic at this task considering it is a bot and should have near perfection with minimal effort. One extra slightly above human has little impact in the game honestly.

They don't do T-spins. They don't stack large attacks for KO's, or even seems to alter targets under any condition at all even. The targeting reticule is hard stuck on attackers with zero input put into it. So it has no overarching strategy besides survival, but even then, it doesn't try to play the badge stealth game either - backstabbing a leading player is the leading method of making comebacks, and necessary ones too. Which is why it reliably gets in the top 15 and then loses, you can not outfire someone without badges, there ARE one-shots in Tetris 99, the bot probably only won when it lucked out early on in being the leader of the pack and then fed on a crowd of people with targetting set to "badges" (there's a firepower multiplier when targeted by many people).

Which is... kinda pathetic reading into when I'm someone who reliably got top 3 outside of the Invictus mode. I think the creator might have 0 idea of what defines Tetris 99 at all. Like, straight up no awareness whatsoever. They're bad at this game, and thus, made a bot equally bad and only wins with luck.

It's just playing normal Tetris. It literally has no reason to do this against humans, does nothing with the human element. So it'll beat other clueless humans and then lose to the actually good humans. Between those two human groups, they're just one more in a sea of typical indistinguishable threats and fodder.

Good on the creator for stopping before making something more competent.

sschul• 1 year ago

Thanks for your critique of the project.

Initially, we chose Tetris 99 because that was the context in which we had the idea. I won't deny, though, that being able to compare Jeff's performance with human players and see his interactions and victories in the Tetris 99 environment made the project more interesting for us; however, it was wrong to do so in a public setting where the players didn't know that our algorithm was involved and didn't opt in to playing against it.

We're no longer testing or developing Jeff, and if I do any similar future projects I'll choose singleplayer games or private environments where opponents voluntarily test their skills against the bot.

taskforcegemini• 1 year ago

thank you for reconsidering. online games are ruined by bots left and right.

free_bip• 1 year ago

Hopefully the author gets banned from the game for this. It's clearly cheating.

tobyhinloopen2• 1 year ago

I agree.

It is the future of cheating, completely undetectable

Daneel_2• 1 year ago

The inputs would form a very distinct pattern that likely doesn’t look anything like what a human creates - I think this would certainly be detectable, although you could also account for this in your program (similar to the ongoing back and forth with captcha).

toast02• 1 year ago

For the author, if they revist this, they might look into 7-bag random generator. TLDR, most modern tetris games, including tetris 99 select a permutation of the 7 unique pieces every 7 pieces; this means even though Tetris 99 shows you the next 6 pieces, you may know more about the next pieces.

For example, at the beginning of the game, it shows you 6 pieces, but you can determine the 7th piece because it's the one that's not shown. The 8th piece could be any of the 7 pieces, but when you see the 13th piece, you know the 14th piece (and when you see the 12th piece, you know there are only two possibilities for the 13th piece).

Additional look ahead every so often might be helpful, given that they found

When looking only 3 moves ahead, Jeff achieves a Tetris percent of 8.9%. When looking 6 moves ahead, he improves to 9.7%—nearly perfect!

I'd also be interested in seeing optimization for combos. Or t-spins; t-spins send 2x lines of garbage for each line cleared; which I hate, because I grew up before t-spins were encouraged. :P

Sohcahtoa82• 1 year ago

TLDR, most modern tetris games, including tetris 99 select a permutation of the 7 unique pieces every 7 pieces; this means even though Tetris 99 shows you the next 6 pieces, you may know more about the next pieces.

Wait, is this true?

I always assumed each piece was selected perfectly randomly, making it possible (though rare) to get the same piece 3 times in a row.

If what you're saying is true, then that mean there should never be more than 12 pieces between I pieces, and if you get two in a row, then it'll be a minimum of 6 before you see another.

Which...all seems within the realm of possibility. Tetris always seemed really good at having a very even spread of pieces without "streaks".

trothamel• 1 year ago

Yes, it's part of the (leaked) Tetris Guideline.

https://tetris.wiki/Tetris_Guideline

toast02• 1 year ago

Yeah, it's true. Old games like gameboy and NES tetris (either flavor), and the Atari arcaee machine were one piece at a time random, and not particularly evenly distributed either.

omoikane• 1 year ago

See also: "A history of Tetris randomizers":

https://simon.lc/the-history-of-tetris-randomizers

via: https://news.ycombinator.com/item?id=20872110

TZubiri• 1 year ago

Using AI to win in a game where reflexes are a key factor is lame.

novia• 1 year ago

I am good at Tetris 99. I've placed first many times.

After you place first it unlocks a level where you battle against only other users who have also placed first. I don't see any mention of this second level in the article (though admittedly I skimmed it), which makes me suspicious of whether they actually got their bot to place first. Obviously the next step would be to try it out on that harder level.

Also, more often than not, there are not 99 player characters who you are battling against. The field has always been filled out with other bots, generated by the game designers themselves. I don't think they would ban a bot player from the game.

zamadatix• 1 year ago

Someone generating dud/faked source code, examples of the algorithms and challenges, videos of gameplay, and an article... rather than just winning a game of Tetris 99 with the approach? That would be more work than the face value of the article, not less, so I don't buy that theory at all.

Plenty of games have both official bots and anti-cheat and player botting rules, the presence of one does not define what the presence of another will or won't be.

umvi• 1 year ago

Pretty sure Invictus is mostly bots these days

gwern• 1 year ago

While testing Jeff’s brain, we found an unusual bug: Jeff would play perfectly fine for a while, and then rapidly stack pieces on top of each other to reach the top, ending the game. The bug would usually happen when the board was starting to get taller and would be less apparent when we reduced the depth of the search—that is, looked fewer moves ahead while considering our next block placement.

Classic RL reward-hacking! You'll often see 'suicidal' agents when the reward-shaping goes wrong, or they converge prematurely after inadequate exploration. (Tom7's Mario agent famously pauses the game to avoid losing.)

I’m not sure if there are good ways around this. Rigorous testing, maybe, but it’s hard to improve your algorithm by observation once it’s not making obvious mistakes. This is, perhaps, one of the promises of using reinforcement learning without human play training: if your algorithm is able to achieve human-level performance, it’s probably correct enough to continue well into superhuman performance.

In this case, because the random number generator's decisions are unaffected by your actions, you can use the clairvoyant oracle trick, I think. Just record games, and then do your DFS planning over the entire game with the known sequence of blocks; this then represents perfect play and is a benchmark for your actually feasible algorithms.

bl4kers• 1 year ago

Doesn't Nintendo frequently fill the 99 spots with bots?

LlamaTrauma• 1 year ago

I considered making a Tetris 99 bot for a while just for the sake of doing it, but interfacing with the switch sounded like a huge pain. Cool to see someone actually went through with it.

waltercool• 1 year ago

And this is why people don't play online anymore.

Bad players are so desperate to cheat in order to win. They don't belive at fair competitions, but instead will use any dirty trick to win.

And this is also why most online games are full of invasive anti-cheat crap.

PetitPrince• 1 year ago

This is reminiscent of 2007 Colin Fahey Tetris AI (including using a webcam instead of a direct feed) : https://www.colinfahey.com/tetris/tetris.html

First place in Tetris 99 using computer vision, classical AI, a lot of free time

Related Stories