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

2 Pages V  1 2 >  
Reply to this topicStart new topic
> Perfect Clear Brute Forcing vs... the Demon Sequence
caffeine
post May 19 2016, 05:38 PM
Post #1


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



Back in 2011, Shuey posted a series of sequences that HD members would then solve. For every puzzle that he posted, someone would eventually find a solution. These sequences could be starting sequences or something that could be arrived at midway through the game. It wasn't known if every legal sequence could be solved, but for a while it looked that way.

User perfectclear then proposed the following:

IPB Image

Myndzi offered the following sequence (that can be arrived at in a standard SRS game):

QUOTE(myndzi @ Dec 17 2011, 04:44 PM) *
Edit: in that vein, let's see somebody solve this one:
[o] iosz zsoitj


I spent many hours trying to come up with a solution this evil sequence of pieces, but I couldn't find one! Yesterday, I decided to solve this sequence once and for all. I wrote a program to try every possible move, and do so for every possible combination of holds.

A perfect clear can be done in 10 pieces seemingly all of the time with SRS rules. Sometimes it can be done in 5. Hold gives us the ability to change the piece sequence. At any point in the sequence, we can either hold or not hold: two options. Given of 10 pieces, we then have 2^10 possible sequences.

Next, it plays out every possible move, and then every possible move after that for each of the ones before. Normally, 10 ply would be intractable (somewhere around 20^10 possibilities). However, we can eliminate the vast majority of possibilities if we know a little bit about how the game works. First off, with a 10 piece PC, we never will stack over the 4th row from the bottom. For that reason, we can simulate these games in a 4x10 matrix. There are only so many possible ways each piece can fit into this box.

Specifically:

38: I
27: O
42: S/Z
84: L/J/T

Moreover, a piece is only deemed legal if there is no collision with the current matrix at that position and it has something below to land on. This shortened the search space by a great deal. The other thing that makes this possible to do is how, as soon as there is no room left to fit a legal position, it trims off that branch.

I did not take the time to encode wall kicks, but this was not necessary. I looked at all positions that can be "deep dropped." The set of all solutions with wall kicks are inside the set of all deep drop solutions.

7,704,684,762 searches made it all the way to 10 ply. It only checked for a perfect clear after that point. It did this for all possible sequences after holding was factored in. It found 18,974 solutions with deep drop. Here are a few examples:









As you've probably noticed, they all involve a vertical T placement that cannot be gotten to with SRS rules. In fact, all of the solutions the solver found included this illegal placement. For this reason, I do not believe it is possible to perfect clear... the demon sequence.

Edit 5/20/16: corrected a few errors.

Update 4/26/17:

This idea has been greatly expanded on thanks to:
User is online!PM
Go to the top of the page
+Quote Post
Shuey
post May 19 2016, 05:41 PM
Post #2


Tetris Expert
Group Icon
Posts: 409
Joined: 12-November 10



Thanks so much for verifying this info caff!!! Good to finally have closure on this one! smile.gif


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Kitaru
post May 20 2016, 01:17 AM
Post #3


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



Nice, this is good stuff. smile.gif Thanks for taking the initiative, caff. This feels analogous to reaching dead ends when trying to solve Pentominos; instead of the field space being incorrectly manipulated such that it would require a duplicate of a piece, we're left with the correct space left unreachable.


--------------------
My Backloggery
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post May 23 2016, 02:48 AM
Post #4


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



Do I win? Grin.png


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
caffeine
post May 23 2016, 02:59 AM
Post #5


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



QUOTE(myndzi @ May 22 2016, 09:48 PM) *

Do I win? Grin.png


Well done. Here is your reward.

IPB Image
User is online!PM
Go to the top of the page
+Quote Post
myndzi
post May 23 2016, 09:56 PM
Post #6


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



I HAVE ALWAYS WANTED THIS AWARD


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post May 26 2016, 09:41 PM
Post #7


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



Based on caffeine's description I also made a perfect clear finder.

Attached File  PerfectClear.zip ( 29.41k ) Number of downloads: 26

edit: new improved version with graphics: http://harddrop.com/forums/index.php?showtopic=7588

It has 2 upgrades:
  • With the help of a height-balanced binary search tree, the program checks if an equal-looking field has been found before. This means that the program needs to check less nodes in the decision tree which helps to save time (the program finishes after about 1 minute). On the other hand, storing the found fields consumes much memory (up to 1 GB as far as I can tell). Maybe the memory usage could be halved by converting the short[4] array into 4 seperate short variables (each line is stored in a short) but I am too lazy to do that.
  • The program checks for solutions involving softdrop, whereas it is able to handle SRS kicks.
The source code is included in the download. The usage of the program is text-based only (batch file or command prompt). A corresponding command line call should look as follows (see perfectclear1.bat):

CODE
java -jar -Xms256M -Xmx1024M PerfectClear.jar oioszzsoitj

Xms and Xmx increase the available memory for Java. After the piece sequence, a further argument can be specified in form of a 1-digit number (0,1,2). This tells the program, if it should check for harddrop only (0), softddrops including kicks (1) and deepdrops (2). Softddrops is the standard. Deepdrops is not recommended.

Pretty sure that the program works correctly with deepdrops: I get pretty much the same number of paths (solutions) as caffeine for the 'demon sequence'. More precisely, if I execute the loop twice if the active piece equals the hold piece, my number of paths (9,487) is exactly the half of caffeine's number of solutions (18,974). For softdrop and kicks I cannot guarantee the correctness, but it recognizes all kicks I've checked. More precisely, for softdrops it does a backwards check. It starts in the deep drop location and tries to reach the surface (location reachable with harddrop) within 3 moves (left, right, up, rotate ccw/cw with reversed kicks). A higher number of moves can be specified by editing a constant in the source code, but I think 3 is enough.

The program will tell you only one solution for each different piece left in hold at the end. The output looks like this:

CODE
try to find perfect clears for the sequence TIOSZZSOITJ (using only harddrop)
depth 0 finished in 0 ms , valid fields = 51 , mergings = 0
depth 1 finished in 0 ms , valid fields = 1039 , mergings = 356
depth 2 finished in 31 ms , valid fields = 16767 , mergings = 4970
depth 3 finished in 328 ms , valid fields = 191094 , mergings = 65508
depth 4 finished in 2203 ms , valid fields = 812433 , mergings = 713167
depth 5 finished in 8282 ms , valid fields = 2064822 , mergings = 1402958
depth 6 finished in 7500 ms , valid fields = 1864246 , mergings = 1221793
depth 7 finished in 4750 ms , valid fields = 755254 , mergings = 409382
depth 8 finished in 1031 ms , valid fields = 21401 , mergings = 21381
depth 9 finished in 31 ms , valid fields = 6 , mergings = 14

Found a solution with 47 different paths (O on hold)
__________
__________
__________
__________
hold = T , paths  = 1
__________
__________
__________
XXXX______
hold = T , paths  = 1
__________
XX________
XX________
XXXX______
hold = T , paths  = 1
__________
XX________
XX____XX__
XXXX_XX___
hold = T , paths  = 1
__________
XX___X____
XX__XXXX__
XXXXXXX___
hold = T , paths  = 1
__________
XX___X___X
XX__XXXXXX
XXXXXXX__X
hold = Z , paths  = 9
__________
XX_XXX___X
XXXXXXX__X
hold = Z , paths  = 9
__________
XX_XXXXX_X
hold = O , paths  = 9
___XXXX___
XX_XXXXX_X
hold = O , paths  = 9
___XXXXXXX
XX_XXXXXXX
hold = O , paths  = 9
hold = O , paths  = 47

...

found solutions with 6 different pieces on hold and 150 paths in total
FINISHED the whole calculation in 24156 ms

Usage directly in Eclipse should look like this (run -> run configurations):
IPB Image


-----------------------

Note that the demon sequence requires a shape (O,I,S or Z) to appear 3 time. So it is still an open question, if there's a not-perfect-clearable sequence that consists of parts of only 2 bags. I am pretty sure that starting with a perfect clear is always possible if the first 11 pieces are known. Of course one can't verify this assumption because there're millions of different piece orders regarding the first 11 pieces.

I would also like to know how long it took caffeine's program to brute-force the sequence.
User is offlinePM
Go to the top of the page
+Quote Post
caffeine
post May 26 2016, 10:06 PM
Post #8


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



Wow! Very cool. Also, thank you for double checking my result. It's a relief to hear I didn't mess up too bad. I think I know why I got 2x solutions. In my "hold permutator" class, I was keeping the held piece at the end of the sequence. Since I didn't look too carefully, I was computing 2^11 sequences instead of 2^10 (half being redundant).

Great idea of storing and checking if you've seen the "state" before already. The full search on my version took about 1 hour on a single core, so I imagine it would take around 30 minutes without the redundant sequences.
User is online!PM
Go to the top of the page
+Quote Post
Shuey
post May 26 2016, 10:08 PM
Post #9


Tetris Expert
Group Icon
Posts: 409
Joined: 12-November 10



Any tips on configuring the heap sizes? I've tried this multiple times and it keeps crashing after depth 4.

I am running Windows 7 Pro 64-Bit with 16GB of RAM.


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post May 27 2016, 05:53 AM
Post #10


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



QUOTE(Shuey @ May 26 2016, 10:08 PM) *
Any tips on configuring the heap sizes? I've tried this multiple times and it keeps crashing after depth 4.

I am running Windows 7 Pro 64-Bit with 16GB of RAM.

Yeah sorry. I didn't test the program with enough sequences. Most sequences will make the program run out of memory (especially with T,L,J pieces early on). The -Xmx1024M argument specifies how much memory the program can allocate at most (and the -Xms256M specifies with how much memory the program starts). On WinXP I couln't allocate more than 1440 MB and on Win7 not more than 1735 MB. You can see how many memory the program is currently in use by looking for the java.exe process in the task manager.

I made a small change to the program. It now checks for a third argument. If it is specified as 0, then the program will stop at a depth after 1,000,000 fields are created.

Attached File  PerfectClear.zip ( 29.85k ) Number of downloads: 18

edit: new improved version with graphics: http://harddrop.com/forums/index.php?showtopic=7588

For example the command line

CODE
java -jar -Xms256M -Xmx1024M PerfectClear.jar jizlotstljs 1 0

creates the following output

CODE
try to find perfect clears for the sequence JIZLOTSTLJS (using softdrop and kicks) (field limit = 1000000)
depth 0 finished in 0 ms , valid fields = 51 , mergings = 0
depth 1 finished in 16 ms , valid fields = 1365 , mergings = 373
depth 2 finished in 62 ms , valid fields = 39787 , mergings = 9501
depth 3 finished in 859 ms , valid fields = 397643 , mergings = 252803
depth 4 finished in 2704 ms , valid fields = 1000017 , mergings = 262181
depth 5 finished in 2953 ms , valid fields = 1000010 , mergings = 536258
depth 6 finished in 4484 ms , valid fields = 1000000 , mergings = 799838
depth 7 finished in 4391 ms , valid fields = 659646 , mergings = 518879
depth 8 finished in 1140 ms , valid fields = 36055 , mergings = 83852
depth 9 finished in 16 ms , valid fields = 5 , mergings = 76
...

Without that 1,000,000 fields limit the program would be stuck at depth = 4 or 5 (more than 10 million fields at depth 5) before it tells you it ran out of memory.

CODE
java -jar -Xms256M -Xmx1735M PerfectClear.jar
jizlotstljs 0
try to find perfect clears for the sequence JIZLOTSTLJS (using only harddrop)
depth 0 finished in 0 ms , valid fields = 51 , mergings = 0
depth 1 finished in 0 ms , valid fields = 1345 , mergings = 356
depth 2 finished in 78 ms , valid fields = 37536 , mergings = 8184
depth 3 finished in 764 ms , valid fields = 367508 , mergings = 198719
depth 4 finished in 13104 ms , valid fields = 4123587 , mergings = 1008247
depth 5 finished in 75551 ms , valid fields = 14706398 , mergings = 7075936
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at oki.pc.Field.<init>(Field.java:41)
        at oki.pc.Field.createField(Field.java:650)
        at oki.pc.PerfectClear.process(PerfectClear.java:63)
        at oki.pc.PerfectClear.execute(PerfectClear.java:95)
        at oki.pc.PerfectClear.main1(PerfectClear.java:164)
        at oki.pc.PerfectClear.main(PerfectClear.java:313)

So yeah, I underestimated how many different playfields could arise in a 4x10 matrix with half cells filled. I thought the problem would be rather running time than memory usage. I consider the program a fail, and won't be working on it anymore. Theoretically with not so much programming effort one could make it more depth-first search than breadth first search, but nah.
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post May 27 2016, 08:12 PM
Post #11


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



You might try solving the 'demon sequence' with every piece in hold, but I imagine you'll find solutions. If you have nothing in hold, I'm not sure it's fairly representative of midgame state, but it's certainly possible. I'm inclined to believe that an arbitrary (or no) piece in hold will make the sequence solvable, and my gut feeling is that this also means there is no sequence that is unsolvable given the right hold piece.

It definitely proves that not EVERY scenario is solvable, however, which was the only intent. It's a less interesting question to me whether there is some sequence which is unsolvable for any given hold state, since that's not a requirement of answering the question "is every state perfect clearable"


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Jun 10 2016, 01:02 AM
Post #12


Tetris Expert
Group Icon
Posts: 409
Joined: 12-November 10



Okey_Dokey: A friend of mine (Jason - he's 34) has been coding since he was about 10, and I showed him the code and details you posted about it. I was hoping that he could take a look at your source and maybe figure out how to make it run all levels without crashing. It was a short, interesting conversation:

QUOTE
Jason: I looked at the code the other day. That's actually a really complicated algorithm. That dude knows what he's doing. If he is planning on coding for a living, he'll have no problem doing well for himself. I couldn't build that even if I spent the entire day on it.

Shuey: Dude, that's surprising! Since I'm not a coder and don't have the faintest idea of what it takes to write a program like that: Why is it so difficult (especially for someone like you who's coded for years)?

Jason: Even before you consider the code, it's just a complicated procedure. Since I'm not familiar with Tetris like you guys, I thought a perfect clear meant getting a Tetris.

I know how to make it fast, but it would have to be re-written.

My ideas would be to:
1) use Go instead of java and do some massive parellelization
2) treat each row as a 10-bit integer and bitwise compare the active piece to determine valid drop locations. That would make it really fast. And it would get faster the more you used it, because you would fill the cache.

Eventually it would be able to calculate every possible PC from whatever you fed it, and it would be virtually instant.


Not sure if that adds anything positive or negative to what you've accomplished so far, but I wanted to share it just in case.

Prior to me telling him about it, I was:
1. Amazed at how powerful and detailed your program is, especially for how small and self-contained it is.
2. Surprised that nobody has tried to do something like this before now!

I hope somebody WILL build a complete PC solver for the bag randomizer someday smile.gif. But until then, you've created some serious inspiration as far as I'm concerned Wink.png.


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Jun 10 2016, 01:13 AM
Post #13


Tetris Expert
Group Icon
Posts: 409
Joined: 12-November 10



No wonder why you can code so well! You've got decades of experience compared to most people! ;P
IPB Image


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Jun 10 2016, 10:48 PM
Post #14


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



Halo.png Actually, I am way too slow to code for a living. Height-balanced binary search tree is a concept that everybody who studied informatics or mathematics should know about and I didn't write the class myself. The matrix encoded as short array/variables is necessary because boolean arrays are so big in Java.

Contrary to a previous statement, I worked a bit further on the program. I could half the number of valid playfields by checking for a barrier, that splits the playfield in 2 parts whereas each part's number of empty cells must be divisible by 4. I came up with only one easy/decent way to look for barriers: 2 adjacent columns form a barrier when for each row there's at least one filled cell in one of the 2 columns. Example:



I have began to write a small program that visualizes the perfect clears and let you specify the starting playfield (in case you don't want to start with an empty field). I will post the program this weekend.
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Jun 10 2016, 10:52 PM
Post #15


Tetris Expert
Group Icon
Posts: 409
Joined: 12-November 10



Awesome, thanks for the info Okey!


--------------------
Subscribe to me on YouTube
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.