HOME WORLD FORUMS WIKI VIDEOS
8162 members and stacking!
     Welcome guest, please login or sign up

2 Pages V  1 2 >  
Reply to this topicStart new topic
> Perfect Clears
theRealMadridcf
post Mar 5 2017, 07:57 PM
Post #1


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 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.


Results

Hold, soft drop and SRS wall kicks
With 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 drop
With 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 best-first 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:
Attached File  Perfect_Clears.zip ( 23.47k ) Number of downloads: 67

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.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Mar 5 2017, 10:59 PM
Post #2


Tetris Expert
Group Icon
Posts: 419
Joined: 13-May 15



Very cool Thumbs Up.png 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 4-line 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?
User is offlinePM
Go to the top of the page
+Quote Post
caffeine
post Mar 5 2017, 11:19 PM
Post #3


Tetris Grand Master
Group Icon
Posts: 1,721
Joined: 27-June 09



Nice work. Very interesting, especially the non-symmetrical PCs. Good idea on using a heuristic to solve most cases faster
User is offlinePM
Go to the top of the page
+Quote Post
theRealMadridcf
post Mar 6 2017, 12:16 AM
Post #4


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 15



QUOTE(Okey_Dokey @ Mar 6 2017, 12:59 AM) *

Very cool Thumbs Up.png 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:
Attached File  unsolved_soft_drop.txt.zip ( 158.31k ) Number of downloads: 49


QUOTE(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 7-bag 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 non-symmetrical PCs. Good idea on using a heuristic to solve most cases faster

Thank you.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Mar 6 2017, 06:24 AM
Post #5


Tetris Expert
Group Icon
Posts: 419
Joined: 13-May 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. smile.gif

QUOTE(theRealMadridcf @ Mar 6 2017, 12:16 AM) *
But the result was only for sequences which can come with 7-bag 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.
User is offlinePM
Go to the top of the page
+Quote Post
Blitz
post Mar 6 2017, 06:10 PM
Post #6


Tetris Specialist
Group Icon
Posts: 229
Joined: 20-April 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 4-line 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 4-line 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 4-line 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?
User is offlinePM
Go to the top of the page
+Quote Post
theRealMadridcf
post Mar 7 2017, 04:27 PM
Post #7


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 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.
User is offlinePM
Go to the top of the page
+Quote Post
Blitz
post Mar 9 2017, 08:35 PM
Post #8


Tetris Specialist
Group Icon
Posts: 229
Joined: 20-April 12



When I think about it, the piece you end up with in hold does not have to be of the same kind that you started with as long as it is either J, L or T. For example you can start with a T in hold and end with either J or L in hold.

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? If there are, is it possible to encounter any of the non PC'able sequences immediately after any of those opening sequences? If that's possible, then we have proven that infinite 4 line perfect clearing is impossible right?
User is offlinePM
Go to the top of the page
+Quote Post
theRealMadridcf
post Mar 12 2017, 02:56 PM
Post #9


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 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.
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Mar 16 2017, 03:31 AM
Post #10


Tetris Grand Master
Group Icon
Posts: 1,926
Joined: 26-June 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 smile.gif

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?


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
theRealMadridcf
post Mar 19 2017, 01:40 PM
Post #11


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 15



QUOTE(myndzi @ Mar 16 2017, 05:31 AM) *

I'm not sure if you caught this thread: http://harddrop.com/forums/index.php?showtopic=5465

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.
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Mar 20 2017, 03:00 AM
Post #12


Tetris Grand Master
Group Icon
Posts: 1,926
Joined: 26-June 09



Sorry, I misspoke. I was wondering if there were any sequences which followed those rules that were perfect clearable. I didn't mean to imply that all impossible sequences matched.


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
theRealMadridcf
post Mar 20 2017, 09:25 PM
Post #13


Tetris Novice
Group Icon
Posts: 13
Joined: 19-March 15



There aren't that kind of sequences with 7-bag randomizer. All sequences which follow those rules are not PC'able with guideline settings.
User is offlinePM
Go to the top of the page
+Quote Post
farter
post May 28 2017, 08:02 AM
Post #14


Tetris Specialist
Group Icon
Posts: 295
Joined: 19-April 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 PC-able for all possible patterns after N pieces? (further, to choose a position maximizing the possibility)


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
Ethereal_Intellect
post Jun 23 2017, 12:21 PM
Post #15


Tetris Novice
Group Icon
Posts: 11
Joined: 13-July 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

(4-6) - 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.
User is offlinePM
Go to the top of the page
+Quote Post

2 Pages V  1 2 >
Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 

©2009-2017 Hard Drop Community & Forum
harddrop.com is not sponsored or endorsed by The Tetris Company or its subsidiaries.