Related:
Minesweeper game written in python
How to Solve Minesweeper Using a Computer Program
The project address for the AI solution to the Minesweeper game implemented in this paper:
/devilmaycry812839668/AI_mine_game
The effect of the solution to the project:
Before the introduction of the Internet to solve some of the Minesweeper game some of the solutions, including DQN and heuristics and other AI algorithms, looking at the implementation of these individuals have some hand itching, so spent some time on their own with python code to implement a heuristic approach to solving the Minesweeper game algorithm.
To solve the game of Minesweeper, a lot of people give a lot of heuristic rules, but in fact, I personally think that there are just two or three, and those other rules belong to the derivation on the basis of those two or three, and in fact, it is enough to use those two or three rules.
Article I:
If a grid is uncovered and its display shows the same number of surrounding mines as the number of unrevealed grids out of the 8 surrounding grids, then it means that all these unrevealed grids are mined;
Article II:
If a grid is uncovered and its display shows the same number of surrounding mines as the number of surrounding 8 grids marked with mines, then it means that several other uncovered grids are mine-free.
Article III:
But having a third rule would somewhat increase our win ratio. (Attention:(Minesweeper has no certainty of victory in many cases, i.e., whether or not you can win in a certain situation depends on probability, and the algorithmic code we wrote can be seen as just trying to get as close to that probability as possible).
The third rule is that a grid displaying Ray's value can in some cases be optimized by the values of 24 nearby grids, e.g., if a grid has coordinates (x, y) then other grids labeled with a value in its range of -2, +2 are possible to simplify with it.
For example, if a grid with coordinates (x, y) has value 3, and its surrounding 8 grids are labeled with the number of mines as 0, and there are four unrevealed grids, and we assume that the true presence and absence of mines in these four unrevealed grids are represented by 0 or 1, respectively, then we can get the following equation:
a+b+c+d=3
And a grid with coordinates (x+2, y+2) yields the following equation:
a+b+c=2
Then we can conclude that the lattice with or without mine case denoted by d must have mine because.
set(a,b,c,d)-set(a,b,c)=d
3-2=1
Similarly, if one assumes that the numerical representation of a lattice of (x-2, y-2) is a + b + c + d + e = 3, then we can determine that the case of the lattice represented by e must be mine-free.
In fact, although the third is a set of operations, but its simulation is a human mathematical reasoning method, in the consideration of the use of this method before I once considered using python's linear algebra library to achieve this mathematical reasoning calculations, but the feeling of so engaged in some of the outrageous, and always feel that the problem should not be to this extent, and then stared at the game screen for a long time, and suddenly inspiration. Suddenly inspired, found that this reasoning process, although it seems to be a matrix operation kind of linear algebra operations, but if only a small range to see this is actually very simple linear algebra, because each variable can only take the value of 0 or 1, and can be completely using the for loop with the set set of operations to achieve the elimination of the way to simplify the use of simpler coding can be achieved! This reasoning process, and do not need to get into a linear math library, but later found that others on GitHub implementation are also roughly the way to use this set combined with a for loop to achieve the elimination of the operation, it seems that this is probably the right solution.
On the basis of these three rules, I also added the probability judgment, which is reflected in the random grid selection, we can be based on an unknown grid around (nearby 8) known grid display value and the number of unknown mines in these 8 grids and its periphery of the other grid to calculate the known grid on the target of the unknown grid of the probability of mines, we can take the unknown grid around the known grid We can take the known grids around the unknown grid to infer the probability of mine to take max, and then calculate how many unknown grids and how many mines, and then calculate the probability of mine of completely randomly selected grids, and then choose the smallest probability, so that we can find the smallest probability of mine of the grids, in order to achieve the smallest probability of triggering the mine.
Further down the line is to use the first two previous rules to determine if the grid just selected (assuming it's a trigger mine at this point) can be determined about the surrounding grids. However, here I add another rule, that is, a grid is uncovered to show the value will affect the reasoning of the unknown grids in its surrounding 8 grids, resulting in these 8 grids in the unknown grids may be reasoned out, so we will be the first to uncover the grids or marked grids its surrounding grids to save, and then these saved various judgment to see whether its surrounding grids can be reasoned out. out.
It should be noted that a grid is revealed to show the value or is marked with a mine, its surrounding affected by the possibility of deduction of the nearby 8 grids, which can be based on the first two rules given before the judgment and reasoning, but a grid is revealed to show the value or is marked with a mine after the 24 grids around its own, that is, a total of 25 grids of the set set are possible to reasoning Simplification, or what was previously known as the for+set implementation of the elimination operation. By combining these rules together there is also the code implementation given in this paper.
Final code implementation:
import numpy as np
import random
from typing import List
def belong_to(h, w, H, W):
near = []
for i in range(h-2, h+3):
for j in range(w-2, w+3):
if i>=0 and j>=0 and i<H and j<W and (i,j)!=(h,w):
((i, j))
return near
def near_by(h, w, H, W):
near = []
for i in range(h-1, h+2):
for j in range(w-1, w+2):
if i>=0 and j>=0 and i<H and j<W and (i,j)!=(h,w):
((i,j))
return near
def mine_count(h, w, real_state:, H, W):
count = 0
for i, j in near_by(h, w, H=H, W=W):
if real_state[i][j]==1:
count += 1
return count
class Env():
def __init__(self, H, W, N):
= H
= W
= N
# real statecenter0show that one is not aware of mines，1Indicates a mine.
self.real_state = ((H, W), dtype=np.int32)
= set()
while len()!=N:
((0, H*W-1))
for x in :
# print(x, , )
# print(self.real_state.shape)
self.real_state[x//][x%] = 1
# state_typecenter0show that one is not aware of mines，1-8Indicates a mine., Use this to indicate counts of nearby mines
self.state_type = ((H, W), dtype=np.int32)
for i in range(H):
for j in range(W):
self.state_type[i][j] = mine_count(h=i, w=j, H=H, W=W, real_state=self.real_state)
# obsbecause of-100Indicates not turned over(uncharted)，0-8Indicates open but no mines，The magnitude of the value indicates the number of mines around the flip position.
# agentstatus records for the，也可以用来作because of打印之用
= ((H, W), dtype=np.int32) -100
def act(self, i, j):
done = False
if [i][j]!=-100:
print("The location has already been revealed，repeat，error！！！")
return ValueError
if self.real_state[i][j] == 1:
# game over stir up trouble
done = True
return None, done
[i][j] = self.state_type[i][j]
return [i][j], done
def pp(self):
for i in range():
for j in range():
if [i][j]>=0:
print([i][j], end=' ')
else:
print('*', end=' ')
print()
def input(self):
while True:
i, j = input('Please enter coordinates:').split()
_, done = (int(i), int(j))
if done:
print('game over!!!')
print(self.real_state)
print(self.state_type)
break
()
# test item
# env=Env(5, 5, 5)
# ()
def play():
N = 99 # Number of mines
H = 16
W = 30
env = Env(H=H, W=W, N=N) # H=36, W=64, N=100
known_count_dict = {} # (2,2):3, (3,3):2
known_set = set() # (2, 2)
unknown_set = set()
boom_set = set()
for i in range(H):
for j in range(W):
unknown_set.add((i,j))
new_nodes = []
new_relation_nodes_set = set()
while(len(unknown_set)>0):
probs_list = [] # ((1,1), 0.5, 3), ((2,2), 0.5, 2) # (node, prob, count) # countbecause ofnodenearbyunknownnumber of individuals
for node in unknown_set:
p_list = []
n_c = 0 # nodenearbyunknown_node的number of individuals
for _node in near_by(*node, H, W):
if _node in unknown_set:
n_c += 1
if _node in known_set:
count = known_count_dict[_node]
n = 0
for _node_node in near_by(*_node, H, W):
if _node_node in unknown_set:
n += 1
if _node_node in boom_set:
count -= 1
p_list.append(count/n) # probability of lightning
p_list.append(N/len(unknown_set))
probs_list.append((node, max(p_list), n_c))
m_p = min(probs_list, key=lambda x:x[1])[1]
probs_list = [x for x in probs_list if x[1]==m_p]
node = min(probs_list, key=lambda x:x[2])[0]
count, done = (*node)
if done == True:
print('Failed game，stir up trouble，game over!!!')
print(node)
raise Exception
print("Successful completion of a step！！！ \n\n")
print("remove node:", node)
unknown_set.remove(node)
known_set.add(node)
known_count_dict[node] = count
() # Print the display of the current game environment
new_nodes.append(node)
new_relation_nodes_set.add(node)
while new_nodes or new_relation_nodes_set:
# debug
# print(new_nodes)
# print(new_relation_nodes_set)
while new_nodes:
node = new_nodes.pop()
k = 0
b = 0
count = known_count_dict[node]
tmp_unk = set()
for _node in near_by(*node, H, W):
if _node in known_set:
new_relation_nodes_set.add(_node)
# k += 1
continue
if _node in boom_set:
new_relation_nodes_set.add(_node)
b += 1
continue
tmp_unk.add(_node) # treat (sb a certain way)unknownNodes for judgment
count -= b
if count==len(tmp_unk):
# It's all thunder.
for _node in tmp_unk:
print("remove node:", _node)
unknown_set.remove(_node)
boom_set.add(_node)
new_relation_nodes_set.add(_node)
N -= 1
if count==0 and len(tmp_unk) > 0:
# It's not Ray at all.
for _node in tmp_unk:
c, done = (*_node)
if done:
print("programming error，Mistakenly triggered the mine.！！！")
raise Exception
print("remove node:", _node)
unknown_set.remove(_node)
known_set.add(_node)
known_count_dict[_node] = c
new_nodes.append(_node)
new_relation_nodes_set.add(_node)
while new_relation_nodes_set:
node = new_relation_nodes_set.pop()
tmp_set = set()
for i in range(-2, 3):
for j in range(-2, 3):
if node[0]+i>=0 and node[0]+i<H and node[1]+j>=0 and node[1]+j<W:
if (node[0]+i, node[1]+j) in known_set:
if known_count_dict[(node[0]+i, node[1]+j)]==0:
continue
tmp_set.add((node[0]+i, node[1]+j))
if len(tmp_set)==0:
continue
relations = []
for node in tmp_set: # node because of known set
tmp_tmp_set = set()
c = known_count_dict[node]
for _node in near_by(*node, H, W):
if _node in boom_set:
c -= 1
continue
if _node in unknown_set:
tmp_tmp_set.add(_node)
continue
if len(tmp_tmp_set)==0:
continue
([tmp_tmp_set, c, node])
if len(relations)<2:
continue
for i in range(0, len(relations)):
for j in range(1, len(relations)):
if relations[i][0].issuperset(relations[j][0]):
relations[i][0] -= relations[j][0]
relations[i][1] -= relations[j][1]
if relations[i][1]==len(relations[i][0]) and relations[i][1]>0:
# It's all thunder.
for _node in relations[i][0]:
if _node in boom_set:
continue
print("remove node:", _node)
unknown_set.remove(_node)
boom_set.add(_node)
new_relation_nodes_set.add(relations[i][2])
N -= 1
if relations[i][1]==0 and len(relations[i][0]):
# It's not Ray at all.
for _node in relations[i][0]:
if _node in known_set:
continue
c, done = (*_node)
if done:
print("programming error，Mistakenly triggered the mine.！！！")
raise Exception
print("remove node:", _node)
unknown_set.remove(_node)
known_set.add(_node)
known_count_dict[_node] = c
new_nodes.append(_node)
new_relation_nodes_set.add(_node)
if relations[j][0].issuperset(relations[i][0]):
relations[j][0] -= relations[i][0]
relations[j][1] -= relations[i][1]
if relations[j][1]==len(relations[j][0]) and relations[j][1]>0:
# It's all thunder.
for _node in relations[j][0]:
if _node in boom_set:
continue
print("remove node:", _node)
unknown_set.remove(_node)
boom_set.add(_node)
new_relation_nodes_set.add(relations[j][2])
N -= 1
if relations[j][1]==0 and len(relations[j][0]):
# It's not Ray at all.
for _node in relations[j][0]:
if _node in known_set:
continue
c, done = (*_node)
if done:
print("programming error，Mistakenly triggered the mine.！！！")
raise Exception
print("remove node:", _node)
unknown_set.remove(_node)
known_set.add(_node)
known_count_dict[_node] = c
new_nodes.append(_node)
new_relation_nodes_set.add(_node)
print('Game winning，game over!!!')
return True
sss = []
for xyz in range(30000):
try:
(play())
print('(prefix indicating ordinal number, e.g. first, number two etc) %d Sub-Game Success'%xyz)
except Exception:
print('(prefix indicating ordinal number, e.g. first, number two etc) %d 次Failed game！！！'%xyz)
continue
print("Number of successes： ", sum(sss))
print("Percentage of success： ", sum(sss)/30000)
Personal github blog address:
/