Бот для сапера с изюминкой

Наверное у многих такое бывает: на работе нечего делать, или нужно подумать перед выполнением очередной задачи, да или попросту нет ничего вкусненького к чаю, тогда рука автоматически тянется к мышке и начинает играть в сапера. И вот в порыве очередного приступа саперомании меня посетила мысль о том, что я уже не думаю, как раньше, где расположены мины, а просто на автомате по выработанному алгоритму тычу по полю, ломая мышку. А раз я действую по алгоритму, без особых творческих усилий, то можно написать бота, который будет играть вместо меня, наверняка внимательнее и быстрее.

Таким образом, вместо того чтобы самому играть в сапера в свободное время, я решил обучить игре бота — написать программу на С#, которая будет выполнять следующее:

1) по картинке окна с игрой заполнять матрицу размеров 16*30(размеры поля сапера в профессиональном режиме) числами в соответствии с диспозицией на экране;
2) прогонять эту матрицу через алгоритм, выполняющий шаблонные действия;
3) в ходе алгоритма тыкать по полю мышкой, расставляя флаги и открывая поле, и возвращаться к первому пункту.
4) поскольку за счет третьего пункта мышь занята, то для остановки программы необходимо настроить перехват нажатых клавиш в операционной системе(т.к. активным постоянно является окно сапера, а не наша программа).
5)Осилив четыре предыдущих пункта, я решил добавить изюминку — сделать программу хоть немного более
полезной/юзабельной — сделать из нее заставку, т.е. автоматически запускать игру в сапера при бездействии клавиатуры и мыши по истечении времени, указанного пользователем(по желанию пользователя, разумеется).

Программа писалась и тестировалась для классического сапера, который был в версиях Windows до XP включительно. Далее я решил перенести ее также и на MineSweeper — сапер из Windows7, об этом в конце статьи.

Итак, пойдем по порядку.

1) В первом пункте мы создаем глаза нашего бота. Получить картинку с игрой нам поможет следующий код:

using Emgu.CV;
using Emgu.CV.Structure;

.................

DllImport("user32.dll", SetLastError = true)]
public static extern IntPtr FindWindow(string lpClassName, string lpWindowName);

[DllImport("user32.dll")]
[return: MarshalAs(UnmanagedType.Bool)]
public static extern bool GetWindowRect(IntPtr hwnd, out RECT lpRect);

public struct RECT
        {
            public int Left;
            public int Top;
            public int Right;
            public int Bottom;
        }
		
public static Bitmap GetScreenImage(Rectangle rect)
{
        Bitmap bmp = new Bitmap(rect.Width, rect.Height, PixelFormat.Format32bppArgb);
        using (Graphics graphics = Graphics.FromImage(bmp))
        {
            graphics.CopyFromScreen(rect.Left, rect.Top, 0, 0, rect.Size, CopyPixelOperation.SourceCopy);
        }
        return bmp;
}
..................
		
RECT rect;

//получаем указатель на окно с названием Сапер
IntPtr handle = FindWindow(null, "Сапер");

//получаем координаты прямоугольника окна
GetWindowRect(handle, out rect);
Rectangle gameScreenRect = new System.Drawing.Rectangle(rect.Left, rect.Top, rect.Right - rect.Left, rect.Bottom - rect.Top);

//получаем изображение экрана на заданном прямоугольнике
Bitmap gameBmp = GetScreenImage(gameScreenRect);
Image<Bgr, Byte> img = new Emgu.CV.Image<Bgr, byte>(gameBmp)

На выходе мы получили цветное изображение окна с игрой — теперь наш бот видит то же, что и мы, но пока не знает, что с этим делать, глупый. Теперь нам по картинке надо заполнить матрицу 16*30 числами от -1 до 10(-1 — это флажок, выставляемый правой клавишей, 0 — клетка не касается ни одной мины, 1-8 — количество мин-соседей у данной клетки, 9 — неоткрытая клетка, 10 — мина(появляется при подрыве)). То есть в начале каждой игры матрица должна быть заполнена девятками, а при проигрыше должна появиться хоть одна десятка. Для заполнения матрицы я сперва хотел воспользоваться какой нибудь библиотекой распознавания символов, но потом подумал, что это как стрелять из пушки по воробьям, ведь у нас всего 12 вариантов изображений, решил написать собственный модуль для распознавания. Когда я переносил приложение под сапера из Windows 7, то пожалел о своем решении, так как количество изображений возросло, и метод их отличия друг от друга заметно усложнился.

Распознать изображение и заполнить матрицу нам поможет оболочка известной библиотеки OpenCV для C# EmguCV, она очень проста в подключении и
использовании. Распознавание в приложении происходит следующим образом: из большого изображения с окном игры, полученного на предыдущем этапе, по очереди вырезаются маленькие изображения — ячейки и сравниваются с заранее заготовленными эталонами. Для более эффективного сравнения делаем изображения черно-белыми: если интенсивность серого в конкретном пикселе меньше THRESHOLD, то он окрашивается в белый, иначе в черный, далее идет попиксельное сравнение.

Image<Gray, Byte> normal = image.Convert<Gray, Byte>().ThresholdBinary(new Gray(THRESHOLD), new Gray(255));

2) Теперь наш бот может видеть, надо научить его думать; алгоритм игры — мозг нашего бота, он состоит из нескольких частей.

Для удобства использования нашей таблицы с числами в алгоритмах прохождения игры создадим класс SaperCell, в котором помимо типа ячейки и координат зададим еще несколько свойств:

class SaperCell
    {
        public int value;
        public int X;
        public int Y;
		
        //количество неоткрытых клеток рядом с данной ячейкой
        public int numberOf9TypeNeighbours;

        //количество флагов, сигнализирующих о бомбе рядом с данной ячейкой
        public int numberOfFlags;
		
		//вероятность попасть на мину, если ткнуть в любую соседнюю неоткрытую клетку
		public float Probability;
	}

Первая часть алгоритма — самая простая, в ней мы пробегаем по всем открытым клеткам(по цифрам от 1 до 8) и проверяем, равно ли количество неоткрытых соседей данной клетки количеству мин, которых она должна касаться(типу данной клетки). Если это так, то мы знаем, что мины расположены во всех соседних неоткрытых ячейках. После этой части алгоритма обработаются все следующие ситуации:







Вторая часть алгоритма отлавливает все типичные ситуации, которые выработались у меня за время, когда не было ничего вкусненького к чаю. Таких шаблонов несколько:

1) Тройка 1, 2, 1 — в этом случае мины стоят напротив единиц.



2) Четверка 1, 2, 2, 1 — в этом случае мины стоят напротив двоек.



3) Замкнутая тройка 1, 1, 1 (это значит, что по диагонали от крайних единиц нет неоткрытых клеток, т.е. напротив тройки ровно три неоткрытых клетки) — в этом случае мина напротив центральной единицы.



4) Замкнутая четверка 1, 1, 1, 1 — мины напротив крайних единиц.



Третья часть алгоритма (если это так можно назвать): пробегаем по всем клеткам, которые уже касаются нужного количества мин, и тыкаем одновременно левой и правой кнопками мыши.

Четвертая часть алгоритма — умный клик, если предыдущие алгоритмы больше не дают результата(не раскрывают ничего нового), то идет поиск клеток, где точно нет мин: если множество неоткрытых соседей клетки А является подмножеством неоткрытых соседей клетки В, и клетка В не должна касаться большего числа мин, чем клетка А, то можно смело открывать всех неоткрытых соседей клетки В, не являющихся соседями клетки А.



Далее, аналогичным образом, идет поиск клеток, где точно есть мина.



3) Теперь наш бот знает, где точно есть мины и где их точно нет, а ничего поделать не может, как говорится нет ручек — нет конфеток. Приделаем нашему боту руки: вот код, позволяющий совершать левый клик мышью в нужной клетке окна сапера:

[DllImport("user32.dll")]
public static extern void mouse_event(uint dwFlags, int dx, int dy, uint dwData, int dwExtraInfo);

[Flags]
public enum MouseEventFlags
{
        LEFTDOWN = 0x00000002,
        LEFTUP = 0x00000004,
        MIDDLEDOWN = 0x00000020,
        MIDDLEUP = 0x00000040,
        MOVE = 0x00000001,
        ABSOLUTE = 0x00008000,
        RIGHTDOWN = 0x00000008,
        RIGHTUP = 0x00000010
}      

public void LeftClick(int y, int x)
        {
            mouse_event((int)(MouseEventFlags.MOVE | MouseEventFlags.ABSOLUTE), x * 65536 / SCREEN_WIDTH,
                y * 65536 / SCREEN_HEIGHT, 0, 0);

            mouse_event((int)(MouseEventFlags.LEFTDOWN), (lx * 65536 / SCREEN_WIDTH,
               y* 65536 / SCREEN_HEIGHT, 0, 0);
            mouse_event((int)(MouseEventFlags.LEFTDOWN), x * 65536 / SCREEN_WIDTH,
                y * 65536 / SCREEN_HEIGHT, 0, 0);

            System.Threading.Thread.Sleep(10);

            mouse_event((int)(MouseEventFlags.LEFTUP), x * 65536 / SCREEN_WIDTH,
              y* 65536 / SCREEN_HEIGHT, 0, 0);

        }

Теперь в ходе алгоритма, чтобы кликнуть по ячейке с координатами (x,y) достаточно написать:

mouse.LeftClick(x,y).

Здесь mouse — это класс, содержащий все виды кликов, позволяющий проще манипулировать мышью в ходе игры.

4) После предыдущих пунктов наш бот просто неудержим — готов играть в сапера до посинения, занимая мышку. Поэтому нужно приделать ему уши, чтоб он слышал, когда останавливаться. Поскольку мышь занята, то для остановки программы придется использовать… клавиатуру, что же еще. Но и с этим есть проблема, так как активным постоянно является окно сапера, то придется отлавливать все нажатые клавиши в операционной системе. Поискав в интернетах, я набрел вот на это готовое решение. Остается создать два отдельных потока — в одном будет трудиться наш бот, во втором перехватчик нажатых клавиш, а также механизм их взаимодействия.

Thread hooker = new Thread(KeyboardHook);
hooker.IsBackground = true;
hooker.Start();

Thread saper = new Thread(SaperGame);
saper.IsBackground = true;
saper.Start();

EventWaitHandle wh = new AutoResetEvent(false);


В функции KeyboardHook при нажатии клавиши:

if (isPaused == false)
{
       isPaused = true; 
}
else
{
        isPaused = false;
        wh.Set();
}

В функции SaperGame:

if (isPaused == false)
{
        wh.Set();
}
else
{
        wh.WaitOne();
}

Поток saper при игре постоянно проверяет, переменную isPaused, если она равна true(значит была нажата клавиша), то поток тормозит и ждет отмашки от ивент вайт хэндлера, а он ее дает только при повторном нажатии клавиши.

5) Теперь наш бот не только хорошо играет, но и стал очень послушным. После всяких оптимизаций (рекорд бота 5 секунд) я уже не знал, что бы еще с ним сделать, а хотелось добавить какую-то изюминку, уж очень меня это увлекло.

В итоге решил преобразовать свою программу в заставку, чего компьютеру простаивать, пусть лучше в сапера играет. Для Windows XP это сделать очень просто — изменить расширение экзешника на .scr и положить его со всеми необходимыми файлами в C\\WINDOWS\\system32, тогда он появится среди остальных стандартных заставок, остается просто выбрать интервал и программа сама запустится при бездействии компьютера. Но я решил сделать универсальное решение, чтобы можно было использовать приложение и в семерке. Для этого создал оконное приложение, висящее в трее, с возможностью добавления в автозагрузку(ведь заставка Windows работает с самого начала), а также прикрутил вот этот класс для отслеживания перемещений мыши. Теперь при любой активности мыши или клавиатуры перезапускается таймер и, если засеченное время больше заданного интервала, то стартует игра. Конечно, это не заставка из Windows, здесь отслеживаются лишь клавиатура и мышь, но все же я остался доволен.

Теперь скажу немного об обучении бота играть в Minesweeper из Windows7. Когда программа работала как часы под Windows XP, но я думал, что всего пару штришков — и все заработает под Windows7. Но не тут то было, хотя, по сути, переделать нужно было только процесс распознавания, но это потребовало времени почти столько же, сколько написание всего предыдущего кода. Дело в том, что однотипные ячейки в сапере из Windows7 очень сильно отличаются в разных частях поля. Поэтому для каждого типа ячейки пришлось заготовить сразу несколько эталонов, но и это не избавило от ошибок в распознавании, так как установить один и тот же THRESHOLD для такого количества картинок не удавалось. Поэтому пришлось для каждой ячейки на ходу высчитывать THRESHOLD, как среднюю интенсивность серого всей картинки, за счет этого время распозвнавания увеличилось в два раза. Ну ладно, главное надежно, но и после этого периодически проскакивали косяки, причем при пошаговой отладке их не было. Все дело оказалось в плавном обновлении самого окна сапера в Windows7, пришлось делать искусственные паузы перед каждым снимком экрана. Кажется все просто, но пока я дошел до этого, я проклял, что взялся за допиливание проги под MineSweeper-а, что начал изобретать этот хромающий велосипед с распознаванием. Но, благо, после небольшой оптимизации прога начала раскладывать сапера за приемлимое время и почти не сбиваться.

Исходный код программы доступен на github.

Таким вот образом у меня получилось написать довольно-таки интересное приложение, попрактиковать свои навыки программирования и изучить что-то новое. Всем, кто прочитал — спасибо, а кто скачал и попробывал бота в действии — огромная благодарность!

А вот и видео с примером работы бота:
Share post

Similar posts

Comments 20

    +8
    Я не совсем понимаю, зачем занимать мышь для этого? Можно ведь просто слать окну WM_LBUTTONDOWN, WM_NCHITTEST и их друзей?
      +8
      И зачем OpenCV, если достаточно брать цвет центрального пикселя клетки с цифрой?
        0
        А вы уверены, что все цифры включают в себя центральный пиксель?
        Впрочем, какой-то общий у них наверняка есть.
          +1
          Пусть не центральный, но можно на основании всех картинок найти пиксель-признак, который есть только у определенной цифры или знака.
            +1
            Чисто визуально у цифр Сапера центральный пиксель везде есть. Хотя конечно можно и несколько пикселей проверять, цвет все равно уникален.
            0
            согласен, что с распознаванием я перемудрил, можно было намного проще
          +34
          В посте не хватает видео работы бота
            0
            добавил
            +14
            Посмотрите как переводится hooker, это явно не то, что вы хотели в коде описать )
              0
              упс) нехорошо получилось, думал, что это перехватчик/отлавливатель
              +2
              Запустил бинарь, что шел в комплекте с сырьками.
              Извините, данная версия не поддерживается либо размеры окна изменены!

              Это в 7-ке. Как я только не пытался изменить размер окна сапера — результат один.
              Расчехлил xp в эмуляторе. Установил туда .NET 4-й версии. Запустил.
              Извините, данная версия не поддерживается либо размеры окна изменены!

              А ведь в XP сапер даже нельзя отресайзить.

              Вобщем не судьба (
                0
                А может у Вас поле не 16х30?
                  0
                  начсет xp — удивительно, я думал, что размеры окна сапера везде стандартны для xp, может у вас широкоформатный монитор и для него автоматически меняются размеры окна
                  +2
                  Видео в студию)
                    0
                    добавил видео
                    +7
                    Запустил бинарь, что шел в комплекте с сырьками.

                    Пишу с телефона…
                      0
                      Бинарики в репозитории, зависимости без NuGet… Ужас, это скорее нужно исправить!
                        0
                        Отличный бот для любимой игры
                          0
                          Добавлю, что один из самых главных шаблонов сапера имеет вид 'A-1-2-B', где под A — точно нет мины, а под B — точно есть.
                            0
                            Дорабатывайте ваш алгоритм. В конце видео бот проиграл, хотя можно было еще определить, где мины, а где пустые
                            image
                            Зеленые клетки — точно пустые
                            Красные клетки — точно мина

                            Only users with full accounts can post comments. Log in, please.