wingos80 / minesweeper_solved

A semi-full recreation of the game minesweeper made in Python using Pygame, with a solver...
1 stars 0 forks source link

Allow solver to select no-neighboured tiles #5

Open wingos80 opened 2 months ago

wingos80 commented 2 months ago

Add logic to add distant tiles to the unknown vector if neighbouring tiles of revealed tiles are uncertain, e.g. $0.2 < x < 0.7$. Really useful when the cells neighbouring revealed cells cannot be deterministically solved, i.e. it's impossible to know exactly where/how many bombs are in those cells.

Could do something like:

  1. guess naively likelihood of bombs in the far cells (cells that are unexplored and do not neighbour a revealed cell)
  2. compare that likelihood with likelihoods (solution from solving LS) of the neighbour cells
  3. If far cells have lower likelihood, pick random cell in far cells. Otherwise pick lowest cell in neighbours.

Equivalently, adding the far cells to the solution vector, setting the value of these cells to be $n{bombs}/n{FarCells}$, then selecting the cell with the lowest value. Computing $n{bombs}$ could be done in different ways, one of the way is to set $n{bombs}$ equal to total number of bombs undetected, or to set $n_{bombs}$ to be total number of bombs undetected - Sum($x$) ... etc.

wingos80 commented 1 month ago

Added functionality with commit 4d91fd7

Number of cells in far cells assumed to be: $MINES - N{flags} - \Sigma x{informed}$. Did not prioritize selecting far cells closest to the revealed cells, this might improve solver performance (TODO).

Some improvements in win rates:

Before:

image

After:

image

wingos80 commented 1 month ago

Still need to add truly random selection of far cells, currently only using np.argmin() which selects the first lowest index. Also need to experiment with only computing far cells estimates if informed cells are all uncertain (e.g. x values between 0.2 and 0.8).