<jupyter_start><jupyter_text>Lab Assignment - 04 Problem - Implementation of MINIMAX and Alpha-beta pruning algorithm for Noughts and Crosses, and display the game tree<jupyter_code>import numpy as np
import time

class Node():
    def __init__(self,state,depth,maximiser,player,parent=None,):
        self.state=state
        self.children=list()
        self.score=0
        self.depth=depth
        self.maximiser=maximiser
        self.player=player
        self.best_child=None

        if parent is not None:
            parent.children.append(self)
# environment of the search agent
class environment():
    def __init__(self,start_state=None):
        if start_state is None:
            self.start_state=np.array([['.','.','.'],['.','.','.'],['.','.','.']])
        else:
            self.start_state=start_state


    # for returning all possibles moves for a given configuration
    def get_moves(self,state,player):
        new_states=[]
        spaces=[]
        for i in range(3):
            for j in range(3):
                if state[i,j]=='.':
                    new_state=state.copy()
                    new_state[i,j]=player #for filling the player choice
                    new_states.append(new_state)
        return new_states

    # check all space filled or not
    def checking(self,state):
        for i in range(3):
            for j in range(3):
                if state[i,j]=='.':
                    return False
        return True

    # for evaluation returns the value for every state
    # +1 for win -1 for lose and 0 for draw
    def evaluation(self,state):
        for i in range(3):
            # check for row wise
            if state[i,0]==state[i,1]==state[i,2]!='.':
                if state[i][0]=='x':
                    return 1
                else:
                    return -1
            # check for column wise
            if state[0,i]==state[1,i]==state[2,i]!='.':
                if state[0,i]=='x':
                    return 1
                else:
                    return -1
        # for diagonally checking
        if state[0,0]==state[1,1]==state[2,2]!='.':
            if state[0][0]=='x':
                return 1
            else:
                return -1
        if state[0,2]==state[1,1]==state[2,0]!='.':
            if state[0,2]=='x':
                return 1
            else:
                return -1
        return 0
    def get_start_state(self):
        return self.start_state

class Agent():
    def __init__(self,env,maximiser):
        self.env=env
        self.start_state=env.get_start_state()
        self.root_node=None
        self.neginf=-10**18
        self.posinf=10**18
        self.maximiser=maximiser
        self.player='x' if maximiser else 'o';
        self.explored_nodes=0

    def minimax(self, node):

        self.explored_nodes += 1
        score = self.env.evaluation(node.state)
        if score != 0:
            node.score = score
            return node

        if self.env.checking(node.state):
            node.score = 0
            return node

        if node.maximiser:

            best_score = self.neginf
            best_depth = self.posinf
            next_moves = self.env.get_moves(node.state, node.player)
            for move in next_moves:
                child = Node(state=move, depth=node.depth + 1,
                             maximiser=not node.maximiser, player='o', parent=node)

                child = self.minimax(child)
                node.children.append(child)

                if best_score < child.score or (best_score == child.score and child.depth < best_depth):
                    best_score = child.score
                    best_depth = child.depth
                    node.best_child = child

            node.depth = best_depth
            node.score = best_score

            return node

        else:
            best_score = self.posinf
            best_depth = self.posinf
            next_moves = self.env.get_moves(node.state, node.player)

            for move in next_moves:
                child = Node(state=move, depth=node.depth + 1,
                             maximiser=not node.maximiser, player='x', parent=node)

                child = self.minimax(child)
                node.children.append(child)

                if best_score > child.score or (best_score == child.score and child.depth < best_depth):
                    best_score = child.score
                    best_depth = child.depth
                    node.best_child = child

            node.depth = best_depth
            node.score = best_score

            return node

    def run(self):

        self.root_node=Node(state=self.start_state,depth=0,
                            maximiser=self.maximiser,player=self.player,parent=None)
        self.root_node=self.minimax(node=self.root_node)

    def print_nodes(self):

        node = self.root_node

        while node is not None:
            print(node.state)
            node = node.best_child

t = 0
for i in range(10):
    start_state = np.array([['.','.','.'],['.','.','.'],['.','.','.']])
    env = environment(start_state = start_state)
    agent = Agent(env, maximiser=True)
    start_time = time.time()
    agent.run()
    end_time = time.time()
    t += end_time-start_time
print("Average time required:", t/10)
print("Game tree of Noughts and Crosses : ")
agent.print_nodes()
agent.explored_nodes
# AlphaBeta Agent
class Alpha_beta_agent():
    def __init__(self,env,maximiser):
        self.env=env
        self.start_state=env.get_start_state()
        self.root_node=None
        self.neginf=-10**18
        self.posinf=10**18
        self.maximiser=maximiser
        self.player='x' if maximiser else 'o';
        self.explored_nodes=0

    def minimax(self,node,alpha,beta):
        self.explored_nodes+=1
        score=self.env.evaluation(node.state)
        if score!=0:
            node.score=score
            return node
        if self.env.checking(node.state):
            node.score=0
            return node
        if node.maximiser:
            best_score=self.neginf
            best_depth=self.posinf
            next_moves=self.env.get_moves(node.state,node.player)
            for move in next_moves:
                child=Node(state=move,depth=node.depth+1,maximiser=not node.maximiser,
                           player='o',parent=node)
                child=self.minimax(node=child,alpha=alpha,beta=beta)
                node.children.append(child)
                if best_score<child.score or (best_score==child.score and child.depth<best_depth):
                    best_score=child.score
                    best_depth=child.depth
                    node.best_child=child
                alpha=max(alpha,best_score)
                if beta<=alpha:
                    break
            node.depth=best_depth
            node.score=best_score
            return node
        else:
            best_score = self.posinf
            best_depth = self.posinf
            next_moves = self.env.get_moves(node.state, node.player)

            for move in next_moves:
                child = Node(state=move, depth=node.depth + 1,
                             maximiser=not node.maximiser, player='x', parent=node)

                child = self.minimax(node=child, alpha=alpha, beta=beta)
                node.children.append(child)

                if best_score > child.score or (best_score == child.score and child.depth < best_depth):
                    best_score = child.score
                    best_depth = child.depth
                    node.best_child = child

                beta = min(beta, best_score)
                if beta <= alpha:
                    break

            node.depth = best_depth
            node.score = best_score

            return node

    def run(self):

        self.root_node = Node(state=self.start_state, depth=0, maximiser=self.maximiser,
                              player=self.player, parent=None)

        self.root_node = self.minimax(node=self.root_node, alpha=self.neginf, beta=self.posinf)

    def print_nodes(self):

        node = self.root_node

        while node is not None:
            print(node.state)
            node = node.best_child


start_state = np.array([['.','.','.'],['.','.','.'],['.','.','.']])
env = environment(start_state = start_state)
agent = Alpha_beta_agent(env, maximiser=True)
agent.run()
agent.print_nodes()
t = 0
for i in range(10):
    start_state = np.array([['.','.','.'],['.','.','.'],['.','.','.']])
    env = environment(start_state = start_state)
    agent = Alpha_beta_agent(env, maximiser=True)
    start_time = time.time()
    agent.run()
    end_time = time.time()
    t += end_time-start_time
print("Average time required:", t/10)
agent.explored_nodes<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11452894438138479, 'fraction_numerical': 0.009534619750283769, 'mean_word_length': 1.742296918767507, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '539518', 'license': 'MIT', 'n_tokens_mistral': 2688, 'n_tokens_neox': 2555, 'n_words': 541, 'path': 'Lab_4minimax_alphabetaPruning.ipynb', 'repo_name': 'sumitramkr/CS362-AI-Lab-Reports-Winter-2021-2022', 'size': '8810'}