{}
"""The Tic-tac-Toe game."""
from __future__ import annotations
from enum import IntEnum
from typing import Callable, ClassVar, Final, Generator, Literal, NewType, Union, cast
__all__ = [
"Board",
"BoardPosition",
"Coordinate",
"MoveEvaluation",
"Player",
"Transformation",
"XCoord",
"YCoord",
]
BoardPosition = NewType("BoardPosition", int)
XCoord = Literal[0, 1, 2, 3]
YCoord = Literal[0, 1, 2, 3]
Coordinate = tuple[XCoord, YCoord]
"""The type for a co-ordinate."""
MoveEvaluation = Union[
tuple[int, XCoord, YCoord],
tuple[int, Literal[-1], Literal[-1]],
]
"""The type for the evaluation of a move"""
class Player(IntEnum):
"""Enumeration of players within a grid cell."""
NONE = 0b00
X = 0b01
O = 0b10 # noqa E741
@property
def opponent(self) -> Player:
"""The player's opponent."""
return {
Player.NONE: Player.NONE,
Player.X: Player.O,
Player.O: Player.X,
}[self]
def _identity(position: BoardPosition) -> BoardPosition:
"""No transformation.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return position
def _reflect_x(position: BoardPosition) -> BoardPosition:
"""Reflect the grid horizontally.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return cast(
"BoardPosition",
((position & 0b11000000110000001100000011000000) >> 6)
| ((position & 0b00110000001100000011000000110000) >> 2)
| ((position & 0b00001100000011000000110000001100) << 2)
| ((position & 0b00000011000000110000001100000011) << 6),
)
def _reflect_y(position: BoardPosition) -> BoardPosition:
"""Reflect the grid vertically.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return cast(
"BoardPosition",
((position & 0b11111111000000000000000000000000) >> 24)
| ((position & 0b00000000111111110000000000000000) >> 8)
| ((position & 0b00000000000000001111111100000000) << 8)
| ((position & 0b00000000000000000000000011111111) << 24),
)
def _reflect_x_y(position: BoardPosition) -> BoardPosition:
"""Reflect the grid horizontally and then vertically.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return _reflect_y(_reflect_x(position))
def _reflect_xy(position: BoardPosition) -> BoardPosition:
"""Reflect the grid in the x=y diagonal.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return cast(
"BoardPosition",
(position & 0b11000000001100000000110000000011)
| ((position & 0b00110000000011000000001100000000) >> 6)
| ((position & 0b00000000110000000011000000001100) << 6)
| ((position & 0b00001100000000110000000000000000) >> 12)
| ((position & 0b00000000000000001100000000110000) << 12)
| ((position & 0b00000011000000000000000000000000) >> 18)
| ((position & 0b00000000000000000000000011000000) << 18),
)
def _reflect_xny(position: BoardPosition) -> BoardPosition:
"""Reflect the grid in the x=-y diagonal.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return _reflect_x_y(_reflect_xy(position))
def _rotate_clockwise(position: BoardPosition) -> BoardPosition:
"""Rotate 90° clockwise about the centre of the grid.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return _reflect_x(_reflect_xy(position))
def _rotate_anticlockwise(position: BoardPosition) -> BoardPosition:
"""Rotate 90° anti-clockwise about the centre of the grid.
Args:
position: The positions taken by players on the grid.
Returns:
The position after applying the transformation.
"""
return _reflect_y(_reflect_xy(position))
class Transformation(IntEnum):
"""Enumeration of reflections and rotations relative to the centre of the grid."""
NONE = 0, ((+1, +0), (+0, +1)), _identity
REFLECT_X = 1, ((-1, +0), (+0, +1)), _reflect_x
REFLECT_Y = 2, ((+1, +0), (+0, -1)), _reflect_y
REFLECT_X_Y = 3, ((-1, +0), (+0, -1)), _reflect_x_y
REFLECT_DIAGONAL = 4, ((+0, +1), (+1, +0)), _reflect_xy
REFLECT_ANTI_DIAGONAL = 5, ((+0, -1), (-1, +0)), _reflect_xny
ROTATE_CLOCKWISE = 6, ((+0, +1), (-1, +0)), _rotate_clockwise
ROTATE_ANTICLOCKWISE = 7, ((+0, -1), (+1, +0)), _rotate_anticlockwise
def __new__(
cls,
_value: int,
_matrix: tuple[
tuple[Literal[-1, 0, 1], Literal[-1, 0, 1]],
tuple[Literal[-1, 0, 1], Literal[-1, 0, 1]],
],
_apply: Callable[[BoardPosition], BoardPosition],
) -> Transformation:
"""Create a new transformation enumeration.
Args:
_value: The integer enumeration for the transformation.
_matrix: The transformation matrix for co-ordinates.
_apply: The transformation function for a grid.
Returns:
The transformation enumeration instance.
"""
transform = int.__new__(cls, _value)
transform._value_ = _value
return transform
def __init__(
self,
_value: int,
_matrix: tuple[
tuple[Literal[-1, 0, 1], Literal[-1, 0, 1]],
tuple[Literal[-1, 0, 1], Literal[-1, 0, 1]],
],
_apply: Callable[[BoardPosition], BoardPosition],
) -> None:
"""Initialise the transformation.
Args:
_value: The integer enumeration for the transformation.
_matrix: The transformation matrix for co-ordinates.
_apply: The transformation function for a grid.
"""
super().__init__()
self.matrix: Final = _matrix
self.apply: Final = _apply
@property
def inverse(self) -> Transformation:
"""The inverse of the transformation."""
return [
Transformation.NONE,
Transformation.REFLECT_X,
Transformation.REFLECT_Y,
Transformation.REFLECT_X_Y,
Transformation.REFLECT_DIAGONAL,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.ROTATE_CLOCKWISE,
][self]
def __mul__(self, value: object) -> Transformation:
"""Multiply two transformations to give a composite transformation.
Args:
value: The second transformation.
Returns:
The composite transformation.
"""
assert isinstance(value, Transformation)
return [
[
Transformation.NONE,
Transformation.REFLECT_X,
Transformation.REFLECT_Y,
Transformation.REFLECT_X_Y,
Transformation.REFLECT_DIAGONAL,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.ROTATE_CLOCKWISE,
Transformation.ROTATE_ANTICLOCKWISE,
],
[
Transformation.REFLECT_X,
Transformation.NONE,
Transformation.REFLECT_X_Y,
Transformation.REFLECT_Y,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.ROTATE_CLOCKWISE,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.REFLECT_DIAGONAL,
],
[
Transformation.REFLECT_Y,
Transformation.REFLECT_X_Y,
Transformation.NONE,
Transformation.REFLECT_X,
Transformation.ROTATE_CLOCKWISE,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.REFLECT_DIAGONAL,
Transformation.REFLECT_ANTI_DIAGONAL,
],
[
Transformation.REFLECT_X_Y,
Transformation.REFLECT_Y,
Transformation.REFLECT_X,
Transformation.NONE,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.REFLECT_DIAGONAL,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.ROTATE_CLOCKWISE,
],
[
Transformation.REFLECT_DIAGONAL,
Transformation.ROTATE_CLOCKWISE,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.NONE,
Transformation.REFLECT_X_Y,
Transformation.REFLECT_X,
Transformation.REFLECT_Y,
],
[
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.ROTATE_CLOCKWISE,
Transformation.REFLECT_DIAGONAL,
Transformation.REFLECT_X_Y,
Transformation.NONE,
Transformation.REFLECT_Y,
Transformation.REFLECT_X,
],
[
Transformation.ROTATE_CLOCKWISE,
Transformation.REFLECT_DIAGONAL,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.REFLECT_Y,
Transformation.REFLECT_X,
Transformation.REFLECT_X_Y,
Transformation.NONE,
],
[
Transformation.ROTATE_ANTICLOCKWISE,
Transformation.REFLECT_ANTI_DIAGONAL,
Transformation.REFLECT_DIAGONAL,
Transformation.ROTATE_CLOCKWISE,
Transformation.REFLECT_X,
Transformation.REFLECT_Y,
Transformation.NONE,
Transformation.REFLECT_X_Y,
],
][self][value]
def coord(self, x: XCoord, y: YCoord) -> Coordinate:
"""Apply the transformation to the co-ordinate.
Args:
x: The x-value of the co-ordinate.
y: The y-value of the co-ordinate.
Returns:
The transformed co-ordinate.
"""
# (x y)(a b) = (ax+cy bx+dy)
# (c d)
xx, yy = x*2-3, y*2-3
(a, b), (c, d) = self.matrix
tx = cast("XCoord", (a*xx + c*yy + 3)//2)
ty = cast("YCoord", (b*xx + d*yy + 3)//2)
return (tx, ty)
class Board:
"""The Tic-Tac-Toe board."""
_position: BoardPosition
_transform: Transformation
_moves: int
_solutions: ClassVar[dict[Player, dict[BoardPosition, MoveEvaluation]]] = {
Player.X: {},
Player.O: {},
}
@classmethod
def from_string(cls, state: str) -> Board:
"""Create a board from a text representation of the board state.
Newline characters in the input are ignored. Any other character that is not X
or O is considered an empty grid-cell.
Args:
state: The text representation of the board state.
Returns:
The board representing that state.
"""
p = 0
ch_map = {Player.X.name: int(Player.X), Player.O.name: int(Player.O)}
count = [0, 0, 0]
for ch in reversed(state):
if ch == "\n":
continue
value = ch_map.get(ch, 0)
count[value] += 1
p = (p << 2) + value
if sum(count) != 16:
raise ValueError(f"{state} does not have 16 grid-cells.")
if count[1] < count[2]:
raise ValueError(f"{state} has too many O's.")
if count[1] > count[2] + 1:
raise ValueError(f"{state} has too many X's.")
return Board(
BoardPosition(p),
Transformation.NONE,
count[1] + count[2],
)
def __init__(
self,
positions: BoardPosition = BoardPosition(0),
transform: Transformation = Transformation.NONE,
moves: int = -1,
) -> None:
"""Initialise the board.
This will normalise the board by applying the transformation that minimises
the position value.
Args:
positions: The positions taken by players in the grid.
transform: The transformation applied to the grid.
moves: The number of moves taken by the players.
"""
pos, trans = min((t.apply(positions), t) for t in Transformation)
self._position = pos
self._transform = transform * trans
if moves < 0:
p: int = positions
counts = [16, 0, 0]
moves = 0
while p > 0:
cell = p & 0b11
if cell > 0:
counts[cell] += 1
counts[0] -= 1
moves += 1
p >>= 2
if counts[1] > counts[2] + 1:
raise ValueError(f"{positions:032b} has too many X's.")
if counts[2] > counts[1]:
raise ValueError(f"{positions:032b} has too many O's.")
self._moves = moves
@staticmethod
def _offset(x: XCoord, y: YCoord) -> int:
"""Convert the (x, y) co-ordinate into the bit-offset for the position.
Args:
x: The x co-ordinate.
y: The y co-ordinate.
Return:
The bit-offset for the cell within the positions integer.
"""
return 2*x + 8*y
def cell(
self,
x: XCoord,
y: YCoord,
) -> Player:
"""Return the player occupying the grid-cell at the given co-ordinate.
Args:
x: The x co-ordinate of the grid-cell.
y: The y co-ordinate of the grid-cell.
Return:
The Player occupying that grid-cell.
"""
xx, yy = self._transform.coord(x, y)
return Player((self._position >> Board._offset(xx, yy)) & 0b11)
def _cache_solution(
self,
player: Player,
result: MoveEvaluation,
) -> None:
score, x, y = result
if x == -1 or y == -1:
Board._solutions[player][self._position] = result
else:
xx, yy = self._transform.coord(x, y)
Board._solutions[player][self._position] = (score, xx, yy)
def _get_cached_solution(
self,
player: Player,
) -> MoveEvaluation:
result = Board._solutions[player][self._position]
score, x, y = result
if x == -1 or y == -1:
return result
xx, yy = self._transform.inverse.coord(x, y)
return (score, xx, yy)
@property
def possible_moves(self) -> Generator[Coordinate, None, None]:
"""The remaining possible moves for the current board state."""
p: int = self._transform.inverse.apply(self._position)
for y in (0, 1, 2, 3):
for x in (0, 1, 2, 3):
if (p & 0b11) == 0:
yield (x, y)
p >>= 2
@property
def current_player(self) -> Player:
"""The player taking the current move."""
return Player((self._moves % 2) + 1)
def move(self, x: XCoord, y: YCoord) -> Board:
"""Make a move for the current player on the board.
Args:
x: The x co-ordinate of the move.
y: The x co-ordinate of the move.
Returns:
A :class:`Board` instance representing the state after the move.
"""
xx, yy = self._transform.coord(x, y)
assert self.cell(x, y) == Player.NONE, (
f"({x}, {y}) {self._transform.name} => ({xx}, {yy}) is not none "
f"({self._position:032b})"
)
return Board(
positions=BoardPosition(
self._position | self.current_player << Board._offset(xx, yy),
),
transform=self._transform,
moves=self._moves + 1,
)
@property
def winner(self) -> Player:
"""The :class:`Player` who has won the board.
Returns:
The :class:`Player` who has won the board.
"""
if self._moves < 5:
return Player.NONE
for mask_x, shifts in (
(0b01_00000001_00000001, (2, 2, 2, 2, 2, 2, 2, 2)), # Vertical lines
(0b010101, (2, 6, 2, 6, 2, 6, 2, 6)), # Horizontal lines
(0b010000_00000100_00000001, (2, 6, 2, 6)), # y=x Diagonal lines
(0b000001_00000100_00010000, (2, 6, 2, 6)), # y=-x Diagonal lines
):
p: int = self._position
for shift in shifts:
if p < mask_x:
break
if (p & mask_x) == mask_x:
return Player.X if self._moves >= 15 else Player.O
mask_o = mask_x << 1
if (p & mask_o) == mask_o:
return Player.O if self._moves >= 15 else Player.X
p >>= shift
return Player.NONE
def optimal_move(
self,
maximising_player: Player,
) -> MoveEvaluation:
"""Find the optimal move for the current board state.
Returns:
A ``tuple`` containing:
- the score for the move;
- the x co-ordinate of the optimal move or ``-1`` for a draw; and
- the y co-ordinate of the optimal move or ``-1`` for a draw.
"""
if self._position in Board._solutions[maximising_player]:
return self._get_cached_solution(maximising_player)
winner = self.winner
result: MoveEvaluation
if winner != Player.NONE:
result = (
(17 - self._moves)
if winner == maximising_player
else (self._moves - 17),
-1,
-1,
)
Board._cache_solution(self, maximising_player, result)
return result
if self._moves >= 16:
result = (0, -1, -1)
Board._cache_solution(self, maximising_player, result)
return result
compare = max if maximising_player == self.current_player else min
result = compare(
(self.move(x, y).optimal_move(maximising_player)[0], x, y)
for x, y in self.possible_moves
)
Board._cache_solution(self, maximising_player, result)
return result
def __str__(self) -> str:
"""Return the board state.
Returns:
The board state.
"""
p: int = self._transform.inverse.apply(self._position)
def cell_value() -> str:
nonlocal p
c = {
int(Player.NONE): "_",
int(Player.X): "X",
int(Player.O): "O",
}[p & 0b11]
p >>= 2
return c
return "\n".join("".join(cell_value() for x in range(4)) for y in range(4))
if __name__ == "__main__":
board = Board()
print(f"\n{board}")
while not board.winner:
score, x, y = board.optimal_move(board.current_player)
if x == -1 or y == -1:
break
board = board.move(x, y)
print(f"\n{board} ({x}, {y}): {score}")