I recently created a Tic Tac Toe Minimax Algorithm that successfully worked. Shortly after, I modified the code to work for Connect 4. However, the algorithm keeps crashing with the error
local variable 'bestMove' referenced before assignment (Referring to the variable bestMove in the minimax function)
The only methods I changed from the Tic Tac Toe to Connect 4 were the showBoard(), getAvailableMoves(), and getWinner() functions.
I suspect the issue may be in the getAvailableMoves() because the amount of available moves on a board is more variable in Connect 4 than Tic Tac Toe because of the whole stacking idea. While I did implement that in the function, perhaps I shouldn't be doing it there, not sure though.
Here is my code below:
minimax.py
class ComputerBrain :
def __init__(self, player = "x") :
self._squares = {}
def createBoard(self) :
for i in range(6) :
for j in range(7):
self._squares[i, j] = " "
self.showBoard()
print("\n")
def showBoard(self) :
print ()
print("------------------------------")
print("|", self._squares[0, 0], "|", self._squares[0, 1], "|", self._squares[0, 2], "|", self._squares[0, 3],
"|", self._squares[0, 4], "|", self._squares[0, 5], "|", self._squares[0, 6], "|")
print("------------------------------")
print("|", self._squares[1, 0], "|", self._squares[1, 1], "|", self._squares[1, 2], "|", self._squares[1, 3],
"|", self._squares[1, 4], "|", self._squares[1, 5], "|", self._squares[1, 6], "|")
print("------------------------------")
print("|", self._squares[2, 0], "|", self._squares[2, 1], "|", self._squares[2, 2], "|", self._squares[2, 3],
"|", self._squares[2, 4], "|", self._squares[2, 5], "|", self._squares[2, 6], "|")
print("------------------------------")
print("|", self._squares[3, 0], "|", self._squares[3, 1], "|", self._squares[3, 2], "|", self._squares[3, 3],
"|", self._squares[3, 4], "|", self._squares[3, 5], "|", self._squares[3, 6], "|")
print("------------------------------")
print("|", self._squares[4, 0], "|", self._squares[4, 1], "|", self._squares[4, 2], "|", self._squares[4, 3],
"|", self._squares[4, 4], "|", self._squares[4, 5], "|", self._squares[4, 6], "|")
print("------------------------------")
print("|", self._squares[5, 0], "|", self._squares[5, 1], "|", self._squares[5, 2], "|", self._squares[5, 3],
"|", self._squares[5, 4], "|", self._squares[5, 5], "|", self._squares[5, 6], "|")
print("------------------------------")
def getAvailableMoves(self) :
self._availableMoves = []
for i in range(6) :
for j in range(7):
is_legal = False
if i == 5:
is_legal = True
else:
if self._squares[i + 1, j] != " ":
is_legal = True
else:
is_legal = False
if self._squares[i, j] == " " and is_legal:
self._availableMoves.append((i, j))
return self._availableMoves
def makeMove(self, position, player) :
x, y = position
self._squares[x, y] = player
def complete(self) :
if " " not in self._squares.values() :
return True
if self.getWinner() != None :
return True
return False
def getWinner(self) :
for player in ("x", "o") :
for i in range(6):
for j in range(7):
if i < 3:
if self._squares[i, j] == player and self._squares[i + 1, j] == player and self._squares[i + 2, j] == player and self._squares[i + 3, j] == player:
return player
if j < 4:
if self._squares[i, j] == player and self._squares[i, j + 1] == player and self._squares[i, j + 2] == player and self._squares[i, j + 3] == player:
return player
if self._squares[i, j] == player and self._squares[i + 1, j + 1] == player and self._squares[i + 2, j + 2] == player and self._squares[i + 3, j + 3] == player:
return player
if j > 2:
if self._squares[i, j] == player and self._squares[i + 1, j - 1] == player and self._squares[i + 2, j - 2] == player and self._squares[i + 3, j - 3] == player:
return player
if i >= 3 and j < 4:
if self._squares[i, j] == player and self._squares[i, j + 1] == player and self._squares[i, j + 2] == player and self._squares[i, j + 3] == player:
return player
if " " not in self._squares.values() :
return "tie"
return None
def getEnemyPlayer(self, player) :
if player == "x" :
return "o"
return "x"
def minimax(self, player, depth = 0) :
self.showBoard()
if player == "o":
best = -10
else:
best = 10
if self.complete() :
if self.getWinner() == "x" :
return -10 + depth, None
elif self.getWinner() == "tie" :
return 0, None
elif self.getWinner() == "o" :
return 10 - depth, None
for move in self.getAvailableMoves() :
self.makeMove(move, player)
val, _ = self.minimax(self.getEnemyPlayer(player), depth+1)
self.makeMove(move, " ")
if player == "o" :
if val > best :
best, bestMove = val, move
else :
if val < best :
best, bestMove = val, move
return best, bestMove
run.py
from minimax import ComputerBrain
def findPlace(available, value):
for i in range(7):
x, y = available[i]
if value == y:
return x
return False
def run():
game = ComputerBrain()
game.createBoard()
print("Computer is X and you are O");
print("Who goes first? Computer (1) or You (2): ");
choice = int(input())
if choice == 1:
_, bestMove1 = game.minimax("x")
game.makeMove(bestMove1, "x")
game.showBoard()
# game.makeMove(randint(0, 9), "x")
# game.showBoard()
while (not game.complete()):
canMove = True;
badMove = False;
while canMove:
if (badMove):
print("No More Spaces Available Here")
print("Please enter your move: ")
new_move = int(input()) - 1
move = findPlace(game.getAvailableMoves(), new_move)
if move == False:
badMove = True;
canMove = True;
else:
game.makeMove((move, new_move), "o")
badMove = False;
canMove = False;
game.showBoard();
if game.complete():
break;
_, bestMove1 = game.minimax("x")
print("best move: ", bestMove1)
game.makeMove(bestMove1, "x")
game.showBoard()
if game.getWinner() != None:
print("\n Result: ", game.getWinner())
else:
print("\n DRAW")
print("\n New Game? (y, n)")
answer = str(input())
if answer == "y":
print("\n \n \n")
run()
else:
return
run()
As @RicardoAbe stated in his comment, I incorrectly assigned -10 and +10 values to the initial minimax function rather than setting them to negative and positive infinity.