I've begun work on a perfect clear finder, unimaginatively called pcf. It uses a different strategy than knewjade's sfinder; instead, it is similar to knewjade's perfect clear enumeration algorithm (gist.github.co.... This hasn't been integrated into Cold Clear yet, but I plan to do that soon.
For this video, I hacked together a version of pcf that works with Zetris. Zetris is well-optimized to using perfect clear finders and gives them about 2 seconds to calculate the next perfect clear. This is more than enough time for pcf to evaluate every 4-line perfect clear it cares to examine, even with only one thread. Since the search is deterministic, has enough time to complete without being interrupted, and I modded the game to give both players the same piece sequence, both bots in this video decide to do the same perfect clear every time.
Description of how pcf works:
1. Determine the height and number of pieces required to do a perfect clear based on the board. Limit our view of the queue to that many pieces, plus one if hold is allowed.
2. Find the lowest of the leftmost empty cells below the height. Find every placement that fills that cell, does not overlap the board, and uses a piece in the set of remaining pieces (regardless of queue order). A placement may split its piece across lines.
3. Check that the resulting placement combination is still viable. A placement combination is viable if there is some order that the placements can be made assuming that the parts of the board not filled by a placement in the combination are filled and pieces can teleport.
4. If the board isn't a perfect clear, then for every remaining placement combination, repeat from step 2. Otherwise, proceed to step 5.
5. Find all the placements in the combination that can be placed next according to the next piece, hold piece, and whether the position is reachable according to the game rules. Repeat until either the perfect clear is solved or no solution is found.
6. If, after all that, no perfect clear solutions are found, raise the height by 2 lines and try again.
Deciding whether a position is reachable in step 5 has the potential to be the most costly part of the algorithm considering the intricacies of the Super Rotation System. pcf gets around this by only checking for hard drop, tucks without rotation, and simple spins without movement. This gives most of the benefits of SRS while remaining fast to calculate.
Due to the overwhelmingly large number of placement combinations that become possible as the number of pieces required increases, this strategy is likely not viable for finding perfect clears at height 6 or higher. Thankfully, my main purpose in developing this is to make the most powerful PC loop bot, and four-line perfect clears are common enough that this strategy works well.
Played on April 15, 2020.
Zetris is developed by mat1jaczyyy, building on the work of misakamm and knewjade.
Zetris' RU-vid channel: / @zetris
pcf's source code: github.com/Min...
16 окт 2024