Website archived by minesweepergame.com
Board Cycles
The Windows Minesweeper version has a finite number of unique boards for each level. Beginner and Intermediate boards repeat in cycles. This discovery was abused to achieve world records and led to Winmine being banned from the world rankings and being replaced by official Clones.
Dream Boards
It was originally thought boards were generated randomly. This changed when Gernot Stania (Germany) set a world record of 15 seconds 20 May 2000 on the Intermediate level. A few days later, Lasse Nyholm (Denmark) noticed that the game was identical to an earlier 18 second game scored by Damien Moore (Canada).
This was a big surprise. Now it was believed games generated randomly from a fixed starting point. Thus everyone would see each board once in their lifetime in the same order. Unfortunately, the Guestbook posts from this era are lost. Over the next few months more duplicate boards were noticed. It soon became worrying that despite the vast number of presumed mine arrangments, records were often being made on the same boards. Damien posted an article on 1 Oct 2000 called "Random Games?" and collected examples. The main feature was several screenshots of what became known as the Dreamboard.
Gernot then broke his record again on 7 Oct 2000, jumping from 15 to 12 seconds on Intermediate. This was a new world record. There was a delay posting the score on Authoritative Minesweeper, but Matt McGinley (USA) realised immediately it was on the same board. Posting on 16 Nov 2000 he wrote, "Wow! 12 in intermediate! And Gernot got the SAME EXACT BOARD AGAIN!!!!!!!!!!!!!!! Hmmmmm, something's not right in the game of minesweeper..."
The same player getting a board twice was a shock than the existence of duplicate boards. One possibility was that Gernot had played on a second computer or had downloaded Winmine again. In that case, the Dreamboard would be close to the beginning of the sequence. Brett Piatt (USA) proposed 28 Dec 2000 that the game used a pseudo-random number generator (PRNG) creating 16 bit numbers. This would limit the number of boards on each level to a maximum of 65535 variations. He pointed out that such a case would have repeating patterns, and the way to make truly random boards would be to use a PRNG with a repeating pattern greater than the number of possible boards for each grid size. David Barry (Australia) noted perhaps minesweeper used a small set of boards, similar to the way Freecell used only 32000 boards.
More duplicate games followed. On 2 Feb 2001 Damien recognised a Beginner game from one of Matt's videos, and he did the last three clicks from memory. His only complaint was not recognising the game sooner and making a faster score. By this point at least six examples of duplicate games had been found.
After Damien mentioned he was talking to Robert Donner, Dan Cerveny (USA) posted 24 Feb 2001, "It will be interesting to see what Rob Donner says about the random board generator. I wish there was a way to guarantee a fresh board every time someone starts a game." It turned out that Robert had not chosen the PRNG and was unable to offer an explanation.
Three days later Matt blasted while playing the Dreamboard. Damien commented, "Tough luck Matt. I don't know if I'd want to get that board though...I make it a rule not to try to get other peoples games...so far I got two 14's and today a 15...all excellent boards, of course. If you try to copy you will miss out on the other boards." Joe Nuss (USA) wrote, "With the crazy frequency with which that baord has been showing up, i bet everyone here's had it at least once" adding that it "makes you think."
Examples continued to accumulate. Matt completed the Dreamboard 28 Apr 2001 in 14 seconds. On 8 Jun 2001 Owen Fox (Ireland) tied his record of 18 seconds - on the same board he had made his original score of 18! Marc Schouten (Netherlands) noticed Matt already had made a video playing that game. Emmanuel Brunelliere (France) posted, "The 16 I've just got finishes on the same board that Damien Moore's 14... Is it possible to know how mines are placed on the board, how "randomness" is made by the program?" No one had an answer.
Shifts and Loops
The first mention of possible shifts came 2 Jul 2001 when Matt posted, "Just a little theory about the board generator: I've noticed many a board that is basically a shift of another board. I've has a board that was my 10 board, shifted left about six rows and up about 10. The patterns that were shifted appeared on the oppsite side of the board. I'n sure many of you have experienced this too. What I'm thinking is that there is a huge pattern of infinte mines and patterns that stretches forever (?) in a 2-dimensional plane. When you make your first click, which is never a mine, a random spot if picked on that net and whatever size board is positioned around that spot. But there's still a discrepancy between the mine densities of the levels, and why certain boards come up again and again."
Georgi Kermekchiev (Bulgaria) was first to reply, "Nice theory Matt, As mine density varies, it is possible to have such a big predesigned pattern (net or whatever) for the main three levels. The problem with custom level still remains - maybe it is generated randomly ... who knows." Marc added, "If boards were picked around a random spot on a very large randomized board, how do you explain the fact that you've had "shifted" boards, where the shifted-off part reappeared on the other side? There should have been another pattern there, according to your theory. But it's an interesting thought." Matt responded, "What I was getting at in that post when I cut myself off, was that if there was a net, it would have to be finite. How else could you explain the recurrence of boards? And I also want to clear something up. All the possible boards - for int. for this example - are equally probable to occur, therefore equally as probable to reccur. The reason we see certain boards that seem to come up more often than not is that they are fast boards that are often record-setting boards. The slow boards come up just as often, but we dont recognize them."
Owen agreed and added that sometimes "i get "loops" where alot of boards that i played yesterday might come up today." Matt had experienced the same phenomenon and wrote, "I too experience the loop phenomenon, Owen. I think my loop with the dream board is being put on the back shelf for a while :) But really, I do experience situations where it feelslike Im playing a whole set of boards over again. I play and it just feels like a dream or something; the exact same boards come up for about five minutes; it's like deja vu."
The first definite evidence of a cycle occured 4 Jul 2001 when Matt noticed something extraordinary: "Going back with the loop thing. The dead board before my 10 and my 14 are the same board. Take a look." Both scores had been made on the Dreamboard and been preceded by the same board. So much for randomness.
Players did not see any problem with this. Most remained unaware of the discovery. Everyone was eager to come across good boards they had seen others play. A ticking time bomb started to emerge as players were able to watch the best boards being played on video, thanks to the emerging popularity of Camtasia. On 12 Jul 2001 Matt posted he had recognised a 17 second game from one of Damien's videos, held his nerve and won in 16 seconds.
A Cycle Exists
Matt scoring a 10 on the Dreamboard prompted David Barry to investigate how minesweeper boards are generated. On 8 Aug 2001 he posted in the Guestbook, "I have some new light and darkness to shed upon the "finite loop" of boards. A few days ago I mentioned to Damien that what we need is some good Windows programmer to write a program that records all of the boards. [...] The API in VB turned out to be very simple to use, and a few hours later I had a program that played a Minesweeper Intermediate board and wrote it to file (actually about 160 boards per file, to save space). I made the program run just over 33000 boards (figuring that there would be 2^15 = 32768, hoping that there weren't 2^30 = 65536). It started by clicking in the top-left corner, and moving across square by square, going down to the next row after 16 clicks. As the first square is never a mine, this will not be a 100% accurate method, but by being consistent, at least the loops should show themselves. The program isn't bug-proof, and I can't be bothered trying to work out precisely what's wrong with it, but here are some early results: Firstly, I ran the program three times, with the second trial giving loads of missed nwe games (see next paragraph), the third trial giving a few and the first trial looking fairly good. The finite loop of boards seems to last about 14875 boards or so. I can't get an exact number because it seems like the program doesn't always hit the smiley face and start a new game all the time. But in the better trials, the gap between boards was about 14870 to 14900."
He continued, "The dream board came up twice in each of the first two trials, and each time it did, the twenty preceding boards were the same, as well as the first few that followed. I assume that if I could be bothered to check, the twenty and few would become thousands. It did not show in the third trial, even though a full loop of boards was completed. After running it, I then started doing the same thing as the program, starting in the top-left, clicking across the board, and checking to see if that board had come up. It didn't in five tries. Statisticians may like a bigger sample size, but they will have to wait till tomorrow for that, because I'm too tired and lazy right now. Also, on the third trial (and maybe the others, I'll check tomorrow), despite here being a complete loop (two in fact), the frist few boards only showed up once. In conclusion, I have more to do. I will post results here when meaningful ones come through. Now, onto other issues dealing with this... This program, once a bug or two has been ironed out, could quite easily be abused [...] I kind of hope that there is something extra going into the randomising of the boards, and that it is not just the bugs in my program that are making it look that way."
David promised to post more results but he never did publicly. Owen and Matt both wrote immediately asking him to abandon the project to prevent minesweeper being ruined. (A few months later the Winmine Congress asked him to investigate further. On 24 Dec 2002 he told them the Dreamboard cycle was 12096 boards and that he had written a program to play the Dreamboard, achieving a 6 on the 25th attempt). These results were lost when David had his laptop stolen.
Matt also said such a cycle was hard to believe, because he had played the same Intermediate game twice in a 24 hour period. (Later in November Matt experienced board repeats within an hour of each other). Ben Drucker (USA) replied, "It is assumed that the initial board is determined by the time of the day, in seconds, truncated to the 15 or 16 lowest order bits (0 - 32767 or 0 - 65535), due the fact of how random number generation is seeded typically. This would mean that minesweeper would not remember the last board generated before the player closed Minesweeper. This would mean that when Matt said he got the same board more than once in the same day, he must have closed Minesweeper in between getting the board the first time and the second time (correct me if I'm wrong), since I doubt if he played tens of thousands of games in that time. This should also mean that if minesweeper is started (the program itself opened, not a new game started) at 12:00:00 AM, and again at 6:12:16 PM, the initial games (as well as subsequent games) would be the same, assuming same board size and number of mines."
Having previously discovered that identical boards preceded the Dreamboard on his videos, Matt now found that both videos of his shifted Dreamboard showed it also was preceded by identical boards. Perhaps some input caused the cycle to shift, such as the program preventing you from losing on your first click.
Another strange phenomenon was soon noticed. It was common knowledge that if your first click was on a mine, the game shifted it to the top left corner (or if occupied, the nearest empty square to its right) to make your first click safe. Thus some games had been found with this one mine difference. However, Matt noticed that a 17 by Steven Welch (USA) and 18 by Frank Wester (Germany) were identical except four mines were different! Lasse also discovered a 17 by Mark Peters (USA) was identical to the Dreamboard except eleven mines were in different locations.
These developments created more questions than they answered. It was now proven Intermediate had a finite number of boards, a number far less than randomly possible. These boards repeated in some sort of cycle. Something caused the cycle to shift. But why had David not found the Dreamboard in every trial? What was the exact number of boards in the cycle? Did the other levels have cycles and what were they? How were games generated? What caused shifts? How could cycle theory be true if some 'identical' boards had mines in the wrong places? These questions went unanswered.
Two Cycles and Eight Shifts
Roland Seibt (Germany) scored a world record of 9 seconds on the Dreamboard on 5 Oct 2002. This was his sixth time playing the board and he openly admitted training for it. Jon Simonsen (Norway) then decided to reveal he had also trained to complete the Dreamboard. In April 2002 he had calculated the fastest method of solving the Dreamboard, starting games with opening clicks that allowed the board to be recognised quickly. Eventually he tired of waiting for the board and recorded a video of nearly 3000 consecutive Intermediate games, looking through the boards trying to find duplicates. He found two nearly identical boards, except that one was shifted down 2 rows and 6 rows to the left. The two boards were seperated by just over 1500 games. More experimentation revealed there to be 8 such shifts, completing a cycle of roughly 12000 boards. He was able to match some of his record boards to those in the cycle, but others were missing. In fact, there was no trace of the Dreamboard. Similar work with Beginner revealed its shifts were by 1 and 3 (rather than 2 and 6). Later while playing he stumbled across a shift of the Dreamboard and made another massive video. This led to the discovery of a seperate cycle of roughly 12000 boards, again consisting of 8 shifts of 1500 grids. In total there were approximately 24000 boards, in 2 cycles each with 8 shifts of 1500 boards. In August he got the Dreamboard for the third time and scored 12 seconds, his first Sub16 score. Jon published his article on 8 Oct 2002, detailing the moral and practical problems his research created. He hoped further abuse of the cycles could be prevented or regulated.
This research answered several questions. David had been looking for the Dreamboard, so when it did not appear in his cycle he ran his program again until he found it. He assumed the discrepancy was due to programming error. Jon had now proven that there were two seperate cycles. David had merged his evidence into a cycle of roughly 14800 boards, but he had actually merely added some boards from the Dreamboard cycle into the other cycle. Jon had now successfully proven shifts were built into each cycle, but it was still unknown how this was caused. He had also proven that something similar occured with the Beginner level. This was all new and interesting, but it was still unknown how this was caused by the unknown seeding algorithm.
Repeating boards continued to be a problem. Later that month, 24 Oct 2002, Emmanuel posted, "Yesterday I missed 2 14s in less than 1 minute ( 29 and 30 3BV ). I was thinking that if our theory about repeted cycles is true, it is very strange that nobody never noticed those 2 fantastic boards that are separated by less than 10 boards." Roland replied, "I´ve got the same cycle yesterday I think just after I read about it. It were two boards with 3BV29 and 30 and I missed the first at possible 13 and finished second in 15 secs. If you´d like to compare I´ll send you the video." Matt also recognised the games and wrote, "Those two boards are some of the fastest out there. The first one, I missed a 10 on the last click over the summer and I dont think Ive ever gotten a second chance to play the second one, although I have seen it before and did get my first sub-20 on it." The Dreamboard debate was already raging by this time, and a solution was needed. The possibility of players swapping videos of the best boards for study and memorisation had arrived.
Getting Into a Groove
It was now standard knowledge that boards cycled, but it was assumed they did so in some orderly fashion. On 15 Dec 2002 Brian Cornell (USA) posted, "Just got a 12 on the dream board. I wasn't expecting it at all because I thought the boards went in order, and I just got the dream board last week, which I lost on the second click." Jon commented, "I think minesweeper starts at a totally random place in the cycle every time you open it. I also noticed that sometimes you get into a cycle that looks pretty much like another, but a few mines (normally about 10 for intermediate) is out of place." Such an example is the previously noted 17 by Mark Peters on the 'Dreamboard'.
A new arrival in the Guestbook, Tim Kostka (USA), provided insight: "I became extremely interested in how Minesweeper generated board so I researched it. Here's how it works. This was all researched on Beginner mode, not any others. When you start minesweeper, it picks a random board according to some seed value. When you hit F2, it picks the next board according to the board directly before it. So if you get the same board twice, the board after that will be the same as well. After about 20-100 boards, it settles into a "board cycle" that is, it repeats itself after so many boards. There's exactly two "board cycles" that minesweeper settles into. One is exactly 24172 boards long and the other is 23953. So if you're in the cycle, and you hit "new game" that many times, you'll end up at the same board. There's some other subtleties, like if the first space you click on was supposed to be a bomb, then the game moves that bomb to the [top left] corner, or the one next to it if the corner already has a bomb. This accounts for games that have exactly one bomb in a different place. I know this because I let my computer play a few hundred thousand games and had it save them. So now I can predict the next board if I wanted to (only on beginner)."
Tim then studied the other levels and posted results on his site. He found there to be roughly 25000 Intermediate boards consisting of the two cycles Jon had discovered. An analysis of 300000 consecutive Expert games revealed no duplicate boards! He thus proposed there was no Expert dreamboard, as duplicates of easy boards were too rare. He made a significant finding in that your first game is not always part of a cycle. It often takes several games before you fall into a cycle and become trapped. For example, his Beginner results show that your first game is in a cycle about 10% of the time. A cycle is usually entered within 15 games, but this can also take more than 200 boards. This arises naturally from any PRNG used.
Memory Reader
In December 2002 Arik Poznanski (Israel) wrote a memory reader to show mine locations without starting the game. This allowed you to see a map of mines and then 'solve' the game by referencing the solution. The community was unaware of this development or his research. He published online some of the code Minesweeper uses to generate boards, although he did not publish how the pseudo-random number generator worked. He did post the algorithm for creating a board:
1: Allocate a block of memory for the mines map and set all the memory bytes to 0x0F ('empty')
2: Loop over the number of mines and for each mine:
2.1: Randomize x position (width).
2.2: Randomize y position (height).
2.3: Set the correct cell in the memory block to 0x8F (a 'mine').
Seeding
Further discoveries were made by Usman Latif (Pakistan) and posted to his site in three articles appearing between 30 Sep 2003 and 24 Oct 2003. After reading the 'Random Games?' article he had decided to reverse engineer minesweeper. His first discovery was that Winmine starts the PRNG by providing the result of GetTickCount, which is the number of milliseconds elapsed since the computer booted. All games are then generated from this starting number. An interesting feature of GetTickCount is that it increments by 55 milliseconds in Windows 95/98/ME but by 10 milliseconds in Windows XP/2000 and later. He also found that the initial seeding number was used to generate a sequence of numbers. These numbers were used as coordinates for placing mines. For example, he suggested a Beginner game required 22 of these numbers to create a board layout while Expert required around 220. Using a Debugger program he started an Expert game with a GetTickCount of 0. He then started a Beginner game with a GetTickCount of 0 and switched immediately to Expert. Screenshots of both Expert games reveal the second game had 92 of 99 mines in the same place as the first one. The reason for this discrepancy was the Beginner game 'eating' the first few numbers from the number sequence. In his example, the Beginner game used the first 22 numbers of the sequence and the following Expert game used the next 220. Thus the two Expert games shared most of the same inputs.
Usman proposed changing levels frequently would create boards outside of limited cycles. Perhaps new dream boards could be discovered using this method. It turns out he had found an explanation for why the first few games played were not always already inside a cycle, as previously noted by Tim Kostka.
Clone Development
At the beginning of 2004 there were two clones actively being promoted, Minesweeper X by Curtis Bright (Canada) and Minesweeper Clone by Rodrigo Camargo (Brazil). Both programmers investigated board cycles but kept their research private, using it to modify their number generators to prevent cycles, or at least increase the lengths of cycles to the point they were unnoticeable. The only information revealed came during March in Minesweeper Addicts, where Rodrigo stated the current version of Clone had a maximum limit of 16777216 (2^24) unique boards per level. Curtis posted that "Minesweeper uses the Randomize function of the Microsoft Visual C Runtimes".
Jon, who had discovered the two Winmine cycles, now decided to find cycles on Beta 0.75 of the Clone. On 17 Mar 2004 he posted, "I don't know how random the boards created with different versions are. I just have materials that suggested that the clone generated a much larger number of different beginner boards than the original sweeper. It also seemed not to follow the same kind of cyclic behaviour as the original. I used the cheat option of the game to search for boards with a 3BV of less than 3." After searching 800000 boards he found 46 unique boards with 3BV<3. Of these 8 appeared twice and 38 appeared once. If there was a cycle, it was on a much larger scale.
Shifts Rediscovered
The minesweeper community often discovers new things and forgets them, only to discover them again later. Such is the case with cycles and shifts. Perhaps this resulted from the inability of the Guestbook format to organise posts into topics.
On 13 Oct 2004 Damien posted an article called 'Board Cycles, the Dreamboard and Shifts' on his site. He had found three shifts of both the Dreamboard and the 6 Circle Board, finding that there was a pattern to the shifts. Starting with the Dreamboard it shifted 2 down 6 left, 4 up 4 left, 2 up 6 right, 4 down 4 right. These two examples convinced him there were four shifts in the cycle David proposed in 2001. Damien was unaware that Jon had already proven the existence of eight shifts in 2002, although Jon had not given evidence for his research and most players were unaware of his work. Damien started his investigation thinking there might be a finite Master board from which games were just 16x16 tiles, unaware that Matt had proposed this in 2001. Damien did manage to prove that no such Master grid existed. As for shifts, he knew many players had found a shift of the Dreamboard (2 down 6 left) and that Dennis Lütken (Denmark) in August 2003 had found two shifts of the 6 Circle Board. Damien believed he was the first to collect four variants of a board, let alone several boards. He was also first to note that shifts occured in a circular pattern, eventually returning to the original board. (Not realising he had rediscovered four of the shifts inside one of the two cycles, he thought he had proven that the entire single cycle proposed by David Barry was shifting).
This article led to James Custer (USA) rediscovering the work of Usman Latif and posting the link in the Guestbook. Xiaohu Zhang (USA) wrote, "Very interesting discovery. I've wondered about how winmine generates board too. I thought this had been fully understood, since we have the clone now. Let's ask Rod, how does he generate the board? and does he know the algorithm of winmine?"
Christoph Nikolaus (Austria) replied, "Indeed there's nothing left to understand. The standard RNGs uses terrible short cycles 2^16 or 2^32 or so. Most of them even use even cyclelengths. Thats the reason why there are two different cycles (the one with the even start and the one with the odd - that of course is only true because the MS version generates two random numbers for every bomb). Moreover not the generated number (in Z/2^32) is used but only a small part (in Z/2^4 (int), Z/2^5 (exp), Z/2^3 (9x9), Z/2^2 (8x8). If that "fits" to the polynomial function that generates the random numbers (and obviously it does at least for int) it will produce shifted subcylces. And that will produce shifted boards. The function itself produces the shift, but the use of the small part of the number makes it visibly. Rods clone uses the same algorithm to genarate boards, but he generates a new seed everytime he creates a new board (using the time when the board is created) and he uses a different polynom with cyclelength 2^24." This information came from discussions in Minesweeper Addicts between Christoph and Rodrigo in March 2004.
After reading the article, Rodrigo posted on 17 Oct 2004, "Hey, everybody, I think I did a major discovery about the original minesweeper, concerning board cycles and shifts! [...] When I read these words from Damien in his article after getting my discovery, I got shocked: what I have to say is that there are not only 4 shifts to the dreamboard. There are EIGHT!! If 4 of them were found in four years, I could find the 4 others this evening, after finally being able to build a program to search over boards on the MS version. The dreamboard is really inserted on a cycle that contains 12096 boards. However, all of them are shifted by two rows and six collumns at each 1512 boards, giving 8 sub-cycles of shifts. Until now I only studied one of the intermediate cycles. I will make a more complete study about it, and then I'll publish here. I don't know if the 8 cycles were already known, but I got really surprised by discovering that. I recorded myself playing all 8 shifts, and compiled them in a single video." His research was not published for another two years. However, Georgi posted on 18 Oct 2004 that there were two shifts of 12096 and 12064 boards each having 8 cycles of 1512 and 1508 boards. He did not say where this information came from.
Rodrigo Solution
On 9 Sep 2006 someone called Alex posted a 7 second Intermediate game in the Guestbook. He wrote, "I am wondering, how could I have just gotten 7 in intermediate, when my previous record was a 27? The game seemed incredibly easy and I wasn't really trying very hard. I looked at the timer at the end of the game, and it said 7. Please, could someone tell me what is wrong? I know that I am not good enough to get a 7 in intermediate..."
A quick count of the board showed it had a 3BV of 11, less than half the previous known minimum. The game was shockingly easier than the Dreamboard and should have been well known. Aryeh Draeger had one theory, namely the reason the board "has not appeared before is because of a mine shift to the upper left corner. My idea of what the board originally looked like (3bv=25!!!!) is posted at the thread linked below." Dennis Lütken commented, "My theory would be that the board is just a fake board."
These posts were interupted by Ian Fraser (England) posting that he had discovered there were 8 shifts, not the 4 proposed by Damien. This was another case of the community forgettings its history!
Rodrigo then posted on 12 Sep 2006, "I found my old researches (back from 2004) about the cycles on Microsoft Minesweeper... I searched the 11 3BV int board, and didn't find it. I also didn't find any board with more than, let's say, 15 mines matching. I can search more, but I am almost completely sure that we are facing a... fake board!" Ian cautioned, "Not every board is in a board cycle, there are loads of boards that happen but if one board in a cycle is generated then it's stuck So the board could still be legit, the only way to truly test it would be to seed the winmine PRNG with all possible values and record all the possible boards." James asked if Rodrigo had tested the XP version of minesweeper. His response was, "I have captured boards in all versions of Microsoft Minesweeper. The dreamboard exists in all of them, as well as its shifts." Curtis Bright backed up Rodrigo, posting, "I've also studied the workings of the original, and have the complete mine randomization algorithm. I can confirm that the recently shown 11 3BV board could not have been generated on Microsoft Minesweeper."
This prompted Rodrigo to publish his research. On 23 Sep 2006 he wrote, "I finished writting an article with the results of my 2004 research about board cycles [...] I think those who are interested about this subject will like it a lot. And you'll see that I wrote it just like a real scientific paper. It's my first attempt to give Minesweeper the seriousness it deserves."
The article was extremely well written and provided the answers sought by the community for so many years. In preparation for programming the Minesweeper Clone, Rodrigo decided to study how boards were generated in the original version. He wrote a program that saved boards into a database. Analysis revealed two Beginner cycles (24320 and 24304 boards) and two Intermediate cycles (12096 and 12064 boards). The Dreamboard is number 4232 in the 12096 board cycle. He then used his database to eliminate the first click mine shift problem by running the program again, starting games only by clicking in openings.
Based on the initial seeding number, the PRNG creates a sequence of numbers which are then converted to mine locations. There is not actually a board cycle; instead, there is a mine cycle. There are two cycles depending on whether the initial input is an odd or even number. He showed cycle length depends on the number of mines used. The existence of cycles at all depends on the size of the grid - some grid sizes never have cycles. One grid size with no cycles is the 9x9 Beginner grid used by Windows XP and later. Another grid without cycles is the 16x30 grid used for Expert. (Dmitriy commented that in 2005 he had generated 6.6 million Expert boards without finding repeats).
Mines are always placed in the same order, which eventually repeats. The initial seed starts you randomly in this sequence. If you happen to start on a number that corresponds to the first mine of a board, then you have started in the cycle for that level. Otherwise you will play several games before you eventually fall into a cycle. This explained why Tim Kostka had found you were in a Beginner cycle only 1 out of 10 times you started. Rodrigo discovered that these 'strange' boards are created using mines from two consecutive boards. You are in the cycle, but you are offset! You always eventually converge into a cycle because if a number in the sequence corresponds to a location where a mine was already placed, this number is simply skipped. So if you started 15 mines off the cycle, these skipped numbers accumulate until you are back on the cycle. Skipped numbers are also the reason why the two cycles for Intermediate (and the two cycles for Beginner) are of different lengths.
Rodrigo further discovered what he called 'quadrant superposition'. After switching from Intermediate to the Beginner level, 10 mines are used to create the Beginner grid. These 10 mines would have been the first 10 of the 40 laid for the next Intermediate game. But since Intermediate is a 16x16 grid, how are these 10 mines placed on an 8x8 grid? It looks like the 16x16 grid is broken into four 8x8 grids which are then placed on top of each other to create the Beginner game. Although it looks like this is happening, the mine layout actually derives directly from the formula used to place mines. Rodrigo was able to determine that mine placement behaves as if it follows the formula 1 + Int(Nx)modD, where 'N' is a fixed number larger than 'D', 'D' is the dimension of the board (eg, 16), and 'x' is the random number.
Rodrigo summarised by noting there were still questions to be answered. For example, what is the period of the numbers generated and their minimum and maximum values? And how exactly does the Winmine PRNG work and what is its exact formula? However, Rodrigo had finally answered the most important questions and explained the cycles.
Conclusion
Six years of research by the minesweeper community had finally solved the riddle of Board Cycles. A solution was important because players, inspired by the Dreamboard, had begun abusing cycles to achieve records. Research into cycles was directly incorporated into official clones by their programmers, leading to enforced honesty amongst players and elevating the world rankings to a new level of authority.
Links
- Random Games - by Damien Moore (1 Oct 2000)
- Dreamboard Essay - by Jon Simonsen (8 Oct 2002)
- Randomness, Board Cycles and Dreamboards - by Tim Kostka (Dec 2002)
- Minesweeper, Behind the Scenes - by Arik Poznanski (Dec 2002)
- Minesweeper Identical Boards Problem- by Usman Latif (30 Sep 2003)
- Board Cycles, the Dreamboard and Shifts - by Damien Moore (13 Oct 2004)
- All 8 Dreamboard Shifts - Rodrigo plays all shifts on video (17 Oct 2004)
- The Board Cycle Bug of Microsoft Minesweeper - by Rodrigo Camargo (23 Sep 2006)
