[m4lvin]

Is there a good way to reduce SAT or other decision problems to Tetris? Do we need to enlarge the grid to reduce larger problem instances, or can the duration of the play / length of the sequence be used for that?

I would hope for something like "This list of clauses is satisfiable iff there is a winning strategy to clear at least N lines when given the following sequence of tetrominoes". (Where the article here says that there is no hope for anything like this with N=1, but )

Or does knowing the whole sequence in advance make any sequence easy to play / clear any number of lines?

[dragontamer]

In my experience, strong human players can consistently keep track of random-bags and plan out holds, and do so at surprisingly high speeds.

I'm not sure if a computer SAT-solver is needed to accomplish any of the tactics in Tetris-Guidelines.

Maybe it'd be a fun exercise, like using SAT-solvers on human-level Sudoku puzzles. Or for maybe inventing "harder" versions of Tetris, designed for computer players instead of human players.

-------

I've given some degree of idle thought in how a SAT-solver can maybe discover patterns that would help an intermediate-player develop the eyesight / instincts that strong players have. (Ex: SAT-solver to see the patterns an intermediate player is using, and then analyzing which patterns the player doesn't see yet).

Its a vague / idle thought however, I never seriously attempted to solve the problem. But "training exercises" exist in many video games, and developing tools for human-training / self-training are always useful.

Ex: if a SAT solver could see that the human _COULD_ have performed a King Crimson at some point (https://harddrop.com/wiki/King_Crimson), but the human-player made a mistake and only saw an easier TSpin-Triple setup instead (https://harddrop.com/wiki/T-Spin_Triple).

Such "computer automatic advice" into which elements of your play was possible, and solving it automatically (and determining if it was a good strategy or not) would be very helpful in training.

[foobarian]

Most NP-complete problems have really good heuristics that come to within a hair of optimal on most useful real-world inputs, e.g. things like integer partitioning, bin packing, traveling salesman, etc. You need really unusual inputs to give an optimal solver a drastic advantage. Case in point, with real-world TSP the fact that the cities are embedded on a plane means their distances have constraints that don't exist in the general problem.

[lupire]

I'm pretty sure 2-D Euclidean TSP is NP-Hard.

https://en.m.wikipedia.org/wiki/Travelling_salesman_problem (Computational Complexity).

[unnah]

It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.

[jhgb]

No, there aren't? The last time I checked, the best polynomial-time approximation algorithm to symmetric TSP (Christofides) could only guarantee finding a tour with no more than 3/2 of optimal length. Has something better been found since then?

[unnah]

Euclidean TSP is easier than general symmetric TSP. Polynomial-time approximation schemes (PTAS) were discovered in parallel by Arora (1998) and Mitchell (1999). AFAIK those algorithms are not very practical though. I haven't followed subsequent work in any detail, but I haven't heard of any major breakthroughs since then.

[bjourne]

You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.

[lupire]

Yes.

https://www.google.com/search?q=tetris%20n-p%20complete