Minimax Tic-Tac-Toe implementation

Question

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)

Answer 1

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)