Creating an Open Tetris Database

So there's plenty of information out there that can take you from a beginner to a good player. However, the skill gap between good players and the best players is enormous. And paradoxically it's rather subtle and challenging to describe. Stuff just sort of happens so fast that even the best players aren't particularly good at articulating why they are the best. I would say that the whole upper range of the skill curve is largely mysterious, and that this is due to the fact that a majority of the progress boils down to "magically better intuition".

So I've been thinking that we could actually do something about this. The skill curve really does simply boil down to mastering numerous quantifiable things. All we're missing is the data to do it. That's where this project comes in.

In my opinion, an attractive target game to approach is TGM1, for several reasons:

• Thanks to The Masters, there is a wealth of superplay videos out there
• There is a good range of players, each with reasonably well defined relative skill levels
• Because of the competition's nature, we see representative samples that don't trade risk for reward the way a world record might

The plan is to create a system where a video could be turned into a replay file. The replay file would be compatible with eg. MAME, however it would instead be played in a basic non-graphical engine that could tear through the replay much faster than realtime. This engine would also let you program any "hooks" you want so that you can log variables of interest.

The whole idea is that you could add new variables to try to answer new questions that weren't even thought of initially, and this would be no big deal. The slow video -> replay conversion is only done once. Afterwards, the engine efficiently reprocesses all replays in the database to calculate new stats super fast. I'm not talking mere piece counters or APM/TPS here, hopefully some of you have the imagination to see just how great the possibilities are.

The engine would of course process my and your shitty replays as well, and articulate all 1000 dimensions along which we suck. Call me a masochist but I get tingles just thinking about it. Research has shown that practice isn't nearly as beneficial as focused practice, and this would provide the mother of all auto focuses.

You could also do stuff like take your lossy video recording, and remaster it into a razor sharp emulated video. Would be cool to remaster the world record games etc.

The engine alone would be ambitious enough, but this requires so many things before it even comes to that:

• Reverse engineering the randomizer (done)
• Code to find the randomizer seed given a sequence
• Some machine learning thing to translate video into game state information
• Code to impute the replay sequence that lines up with the game states
• A frame perfect engine to run the replay files
• A bunch of hooks to log interesting stats
• Then the fun finally starts

As a project, I have a decent idea how to move forward with this, and the bits that are less clear synergize well with stuff I want to learn for work anyways so I could see myself chipping away at it in my spare time.
Does anyone else have interest in collaborating / have the required skills?

 

Absolutely! This is exactly the kind of thing I've been thinking about lately. We should chat more about it. I've been trying to take another look at AI and game evaluation stuff myself. You're describing something a lot like one of the long term objectives I've been daydreaming about!

 

I would like to help in any way I can (hopefully poor tetris skills do not matter )

I was thinking a bit about the randomizer part . [DELETED : While thinking my Math skills decided to take a break. The outcome was not worth reading...]

Hopefully I didn't mess up anything... [Yes, I did]

 

Does this work in this case? (because we don't know whether pieces have been generated in between and if yes, which, do we?)
Seems like I should probably leave this topic to more skilled people.
EDIT: did you mean to brute force a seed which generates the piece sequence ignoring the way TGM created it?

 

The way it works isn't too complicated, but you have to think in terms of how the CPU is generating the random sequence. It's seeded with some value, and then everything after that is deterministic. Yes there are rerolls, but given the same seed they resolve in the same way every time.

Let's say the randomizer is seeded with a 32 bit value. This means that even if there are infinite theoretically possible sequences, there are only 2^32 sequences in the actual game.
Let's say the randomizer is pure random. Then only 1 out of every 7 seeds has the correct first piece. You'd expect the number of matching seeds left to be around (2^32)/7.
Now if you take a look at the remaining seeds, and try to match the second piece, again only 1 out of 7 are a match. You'd expect the number of matching seeds left to be around (2^32)/(7^2).
So you can continue like this, and if you have a sequence of length n, the viable seeds left are around (2^32)/7^n).
Now I ask you, what happens when (2^32)/7^n) = 1? You would expect, on average, to have exactly 1 seed that matches your pattern!

Doing a bit of math, we are looking for n where 7^n = 2^32. That turns out to be ~11.4 so we expect that after around 12 pieces, you can determine the seed that lead to the observed sequence.

With a randomizer like TGM, the sequences are more similar to each other. Approximating the math, you'd expect the worst case (where the game always picks pieces outside the history) to reduce the seeds around (2^32)/(4^n).
(2^32)/(4^n) = 1 at n = 16, so it's still not that bad.

Now these n = 12 and n = 16 values are just what you would expect on average. In practice you will sometimes need less or more. But even in an extreme case, the n = ~1000 you get from a replay will be plenty to determine the original seed. And by knowing the seed, you can then create an emulator-compatible replay!

 

Thanks for explaining! (Although I'm planning to study Computer Science, I don't know much about randomizers... yet)
Noob question: which part of obtaining the seed is currently tackled?

 

There's a image-to-fumen converter coded by one of us (based OpenCV IIRC) lying around. Ask @Qlex or @steadshot ?
---
How are we solving the problem of getting the player input ?

Assuming noise in the image isn't a problem (it probably is; also, lineclear, see this thread), getting the player input is going to be tricky. How can we differentiate between a player using DAS and a player using conventional input ? I guess we could look at the previous frame and next frame ( if (noMovementInPreviousFrame) && (movementWayToFast) ), but that would be considerably more difficult that just deducing the playfield state.

---
At least getting the piece sequence is easy: look at the Next area, and update the piece list when the pixel changes.

 

I think it is even more tricky, because DAS can be charged during ARE --> it is possible that a piece spawns and instantly flies across the screen, which means noMovementInPreviousFrame won't trigger.
What might be helpful instead is that DAS speed is constant over time, while (tap,tap,tap) most likely (not definitely) has pauses of different lengths in between.
Then the condition would rather look like (if (movementWayToFast) && (pieceHasConstantSpeed)).

 

You do a brute force search for the seed. If you have a randomizer algorithm, and a long piece sequence, you literally just try each of the 2^32 seeds one at a time until you find the match. I've written this before for TGM3, just need some modifications to get it for TGM1.

@PetitPrince Player input is tricky. It must be inferred based on observations from the stack space across many frames. DAS is 60Hz, tapping is maximum 30Hz, so that clears up most situations. Ambiguities exist (eg. did the player tap left once? or DAS left into an obstruction 1 space away?) and will need to be resolved using heuristics (eg. does this replay score high on DAS use for similar non-ambiguous placements?). Fortunately, by converting a MAME replay to video, it should be possible to validate the heuristics using real human behaviour. I guess the premise of this project includes my opinion that the vast majority of piece placement inputs are not ambiguous, and the ambiguities that do exist are not very important for analysis and/or have clear heuristics for resolving them.

Sadly it gets more complicated. What if you get the same piece twice in a row? During levelstop? You're stuck either using audio cues or looking for a piece dropping in the stack area.
I do have a solution in mind to at least find the seed without making this complicated.

 

Been super busy of late, but I would toss my hat into the ring to help out if required/of benefit; I'm reasonably sure I could lend something to most of the areas initially listed. At the very least, I'll be sure to follow your progess

 

Appreciate the offers! If anyone has thoughts please chime in. Especially @Qlex and @steadshot if they've gone down this path before.

Right now I'm focusing on the randomizer side of things, the part of automatically transcribing the piece sequence. I'm thinking that I should train a Haar cascade to recognize the area of the playfield/next piece/stats. And then I can cut out sub windows of this (eg. just the next piece area) for additional processing.

Something just about anyone could do to help:
Create a list of important youtube videos you'd like to see processed. For now just limit it to TGM1 though.

 

I'm confused, I thought the autohotkey thing was just a script to twerk the mouse while you play to keep the lag lower "because Windows".

 

Oh well then I have no idea what that is. @Muf @K tell me more!

 

@colour_thief: I really love your idea, it's been something that has been on mind for a while as well and I'd like to try and help.

The thing that @PetitPrince mentioned is a thing I made for Qlex's stream a while ago when he was taking video analysis requests. It just uses OpenCV to convert a screenshot of a playing field into a fumen diagram. Here's a live demo of the concept (it's still a bit primitive, because it doesn't try to detect colour) and here's the code. I've also dabbled in using OpenCV to analyse live video (I can share some notes on that later when I get back from the Eindhoven meeting) and it seems doable. One problem with TGM1, though, is that the background is a bit transparent, so in some sections the background shines through and the fumenizer gets confused.

This is jago's thing, but as far as I understand it, it requires pixel perfect video output to properly recognise stuff.

 

Thanks for sharing I'll check that out!
And yeah, I'd like to stay away from solutions dependent on pixel perfect video. Hopefully we can get something that works with even heavily lossy video (eg. YouTube) and perhaps even video camera footage.

 

I have been playing around a bit with the fumenizer. Great work! (atleast for TGM2).

Currently, as you stated, the semi-transparent background is a little problem in TGM1. Let's take this situation:


That's the best capture I could create by increasing the threshold parameter before blue pieces went missing. The only thing that confused me was one green square gone missing in the upper left corner.
This program provides a solid basis, but I think we still got some work to do. I would try to get reliable block detection first before dealing with colors.

 

The TGM1 threshold feature was very experimental and seemed good enough for the thing Qlex was doing at the time. It'll be fixed once I do some more research or alternatively some trial and error to get good threshold values for each individual section.