Tic tac toe Generalized AI (prune alpha-beta minimax) Develop an algorithm in py
ID: 3912072 • Letter: T
Question
Tic tac toe Generalized AI (prune alpha-beta minimax)
Develop an algorithm in python console should receive as input the dimensions m, n, j (the player),
the constant k is a state of the game Tic-tac-toe. The player "X" is represented by the integer 1,
the player "O" by the integer 2 and blank positions on the board by the integer 0. Example of
Possible valid entries include:
Example of a 3 × 3 entry, k = 3 being played by "X".
./a.out 3 3 1 3 0 0 0 0 0 0 0 0 0
Example of a 3 × 3 entry, k = 3 being played by "O".
./a.out 3 3 2 3 1 1 2 0 0 0 2 1 0
Example of a 4 × 4 entry, k = 2 being played by "O".
./a.out 4 4 2 2 1 2 1 2 0 0 0 0 0 0 0 0 0 0 1 0
Output:
The algorithm developed should print on the standard output of the operating system the result
of the game played by the BOT through a pair of indices ij, where (i Example of a valid output:
1 1
Example of a valid output:
2 1
Explanation / Answer
## Generalized Tic-Tac-Toe
import board as b
import config as c
import math
import unittest
import sys
class Game:
## MORE LIKE POOP METHODS ##
def __init__(self, num_spaces, winning_paths, board = {}, whos_turn = c.COMPUTER):
''' Initalizes a Game object '''
self.num_spaces = num_spaces
self.winning_paths = winning_paths
# The board will be represented via a dictionary,
# {space: [c.BLANK|c.HUMAN|c.COMPUTER]}
if board:
self.board = board
else:
self.board = b.Board(self.num_spaces, self.winning_paths)
self.whos_turn = whos_turn
def make_move(self, space, player):
"""Puts <player>'s token on <space>
If the game is over, returns the winner (c.HUMAN, c.COMPUTER, or, c.TIE).
If the game is not over, it returns False.
"""
## First, change the state of the 'board' map
if space not in self.board.get_board():
raise Exception("Space not in board")
elif self.board.get_player(space) is not c.BLANK:
raise Exception("Incorrect move")
else:
self.board.add_marker(space, player)
winning_player = self.board.is_terminal() # False if there is no winning_player
if winning_player:
return winning_player
else:
return False
def change_player(self):
''' Switches the current player '''
if self.whos_turn == c.COMPUTER:
self.whos_turn = c.HUMAN
else:
self.whos_turn = c.COMPUTER
def play_game(self, max_depth = False):
''' Returns the winner if there is one (or returns TIE)'''
winning_player = False
while not winning_player:
self.display_game()
space = self.get_next_move(max_depth)
winning_player = self.make_move(space, self.whos_turn)
self.change_player()
return winning_player
def get_next_move(self, max_depth=False):
'''Gets the next move, by listening to the self.whos_turn class variable.
If it is human's turn, it asks for input from the user.
If it is the computer's turn, it performs a minimax search with alpha-beta pruning,
with depth-limited search if requested.
'''
if self.whos_turn == c.HUMAN:
try:
space = int(raw_input("Enter a next move: "))
except:
print "Invalid input. Enter a positive integer."
return self.get_next_move(max_depth)
if space in xrange(1, self.num_spaces+1) and self.board.get_player(space) is c.BLANK:
return space
else:
print "Invalid input. Pick an available space."
return self.get_next_move(max_depth)
elif self.board.is_empty() and max_depth > 4: # First move if large max_depth
return self.first_move()
else:
board_copy = self.board.get_board_copy()
if max_depth:
(score, space) = self.minimax_max_alphabeta_DL(c.NEG_INF, c.POS_INF, board_copy, max_depth)
else:
(score, space) = self.minimax_max_alphabeta(c.NEG_INF, c.POS_INF, board_copy)
return space
def display_game(self):
'''Presents a visual representation of the board. If the board size is square, it calls
display_game_square() to represent a visual output. (see below). If the board size
is not square, it simply informs you of the available spaces, the spaces you occupy, and
the spaces your opponent (the computer) occupies.
'''
if self.num_spaces in [4, 9, 16, 25, 36]: # Reasonable sizes
self.display_game_square()
else:
if self.whos_turn == c.HUMAN:
print "Winning paths: ", self.board.winning_paths
available_spaces = self.board.get_free_spaces()
print "Available Spaces: ", available_spaces
spaces_HUMAN_owns = self.board.get_HUMAN_spaces()
print "Spaces you own: ", spaces_HUMAN_owns
spaces_COMPUTER_owns = self.board.get_COMPUTER_spaces()
print "Spaces COMPUTER owns: ", spaces_COMPUTER_owns
def display_game_square(self):
''' If the board size is square, creates a visual representation of the board. '''
num_rows = int(math.sqrt(self.num_spaces))
if self.whos_turn == c.HUMAN:
print "Your turn"
else:
print "COMPUTER's turn"
for row in range(num_rows):
row_str = ""
for col in range(num_rows):
space = num_rows*row + col + 1
token = self.board.get_player(space)
if token == c.BLANK:
row_str += "_ "
elif token == c.HUMAN:
row_str += "X "
else:
row_str += "O "
print row_str
## AI METHODS ##
def ai_dummy(self):
"""Returns the first of all available spaces (not used in prouduction, just testing)"""
for space, player in self.board.iteritems():
if player == c.BLANK:
return space
def minimax_max(self, board):
''' Minimax algorithm without alpha-beta pruning (not used in production)'''
if board.is_terminal():
return (board.obj(), None) # Space is none, because the board is terminal
else:
children = []
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.COMPUTER)
children.append((self.minimax_min(new_board)[0], space))
return max(children)
def minimax_min(self, board):
''' Minimax algorithm without alpha-beta pruning (not used in production)'''
if board.is_terminal():
return (board.obj(), None) # Space is none, because the board is terminal
else:
children = []
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.HUMAN)
children.append((self.minimax_max(new_board)[0], space))
return min(children)
def minimax_max_alphabeta(self, alpha, beta, board):
''' Minimax algorithm with alpha-beta pruning. '''
if board.is_terminal():
return (board.obj(), None) # Space is none, because the board is terminal
else:
max_child = (c.NEG_INF, None)
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.COMPUTER)
score = self.minimax_min_alphabeta(alpha, beta, new_board)[0]
if score > max_child[0]:
max_child = (score, space)
if max_child[0] >= beta:
return max_child # Shouldn't help anyway
alpha = max(alpha, score)
return max_child
def minimax_min_alphabeta(self, alpha, beta, board):
''' Minimax algorithm with alpha-beta pruning.'''
if board.is_terminal():
return (board.obj(), None)
else:
min_child = (c.POS_INF, None)
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.HUMAN)
score = self.minimax_max_alphabeta(alpha, beta, new_board)[0]
if score < min_child[0]:
min_child = (score, space)
if min_child[0] <= alpha:
return min_child # Shouldn't help anyway
beta = min(beta, score)
return min_child
def minimax_max_alphabeta_DL(self, alpha, beta, board, depth):
'''Minimax algorithm with alpha-beta pruning and depth-limited search. '''
if board.is_terminal() or depth <= 0:
return (board.obj(), None) # Terminal (the space will be picked up via recursion)
else:
max_child = (c.NEG_INF, None)
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.COMPUTER)
score = self.minimax_min_alphabeta_DL(alpha, beta, new_board, depth - 1)[0]
if score > max_child[0]:
max_child = (score, space)
if max_child[0] >= beta:
return max_child # Shouldn't help anyway
alpha = max(alpha, score)
return max_child
def minimax_min_alphabeta_DL(self, alpha, beta, board, depth):
'''Minimax algorithm with alpha-beta pruning and depth-limited search. '''
if board.is_terminal() or depth <= 0:
return (board.obj(), None) # Terminal (the space will be picked up via recursion)
else:
min_child = (c.POS_INF, None)
for space in board.get_free_spaces():
new_board = board.get_board_copy()
new_board.add_marker(space, c.HUMAN)
score = self.minimax_max_alphabeta_DL(alpha, beta, new_board, depth - 1)[0]
if score < min_child[0]:
min_child = (score, space)
if min_child[0] <= alpha:
return min_child # Shouldn't help anyway
beta = min(beta, score)
return min_child
def first_move(self):
'''Picks the space that appears in the most winning paths first.
This is used for large board sizes.
'''
all_spaces = [space for path in self.winning_paths for space in path]
counts = {}
for space in all_spaces:
if space in counts:
counts[space] += 1
else:
counts[space] = 1
return max([(count, space) for space, count in counts.iteritems()])[1]
def start_game(file_path):
'''Opens the file, processes the input, and initailizes the Game() object'''
try:
input_file = open(file_path ,'r')
except:
raise Exception("File not found!!! Make sure you didn't make a spelling error.")
num_spaces = int(input_file.readline())
winning_paths = []
for line in input_file:
path = map(int, line.split())
winning_paths.append(path)
game = Game(num_spaces, winning_paths)
return game
class TicTacToeTest(unittest.TestCase):
''' Test suite, only used for debugging. I wanted to experiment with
test-driven development.
'''
def setUp(self):
self.game = start_game('examples/tictactoe.txt')
self.board = Board(self.game.num_spaces, self.game.winning_paths)
def tearDown(self):
self.game = None
def test_board_properties(self):
assert self.board.get_free_spaces() == [1,2,3,4,5,6,7,8,9]
assert len(self.board.get_children(c.COMPUTER)) == 9
self.board.add_marker(1, c.COMPUTER)
assert self.board.get_free_spaces() == [2,3,4,5,6,7,8,9]
assert len(self.board.get_children(c.HUMAN)) == 8
def test_basic_game_play(self):
assert self.game.board.obj() == 0
assert self.game.board.obj() == 0
self.game.make_move(2, c.COMPUTER)
assert self.game.board.get_player(2) == c.COMPUTER
assert self.game.board.obj() == 10*2
self.game.make_move(3, c.HUMAN)
assert self.game.board.get_player(3) == c.HUMAN
assert self.game.board.obj() == -10
self.game.make_move(5, c.COMPUTER)
self.game.make_move(4, c.HUMAN)
self.game.make_move(8, c.COMPUTER)
assert self.game.board.obj() == WIN_SCORE
if __name__ == "__main__":
if len(sys.argv) != 2:
print "Invalid input. Make sure to include a file path."
print "Example: $ python gentictactoe.py <file_path>"
else:
max_depth = raw_input("Do you want the AI to perform a depth-limited search?
If yes, enter a positive integer representing the desired depth.
If no, enter 'n': ")
# Ask user for maximum depth
if max_depth == 'n':
max_depth = False
else:
try:
if int(max_depth) > 0:
max_depth = int(max_depth)
else:
raise Exception("Please enter a positive integer for max_depth, or an 'n'")
except:
raise Exception("Please enter a positive integer for max_depth, or a 'n'")
# Get file path, and start playing!
file_path = sys.argv[1]
game = start_game(file_path)
winning_player = game.play_game(max_depth)
if winning_player == c.HUMAN:
print "HUMAN is the winner!"
elif winning_player == c.COMPUTER:
print "COMPUTER is the winner!"
else:
print "Tie game!"