Source

python-ai / src / tic-tac-toe / game.py

Full commit
import struct, string


class Player(object):
    def actions(self, state):
        return [(i,j) for i in range(3) for j in range(3)
                      if state.getSquare(i, j) == state.emptyMark]
    def nextState(self, state, action):
        (i, j) = action
        return state.playSquare(i, j)


class NaivePlayer(Player):
    def getNextAction(self, state):
        actions = self.actions(state)
        return actions[0]
    def __repr__(self):
        return str(self)
    def __str__(self):
        return "NaivePlayer()"


class MinimaxPlayer(Player):
    NEG_INF = -10
    INF = 10
    def utility(self, state, mark):
        if not state.complete():
            return None
        elif state.winner() == None:
            return 1
        elif state.winner() == mark:
            return 2
        else:
            return 0
    def getNextAction(self, state):
        return self.minimax(state)
    def minimax(self, state):
        mark = state.currentMark
        a, score = self.maxValue(state, mark)
        return a
    def maxValue(self, state, mark):
        if state.complete():
            return (None, self.utility(state, mark))
        actions = self.actions(state)
        best_action = None
        best_action_score = self.NEG_INF
        for action in actions:
            next = self.nextState(state, action)
            a, score = self.minValue(next, mark)
            if score > best_action_score:
                best_action = action
                best_action_score = score
        return (best_action, best_action_score)
    def minValue(self, state, mark):
        if state.complete():
            return (None, self.utility(state, mark))
        actions = self.actions(state)
        best_action = None
        best_action_score = self.INF
        for action in actions:
            next = self.nextState(state, action)
            a, score = self.maxValue(next, mark)
            if score < best_action_score:
                best_action = action
                best_action_score = score
        return (best_action, best_action_score)
    def __repr__(self):
        return str(self)
    def __str__(self):
        return "MinimaxPlayer()"


class HumanPlayer(Player):
    def getNextAction(self, state):
        action = None
        while True:
            print("Your move, pick a row (0-2):")
            row = int(input())
            print("Now pick a col (0-2):")
            col = int(input())
            action = (row, col)
            if action in self.actions(state):
                return action
            print("Not a valid move! Pick again.")
    def __repr__(self):
        return str(self)
    def __str__(self):
        return "HumanPlayer()"


class BadMove(Exception):
    def __str__(self):
        return "Not a valid move."


class State(object):
    def __init__(self):
        self.emptyMark = 'N'
        self.currentMark = 'X'
        self.otherMark = 'O'
        self.board = (['N']*3, ['N']*3, ['N']*3)
    def __repr__(self):
        str(self)
    def __str__(self):
        b = self.board
        s = ""
        s += b[0][0] + "|" + b[0][1] + "|" + b[0][2] + "\n"
        s += b[1][0] + "|" + b[1][1] + "|" + b[1][2] + "\n"
        s += b[2][0] + "|" + b[2][1] + "|" + b[2][2] + "\n"
        return s
    def copy(self):
        next = State()
        next.emptyMark = self.emptyMark
        next.currentMark = self.currentMark
        next.otherMark = self.otherMark
        for i in range(3):
            for j in range(3):
                next.board[i][j] = self.board[i][j]
        return next
    def complete(self):
        return self.boardFull() or self.winner()
    def boardFull(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 'N':
                    return False
        return True
    def winner(self):
        for s in (self.currentMark, self.otherMark):
            if self.winnerRows(s): return s
            if self.winnerCols(s): return s
            if self.winnerDiag(s): return s
        return None
    def winnerRows(self, s):
        b = self.board
        for row in range(3):
            if (b[row][0], b[row][1], b[row][2]) == (s, s, s):
                return True
        return False
    def winnerCols(self, s):
        b = self.board
        for col in range(3):
            if (b[0][col], b[1][col], b[2][col]) == (s, s, s):
                return True
        return False
    def winnerDiag(self, s):
        b = self.board
        if (b[0][0], b[1][1], b[2][2]) == (s, s, s):
            return True
        if (b[0][2], b[1][1], b[2][0]) == (s, s, s):
            return True
        return False
    def getSquare(self, row, col):
        return self.board[row][col]
    def playSquare(self, col, row):
        next = self.copy()
        if row not in range(3) or col not in range(3):
            raise BadMove()
        elif next.board[col][row] != next.emptyMark:
            raise BadMove()
        next.board[col][row] = next.currentMark
        (next.currentMark, next.otherMark) = (next.otherMark, next.currentMark)
        return next


class Board(object):
    def __init__(self, player_a, player_b):
        self.player_a = player_a
        self.player_b = player_b
    def play(self):
        current = State()
        turn, waiting = self.player_a, self.player_b
        while not current.complete():
            print("Current player:", turn)
            print("Waiting player:", waiting)
            print("Current board state:")
            print(current)
            action = turn.getNextAction(current)
            (i, j) = action
            current = current.playSquare(i, j)
            turn, waiting = waiting, turn
        print("Final board state:")
        print(current)
        if current.winner() == current.otherMark:
            return waiting
        elif current.winner() == current.currentMark:
            return turn
        else:
            return None


def main():
    player_a = HumanPlayer()
    player_b = MinimaxPlayer()
    b = Board(player_a, player_b)
    winner = b.play()
    if winner == player_a:
        print("You win!")
    elif winner == player_b:
        print("You lose! Good day, sir.")
    else:
        print("Tie.")


if __name__ == "__main__":
    main()