tictactoe.py

import random
import curses
import sys
import time


class Board(object):
    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 __init__(self, state=None):
        self.state = [None] * 9 if not state else state[:]
        self.f = {
            0: 'x',
            1: 'o',
            None: ' '
        }

    def __str__(self):
        return ('+---+---+---+\n'
                '| %s | %s | %s |\n'
                '+---+---+---+\n'
                '| %s | %s | %s |\n'
                '+---+---+---+\n'
                '| %s | %s | %s |\n'
                '+---+---+---+\n') % tuple(self.f[k] for k in self.state)

    def is_full(self):
        return 9 == sum(1 for mark in self.state if mark is not None)

    def is_empty(self):
        return 9 == sum(1 for mark in self.state if mark is None)

    def fill(self, position, mark):
        if self.state[position] is not None:
            raise Exception('Slot is filled already')
        self.state[position] = mark

    def get_free_positions(self):
        return [index
                for index, position in enumerate(self.state)
                if position is None]

    def is_tied(self):
        return not (self.habemus_victor(0) or self.habemus_victor(1)) and \
                not self.is_empty()

    def habemus_victor(self, mark):
        for combo in self.WINNING_COMBOS:
            if [mark, mark, mark] == [self.state[position] for position in combo]:
                return True
        return False

    def is_finished(self):
        return self.habemus_victor(0) or \
                self.habemus_victor(1) or \
                self.is_full()


class Player(object):
    def __init__(self, mark):
        self.mark = mark

    def make_move(self, board):
        raise NotImplementedError


class RandomPlayer(Player):
    def make_move(self, board):
        index = random.choice(board.get_free_positions())
        board.fill(index, self.mark)


class Human(Player):
    def __init__(self, mark, screen):
        super().__init__(mark)
        self.screen = screen

    def clear_line(self):
        self.screen.move(8, 0)
        self.screen.clrtoeol()
        self.screen.addstr(8, 0, '')
        self.screen.refresh()

    def make_move(self, board):
        free_positions = board.get_free_positions()
        self.clear_line()
        self.screen.addstr(8, 0, 'Choose one position %s: ' % free_positions)
        self.screen.refresh()
        position = -1
        while True:
            try:
                position = int(chr(self.screen.getch()))
                board.fill(position, self.mark)
                self.clear_line()
                break
            except:
                pass


def negamax(board, depth, mark):
    opponent_mark = 1 - mark
    max_score = -9999
    best_position = None

    # board evaluation
    if board.habemus_victor(mark):
        return 10 - depth, None

    if board.habemus_victor(opponent_mark):
        return depth - 10, None

    if board.is_full():
        return 0, None

    for position in board.get_free_positions():
        _board = Board(board.state)
        _board.fill(position, mark)
        score, _ = negamax(_board, depth + 1, opponent_mark)
        if -score > max_score:
            max_score = -score
            best_position = position
    return max_score, best_position


class PerfectPlayer(Player):
    def make_move(self, board):
        if board.is_empty():
            # optimal position is 0
            # but we will use any corner
            position = random.choice([0, 2, 6, 8])
        else:
            _, position = negamax(board, 0, self.mark)
        board.fill(position, self.mark)


def game():
    screen = curses.initscr()
    curses.noecho()
    curses.cbreak()

    players = (PerfectPlayer(0), PerfectPlayer(1))
    # players = (Human(0, screen), Human(1, screen))
    # players = (Human(0, screen), PerfectPlayer(1))
    b = Board()
    turn = 0

    while not b.is_finished():
        player = players[turn % 2]
        player.make_move(b)
        screen.addstr(0, 0, str(b))
        screen.refresh()
        time.sleep(1)
        turn += 1

    curses.echo()
    curses.nocbreak()
    curses.endwin()


if __name__ == '__main__':
    game()