# An experimental minsweeper implementation Well, this article is relating to my last [article on tictactoe game](https://hackmd.io/@0xosas/S1uWnLChq) 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](https://hackmd.io/@0xosas/B1H8OY03c) 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. ```python= 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. ```python= 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: ```python= 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: ```python= 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. ```python= 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. ```python= 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](https://gist.github.com/0xosas/8e1ade6a1a0b4067ba00c0094577f776). ## Reference materials [Final Project: Minesweeper](https://itp.uni-frankfurt.de/~mwagner/teaching/C_WS17/projects/Minesweeper.pdf) [Assignment 1: minesweeper, MIPS minesweeper](https://cgi.cse.unsw.edu.au/~cs1521/21T3/assignments/ass1/index.html) [Implementation of Minesweeper Game](https://www.geeksforgeeks.org/cpp-implementation-minesweeper-game/) [How to program MineSweeper in Python](https://replit.com/talk/learn/How-to-program-MineSweeper-in-Python-fully-explained-in-depth-tutorial/9397) [Optimized tic-tac-toe game in Solidity](https://hackmd.io/@0xosas/S1uWnLChq) [Bit Operations](https://hackmd.io/@0xosas/B1H8OY03c) ----- If you found this helpful, consider following me on Twitter [@0xosas](https://twitter.com/0xosas).
Last changed by  
 
0xosas
191

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'd pay the gas up until the revert opcode was hit. They don'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;

8/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'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’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'd see that a single block can hold just 1,428 transfers approximately. A few relating terms.

8/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'd be explaining a program I wrote not long ago, just so you'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'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

8/3/2022
Bit Operations

This is an introduction to using bitwise operators and you'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 & 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 & 1 = 1); otherwise, the result is 0 (1 & 0 = 0 and 0 & 0 = 0) source. Here is a typical example: A B A & B

7/27/2022
Read more from 0xosas
Published on HackMD