Try   HackMD

An experimental minsweeper implementation

Well, this article is relating to my last article on tictactoe game and this is because of similar logic being used.

A Minsweeper Game

The objective of the game is to clear a board that contains hidden "mines" or "bombs" without detonating any of them, and they are randomly placed in a 9x9 grid (beginners level). On every right opeing there's a clue which indicate how many bombs are in the adjacent cells.

At any point, you can perform 2 actions:

  • Marking a cell - marking or flagging a cell that you think might be a bomb
  • Revealing a cell - revealing the cell. If it is an empty cell, then all of the surrounding empty cells will also be revealed. Revealing a cell containing a bomb is game over.

Once you have revealed all cells that do not contain a bomb, you win the game. Also before going forward it is recommended that you understand how to play Minesweeper practically! and also understand the concept of bitwise operations as this article would rely heavily on it.

Planning

Given a grid of N rows and M columns to play the game, we'd represent this grid as bits. We'd denote each cell as an 7-bit integer and here is the data that'd be stored:

 0          0         0          0 0 0 0
---        ---       ---        ---------
 |          |         |             |
is-marked  is-bomd   is-revealed  cell-value

Note: We can use bitwise operations to extract or set relevant bits. The relevant masks would be defined later in this article.

By default, the game is played on a 9x9 grid and a maximum of 10 bombs. However, you can change these later and I'd include settings to easily make changes. As a brief guidline, the standard levels of Minesweeper are:

Beginner Intermediate Expert
Grid size 9 x 9 16 x 16 16 x 30
Max bombs 10 40 90

So here is a visual example of a 9 x 9 grid and how it'd be represented in bits.

      0       1       2       3       4       5       6       7      8            0   1   2   3   4   5   6   7   8
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
      9      10      11      12      13      14      15      16     17          ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     18      19      20      21      22      23      24      25      26         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 1
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     27      28      29      30      31      32      33      34      35         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 2
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     36      37      38      39      40      41      42      43      44         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 3
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     45      46      47      48      49      50      51      52      53         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 4
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     54      55      56      57      58      59      60      61      62         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 5
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     63      64      65      66      67      68      69      70      71         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 6
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
     72      73      74      75      76      77      78      79      80         ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 7
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000         ╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
                                                                                ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 8
                                                                                ╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝

So firstly, we need a way to generate a game and add bombs at random; and here is how we'd implement this in python.

I'd define certain constants which would be used through out this code.









DATA_SIZE = 7

BITMASK_VALUE = (1 << 4) - 1 # 0xf
BITSHIFT_IS_REVEALED = 4
BITSHIFT_IS_BOMB = 5
BITSHIFT_IS_FLAGED = 6

BITMASK_CELL = (1 << DATA_SIZE) -1

And here defining a simple Minesweeper class to simply help hold some property variables and also making it easy to tweek.










class Minesweeper:
    def __init__(self, rows, columns):
        self.rows = rows
        self.columns = columns
        self.data_size = 7     # 7 bits
        self.bits = self.rows * self.columns * self.data_size

        self.grid = 1 << (self.bits + 1) # 0b1000...000 to the `self.bits` zeros

Placing Bombs

On getting this far, you might be able to picture some of the diagrams prevously drawn, in code. Though not the full picture yet but very soon you'd get it. Since evey game needs a bomb and clues, we'd need to generate these randomly. Here is how we'd implement it:



























from random import randint

class Minesweeper:
    ...

    def placeBomb(self, grid):
        """Places a bomb in a random cell"""
        bomb_cell = randint(0, self.rows * self.columns)

        cell = (bomb_cell * self.data_size)

        # getting the value of the cell (7-bits)
        val = (grid >> cell) & BITMASK_CELL

        if (val >> BITSHIFT_IS_BOMB) & 1:
            grid = self.placeBomb(grid)
        else:
            # setting the bomb bit and adding it to the grid (setting the 6th bit)
            new_cell = (1 << BITSHIFT_IS_BOMB) << cell
            grid |= new_cell
        
        return grid    
    
    def new_game(self):
        for _ in range(10):
            self.grid = self.placeBomb(self.grid)

The function placeBomb places a bomb in a random cell. If you look closely you'd see a little recursion which makes sure that a bomb is place in a unique cell, since there is a possiblity of a random cell being generated more than once. So from the above code we can only generate a grid with bombs on it.

game = Minesweeper(9,9)
game.new_game()
game.print_game(debug=True) # function not added here

========== OUTPUT =============
 _  *  _  _  _  _  _  _  _ 
 *  _  _  _  _  _  _  _  * 
 *  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _ 
 _  _  _  _  *  _  _  _  _ 
 *  _  *  _  *  _  _  _  _ 
 _  _  _  _  _  *  _  _  _ 
 _  _  _  _  _  _  _  *  _


Note: * denotes a bomb. Also it'd be different if you run it since it is generated at random

Adding Clues

Clues indicate how many bombs are in the adjacent cells. So we'd need to know the cells adjacent if a particular cell and also count how many of these cells are bombs.

      Count all the mines in the 8 adjacent cells

      N.W  N  N.E
        \  |  /
         \ | /
    W----Cell----E
         / | \
        /  |  \
      S.W  S  S.E

Solving this problem is far simpilar using a 2d array since you can easily do math on the (row, col). Here each cell is represented differently, in other words each cell has an id like so:

0    1   2   3   4   5   6   7   8   

9   10  11  12  13  14  15  16  17

18  19  20  21  22  23  24  25  26

27  28  29  30  31  32  33  34  35

36  37  38  39  40  41  42  43  44

45  46  47  48  49  50  51  52  53

54  55  56  57  58  59  60  61  62

63  64  65  66  67  68  69  70  71

72  73  74  75  76  77  78  79  80

If we want the adjacent cells for cell 30 which from the above grid would look like:

TOP       | 20 | 21 | 22 |
          ----------------
SIDED     | 29 | 30 | 31 |
          ----------------
BOTTOM    | 38 | 39 | 40 | 

Adjacent cells would be [20, 21, 22, 29, 31, 38, 39, 40]

To get the top cells, We'd need to check if the current row isn't the first row since there is noting above the first row. Also you'd realize that the top cell is just the current_cell - number_of_columns in this case the top cell of 30 is 21 which is 30 - 9 and the bottom cell of 30 is current_cell + number_of_columns which in this case is 39. You'd also realize that the diagonal cells are the cells by the sides of the top and bottom cell. So to get the top diagonals we'd just minus and add 1 to the top cell, also to get the bottom
diagonals we'd minus and add 1 to the bottom cell.

Psuedocode

# add top cells
adjacent_cells = []
if row > 1:
    top = current_cell - number_of_columns
    adjacent_cells.push(top)

    # add the sides
    adjacent_cells.push(top-1)
    adjacent_cells.push(top+1)

# Add the sides of the current cell
adjacent_cells.push(current_cell-1)
adjacent_cells.push(current_cell+1)

# add bottom cells

if row < number_of_rows:
    bottom = current_cell + number_of_columns
    adjacent_cells.push(bottom)

    # add the sides
    adjacent_cells.push(bottom-1)
    adjacent_cells.push(bottom+1)


Note: extra checks would be done to make sure the right cells are added.
for example a cell at the edge would only have one valid cell by it side instead of 2

Here I would define a property function that gets adjacent cells:







































class Minesweeper:
    ...

    def adjacent_cells(self, pos, pos_row):
        adj_cells = []
        # top
        if pos_row > 1:
            t = pos - self.columns
            adj_cells.append(t)

            if t+1 < ((pos_row-1) * self.columns):
                adj_cells.append(t+1)

            if t-1 >= (((pos_row-1) * self.columns) - self.columns):
                adj_cells.append(t-1)      

        # sides
        if pos + 1 < (pos_row * self.columns):    
            adj_cells.append(pos+1)
        
        if pos - 1 > ((pos_row-1) * self.columns) - self.columns:    
            if pos -1 >= 0:
                adj_cells.append(pos-1)
        
        # bottom

        if pos_row < self.rows:
            b = pos + self.columns
            adj_cells.append(b)

            if b+1 < ((pos_row+1) * self.columns):
                adj_cells.append(b+1)

            if b-1 >= (pos_row * self.columns):
                adj_cells.append(b-1)     
        
        return sorted(adj_cells)

Now, I think you understand how the adjacent cells are gotten. We can now move forward with adding the clues.






































class Minesweeper:
    ...

    def new_game(self):
        ...

        # the row of the current position
        pos_row = 1

        # p is the position here
        for p, y in enumerate(range(0, self.bits, self.data_size)):

            adj_cells = self.adjacent_cells(p, pos_row)
            bombs = 0
            cell = (p * self.data_size)
            val = (self.grid >> cell) & BITMASK_CELL # gets the data of the current cell position

            if (val >> BITSHIFT_IS_BOMB) & 1 == 0: # checks if the current position is a bomb
                # looping through each adjacent cells and increments
                # the bomb count if the cell is a bomb
                for pos in adj_cells:
                    pos_cell = (pos * self.data_size)
                    pos_val = (self.grid >> pos_cell) & BITMASK_CELL # gets the data of the current cell position

                    if (pos_val >> BITSHIFT_IS_BOMB) & 1:
                        bombs += 1

                if bombs:
                    # adds the amount of bombs in adjacent cells to the grid
                    new_cell =  bombs << cell
                    self.grid |= new_cell


            # incrementing the row onces it gets to the end of a row
            y += self.data_size
            if y % (self.columns * self.data_size) == 0:
                pos_row += 1

Running the current code here is what we have to far.

game = Minesweeper(9,9)
game.new_game()
game.print_game(debug=True) # function not added here

========== OUTPUT =============
_  _  _  _  _  _  _  _  _ 
_  _  1  1  1  _  _  _  _ 
2  2  2  *  2  2  1  1  _ 
*  *  2  2  *  2  *  1  _ 
*  3  1  1  1  2  1  1  _ 
2  3  1  1  _  _  _  _  _ 
*  3  *  1  _  _  _  _  _ 
*  3  1  1  _  _  _  _  _ 
1  1  _  _  _  _  _  _  _ 

Note: It'd be different every time you run it since it is generated at random

Making Moves

I think the game is a little bit ready and it's not complete if a play can't make a move. So basically a player should be able to flag a cell and also reveal a cell. The functions here are just basically setting and checking bits. In this case of flag its setting the 7th bit.

























class Minesweeper:
    ...

    def flag(self, pos):
        """Lets a play flag a cell or position"""
        
        cell = (pos * self.data_size)
        _flag =  (1 << BITSHIFT_IS_FLAGED) << cell
        self.grid |= _flag

    def reveal(self, pos):
        """Lets a play reveal a cell or position. Also
        raises an exception is a player reveals a cell with
        a bomb
        """

        cell = (pos * self.data_size)
        val = (self.grid >> cell) & BITMASK_CELL

        if (val >> BITSHIFT_IS_BOMB) & 1:
            raise Exception("Game ended: revealed a bomb")

        reveal =  (1 << BITSHIFT_IS_REVEALED) << cell
        self.grid |= reveal

The full code is available on github.

Reference materials

Final Project: Minesweeper
Assignment 1: minesweeper, MIPS minesweeper
Implementation of Minesweeper Game
How to program MineSweeper in Python
Optimized tic-tac-toe game in Solidity
Bit Operations

If you found this helpful, consider following me on Twitter @0xosas.

Last changed by 
 
0xosas
0
282

Read more

Why you should revert early

Ethereum transactions that revert still have to pay the gas used up until the revert was triggered; If they run out of gas they pay the full limit. If they hits a revert opcode, probably from a require statement as a result of maybe an integer overflow check, they&apos;d pay the gas up until the revert opcode was hit. They don&apos;t pay for the gas afterwards. The implication is we should revert as early as possible in the execution to save the users gas incase a transaction reverts. Here are two (2) example contracts: // DO NOT USE IN PRODUCTION // USED FOR EXPLANATION ONLY contract Example1 { uint256 public a;

Aug 4, 2022
Ethereum block limit

The first crypto-currency Bitcion has limited a block size to 1-MB, and this is beacause if a block is too large it becomes expensive to store or sync with other nodes across the world or the blockchain. Ethereum doesn&apos;t place a block limit like Bitcion does, it just limits the total amount of computation on a single block since each computation has a gas cost. And the reason for this is, if a block has too much computation on it, it becomes difficult for nodes to verify the transactions quickly. So with a block limit set, if a transactions requires too much gas the transactions gets reverted. What is gas? Gas is a transaction unit that represents computational effort. It&#x2019;s the fuel you must buy to get miners to add your transaction to a block. At the time of writting the block limit is 30 million (30,000,000) gas; An eth transfer cost 21 thousand (21,000) gas, so doing the math you&apos;d see that a single block can hold just 1,428 transfers approximately. A few relating terms.

Aug 3, 2022
Optimized tic-tac-toe game in Solidity

Building on Ethereum can be expensive, and many times it intuitive to gain control over your code and one way to achieve this is by utilzing bit operations. Many developers use it as a means of optimization, expecially in the case of ethereum when you code now cost you money. Here I&apos;d be explaining a program I wrote not long ago, just so you&apos;d gain an understanding of a simple use case of bit operations. Also, I assume you understand how to work with bitwise operators, and if you don&apos;t check out my article on how they work here. What is Tic-tac-toe Tic-tac-toe is a 2 player game where players take turns to make a finite amount of moves until either all moves has been exhausted (its a draw) or a player has won. Here is a typical tic-tac-toe game. # an empty game # game where play x won

Aug 3, 2022
Bit Operations

This is an introduction to using bitwise operators and you&apos;d learn how to do magical stuffs with them. So basically bit operations are used to manipulate bits (binary numbers) and here are the signs used: Bitwise AND &amp; A bitwise AND is a binary operation that takes two bits and performs the logical AND operation on them. If the bits compared are 1, then bit in the resulting binary representation is 1 (1 &amp; 1 = 1); otherwise, the result is 0 (1 &amp; 0 = 0 and 0 &amp; 0 = 0) source. Here is a typical example: A B A &amp; B

Jul 27, 2022
Read more from 0xosas
Published on HackMD