3
\$\begingroup\$

Notes:

  • I know \ are against PEP8; they are for readibility
  • I created this working through a tutorial
  • I forgot to add blank lines, so it may be a little squished
''' Tic-Tac-Toe Minimax Program by Peter'''

#Tutorial found at: http://giocc.com/concise-implementation-of-minimax-through-higher-order-functions.html'''
class GameState:
    def __init__(self,board):
        self.board = board
        self.winning_combos = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    def is_gameover(self):
        '''returns if a game_state has been won or filled up'''
        if self.board.count('X') + self.board.count('O') == 9:
            return True
        for combo in self.winning_combos:
            if (self.board[combo[0]] == 'X' and self.board[combo[1]] == 'X' and self.board[combo[2]] == 'X') or \
            (self.board[combo[0]] == 'O' and self.board[combo[1]] == 'O' and self.board[combo[2]] == 'O'):
                return True
        return False
    def get_possible_moves(self):
        '''returns all possible squares to place a character'''
        squares = []
        for index, square in enumerate(self.board):
            if square != 'X' and square != 'O':
                squares.append(index)
        return squares
    def get_next_state(self, move, our_turn):
        '''returns the gamestate with the move filled in'''
        copy = self.board[:]
        if our_turn:
            copy[move] = 'X'
        else:
            copy[move] = 'O'
        return GameState(copy)
'''Named evals instead of eval to respect the eval function. http://stackoverflow.com/questions/9383740/what-does-pythons-eval-do'''
def evals(game_state):
    '''score a game_state from the computers point of view, 1 = win, 0 = tie, -1 = lose'''
    for combo in game_state.winning_combos:
        if game_state.board[combo[0]] == 'X' and game_state.board[combo[1]] == 'X' and game_state.board[combo[2]] == 'X':
            return 1    
        elif game_state.board[combo[0]] == 'O' and game_state.board[combo[1]] == 'O' and game_state.board[combo[2]] == 'O':
            return -1
    else:
        return 0

'''max and min will call on each other recusively, until a terminal state'''
def max_play(game_state):
    '''if the game is over returns score, otherwise calls min_play on it's childen (possible moves from the state) and returns the maximum'''
    if game_state.is_gameover():
        return evals(game_state)
    return max(map(lambda move: min_play(game_state.get_next_state(move, True)), game_state.get_possible_moves()))
def min_play(game_state):
    '''if the game is over returns score, otherwise calls max_play on it's childen (possible moves from the state) and returns the minimum'''
    if game_state.is_gameover():
        return evals(game_state)
    return min(map(lambda move: max_play(game_state.get_next_state(move, False)), game_state.get_possible_moves()))

def minimax(game_state):
    '''returns the max of mapping the (move, score) tuple to the possible move using [1] of the tuple the (score)'''
    return max(map(lambda move: (move, min_play(game_state.get_next_state(move, True))), game_state.get_possible_moves()), key = lambda x: x[1])

def pretty_print(board):
    '''prints a list by 3 chars, joined by spaces'''
    print(' '.join(board[:3]))
    print(' '.join(board[3:6]))
    print(' '.join(board[6:9]))

'''starting board, assuming it is X's turn.'''
start_board = '_ _ _ ' + '_ O _ ' + '_ _ _'

'''Interpreting and printing start board'''
start_game_state = GameState(start_board.split(' '))
pretty_print(start_game_state.board)
'''Finding best possible move and score'''
move, score = minimax(start_game_state)
'''Displaying move and outcome'''
if score == 0:
    word = 'TIE'
elif score == 1:
    word = 'WIN'
else:
    word = 'LOSS, who rigged the board?!?'
print('X should go at index #',move, 'Which will always result in a ' + word) 
start_game_state.board[move] = 'X'
pretty_print(start_game_state.board)
\$\endgroup\$
3
\$\begingroup\$

A couple minor comments:

  1. start_board is defined as a string with spaces, then only used once with the spaces split. This means that you can completely remove the variable and do start_game_state = GameState(['_','_','_','O','_','_','_']), which the would be better formatted over multiple lines to make the layout clear:

    GameState(['_','_','_',
               '_','O','_',
               '_','_','_'
             ])
    
  2. The functions min_play, max_play, and minmax are near duplicates of eachother and should be merged into one with a second argument.

  3. All three of those functions could be made clearer with a generator expression/list comprehension

  4. Your comments should be written using the comment operator rather than the multi-line string operator, which should be used only for multiline comments and docstrings

  5. The function get_next_state could be simplified using a ternary operator.

  6. Get_possible_moves could also be simplified with a list comprehension.

  7. Instead of checking if all nine squares are filled in is_gameover, you could check if no squares are free, which is faster as it only does one pass through the loop.

  8. lambda x:x[1] should be replaced with operator.itemgetter(1), which is faster.

  9. is_gameover and evals are near duplicates of eachother and should be merged


Fixed code:

#Tic-Tac-Toe Minimax Program by Peter

#Tutorial found at: http://giocc.com/concise-implementation-of-minimax-through-higher-order-functions.html
from operator import itemgetter

class GameState:
    def __init__(self,board):
        self.board = board
        self.winning_combos = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
    def get_winner(self):
        '''returns None if the game is still going, otherwise scores from computer's point of view (1=win, 0=tie, -1=win)'''
        if self.board.count('_') == 0:
            return 0
        for combo in self.winning_combos:
            if (self.board[combo[0]] == 'X' and self.board[combo[1]] == 'X' and self.board[combo[2]] == 'X'):
                return 1
            elif self.board[combo[0]] == 'O' and self.board[combo[1]] == 'O' and self.board[combo[2]] == 'O':
                return 0
        return None
    def get_possible_moves(self):
        '''returns all possible squares to place a character'''
        return [index for index, square in enumerate(self.board) if square == '_']
    def get_next_state(self, move, our_turn):
        '''returns the gamestate with the move filled in'''
        copy = self.board[:]
        copy[move] = 'X' if our_turn else 'O'
        return GameState(copy)


def play(game_state, our_turn):
    '''if the game is over returns (None, score), otherwise recurses to find the best move and returns it and the score.'''
    score = game_state.get_winner()
    if score != None:
        return None, score
    moves = ((move, play(game_state.get_next_state(move, our_turn), not our_turn)[1]) for move in game_state.get_possible_moves())
    return (max if our_turn else min)(moves, key=itemgetter(1))

def pretty_print(board):
    '''prints a list by 3 chars, joined by spaces'''
    print(' '.join(board[:3]))
    print(' '.join(board[3:6]))
    print(' '.join(board[6:9]))


#Interpreting and printing board
start_game_state = GameState(['_','_','_',
                              '_','O','_',
                              '_','_','_'
                            ])
pretty_print(start_game_state.board)
#Finding best possible move and score
move, score = play(start_game_state, True)
#Displaying move and outcome
if score == 0:
    word = 'TIE'
elif score == 1:
    word = 'WIN'
else:
    word = 'LOSS, who rigged the board?!?'
print('X should go at index #',move, 'Which will always result in a ' + word) 
start_game_state.board[move] = 'X'
pretty_print(start_game_state.board)
\$\endgroup\$
  • \$\begingroup\$ Can you break this line down? ((move, play(game_state.get_next_state(move, our_turn)), not our_turn) for move in game_state.get_possible_moves())) \$\endgroup\$ – PAS Dec 12 '16 at 15:19
  • \$\begingroup\$ Also, is that line the same as: for move in game_state.get_possible_moves: moves.append(move, minimax(game_state.get_next_state(move, our_turn), not our_turn)) \$\endgroup\$ – PAS Dec 12 '16 at 15:28
  • \$\begingroup\$ This code does not work :( \$\endgroup\$ – PAS Dec 12 '16 at 17:05
  • \$\begingroup\$ @PAS Fixed, some parens were slightly out of position. \$\endgroup\$ – pppery Dec 12 '16 at 20:11
  • \$\begingroup\$ @PAS mostly. The function I call is called play, not minmax, the argument to moves.append in your code needs to be parenthesized, game_state.get_possible_moves() is a function and thus needs parents, and my code doesn't compute the move until it is needed, whereas yours computes all of them at once. Comprehensions are generally more pythonic than for loops, though. \$\endgroup\$ – pppery Dec 12 '16 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.