smack42 / colorfill Goto Github PK
View Code? Open in Web Editor NEWColorFill - yet another Flood-It clone (game and solver algorithm)
Home Page: https://github.com/smack42/ColorFill/wiki
License: GNU General Public License v3.0
ColorFill - yet another Flood-It clone (game and solver algorithm)
Home Page: https://github.com/smack42/ColorFill/wiki
License: GNU General Public License v3.0
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.
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:
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.