I am trying to make a tic tac toe ai in python using minimax algorithm. I have read a few blogs and came up with these functions. But for some reason it does not work.
Code:
class RunTimeError(Exception):
pass
class TicTacToe:
'''Tic Tac Toe class'''
SYMBOL_X = 'x'
SYMBOL_O = 'o'
SYMBOL_EMPTY = '-'
INDEX_MAP = {
0: [0, 0], 1: [0, 1], 2: [0, 2],
3: [1, 0], 4: [1, 1], 5: [1, 2],
6: [2, 0], 7: [2, 1], 8: [2, 2]
}
def __init__(self) -> None:
'''Initialize the game'''
self.reset()
def reset(self) -> None:
'''Reset the game'''
self.board = [[self.SYMBOL_EMPTY for _ in range(3)] for _ in range(3)]
self.current_turn = 'x'
self.moves_stack = []
self.winner = None
self.game_state = 'RUNNING'
def swap_turn(self) -> None:
'''Swap the turn'''
self.current_turn = self.SYMBOL_X if self.current_turn == self.SYMBOL_O else self.SYMBOL_O
def play_move(self, index: int) -> None:
'''Play a move on the given index:
0 1 2
3 4 5
6 7 8'''
if self.game_state != 'RUNNING':
raise RuntimeError('Game already terminated')
if not isinstance(index, int):
raise RunTimeError(f"Expected index type 'int' got {type(index)}")
try:
y, x = self.INDEX_MAP[index]
except KeyError:
raise RunTimeError(f'Expected index to be from 0-8, got {index}')
if self.board[y][x] != self.SYMBOL_EMPTY:
raise RunTimeError('Invalid Move - Box occupied')
self.board[y][x] = self.current_turn
self.moves_stack.append(index)
self.update_game_state()
self.swap_turn()
def undo_move(self) -> int:
'''Reverse the last move and return its index'''
index = self.moves_stack.pop()
y, x = self.INDEX_MAP[index]
self.board[y][x] = self.SYMBOL_EMPTY
self.winner = None
self.game_state = 'RUNNING'
self.swap_turn()
return index
def update_game_state(self) -> None:
'''Check for a winner'''
win_cases = [
self.board[0][0] == self.board[0][1] == self.board[0][2] == self.current_turn,
self.board[1][0] == self.board[1][1] == self.board[1][2] == self.current_turn,
self.board[2][0] == self.board[2][1] == self.board[2][2] == self.current_turn,
self.board[0][0] == self.board[1][0] == self.board[2][0] == self.current_turn,
self.board[0][1] == self.board[1][1] == self.board[2][1] == self.current_turn,
self.board[0][2] == self.board[1][2] == self.board[2][2] == self.current_turn,
self.board[0][0] == self.board[1][1] == self.board[2][2] == self.current_turn,
self.board[0][2] == self.board[1][1] == self.board[2][0] == self.current_turn,
]
if any(win_cases):
self.winner = self.current_turn
self.game_state = 'WIN'
elif self.SYMBOL_EMPTY not in [element for row in self.board for element in row]:
self.game_state = 'DRAW'
def generate_possible_moves(self) -> list:
'''Returns a list with all possible move indexes'''
moves = []
for num in range(8):
if num not in self.moves_stack:
moves.append(num)
return moves
def __str__(self) -> str:
'''Returns the board as a string'''
return '\n'.join([
f' {self.board[0][0]} | {self.board[0][1]} | {self.board[0][2]}',
'-' * 11,
f' {self.board[1][0]} | {self.board[1][1]} | {self.board[1][2]}',
'-' * 11,
f' {self.board[2][0]} | {self.board[2][1]} | {self.board[2][2]}'
])
def ai_play(self):
best_score = -100
best_move = None
for move in self.generate_possible_moves():
self.play_move(move)
score = self.minmax(False, self.current_turn)
print(score)
self.undo_move()
if score > best_score:
best_score = score
best_move = move
self.play_move(best_move)
def minmax(self, maximizing, symbol):
if self.game_state == 'DRAW':
return 0
elif self.game_state == 'WIN':
return 1 if self.winner == symbol else -1
scores = []
for move in self.generate_possible_moves():
self.play_move(move)
scores.append(self.minmax(not maximizing, symbol))
self.undo_move()
return max(scores) if maximizing else min(scores)
game1 = TicTacToe()
print(game1)
game1.ai_play()
print(game1)
It raises the following error:
Traceback (most recent call last):
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 139, in <module>
game1.ai_play()
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 112, in ai_play
score = self.minmax(False, self.current_turn)
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
scores.append(self.minmax(not maximizing, symbol))
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
scores.append(self.minmax(not maximizing, symbol))
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
scores.append(self.minmax(not maximizing, symbol))
[Previous line repeated 4 more times]
File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 134, in minmax
return max(scores) if maximizing else min(scores)
ValueError: max() arg is an empty sequence
I dont have any idea whats the issue(I have spent a lot of time trying to solve it) Any help would be appreciated!
The max and min functions expect at-least one item in the passed list. When in minmax function there are no more possible moves, generate_possible_moves returns an empty list, so scores is []. max([]) will throw an error because there is nothing to do max from.
You will have to assign some score for when there is no possible move and return that when len(scores) is 0
Also, you have to call update_game_state when you undo any move, otherwise the state is incorrect.