/MinesweeperAI

Minesweeper AI that interfaces with minesweeperonline.com with OpenCV

Primary LanguagePython

Minesweeper AI

Minesweeper AI solver that interfaces with minesweeperonline.com with OpenCV

Also works with the original winmine.exe (download here)

Demo

minesweeper

Results

Solver Deterministic Expert solve rate
OH (Buffet et al. 2013) No 38.7 %
This solver Yes 38.0 %
cSimEnuLoClf (Legendre et al. 2012) Yes 37.5 %
CSP (Studholme 2000) Yes 33.9 %
CSCSP (Becerra 2015) Yes 32.9 %

Features

Algorithm

  • First tile clicked is corner tile
  • Simple search
    • Number of mines = value on tile - number of flags adjacent to tile
    • If number of mines == len(adjacent tiles): all adjacent tiles are mines
    • If number of mines == 0: all adjacent tiles are safe tiles
  • Group search
    • If one group (consisting of all unopened tiles adjacent to one tile) is a subset of another group:
      • If they have the same number of mines:
        • The difference between them are safe tiles
      • If the subset has X less mines than the other group and X == size of group that is the difference between them are safe tiles:
        • The difference between them are mines
  • Subgroup search
    • For each group:
      • Create a 'no more than' subgroup
      • Create an 'at least' subgroup
      • Perform safe and mine checks between each group and subgroup
  • Constraint Satisfaction Problem (CSP) search
    • Couple constraints together into a subset if they share a common variable
    • Solve for solutions to the coupled subset
    • Eliminate solutions with more mines than remaining mines
    • Calculate probability of a tile in subset being mine-free (based on all its possible solutions)
      • Calculate no of possible combinations of bombs with remaining tiles given a solution (use this as weight)
    • Calculate probability of an unconstrained tile being mine-free
      • Position of unconstrained tile in the order of corner, edge then internal tile

Potential improvements

How to use

  1. Modify INITIAL_MINES in main.py
  2. Run main.py
  3. Left click on upper left hand corner of board
  4. Left click on lower right hand corner of board

Side notes:

  • Press 'b' to terminate midway through loop
  • Modify main.py if you want it to remember the position of the board
  • Modify main.py and set benchmark_runs = x for x runs of the benchmark

Dependencies

  • pynput
  • pyautogui
  • opencv-python
  • mss
  • numpy
  • keyboard

References