antimine-android

antimine-android copied to clipboard

the guess-free game generator has some obvious issues, like absolutely abysmal performance with many mines (#407) and rather undesirable side effects on game complexity (#351).

therefore i'd like to propose an alternative mode of operation, shamelessly stolen from https://pwmarcz.pl/kaboom/:

This is a cruel, but fair Minesweeper game:

• The mines are not placed at the beginning, but determined as you play. There is no hidden state.
• If you try to guess, the game will always choose the worst scenario.
• Except when you are forced to guess (there are no safe cells anywhere). Then, guessing is completely safe.
  • You are still expected to select one of the adjacent cells. Select "Allow guessing anywhere" if you want to be able to play elsewhere on the board.

the MIT-licensed code is at https://github.com/pwmarcz/kaboom, so you can simply translate the js to java and be done.

Hi Oswald, I wouldn't want to have this as the only option[^], that's not the game I want to play[^1]. But it would be nice as an option, along with the naive approach (truly random field, just clear 33 on first tap) and the current guess-free algorithm. So let me entertain your suggestion a bit, in the context of big playing fields.

1. If the game state has multiple independent puzzles that require guessing, one should be allowed to guess on each of those, no matter if the probability is ½ on one and ⅓ on another, because in the end you have to guess on each of them. So the proposed algorithm would need to establish the independence. It would be unfair to punish the player for first guessing on the ½ puzzle because the ⅓ puzzle has better odds, but only if the puzzles are independent (solving one won't help solve the other).
2. There are some puzzles where there are solutions with different mine counts, and depending on the game state (density over all unopened tiles, total number of mines remaining) one can make an informed guess or even know the solution. There are some cases to differentiate here:
   1. One can know the solution. The game should only allow the right guess.[^2]
   2. One can't know the solution, and there aren't other, independent puzzles. Is any guess allowed, or just the most probable?
   3. There are currently other, independent uncertain puzzles and you don't know how many mines are in/behind them. So if you take a guess, the algorithm has to make a decision like in 1., but the probabilities aren't certain.

I don't think Kaboom respects all of this. (@pwmarcz?) And I didn't even come to a conclusion on 2.iii.

PS: thanks for reminding me of Kaboom! I am using @freaktechnik's Mines.js for the time being while Antimine doesn't work for me.

[^*]: not that I'm in any position to make decisions here [^1]: occasionally yes, but not all the time [^2]: This can still happen if there are other uncertain puzzles, as long as it's certain how many mines there are in/behind those.

@ossilator That's a good feedback. Once I tried to implement something similar but it was too complex. For now, something I would like to do is to create the minefield using small cells. That would allow it to create safe games way faster. But I can't promise that for now because it's also a complex change that will take some time.

Hi! I wanted to link to Simon Tatham's guess-free generator but I see you're already aware of it.

I don't think Kaboom respects all of this. (@pwmarcz?)

My game allows any guess (on the boundary of revealed fields), it has no notion of probabilities or independent sections of the puzzle (at a point in time, guessing either is globally allowed or it isn't), and it does take the number of mines into account (otherwise it would be possible to get it to a state that is inconsistent with the claimed number of mines on board).

I don't believe that allowing only the most probable guess would make for a good game (or at least it'd be too hard for me to play). Maybe it would be good to allow guessing in isolated sections, but it might be difficult to determine if an isolated section is truly independent, i.e. it's never going to become determined later in the game, even based on how many mines are left.

I don't know what would be a good way of tracking probabilities / independence. For some time I experimented with calculating all possible layouts of boundary mines (using backtracking), but it works well only for small boards.

Hey Pawel, thanks for chiming in! I played some rounds in Kaboom yesterday, for the first time in years, and I think your solution to allow guessing anywhere on the boundary if there are no tiles with probability 0 is good. I have some more thoughts on this but they don't belong in this forum.