If we calculate all possible combinations in each group separately, we certainly gain some performance boost. That means we can group them into sections: You might notice, that some of these cells are located closely to each other, while some of them do not even have common neighbours. Considering we need not only to calculate all possible variations, but apply each of them on the field and check whether they satisfy game conditions, then processing could take hours! Can we somehow reduce this number? Let's analyse this case further. According to formula, it will result inĬombinations. Thus all of them can be taken into account while calculating of combinations of possible mines placement. There are 27 closed cells which border to one or more opened ones. Readability and simplicity are one of the most crucial qualities of the code imo, so we need to pay some attention to this aspect as well. Very often it is even challenging to understand what exactly such algorithm is doing after coming back to it after some time. Though for sure, it is possible to create such algorithm ourselves, but even after putting significant efforts there, most probably it will result in something we won't be happy to work with in future. One can just imagine the amount of "for" loops we might need for this. First off, it is easy to work out what to do with 0s: there cant be mines in. And then finally commit a decision (make a move). You must use logic alone to work out where all the mines are and locate them. Then based on remaining combinations for each cell we need to calculate probability of whether it is empty or contains a mine. Then filter out the list of combinations based on applying each combination and checking whether it fits the field conditions or not. To begin we need to find all possible combinations. Secondly, it will certainly introduce some programmatic complexity. According to our indispensable Big O Cheat Sheet it is horrible :) However it faces several problems.įirst of all, the number of all possible combinations can be (and on a large field often will be) too huge. How exactly are we going to implement this? At first sight, the idea of calculating all possible combinations of mines placement and picking the most reasonable one seems as the way to go. So let's "teach" our Computer player how to handle these cases! Actually there are plenty of similar cases, and those who play Minesweeper often don't even bother to calculate them each time, they simply instantly recognise familiar patterns. But after calculating all possible combinations of mines placements at these three closed cells, it becomes clear that only one combination is possible (as flagged in the picture). Clicking both the left and right mouse buttons simultaneously over a number that already has its mine(s) found, will open all the blocks around it. When looking at every opened cell one by one, it is impossible to determine where exactly is the mine(s) in the neighbour cells. Every Minesweeper player knows that there are many cases when one must consider two or more cells at a time to make their next decision. However it appeared, it's solving abilities are limited - it can analyse individual cells only. We ended with a program which can efficiently iterate through cells on a field and make a decision which of their neighbours contains a mine or not. In fact, on Expert mode (16x30, 99 mines) when the only revealed number is 2, then the probability on adjacent tiles is 25%, whereas on the rest of the tiles we have 97/(16*30-9)=21%, so your program advises a bad move! I'm not for covering the whole area with numbers, but I think writing the probability of the unstable tales would be good.In the first article of the series we've implemented a basic Minesweeper solving algorithm for Minesweeper Battle game. Then, the rest of the board has much less probability of not being mined, that these 8 tiles adjacent to this 5. Imagine a corner tile (or Node as I prefer) surrounded by flags. If you google minesweeper and play the game on the 2nd link, you may encounter one of the first bugs/edge cases I came across. Let's imagine situation where you have just made the first move, and the number 5 was revealed. Minesweeper/solver is simple to learn, but brutally and deceptively difficult to implement. My idea would be also to check probabilities of not only those tiles that are adjacent to open tiles. And then I'd add an option for auto pressing Ctrl+Space as fast as possible.Īlso, after making a move, the capture engine could just check those fields that might have changed, if that would make the process faster. I'd add an option that allows the program to choose one of the fields with least probability of being mined, if nothing is obvious, so that all board can (might) be solved just by pressing Ctrl+Space.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |