Printable Version of Topic

Click here to view this topic in its original format

Forums - Hard Drop - Tetris Community _ Tetris _ Perfect Clear Finder

Posted by: Okey_Dokey Jun 12 2016, 07:56 PM

The Perfect Clear Finder is a Java program that tries to place pieces in a way that results in an empty board. You specify the starting playfield & the piece sequence and the program does the rest. It can handle Hold, Soft Drop and Wall Kicks. The program won't display all possible solutions. Instead, it will show all solutions that differ in either the piece left on hold (grouped in different windows) or the location where the last piece was placed. Start the program by double clicking PerfectClear.bat .

Download: Attached File  PerfectClearFinder.zip ( 127.77k ) Number of downloads: 793

Video:


Limitations
The Perfect Clear Finder can find all solutions of a 4-lines-perfect clear within two minutes or less ... provided it has enough virtual memory (RAM) at its disposal. With lots of J,L,T pieces at the start of the piece sequence it may need more than 1 Giga Byte of memory (with hold there'll be millions of different playfields after 5 placed pieces that may still end up in a 4-lines-perfect clear). So, the Perfect Clear Finder's speed is its strength (in relation to how difficult the actual problem is), but its need for memory is its weakpoint. I cannot guarantee that the program is terminating for a sequence longer than 10 pieces or a matrix higher than 4 rows. Therefore, there's an option to limit the amount of playfields created per ply, but in this case the program may not find all perfect clears. Also note, that the program was tested in a 32-bit environment. For 64-bit Java, it may need even more memory (because a object reference is 8 bytes there instead of 4 bytes). The Batch files (*.bat) will look like java -jar -Xms256M -Xmx1024M whereas -Xms specifies how much memory the program gets at the start and -Xmx specifies how much memory it can use at maximum.

About
The Perfect Clear Finder uses breadth first search. All fields of a ply are stored in a queue. The program processes the queue: for each field in the queue, it tries to place the current piece (or hold piece) in all possible locations (that fullfil the height limitation) and saves the resulting playfields in the next queue. If a playfield was found before, it isn't saved again: The program uses a height-balanced binary search tree to sort the found playfields such that it can swiftly say if a field is already in the next queue or not (e.g. for 1 million stored fields, the program needs only 20 or 21 comparisons). To reduce the memory usage as much as possible, the playfield was encoded in 8 short variables and the queue as a Vector. To reduce the number of saved fields, the program also checks for barriers that spit the field in 2 parts with number of empty cells not divisible by 4 (2 adjacent columns form a barrier if for each row there's at least one filled cell in those 2 columns).

The Perfect Clear Finderô was brought to you by http://downloadmoreram.com/ - get https://youtu.be/q2vWhyQlNI8?t=13s for free!

Posted by: caffeine Jun 12 2016, 08:16 PM

Wow, you really went above and beyond on this one. Very thorough and very useful. Thanks for making this.

Posted by: Shuey Jun 12 2016, 09:26 PM

Dang, this is head and shoulders above your last version!

Posted by: Taiga Jun 13 2016, 09:22 PM

Awesome program Misstake! I love the multiple solutions and high customization it provides, this is truly fantastic Heart.png

Posted by: baseballboy4296 Jun 13 2016, 11:54 PM

Wow, this is great. Thanks for sharing!

Posted by: Swarley Jun 14 2016, 01:38 AM

Coolest thing to ever have happened since Belzebub's Nullpomino things.
Great job Misstake, this is awesome.

Posted by: Okey_Dokey Jun 14 2016, 06:11 AM

Thanks, guys! Grin.png

Posted by: Alexandra Jun 25 2016, 05:10 PM

Blush.png okkidokki Blush.png quality posts always 100%
I've seen the japanese use it Blush.png

you're Blush.png amazing Blush.png Blush.png okkidokki Blush.png Blush.png Blush.png Blush.png Blush.png

Bump

Posted by: farter Nov 7 2016, 01:43 PM

there seems to be a little bug.. found when i'm trying it with sega tetris' power-on pattern.

choose pc after 8 rows, limit to 1000000 fields (to let it finish), hold=off and softdrop=off (don't know whether it's related), input whatever sequence, let it run, it successfully calculates to the end, but seems to get problem generating and presenting the solution list. it prints a block of exception in the console window, arrayindexoutofboundexception i remember..

yeah so how about adding real sega tetris rotation and doing a brute-force solution for sega tetris?

http://www.geocities.jp/arcadon765/tetris.html
http://www.geocities.jp/tetris_denpa/index.html

Posted by: Okey_Dokey Nov 7 2016, 11:30 PM

I was able to reproduce that bug. I have set the maximum sequence length to 15 or 16 in the visualizer (NUM_TURNS = 15). I will fix it sometime and probably also add Sega rotation system (I guess that also means changing the kick-table to TGM if selecting Sega).

Posted by: zaphod77 Dec 6 2016, 01:29 AM

sega tetris has no kicks at all, and only CCW rotation.

Posted by: Shuey Dec 24 2016, 02:42 AM

Hey Okey, I've been working off and on on a project to document every possible solution for clearing fixed spaces, beyond just the scope of the standard 4x10 PCs; I'm also looking into possibilities for fields 4x5 thru 4x9.

How hard would it be to create a separate, modified version of your PC finder for these other field sizes? :-S

Posted by: Okey_Dokey Dec 24 2016, 09:40 AM

It's possible but it takes some effort. For a 9 columns wide matrix you can also fill the most left column with blocks (or most right).

Posted by: Shuey Dec 24 2016, 10:50 AM

Is that the case with 4x5, 4x6, 4x7 and 4x8 as well?

If it's too much work or not worth the effort, I would totally understand. If you do decide to make time to do it, I can't even begin to think of how I could thank you.

The reason I'm asking is because I'm building a Tetris curriculum for kids, and having something that can calculate these possibilities would be a great tool in my pool of resources.

Posted by: Okey_Dokey Dec 24 2016, 11:39 AM

I'll probably do it but I don't have the time in the next few days.

Also: There's a http://tetrisonline.pl/toj_flash/puzzle.html Flash game with the goal to do perfect clears. You can decide in which order the pieces appear. No softdrop though and every placement must clear a line.

Posted by: Shuey Dec 24 2016, 05:42 PM

Thanks for the info! And thank you in advance if you end up working on that alternate version sometime early next year! smile.gif

Posted by: Pineapple Jan 7 2017, 04:19 AM

QUOTE(Okey_Dokey @ Dec 24 2016, 11:39 AM) *
Also: There's a http://tetrisonline.pl/toj_flash/puzzle.html Flash game with the goal to do perfect clears. You can decide in which order the pieces appear. No softdrop though and every placement must clear a line.

Looks exactly like Puzzle mode from Tetris DS. Except with worse music and sound effects.

I actually have an old unsolved problem (that's no longer entirely relevant, because some people here aer too damn clever) that this solver might be able to help with, but I'm not certain if it can in its current form.

So, take this board:


This is the state of play, after 27 pieces have been placed, and the T from the 4th bag is held. Assuming the full power of Guideline Tetris, how many of the 5040 different orders of the next bag allow the board to be cleared? I'd like to exclude the degenerate cases where only 4 lines are cleared (any two of JLT in the first 3 pieces springs to mind; there are probably others), as the intent is to perfect clear on a board seam, which would clear 6 lines from this position.

I know that there is at least one solution, but I cannot remember what it is (as it was several years ago that it was found, and I don't know if the hard drive I was using at the time is in working order or not).

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