Cube drawing

[deanhystad]

As I said, not unbeatable. To be unbeatable the robot player has to look at all three boards simultaneously. That takes a really long time using minimax. I even wrote the code in C to see if that would be fast enough to use as a support module. No luck.

Here's another hack. The easiest way to beat the computer was something like this:
X O X
X O 6
O X 9

If player selects 6, computer selects 9 and the board ends in a draw, score = 0. But the computer can also draw selecting a square in an empty board. Because we are solving each board individually, there is no way for minmax to know that selecting a square on a different side will result in a loss on the next move.

An attempt to prevent this is to solve the board twice, once playing "O" (the computer mark) and once playing "X" (the player mark). When the computer plays "X" it will see playing square 9 is an immediate win (score = 10). No other square will have this high a score.

"""A tic-tac-toe game"""
import pygame
import random

PLAYER = 'X'
ROBOT = 'O'
colors = {None: 'black', ROBOT: 'red', PLAYER: 'green'}


class Robot:
    """Computer tic-tac-toe player"""
    def __init__(self, cube):
        self.boards = cube.boards

    def get_scores(self, board):
        """Get scores for all open squares on a board"""

        def minimax(mark, square, alpha=-1000, beta=1000, depth=0):
            """Compute a score for the square.  Uses using minimax
            algorithm with alpha/beta pruning.
            """
            # Place the marker and compute a score for the square.
            # Score is a win, a loss, a draw, or the score from
            # the next play.
            square.mark = mark
            if square.check_win():
                # Give extra weight to earlier wins/losses
                score = 10 - depth if mark == ROBOT else depth - 10
                board.depth = min(board.depth, depth)
            else:
                empty_squares = board.empty_squares()
                if not empty_squares:
                    score = 0  # Draw
                elif mark == PLAYER:
                    # Pick best move for robot
                    score = -1000
                    for s in empty_squares:
                        score = max(score, minimax(ROBOT, s, alpha, beta, depth+1))
                        alpha = max(alpha, score)
                        if alpha > beta:
                            break
                else:
                    # Guess what move we think player will make
                    score = 1000
                    for s in empty_squares:
                        score = min(score, minimax(PLAYER, s, alpha, beta, depth+1))
                        beta = min(beta, score)
                        if alpha > beta:
                            break
            # Undo play and return score
            square.mark = None
            return score

        # Collect scores for empty squares.  If board is empty,
        # minimax will return 0 for all squares
        board.depth = 10
        empty_squares = board.empty_squares()
        if len(empty_squares) == 9:
            board.scores = [[0, s] for s in empty_squares]
        else:
            # Calling minimax twice.  The first is to find the square
            # giving us best chance to win board.  Second is to prevent
            # abandoning board early and giving player an easy win.
            board.scores = [[minimax("O", s), s] for s in empty_squares]
            [minimax("X", s, depth=1) for s in empty_squares]

    def play(self):
        """Place robot mark."""
        # Get scores for all empty squares
        depth = 10
        for iboard in self.boards:
            self.get_scores(board)
            depth = min(depth, board.depth)

        # Select board(s) with minimum depth.  This is the board(s) that
        # will win/lose in the least number of moves.
        scores = []
        for board in self.boards:
            if board.depth <= depth:
                scores.extend(board.scores)

        # Randomly select from best scores on the selected board(s).
        max_score = max(score[0] for score in scores)
        squares = [score[1] for score in scores if score[0] >= max_score]
        return random.choice(squares)


class Square:
    """I am a square in a tic-tac-toe board in 3D"""
    def __init__(self, board, index, side, center=(0, 0, 0)):
        self.board = board
        self.index = index
        self.mark = None
        self.corners = [
            pygame.Vector3(-1, -1, 0) * side / 2,
            pygame.Vector3(1, -1, 0) * side / 2,
            pygame.Vector3(1, 1, 0) * side / 2,
            pygame.Vector3(-1, 1, 0) * side / 2
        ]
        self.move(center)

    def rotate(self, rotation):
        """Rotate square (rx, ry, rz) degrees"""
        for deg, axis in zip(rotation, ((1, 0, 0), (0, 1, 0), (0, 0, 1))):
            if deg:
                for corner in self.corners:
                    corner.rotate_ip(deg, axis)

    def move(self, offset):
        """Move square offset (x, y, z) pixels"""
        x, y, z = offset
        for corner in self.corners:
            corner.x += x
            corner.y += y
            corner.z += z

    def projection(self):
        """Return corners projected on xy plane"""
        return [pygame.Vector2(p.x, p.y) for p in self.corners]

    def draw(self, surface):
        """Draw projection of square on xy plane"""
        pygame.draw.polygon(surface, colors[self.mark], self.projection())

    def contains(self, point):
        """Return True if projection contains point."""
        def area(a, b, c):
            """Compute area of triangle"""
            return abs((a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0)

        def has_point(a, b, c, p):
            """Return True if triange ABC contains point p."""
            return area(a, b, c) >= int(area(a, p, b) + area(b, p, c) + area(c, p, a))

        a, b, c, d = self.projection()
        return has_point(a, b, c, point) or has_point(a, c, d, point)

    def check_win(self):
        return self.board.check_win(self)


class Board:
    """A 3x3 tic-tac-toe boaard"""
    winning_combos = (
        (0, 2, 4, 6, 8), (1, 3, 5, 7), (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, side):
        dx = side / 3
        self.squares = []
        for index in range(9):
            x = (index % 3 - 1) * dx
            y = (index // 3 - 1) * dx
            self.squares.append(Square(self, index, dx-6, (x, y, 0)))
        self.scores = None
        self.depth = 10

    def empty_squares(self):
        """Return list of empty squares"""
        return [s for s in self.squares if s.mark is None]

    def check_win(self, square):
        """Return winning combination from last move, else None"""
        for combo in self.winning_combos:
            if square.index in combo:
                squares = [self.squares[i] for i in combo]
                if all(square.mark == s.mark for s in squares):
                    return squares
        return None


class Cube:
    """Three tic-tac-toe boards plastered on the sides of a cube"""
    def __init__(self, side):
        def make_board(center, rotation):
            board = Board(side)
            for square in board.squares:
                square.rotate(rotation)
                square.move(center)
            return board

        self.boards = [
            make_board((0, 0, -side/2), (0, 0, 0)),
            make_board((side/2, 0, 0), (0, 270, 0)),
            make_board((0, -side/2, 0), (90, 0, 0))
        ]
        self.squares = [s for b in self.boards for s in b.squares]
        self.winner = None
        self.mark = PLAYER
        self.reset()

    def click(self, point):
        """Try to place mark in clicked square."""
        if self.mark == PLAYER:
            for square in self.squares:
                if square.contains(point):
                    if square.mark is None:
                        self.play(square, self.mark)
                        return square
                    break
        return None

    def play(self, square, mark):
        """Place mark in square.  Test if is a winning move"""
        square.mark = mark
        self.mark_count += 1
        if winner := square.check_win():
            self.winner = winner
            for square in self.squares:
                if square not in winner:
                    square.mark = None
        self.mark = PLAYER if mark == ROBOT else ROBOT

    def done(self):
        """Return True if there is a winner or draw"""
        return self.winner or self.mark_count >= 27

    def reset(self):
        """Reset all boards to empty"""
        self.mark_count = 0
        self.winner = None
        for square in self.squares:
            square.mark = None

    def draw(self, surface):
        """Draw all the tic-tac-toe boards."""
        surface.fill("white")
        for square in self.squares:
            square.draw(surface)
        pygame.display.flip()


def main():
    """Play tic-tac-toe"""
    pygame.display.set_caption("Tic-Tac-Toe")
    surface = pygame.display.set_mode((500, 500))
    cube = Cube(300)
    center = surface.get_rect()
    for square in cube.squares:
        square.rotate((0, 45, 0))
        square.rotate((22.5, 0, 0))
        square.move((center.centerx, center.centery, 0))
    robot = Robot(cube)
    cube.draw(surface)

    running = True
    while running:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
            elif event.type == pygame.MOUSEBUTTONDOWN:
                if cube.done():
                    cube.reset()
                else:
                    cube.click(pygame.Vector2(event.pos))
                    pygame.event.clear()
                if cube.mark == ROBOT and not cube.done():
                    cube.play(robot.play(), "O")
                cube.draw(surface)


if __name__ == "__main__":
    pygame.init()
    main()
    pygame.quit()