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

2 Pages V  1 2 >  
Reply to this topicStart new topic
> Perfect Clear Finder
Okey_Dokey
post Jun 12 2016, 07:56 PM
Post #1


Tetris Professional
Group Icon
Posts: 577
Joined: 13-May 15



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

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 Download More RAM - get more RAM for free!
User is offlinePM
Go to the top of the page
+Quote Post
caffeine
post Jun 12 2016, 08:16 PM
Post #2


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



Wow, you really went above and beyond on this one. Very thorough and very useful. Thanks for making this.
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Jun 12 2016, 09:26 PM
Post #3


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



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


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Taiga
post Jun 13 2016, 09:22 PM
Post #4


Tetris Novice
Group Icon
Posts: 52
Joined: 27-April 15



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


--------------------
"Practice Makes Perfect Never Give Up Pizza Power!"
User is offlinePM
Go to the top of the page
+Quote Post
baseballboy4296
post Jun 13 2016, 11:54 PM
Post #5


Tetris Apprentice
Group Icon
Posts: 196
Joined: 3-October 09



Wow, this is great. Thanks for sharing!
User is offlinePM
Go to the top of the page
+Quote Post
Swarley
post Jun 14 2016, 01:38 AM
Post #6


King of the Forum
Group Icon
Posts: 28
Joined: 4-February 11



Coolest thing to ever have happened since Belzebub's Nullpomino things.
Great job Misstake, this is awesome.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Jun 14 2016, 06:11 AM
Post #7


Tetris Professional
Group Icon
Posts: 577
Joined: 13-May 15



Thanks, guys! Grin.png
User is offlinePM
Go to the top of the page
+Quote Post
Alexandra
post Jun 25 2016, 05:10 PM
Post #8


Tetris Apprentice
Group Icon
Posts: 143
Joined: 21-March 14



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
User is offlinePM
Go to the top of the page
+Quote Post
farter
post Nov 7 2016, 01:43 PM
Post #9


Tetris Expert
Group Icon
Posts: 302
Joined: 19-April 11



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


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Nov 7 2016, 11:30 PM
Post #10


Tetris Professional
Group Icon
Posts: 577
Joined: 13-May 15



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).
User is offlinePM
Go to the top of the page
+Quote Post
zaphod77
post Dec 6 2016, 01:29 AM
Post #11


Tetris Expert
Group Icon
Posts: 316
Joined: 31-July 09



sega tetris has no kicks at all, and only CCW rotation.
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Dec 24 2016, 02:42 AM
Post #12


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



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


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Dec 24 2016, 09:40 AM
Post #13


Tetris Professional
Group Icon
Posts: 577
Joined: 13-May 15



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).
User is offlinePM
Go to the top of the page
+Quote Post
Shuey
post Dec 24 2016, 10:50 AM
Post #14


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



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.


--------------------
Subscribe to me on YouTube
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Dec 24 2016, 11:39 AM
Post #15


Tetris Professional
Group Icon
Posts: 577
Joined: 13-May 15



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

Also: There's a Tetris Puzzle 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.
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-2018 Hard Drop Community & Forum
harddrop.com is not sponsored or endorsed by The Tetris Company or its subsidiaries.