4 ms·

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 t

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.

cfcosta 8y ago
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.
ComplexSystems 8y ago
Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
- hopler 8y ago
  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
  - bjourne 8y ago
    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.
- schwurb 8y ago
  ML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
  - mlevental 8y ago
    that's not true at all https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hardness_of_Approximation https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hard...
    - schwurb 8y ago
      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).
steveklabnik 8y ago
Eventually, the speed kills everyone’s game. It literally becomes impossible to get pieces to the edge. (This is in NES Tetris.)
- jchw 8y ago
  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.)
  - stormbrew 8y ago
    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.
    - jchw 8y ago
      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.
      - stormbrew 8y ago
        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.
        8y ago

cfcosta 8y ago

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.

ComplexSystems 8y ago

Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.

hopler 8y ago
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
- bjourne 8y ago
  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.
schwurb 8y ago
ML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
- mlevental 8y ago
  that's not true at all https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hardness_of_Approximation https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hard...
  - schwurb 8y ago
    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).

steveklabnik 8y ago

Eventually, the speed kills everyone’s game. It literally becomes impossible to get pieces to the edge. (This is in NES Tetris.)

jchw 8y ago
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.)
- stormbrew 8y ago
  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.
  - jchw 8y ago
    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.
    - stormbrew 8y ago
      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.
      - 8y ago