Bot for sapper with a twist
Probably many people have it: there is nothing to do at work, or you need to think before performing the next task, yes, or there is simply nothing tasty for tea, then the hand automatically reaches for the mouse and starts playing sapper. And in the rush of another attack of sapromania, I was struck with the thought that I no longer think, as before, where the mines are located, but simply on the machine, using the algorithm developed, to jog along the field, breaking the mouse. And if I act on the algorithm, without much creative effort, then you can write a bot that will play instead of me, probably more attentively and quickly.
Thus, instead of playing sapper in my spare time, I decided to train a bot to write a program in C # that would do the following:
1) in the picture of the game window, fill in a matrix of sizes 16 * 30 (sapper field sizes in professional mode) with numbers in accordance with the disposition on the screen;
2) drive this matrix through an algorithm that performs template actions;
3) in the course of the algorithm, poke the field with the mouse, placing flags and opening the field, and return to the first item.
4) since, due to the third point, the mouse is busy, then to stop the program, you must configure the interception of keystrokes in the operating system (because the sapper window is always active, not our program).
5) Having mastered the four previous points, I decided to add a zest - to make the program at least a little more
useful / usable - make it a screensaver, i.e. automatically start the game in the sapper when the keyboard and mouse are idle after the time specified by the user (at the request of the user, of course).
The program was written and tested for the classic sapper, which was in versions of Windows before XP, inclusive. Then I decided to transfer it to MineSweeper too - a sapper from Windows7, about this at the end of the article.
')
So let's go in order.
1) In the first paragraph, we create the eyes of our bot. Get the picture with the game will help us the following code:
At the exit, we got a color image of the window with the game - now our bot sees the same thing as we, but does not know yet what to do with it, stupid. Now we need to fill in the matrix with 16 * 30 numbers from -1 to 10 (-1 is the flag set by the right key, 0 - the cell doesn’t touch any mines, 1-8 - the number of min-neighbors in this cell, 9 - undiscovered cell, 10 - mine (appears when undermined)). That is, at the beginning of each game, the matrix must be filled with nines, and at a loss, at least one dozen should appear. To fill in the matrix, I first wanted to use some sort of a character recognition library, but then I thought it was like shooting a gun at sparrows, because we have only 12 image variants, I decided to write my own module for recognition. When I transferred the application under the sapper from Windows 7, I regretted my decision, as the number of images increased, and the method of distinguishing them from each other became much more complicated.
The shell of the well-known OpenCV library for C # EmguCV will help us to recognize the image and fill the matrix, it is very easy to connect and
using. Recognition in the application is as follows: from the large image with the game window obtained in the previous step, small images are cut out one by one - the cells and compared with the previously prepared standards. For more effective comparison, we make the images black and white: if the gray intensity in a particular pixel is less than THRESHOLD, then it is painted white, otherwise it is black, then there is a pixel-by-pixel comparison.
2) Now our bot can see, we must teach him to think; The game's algorithm is the brain of our bot, it consists of several parts.
For ease of use of our table with numbers in the game passing algorithms, we will create the class SaperCell, in which in addition to the cell type and coordinates, we will define several properties:
The first part of the algorithm is the simplest one, in it we run over all open cells (numbers 1 through 8) and check whether the number of unopened neighbors of a given cell is equal to the number of mines it should relate to (the type of this cell). If so, then we know that the mines are located in all the adjacent undiscovered cells. After this part of the algorithm, all of the following situations will be handled:
The second part of the algorithm catches all the typical situations that have developed in my time, when there was nothing tasty for tea. There are several such templates:
1) Troika 1, 2, 1 - in this case, the mines are opposite units.
2) Quartet 1, 2, 2, 1 - in this case, the mines stand opposite the two.
3) The closed triple 1, 1, 1 (this means that there are no undiscovered cells diagonally from the extreme units, that is, there are exactly three undiscovered cells opposite the triple) - in this case, the mine is opposite the central unit.
4) Four closed four, 1, 1, 1 - mines opposite extreme units.
The third part of the algorithm (if you can call it that): run through all the cells that already touch the required number of mines, and simultaneously poke the left and right mouse buttons.
The fourth part of the algorithm is a smart click, if the previous algorithms no longer produce results (they do not reveal anything new), then there is a search for cells that have no mines: if the set of undiscovered neighbors of cell A is a subset of undiscovered neighbors of cell B, and cell B should not touch more mines than cell A, then we can safely open all undiscovered neighbors of cell B, which are not neighbors of cell A.
Next, in a similar way, there is a search for cells where exactly there is a mine.
3) Now our bot knows where exactly the mines are and where they are definitely not there, but cannot do anything, as they say there are no pens - no candies. Let's attach our bot hand: here is the code that allows you to left-click with the mouse in the desired cell of the sapper window:
Now in the course of the algorithm, to click on a cell with coordinates (x, y) it is enough to write:
Here, the mouse is a class that contains all kinds of clicks, making it easier to manipulate the mouse during the game.
4) After the previous points, our bot is simply unstoppable - ready to play sapper until blue in the face, taking up the mouse. Therefore, you need to attach his ears so that he can hear when to stop. Since the mouse is busy, then to stop the program will have to use ... the keyboard, what else. But there is a problem with this, since the sapper window is always active, you will have to catch all keystrokes in the operating system. Searching on the Internet, I came across this ready- made solution . It remains to create two separate streams - in one our bot will work, in the second an interceptor of keystrokes, and also the mechanism of their interaction.
In the KeyboardHook function when you press a key:
In the SaperGame function:
When playing, the saper stream constantly checks if the variable isPaused, if it is equal to true (it means that the key was pressed), then the flow slows down and waits for the event handler to wait, and he gives it only when the key is pressed again.
5) Now our bot not only plays well, but also became very obedient. After all sorts of optimizations (bot record 5 seconds), I didn’t know what else to do with it, but I wanted to add some zest, which really fascinated me.
As a result, I decided to convert my program into a screensaver, so that the computer is idle, it's better to play a sapper. For Windows XP, this is very easy to do - change the file extension to .scr and put it with all the necessary files in C \\ WINDOWS \\ system32, then it will appear among other standard screen savers, you just have to select the interval and the program will start when the computer is idle. But I decided to make a universal solution so that you can use the application in the seven. To do this, I created a window application that hangs in the tray, with the ability to add to autoload (after all, the Windows splash screen works from the very beginning), and also screwed this class to track mouse movements. Now, with any activity of the mouse or keyboard, the timer is restarted and, if the detected time is longer than the specified interval, the game starts. Of course, this is not a screensaver from Windows, only the keyboard and mouse are tracked here, but still I was pleased.
Now I’ll say a little about learning how to play Minesweeper from Windows7. When the program worked like a clock under Windows XP, but I thought that just a couple of shadings would work for Windows7. But it was not there, although, in fact, it was necessary only to redo the recognition process, but it took almost as much time as writing all the previous code. The fact is that single-type cells in the sapper from Windows7 are very different in different parts of the field. Therefore, for each type of cell, several standards had to be prepared at once, but this did not eliminate the recognition errors, since it was not possible to establish the same THRESHOLD for such a number of pictures. Therefore, it was necessary for each cell on the move to calculate THRESHOLD as the average gray intensity of the entire image, due to this, the recognition time doubled. Well, okay, the main thing is reliable, but even after that, the jambs periodically jumped, and they were not in step-by-step debugging. The whole thing turned out to be a smooth update of the sapper window itself in Windows7, I had to make artificial pauses before each screen shot. Everything seems simple, but until I got to that, I cursed that I took over the doping of the program under MineSweeper, and that I began to invent this limping bike with recognition. But, fortunately, after a small optimization, the program began to spread the sapper in an acceptable time and almost did not stray.
The source code of the program is available on github .
In this way, I managed to write a rather interesting application, practice my programming skills and learn something new. Anyone who read - thanks, and who downloaded and tried the bot in action - huge thanks!
And here is a video with an example of the bot's work:
Thus, instead of playing sapper in my spare time, I decided to train a bot to write a program in C # that would do the following:
1) in the picture of the game window, fill in a matrix of sizes 16 * 30 (sapper field sizes in professional mode) with numbers in accordance with the disposition on the screen;
2) drive this matrix through an algorithm that performs template actions;
3) in the course of the algorithm, poke the field with the mouse, placing flags and opening the field, and return to the first item.
4) since, due to the third point, the mouse is busy, then to stop the program, you must configure the interception of keystrokes in the operating system (because the sapper window is always active, not our program).
5) Having mastered the four previous points, I decided to add a zest - to make the program at least a little more
useful / usable - make it a screensaver, i.e. automatically start the game in the sapper when the keyboard and mouse are idle after the time specified by the user (at the request of the user, of course).
The program was written and tested for the classic sapper, which was in versions of Windows before XP, inclusive. Then I decided to transfer it to MineSweeper too - a sapper from Windows7, about this at the end of the article.
')
So let's go in order.
1) In the first paragraph, we create the eyes of our bot. Get the picture with the game will help us the following code:
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) At the exit, we got a color image of the window with the game - now our bot sees the same thing as we, but does not know yet what to do with it, stupid. Now we need to fill in the matrix with 16 * 30 numbers from -1 to 10 (-1 is the flag set by the right key, 0 - the cell doesn’t touch any mines, 1-8 - the number of min-neighbors in this cell, 9 - undiscovered cell, 10 - mine (appears when undermined)). That is, at the beginning of each game, the matrix must be filled with nines, and at a loss, at least one dozen should appear. To fill in the matrix, I first wanted to use some sort of a character recognition library, but then I thought it was like shooting a gun at sparrows, because we have only 12 image variants, I decided to write my own module for recognition. When I transferred the application under the sapper from Windows 7, I regretted my decision, as the number of images increased, and the method of distinguishing them from each other became much more complicated.
The shell of the well-known OpenCV library for C # EmguCV will help us to recognize the image and fill the matrix, it is very easy to connect and
using. Recognition in the application is as follows: from the large image with the game window obtained in the previous step, small images are cut out one by one - the cells and compared with the previously prepared standards. For more effective comparison, we make the images black and white: if the gray intensity in a particular pixel is less than THRESHOLD, then it is painted white, otherwise it is black, then there is a pixel-by-pixel comparison.
Image<Gray, Byte> normal = image.Convert<Gray, Byte>().ThresholdBinary(new Gray(THRESHOLD), new Gray(255)); 2) Now our bot can see, we must teach him to think; The game's algorithm is the brain of our bot, it consists of several parts.
For ease of use of our table with numbers in the game passing algorithms, we will create the class SaperCell, in which in addition to the cell type and coordinates, we will define several properties:
class SaperCell { public int value; public int X; public int Y; // public int numberOf9TypeNeighbours; // , public int numberOfFlags; // , public float Probability; } The first part of the algorithm is the simplest one, in it we run over all open cells (numbers 1 through 8) and check whether the number of unopened neighbors of a given cell is equal to the number of mines it should relate to (the type of this cell). If so, then we know that the mines are located in all the adjacent undiscovered cells. After this part of the algorithm, all of the following situations will be handled:
The second part of the algorithm catches all the typical situations that have developed in my time, when there was nothing tasty for tea. There are several such templates:
1) Troika 1, 2, 1 - in this case, the mines are opposite units.
2) Quartet 1, 2, 2, 1 - in this case, the mines stand opposite the two.
3) The closed triple 1, 1, 1 (this means that there are no undiscovered cells diagonally from the extreme units, that is, there are exactly three undiscovered cells opposite the triple) - in this case, the mine is opposite the central unit.
4) Four closed four, 1, 1, 1 - mines opposite extreme units.
The third part of the algorithm (if you can call it that): run through all the cells that already touch the required number of mines, and simultaneously poke the left and right mouse buttons.
The fourth part of the algorithm is a smart click, if the previous algorithms no longer produce results (they do not reveal anything new), then there is a search for cells that have no mines: if the set of undiscovered neighbors of cell A is a subset of undiscovered neighbors of cell B, and cell B should not touch more mines than cell A, then we can safely open all undiscovered neighbors of cell B, which are not neighbors of cell A.
Next, in a similar way, there is a search for cells where exactly there is a mine.
3) Now our bot knows where exactly the mines are and where they are definitely not there, but cannot do anything, as they say there are no pens - no candies. Let's attach our bot hand: here is the code that allows you to left-click with the mouse in the desired cell of the sapper window:
[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); } Now in the course of the algorithm, to click on a cell with coordinates (x, y) it is enough to write:
mouse.LeftClick(x,y). Here, the mouse is a class that contains all kinds of clicks, making it easier to manipulate the mouse during the game.
4) After the previous points, our bot is simply unstoppable - ready to play sapper until blue in the face, taking up the mouse. Therefore, you need to attach his ears so that he can hear when to stop. Since the mouse is busy, then to stop the program will have to use ... the keyboard, what else. But there is a problem with this, since the sapper window is always active, you will have to catch all keystrokes in the operating system. Searching on the Internet, I came across this ready- made solution . It remains to create two separate streams - in one our bot will work, in the second an interceptor of keystrokes, and also the mechanism of their interaction.
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); In the KeyboardHook function when you press a key:
if (isPaused == false) { isPaused = true; } else { isPaused = false; wh.Set(); } In the SaperGame function:
if (isPaused == false) { wh.Set(); } else { wh.WaitOne(); } When playing, the saper stream constantly checks if the variable isPaused, if it is equal to true (it means that the key was pressed), then the flow slows down and waits for the event handler to wait, and he gives it only when the key is pressed again.
5) Now our bot not only plays well, but also became very obedient. After all sorts of optimizations (bot record 5 seconds), I didn’t know what else to do with it, but I wanted to add some zest, which really fascinated me.
As a result, I decided to convert my program into a screensaver, so that the computer is idle, it's better to play a sapper. For Windows XP, this is very easy to do - change the file extension to .scr and put it with all the necessary files in C \\ WINDOWS \\ system32, then it will appear among other standard screen savers, you just have to select the interval and the program will start when the computer is idle. But I decided to make a universal solution so that you can use the application in the seven. To do this, I created a window application that hangs in the tray, with the ability to add to autoload (after all, the Windows splash screen works from the very beginning), and also screwed this class to track mouse movements. Now, with any activity of the mouse or keyboard, the timer is restarted and, if the detected time is longer than the specified interval, the game starts. Of course, this is not a screensaver from Windows, only the keyboard and mouse are tracked here, but still I was pleased.
Now I’ll say a little about learning how to play Minesweeper from Windows7. When the program worked like a clock under Windows XP, but I thought that just a couple of shadings would work for Windows7. But it was not there, although, in fact, it was necessary only to redo the recognition process, but it took almost as much time as writing all the previous code. The fact is that single-type cells in the sapper from Windows7 are very different in different parts of the field. Therefore, for each type of cell, several standards had to be prepared at once, but this did not eliminate the recognition errors, since it was not possible to establish the same THRESHOLD for such a number of pictures. Therefore, it was necessary for each cell on the move to calculate THRESHOLD as the average gray intensity of the entire image, due to this, the recognition time doubled. Well, okay, the main thing is reliable, but even after that, the jambs periodically jumped, and they were not in step-by-step debugging. The whole thing turned out to be a smooth update of the sapper window itself in Windows7, I had to make artificial pauses before each screen shot. Everything seems simple, but until I got to that, I cursed that I took over the doping of the program under MineSweeper, and that I began to invent this limping bike with recognition. But, fortunately, after a small optimization, the program began to spread the sapper in an acceptable time and almost did not stray.
The source code of the program is available on github .
In this way, I managed to write a rather interesting application, practice my programming skills and learn something new. Anyone who read - thanks, and who downloaded and tried the bot in action - huge thanks!
And here is a video with an example of the bot's work:
Source: https://habr.com/ru/post/267047/
All Articles