Subscribe to DSC Newsletter

Solving a few AI problems with Python: Part 1

In this blog we shall discuss about a few problems in artificial intelligence and their python implementations. The problems discussed here appeared as programming assignments in the edX course CS50’s Introduction to Artificial Intelligence with Python (HarvardX:CS50 AI). The problem statements are taken from the course itself.

Degrees

Write a program that determines how many “degrees of separation” apart two actors are.

Image for posthttps://miro.medium.com/max/690/1*KoCfC9QZ_QjTVHjzFJEdBA.png 552w, https://miro.medium.com/max/800/1*KoCfC9QZ_QjTVHjzFJEdBA.png 640w, https://miro.medium.com/max/870/1*KoCfC9QZ_QjTVHjzFJEdBA.png 696w" sizes="696px" />

Image created by Author from the csv files provided here

  • In the csv file for the movies, each movie also has a unique id, in addition to a title and the year in which the movie was released.
  • The csv file for the stars establishes a relationship between the people and the movies from the corresponding files. Each row is a pair of a person_id value and movie_id value.
  • Given two actors nodes in the graph we need to find the distance (shortest path) between the nodes. We shall use BFS to find the distance or the degree of separation. The next figure shows the basic concepts required to define a search problem in AI.
Image for posthttps://miro.medium.com/max/690/1*5ol7zprtW7cQca2zUG4hDA.png 552w, https://miro.medium.com/max/800/1*5ol7zprtW7cQca2zUG4hDA.png 640w, https://miro.medium.com/max/875/1*5ol7zprtW7cQca2zUG4hDA.png 700w" sizes="700px" />
Image created from the lecture notes from this course

def shortest_path(source, target):
"""
Returns the shortest list of (movie_id, person_id) pairs
that connect the source to the target.
If no possible path, returns None.
"""

explored = set([])
frontier = [source]
parents = {}
while len(frontier) > 0:
person = frontier.pop(0)
if person == target:
break
explored.add(person)
for (m, p) in neighbors_for_person(person):
if not p in frontier and not p in explored:
frontier.append(p)
parents[p] = (m, person)
if not target in parents:
return None
path = []
person = target
while person != source:
m, p = parents[person]
path.append((m, person))
person = p
path = path[::-1]
return path

Image for posthttps://miro.medium.com/max/690/0*NlISzC4qgKOMXyg6.gif 552w, https://miro.medium.com/max/800/0*NlISzC4qgKOMXyg6.gif 640w, https://miro.medium.com/max/875/0*NlISzC4qgKOMXyg6.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*cBbphXn5Dlmf4-q_memrJw.png 552w, https://miro.medium.com/max/800/1*cBbphXn5Dlmf4-q_memrJw.png 640w" sizes="640px" />

Image by Author

Tic-Tac-Toe

Using Minimax, implement an AI to play Tic-Tac-Toe optimally.

  • Implement a player function that should take a board state as input, and return which player’s turn it is (either X or O).
  • In the initial game state, X gets the first move. Subsequently, the player alternates with each additional move.
  • Any return value is acceptable if a terminal board is provided as input (i.e., the game is already over).
  • Implement an action function that should return a set of all of the possible actions that can be taken on a given board.
  • Each action should be represented as a tuple (i, j) where i corresponds to the row of the move (0, 1, or 2) and j corresponds to which cell in the row corresponds to the move (also 0, 1, or 2).
  • Possible moves are any cells on the board that do not already have an X or an O in them.
  • Any return value is acceptable if a terminal board is provided as input.
  • Implement a result function that takes a board and an action as input, and should return a new board state, without modifying the original board.
  • If action is not a valid action for the board, your program should raise an exception.
  • The returned board state should be the board that would result from taking the original input board, and letting the player whose turn it is make their move at the cell indicated by the input action.
  • Importantly, the original board should be left unmodified: since Minimax will ultimately require considering many different board states during its computation. This means that simply updating a cell in board itself is not a correct implementation of the result function. You’ll likely want to make a deep copy of the board first before making any changes.
  • Implement a winner function that should accept a board as input, and return the winner of the board if there is one.
  • If the X player has won the game, your function should return X. If the O player has won the game, your function should return O.
  • One can win the game with three of their moves in a row horizontally, vertically, or diagonally.
  • You may assume that there will be at most one winner (that is, no board will ever have both players with three-in-a-row, since that would be an invalid board state).
  • If there is no winner of the game (either because the game is in progress, or because it ended in a tie), the function should return None.
  • Implement a terminal function that should accept a board as input, and return a boolean value indicating whether the game is over.
  • If the game is over, either because someone has won the game or because all cells have been filled without anyone winning, the function should return True.
  • Otherwise, the function should return False if the game is still in progress.
  • Implement an utility function that should accept a terminal board as input and output the utility of the board.
  • If X has won the game, the utility is 1. If O has won the game, the utility is -1. If the game has ended in a tie, the utility is 0.
  • You may assume utility will only be called on a board if terminal(board) is True.
  • Implement a minimax function that should take a board as input, and return the optimal move for the player to move on that board.
  • The move returned should be the optimal action (i, j) that is one of the allowable actions on the board. If multiple moves are equally optimal, any of those moves is acceptable.
  • If the board is a terminal board, the minimax function should return None.
  • For all functions that accept a board as input, you may assume that it is a valid board (namely, that it is a list that contains three rows, each with three values of either X, O, or EMPTY).
  • Since Tic-Tac-Toe is a tie given optimal play by both sides, you should never be able to beat the AI (though if you don’t play optimally as well, it may beat you!)
  • The following figure demonstrates the basic concepts of adversarial search and Game and defines the different functions for tic-tac-toe.
  • Here we shall use Minimax with alpha-beta pruning to speedup the game when it is computer’s turn.

Image for posthttps://miro.medium.com/max/690/1*UdflQeTyI19HT5KT7ycM_w.png 552w, https://miro.medium.com/max/800/1*UdflQeTyI19HT5KT7ycM_w.png 640w, https://miro.medium.com/max/875/1*UdflQeTyI19HT5KT7ycM_w.png 700w" sizes="700px" />

Image created from the lecture notes from this course

def max_value_alpha_beta(board, alpha, beta):
if terminal(board):
return utility(board), None
v, a = -np.inf, None
for action in actions(board):
m, _ = min_value_alpha_beta(result(board, action),
alpha, beta)
if m > v:
v, a = m, action
alpha = max(alpha, v)
if alpha >= beta:
break
return (v, a)

def min_value_alpha_beta(board, alpha, beta):
if terminal(board):
return utility(board), None
v, a = np.inf, None
for action in actions(board):
m, _ = max_value_alpha_beta(result(board, action),
alpha, beta)
if m < v:
v, a = m, action
beta = min(beta, v)
if alpha >= beta:
break
return (v, a)

def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
if terminal(board):
return None
cur_player = player(board)
if cur_player == X:
_, a = max_value_alpha_beta(board, -np.inf, np.inf)
elif cur_player == O:
_, a = min_value_alpha_beta(board, -np.inf, np.inf)
return a

Image for posthttps://miro.medium.com/max/690/1*Sl9PbYu4IlVaq-o_tL4Bkw.png 552w, https://miro.medium.com/max/800/1*Sl9PbYu4IlVaq-o_tL4Bkw.png 640w, https://miro.medium.com/max/875/1*Sl9PbYu4IlVaq-o_tL4Bkw.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*qNhjGy61bHA_UFb8.gif 552w, https://miro.medium.com/max/800/0*qNhjGy61bHA_UFb8.gif 640w, https://miro.medium.com/max/875/0*qNhjGy61bHA_UFb8.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*OaixCe0yfd5a_QlNrZ4Riw.gif 552w, https://miro.medium.com/max/800/1*OaixCe0yfd5a_QlNrZ4Riw.gif 640w, https://miro.medium.com/max/875/1*OaixCe0yfd5a_QlNrZ4Riw.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*qBDJqCZSA6DVaV40hyMwRg.png 552w, https://miro.medium.com/max/800/1*qBDJqCZSA6DVaV40hyMwRg.png 640w, https://miro.medium.com/max/875/1*qBDJqCZSA6DVaV40hyMwRg.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*TY2B7jAbANY8vjrOeFEQ_A.png 552w, https://miro.medium.com/max/800/1*TY2B7jAbANY8vjrOeFEQ_A.png 640w, https://miro.medium.com/max/875/1*TY2B7jAbANY8vjrOeFEQ_A.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*4IcjyIVv4LsEMtXl.gif 552w, https://miro.medium.com/max/800/0*4IcjyIVv4LsEMtXl.gif 640w, https://miro.medium.com/max/875/0*4IcjyIVv4LsEMtXl.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*3BDLfcpmuD1YGxb5m1o1kA.png 552w, https://miro.medium.com/max/800/1*3BDLfcpmuD1YGxb5m1o1kA.png 640w, https://miro.medium.com/max/875/1*3BDLfcpmuD1YGxb5m1o1kA.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*EQf5eNuBIkuFN4jz-eiNnw.png 552w, https://miro.medium.com/max/800/1*EQf5eNuBIkuFN4jz-eiNnw.png 640w, https://miro.medium.com/max/875/1*EQf5eNuBIkuFN4jz-eiNnw.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*ZS4kSWQ1iTWGkMWv.gif 552w, https://miro.medium.com/max/800/0*ZS4kSWQ1iTWGkMWv.gif 640w, https://miro.medium.com/max/875/0*ZS4kSWQ1iTWGkMWv.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*f4Zhv-l7jKrvi3a8na4eUw.png 552w, https://miro.medium.com/max/800/1*f4Zhv-l7jKrvi3a8na4eUw.png 640w, https://miro.medium.com/max/875/1*f4Zhv-l7jKrvi3a8na4eUw.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*cUKFr2gggXyw6n9D7qQLhw.png 552w, https://miro.medium.com/max/800/1*cUKFr2gggXyw6n9D7qQLhw.png 640w, https://miro.medium.com/max/875/1*cUKFr2gggXyw6n9D7qQLhw.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*kM3ggKU5-6uvF-LH.gif 552w, https://miro.medium.com/max/800/0*kM3ggKU5-6uvF-LH.gif 640w, https://miro.medium.com/max/875/0*kM3ggKU5-6uvF-LH.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*iCTBE2ENuXJwcutV.gif 552w, https://miro.medium.com/max/800/0*iCTBE2ENuXJwcutV.gif 640w, https://miro.medium.com/max/875/0*iCTBE2ENuXJwcutV.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*Co6oPEeiIax7A222.gif 552w, https://miro.medium.com/max/800/0*Co6oPEeiIax7A222.gif 640w, https://miro.medium.com/max/875/0*Co6oPEeiIax7A222.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*hWJ0y25qGQUOuNqb.gif 552w, https://miro.medium.com/max/800/0*hWJ0y25qGQUOuNqb.gif 640w, https://miro.medium.com/max/875/0*hWJ0y25qGQUOuNqb.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*nZtdNRb8D0B-30K-0D_16A.png 552w, https://miro.medium.com/max/800/1*nZtdNRb8D0B-30K-0D_16A.png 640w, https://miro.medium.com/max/875/1*nZtdNRb8D0B-30K-0D_16A.png 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*-bUwZ11liYB-Aimtz5d2eQ.jpeg 552w, https://miro.medium.com/max/800/1*-bUwZ11liYB-Aimtz5d2eQ.jpeg 640w, https://miro.medium.com/max/875/1*-bUwZ11liYB-Aimtz5d2eQ.jpeg 700w" sizes="700px" />

Image by Author

Knights

Write a program to solve logic puzzles.

  • A knight will always tell the truth: if knight states a sentence, then that sentence is true.
  • Conversely, a knave will always lie: if a knave states a sentence, then that sentence is false.
  • The objective of the puzzle is, given a set of sentences spoken by each of the characters, determine, for each character, whether that character is a knight or a knave.
  1. Has two characters: A and B.
    - A says “We are both knaves.”
    - B says nothing.
  2. Has two characters: A and B.
    - A says “We are the same kind.”
    - B says “We are of different kinds.”
  3. Has three characters: A, B, and C.
    - A says either “I am a knight.” or “I am a knave.”, but you don’t know which.
    - B says “A said ‘I am a knave.’”
    - B then says “C is a knave.”
    - C says “A is a knight.”

Image for posthttps://miro.medium.com/max/690/1*5gEaaFniCxUqq1Xmzm1QOQ.png 552w, https://miro.medium.com/max/800/1*5gEaaFniCxUqq1Xmzm1QOQ.png 640w, https://miro.medium.com/max/875/1*5gEaaFniCxUqq1Xmzm1QOQ.png 700w" sizes="700px" />

Image created from the lecture notes from this course

import itertoolsclass Sentence():    def evaluate(self, model):
"""Evaluates the logical sentence."""
raise Exception("nothing to evaluate")
def formula(self):
"""Returns string formula representing logical sentence."""
return ""
def symbols(self):
"""Returns a set of all symbols in the logical sentence."""
return set()
@classmethod
def validate(cls, sentence):
if not isinstance(sentence, Sentence):
raise TypeError("must be a logical sentence")
class And(Sentence):
def __init__(self, *conjuncts):
for conjunct in conjuncts:
Sentence.validate(conjunct)
self.conjuncts = list(conjuncts)
def __eq__(self, other):
return isinstance(other, And) and \
self.conjuncts == other.conjuncts
def __hash__(self):
return hash(
("and", tuple(hash(conjunct) for conjunct in
self.conjuncts))
)
def __repr__(self):
conjunctions = ", ".join(
[str(conjunct) for conjunct in self.conjuncts]
)
return f"And({conjunctions})"
def add(self, conjunct):
Sentence.validate(conjunct)
self.conjuncts.append(conjunct)
def evaluate(self, model):
return all(conjunct.evaluate(model) for conjunct in
self.conjuncts)
def formula(self):
if len(self.conjuncts) == 1:
return self.conjuncts[0].formula()
return " ∧ ".join([Sentence.parenthesize(conjunct.formula())
for conjunct in self.conjuncts])
def symbols(self):
return set.union(*[conjunct.symbols() \
for conjunct in self.conjuncts])
AKnight = Symbol("A is a Knight")
AKnave = Symbol("A is a Knave")
BKnight = Symbol("B is a Knight")
BKnave = Symbol("B is a Knave")
CKnight = Symbol("C is a Knight")
CKnave = Symbol("C is a Knave")
# Puzzle 1
# A says "I am both a knight and a knave."
knowledge1 = And(
Or(And(AKnight, Not(AKnave)), And(Not(AKnight), AKnave)),
Implication(AKnight, And(AKnight, AKnave)),
Implication(AKnave, Not(And(AKnight, AKnave)))
)

Image for posthttps://miro.medium.com/max/690/1*xxNrl1W9GTNT-4rWOwhhoQ.jpeg 552w, https://miro.medium.com/max/800/1*xxNrl1W9GTNT-4rWOwhhoQ.jpeg 640w, https://miro.medium.com/max/875/1*xxNrl1W9GTNT-4rWOwhhoQ.jpeg 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*L9DS8SKHc49nGD6p.gif 552w, https://miro.medium.com/max/800/0*L9DS8SKHc49nGD6p.gif 640w, https://miro.medium.com/max/875/0*L9DS8SKHc49nGD6p.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*R-3Youq8dgOWSfF24yDmtA.jpeg 552w, https://miro.medium.com/max/800/1*R-3Youq8dgOWSfF24yDmtA.jpeg 640w, https://miro.medium.com/max/875/1*R-3Youq8dgOWSfF24yDmtA.jpeg 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*AgN5XIJ9keDuQemo.gif 552w, https://miro.medium.com/max/800/0*AgN5XIJ9keDuQemo.gif 640w, https://miro.medium.com/max/875/0*AgN5XIJ9keDuQemo.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*qfZVNMaDclUiys45AKFGIQ.jpeg 552w, https://miro.medium.com/max/800/1*qfZVNMaDclUiys45AKFGIQ.jpeg 640w, https://miro.medium.com/max/875/1*qfZVNMaDclUiys45AKFGIQ.jpeg 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*lC-b57RB2GcnL3kV.gif 552w, https://miro.medium.com/max/800/0*lC-b57RB2GcnL3kV.gif 640w, https://miro.medium.com/max/875/0*lC-b57RB2GcnL3kV.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/1*RPFXmQjTaoPYHRyohzR3UA.jpeg 552w, https://miro.medium.com/max/800/1*RPFXmQjTaoPYHRyohzR3UA.jpeg 640w, https://miro.medium.com/max/875/1*RPFXmQjTaoPYHRyohzR3UA.jpeg 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*wIDhikqpQ3jstSOU.gif 552w, https://miro.medium.com/max/800/0*wIDhikqpQ3jstSOU.gif 640w, https://miro.medium.com/max/875/0*wIDhikqpQ3jstSOU.gif 700w" sizes="700px" />

Image by Author

Minesweeper

Write an AI agent to play Minesweeper.

Image for post
https://miro.medium.com/max/373/0*OL5UlEAk2F9sToVZ.png 298w" sizes="298px" />

Image taken from here

  • Clicking on a cell that contains a mine detonates the mine, and causes the user to lose the game.
  • Clicking on a “safe” cell (i.e., a cell that does not contain a mine) reveals a number that indicates how many neighboring cells — where a neighbor is a cell that is one square to the left, right, up, down, or diagonal from the given cell — contain a mine.
  • The following figure shows an example Minesweeper game. In this 3 X 3 Minesweeper game, for example, the three 1 values indicate that each of those cells has one neighboring cell that is a mine. The four 0 values indicate that each of those cells has no neighboring mine.

Image for posthttps://miro.medium.com/max/375/0*vW98E5LIWtVokhFj.png 300w" sizes="300px" />

Image taken from here

  • The goal of the game is to flag (i.e., identify) each of the mines.
  • In many implementations of the game, the player can flag a mine by right-clicking on a cell (or two-finger clicking, depending on the computer).
  • One way we could represent an AI’s knowledge about a Minesweeper game is by making each cell a propositional variable that is true if the cell contains a mine, and false otherwise.
  • What information does the AI agent have access to? Well, the AI would know every time a safe cell is clicked on and would get to see the number for that cell.
  • Consider the following Minesweeper board, where the middle cell has been revealed, and the other cells have been labeled with an identifying letter for the sake of discussion.

Image for post
https://miro.medium.com/max/375/0*M7LH0dvaoUji10H9.png 300w" sizes="300px" />

Image taken from here

  • But we actually know more than what this expression says. The above logical sentence expresses the idea that at least one of those eight variables is true. But we can make a stronger statement than that: we know that exactly one of the eight variables is true. This gives us a propositional logic sentence like the below.
Or(
And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),
And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),
And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),
And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),
And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),
And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H)
)
  • Trying to perform model checking on this type of problem, too, would quickly become intractable: on an 8 X 8 grid, the size Microsoft uses for its Beginner level, we’d have 64 variables, and therefore 2⁶⁴ possible models to check — far too many for a computer to compute in any reasonable amount of time. We need a better representation of knowledge for this problem.
  • Every logical sentence in this representation has two parts: a set of cells on the board that are involved in the sentence, and a number count , representing the count of how many of those cells are mines. The above logical sentence says that out of cells A, B, C, D, E, F, G, and H, exactly 1 of them is a mine.
  • Why is this a useful representation? In part, it lends itself well to certain types of inference. Consider the game below:

Image for posthttps://miro.medium.com/max/356/0*boeBD-_TksR8jDNj.png 285w" sizes="285px" />

Image taken from here

  • Intuitively, we can infer from that sentence that all of the cells must be safe. By extension, any time we have a sentence whose count is 0 , we know that all of that sentence’s cells must be safe.
  • Similarly, consider the game below.

Image for posthttps://miro.medium.com/max/365/0*fNpA9Phrec-SPteN.png 292w" sizes="292px" />

Image taken from here

  • More generally, any time the number of cells is equal to the count , we know that all of that sentence’s cells must be mines.
  • In general, we’ll only want our sentences to be about cells that are not yet known to be either safe or mines. This means that, once we know whether a cell is a mine or not, we can update our sentences to simplify them and potentially draw new conclusions.
  • For example, if our AI agent knew the sentence {A, B, C} = 2 , we don’t yet have enough information to conclude anything. But if we were told that C were safe, we could remove C from the sentence altogether, leaving us with the sentence {A, B} = 2 (which, incidentally, does let us draw some new conclusions.)
  • Likewise, if our AI agent knew the sentence {A, B, C} = 2 , and we were told that C is a mine, we could remove C from the sentence and decrease the value of count (since C was a mine that contributed to that count), giving us the sentence {A, B} = 1 . This is logical: if two out of A, B, and C are mines, and we know that C is a mine, then it must be the case that out of A and B, exactly one of them is a mine.
  • If we’re being even more clever, there’s one final type of inference we can do

Image for posthttps://miro.medium.com/max/354/0*7ScdGG3nIwxXwzhd.png 283w" sizes="283px" />

Image taken from here

  • More generally, any time we have two sentences set1 = count1 and set2 = count2 where set1 is a subset of set2 , then we can construct the new sentence set2 — set1 = count2 — count1 . Consider the example above to ensure you understand why that’s true.
  • So using this method of representing knowledge, we can write an AI agent that can gather knowledge about the Minesweeper board, and hopefully select cells it knows to be safe!
  • The following figure shows examples of inference rules and resolution by inference relevant for this problem:

Image for posthttps://miro.medium.com/max/690/1*X1Wn4ufBJtL2uNW0teX7zg.png 552w, https://miro.medium.com/max/800/1*X1Wn4ufBJtL2uNW0teX7zg.png 640w, https://miro.medium.com/max/851/1*X1Wn4ufBJtL2uNW0teX7zg.png 681w" sizes="681px" />

Image created from the lecture notes from this course

  • Each sentence has a set of cells within it and a count of how many of those cells are mines.
  • Let the class also contain functions known_mines and known_safes for determining if any of the cells in the sentence are known to be mines or known to be safe.
  • It should also have member functions mark_mine() and mark_safe() to update a sentence in response to new information about a cell.
  • Each cell is a pair (i, j) where i is the row number (ranging from 0 to height — 1 ) and j is the column number (ranging from 0 to width — 1 ).
  • Implement a known_mines() method that should return a set of all of the cells in self.cells that are known to be mines.
  • Implement a known_safes() method that should return a set of all the cells in self.cells that are known to be safe.
  • Implement a mark_mine() method that should first check if cell is one of the cells included in the sentence. If cell is in the sentence, the function should update the sentence so that cell is no longer in the sentence, but still represents a logically correct sentence given that cell is known to be a mine.
  • Likewise mark_safe() method should first check if cell is one of the cells included in the sentence. If yes, then it should update the sentence so that cell is no longer in the sentence, but still represents a logically correct sentence given that cell is known to be safe.
  • Implement a method add_knowledge() that should accept a cell and
  • The function should mark the cell as one of the moves made in the game.
  • The function should mark the cell as a safe cell, updating any sentences that contain the cell as well.
  • The function should add a new sentence to the AI’s knowledge base, based on the value of cell and count , to indicate that count of the cell ’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 , then those sentences should be added to the knowledge base as well.
  • Implement a method make_safe_move() that should return a move (i, j) that is known to be safe.
  • The move returned must be known to be safe, and not a move already made.
  • If no safe move can be guaranteed, the function should return None .
  • Implement a method make_random_move() that should return a random move (i, j) .
  • This function will be called if a safe move is not possible: if the AI agent doesn’t know where to move, it will choose to move randomly instead.
  • The move must not be a move that has already been made.
  • he move must not be a move that is known to be a mine.
  • If no such moves are possible, the function should return None .
class MinesweeperAI():
"""
Minesweeper game player
"""
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)
# ensure that no duplicate sentences are added
def knowledge_contains(self, sentence):
for s in self.knowledge:
if s == sentence:
return True
return False
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 KB
5) add any new sentences to the AI's knowledge base
if they can be inferred from existing knowledge
"""
# mark the cell as a move that has been made
self.moves_made.add(cell)
# mark the cell as safe
self.mark_safe(cell)
# add a new sentence to the AI's knowledge base,
# based on the value of `cell` and `count
i, j = cell
cells = []
for row in range(max(i-1,0), min(i+2,self.height)):
for col in range(max(j-1,0), min(j+2,self.width)):
# if some mines in the neighbors are already known,
# make sure to decrement the count
if (row, col) in self.mines:
count -= 1
if (not (row, col) in self.safes) and \
(not (row, col) in self.mines):
cells.append((row, col))
sentence = Sentence(cells, count)
# add few more inference rules here

def make_safe_move(self):
"""
Returns a safe cell to choose on the Minesweeper board.
The move must be known to be safe, and not already a move
that has been made.
This function may use the knowledge in self.mines,
self.safes and self.moves_made, but should not modify any of
those values.
"""
safe_moves = self.safes - self.moves_made
if len(safe_moves) > 0:
return safe_moves.pop()
else:
return None

Image for posthttps://miro.medium.com/max/690/0*Z5EHTjqn0JM8m34R.gif 552w, https://miro.medium.com/max/800/0*Z5EHTjqn0JM8m34R.gif 640w, https://miro.medium.com/max/875/0*Z5EHTjqn0JM8m34R.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*rkI9JOXHYIzsrxAC.gif 552w, https://miro.medium.com/max/800/0*rkI9JOXHYIzsrxAC.gif 640w, https://miro.medium.com/max/875/0*rkI9JOXHYIzsrxAC.gif 700w" sizes="700px" />

Image by Author

Image for posthttps://miro.medium.com/max/690/0*566rbRuqvTmd6HEc.gif 552w, https://miro.medium.com/max/800/0*566rbRuqvTmd6HEc.gif 640w, https://miro.medium.com/max/875/0*566rbRuqvTmd6HEc.gif 700w" sizes="700px" />

Image by Author

Artificial Intelligence is a vast area of research and it contains many different sub-areas those themselves are huge. In this blog, we discussed some problems from Search and  Knowledge (Logic) aspects of AI. We discussed how to implement AI agents for an adversarial search game (tic-tac-toe) and a logic-based game (minesweeper). In the next part of this blog we shall discuss on some more problems on AI from a few more areas of AI research.

Views: 794

Comment

You need to be a member of Data Science Central to add comments!

Join Data Science Central

© 2021   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service