Hacker News new | ask | show | jobs
by dragontamer 1520 days ago
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.

1 comments

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.
I'm pretty sure 2-D Euclidean TSP is NP-Hard.

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

It is, but there are polynomial-time approximation algorithms that can get you arbitrarily close to the optimum.
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?
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.
Well, damn. I imagine the reason why didn't know about this is because I have never been able to formulate any of my particular problems in terms of Euclidean TSP (even just metric was hard enough at times), so all interesting stuff was about metric TSP for me. I'll have to look at that work, though. Thanks for the pointers.
You are correct for Metric TSP (weights satisfying the triangle inequality) but not for Euclidean TSP.
Further, for metric TSP, an approximation algorithm with a slightly better ratio was found, and received a best paper award at STOC'21. See the second paragraph of https://en.wikipedia.org/wiki/Christofides_algorithm.