News for hackers. Stuff that matters.
Re:Tetris Is Hard, Even to Approximate by rhacker on Friday March 29, 2019 @06:47PM (#19526301)
Interesting. I would think ML would do well to copy players. When I play it's a rather boring game, I'm almost always just setting up for the |. I can imagine trying to approximate a player using a complex branch if/else structure being complicated code. But I have to wonder if deep ML would be a rather impressive implementation (even without seeing the next block). The only thing that kills my game is the ever increasing speed, which wouldn't matter to ML.
Re:Tetris Is Hard, Even to Approximate by cfcosta on Friday March 29, 2019 @08:38PM (#19526800)
That’s the high level, however t has thousands of micro decisions each time, such as some situations where you might choose to create a hole to maximize a clear later, or when it is better to try to Tetris at higher levels as compared to clear the lower ones to avoid getting too high and therefore harder or impossible to manipulates the pieces properly.
Re:Tetris Is Hard, Even to Approximate by steveklabnik on Friday March 29, 2019 @09:03PM (#19526883)
Eventually, the speed kills everyone’s game. It literally becomes impossible to get pieces to the edge. (This is in NES Tetris.)
Re:Tetris Is Hard, Even to Approximate by jchw on Friday March 29, 2019 @09:32PM (#19527004)
Imo NES Tetris gets a bit too much attention, there's plenty of better Tetris games if you want to talk about speed (SEGA Tetris, TGM, clones like DTet or Cultris, and so forth.)
Re:Tetris Is Hard, Even to Approximate by stormbrew on Friday March 29, 2019 @11:36PM (#19527558)
Ironically, tgm gets much faster (nestris tops out at 1 row dropped per frame, tgm at 20) but the faster speeds in tgm are much much easier (and more fun imo) to control because of various other variables in how dropping and locking work.
Re:Tetris Is Hard, Even to Approximate by jchw on Friday March 29, 2019 @11:57PM (#19527639)
Agreed. TGM is probably my favorite Tetris game; once you get used to the rotation it feels very natural without needing to go through the wall kick gymnastics of modern guideline Tetris. Sadly it seems Arika is either not able or not willing to produce more TGM games using their own ruleset. The guideline Tetris ruleset feels ass backwards in comparison, but I guess it really doesn't matter too much.

I never quite hit GM in any TGM game anyways; as fun as it was, I definitely had trouble keeping a clean stack at high speeds.

Re:Tetris Is Hard, Even to Approximate by stormbrew on Saturday March 30, 2019 @12:26AM (#19527757)
I got my first GM a couple months ago. Definitely felt like an achievement.

Afaik Arika is not allowed to make non-guideline Tetris games, but the fact that they made Tetris 99 for the switch has got some rumors going that they reached some kind of agreement and maybe a tgm4 could actually happen again.

Re:Tetris Is Hard, Even to Approximate by httpsterio on Saturday March 30, 2019 @04:39AM (#19528461)
TGM4 didn't fail due to TTC licensing issues. They had a hard time getting arcade vendors to co-operate and distribute cabinets. TGM1 and 2 (plus TAP+) were made before TTC started to enforce their rotation guidelines for games and that's why TGM3 and TGM Ace had the "World" and "classic" modes. Former being the TTC required rotation system and Classic being the (superior imo) Arika rotation system.

TGM4 is essentially finished and just in hold until Arika figures out how they're going to distribute it. I think you're right though that T99 is kinda Arika testing the waters with a console version and I think they might release it on Switch at least.

Re:Tetris Is Hard, Even to Approximate by ComplexSystems on Friday March 29, 2019 @08:39PM (#19526803)
Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
Re:Tetris Is Hard, Even to Approximate by schwurb on Saturday March 30, 2019 @04:52AM (#19528498)
ML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
Re:Tetris Is Hard, Even to Approximate by mlevental on Saturday March 30, 2019 @05:15PM (#19531911)
Re:Tetris Is Hard, Even to Approximate by schwurb on Sunday March 31, 2019 @09:43AM (#19535544)
Please point out where I am (completely!) wrong.

I have formally dealt with approximation algorithms before and I skimmed the wikipedia article, yet I did not find anything that contradicts me. Note the in the section on hardness, P and NP (obviously) appear as bounds of solutions. Where is the contradiction?

Further, all this (approximation algos and P/NP algos) are discrete, complete algorithms. ML is a completely different story, as one is never certain whether some optimum is global or local. Hence, ML is a heuristic, while Djikstras shortest path algorithm is a series of steps with a success guarantee (with provable worst runtime behavior).

Re:Tetris Is Hard, Even to Approximate by hopler on Friday March 29, 2019 @10:48PM (#19527340)
What does "too well” mean?

The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to play as well as a human and faster

Re:Tetris Is Hard, Even to Approximate by bjourne on Saturday March 30, 2019 @01:57PM (#19530770)
That is the "even to approximate" part. It means that Tetris is NP-hard AND no polynomial time algorithm can be shown to be within a constant factor of the optimal solution. Eg no matter how good your Tetris bot is, there may be one that is a thousand times better waiting to be discovered.