Skip to content

Instantly share code, notes, and snippets.

@lelandbatey

lelandbatey/probabilities.py

Last active December 31, 2022 01:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lelandbatey/0de584cf7cbf4bb07afce71b7c4c978f to your computer and use it in GitHub Desktop.
Save lelandbatey/0de584cf7cbf4bb07afce71b7c4c978f to your computer and use it in GitHub Desktop.
Download ZIP
Proto-minesweeper probability -- a kludged together POC for statistics of mines in squares
Raw
probabilities.py
'''
A toy example to calculate the probability of a mine existing on any particular square.
Runs slowly and is organized like spaghetti, but it does currently work!
Note that for this to work, it depends on a slightly modified defusedivision;
inside defuse_division the _create_foothold function in game.py has to be
modified to be public, instead of private like in the public version.
'''
from pprint import pprint
import random
import time
import re
random.seed(4)
from defusedivision.minesweeper import minefield as mf
from defusedivision.game import create_foothold
COLOR_RESET = "\x1b[0m"
COLOR_BLACK = "\x1b[30m"
COLOR_RED = "\x1b[31m"
COLOR_GREEN = "\x1b[32m"
COLOR_YELLOW = "\x1b[33m"
COLOR_BLUE = "\x1b[34m"
COLOR_MAGENTA = "\x1b[35m"
COLOR_CYAN = "\x1b[36m"
COLOR_WHITE = "\x1b[37m"
def extract_colornum(color):
ccode = re.search('\[3(.*?)m', color)
ccode = ccode.groups()[0].split(';')[0]
return ccode
def background(fg_color, bg_color):
fg_code = extract_colornum(fg_color)
bg_code = extract_colornum(bg_color)
return "\x1b[3{}m\x1b[4{}m".format(fg_code, bg_code)
def apply_color(color, instr):
return color + instr + COLOR_RESET
def iterCells(field, func):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
func(c)
def printField(field, func):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
func(c)
print("\n")
def printProbability(field):
def func(c):
contents = c.probability
contents = "{:^5.1f}".format(c.probability)
if c.probability == -1.0:
contents = "{:^5}".format(" ")
print(contents, flush=True, end="")
printField(field, func)
def printContents(field):
def func(c):
contents = c.contents
if c.mine_contacts() and not contents.strip():
contents = c.mine_contacts()
view = "{:^5}".format(contents)
if c.probed:
bg = background(COLOR_WHITE, COLOR_BLUE)
view = apply_color(bg, view)
if c.mine_contacts() == 0 and not c.probed:
bg = background(COLOR_BLACK, COLOR_WHITE)
view = apply_color(bg, view)
print(view, flush=True, end="")
# print('what')
printField(field, func)
def init_prob(c):
c.probability = -1.0
def probe_selected(field):
x, y = field.selected
field.board[x][y].probe()
# field = mf.MineField(height=None, width=None, mine_count=None)
field = mf.MineField(height=16, width=16, mine_count=None)
iterCells(field, init_prob)
field.selected = [5, 5]
create_foothold(field)
probe_selected(field)
def solved_cells(cell):
near = [n for _, n in cell.neighbors.items() if not n is None]
return [n for n in near if n.probability >= 1.0 or n.probability == 0 or n.probed]
def known_mines(cell):
near = [n for _, n in cell.neighbors.items() if not n is None]
return [n for n in near if n.probability >= 1.0]
def has_probed_neighbors(cell):
neighbors = [n for _, n in cell.neighbors.items() if not n is None and n.probed]
return len(neighbors)
def calc_prob(cell):
probs = []
if cell.probed:
cell.probability = 0.0
return
if cell.probability >= 1.0:
return
if not has_probed_neighbors(cell):
return
for _, c in cell.neighbors.items():
if c is None:
continue
# Number of valid cells I am touching
near = [n for _, n in c.neighbors.items() if not n is None]
# Cells which I know the value of for sure. They either 100% do contain
# a mine, or they 100% do not contain a mine.
solved = solved_cells(c)
# The number of cells that I'm touching which I know for sure contain a mine, and I know exactly which cell that mine is in.
explody = known_mines(c)
# The number of cells where I don't know for sure what they contain.
# They could be empty, they could contain a mine.
unsolved = len(near) - len(solved)
if unsolved == 0:
# We know that this is not a mine
c.probability = 0
elif len(explody) - c.mine_contacts() == 0:
# We, the neighbor c, know where all our neighbors who have mines
# are located. Thus, if you're our inquisitor cell, you can't have
# gotten this far if you had a mine, so Cell doesn't have a mine.
cell.probability = 0.0
return
else:
p = (c.mine_contacts() - len(explody)) / unsolved
if p == 1:
cell.probability = 1.0
for q in near:
calc_prob(q)
# calc_prob(cell)
# return
return
probs.append(p)
cell.probability = sum(probs)/len(probs)
# field.selected = [10, 2]
field.selected = [6, 9]
x, y = field.selected
calc_prob(field.board[x][y])
[calc_prob(n) for _, n in field.board[x][y].neighbors.items() if not n is None]
iterCells(field, calc_prob)
printContents(field)
printProbability(field)
Raw
probability2_queue_based.py
'''
An attempt to improve the rigour/implementation of calculating the probability
that a Cell contains a mine.
'''
from pprint import pprint
import random
import queue
import time
import sys
import re
import os
# Since cell probing is donre recursively, for large minefields with fiew
# mines, the default recursion limit may be reached.
sys.setrecursionlimit(5000)
seed = random.randint(0, 100000)
seed = 75322
# seed = 76390
# seed = 13902
#seed = 22390
# Cool seeds:
# 58623, 42621, 68526, 82834
# Broken seeds:
# 32146
# print("Seed: {}".format(seed))
random.seed(seed)
# Seed which causes invalid evaluation: 4463
# random.seed(76390)
from defusedivision.minesweeper import minefield as mf
from defusedivision.minesweeper import contents as cell_items
from defusedivision.game import create_foothold
COLOR_RESET = "\x1b[0m"
# COLOR_BLACK = "\x1b[30m"
# COLOR_RED = "\x1b[31m"
# COLOR_GREEN = "\x1b[32m"
# COLOR_YELLOW = "\x1b[33m"
# COLOR_BLUE = "\x1b[34m"
# COLOR_MAGENTA = "\x1b[35m"
# COLOR_CYAN = "\x1b[36m"
# COLOR_WHITE = "\x1b[37m"
COLOR_BLACK = "\x1b[30;1m"
COLOR_RED = "\x1b[31;1m"
COLOR_RED = "\x1b[48;2;255;0;0m"
COLOR_GREEN = "\x1b[32;1m"
COLOR_GREEN = "\x1b[48;2;0;225;0m"
COLOR_YELLOW = "\x1b[33;1m"
COLOR_YELLOW = "\x1b[48;2;255;225;0m"
COLOR_BLUE = "\x1b[34;1m"
COLOR_BLUE = "\x1b[48;2;0;0;255m"
COLOR_MAGENTA = "\x1b[35;1m"
COLOR_MAGENTA = "\x1b[48;2;255;0;255m"
COLOR_CYAN = "\x1b[36;1m"
COLOR_CYAN = "\x1b[48;2;0;255;255m"
COLOR_WHITE = "\x1b[37;1m"
COLOR_WHITE = "\x1b[48;2;245;245;245m"
COLOR_ORANGE = "\x1b[48;2;255;123;0m"
COLOR_GREY = "\x1b[48;2;225;225;225m"
def map_stat_color(stat):
stat = 1 - stat
base = "\x1b[48;2;{};{};255m"
v = (stat * 205) + 50
return base.format(int(v), int(v))
def extract_colornum(color):
ccode = re.search('\[3(.*?)m', color)
ccode = ccode.groups()[0].split(';')[0]
return ccode
def background(fg_color, bg_color):
fg_code = extract_colornum(fg_color)
bg_code = extract_colornum(bg_color)
return "\x1b[3{}m\x1b[4{}m".format(fg_code, bg_code)
def apply_color(color, instr):
return color + instr + COLOR_RESET
def iterCells(field, func):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
func(c)
def init_prob(c):
c.probability = -1.0
def printField(field, func):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
func(c)
print()
# print("\n")
def printProbability(field):
def func(c):
contents = c.probability
contents = "{:^5.1f}".format(c.probability)
if c.probability == -1.0:
contents = "{:^5}".format(" ")
print(contents, flush=True, end="")
printField(field, func)
def printContents(field):
def func(c):
contents = c.contents
if c.mine_contacts() and not contents.strip():
contents = c.mine_contacts()
view = "{:^5}".format(contents)
if c.probed:
# bg = background(COLOR_WHITE, COLOR_BLUE)
bg = COLOR_BLUE
view = apply_color(bg, view)
if c.mine_contacts() == 0 and not c.probed:
# bg = background(COLOR_BLACK, COLOR_WHITE)
bg = COLOR_WHITE
view = apply_color(bg, view)
print(view, flush=True, end="")
printField(field, func)
def visualizeStats(field):
def func(c):
base = " "
view = base
if c.probed:
view = str(c.mine_contacts())
if c.probability > 0.0 and c.probability < 1.0:
view = apply_color(map_stat_color(c.probability), view)
elif c.probability == -1.0 and not c.probed:
view = apply_color(COLOR_GREY, view)
elif c.probability == 0.0 and not c.probed:
view = apply_color(COLOR_WHITE, view)
if c.contents == cell_items.Contents.mine:
# bg = background(COLOR_WHITE, COLOR_RED)
bg = COLOR_GREY
if c.probability >= 1.0:
# bg = background(COLOR_BLACK, COLOR_GREEN)
bg = COLOR_GREEN
elif c.probability < 1.0 and c.probability > 0.0:
# bg = background(COLOR_WHITE, COLOR_BLUE)
bg = COLOR_ORANGE
pass
elif c.probability == -1.0:
# bg = background(COLOR_BLACK, COLOR_YELLOW)
# bg = COLOR_YELLOW
pass
view = apply_color(bg, base)
if c.contents != cell_items.Contents.mine and c.probability >= 1.0:
view = apply_color(COLOR_RED, view)
if [c.x, c.y] == field.selected:
view = apply_color(COLOR_MAGENTA, " ")
print(view, flush=True, end="")
for h in range(field.height):
print(" ", end="")
for w in range(field.width):
c = field.board[w][h]
func(c)
print()
def probe_selected(field):
x, y = field.selected
field.board[x][y].probe()
# This implementation based on this description of a minesweeper probability
# evaluation from stack overflow:
# http://stackoverflow.com/a/1738685
def clean_neighbors(cell):
'''
Returns a slice of neighbor Cells that are not None.
'''
return [n for _, n in sorted(cell.neighbors.items()) if not n is None]
def considerable_cell(cell):
'''
Returns whether a cell is 'considerable' or not. A cell is considerable
when it's one we have some information about. More rigorously, it's a cell
that has at least one neighbor that is probed, and at least one neighbor
that is not probed.
'''
p = False
np = False
for n in clean_neighbors(cell):
if n.probed:
p = True
if not n.probed:
np = True
return p and np
def enqueue_considerable(field, q):
done = [False]
def walk_enq(cell):
near = [c for c in clean_neighbors(cell) if considerable_cell(c)]
for c in near:
if not c in q.queue:
q.put(c)
walk_enq(c)
def enq(cell):
if considerable_cell(cell) and not done[0]:
# done[0] = True
q.put(cell)
# walk_enq(cell)
iterCells(field, enq)
def enqueue_uncertain_neighbors(cell, q):
for n in clean_neighbors(cell):
if n.probability < 1.0 and not n.probability == 0.0 and considerable_cell(
n):
q.put(n)
def calc_prob(cell, q):
# The probability is already known; ignore
if cell.probability == 0.0 or cell.probability >= 1.0:
recheck_neighbors = True
# return
if not cell.probed: return
# The cell's already been probed, ignore
if cell.probed:
cell.probability = 0.0
recheck_neighbors = True
# enqueue_uncertain_neighbors(cell, q)
recheck_neighbors = False
# count the number of mines you have revealed next to the cell. The number
# of "revealed mines" is the number of neighbors that have a probability of
# 1.0 of being a mine.
revealed_mines = [n for n in clean_neighbors(cell) if n.probability >= 1.0]
# From the number that is written in the square (the true number of mines
# that are around it), subtract the number of revealed mines. That is the
# number of unrevealed mines left around this square.
unrevealed_mines = cell.mine_contacts() - len(revealed_mines)
# Divide the number of unrevealed mines by the number of unrevealed cells
# around the current square. That is the probability of each of the
# adjacent square containing a mine.
# The neighboring cells which we're unsure about.
unrevealed_neighbors = [
n for n in clean_neighbors(cell)
if n.probability < 1.0 and not n.probability == 0.0 and not n.probed
]
prob = 0.0
if not unrevealed_neighbors:
if unrevealed_mines:
cell.probability = 0.0
# enqueue_uncertain_neighbors(cell, q)
recheck_neighbors = True
# return
else:
prob = unrevealed_mines / len(unrevealed_neighbors)
if prob < 0.0:
print("prob: {}, unrevealed_mines: {}, len(unrevealed_neighbors): {}".
format(prob, unrevealed_mines, len(unrevealed_neighbors)))
print("len(revealed_mines): {}, cell.mine_contacts(): {}".format(
len(revealed_mines), cell.mine_contacts()))
raise Exception
for n in unrevealed_neighbors:
if prob == 0.0 or prob >= 1.0:
n.probability = prob
recheck_neighbors = True
enqueue_uncertain_neighbors(n, q)
elif n.probability == -1.0:
n.probability = prob
enqueue_uncertain_neighbors(n, q)
else:
# Really bad running average of only two measurements
# new_prob = (n.probability + prob) / 2.0
new_prob = max(n.probability, prob)
# print(new_prob)
if new_prob != n.probability:
n.probability = new_prob
# enqueue_uncertain_neighbors(n, q)
if recheck_neighbors:
enqueue_uncertain_neighbors(cell, q)
def main():
# field = mf.MineField(height=32, width=32, mine_count=110)
width = 50
height = 30
mine_count = int(int(0.15 * (height * width)) * (4/5))
# mine_count = None
field = mf.MineField(height=height, width=width, mine_count=mine_count)
iterCells(field, init_prob)
field.selected = [int(width /2 ), int(height/2)]
create_foothold(field)
probe_selected(field)
q = queue.LifoQueue()
# Enqueue all cells we want to consider
enqueue_considerable(field, q)
while not q.empty():
cell = q.get()
field.selected = [cell.x, cell.y]
calc_prob(cell, q)
print("\r\x1b[1A" * (field.height + 3))
visualizeStats(field)
print("Seed: {}".format(seed))
time.sleep(0.100)
# printContents(field)
# printProbability(field)
print("\r\x1b[1A" * (field.height + 3))
visualizeStats(field)
# odd_cell = field.board[0][5]
# [calc_prob(x, q) for x in clean_neighbors(odd_cell) if considerable_cell(x)]
# calc_prob(odd_cell, q)
# pprint(odd_cell.__dict__)
# printContents(field)
print("Seed: {}".format(seed))
# print(field.mine_count)
if __name__ == '__main__':
main()
Raw
probability3_queue_and_ioccc.py
"""
Revisiting minsweeping after viewing one of the IOCCC 2020 winners here:
https://www.ioccc.org/2020/endoh1/index.html
"""
from typing import List, Dict, Tuple
from pprint import pprint
import random
import queue
import time
import sys
import re
import os
# Since cell probing is donre recursively, for large minefields with fiew
# mines, the default recursion limit may be reached.
sys.setrecursionlimit(5000)
seed = random.randint(0, 100000)
# seed = 88467
# seed = 75322
# seed = 76390
# seed = 13902
# seed = 22390
# Cool seeds:
# 58623, 42621, 68526, 82834
# Broken seeds:
# 32146
# print("Seed: {}".format(seed))
random.seed(seed)
# Seed which causes invalid evaluation: 4463
# random.seed(76390)
from defusedivision.minesweeper import minefield as mf
from defusedivision.minesweeper import contents as cell_items
from defusedivision.game import create_foothold
from defusedivision.minesweeper.minefield import Cell, MineField
from defusedivision.minesweeper.contents import Contents
COLOR_RESET = "\x1b[0m"
# COLOR_BLACK = "\x1b[30m"
# COLOR_RED = "\x1b[31m"
# COLOR_GREEN = "\x1b[32m"
# COLOR_YELLOW = "\x1b[33m"
# COLOR_BLUE = "\x1b[34m"
# COLOR_MAGENTA = "\x1b[35m"
# COLOR_CYAN = "\x1b[36m"
# COLOR_WHITE = "\x1b[37m"
COLOR_BLACK = "\x1b[30;1m"
COLOR_RED = "\x1b[31;1m"
COLOR_RED = "\x1b[48;2;255;0;0m"
COLOR_GREEN = "\x1b[32;1m"
COLOR_GREEN = "\x1b[48;2;0;225;0m"
COLOR_YELLOW = "\x1b[33;1m"
COLOR_YELLOW = "\x1b[48;2;255;225;0m"
COLOR_BLUE = "\x1b[34;1m"
COLOR_BLUE = "\x1b[48;2;0;0;255m"
COLOR_MAGENTA = "\x1b[35;1m"
COLOR_MAGENTA = "\x1b[48;2;255;0;255m"
COLOR_CYAN = "\x1b[36;1m"
COLOR_CYAN = "\x1b[48;2;0;255;255m"
COLOR_WHITE = "\x1b[37;1m"
COLOR_WHITE = "\x1b[48;2;245;245;245m"
COLOR_ORANGE = "\x1b[48;2;255;123;0m"
COLOR_GREY = "\x1b[48;2;225;225;225m"
def map_stat_color(stat):
stat = 1 - stat
base = "\x1b[48;2;{};{};255m"
v = (stat * 205) + 50
return base.format(int(v), int(v))
def extract_colornum(color):
ccode = re.search("\[3(.*?)m", color)
ccode = ccode.groups()[0].split(";")[0]
return ccode
def background(fg_color, bg_color):
fg_code = extract_colornum(fg_color)
bg_code = extract_colornum(bg_color)
return "\x1b[3{}m\x1b[4{}m".format(fg_code, bg_code)
def apply_color(color, instr):
return color + instr + COLOR_RESET
def cells(field: MineField):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
yield c
def iterCells(field, func):
for c in cells(field):
func(c)
# for h in range(field.height):
# for w in range(field.width):
# c = field.board[w][h]
# func(c)
def init_prob(c):
c.probability = -1.0
def printField(field, func):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
func(c)
print()
def visualizeStats(field):
def func(c):
base = " "
view = base
if c.probability > 0.0 and c.probability < 1.0:
view = apply_color(map_stat_color(c.probability), view)
elif c.probability == -1.0 and not c.probed:
view = apply_color(COLOR_GREY, view)
elif c.probability == 0.0 and not c.probed:
view = apply_color(COLOR_WHITE, view)
if c.contents == cell_items.Contents.mine:
bg = COLOR_GREY
if c.probability >= 1.0:
bg = COLOR_GREEN
elif c.probability < 1.0 and c.probability > 0.0:
bg = COLOR_ORANGE
elif c.probability == 0.0:
bg = COLOR_RED
view = apply_color(bg, base)
print(view, flush=True, end="")
return
elif c.probability == -1.0:
pass
view = apply_color(bg, base)
if c.contents != cell_items.Contents.mine and c.probability >= 1.0:
view = apply_color(COLOR_RED, view)
if [c.x, c.y] == field.selected:
view = apply_color(COLOR_MAGENTA, "X")
print(view, flush=True, end="")
return
if c.probed:
view = str(c.mine_contacts())
if c.contents == cell_items.Contents.mine:
view = "b"
print(view, flush=True, end="")
return
print(view, flush=True, end="")
for h in range(field.height):
print(" ", end="")
for w in range(field.width):
c = field.board[w][h]
func(c)
print()
def probe_selected(field):
x, y = field.selected
field.board[x][y].probe()
# This implementation based on this description of a minesweeper probability
# evaluation from stack overflow:
# http://stackoverflow.com/a/1738685
def clean_neighbors(cell) -> List[Cell]:
"""
Returns a slice of neighbor Cells that are not None.
"""
return [n for _, n in sorted(cell.neighbors.items()) if not n is None]
def considerable_cell(cell):
"""
Returns whether a cell is 'considerable' or not. A cell is considerable
when it's one we have some information about. More rigorously, it's a cell
that has at least one neighbor that is probed, and at least one neighbor
that is not probed.
"""
p = False
np = False
for n in clean_neighbors(cell):
if n.probed:
p = True
if not n.probed:
np = True
return p and np
def enqueue_considerable(field, q):
done = [False]
def enq(cell: Cell):
if considerable_cell(cell) and not done[0]:
q.put(cell)
iterCells(field, enq)
def enqueue_uncertain_neighbors(cell, q):
for n in clean_neighbors(cell):
if n.probability < 1.0 and not n.probability == 0.0 and considerable_cell(n):
q.put(n)
def rule_one(cell: Cell, q):
if not cell.probed:
return
# 1. If the number of a cell.mine_contacts() is equal to the count of the
# flagged neighbors, all the unprobed neighbors are probed.
revealed_mines = [n for n in clean_neighbors(cell) if n.probability >= 1.0]
unrevealed_mines = cell.mine_contacts() - len(revealed_mines)
# The neighboring cells which we're unsure about.
unrevealed_neighbors = [
n
for n in clean_neighbors(cell)
if n.probability < 1.0 and not n.probability == 0.0 and not n.probed
]
if unrevealed_mines == 0:
for n in unrevealed_neighbors:
n.probability = 0.0
n.probe()
if n.contents == cell_items.Contents.mine:
raise ValueError("probed a mine in rule 1")
return
def rule_two(cell: Cell, q):
if not cell.probed:
return
# 2. If the number of a cell.mine_contacts() is equal to the count of the
# unprobed or flagged neighbors, all the unprobed neighbors are flagged,
unprobed_neighbors = [n for n in clean_neighbors(cell) if not n.probed]
unprobed_or_flagged_neighbors = [
n for n in clean_neighbors(cell) if not n.probed or n.probability >= 1.0
]
if cell.mine_contacts() == len(unprobed_or_flagged_neighbors):
for n in unprobed_neighbors:
n.probability = 1.0
n.flagged = True
return
def rule_three(cell: Cell, q):
if not cell.probed:
return
# 3. Consider two number cells A and B. If A.mine_contacts() is equal to
# the difference of (B.mine_contacts()) and (the count of B's unprobed and
# flagged neighbors that are not A's neighbors), all A's unprobed
# neighbors that are not B's neighbors are probed.
#
# if A.mine_contacts() == (B.mine_contacts() -
# ( (B's unprobed neighbors which are not A's neighbors) +
# (B's flagged neighbors which are not A's neighbors) ):
probed_neighbors: List[Cell] = [n for n in clean_neighbors(cell) if n.probed]
for n in probed_neighbors:
A = cell
B = n
# print(f"{B=}")
# print(f"{B.mine_contacts()=}")
# the count of B's uprobed and flagged neighbors which are not A's neighbors
Aneighbors = clean_neighbors(A)
Bneighbors = clean_neighbors(B)
Bneighbor_but_not_Aneighbor = [C for C in Bneighbors if not C in Aneighbors]
Aneighbor_but_not_Bneighbor = [C for C in Aneighbors if not C in Bneighbors]
B_unprobed_not_Aneighbor = [
C for C in Bneighbor_but_not_Aneighbor if not C.probed
]
B_flagged_not_Aneighbor = [C for C in Bneighbor_but_not_Aneighbor if C.flagged]
B_count = set(B_unprobed_not_Aneighbor + B_flagged_not_Aneighbor)
count = B.mine_contacts() - (
len(B_count)
# len(B_unprobed_not_Aneighbor) + len(B_flagged_not_Aneighbor)
)
if A.mine_contacts() == count:
A_unprobed_not_B_neighbors = [
n for n in Aneighbor_but_not_Bneighbor if not n.probed
]
for n in A_unprobed_not_B_neighbors:
# print("Probed!" * 50)
# n.probe()
n.probed = True
n.probability = 0.0
if n.contents == cell_items.Contents.mine:
print("\n" * 8, "n:", n)
print(f"{len(A_unprobed_not_B_neighbors)=}")
print(f"{len(B_unprobed_and_flagged_neighbors_not_Aneighbor)=}")
print(f"{B.mine_contacts()=}")
print(
"\n".join(
f"B {c} prob={c.probability}" for c in clean_neighbors(A)
)
)
print(
"\n".join(
f"A {c} prob={c.probability}" for c in clean_neighbors(B)
)
)
print(f"{A=}")
print(f"{B=}")
print(f"{n=}")
raise ValueError("probed a mine in rule 3")
def rule_four(cell: Cell, q):
if not cell.probed:
return
# Consider two number cells A and B. If B.mine_contacts() is equal to the difference of A
# and the count of A's unprobed and flagged neighbors that are not B's
# neighbors, all A's unprobed neighbors that are not B's neighbors are
# flagged.
probed_neighbors: List[Cell] = [n for n in clean_neighbors(cell) if n.probed]
for n in probed_neighbors:
A = cell
B = n
Aneighbors = clean_neighbors(A)
Bneighbors = clean_neighbors(B)
Bneighbor_but_not_Aneighbor = [C for C in Bneighbors if not C in Aneighbors]
Aneighbor_but_not_Bneighbor = [C for C in Aneighbors if not C in Bneighbors]
count = A.mine_contacts() - len(
[C for C in Aneighbor_but_not_Bneighbor if C.flagged or (not C.probed)]
)
if B.mine_contacts() == count:
for C in [
n for n in Aneighbors if (not n in Bneighbors) and (not n.probed)
]:
C.flagged = True
def calc_prob(cell, q):
# The probability is already known; ignore
if cell.probability == 0.0 or cell.probability >= 1.0:
recheck_neighbors = True
# return
if not cell.probed:
return
# The cell's already been probed, ignore
if cell.probed:
cell.probability = 0.0
recheck_neighbors = True
# enqueue_uncertain_neighbors(cell, q)
recheck_neighbors = False
# count the number of mines you have revealed next to the cell. The number
# of "revealed mines" is the number of neighbors that have a probability of
# 1.0 of being a mine.
revealed_mines = [n for n in clean_neighbors(cell) if n.probability >= 1.0]
# From the number that is written in the square (the true number of mines
# that are around it), subtract the number of revealed mines. That is the
# number of unrevealed mines left around this square.
unrevealed_mines = cell.mine_contacts() - len(revealed_mines)
# Divide the number of unrevealed mines by the number of unrevealed cells
# around the current square. That is the probability of each of the
# adjacent square containing a mine.
# The neighboring cells which we're unsure about.
unrevealed_neighbors = [
n
for n in clean_neighbors(cell)
if n.probability < 1.0 and not n.probability == 0.0 and not n.probed
]
prob = 0.0
if not unrevealed_neighbors:
if unrevealed_mines:
cell.probability = 0.0
# enqueue_uncertain_neighbors(cell, q)
recheck_neighbors = True
# return
else:
prob = unrevealed_mines / len(unrevealed_neighbors)
if prob < 0.0:
print(
"prob: {}, unrevealed_mines: {}, len(unrevealed_neighbors): {}".format(
prob, unrevealed_mines, len(unrevealed_neighbors)
)
)
print(
"len(revealed_mines): {}, cell.mine_contacts(): {}".format(
len(revealed_mines), cell.mine_contacts()
)
)
raise Exception
for n in unrevealed_neighbors:
if prob == 0.0 or prob >= 1.0:
n.probability = prob
if n.probability == 0.0:
n.probe()
if n.contents == cell_items.Contents.mine:
raise ValueError("probed a mine in later enforcement")
recheck_neighbors = True
enqueue_uncertain_neighbors(n, q)
elif n.probability == -1.0:
n.probability = prob
enqueue_uncertain_neighbors(n, q)
else:
# Really bad running average of only two measurements
new_prob = max(n.probability, prob)
if new_prob != n.probability:
n.probability = new_prob
if n.probability >= 1.0:
n.flagged = True
if recheck_neighbors:
enqueue_uncertain_neighbors(cell, q)
def probeSafeCells(cell: Cell):
if cell.probability == 0.0:
cell.probe()
if cell.contents == cell_items.Contents.mine:
raise ValueError("probed a mine in later enforcement")
def parse_board_shorthand(s: str) -> MineField:
rows = s.split("\n")
rows = [r.strip() for r in rows if r.strip()]
ln = len(rows[0])
for row in rows:
assert len(row) == ln
height = len(rows)
width = ln
field = mf.MineField(height=height, width=width, mine_count=0)
for h in range(height):
for w in range(width):
strcell = rows[h][w]
con = Contents.empty
if strcell.lower() == "b":
con = Contents.mine
field.board[w][h].contents = con
# field.board[w][h].probe()
return field
def main():
width = 150
height = 50
mine_count = int(int(0.15 * (height * width)) * (4 / 5))
mine_count = int(int(0.15 * (height * width)) * (7 / 5))
field = mf.MineField(height=height, width=width, mine_count=mine_count)
# field = parse_board_shorthand(
# """
# 0000b000
# b0b0000b
# 00000000
# """
# )
iterCells(field, init_prob)
height = field.height
width = field.width
field.selected = [int(width / 2), int(height / 2)]
# field.selected = [8, 4]
# field.selected = [5, 2]
create_foothold(field)
probe_selected(field)
cellcheckcount = dict()
q = queue.LifoQueue()
for _ in range(10):
for rule in [rule_one, rule_two, rule_three, rule_four]:
# visualizeStats(field)
# print("\r\x1b[1A" * (field.height + 1))
for cell in cells(field):
field.selected = [cell.x, cell.y]
try:
rule(cell, q)
except Exception as e:
visualizeStats(field)
print("\n" * 20)
raise e
try:
visualizeStats(field)
print("Seed: {}".format(seed))
print("\r\x1b[1A" * (field.height + 2))
except KeyboardInterrupt as e:
# visualizeStats(field)
print("\n" * 50)
raise e
continue
visualizeStats(field)
count = 0
for _ in range(2000):
# Enqueue all cells we want to consider
enqueue_considerable(field, q)
while not q.empty():
cell: Cell = q.get()
if not cell in cellcheckcount:
cellcheckcount[cell] = 0
field.selected = [cell.x, cell.y]
try:
calc_prob(cell, q)
except Exception as e:
visualizeStats(field)
print("\n" * 20)
print(field.selected)
raise e
# if (cellcheckcount[cell] + 1) % 98 == 0:
if count % 98 == 0:
# if True:
visualizeStats(field)
print("Seed: {}".format(seed))
print("\r\x1b[1A" * (field.height + 2))
cellcheckcount[cell] += 1
count += 1
# time.sleep(0.010)
iterCells(field, probeSafeCells)
print("\r\x1b[1A" * (field.height + 3))
visualizeStats(field)
print("Seed: {}".format(seed))
if __name__ == "__main__":
main()
Raw
probability_rules_test.py
from typing import List, Dict, Tuple
from pprint import pprint
import random
import queue
import time
import sys
import re
import io
import os
import difflib
import columnize
from defusedivision.minesweeper import minefield as mf
from defusedivision.minesweeper import contents as cell_items
from defusedivision.game import create_foothold
from defusedivision.minesweeper.minefield import Cell, MineField
from defusedivision.minesweeper.contents import Contents
def unidiff_output(expected: str, actual: str) -> str:
"""
Helper function. Returns a string containing the unified diff of two multiline strings.
"""
expected = expected.splitlines(1)
actual = actual.splitlines(1)
diff = difflib.unified_diff(expected, actual)
return "".join(diff)
def clean_neighbors(cell) -> List[Cell]:
"""Returns a slice of neighbor Cells that are not None."""
return [n for _, n in sorted(cell.neighbors.items()) if not n is None]
def cells(field: MineField):
for h in range(field.height):
for w in range(field.width):
c = field.board[w][h]
yield c
def parse_board_shorthand(s: str) -> MineField:
# rows is 2-d array with 0, 0 in top left
rows = s.split("\n")
rows = [r.strip() for r in rows if r.strip()]
ln = len(rows[0])
for row in rows:
assert len(row) == ln
height = len(rows)
width = ln
# field.board is 2d array with 0, 0 in bottom left
field = mf.MineField(height=height, width=width, mine_count=0)
DIGITS = set(str(n) for n in range(0, 10))
for h in range(height):
for w in range(width):
strcell = rows[h][w]
cell = field.board[w][h]
if strcell.lower() == "b":
cell.contents = Contents.mine
cell.probed = False
cell.flagged = False
if strcell == "!":
cell.contents = Contents.mine
cell.probed = False
cell.flagged = True
if (strcell.lower() in DIGITS) or (strcell == "."):
cell.contents = Contents.empty
cell.probed = True
cell.flagged = False
if strcell == ".":
cell.probability = 0.0
if strcell == "?":
cell.probed = False
cell.flagged = False
# verify the string form of the board checks out with the mines
for h in range(height):
for w in range(width):
strcell = rows[h][w]
cell = field.board[w][h]
if strcell.lower() in DIGITS:
count = int(strcell)
try:
assert cell.mine_contacts() == count
except AssertionError as e:
print("\n\nAssertion Error:")
for idx, r in enumerate(rows):
print(" ", r)
print(display_board_both(field))
print(f"{strcell=}")
print(f"{cell=}")
print(f"{cell.mine_contacts()=}")
print(f"{count=}")
raise e
return field
def display_board_omniscient(field: MineField) -> str:
s = io.StringIO()
print("omniscient:", file=s)
for ypos in list(range(0, field.height)):
for xpos in range(0, field.width):
cell: Cell = field.board[xpos][ypos]
fill = " "
cont = str(cell.mine_contacts())
if cell.contents == Contents.mine:
cont = "b"
if cell.flagged:
cont = "!"
print(fill + cont, end="", file=s)
print(file=s)
return s.getvalue()
def display_board_ambiguous(field: MineField) -> str:
s = io.StringIO()
print("ambiguous:", file=s)
for ypos in list(range(0, field.height)):
for xpos in range(0, field.width):
cell: Cell = field.board[xpos][ypos]
fill = " "
cont = "?"
if cell.probed:
cont = str(cell.mine_contacts())
if cell.mine_contacts() == 0:
cont = "."
if cell.flagged:
cont = "!"
print(fill + cont, end="", file=s)
print(file=s)
return s.getvalue()
def display_board_both(field: MineField) -> str:
ambig = display_board_ambiguous(field)
omnis = display_board_omniscient(field)
fmtchunk = columnize.columnize(zip(ambig.splitlines(), omnis.splitlines()))
s = ""
for row in fmtchunk:
s += " ".join(row).strip() + "\n"
return s
def rule_one(cell: Cell):
if not cell.probed:
return
# 1. If the number of a cell.mine_contacts() is equal to the count of the
# flagged neighbors, all the unprobed neighbors are probed.
revealed_mines = [n for n in clean_neighbors(cell) if n.flagged]
unrevealed_mines = cell.mine_contacts() - len(revealed_mines)
# The neighboring cells which we're unsure about.
unrevealed_neighbors = [
n
for n in clean_neighbors(cell)
if n.probability < 1.0 and not n.probability == 0.0 and not n.probed
]
if unrevealed_mines == 0:
for n in unrevealed_neighbors:
n.probability = 0.0
n.probe()
if n.contents == cell_items.Contents.mine:
raise ValueError("probed a mine in rule 1")
return
def rule_two(cell: Cell):
if not cell.probed:
return
# 2. If the number of a cell.mine_contacts() is equal to the count of the
# unprobed or flagged neighbors, all the unprobed neighbors are flagged,
unprobed_neighbors = [n for n in clean_neighbors(cell) if not n.probed]
unprobed_or_flagged_neighbors = [
n for n in clean_neighbors(cell) if not n.probed or n.probability >= 1.0
]
if cell.mine_contacts() == len(unprobed_or_flagged_neighbors):
for n in unprobed_neighbors:
n.probability = 1.0
n.flagged = True
return
def rule_three(cell: Cell):
if not cell.probed:
return
# 3. Consider two number cells A and B. If A.mine_contacts() is equal to
# the difference of (B.mine_contacts()) and (the count of B's unprobed and
# flagged neighbors that are not A's neighbors), all A's unprobed
# neighbors that are not B's neighbors are probed.
#
# if A.mine_contacts() == (B.mine_contacts() -
# ( (B's unprobed neighbors which are not A's neighbors) +
# (B's flagged neighbors which are not A's neighbors) ):
probed_neighbors: List[Cell] = [n for n in clean_neighbors(cell) if n.probed]
for n in probed_neighbors:
A = cell
B = n
# print(f"{B=}")
# print(f"{B.mine_contacts()=}")
# the count of B's uprobed and flagged neighbors which are not A's neighbors
Aneighbors = clean_neighbors(A)
Bneighbors = clean_neighbors(B)
Bneighbor_but_not_Aneighbor = [C for C in Bneighbors if not C in Aneighbors]
Aneighbor_but_not_Bneighbor = [C for C in Aneighbors if not C in Bneighbors]
B_unprobed_not_Aneighbor = [
C for C in Bneighbor_but_not_Aneighbor if not C.probed
]
B_flagged_not_Aneighbor = [C for C in Bneighbor_but_not_Aneighbor if C.flagged]
B_count = set(B_unprobed_not_Aneighbor + B_flagged_not_Aneighbor)
count = B.mine_contacts() - (
len(B_count)
# len(B_unprobed_not_Aneighbor) + len(B_flagged_not_Aneighbor)
)
if A.mine_contacts() == count:
A_unprobed_not_B_neighbors = [
n for n in Aneighbor_but_not_Bneighbor if not n.probed
]
for n in A_unprobed_not_B_neighbors:
# print("Probed!" * 50)
# n.probe()
n.probed = True
n.probability = 0.0
if n.contents == cell_items.Contents.mine:
print("\n" * 8, "n:", n)
print(f"{len(A_unprobed_not_B_neighbors)=}")
print(f"{len(B_unprobed_and_flagged_neighbors_not_Aneighbor)=}")
print(f"{B.mine_contacts()=}")
print(
"\n".join(
f"B {c} prob={c.probability}" for c in clean_neighbors(A)
)
)
print(
"\n".join(
f"A {c} prob={c.probability}" for c in clean_neighbors(B)
)
)
print(f"{A=}")
print(f"{B=}")
print(f"{n=}")
raise ValueError("probed a mine in rule 3")
def rule_four(cell: Cell):
if not cell.probed:
return
# Consider two number cells A and B. If B.mine_contacts() is equal to the difference of A
# and the count of A's unprobed and flagged neighbors that are not B's
# neighbors, all A's unprobed neighbors that are not B's neighbors are
# flagged.
probed_neighbors: List[Cell] = [n for n in clean_neighbors(cell) if n.probed]
for n in probed_neighbors:
A = cell
B = n
Aneighbors = clean_neighbors(A)
Bneighbors = clean_neighbors(B)
Bneighbor_but_not_Aneighbor = [C for C in Bneighbors if not C in Aneighbors]
Aneighbor_but_not_Bneighbor = [C for C in Aneighbors if not C in Bneighbors]
count = A.mine_contacts() - len(
[C for C in Aneighbor_but_not_Bneighbor if C.flagged or (not C.probed)]
)
if B.mine_contacts() == count:
for C in [
n for n in Aneighbors if (not n in Bneighbors) and (not n.probed)
]:
C.flagged = True
def main():
# Notation:
# Chr Mined probed??? probability flagged
# ? unknown, unprobed, -1 noflag
# ! mine, unprobed, 1.0 flag
# 0-9 no mine probed 0.0 noflag
# . no mine probed 0.0 noflag
# b mine unprobed -1.0 noflag
rule1_begin = """
???
?3?
!!!
"""
rule1_end = """
...
.3.
!!!
"""
rule2_begin = """
.bb
.4b
.2!
"""
rule2_end = """
.!!
.4!
.2!
"""
rule3_begin = """
???.
?1bb
??4.
.b.!
"""
rule3_end = """
....
.1bb
.?4.
.b.!
"""
rule4_begin = """
b?b?
b31.
....
"""
rule4_end = """
!?b?
!31.
....
"""
# mf = MineField(width=2, height=10, mine_count=0)
# from pprint import pprint
# pprint(mf.json())
# for ridx, row in enumerate(mf.board):
# print(ridx, row)
# return
cases = [
# ("1", rule_one, rule1_begin, rule1_end),
# ("2", rule_two, rule2_begin, rule2_end),
("3", rule_three, rule3_begin, rule3_end),
("4", rule_four, rule4_begin, rule4_end),
]
for cs in cases:
name = cs[0]
rule = cs[1]
inptstr = cs[2]
exptstr = cs[3]
try:
inptboard = parse_board_shorthand(inptstr)
exptboard = parse_board_shorthand(exptstr)
mutated = mf.minefield_from_json(inptboard.json())
# rule(mutated.board[1][1])
for cell in cells(mutated):
rule(cell)
# except Exception as e:
# print("\n!!EXCEPTION!!")
# print(f"{name=}")
# print(f"{rule=}")
# print(f"inptstr: {inptstr}")
# print(f"exptstr: {exptstr}")
# raise e
#
# try:
assert exptboard.json() == mutated.json()
except Exception as e:
print("\n!!EXCEPTION!!")
print(f"{name=}")
print(f"{rule=}")
print(f"inptstr: {inptstr}")
print(f"exptstr: {exptstr}")
print("exptboard:")
print(display_board_both(exptboard))
print("mutated:")
print(display_board_both(mutated))
print(
unidiff_output(
mf.json_dump(exptboard.json()), mf.json_dump(mutated.json())
)
)
raise e
print("Done!")
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment