search

Flowit-Game / Flowit

Minimalistic puzzle game
GNU General Public License v3.0
77 stars 7 forks source link

Show best possible #40

Closed vertigo220 closed 1 month ago

vertigo220 commented 7 months ago

Given that a big part of the challenge of this game is to do each level in as few moves as possible, it would be nice to know what that actually is. Often it's fairly clear that I've done the best possible, but sometimes it's not, and it would be nice to know if I have or not so I know whether I should keep trying. It wouldn't even need to say the number of minimum moves, as some might not like that as it could help strategize. It could simply show a star or something when a level is complete using the minimum number, i.e. when the best equals the minimum (that also means if this were added, when looking at previously beat levels, any that qualify would show a star, allowing users to go through and check if any can be done better).

ByteHamster commented 1 month ago

I just added the feature to show the best possible number of steps. This works for all levels from the "easy" pack and for many levels from the other packs. To give best possible steps for all levels, I need a stronger computer (or a better solver).

CC @ywnico @HybridAU in case you want to add this to your ports :)

vertigo220 commented 1 month ago

Is this something that can be crowdsourced? Can you provide something that users can run to crunch the numbers, so to speak, and help determine all the best solutions? I have a fairly powerful computer and wouldn't mind helping.

ByteHamster commented 1 month ago

Is this something that can be crowdsourced?

I don't think so.

I believe one can mathematically prove that Flowit is NP complete, which basically means that it is very hard for computers to solve. Essentially, in the general case one cannot get much better than testing all combinations. To test a level with 7 actions and 30 steps, it needs to check about 7^30 states. Even if the PC tests 100 million states per second (which is way too much), it will take about 7 billion years to test all of them.

With a good solver containing a bunch of heuristics, it is possible to solve some of the levels more quickly. I implemented a branch&bound solver, which made it possible to solve another 6 levels. There are still a lot of algorithmic opportunities, though. I might talk to a colleague who did his PhD on solving these kinds of problems.

ywnico commented 1 month ago

It's definitely not my field, but just wanted to chime in to agree with ByteHamster as well. I was discussing this with someone a while back and came to the same conclusion, that conclusively proving the minimum moves of the more complex levels is likely not possible. But indeed maybe with good enough heuristics one could determine some good solutions that are rarely beaten by humans.

I think this is not a bad thing though; this complexity is what makes the game so fun and intriguing. @ByteHamster , I admire you so much for making this game, it's a real masterpiece.

I'll update my port soon. Edit: done

ByteHamster commented 1 month ago

But indeed maybe with good enough heuristics one could determine some good solutions that are rarely beaten by humans.

I don't really want to add heuristic solutions because that could confuse users when they get better than the minimum. For the ones that do have a solution in the levels file (156 out of 183, now), it is a minimal solution :)

I admire you so much for making this game, it's a real masterpiece.

Thanks, that made my day :)

Edit: done

Awesome, thanks!