Scribd
Upload
6 views41 pages

Uninformed and Informed Search Methods

The document contains Python implementations of various uninformed and informed search algorithms, including Breadth First Search, Depth First Search, Depth Limited Search, Iterative Deepening Search, Best First Search, and Greedy Search. Each algorithm is encapsulated within a Graph class that manages nodes and edges, with methods for adding edges, finding neighbors, and executing the respective search algorithms. The document also includes examples of graph creation and search execution, demonstrating the functionality of each algorithm.

Uploaded by

gaikwadraj540
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views41 pages

Uninformed and Informed Search Methods

The document contains Python implementations of various uninformed and informed search algorithms, including Breadth First Search, Depth First Search, Depth Limited Search, Iterative Deepening Search, Best First Search, and Greedy Search. Each algorithm is encapsulated within a Graph class that manages nodes and edges, with methods for adding edges, finding neighbors, and executing the respective search algorithms. The document also includes examples of graph creation and search execution, demonstrating the functionality of each algorithm.

Uploaded by

gaikwadraj540
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

AIM :- Programs on uninformed search

methods
Breadth First Search

from collections import deque

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = set()

[Link](node2)

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, True)

def neighbors(self, node):

try: return [Link][node]

except KeyError: return []


def breadth_first_search(self, start, goal):

found, fringe, visited, came_from = False, deque([start]), set([start]),


{start: None}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', start))

while not found and len(fringe):

current = [Link]()

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

for node in [Link](current):

if node not in visited: [Link](node); [Link](node);


came_from[node] = current

print(', '.join(fringe))

if found: print(); return came_from

else: print('No path from {} to {}'.format(start, goal))

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')


def __str__(self):

return str([Link])

graph = Graph(directed=False)

graph.add_edge('A', 'B')

graph.add_edge('A', 'S')

graph.add_edge('S', 'G')

graph.add_edge('S', 'C')

graph.add_edge('C', 'F')

graph.add_edge('G', 'F')

graph.add_edge('C', 'D')

graph.add_edge('C', 'E')

graph.add_edge('E', 'H')

graph.add_edge('G', 'H')

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path,


goal);print()
Depth First Search

from collections import deque

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = set()

[Link](node2)

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, True)

def neighbors(self, node):

try: return [Link][node]

except KeyError: return []

def breadth_first_search(self, start, goal):


found, fringe, visited, came_from = False, deque([start]), set([start]),
{start: None}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', start))

while not found and len(fringe):

current = [Link]()

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

for node in [Link](current):

if node not in visited: [Link](node); [Link](node);


came_from[node] = current

print(', '.join(fringe))

if found: print(); return came_from

else: print('No path from {} to {}'.format(start, goal))

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')


def __str__(self):

return str([Link])

graph = Graph(directed=False)

graph.add_edge('A', 'B')

graph.add_edge('A', 'S')

graph.add_edge('S', 'G')

graph.add_edge('S', 'C')

graph.add_edge('C', 'F')

graph.add_edge('G', 'F')

graph.add_edge('C', 'D')

graph.add_edge('C', 'E')

graph.add_edge('E', 'H')

graph.add_edge('G', 'H')

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path,


goal);print()
Depth Limited Search

from collections import deque

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = set()

[Link](node2)

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, True)

def neighbors(self, node):

try: return [Link][node]

except KeyError: return []

def depth_limited_search(self, start, goal, limit=-1):

print('Depth limit =', limit)


found, fringe, visited, came_from = False, deque([(0, start)]), set([start]),
{start: None}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', start))

while not found and len(fringe):

depth, current = [Link]()

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

if limit == -1 or depth < limit:

for node in [Link](current):

if node not in visited:

[Link](node); [Link]((depth + 1, node))

came_from[node] = current

print(', '.join([n for _, n in fringe]))

if found: print(); return came_from

else: print('No path from {} to {}'.format(start, goal))

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return


print(' =>', goal, end='')

def __str__(self):

return str([Link])

graph = Graph(directed=False)

graph.add_edge('A', 'B')

graph.add_edge('A', 'S')

graph.add_edge('S', 'G')

graph.add_edge('S', 'C')

graph.add_edge('C', 'F')

graph.add_edge('G', 'F')

graph.add_edge('C', 'D')

graph.add_edge('C', 'E')

graph.add_edge('E', 'H')

graph.add_edge('G', 'H')

start, goal, l = 'A', 'H', 3

traced_path = graph.depth_limited_search(start, goal, l)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path,


goal);print()
Iterative Deepening Search

from collections import deque

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = set()

[Link](node2)

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, True)

def neighbors(self, node):

try: return [Link][node]

except KeyError: return []

def iterative_deepening_dfs(self, start, goal):

prev_iter_visited, depth = [], 0

while True:
traced_path, visited = self.depth_limited_search(start, goal, depth)

if traced_path or len(visited) == len(prev_iter_visited): return


traced_path

else: prev_iter_visited = visited; depth += 1

def depth_limited_search(self, start, goal, limit=-1):

print('Depth limit =', limit)

found, fringe, visited, came_from = False, deque([(0, start)]), set([start]),


{start: None}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', start))

while not found and len(fringe):

depth, current = [Link]()

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

if limit == -1 or depth < limit:

for node in [Link](current):

if node not in visited:

[Link](node); [Link]((depth + 1, node))

came_from[node] = current

print(', '.join([n for _, n in fringe]))

if found: print(); return came_from, visited

else: print('No path from {} to {}'.format(start, goal)); return None, visited


@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')

def __str__(self):

return str([Link])

graph = Graph(directed=False)

graph.add_edge('A', 'B')

graph.add_edge('A', 'S')

graph.add_edge('S', 'G')

graph.add_edge('S', 'C')

graph.add_edge('C', 'F')

graph.add_edge('G', 'F')

graph.add_edge('C', 'D')

graph.add_edge('C', 'E')

graph.add_edge('E', 'H')

graph.add_edge('G', 'H')
start, goal = 'A', 'H'

traced_path = graph.iterative_deepening_dfs(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path,


goal);print()
AIM :- Program on informed search
methods.

Best First Search

from queue import heappop, heappush

from math import inf

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, cost = 1, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = {}

neighbors[node2] = cost

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, cost,


True)
def set_huristics(self, huristics={}):

[Link] = huristics

def neighbors(self, node):

try: return [Link][node]

except KeyError: return []

def cost(self, node1, node2):

try: return [Link][node1][node2]

except: return inf

def best_first_search(self, start, goal):

found, fringe, visited, came_from, cost_so_far = False,


[([Link][start], start)], set([start]), {start: None}, {start: 0}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', str(fringe[0])))

while not found and len(fringe):

_, current = heappop(fringe)

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

for node in [Link](current):

new_cost = cost_so_far[current] + [Link](current, node)

if node not in visited or cost_so_far[node] > new_cost:


[Link](node); came_from[node] = current; cost_so_far[node] =
new_cost

heappush(fringe, (new_cost + [Link][node], node))

print(', '.join([str(n) for n in fringe]))

if found: print(); return came_from, cost_so_far[goal]

else: print('No path from {} to {}'.format(start, goal)); return None, inf

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')

def __str__(self):

return str([Link])

graph = Graph(directed=True)

graph.add_edge('A', 'B', 4)

graph.add_edge('A', 'C', 1)

graph.add_edge('B', 'D', 3)

graph.add_edge('B', 'E', 8)

graph.add_edge('C', 'C', 0)
graph.add_edge('C', 'D', 7)

graph.add_edge('C', 'F', 6)

graph.add_edge('D', 'C', 2)

graph.add_edge('D', 'E', 4)

graph.add_edge('E', 'G', 2)

graph.add_edge('F', 'G', 8)

graph.set_huristics({'A': 8, 'B': 8, 'C': 6, 'D': 5, 'E': 1, 'F': 4, 'G': 0})

start, goal = 'A', 'G'

traced_path, cost = graph.best_first_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path, goal);


print('\nCost:', cost)
Greedy Search

from queue import heappop, heappush

from math import inf

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, cost = 1, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = {}

neighbors[node2] = cost

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, cost,


True)

def set_huristics(self, huristics={}):

[Link] = huristics

def neighbors(self, node):


try: return [Link][node]

except KeyError: return []

def cost(self, node1, node2):

try: return [Link][node1][node2]

except: return inf

def greedy_search(self, start, goal):

found, fringe, visited, came_from, cost_so_far = False,


[([Link][start], start)], set([start]), {start: None}, {start: 0}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', str(fringe[0])))

while not found and len(fringe):

_, current = heappop(fringe)

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

for node in [Link](current):

new_cost = cost_so_far[current] + [Link](current, node)

if node not in visited or cost_so_far[node] > new_cost:

[Link](node); came_from[node] = current; cost_so_far[node] =


new_cost

heappush(fringe, ([Link][node], node))

print(', '.join([str(n) for n in fringe]))


if found: print(); return came_from, cost_so_far[goal]

else: print('No path from {} to {}'.format(start, goal)); return None, inf

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')

def __str__(self):

return str([Link])

graph = Graph(directed=True)

graph.add_edge('A', 'B', 4)

graph.add_edge('A', 'C', 1)

graph.add_edge('B', 'D', 3)

graph.add_edge('B', 'E', 8)

graph.add_edge('C', 'C', 0)

graph.add_edge('C', 'D', 7)

graph.add_edge('C', 'F', 6)

graph.add_edge('D', 'C', 2)
graph.add_edge('D', 'E', 4)

graph.add_edge('E', 'G', 2)

graph.add_edge('F', 'G', 8)

graph.set_huristics({'A': 8, 'B': 8, 'C': 6, 'D': 5, 'E': 1, 'F': 4, 'G': 0})

start, goal = 'A', 'G'

traced_path, cost = graph.greedy_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path, goal);


print('\nCost:', cost)
A* Search

from queue import heappop, heappush

from math import inf

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, cost = 1, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = {}

neighbors[node2] = cost

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, cost,


True)

def set_huristics(self, huristics={}):

[Link] = huristics

def neighbors(self, node):


try: return [Link][node]

except KeyError: return []

def cost(self, node1, node2):

try: return [Link][node1][node2]

except: return inf

def a_star_search(self, start, goal):

found, fringe, visited, came_from, cost_so_far = False,


[([Link][start], start)], set([start]), {start: None}, {start: 0}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', str(fringe[0])))

while not found and len(fringe):

_, current = heappop(fringe)

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

for node in [Link](current):

new_cost = cost_so_far[current] + [Link](current, node)

if node not in visited or cost_so_far[node] > new_cost:

[Link](node); came_from[node] = current; cost_so_far[node] =


new_cost

heappush(fringe, (new_cost + [Link][node], node))

print(', '.join([str(n) for n in fringe]))


if found: print(); return came_from, cost_so_far[goal]

else: print('No path from {} to {}'.format(start, goal)); return None, inf

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')

def __str__(self):

return str([Link])

graph = Graph(directed=True)

graph.add_edge('A', 'B', 4)

graph.add_edge('A', 'C', 1)

graph.add_edge('B', 'D', 3)

graph.add_edge('B', 'E', 8)

graph.add_edge('C', 'C', 0)

graph.add_edge('C', 'D', 7)

graph.add_edge('C', 'F', 6)

graph.add_edge('D', 'C', 2)
graph.add_edge('D', 'E', 4)

graph.add_edge('E', 'G', 2)

graph.add_edge('F', 'G', 8)

graph.set_huristics({'A': 8, 'B': 8, 'C': 6, 'D': 5, 'E': 1, 'F': 4, 'G': 0})

start, goal = 'A', 'G'

traced_path, cost = graph.a_star_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path, goal);


print('\nCost:', cost)
Iterative Deepening A* search
(memory bounded heuristic search)

from queue import heappop, heappush

from math import inf

class Graph:

def __init__(self, directed=True):

[Link] = {}

[Link] = {}

[Link] = directed

def add_edge(self, node1, node2, cost = 1, __reversed=False):

try: neighbors = [Link][node1]

except KeyError: neighbors = {}

neighbors[node2] = cost

[Link][node1] = neighbors

if not [Link] and not __reversed: self.add_edge(node2, node1, cost,


True)

def set_huristics(self, huristics={}):

[Link] = huristics
def neighbors(self, node):

try: return [Link][node]

except KeyError: return []

def cost(self, node1, node2):

try: return [Link][node1][node2]

except: return inf

def iterative_deepening_astar_search(self, start, goal):

prev_visited, depth = 0, 0

while True:

trace, cost, visited = self.dept_limited_astar_search(start, goal, depth)

if trace or visited == prev_visited: return trace, cost

prev_visited = visited

depth += 1

def dept_limited_astar_search(self, start, goal, limit=-1):

print('Depth Limit =', limit)

found, fringe, visited = False, [([Link][start], start, 0)], set([start])

came_from, cost_so_far = {start: None}, {start: 0}

print('{:11s} | {}'.format('Expand Node', 'Fringe'))

print('--------------------')

print('{:11s} | {}'.format('-', str(fringe[0][:-1])))


while not found and len(fringe):

_, current, depth = heappop(fringe)

print('{:11s}'.format(current), end=' | ')

if current == goal: found = True; break

if limit == -1 or depth < limit:

for node in [Link](current):

new_cost = cost_so_far[current] + [Link](current, node)

if node not in visited or cost_so_far[node] > new_cost:

[Link](node); came_from[node] = current;


cost_so_far[node] = new_cost

heappush(fringe, (new_cost + [Link][node], node, depth +


1))

print(', '.join([str(n[:-1]) for n in fringe]))

if found: print(); return came_from, cost_so_far[goal], len(visited)

else: print('No path from {} to {}'.format(start, goal)); return None, inf,


len(visited)

@staticmethod

def print_path(came_from, goal):

parent = came_from[goal]

if parent:

Graph.print_path(came_from, parent)

else: print(goal, end='');return

print(' =>', goal, end='')


def __str__(self):

return str([Link])

graph = Graph(directed=True)

graph.add_edge('A', 'B', 4)

graph.add_edge('A', 'C', 1)

graph.add_edge('B', 'D', 3)

graph.add_edge('B', 'E', 8)

graph.add_edge('C', 'C', 0)

graph.add_edge('C', 'D', 7)

graph.add_edge('C', 'F', 6)

graph.add_edge('D', 'C', 2)

graph.add_edge('D', 'E', 4)

graph.add_edge('E', 'G', 2)

graph.add_edge('F', 'G', 8)

graph.set_huristics({'A': 8, 'B': 8, 'C': 6, 'D': 5, 'E': 1, 'F': 4, 'G': 0})

start, goal, limit = 'A', 'G', 3

traced_path, cost = graph.iterative_deepening_astar_search(start, goal)

if (traced_path): print('Path:', end=' '); Graph.print_path(traced_path, goal);


print('\nCost:', cost)
AIM :- Program on Game playing algorithms.

TicTacToe Game

#Header Files

import cv2

import numpy as np

from random import randint

import time

#-----------------------------------------------------------------------------------

#Classes

class Block() :

def __init__(self,i,j) :

[Link] = None

[Link] = (i,j)

def setValue(self,value) :

[Link] = value

#-----------------------------------------------------------------------------------
class GUI() :

def __init__(self,windowName) :

[Link] = windowName

[Link],[Link] = 400,400

[Link] = 100

[Link] = [Link](([Link]+[Link],[Link],3),np.uint8)

[Link] = 1

[Link] = 0

[Link]()

#-----------------------------------------------------------------------------------

#Reset Game

def reset(self) :

[Link] = []

[Link] = False

[Link] = True

[Link] = False

for i in range(3) :

row = []

for j in range(3) :

[Link]([Block(i,j),(j*([Link]//3)+3,i*([Link]//3)+3),((j+1)*
([Link]//3)-3,(i+1)*([Link]//3)-3)])

[Link](row)

#-----------------------------------------------------------------------------------

#Drawing GUI and Game Screen


def draw(self) :

[Link] = [Link](([Link]+[Link],[Link],3),np.uint8)

for i in range(3) :

for j in range(3) :

start_point = [Link][i][j][1]

end_point = [Link][i][j][2]

[Link]([Link],start_point,end_point,(255,255,255),-1)

value = " " if [Link][i][j][0].value is None else


[Link][i][j][0].value

[Link]([Link],value,(j*([Link]//3)+25,(i*[Link]//3)+1
00),cv2.FONT_HERSHEY_SIMPLEX,5,(0,0,0),5)

if [Link]() :

string = ("Player "+str([Link])+" Wins" if [Link]!=[Link] else


"Computer Wins") if [Link]==1 else ("Player "+str(2)+" Win" if
[Link]!=[Link] else "Computer Win")

else :

if not [Link]() :

string = ("Player "+str([Link])+"'s Turn" if [Link]!=[Link] else


"Computer's Turn") if [Link]==1 else ("Player "+str(2)+"'s Turn" if
[Link]!=[Link] else "Computer's Turn")

else :

string = "Match Draw!!"

[Link]([Link],string,([Link]//2-
70,[Link]+30),cv2.FONT_HERSHEY_SIMPLEX,0.5,(255,255,255),1)

[Link]([Link],"R -
Reset",(10,[Link]+60),cv2.FONT_HERSHEY_SIMPLEX,0.5,(255,255,255),1)
[Link]([Link],"Esc -
Exit",(10,[Link]+80),cv2.FONT_HERSHEY_SIMPLEX,0.5,(255,255,255),1)

string = "vs Computer" if [Link]==0 else "vs Human"

[Link]([Link],"Space -
"+string,([Link]//2+10,[Link]+80),cv2.FONT_HERSHEY_SIMPLEX,0.5,(2
55,255,255),1)

if [Link] and not([Link]() or [Link]()):

[Link] = True

[Link] = False

[Link] *= -1

#-----------------------------------------------------------------------------------

#Game Play Functions

def mainLoop(self) : #Game Loop till Esc(Close) button is pressed

[Link]([Link])

[Link]([Link],[Link])

try:

while True and [Link]([Link],1) != -1 :

if [Link] :

[Link]=False

[Link]()

if [Link] == [Link] and not([Link]() or


[Link]()):

block = [Link]()
[Link]("x" if [Link]==1 else "o")

[Link] = True

[Link] = True

[Link]([Link],[Link])

#Keyboard Hits

key = [Link](1)

if key == 27 : break

elif key == ord("r") or key == ord("R") :

[Link]()

if key == ord(" ") and not([Link]() or [Link]()):

if [Link] :

[Link] = 0

else :

[Link] = [Link]

[Link] = True

[Link]()

except:

print("Window is successfully closed")

def checkWin(self) :
[Link] = False

if ([Link][0][0][0].value is not None and


[Link][0][0][0].value==[Link][0][1][0].value==[Link][0][2][0].value
)or([Link][1][0][0].value is not None and
[Link][1][0][0].value==[Link][1][1][0].value==[Link][1][2][0].value
)or([Link][2][0][0].value is not None and
[Link][2][0][0].value==[Link][2][1][0].value==[Link][2][2][0].value
)or([Link][0][0][0].value is not None and
[Link][0][0][0].value==[Link][1][0][0].value==[Link][2][0][0].value
)or([Link][0][1][0].value is not None and
[Link][0][1][0].value==[Link][1][1][0].value==[Link][2][1][0].value
)or([Link][0][2][0].value is not None and
[Link][0][2][0].value==[Link][1][2][0].value==[Link][2][2][0].value
)or([Link][0][0][0].value is not None and
[Link][0][0][0].value==[Link][1][1][0].value==[Link][2][2][0].value
)or([Link][2][0][0].value is not None and
[Link][2][0][0].value==[Link][0][2][0].value==[Link][1][1][0].value
):

[Link] = True

return [Link]

def checkDraw(self) :

flag = True

for i in range(3) :

for j in range(3) :

if [Link][i][j][0].value == None :

flag=False

return flag

#-----------------------------------------------------------------------------------
#Computers Move Decided Using Minmax Algorithm

def nextMove(self) : #Decide NextMove of Computer by this return the


block to selected by the Computer

flag=0

blocks = []

for i in range(3) :

for j in range(3) :

if [Link][i][j][0].value == None :

[Link]([Link][i][j][0])

if not (len(blocks)==sum([len(row) for row in [Link]]) or


len(blocks)==sum([len(row) for row in [Link]])-1 or len(blocks)==1) :

scoresList={}

for block in blocks :

if [Link] == None :

if [Link](block) :

scoresList[block] = 50

elif [Link](block) :

scoresList[block] = -50

elif not [Link]() :

[Link] = ("x" if [Link] == 1 else "o")

scoresList[block] = self.min_max(1,[Link])

[Link] = None

else :

scoresList[block] = 0
#Choosing Either Best Closest Winning Score or Next Closest Losing
Score

bestScore = (min([Link]()) if
abs(min([Link]()))>abs(max([Link]())) else
max([Link]()))

blocks = []

for block in scoresList :

if scoresList[block] == bestScore :

##print([Link],bestScore)

[Link](block)

choice = blocks[randint(0,len(blocks)-1)]

#print([Link])

return choice

def min_max(self,depth,player) : #MinMax Algorithms Function

scoresList = []

for row in [Link] :

for block in row :

if block[0].value == None :

if [Link](block[0]) :

return (50-depth)

elif [Link](block[0]) :

return (-50+depth)

else :
block[0].value = ("x" if [Link] == 1 else "o")

[Link](self.min_max(depth+1,player*-1))

block[0].value = None

if scoresList:

return (min(scoresList) if abs(min(scoresList))>abs(max(scoresList)) else


max(scoresList))

return 0

def computerWins(self,block) :

flag = False

[Link] = ("x" if [Link] == 1 else "o")

if [Link]() : flag = True

[Link] = False

[Link] = None

return flag

def playerWins(self,block) :

flag = False

[Link] = ("x" if [Link] != 1 else "o")

if [Link]() : flag = True

[Link] = False

[Link] = None

return flag

#-----------------------------------------------------------------------------------
#Mouse Click Functions - (For User Players)

def mouseCall(self,event,posx,posy,flag,param) :

if event == cv2.EVENT_LBUTTONDOWN and not [Link] and


[Link]!=[Link]:

[Link](posx,posy)

def setBlockInPos(self,x,y) :

for i in range(3) :

for j in range(3) :

if [Link][i][j][0].value is None and


[Link][i][j][1][0]<=x<=[Link][i][j][2][0] and [Link][i][j][1][1]<= y<=
[Link][i][j][2][1]:

[Link][i][j][0].setValue("x" if [Link] == 1 else "o")

[Link] = True

[Link] = True

break

#-----------------------------------------------------------------------------------

#Main Program

game = GUI("TicTacToe")

[Link]()

You might also like