Proposal for fast inadmissible heuristic that gives good solutions

[Flolle]

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.

[smack42]

Thank you very much for your kind words on my program! It's nice to meet somebody else interested in this little topic.

I've read your proposal with great interest and will have a closer look at your program as well. You're right, the optimal strategy is quite demanding with regards to resources (time and memory). For me personally, the optimal solver is the most interesting aspect, because this is the particular strength of the computer algorithm vs. a human player who can find optimal solutions by luck or skill sometimes. In the game it's nice to have an authority to tell the player: this solution you've found is perfect or not.

I'm going to experiment with your code and algorithm ideas. You are also invited to contribute some code to ColorFill if you like to

[Flolle]

I understand. Having guaranteed optimal solutions is indeed an alluring proposition, and definitely preferred whenever possible. But an optimal solution does have limited benefits when you can't compute it due to time/memory constraints. 😉

I might take you up on that offer to implement the heuristic in your program myself, but it won't be anytime soon. For now, I'm still working on terminal-flood here and there when I have free time and after that I already have some plans for a different/not related new side project.

In any case, I look forward to any and all future performance optimizations that you manage to find/develop for your optimal solver.

[smack42]

In the last few days I could spend some time to work on this program again.

I tweaked the optimal solver AStarPuchertStrategy to run slightly faster and started to implement AStarFlolleStrategy, which is based on the ideas that you described here.

There are some minor modifications from "terminal-flood" InadmissibleSlowStrategy, some are accidental and others on purpose. It's running quite fast already and finds good solutions (mostly optimal ones) but for sure there is potential for improvement in my implementation...

[smack42]

AStarFlolleStrategy is included in release 1.3.0