/minesweeper

minesweeper solver

Primary LanguagePython

Very early alpha demo (only 1 solve strategy):

demo1.gif

Demo 2 (3 solve strategy):

demo2.gif

Demo 3 (5 solve strategy):

demo3.gif

TODO

[x] MatchTemplate занимает до 25-50% времени выполнения. Надо с этим что-то делать
[ ] Написать тесты?
[ ] Возможность остановть выполнение по нажатию клавиши
[ ] Выяснить, что не так с red bomb (особенно когда красная бомба последняя = баг)
[x] Реализовать режим без флагов (NF)
[x] Режим NG
[-] TODO можно делать движения мыши более "человеческими" PS Нет смысла, движения не пишутся, только время между кликами.
[x] Сделать настройки через settings.ini
[x] Сделать слой абстракции конкретной реализации сапера
[ ] Сделать в ридми описание стратегий
[ ] Хочу, чтобы можно было так делать: if bomb in matrix:, или, если у нас есть array of cells - if bomb in array
[ ] Разобраться, где и как используются cell.status и cell.type
[x] Перед выполнением R1 сохранять скриншот и pickle
[x] Печатать время после игры
[ ] Считать потраченные на игру клики
[ ] Научить солверы быть "эффективными". Для этого можно выявлять все возможные решения и применять тот, который открывает максимум клеток.
[x] Сделать время движения мыши зависимо от расстояния между клетками
[ ] Solver E2 возвращает сильно много клеток - получается, что они могут открыться после нажатия на первую клетку, а он все равно ползает и кликает по уже открывшимся
[ ] Если в начале игры на поле обнаруден крест - автоматически ставить игру в режим No Guess
[x] Проверять, все ли файлы ассета в наличии
[x] Провести эксперимент - играть руками в сапера на разных размерах и питоном записать распределение времени между кликами
[ ] Можно находить координаты для клика Reset автоматом по smile.png
[ ] asset_24_1920x1080 (а может быть, и другие ассеты) не распознает окончание игры, если взорвались на последней бомбе (т.е. на поле только одна бомба и она красная)
[ ] непонятно, откуда брать настройки... многие сначала импортируются в asset, а потом напрямую берутся из config
[x] move asset.py to settings.ini
[ ] Считать количество фейлов в начале, середине, и конце игры

Targets and indicators

Engine speed

Измеряется на Vienna Minesweeper с нулевыми задержками на Professional поле. Показывает общую скорость движка и потенциальные бутылочные горлышки.

No guess solving

Показывает мощь алгоритмов. В no guess досках всегда есть решение и не применяется случайный выбор. Процент решенных досок показывает, насколько "умны" алгоритмы решений. Выполняется на online-сапере.

Guess percentage

Аналогично предыдущему, но так же задействует алгоритм выборы случайной клетки. Выполняется на Vienna с большими выборками.

Efficiency

Значение 3BV, поделенное на количество кликов. Требует особой настройки алгоритмов. Сейчас можно просто произвести замеры. Требует технологии подсчета 3BV, пока не реализовано.

R1 fail chance

Подсчитать на длинных прогонах, сколько раз ошибается R1 обычный и сколько раз он будет ошибаться после вычислений вероятности нахождения бомб

Perfomance

see perfomance

Installation

Numpy

Для винды нужны прекомпилированные пакеты, иначе придется их либо через conda устанавливать (что ведет к ебле с окружением, ибо у конды свое), либо нужно тянуть 4-6 гигов майкрасофтовских компиляторов. Брал отсюда https://www.lfd.uci.edu/~gohlke/pythonlibs/#numpy

Opencv

аналогично

для установки opencv нужно установить это:
Microsoft Visual C++ Redistributable for Visual Studio 2015, 2017 and 2019

Libraries

opencv

Real-time computer vision.

pywinauto

[not used] pywinauto is a set of python modules to automate the Microsoft Windows GUI. At its simplest it allows you to send mouse and keyboard actions to windows dialogs and controls, but it has support for more complex actions like getting text data.
github

pyautogui

[not used] PyAutoGUI is a cross-platform GUI automation Python module for human beings. Used to programmatically control the mouse & keyboard.
github

python-imagesearch

[not used] search the screen for a specific element
github

mouse

Controlled mouse (at 100 times faster of pyautogui) github

Articles and Algorithms

Automate gaming with python
You never get bored playing with Computer Vision

Search the screen for a specific element
Easy Image recognition for automation with python
How to easily image search with python

Крутая статья по вероятностям в эндшпиле Minesweeper: Advanced Tactics

How to Write your own Minesweeper AI
-- and it's reddit thread
Logic solver aka PROLOG
Solving Minesweeper with Matrices
Another matrix solution

First click probability TLM Theory

Minesweeper and NP-completeness
Algorithmic Approaches to Playing Minesweeper PDF
reddit
Официальное сообщество Minesweeper
Авторитетный сапер
-- Почти все саперы скачать Вероятности закрытых ячеек
Algorithms for Minesweeper Game Grid Generation
Puzzling StackExchange
Minesweeper Board Museum

Большое сборник статей по мат. алгоритмам

Human strategy

Strategy wiki
Minesweeper Strategy

Non algorithm articles

Minesweeper and Hypothetical Thinking Action Research

Minesweeper boards

Miner online another
Minesweeper-X
Arbiter
Viennasweeper
minesweeper.online
Google minesweeper
minesweeperonline.com
Analize bot