

9580 members and stacking!


After 10+ years, the Hard Drop forums are now retired. It will remain here as an archive. For more active discussions visit our Discord. Thanks for the memories  Blink (10/17/2019)

Perfect Clears 


theRealMadridcf 
Mar 5 2017, 07:57 PM

Tetris Novice
Posts: 14
Joined: 19March 15

Hello, I made a program which tries to make perfect clears for all possible sequences of 11 pieces with guideline rules. The program uses hold, soft drop and wall kicks. Also deep drop can be allowed. With 1 piece in hold there are 99,736,560 possible guideline sequences which can happen at some moment of the game. The program can determine for all of them whether it is possible to make a PC or not by dropping 10 pieces. The program makes PC's for only 10 pieces (It doesn't check for PC after 5 pieces). I run the program for all sequences with soft drop and with deep drop. The results can be seen below. ResultsHold, soft drop and SRS wall kicksWith these settings the program found 62,834 sequences which are impossible to make a PC with 10 pieces. That is about 0.0630% of all the 99,736,560 sequences. So 99.937% of sequences are PC'able with the normal guideline rules. Hold and deep dropWith these settings there are 110 sequences which are not PC'able. 55 of them are in the following spoiler. The other 55 can be made by changing J>L, L>J, S>Z and Z>S. The piece in brackets is in hold. Notice that none of the sequences contain T piece and I is only in the last place in every sequence. The holded piece is either S or Z and the second to last piece is the other one of S and Z.
(S)LOSZLSJOZI (S)LOZSLSJOZI (S)LSOZLOSJZI (S)LSOZLSJOZI (S)LSOZLSOJZI (S)LSOZOLSJZI (S)LSZOLOSJZI (S)LSZOLSJOZI (S)LSZOLSOJZI (S)LSZOOLSJZI (S)LZOSLSJOZI (S)LZSOLOSJZI (S)LZSOLSJOZI (S)LZSOLSOJZI (S)LZSOOLSJZI (S)OLSZLSJOZI (S)OLZSLSJOZI (S)OSLZLSJOZI (S)OSZLLSJOZI (S)OZLSLSJOZI (S)OZSLLSJOZI (S)SLOZLOSJZI (S)SLOZLSJOZI (S)SLOZLSOJZI (S)SLOZOLSJZI (S)SLZOLOSJZI (S)SLZOLSJOZI (S)SLZOLSOJZI (S)SLZOOLSJZI (S)SOLZLSJOZI (S)SOLZLSOJZI (S)SOZLLSJOZI (S)SOZLLSOJZI (S)SZLOLOSJZI (S)SZLOLSJOZI (S)SZLOLSOJZI (S)SZLOOLSJZI (S)SZOLLSJOZI (S)SZOLLSOJZI (S)ZLOSLSJOZI (S)ZLOSLSOJZI (S)ZLSOLOSJZI (S)ZLSOLSJOZI (S)ZLSOLSOJZI (S)ZLSOOLSJZI (S)ZOLSLSJOZI (S)ZOLSLSOJZI (S)ZOSLLSJOZI (S)ZOSLLSOJZI (S)ZSLOLOSJZI (S)ZSLOLSJOZI (S)ZSLOLSOJZI (S)ZSLOOLSJZI (S)ZSOLLSJOZI (S)ZSOLLSOJZI
Not PC'able (guideline) I confirmed that all the sequences told by user perfectclear are not PC'able with guideline rules. See more about them in the topic by caffeine: http://harddrop.com/forums/index.php?showtopic=7565 There are 4,608 different sequences which are made by those rules.
I found another rule which defines a set of sequences which are not PC'able: A sequence with the last piece being T and the total number of J, L and T pieces being 2, is not PC'able. There are 52,992 sequences with this rule.
Those combined it makes 57,600 sequences which are not PC'able. So there are still 5,234 sequences which don't follow those rules and are not PC'able.
Beginning and 2 bags With the program I confirmed that all sequences in the beginning of a game are PC'able and actually all sequences which are made out of 2 bags are PC'able.
No symmetric solution I found out that there are sequences which are PC'able but their symmetric sequences aren't. With symmetric I mean changing every piece to their symmetric shape (J>L, L>J, S>Z, Z>S). Here is one of those sequences: (S)SOLJZOSLIZ This sequence is PC'able but it's symmetric sequence is not. The sequence has only 1 solution and here it is:
As you can see, the second to last piece is I and the move which is made needs a wall kick which isn't possible to make in the symmetric situation:
Therefore the symmetric sequence (Z)ZOJLSOZJIS is not PC'able because the solution which I showed is the only solution.
Here are all PC'able sequences which have a non PC'able symmetric sequence:
(Z)OZSLJLZIST (Z)OZSLJJZIST (Z)OZSJLLZIST (Z)OZSJLJZIST (Z)OSZLJLZIST (Z)OSZLJJZIST (Z)OSZJLLZIST (Z)OSZJLJZIST (Z)ZOSLJLZIST (Z)ZOSLJJZIST (Z)ZOSJLLZIST (Z)ZOSJLJZIST (Z)SOZLJLZIST (Z)SOZLJJZIST (Z)SOZJLLZIST (Z)SOZJLJZIST (S)SLOIJLZSOT (S)SOLJZOSLIZ (Z)ZLSSJLOIZT (Z)ZLSSJOLIZT (Z)ZSLSJLOIZT (Z)ZSLSJOLIZT (Z)SZLSJLOIZT (Z)SZLSJOLIZT (S)SLOLIJZOST (S)SLOLIJZSOT
I confirmed with Okey_Dokey's Perfect Clear Finder that all these sequences are PC'able but the symmetric sequences aren't. According to the Perfect Clear Finder all these sequences have only 1 solution. Link to the Perfect Clear Finder: http://harddrop.com/forums/index.php?showtopic=7588
Performance I optimized the performance of the program quite a lot. On my ordinary computer the program solves all sequences with guideline rules in 4 hours and with deep drop it finishes in about an hour. Some things which I did to improve the performance are the following: The program uses bestfirst search with the heuristic function h(n) = (depth>>1)  (linesCleared<<1) + rowTransitions + (columnTransitions>>2). Here >> means divide by 2 and round down and << means multiply by 2. 'depth' means how many pieces are placed on the field. I found this heuristic function to work quite well. The smaller the value the better the matrix is.
 The program solves multiple sequences at the same time. For example it is much faster to solve sequences (I)JLOSTZIJLO and (I)JLOSTZIJLS at the same time rather than separately. The program solves on average about 1000 sequences at the same time.
 The program saves matrices and also piece placements in 64 bit integers. It is much faster to compare those integers rather than looping through arrays.
Also other optimizations are made. For example all possible places where a piece can be placed are calculated before the program starts solving any sequences. Then it is fast to just loop through that array and determine all places where a piece can be placed.
The program takes on average about 0.05 milliseconds to solve a PC'able sequence. Sequences which are not PC'able take much longer as the program has to go through all possible piece placements. The performance could still be more optimized for example with multithreading.
Source code The program is written with Scala. If anyone is interested to have a look at the source code you can download it here:
Perfect_Clears.zip ( 23.47k )
Number of downloads: 250
If you want to run the program or examine something about PC's with the program you need Scala compiler and Java virtual machine. (Scala is easy to install with Eclipse)
EDIT: Fixed a bug in the program: the first version throwed an error if you didn't want to save all solutions to a file.




Okey_Dokey 
Mar 5 2017, 10:59 PM

Tetris Professional
Posts: 630
Joined: 13May 15

Very cool Didn't think a computer could solve so many sequences in a reasonable time. Could you also attach that text file with all sequences that are not PC'able? I guess the last open Perfect Clear problem is that if it's possible to make 4line PCs forever or not. Your research didn't answer that problem because you didn't check for leaving certain pieces on hold (I guess such a calculation would take too long). Unless you found a sequence that is not PC'able no matter which piece is on hold (in which case it's impossible to PC forever). QUOTE(theRealMadridcf @ Mar 5 2017, 07:57 PM) A sequence with the last piece being T and the total number of J, L and T pieces being 2, is not PC'able.
Just to clarify: You mean if T comes last then it's not PC'able if the sum over all J, L and T pieces in that sequence is exactly 2? QUOTE(theRealMadridcf @ Mar 5 2017, 07:57 PM) With the program I confirmed that [...] all sequences which are made out of 2 bags are PC'able.
That's a very nice result. Just to clarify: The 99,736,560 sequences you examined looked like [random piece on hold] + [last pieces of bag #1] + [first pieces of bag #2]. And if piece on hold was different from the last pieces of bag #1, then there was always a way to perfect clear that sequence? edit: oops, forgot that there could be 3 bags involved if their are less than 2 remaining pieces in bag #1. Let's introduce the notion: [piece on hold]+[number of remaining pieces in bag #1]. For example, T7 means a sequence where T is on hold and the next 7 pieces come from bag #1 (and the last 3 pieces from bag #2). Or L6 means a sequence where L is on hold and the next 6 pieces come from bag #2 (and the last 4 pieces from bag #2). Are all sequences in T7 PC'able? What about T6? Also, are all sequences in L7 PC'able? What about L6?




theRealMadridcf 
Mar 6 2017, 12:16 AM

Tetris Novice
Posts: 14
Joined: 19March 15

QUOTE(Okey_Dokey @ Mar 6 2017, 12:59 AM) Very cool Didn't think a computer could solve so many sequences in a reasonable time. Could you also attach that text file with all sequences that are not PC'able? Thanks. Yes, I had to add it to the first post but I didn't find a way to add 2 attachments. Here are all not PC'able sequences with guideline rules:
unsolved_soft_drop.txt.zip ( 158.31k )
Number of downloads: 175QUOTE(Okey_Dokey @ Mar 6 2017, 12:59 AM) Just to clarify: You mean if T comes last then it's not PC'able if the sum over all J, L and T pieces in that sequence is exactly 2?
Yes that's what I mean. But the result was only for sequences which can come with 7bag randomizer. I don't know if for example sequences like (O)OOOOOOOOTT can be PC'able. As a note, the amount of J, L and T pieces can't be less than 2 with bags of 7 pieces. QUOTE(Okey_Dokey @ Mar 6 2017, 12:59 AM) Just to clarify: The 99,736,560 sequences you examined looked like [random piece on hold] + [last pieces of bag #1] + [first pieces of bag #2]. And if piece on hold was different from the last pieces of bag #1, then there was always a way to perfect clear that sequence?
In those 99,736,560 sequences the hold can be any piece. But in the result which I got for 2 bags the hold piece must be different than the last pieces of bag #1. I haven't tested only for the situations where hold piece can be any piece and the other 10 pieces are made out of 2 bags. QUOTE(Okey_Dokey @ Mar 6 2017, 12:59 AM) Are all sequences in T7 PC'able? What about T6? Also, are all sequences in L7 PC'able? What about L6?
Looking at the file which I attached, all sequences where the hold piece is T, J or L are PC'able. So yes those sequences which you asked are PC'able. QUOTE(caffeine @ Mar 6 2017, 01:19 AM) Nice work. Very interesting, especially the nonsymmetrical PCs. Good idea on using a heuristic to solve most cases faster
Thank you.




Okey_Dokey 
Mar 6 2017, 06:24 AM

Tetris Professional
Posts: 630
Joined: 13May 15

Thanks for answering my question. QUOTE(theRealMadridcf @ Mar 6 2017, 12:16 AM) Looking at the file which I attached, all sequences where the hold piece is T, J or L are PC'able.
That's another nice result. QUOTE(theRealMadridcf @ Mar 6 2017, 12:16 AM) But the result was only for sequences which can come with 7bag randomizer. I don't know if for example sequences like (O)OOOOOOOOTT can be PC'able.
I am very sure that if a sequence contains no L and J pieces and exactly 2 T pieces, then it can be only PC'able if you place both T pieces vertically (and if T comes last in the sequence, you can't put it vertically). See the a deadly piece sequence article. In the proof it compares how many filled cells are added to each column. Just consider the 2 columns on the very left side. Any S, Z, O placement and any horizontal T and I placement will add at least as much filled cells to the 2nd column as to the 1st column. If you place an I piece vertically, it's like reducing the width of the matrix, so you can leave vertical I placements out of consideration. Same goes for 2 O pieces stacked above each other. In the end, you can only fill all cells on the left side if you put a T piece vertically against the left wall (resp. to the very left of the reduced matrix). You must do the same on the right side. So you need to place both T pieces vertically.
Maybe a similar consideration can be done for L and J pieces. Maybe considering a field as checkered and looking where unbalances occur can also help. See the Parity article.




Blitz 
Mar 6 2017, 06:10 PM

Tetris Specialist
Posts: 231
Joined: 20April 12

QUOTE(theRealMadridcf @ Mar 6 2017, 12:16 AM) Looking at the file which I attached, all sequences where the hold piece is T, J or L are PC'able.
So that is proof that any sequence is PC'able if you have either T, J or L in hold at the start of the sequence right? I think I know how to answer the question if it's possible to make 4line PC's forever. Run through all the sequences in the unsolved sequences file but with T, J and L in hold. We know that all of these must be PC'able now because there is no sequence that starts with T, J or L in hold in the file. So the question becomes: Are they still PC'able if you have to have either T, J or L in hold after the perfect clear is complete? If they are, then it is possible to make 4line PC's forever. And if some of those sequences does not have a solution that ends with T, J or L in hold, that doesn't automatically mean it's impossible to make 4line PC's forever. It means we have to check the next few bags and see if we are able to continue making PC's and obtain a T, J or L in hold BEFORE we have a chance to encounter another sequence from the unsolved file. edit: wait, that doesn't cover all the cases. I think the correct question is: Can you PC any possible bag sequence if you start with one specific piece in hold and also end with that specific piece in hold?




theRealMadridcf 
Mar 7 2017, 04:27 PM

Tetris Novice
Posts: 14
Joined: 19March 15

QUOTE(Okey_Dokey @ Mar 6 2017, 08:24 AM) ...
Thanks for the explanation and for the links. I had heard of the deadly piece sequence but I hadn't seen that article. QUOTE(Blitz @ Mar 6 2017, 08:10 PM) So that is proof that any sequence is PC'able if you have either T, J or L in hold at the start of the sequence right?
Yes, the program was able to solve every sequence which had any of those pieces in hold. QUOTE(Blitz @ Mar 6 2017, 08:10 PM) I think the correct question is: Can you PC any possible bag sequence if you start with one specific piece in hold and also end with that specific piece in hold?
That is not possible. For example this sequence: (?)JOSLIZLZOS. No matter what the hold piece is here, the same piece can't be in hold anymore after a PC. I tried all those cases with Okey_Dokey's PC Finder. By the way, there are many sequences which are PC'able only if you have T, J or L piece in hold. As an example this sequence: (?)IJOSZIOSZT The question mark has to be T, J or L for this to be PC'able.




theRealMadridcf 
Mar 12 2017, 02:56 PM

Tetris Novice
Posts: 14
Joined: 19March 15

QUOTE(Blitz @ Mar 9 2017, 10:35 PM) Are there any sequences in the beginning of a game that are only PC'able when the piece in hold after the initial perfect clear is either I, O, S or Z?
I checked this and there are no that kind of sequences. Every sequence in the beginning of a game is PC'able in the way that the hold piece is either J, L or T after a PC. I think it can be checked whether it is possible to make continuous PC's or not. It could be done by solving for all sequences which of the pieces J, L and T can be in hold after a PC. When that is solved for all sequences it is fast to check for all combinations of sequences if it is possible to make a PC because you don't have to solve the sequences anymore, you can just look at the results which are found earlier.




myndzi 
Mar 16 2017, 03:31 AM

Tetris Grand Master
Posts: 1,932
Joined: 26June 09

Really nice work! I'm not sure if you caught this thread: http://harddrop.com/forums/index.php?showtopic=5465 but I described a different kind of parity which you seem to touch on in your analysis here. I've long felt that certain "rules" were begging to be discerned for the art of consecutive perfect clearing with the bag randomizer, but haven't put in the work to really determine what they are. You've brought us somewhat closer A question: For the rules which you've stated that define sequences that can't be cleared, have you checked the inverse? You stated that "All impossible sequences follow these rules", but are all sequences that follow those rules impossible?





theRealMadridcf 
Mar 19 2017, 01:40 PM

Tetris Novice
Posts: 14
Joined: 19March 15

QUOTE(myndzi @ Mar 16 2017, 05:31 AM) Thank you for the link, I hadn't seen it before. It was interesting. QUOTE(myndzi @ Mar 16 2017, 05:31 AM) For the rules which you've stated that define sequences that can't be cleared, have you checked the inverse? You stated that "All impossible sequences follow these rules", but are all sequences that follow those rules impossible?
I didn't say all impossible sequences follow those rules. I said that all sequences which follow those rules are not PC'able. So there are still 5234 not PC'able sequences which don't follow those rules.




farter 
May 28 2017, 08:02 AM

Tetris Expert
Posts: 303
Joined: 19April 11

great! i can't come up with words to show my respect to this work (my English is not good enough).. because this just has solved one of the biggest fundamental problems in guideline tetris players' mind...
also optimization techniques mentioned are very inspiring as i'm also a programmer.
but then it comes my shameless additional feature request (slap
as we all see, in most official versions, the number of preview pieces shown is usually 1, 2, 3, or 6, but not 10. it brings further restriction that we only see the current piece + hold + the next N of the next pieces.
so.. how many sequences are solvable when only N previews are available, in other words, to make a decision based on 1+1+N pieces so that it's PCable for all possible patterns after N pieces? (further, to choose a position maximizing the possibility)





Ethereal_Intellect 
Jun 23 2017, 12:21 PM

Tetris Novice
Posts: 11
Joined: 13July 12

Well, i guess i'm coming back to this years later with new knowledge (in a few weeks when i have more time) I originally posted a few unsolvable (without hold) sequences back in http://harddrop.com/forums/index.php?showt...4068&st=105(46)  8 Unsolvable sets found 123567 1256 // translated as IJLZOS IJ ZO 123567 1257 // translated as IJLZOS IJ ZS 123567 1267 // translated as IJLZOS IJ OS 123567 1356 // translated as IJLZOS IL ZS 123567 1357 // translated as IJLZOS IL ZS 123567 1367 // translated as IJLZOS IL OS 123567 2567 // translated as IJLZOS JZ OS 123567 3567 // translated as IJLZOS LZ OS I'll try and make a newer more optimized version or use yours as a template or even piece of it. And just so I didn't miss the answer anywhere, we still don't know if it's possible to perfect clear forever right? (In a random official game like Tetris Friends on facebook) I mean some sequences are unsolvable (those 55 you mentioned) but i didn't notice if there was yet an analysis of an algorithm that prepares in advance for their possibility and brings over a hold from a previous bunch to purposely break and prevent them.




1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:
IP.Board © 2021 IPS, Inc.
