Back in 2011, Shuey http://harddrop.com/forums/index.php?showtopic=4068&st=0 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:

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

Edit: in that vein, let's see somebody solve this one:

[o] iosz zsoitj

[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

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:

- http://harddrop.com/forums/index.php?showtopic=7588
- http://harddrop.com/forums/index.php?showtopic=7792

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

Nice, this is good stuff. 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.

Do I win?

Do I win?

Well done. Here is your reward.

I HAVE ALWAYS WANTED THIS AWARD

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

PerfectClear.zip ( 29.41k )
Number of downloads: 135

**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.

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

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):

http://i.imgur.com/SI9szyL.png

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

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.

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.

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.

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.

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.

PerfectClear.zip ( 29.85k ) Number of downloads: 119

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

...

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)

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.

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"

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.

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 . But until then, you've created some serious inspiration as far as I'm concerned .

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

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.

Awesome, thanks for the info Okey!

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 nmber 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:

Clever. A similar thought had also occurred to me, but I wasn't sure if the pros of doing such a check outweighed the cons of having to do a check in the first place. I suppose if space is your problem, then it's worth it for sure.

Another thing I thought about was how after 1 line clear, nothing can be filled on the top row. After 2, nothing on the top 2. After 3, only the bottom row can have filled cells. Of course that would entail storing at least a byte, which may defeat the purpose. On second thought, how many line clears that are done can be inferred from the ply level and how many filled cells are on the playfield.

Another idea was to store the entire game state in a 64 bit double.

A similar thought had also occurred to me, but I wasn't sure if the pros of doing such a check outweighed the cons of having to do a check in the first place. I suppose if space is your problem, then it's worth it for sure.

Actually, this barrier test can be done so quickly, that it's always worth it. If a playfield can be recognized as invalid prematurely, the program doesn't have to create all fields resulting from dropping the next piece, whereas some of these fields may still be valid and have 'children' themselves. Even checking kicks instead of considering every deepdrop location valid will speed up your program a little, although the kick test is pretty time consuming.

Another thing I thought about was how after 1 line clear, nothing can be filled on the top row. After 2, nothing on the top 2. After 3, only the bottom row can have filled cells.

Actually, I did that. I reduced the playfield height (array length) after each line clear. However, I did that because I thought it would simplify programming, not to save memory space. In Java, each class object needs a multiple of 8 bytes, so reducing the length of an array doesn't usually result in less memory used.

The space-division thing is a good way of pruning branches early... I use it when I'm solving PCs myself. I believe I posted also about some parity considerations a while back that might allow for similar exclusion of piece placements. As to the comment about using an integer and bitwise operations for collision detection, I came up with an idea while talking to Caffeine about the AI block battle competition which allows for using lookup tables to identify all piece placements for a given field shape; he wrote his solution in Java too, so maybe he can share the code? It's definitely a speed/memory tradeoff, but it seemed to have a significant speed impact.

Fake edit: thread: http://harddrop.com/forums/index.php?showtopic=5465 (appears I mentioned the subdivision thing here too)

I have a vague idea that you can reduce your search area significantly by identifying which piece parity combinations are valid before even working with the shapes/matrix...

Powered by Invision Power Board (http://www.invisionboard.com)

© Invision Power Services (http://www.invisionpower.com)