I am doing a CS50’s Introduction to Artificial Intelligence with Python course and I enjoy it very much. When I run my script, it seems its all working well, but CS50 checker finds some kind of edge case where my software apparently does not find a safe cell when inferring knowledge. Here is the CS50 specification focused on the part that is not passing the test:
Specification
Complete the implementations of the
Sentenceclass and theMinesweeperAIclass inminesweeper.py.
In the
Sentenceclass, complete the implementations ofknown_mines,known_safes,mark_mine, andmark_safe.The
known_minesfunction should return a set of all of the cells inself.cellsthat are known to be mines.The
known_safesfunction should return a set of all the cells inself.cellsthat are known to be safe.The
mark_minefunction should first check to see ifcellis one of the cells included in the sentence.
If
cellis in the sentence, the function should update the sentence so thatcellis no longer in the sentence, but still represents a logically correct sentence given thatcellis known to be a mine.If
cellis not in the sentence, then no action is necessary.The
mark_safefunction should first check to see ifcellis one of the cells included in the sentence.
If
cellis in the sentence, the function should update the sentence so thatcellis no longer in the sentence, but still represents a logically correct sentence given thatcellis known to be safe.If
cellis not in the sentence, then no action is necessary.In the
MinesweeperAIclass, complete the implementations ofadd_knowledge,make_safe_move, andmake_random_move.
add_knowledgeshould accept acell(represented as a tuple(i, j)) and its correspondingcount, and updateself.mines,self.safes,self.moves_made, andself.knowledgewith any new information that the AI can infer, given thatcellis known to be a safe cell withcountmines neighboring it.
The function should mark the
cellas one of the moves made in the game.The function should mark the
cellas a safe cell, updating any sentences that contain thecellas well.The function should add a new sentence to the AI’s knowledge base, based on the value of
cellandcount, to indicate thatcountof thecell’s neighbors are mines. Be sure to only include cells whose state is still undetermined in the sentence.If, based on any of the sentences in
self.knowledge, new cells can be marked as safe or as mines, then the function should do so.If, based on any of the sentences in
self.knowledge, new sentences can be inferred (using the subset method described in the Background), then those sentences should be added to the knowledge base as well.Note that any time that you make any change to your AI’s knowledge, it may be possible to draw new inferences that weren’t possible before. Be sure that those new inferences are added to the knowledge base if it is possible to do so.
Here is my code (most of the task is completed, so if you don't want to spoil it, do not proceed):
import itertools
import random
import copy
"""
- cut code related to setting up a board of 8x8 cells with 8 mines spread around randomly in them.
"""
class Sentence:
"""
Logical statement about a Minesweeper game
A sentence consists of a set of board cells,
and a count of the number of those cells which are mines.
"""
def __init__(self, cells, count):
self.cells = set(cells)
self.count = count
def __eq__(self, other):
return self.cells == other.cells and self.count == other.count
def __str__(self):
return f"{self.cells} = {self.count}"
def known_mines(self):
"""
Returns the set of all cells in self.cells known to be mines.
"""
if len(self.cells) == self.count != 0:
return self.cells
else:
return set()
def known_safes(self):
"""
Returns the set of all cells in self.cells known to be safe.
"""
if self.count == 0:
return self.cells
else:
return set()
def mark_mine(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be a mine.
"""
if cell in self.cells:
self.cells.remove(cell)
self.count -= 1
return True
return False
def mark_safe(self, cell):
"""
Updates internal knowledge representation given the fact that
a cell is known to be safe.
"""
if cell in self.cells:
self.cells.remove(cell)
return True
return False
class MinesweeperAI:
"""
Minesweeper game player
"""
def __init__(self, height=8, width=8):
# Set initial height and width
self.height = height
self.width = width
# Keep track of which cells have been clicked on
self.moves_made = set()
# Keep track of cells known to be safe or mines
self.mines = set()
self.safes = set()
# List of sentences about the game known to be true
self.knowledge = []
def mark_mine(self, cell):
"""
Marks a cell as a mine, and updates all knowledge
to mark that cell as a mine as well.
"""
self.mines.add(cell)
for sentence in self.knowledge:
sentence.mark_mine(cell)
def mark_safe(self, cell):
"""
Marks a cell as safe, and updates all knowledge
to mark that cell as safe as well.
"""
self.safes.add(cell)
for sentence in self.knowledge:
sentence.mark_safe(cell)
def nearby_cells(self, cell):
"""
Returns set of cells around the given cell.
"""
# Keep count of nearby mines
cells = set()
# Loop over all cells within one row and column
for i in range(cell[0] - 1, cell[0] + 2):
for j in range(cell[1] - 1, cell[1] + 2):
# Ignore the cell itself
if (i, j) == cell:
continue
# Add cell to set if cell in bounds
if 0 <= i < self.height and 0 <= j < self.width:
cells.add((i, j))
return cells
def add_sentence(self, cells, count):
# Create new sentence based on the nearby cells and known mines and safe cells.
newSentence = Sentence(cells, count)
self.knowledge.append(newSentence)
# Check new sentence for discoveries.
for cell in copy.deepcopy(newSentence.known_safes()):
if cell not in self.safes:
self.mark_safe(cell)
for cell in copy.deepcopy(newSentence.known_mines()):
if cell not in self.mines:
self.mark_mine(cell)
# Remove empty sentences:
for sentence in self.knowledge:
if len(sentence.cells) == 0:
self.knowledge.remove(sentence)
# Add mines and safes from inferred sentences:
for sentence in self.knowledge:
if len(sentence.cells) == sentence.count:
for cell in copy.deepcopy(sentence.cells):
self.mark_mine(cell)
self.knowledge.remove(sentence)
continue
if sentence.count == 0:
for cell in copy.deepcopy(sentence.cells):
self.mark_safe(cell)
self.knowledge.remove(sentence)
continue
# Remove same sentences
updatedKnowledge = []
for sentence in self.knowledge:
if sentence not in updatedKnowledge:
updatedKnowledge.append(sentence)
self.knowledge = updatedKnowledge
# Infer knowledge based on new sentence
if len(self.knowledge) > 1:
for sentence in self.knowledge:
if sentence != newSentence:
if sentence.cells.issubset(newSentence.cells):
inferredSet = Sentence(
newSentence.cells - sentence.cells,
newSentence.count - sentence.count,
)
if inferredSet not in self.knowledge:
self.add_sentence(
newSentence.cells - sentence.cells,
newSentence.count - sentence.count,
)
if newSentence.cells.issubset(sentence.cells):
inferredSet2 = Sentence(
sentence.cells - newSentence.cells,
sentence.count - newSentence.count,
)
if inferredSet2 not in self.knowledge:
self.add_sentence(
sentence.cells - newSentence.cells,
sentence.count - newSentence.count,
)
def add_knowledge(self, cell, count):
"""
Called when the Minesweeper board tells us, for a given
safe cell, how many neighboring cells have mines in them.
This function should:
1) mark the cell as a move that has been made
2) mark the cell as safe
3) add a new sentence to the AI's knowledge base
based on the value of `cell` and `count`
4) mark any additional cells as safe or as mines
if it can be concluded based on the AI's knowledge base
5) add any new sentences to the AI's knowledge base
if they can be inferred from existing knowledge
"""
# Mark cell as the move made
self.moves_made.add(cell)
# Mark cell as safe
self.mark_safe(cell)
# Get nearby cells and substract known mines and safe cells
NearbyCells = self.nearby_cells(cell)
validNearbyCells = copy.deepcopy(NearbyCells)
for cell in NearbyCells:
if cell in self.safes:
validNearbyCells.discard(cell)
if cell in self.mines:
validNearbyCells.discard(cell)
count -= 1
# Add new sentence and infer knowledge based on added sentence
self.add_sentence(validNearbyCells, count)
After I run my script through CS50 check function this is the output:
:) minesweeper.py exists
:) minesweeper.py imports
:) Sentence.known_mines returns mines when conclusions possible
:) Sentence.known_mines returns no mines when no conclusion possible
:) Sentence.known_safes returns mines when conclusion possible
:) Sentence.known_safes returns no mines when no conclusion possible
:) Sentence.mark_mine marks mine when cell in sentence
:) Sentence.mark_mine does not mark mine when cell not in sentence
:) Sentence.mark_safe marks safe when cell in sentence
:) Sentence.mark_safe does not mark safe when cell not in sentence
:) MinesweeperAI.add_knowledge marks cell as a move made
:) MinesweeperAI.add_knowledge marks cell as safe
:) MinesweeperAI.add_knowledge adds sentence in middle of board
:) MinesweeperAI.add_knowledge adds sentence in corner of board
:) MinesweeperAI.add_knowledge ignores known mines when adding new sentence
:) MinesweeperAI.add_knowledge ignores known safes when adding new sentence
:) MinesweeperAI.add_knowledge infers additional safe cells
:) MinesweeperAI.add_knowledge can infer mine when given new information
:) MinesweeperAI.add_knowledge can infer multiple mines when given new information
:( MinesweeperAI.add_knowledge can infer safe cells when given new information
did not find (0, 0) in safe cells when possible to conclude safe
:) MinesweeperAI.add_knowledge combines multiple sentences to draw conclusions
Help!
I tried everything already, chat GPT did not help one bit, I tried pytest with test_minesweeper.py to unit test my code and it all seemed fine! In all situations I add to my knowledge the code seems to be working well.
You have multiple issues to address. I will start with the most basic ones. Review the code in the add_sentence() method where you remove empty sentences and find sentences with known mines and safes. You can test with this snippet. Run it and examine knowledge after each for loop to see the problems:
from minesweeper import Sentence
knowledge = []
safes = set()
mines = set()
s = Sentence(set(), 0)
knowledge.append(s)
s = Sentence(set(), 0)
knowledge.append(s)
s = Sentence(set([(1,1),(2,2),(3,3)]), 3)
knowledge.append(s)
s = Sentence(set([(0,0),(0,1),(0,2)]), 3)
knowledge.append(s)
s = Sentence(set([(1,0),(2,0),(3,0)]), 0)
knowledge.append(s)
s = Sentence(set([(2,1),(1,2),(1,3),(3,2)]), 0)
knowledge.append(s)
Tip for the mines/safes loop: You don't need continue statements if you use if/elif.
After you fix that segment, you have more things to fix. Suppose you have these 2 sentences in knowledge (in this order):
knowledge = []
s = Sentence(set([(0,0),(0,1),(1,0),(2,0)]), 2)
knowledge.append(s)
s = Sentence(set([(0,0),(0,1),(0,2)]), 3)
knowledge.append(s)
After you find mines in (0,0),(0,1),(0,2), you should discover the mines in (1,0),(2,0). However, you won't catch it with 1 call to add_sentence().
Finally, your last step (infer knowledge) needs work. I have a post in the CS50AI ED Forum that demonstrates this. Use this link: How to debug minesweeper