smack42 / colorfill Goto Github PK

Hello!

First, I want to congratulate you on your program! Personally, I consider it the best Flood-It implementation playable on desktop PCs. 👍🏻

But to get to the reason I'm writing you: I've been working on and off again on my own version of a Flood-It clone with an included solver (Flolle/terminal-flood). I wasn't originally intending to upload it to GitHub, but then I thought "What the hell, why not?". Even though I spent quite a bit of time optimizing it, it's still a bit slower than your program, which is OK as you seem to be more willing to write low level performant code than I am. I did however find one thing that might be of use to you: A fast inadmissible heuristic that's still able to find relatively close to optimal results.

To give two examples: My implementation of A* with the Puchert admissible heuristic when run single-threaded needs about 48s to finish the pc19 dataset, while my inadmissible heuristic needs about 8.5s and manages a score of 20189. Additionally, my inadmissible heuristic when using 12 threads needs less than 25min to finish the floodtest dataset with a score of 1992612. I did a bunch more benchmarks with additional datasets, you can check them out if you want.

The basic idea for the heuristic is based on the Puchert admissible heuristic, the difference being that you don't do color blind moves, but instead only take the two most promising colors. The basic rundown is:

1. if more than half the fields are already taken over, just use the admissible heuristic (I found this to improve performance both in regards to time and the "optimality" of the found solutions, might be implementation dependent)
2. if we can eliminate colors, do that
3. if we couldn't eliminate colors, there are two options
   • if there are two or less neighbor colors, just take over all the neighbors
   • otherwise, take the two colors that give access to the most new neighboring fields
4. repeat starting from step 2 until the whole board is taken over

You can check out how I implemented this exactly in my project if you want, the code for the heuristic is in the file Strategy.kt. I implemented a couple more heuristics, maybe they are of interest to you too. I'm using the same license for my project as you do, so there shouldn't be any problems regarding that.

I'm mainly proposing this new heuristic as a way to have pretty good solutions available when playing the game with big boards. While you made great strides in regards to the performance of the Puchert heuristic, it's still quickly reaching its limits once you get to board sizes above 20x20 with 6 colors for example. The new heuristic would stay usable in terms of time needed to compute solutions a while longer.

I have looked a bit into your code, and while you have nice sub-optimal solvers, the exhaustive search you're doing is a bit slow.
Now, the "true" reason why I came here is because my brother and I are doing something similar (aaronpuchert/floodit). It even has the same license, so you can just rummage through it.
I've done some more work locally (mostly merging the master branch and the performance branch) and the resulting program took about 4 seconds on average for each of the codegolf grids, which would mean ~110 CPU hours in total (that was on a Phenom II x4 965).
From the partial runs I did, I'd expect around 1 986 000 moves for the 100 000 grids.

We use an A*-type algorithm with a heuristic similar to tigrou's (but actually admissible) and move pruning similar to Jump-Point Search.