Perfect Clear Brute Forcing vs... the Demon Sequence Options

[caffeine]

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.

[Okey_Dokey]

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.

[myndzi]

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