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 Brute Forcing vs... the Demon Sequence
caffeine
post Jun 11 2016, 12:04 AM
Post #16


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



QUOTE(Okey_Dokey @ Jun 10 2016, 05:48 PM) *

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.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Jun 11 2016, 05:55 AM
Post #17


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



QUOTE(caffeine @ Jun 11 2016, 12:04 AM) *
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.

QUOTE(caffeine @ Jun 11 2016, 12:04 AM) *
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.
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Jun 12 2016, 10:35 PM
Post #18


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



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


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