[HN Gopher] NES Tetris AI hits 102M points and level 237
___________________________________________________________________
NES Tetris AI hits 102M points and level 237
Author : zdw
Score : 180 points
Date : 2021-11-23 18:18 UTC (4 days ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| beebeepka wrote:
| Didn't even know there was Tetris on the Famicom. I thought
| Bejeweled and Dr Mario had the niche covered.
|
| Honestly, I am not super impressed. Where are the Quake and
| StarCraft bots? Deepmind hasn't shown anything interesting on
| that front after their last bot got smacked repeatedly buy a
| couple of low tier European players
| throwaway675309 wrote:
| Name a system that Tetris _hasn 't_ been ported to. Maybe the
| LaserActive?
| eigenket wrote:
| The point of the starcraft bot was never to be able to beat
| humans, it was about getting headlines and moving on. To be
| honest getting good at starcraft isn't really an interesting
| problem for AI to solve, you can probably do it if you throw
| enough GPUs at the problem, but you learn pretty much nothing
| in the process.
| NavinF wrote:
| > starcraft isn't really an interesting problem for AI to
| solve
|
| I completely disagree. This is much more interesting than the
| toy problems that most academics work on.
|
| RL problems in this space are inherently difficult since you
| only get 1bit of "ground truth" information (win/loss) at the
| end of a game and have to guess which of your actions
| contributed to that outcome. Sure you can throw hardware at
| the problem, but you've got a huge incentive to minimize
| costs.
|
| It's only recently that the default consensus for RL problems
| changed from "this is an inherently creative endeavor and
| needs human input" to "you can probably do it if you throw
| enough GPUs at the problem".
| gwern wrote:
| I'd say SC2 is still in the "inherently creative" part.
| Even with the very interesting AlphaStar League _partially_
| solving the self-play diversity and exploration problem, it
| 's not at all obvious that just sinking in another 10-100x
| TPU-time into AlphaStar would patch up all of the errors
| and poor strategy AS exhibited - in fact, I'd bet heavily
| against it, since spending a large-but-still-feasible
| amount of compute doesn't appear to have fixed OA5 or
| AlphaGo's similar-looking problems, but AlphaZero was
| required.
|
| Now, applying MuZero _might_ be powerful to solve SC2 with
| much more compute, but that is still not something many DRL
| researchers would give you large odds on, and you still
| probably need to come up with some ways to abstract it and
| condense the game tree into something tractable for
| planning over, especially with the partial information
| making modeling the future much harder. (VQ-VAE and related
| generative modeling approaches are promising in this
| regard... but still no slam dunk. If DM announced tomorrow
| that MuZero+VQ-VAE had defeated AS and a bunch of human
| pros, people would be extremely shocked, even as they
| scrambled to tweet about how they saw it coming all along
| & also are very offended by the waste of CO2 and how
| unreplicable it is on a grad student budget.)
| NikolaeVarius wrote:
| I'm skeptical of your claims that Starcraft is not
| interesting problems for AI.
|
| For many problems, the AI is given as much information as
| possible of the state of the system to make decisions. The AI
| knows the entire state of the game in Tetris or Go or Chess.
|
| Starcraft/RTSs are designed specifically to remove
| information from the player and force you to balance info
| gathering, building, and countering new information, which is
| a massive difference from the currently impressive AlphaGo
| and such
| oblak wrote:
| Strongly disagree. They were clearly pushing very hard right
| until their precious bot was defeated repeatedly by - again -
| a low tier European "pro".
|
| I still remember the principal (somewhat curly hair and
| glasses) engineer looking extremely pissed after the matches.
| Funny how they switched priorities right after that. 100%
| completely unrelated, as you say.
|
| Also, as NikolaeVarius pointed, SC is a game of imperfect
| information. If that's not interesting from an AI
| perspective, I don't know what is.
| toast0 wrote:
| I don't know if it was released for Famicom, but Tengen (Atari)
| had also released their version of Tetris for the NES, which
| hews closely to the coin-op Tetris. It was famously removed
| from the market because of licensing clarifications, Tengen
| didn't have the license to release Tetris on home gaming
| platforms, like they thought they did.
| kilovoltaire wrote:
| Meanwhile human NES Tetris is also getting unbelievably good,
| including a whole new method of 'rolling' your fingers across the
| back of the controller
|
| Here's a video of a former world champion 'hypertapper' Joseph
| versus the newly ascendant 'roller' Huff, from the world
| championship a couple weeks ago.
|
| They both reach a million points (called a 'max out' because the
| unmodified game stops counting after that) at around 9 minutes in
| to the video:
|
| https://youtu.be/wELh6bO_ze0?t=9m
| jeffwass wrote:
| What is Huff actually doing with his gloved right hand? Can't
| really tell in the video.
| ChrisClark wrote:
| Looks like he's flicking the back with multiple fingers one
| after another, so instead of pushing down on the dpad, he's
| pushing the controller into his left hand. I guess it's a
| faster way to multi tap it.
| fartcannon wrote:
| Here's the world NES Tetris records leaderboard.
|
| https://docs.google.com/spreadsheets/d/1ZBxkZEsfwDsUpyire4Xb...
|
| Looks like Huff finally beat HydrantDude's 1.6 million.
| wanderingstan wrote:
| What does the finger rolling accomplish? I see one playing
| doing it in the video, but it's not clear why. IIRC, there are
| no buttons on the back.
| runevault wrote:
| So a detail I didn't see from the others to add on. Tetris
| technically allows you to push the button every frame, so 60
| moves/second would be optimal if you ignore physical limits
| of the controller etc. With the oldest way of playing called
| DAS (I forget what it stands for) after a couple frames it
| starts inputting really fast, but you have to store inputs to
| manage to make it move the way you want efficiently. This new
| rolling is the fastest way found so far to press the
| direction buttons quickly and get as many presses per second
| possible to better position blocks.
| LocalH wrote:
| I think you mean 30 moves per second, as Tetris (like most
| games) doesn't count two consecutive frames of "button
| pressed" as two button presses, but a press-and-hold. Still
| faster than the 10Hz of DAS, but by necessity a full,
| separate button press requires at least one frame of
| "button pressed" separated by one frame of "button not
| pressed".
| runevault wrote:
| You're right on 30fps. Been a while since I followed NES
| Tetris. Thanks for the correction.
| oooooooooooow wrote:
| Delayed Auto Shift. In NES tetris the rate is 10 moves per
| second, so to beat it in speed you have to press on the
| dpad at more than 10Hz.
| sjburt wrote:
| They hold one finger over the desired button and the finger
| roll on the back pushes the controller into the first finger,
| generating multiple taps faster than you could with a single
| finger.
| goldenkey wrote:
| It's basically like bump firing but for controllers instead
| of guns. World-class revolver shooters also use this kind
| of method.
| dylanfw wrote:
| I was curious as well and found this video explanation[1].
| The idea is that tapping on the back of the controller pushes
| it up into the player's thumb which is resting on the D-pad
| causing a button press.
|
| [1] https://youtu.be/n-BZ5-Q48lE
| [deleted]
| zucker42 wrote:
| You rest your finger from the other hand on the button in
| front, so when rolling the button is pressed. That way you
| can use more than one finger to press, which allows faster
| pressing. The fastest rollers can hit the button around 20
| times a second, whereas by holding the button down (i.e.
| manipulating DAS, the traditional technique) you can only
| reach 10 Hz.
| garaetjjte wrote:
| There's a interesting page about Tetris AIs:
| https://web.archive.org/web/20081101211903/http://www.colinf...
|
| It would be interesting how algorithm featured on the video
| compares to these described on the linked page, but it would need
| different runtime as NES crashing at just over 3000 lines is few
| orders of magnitude too short.
| elihu wrote:
| I wondered if this was using a machine-learning style AI and it
| was, among other things, learning the state of the random number
| generator so it could predict pieces accurately more than one
| turn out? (And if not, how would you prove that it wasn't?
| Perhaps tweak the game RNG and see if the AI performs badly?)
|
| Looking at the github repo, it looks like it's actually more of a
| classical AI doing traditional game tree search. There is some
| interesting code around the RNG, though: apparently the RNG does
| make certain piece sequences more likely than others, and there's
| a lookup table for the probability of the next piece given the
| current piece:
|
| https://github.com/GregoryCannon/StackRabbit/blob/master/src...
|
| I suppose one could extend this to be a 3-dimensional lookup
| table with the probabilities of the next pieces given the last
| two pieces, or to extend it to 4 or 5 or (if you had infinite
| resources) 100. At some point you'd know enough to be able to
| predict the next piece with 100% accuracy.
| mdavidn wrote:
| The NES version is quirky, as your link points out. It's best
| described as an 8-sided die, with rolls for 8 or the previous
| piece triggering a single reroll. The probability of the next
| piece being an "I" do not increase after a long drought.
|
| Newer versions of Tetris give random permutations drawn from a
| 7-tetrominoe bag, so the longest possible drought between two
| "I" pieces is 12 tetrominoes.
| karmasimida wrote:
| If it is a pseudo RNG then you can try a autogressive seq2seq
| model and see how it is doing.
|
| If it is a true RNG, then good luck, it would be unpredictable
| by definition.
| ineedasername wrote:
| Anyone know what would be a good source of entropy on a NES
| system for a good RNG?
| jenscow wrote:
| I'm guessing, the only thing available that was
| unpredictable is the user.. so things like the input
| timings.
| rahimnathwani wrote:
| I didn't know the move at 21:25-21:26 was possible. The player
| rotates a z shape from vertical, into its final position. If you
| were playing with physical blocks, this rotation wouldn't be
| possible.
| mypalmike wrote:
| Yeah z-spins give bonus points in some later variants of
| Tetris.
| jFriedensreich wrote:
| one of the few titles that are less click-baity than could be. it
| reached the level that broke and froze the game...
| mikub wrote:
| I just played the SNES version of Tetris today before seeing
| this. Got 123 lines, which I considered a pretty good run. :)
| airstrike wrote:
| Came for the Tetris, stayed for the named color palettes. At
| first I thought these were official names but "Mexico According
| to Hollywood" kinda gave it away (level C8 or 182)
| kevincox wrote:
| What a graceful way to handle levels beyond what you had the
| resources to include in the game. They could have wrapped
| around, but that would have been boring, they could have
| switched to random generation but that would have required
| additional code. Instead just let it slowly cycle through ROM
| and use whatever is there.
|
| I'm not sure it was on purpose, but a nice solution.
| grendelt wrote:
| What causes it to freeze where it does?
| pronoiac wrote:
| I've heard somewhere that the CPU didn't have multiplication
| built-in, so in calculating how much level bonus to add would
| require a loop of additions. This was also an era where timing
| between frames was delicate, and if the housekeeping part of
| scorekeeping takes too long, weird things happen, it drops the
| ball on something else, and it seizes up.
| kevincox wrote:
| I guessed that it was a math loop causing the slowdown, but I
| wonder what actually killed it. Naively I would have thought
| that you just missed a frame like many other games on the NES
| (see SMB1). It is surprising that a missed frame actually
| kills the game.
| kthejoker2 wrote:
| He says earlier in the video it's building up memory pressure,
| so it's some sort of (obviously unconsidered) garbage
| collection issue.
| Agingcoder wrote:
| Garbage collection on a NES? AFAIK Lots of (most) games were
| written in asm, not with very high level languages.
| tinus_hn wrote:
| The NES contains 2k of RAM. Although you can extend that in
| the cartridge I doubt games use garbage collection.
|
| Why would you anyway? It's such a basic, predictable game.
| There's a fixed size playing field that contains only one
| fixed size moving object.
| __s wrote:
| Better would've been to suggest a memory leak
|
| But the level being near 256 suggests an integer overflow
| mypalmike wrote:
| Going a bit off topic here, but there's no reason you
| couldn't use a garbage collector to manage heap memory for
| your assembly language program.
|
| On the NES, such a memory management approach would be
| particularly insane.
| Ecco wrote:
| Maybe an integer overflow somewhere? Either that or the NES is
| just too bored at this point and cries uncle.
| beebeepka wrote:
| "cries uncle"? I am not a big fan of idioms but this one is
| bad. What does it mean?
|
| Edit: keep piling on me, guys. That'll teach me to like
| obscure idioms
| variaga wrote:
| https://idioms.thefreedictionary.com/cry+uncle
| throwaway675309 wrote:
| It's not a particularly obscure idiom (lots of pop culture
| tv shows make reference to it), and calling it "bad" makes
| zero sense.
| biddit wrote:
| To admit defeat
| jcims wrote:
| It's intentionally obscure, it's basically a safeword for
| young kids that enjoy torturing each other in one way or
| another. You're getting piled on for being weirdly critical
| about something you clearly don't understand.
| kordlessagain wrote:
| It's where your bigger cousin is giving you a noogie and
| you want his dad to help.
| moron4hire wrote:
| I always understood the usage of "to cry uncle", but
| never understood the origin until you described it this
| way. I guess, being the oldest cousin in my family, and
| not being the kind of person to beat up my younger
| cousins, it never came up.
| boomboomsubban wrote:
| I don't think that's the actual origin, Wikipedia says it
| likely comes from a 19th century joke about a parrot.
| https://en.wikipedia.org/wiki/Say_Uncle
| Y_Y wrote:
| from the Iowa Citizen of 9 October 1891:
|
| > A gentleman was boasting that his parrot would repeat
| anything he told him. For example, he told him several
| times, before some friends, to say "Uncle," but the
| parrot would not repeat it. In anger he seized the bird,
| and half-twisting his neck, said: "Say 'uncle,' you
| beggar!" and threw him into the fowl pen, in which he had
| ten prize fowls. Shortly afterward, thinking he had
| killed the parrot, he went to the pen. To his surprise he
| found nine of the fowls dead on the floor with their
| necks wrung, and the parrot standing on the tenth
| twisting his neck and screaming: "Say 'uncle,' you
| beggar! say uncle.'"
| NikolaeVarius wrote:
| You know its an idiom, and refuse to just Google it?
| Ecco wrote:
| I'm not sure why this is called an AI. I feel like a
| deterministic algorithm to play Tetris in an efficient way is not
| super complicated to write.
| ceautery wrote:
| https://github.com/GregoryCannon/StackRabbit if you'd like to
| test your casually flippant statement.
| H8crilA wrote:
| > It's not AI if I can understand what it's doing
|
| - found on the internet, 2021
| Ecco wrote:
| Not what I said or meant at all. I'm arguing about the proper
| use of the "intelligence" noun here. Does this really show a
| "capacity for abstraction, logic, understanding, self-
| awareness, learning, emotional knowledge, reasoning,
| planning, creativity, critical thinking, and problem-solving.
| "(Wikipedia)? I don't think so. All I see here is a simple
| list of steps that a machine keeps on repeating.
| Vetch wrote:
| There is the intelligence required to play the game and the
| intelligence required to learn it. As long as the activity
| of playing Tetris can be labeled as relying on intelligence
| then the machine can be labeled as an excised expression of
| said intelligence.
| [deleted]
| NamTaf wrote:
| We have used "AI" to denote the computer player in games
| for as long as I've been alive, and I'm pushing my late
| 30s. This is not new ground, and I'm a bit surprised you're
| choosing this hill to make your stand.
|
| e: This is precisely why there's the distinction of
| "artificial general intelligence"
| kzrdude wrote:
| It's not strange, it's precisely because AI is used as a
| term everywhere now, that we should be skeptical of using
| it that way.
| H8crilA wrote:
| You're right. In my little joke I implied something else
| than you said. It's a low/middle complexity piece of
| control software.
| qayxc wrote:
| That's a strange takeaway from this.
|
| Ecco simply missed the fact that the Tetris AI used here is
| actually exactly that: a deterministic algorithm that uses
| heuristics to search the best placement options.
|
| This is not deep learning in case you're wondering.
| ArtWomb wrote:
| I love to see all the Nintendo preservation, enhancement and AI
| research ;)
|
| What's the best way to programmatically interface with an NES ROM
| in 2022? JSNES, from which you could run tensorflow.js, seems
| perfect for browsers. But NES-py integrates with Open AI Gym env
|
| https://github.com/Kautenja/nes-py/wiki/Creating-Environment...
| fartcannon wrote:
| Gym-Retro works up to python 3.8 at the moment.
|
| https://www.youtube.com/watch?v=sgEIoOQgjFg shows how to
| integrate an AI using gym-retro, stable baselines with pygame
| so you can fight it.
| [deleted]
| loufe wrote:
| I love that there's something innate about our desire to do
| things like these. I caught myself c# a couple years ago on a
| project I made to solve Minesweeper
| (https://github.com/Loufe/GroundPenetratingRadar). Very much a
| "journey" and not "destination" oriented endeavour.
| jareklupinski wrote:
| ha! great name :)
| jedberg wrote:
| Me: Clicks on video, see's it's 25 minutes long. Thinks, "I'll
| watch a few minutes and see if it gets interesting".
|
| Me, 25 minutes later: Dang, that was cool and a fun nostalgia
| trip!
| akira2501 wrote:
| The "Classic Tetris World Championships" are my favorite and
| personally most entertaining e-sports championships I watch. I
| highly recommend it.
| 14 wrote:
| That was really neat to watch. I started playing Tetris when it
| was first released and still play it on my Nintendo years later.
| My kids try but I can always beat their score and they think I am
| a master of the game. I can't wait to show them this video. Very
| awesome to watch.
___________________________________________________________________
(page generated 2021-11-27 23:00 UTC)