antimine-android
antimine-android copied to clipboard
lucasnlm
Implement game generator without guessing
Currently the generated games may have guessing situations. The game generator should be updated to avoid guessing situations.
This feature is now available on 7.3.0 release.
I've implemented a brute force algorithm and a interface to easily add new implementations. They are both here.
I have 8.3.0 and the game generated this which required guessing.
Note this is at the edge of the board.
@luke-clifton The current implementation was changed to try find games without guessing. If it takes too long to find a 100% no-guess game it will stop searching. I did it to have a better UX (it usually happens when a game has too many mines).
What's the maximum expected mine density that's safe? Here is a screenshot of a guessing scenario on a 30 mine standard field.
@petersohn Depending on how my mines it must place and the area available it's impossible (or it take too much time) to find a 100% solvable level. So it fails in some cases. I think that is what happened to you. 😞
I looked at the code, and the current no-guessing algorithm is actually not what I want. It only accepts a map if it can be solved by brute-force, i.e. by long-clicking on the numbers. This will get boring pretty fast. I like maps where I have to make some more advanced deductions, but I don't have to guess randomly. This is actually pretty rare.
So I threw together a more sophisticated algorithm. I'm not fluent in either Kotlin or Android development, so instead of creating a PR, I made a simple Python emulator / implementation, here: https://github.com/petersohn/mine-solver . Using this or something similar for the no-guessing algorithm would result in a higher chance of accepting a map, and also in possibly more challenging, but still solvable, maps. There is also a description of the algorithm in the readme.
Note that I threw this together in one afternoon, so there might be errors. They work fine for some tests that I tried it on. There are also possibilities for performance improvements, which might be important when running it multiple times in a row on an Android.
Another far simpler solution would be to just allow players to win if all mines are marked correctly, but not all squares are revealed. Since it could be seen as cheating (but it would require far more time to solve this way then the normal way, hence not being a time-competetive method), it could be a toggle-able option in the settings.
@petersohn Sorry for take so much time to implement your suggestion. 😓 I got your code, but I'm still working on fix some render issues and adding support to opengl.
I hope to improve the generator soon.
@BloodRaven0 It's valid as a toggle-able option. As default It may confuse some users that aren't used to this.
@lucasnlm Yeah, I wouldn't have it as the default option either, even though I've seen some minesweeper apps leave it on as the default, and even have no option to turn it off. Still, it's not a perfect solution, because sometimes you might have a guessing scenario which is preventing you from revealing a larger part of the field, and this method can't help you with that.
I just experienced an end game guessing condition with guess free on. Though I don't know how to put some details here.
Version 12.4.2
Still have guessing situation even though 'No guessing' mode is on. Thanks for the overall awesome game implementation!
