I need help for implement the minimax adversarial search algorithm on the game of Connect Four. The game is played on an 8x8 board of red and black pieces. For us, we'll use $n=8$. ---- I attached main and tester file in description. Question: The functions that need to complete( # YOU FILL THIS IN) are below:

possible_moves neighbor winning_state tournament RandomAgent(Agent) class FirstMoveAgent(Agent) class MinimaxAgent(Agent)

Tests whether your minimax agent outperforms a random agent. minimax agent to win 85% of games against a random agent. --------------------------------------------------------------------------------------------------------- import copy import time import abc

class Game(object): """A connect four game."""

def __init__(self, grid): """Instances differ by their board.""" self.grid = copy.deepcopy(grid) # No aliasing!

def display(self): """Print the game board.""" for row in self.grid: for mark in row: print(mark, end='') print() print()

def possible_moves(self): """Return a list of possible moves given the current board.""" # YOU FILL THIS IN

def neighbor(self, col, color): """Return a Game instance like this one but with a move made into the specified column.""" # YOU FILL THIS IN

def utility(self): """Return the minimax utility value of this game""" # YOU FILL THIS IN

def winning_state(self): """Returns float("inf") if Red wins; float("-inf") if Black wins; 0 if board full; None if not full and no winner""" # YOU FILL THIS IN

class Agent(object): """Abstract class, extended by classes RandomAgent, FirstMoveAgent, MinimaxAgent. Do not make an instance of this class."""

def __init__(self, color): """Agents use either RED or BLACK chips.""" self.color = color

@abc.abstractmethod def move(self, game): """Abstract. Must be implemented by a class that extends Agent.""" pass

class RandomAgent(Agent): """Naive agent -- always performs a random move"""

def move(self, game): """Returns a random move""" # YOU FILL THIS IN

class FirstMoveAgent(Agent): """Naive agent -- always performs the first move"""

def move(self, game): """Returns the first possible move""" # YOU FILL THIS IN

class MinimaxAgent(Agent): """Smart agent -- uses minimax to determine the best move"""

def move(self, game): """Returns the best move using minimax""" # YOU FILL THIS IN

def tournament(simulations=50): """Simulate connect four games, of a minimax agent playing against a random agent"""

redwin, blackwin, tie = 0,0,0 for i in range(simulations):

game = single_game(io=False)

print(i, end=" ") if game.winning_state() == float("inf"): redwin += 1 elif game.winning_state() == float("-inf"): blackwin += 1 elif game.winning_state() == 0: tie += 1

print("Red %d (%.0f%%) Black %d (%.0f%%) Tie %d" % (redwin,redwin/simulations*100,blackwin,blackwin/simulations*100,tie))

return redwin/simulations

def single_game(io=True): """Create a game and have two agents play it."""

game = Game([['-' for i in range(8)] for j in range(8)]) # 8x8 empty board if io: game.display()

maxplayer = MinimaxAgent('R') minplayer = RandomAgent('B')

while True:

m = maxplayer.move(game) game = game.neighbor(m, maxplayer.color) if io: time.sleep(1) game.display()

if game.winning_state() is not None: break

m = minplayer.move(game) game = game.neighbor(m, minplayer.color) if io: time.sleep(1) game.display()

if game.winning_state() is not None: break

if game.winning_state() == float("inf"): print("RED WINS!") elif game.winning_state() == float("-inf"): print("BLACK WINS!") elif game.winning_state() == 0: print("TIE!")

return game

if __name__ == '__main__': single_game(io=True) #tournament(simulations=50)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Tester.py

from minimax_connectfour import *

class GameBoards(): game1 = Game([['-' for i in range(8)] for j in range(8)])

def test_moves1(): assert len(GameBoards.game1.possible_moves()) == len([0, 1, 2, 3, 4, 5, 6, 7]) assert set(GameBoards.game1.possible_moves()) == set([0, 1, 2, 3, 4, 5, 6, 7])

def test_moves2(): assert GameBoards.game9.possible_moves() == [0]

def test_moves3(): assert len(GameBoards.game5.possible_moves()) == len([0, 1, 3, 4, 5, 6, 7]) assert set(GameBoards.game5.possible_moves()) == set([0, 1, 3, 4, 5, 6, 7])

def test_neighbor1(): game1_a = GameBoards.game1.neighbor(2, 'R') assert game1_a.grid == GameBoards.game2.grid

def test_neighbor2(): game2_a = GameBoards.game2.neighbor(3, 'R') assert game2_a.grid == GameBoards.game8.grid

def test_neighbor3(): game9_a = GameBoards.game9.neighbor(0, 'B') assert game9_a.grid == GameBoards.game10.grid

def test_winningstate1(): assert GameBoards.game1.winning_state() is None

def test_winningstate2(): assert GameBoards.game3.winning_state() == float("-inf")

def test_winningstate3(): assert GameBoards.game4.winning_state() == float("inf")

def test_winningstate4(): assert GameBoards.game5.winning_state() == float("inf")

def test_winningstate5(): assert GameBoards.game6.winning_state() == float("-inf")

def test_winningstate6(): assert GameBoards.game7.winning_state() == 0

def test_tournament575(): assert tournament(50) >= .85