Question

I need to complete the code by implementing the min function and the alpha betta pruning in order to complete the tic tac toe game using pything.

code:

# -*- coding: utf-8 -*-
"""
Created on:

@author: 
"""
import random
from collections import namedtuple

GameState = namedtuple('GameState', 'to_move, utility, board, moves')
infinity = float('inf')
game_result = { 1:"Player 1 Wins", -1:"Player 2 Wins", 0:"It is a Tie" }

class Game:
    """To create a game, subclass this class and implement actions,
    result, utility, and terminal_test. You may override display and
    successors or you can inherit their default methods. You will also
    need to set the .initial attribute to the initial state; this can
    be done in the constructor."""

    def actions(self, state):
        """Return a list of the allowable moves at this point."""
        raise NotImplementedError

    def result(self, state, move):
        """Return the state that results from making a move from a state."""
        raise NotImplementedError

    def utility(self, state, player):
        """Return the value of this final state to player."""
        raise NotImplementedError

    def terminal_test(self, state):
        """Return True if this is a final state for the game."""
        return not self.actions(state)

    def to_move(self, state):
        """Return the player whose move it is in this state."""
        return state.to_move

    def display(self, state):
        """Print or otherwise display the state."""
        print(state)

    def __repr__(self):
        return '<{}>'.format(self.__class__.__name__)

    def play_game(self, *players):
        """Play an n-person, move-alternating game."""
        state = self.initial
        while True:
            for player in players:
                
                move = player(self, state)
                state = self.result(state, move)
                
                if self.terminal_test(state):
                    self.display(state)
                    print("Game Over.", game_result.get(self.utility(state, self.to_move(self.initial)), "Thank you for playing"))
                    return self.utility(state, self.to_move(self.initial))
                

class TicTacToe(Game):
    """Play TicTacToe on an h x v board, with Max (first player) playing 'X'.
    A state has the player to move, a cached utility, a list of moves in
    the form of a list of (x, y) positions, and a board, in the form of
    a dict of {(x, y): Player} entries, where Player is 'X' or 'O'."""

    def __init__(self, h=3, v=3, k=3):
        self.h = h
        self.v = v
        self.k = k
        moves = [(x, y) for x in range(1, h + 1)
                 for y in range(1, v + 1)]
        self.initial = GameState(to_move='X', utility=0, board={}, moves=moves)

    def actions(self, state):
        """Legal moves are any square not yet taken."""
        return state.moves

    def result(self, state, move):
        if move not in state.moves:
            print("\nThis is not a legal move, please play again\n")
            return state  # Illegal move has no effect
        
        board = state.board.copy()
        board[move] = state.to_move
        moves = list(state.moves)
        moves.remove(move)
        
        return GameState(to_move=('O' if state.to_move == 'X' else 'X'),
                         utility=self.compute_utility(board, move, state.to_move),
                         board=board, moves=moves)

    def utility(self, state, player):
        """Return the value to player; 1 for win, -1 for loss, 0 otherwise."""
        return state.utility if player == 'X' else -state.utility

    def terminal_test(self, state):
        """A state is terminal if it is won or there are no empty squares."""
        return state.utility != 0 or len(state.moves) == 0

    def display(self, state):
        board = state.board
        for x in range(1, self.h + 1):
            for y in range(1, self.v + 1):
                print(board.get((x, y), '.'), end=' ')
            print()
        
    def compute_utility(self, board, move, player):
        """If 'X' wins with this move, return 1; if 'O' wins return -1; else return 0."""
        if (self.k_in_row(board, move, player, (0, 1)) or
                self.k_in_row(board, move, player, (1, 0)) or
                self.k_in_row(board, move, player, (1, -1)) or
                self.k_in_row(board, move, player, (1, 1))):
            return +1 if player == 'X' else -1
        else:
            return 0

    def k_in_row(self, board, move, player, delta_x_y):
        """Return true if there is a line through move on board for player."""
        (delta_x, delta_y) = delta_x_y
        x, y = move
        n = 0  # n is number of moves in row
        while board.get((x, y)) == player:
            n += 1
            x, y = x + delta_x, y + delta_y
        x, y = move
        while board.get((x, y)) == player:
            n += 1
            x, y = x - delta_x, y - delta_y
        n -= 1  # Because we counted move itself twice
        return n >= self.k

""" REMOVE THIS LINE

def minimax_search(state, game):
    #Search game to determine best action; use minimax search

    player = game.to_move(state) # get the player to move

    def max_value(state): # max_value function to return v the value of a max node
        
        if game.terminal_test(state):
            return game.utility(state, player)
        v = -infinity
        for a in game.actions(state):
            v = max(v, min_value(game.result(state, a)))
        return v

    def min_value(state): # min_value function to return v the value of a min node
        #TO IMPLEMENT
                
    # Body of minimax:
    best_score = -infinity
    best_action = None
    
    #TO IMPLEMENT the body of the function minimax_search
    
   
    return best_action
    
    
REMOVE THIS LINE """

"""Define the players"""

def random_player(game, state):
    """A player that chooses a legal move at random."""
    return random.choice(game.actions(state)) if game.actions(state) else None

def minmax_player(game, state):
    """A player that chooses a legal move using minmax."""
    return minimax_search(state, game)

def alphabeta_player(game, state):
    """A player that chooses a legal move using minmax with alpha-beta pruning."""
    return alphabeta_search(state, game)
    
def human_player(game, state):
    """Human player: make a move by querying standard input."""
    
    print("Game board:")
    game.display(state)
    print("Available moves: {}".format(game.actions(state)))
    print("")
    move = None
    if game.actions(state):
        move_string = input('Your move? ')
        try:
            move = eval(move_string)
        except NameError:
            move = move_string
    else:
        print("no legal moves: passing turn to next player")
    return move

# play a game of tic tac toe

ttt_game = TicTacToe()

ttt_game.play_game(human_player,random_player)

Answer 1

  

import numpy as np
import random
from time import sleep
  
def create_board():
return(np.array([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]))

def possibilities(board):
l = []
  
for i in range(len(board)):
for j in range(len(board)):
  
if board[i][j] == 0:
l.append((i, j))
return(l)
  
# Select a random place for the player
def random_place(board, player):
selection = possibilities(board)
current_loc = random.choice(selection)
board[current_loc] = player
return(board)
  
# Checks whether the player has three
# of their marks in a horizontal row
def row_win(board, player):
for x in range(len(board)):
win = True
  
for y in range(len(board)):
if board[x, y] != player:
win = False
continue
  
if win == True:
return(win)
return(win)
  
# Checks whether the player has three
# of their marks in a vertical row
def col_win(board, player):
for x in range(len(board)):
win = True
  
for y in range(len(board)):
if board[y][x] != player:
win = False
continue
  
if win == True:
return(win)
return(win)
  
# Checks whether the player has three
# of their marks in a diagonal row
def diag_win(board, player):
win = True
  
for x in range(len(board)):
if board[x, x] != player:
win = False
return(win)
  
# Evaluates whether there is
# a winner or a tie
def evaluate(board):
winner = 0
  
for player in [1, 2]:
if (row_win(board, player) or
col_win(board,player) or
diag_win(board,player)):

winner = player
  
if np.all(board != 0) and winner == 0:
winner = -1
return winner
  
# Main function to start the game
def play_game():
board, winner, counter = create_board(), 0, 1
print(board)
sleep(2)
  
while winner == 0:
for player in [1, 2]:
board = random_place(board, player)
print("Board after " + str(counter) + " move")
print(board)
sleep(2)
counter += 1
winner = evaluate(board)
if winner != 0:
break
return(winner)
  
# Driver Code
print("Winner is: " + str(play_game()))