Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Can you be sure to clear a line at Tetris?

a3nm.net

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Can you be sure to clear a line at Tetris?

#31

Post by rahimnathwani »

hackernewds wrote: post #29
georgecmu wrote: post #14

If you want to test a strategy against an adversarial tetris opponent: https://qntm.org/files/hatetris/hatetris.html The method by which the AI selects the worst possible piece is extremely simple to describe (test all possible locations of all possible pieces, see which of the pieces' best-case scenarios is the worst, then spawn that worst piece), but quite time-consuming to execute, so please forgive me if your bro…

It produces only S for me. which is fine, but then produces only a 4bar. seems pretty boringly simplistic as an outcome. I also got this message at the end, pretty random and cryptic ԊටຯߢதؿଈϠଵദເם௨කໃݹதغƬݷȿට༠ਡ௨

I think the last line is a replay, encoded in base2048: https://github.com/qntm/base2048

But when I tried your replay, it didn't work. Perhaps HN's text editor mangled something.

Re: Can you be sure to clear a line at Tetris?

#32

Post by jhgb »

unnah wrote: post #30
lupire wrote: post #21

Earlier quoted context omitted.

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?

Re: Can you be sure to clear a line at Tetris?

#33

Post by unnah »

jhgb wrote: post #32
unnah wrote: post #30

Earlier quoted context omitted.

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.

Re: Can you be sure to clear a line at Tetris?

#34

Post by samatman »

tosh wrote: post #2

Related: in the official specification of the game the pieces ("tetrominoes") are drawn from a bag to prevent the possibility of an unfavorable sequence of pieces that force you to lose the game. IIRC early implementations of the game did not always behave like that. https://tetris.fandom.com/wiki/Tetris_Guideline > You might have heard of the result that you can play forever with bag randomizer, Hold and 3 previews…

This is the perfect illustration of the gambler's it-isn't-necessarily-a-fallacy!

Despite a uniform distribution of tetrominoes, if you haven't seen that all important I in awhile, the run is "cold" and you are in fact "due".

For the gambler's fallacy to apply, events have to be both random and uncorrelated, where most interesting real-life situations (i.e. not games) the degree of correlation between events isn't zero: that's one way to observe a normal distribution, but not even the usual one.

Re: Can you be sure to clear a line at Tetris?

#35

Post by bjourne »

jhgb wrote: post #32
unnah wrote: post #30

Earlier quoted context omitted.

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?

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

Re: Can you be sure to clear a line at Tetris?

#36

Post by a3_nm »

bjourne wrote: post #35
jhgb wrote: post #32

Earlier quoted context omitted.

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?

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.

Re: Can you be sure to clear a line at Tetris?

#37

Post by a3_nm »

Arcorann wrote: post #24

qntm, creator of Hatetris [1], once did an analysis of this exact problem using brute force methods. While he managed to solve the problem for 4, 6 and 8 wide boards (including the minimum board height required, assuming game over if any part of a piece locks above the ceiling), solution eluded him for 10 wide, though he did prove that 6 height was insufficient. As it happens, since this work assumes a 20 high board…

Thanks for the pointer to https://qntm.org/tetris -- that's very relevant, I'll add it to the post.

Re: Can you be sure to clear a line at Tetris?

#38

Post by bick_nyers »

__s wrote: post #13
Hogarth01 wrote: post #9

There was a kid I knew in school who I would consider a very good tetris player. One time someone else was lamenting that they always get bad pieces and he said, "The Tetris gods will never give you a piece you can't play, you just don't know how to play it." Which has resonated with me for an oddly long time in my life.

This sort of thing comes up a lot in card games like mtg. Some players are convinced they're naturally unlucky. I like to phrase it as "bad decks get bad draws". To improve one has to be luck oblivious: improve what you can, accept what you can't. Bit of a serenity prayer approach

It's also important to understand that in a best of 3 format, if you have a 80% winrate per game against every player (which is insane btw), you still lose 10% of those matches. In a 9 round tournament day (which is standard for YuGiOh iirc), your chance of winning every single round for the entire day is merely 40%. If your edge is more realistic, say 60% winrate, then you lose 35% of those matches. More games per match are your friend for determining who is actually better.

Re: Can you be sure to clear a line at Tetris?

#39

Post by jhgb »

unnah wrote: post #33
jhgb wrote: post #32

Earlier quoted context omitted.

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.
Post reply on HN