An AI for playing NES Tetris at a high level. Based primarily on search & heuristic, with high quality board evaluation through value iteration.

Overview

StackRabbit

An AI that plays NES Tetris at a high level. Primarily based on search & heuristic, with high-quality board eval through value iteration.

Due to the logistics of playing NES Tetris, there are two different clients for interacting with the main AI backend:

  • fceux contains a Lua client for playing in the FCEUX emulator (primary client)
  • console_client contains a python client that runs on Raspberry Pi to play on a real console.
  • TetrisTrainer is a public web client (try it live!) that lets users draw a board and ask AI about the best placements.

Then there are two components of the backend:

  • server contains the primary server, written in Node.js. It handles the request parsing, and the delegation to worker threads. It also contains lots of deprecated AI code, since the initial implmentation was entirely in JS (oops).
  • cpp_modules contains modules that perform the core AI computation at literally 100x the speed of the original JS implementation. The main flow involves a Node server thread sending a game state to the C++ module, which returns the value of each possible move as an encoded JSON map.
Comments
  • Issue with Node on MacOS

    Issue with Node on MacOS

    When I clone the repo and run npm run-script start-server, this error message pops up after the project builds:

    Error: ENOENT: no such file or directory, open 'docs/condensed_NoNextBox_NoBars.txt'
    

    I fixed this by removing this code block in rank-lookup.js

    const ranks_NoNextBox_NoBars = fs.readFileSync(
      "docs/condensed_NoNextBox_NoBars.txt",
      "utf8"
    

    It doesn't seem to be used anywhere for some reason...

    opened by AstroOrbis 3
  • Error with cmodules

    Error with cmodules

    When I use npm run cr, this error pops up:

    make: Nothing to be done for `all'.
    Making C++ module call
    /Users/noahschatz/Desktop/StackRabbit/built/src/server/cmodules.js:7
        var result = cModule.length("00000000000000000000000000000000000000000000000000000000000000000011100000001110000000111100000111110000011110000011111100011101110011101110001111111000111111100111111110011111111001111111101111111110|18|2|5|0|X...|");
                             ^
    
    TypeError: cModule.length is not a function
    
    opened by AstroOrbis 1
  • Correct human-possible assumptions?

    Correct human-possible assumptions?

    @GregoryCannon Your "human possible" recording tops out at score 1½ million, but recent actual WR are >3 million. #7 notwithstanding, does it mean that the recent record holders are now better than your assumptions for "human possible"?

    opened by TPS 0
  • "Human Possible" seems to presume overly accurate tucks and spins.

    The latency and Hz metric make StackRabbit very good at analyzing boards given the physical limitations of a particular human player. However, one metric is seems to be missing is the natural "misdrop" rate associated with actions that have a very small window of frames to work with. In particular, sometimes an issue occurs where on S/Z next piece, StackRabbit suggests an adjustment based on what would require a near frame-perfect tuck or spin at late levels.


    I think this could be resolved by allowing us to input a mapping between how many frames of lee-way are available, and the odds of missing an input.

    An example mapping could be

    Window of 1 Frame: Misdrop Rate 50% Window of 2 Frames: Misdrop Rate 20% Window of 3 Frames: Misdrop Rate 4% Window of 4 Frames: Misdrop Rate 1% Window of 5 Frames: Misdrop Rate 0.5%

    And of course, these numbers could be adjustable just like how latency and Hz are adjustable, since various players have various physical input skill levels.

    In this method the algorithm can calculate the quality of the position Q1 assuming the place is placed correctly, and the quality of the position Q2 assuming the tuck or spin failed to execute (e.g. where the piece would go if the rotate button was never pressed, in the case of a spin, and if the left/right button were not pressed, in the case of a tuck). And then, it can calculate the EV of that move as Q1 * (1 - MisdropRate) + Q2 * MisdropRate.

    This could also help apply for cliffs. At 15Hz, that's one button press every 4th frame. It takes minimum 13 frames to press the button 4 times. But, if there's a spire that requires tapping 4 times within 16 frames to clear, that leaves only a 3 frame window to miss the spire, implying that we'll hang the piece on the spire 4% of the time at Level 18.

    1 0 0 0 1 0 0 0 1 0 0 0 1
     <- 
      1 0 0 0 1 0 0 0 1 0 0 0 1
   <- The three possible ways to overcome the spire at 15Hz
        1 0 0 0 1 0 0 0 1 0 0 0 1 <-
    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ <- The 16-frame window to press the button 4-times within
    

    This calculation in particular can really matter for some of its "Adjustment" recommendations, which often involves a suggestion to swing from the far left side of the board all the way to the right side of the board, barely missing the middle of the stack. Especially on higher levels, these are moves that humans wouldn't want to execute, due to the risk of hanging the piece on a spire (Or at least, the risk of the misdrop should be weighed against the quality of the board achieved by the adjustment). Avoiding these adjustments will also make StackRabbit avoid moves that depend on your future ability to make that adjustment if a "bad" piece comes.


    I think including these metrics into StackRabbit would cause the "Human Possible" simulation to look far more like human play, and most importantly increase the quality of the suggestions of the "Live Trainer" by suggesting moves that weigh the risk of a misdrop. Additionally, it would likely compel the Live Trainer to create stacks that are "cleaner" with respect to avoiding dependencies on very precise moves.

    opened by npip99 0
  • Simulate future board trees by analyzing RNG?

    Simulate future board trees by analyzing RNG?

    Hi, love the project! I just saw your 102 million video on youtube and thought about what a "no-limit AI" really means in the context of NES tetris. Well, I dunno if you've taken a look at https://meatfighter.com/nintendotetrisai/#Picking_Tetriminos but it turns out that once you've figured out what your current RNG seed is (which can be done in a fairly small number of piece drops with a simple lookup table for all 32,767 possible starting seeds), you can simulate the entire future game outside of the game.

    And once you can simulate it, you can also find branching paths towards optimal play. I assume pause-based RNG manip is completely off the table for you since you want this AI to play the game under the "rules" as if it's an impossibly talented human being, but minor rng manipulation is still possible based on how high up you place your pieces (ie, how many frames it takes for them to fall) and when you choose to complete your tetrises (since the frames it takes for line clears will advance the generator several--completely predictable--steps) and would be completely allowed for a human if they had a brain capable of understanding it.

    Implementing this would be a major change to how the AI makes decisions, but would allow you to avoid more burns both by getting more line pieces (through minor rng manipulation, as determined by the AI's own decision trees) and by playing "riskier" (from the perspective of an outside observer), being able to stack higher when necessary under the knowledge of how much longer you have to wait for a future line piece.

    Without pause-manipulation, it's theoretically impossible to completely eliminate all burns in all scenarios, but I think it wouldn't be impossible to make it to level 236+ with a single-digit number of burns in the entire game.

    I wouldn't expect the AI to simulate every possible non-hole-creating position for every single piece, as that would obviously get exponentially large too quickly, but it could maintain a few trees that currently seem "most promising" based on the current placement algorithm, culling first and foremost whatever tree takes a burn in a time span in which any other tree found a tetris (and then obviously culling whatever trees become obsolete based on live piece placement, since you'll have to pick exactly one branch you're currently going with by the time you place a piece--though you'd be searching trees so far ahead that having a piece actually arrive at a branch that hasn't been culled to 1 option is something I don't yet know is realistic. Maybe if both branches allow you to continue playing perfectly, you'd have kept them both around? But at some point before that you should be picking and choosing arbitrary equal-value branches to cull simply to free up more memory for future branches).

    I am not aware of potential desynchronization issues on NES hardware (ie, a frame failing to call the randomizer for some erratic reason, such as perhaps the slowdowns that happen in much later levels), but even if they do, you could fall back to the old behavior if a piece ends up being "wrong", and then start rebuilding trees after finding the "new" seed (which should only be 1 frame off in one direction or the other). Hell, NES hardware should be predictable enough that even if e.g. scores start clobbering the rng seed at higher values (which probably isn't the case), the AI could account for that deterministically as well.

    opened by codetaku 0
  • Running the program

    Running the program

    The program compiles and starts fine, but I'm not sure what to do afterwards... Running the stackrabbit.lua file gives me this error: lua: stackrabbit.lua:226: invalid escape sequence near '",|\|'

    npm run start
    
    > [email protected] start
    > node built/src/server/app.js
    
    loading: 37.594ms
    loading: 30.735ms
    loading: 34.795ms
    loading: 30.625ms
    loading: 32.999ms
    loading: 33.019ms
    loading: 28.115ms
    Done loading worker threads
    Listening on port 3000
    

    Navigating to localhost:3000 gives me this: Screen Shot 2021-10-27 at 11 34 59

    opened by AstroOrbis 4
Owner
Greg Cannon
Software engineer at Google, working on Duo Android. Computer Science graduate from Pomona College.
Greg Cannon
Had a tough time playing Microsoft Wordament ? Well WORDament_Solver has your back. It suggests you meaningful words you can use while playing the game and help you top the leaderboard.

WORDament_Solver Had a tough time playing Microsoft Wordament ? Well WORDament_Solver has your back. It suggests you meaningful words you can use whil

Tushar Agarwal 3 Aug 19, 2021
John Walker 24 Dec 15, 2022
A gazebo actor plugin that utilizes the map of the environment and graph search methods to generate random actor trajectories that don't pass through walls, furniture, etc.

Gazebo-Map-Actor-Plugin A gazebo actor plugin that utilizes the map of the environment and graph search methods to generate random actor trajectories

Yasin Sonmez 11 Dec 23, 2022
Typesense is a fast, typo-tolerant search engine for building delightful search experiences.

Fast, typo tolerant, fuzzy search engine for building delightful search experiences ⚡ ??

Typesense 12k Jan 2, 2023
A port of uMario (a widescreen remake of SMB NES) to the Playstation vita.

uMario PSVita Port A port of uMario (a widescreen remake of SMB NES) to the Playstation vita. Gameplay video: https://youtu.be/QZDfrHlEhj4 uMario: htt

WeegeeDEV 18 Jul 5, 2022
High-level interface for low-level programming

Singeli Singeli is now able to compile useful programs to C, but it's very rough around the edges, with poor error reporting. We are beginning to use

Marshall Lochbaum 40 Dec 30, 2022
A simple assembler, made primarily for assembling output from my compiler.

Assembler This assembler is not currently meant for general use. It supports only the instructions and features emitted (and used) in my C compiler. I

null 2 Nov 14, 2021
Implementation of python itertools and builtin iteration functions for C++17

CPPItertools Range-based for loop add-ons inspired by the Python builtins and itertools library. Like itertools and the Python3 builtins, this library

Ryan Haining 1.2k Jan 7, 2023
Tetris on a Raspberry Pi Pico mounted on a Pimoroni Pico Explorer

PicoTetris Classic Tetris game running on a Raspberry Pi Pico microcontroller. Pico C port by Richard Birkby Original JavaScript implementation - Jake

Richard Birkby 34 Dec 3, 2022
Tetris bot

Lemon Tea Guildline versus tetris bot How to build Notices Lemon Tea makes use of standard library header <bit> available in C++20, so make sure your

null 5 Aug 18, 2022
A version of Tetris with randomly generated polyominoes of varying sizes

Multris A version of Tetris with randomly generated polyominoes of varying sizes ----- CONTROLS ----- LEFT / RIGHT ARROW - Move. Hold to move quicker.

null 17 Nov 5, 2022
Simple Tetris clone written in C++ using SFML

stetris Simple Tetris clone written in C++ using SFML. The game has been tested only on GNU/Linux system so far. Building dependencies (on Linux) g++

sewe2000 3 Jun 14, 2022
A high performance, shared memory, lock free, cross platform, single file, no dependencies, C++11 key-value store

SimDB A high performance, shared memory, lock free, cross platform, single file, no dependencies, C++11 key-value store. SimDB is part of LAVA (Live A

null 454 Dec 29, 2022
A water tank level sensor **Built With WisBlock** to detect overflow and low level conditions.

RAK12014 Laser TOF sensor coming soon WisBlock Watertank Level Sensor Watertank Overflow detection using the RAKwireless WisBlock modules. It implemen

Bernd Giesecke 3 Feb 3, 2022
High Quality DeNoise 3D is an AviSynth port of the MPlayer filter of the same name

High Quality DeNoise 3D is an AviSynth port of the MPlayer filter of the same name. It performs a 3-way low-pass filter, which can completely remove high-frequency noise while minimizing blending artifacts.

null 13 Oct 3, 2022
This progrom aims at providing high-quality healthcare system for everyone ragardless of their social status.

This progrom aims at providing high-quality healthcare system for everyone ragardless of their social status. It tackles long-existed problems such as incompetent staff, long queues and outdated equipment. I am sure that this program has a potential to transform a healthcare system in our country.

Azimjon Abduvohidov 1 Jul 28, 2022
The FLIP Fluids addon is a tool that helps you set up, run, and render high quality liquid fluid effects all within Blender, the free and open source 3D creation suite.

FLIP Fluids The FLIP Fluids addon is a tool that helps you set up, run, and render liquid simulation effects. Our custom built fluid engine is based a

Ryan Guy 1.4k Dec 22, 2022
High-quality Interactive Audio/Video Windows SDK

腾讯云实时音视频 TRTC SDK English | 简体中文 产品介绍 腾讯实时音视频(Tencent Real-Time Communication,TRTC),将腾讯多年来在网络与音视频技术上的深度积累,以多人音视频通话和低延时互动直播两大场景化方案,通过腾讯云服务向开发者开放,致力于帮助开

LiteAVSDK 14 Sep 14, 2022