News for hackers. Stuff that matters.
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.