"""
Tic-tac-toe engine code and helpers.
"""
from collections import Counter, defaultdict, deque
from functools import lru_cache
from typing import Callable, Deque, Dict, Optional, Tuple
GameAgent = Callable[[str], Tuple[str, ...]]
MoveCache = Dict[str, Tuple[str, ...]]
@lru_cache()
def move_at(board: str, index: int) -> str:
"""
Make a move at `board[index]`.
This helper function that takes in a board state and makes the next move at the position indicated by `index`
"""
return board[:index] + "OX"[board.count(".") % 2] + board[index + 1 :]
@lru_cache()
def all_possible_moves(board: str) -> Tuple[str, ...]:
"""
Make all legal moves - a valid agent but more useful in the engine.
This function acts as a valid agent and is used by default in the engine to generate every
possible move on a board to explore the full game tree of a given agent
"""
return tuple(move_at(board, i) for i, c in enumerate(board) if c == ".")
@lru_cache()
def winner(board: str) -> Optional[str]:
"""Return the winning symbol, or None if neither player has outright won the game."""
# A player with their symbol in any row, column, or diagonal has won.
# (note that this doesn't check that they're the *only* winner!)
for a, b, c, d in (
(0, 1, 2, 3), # 1st row (top-bottom) Here's the board:
(4, 5, 6, 7), # 2nd row (top-bottom) 0 1 2 3
(8, 9, 10, 11), # 3rd row (top-bottom) 4 5 6 7
(12, 13, 14, 15), # 4th row (top-bottom) 8 9 10 11
(0, 4, 8, 12), # 1st column (left-right) 12 13 14 15
(1, 5, 9, 13), # 2nd column (left-right)
(2, 6, 10, 14), # 3rd column (left-right)
(3, 7, 11, 15), # 4th column (left-right)
(0, 5, 10, 15), # top-left to bottom-right diagonal
(3, 6, 9, 12), # top-right to bottom-left diagonal
):
if board[a] == board[b] == board[c] == board[d] != ".":
return board[a]
return None
@lru_cache()
def check_valid_moves(board: str, moves: Tuple[str, ...]) -> None:
"""
Check that moves are valid, and provide useful feedback if not.
This set of checks is generated by thinking ahead of possible ways that an agent function
could return something that won't work within the engine and covering edge cases as they come up
"""
# Check that moves are the right type (tuple)
if not isinstance(moves, tuple):
raise TypeError(f"moves={moves!r} must be a tuple")
# Check that the list of moves is not empty
if not moves:
raise ValueError(f"You did not make any moves from board={board!r}")
# Looping now over each move
for i, move in enumerate(moves):
msg = f"moves[{i}]={move!r}, from board={board!r}, is an invalid move: "
# Check that move is correct type (string)
if not isinstance(board, str):
raise TypeError(msg + "must be a string")
# Each move should be a string of sixteen characters to represent the board
if not len(board) == 16:
raise ValueError(msg + "must have sixteen characters")
# "X", "O" and "." are the only valid options for each position on the board
if not set(board).issubset(".XO"):
raise ValueError(msg + "must only contain '.', 'X', and 'O'")
# Check that each proposed move only changes a single "." into a valid piece
diff = [(a, b) for a, b in zip(board, move) if a != b]
if len(diff) != 1:
raise RuntimeError(msg + "must change exactly one character")
if diff[0] not in {(".", "X"), (".", "O")}:
raise RuntimeError(msg + "must change a '.' to either 'X' or 'O'")
# if (move.count("X") - move.count("O") == 0):
# # True for initial states and true for all moves -> true for board.
# raise RuntimeError(msg + "moved for the wrong side")
# Check that each move is only given once in the list
if len(set(moves)) < len(moves):
duplicates = Counter(moves) - Counter(set(moves))
raise ValueError(f"Duplicate moves are not allowed, got {duplicates}")
def engine(agent: GameAgent, *, opponent: GameAgent = all_possible_moves, print_report=True) -> MoveCache:
"""
Fully explore the behaviour of the provided agent function.
This is where the magic happens.
"""
# The queue tracks board positions that we haven't gotten the move(s) for yet.
# We use a deque so that we can operate in order of increasing depth, which
# results errors being encountered for the simplest possible boards.
queue: Deque[str] = deque(("................",) + opponent("................"))
# For each board that we've seen the moves for, the gametree stores what those
# moves were. Because you can never get back to the same position, we can use
# a flat dictionary for this.
# Initilise a dictionary to hold all the games, integers to hold the win/loss/draw tallies and
# a placeholder variable to hold the loss report that can be queried to find if that variable is
# not `None`
gametree: MoveCache = {}
wins = 0
draws = 0
losses = 0
loss_report = None
# `queue` is pre-filled with some moves above and as each board is played new moves by the opponent
# are added within the loop. As such, `while queue` will loop until every branch of the game tree is
# fully played out
while queue:
# Pull the first (left most) item from the queue
board = queue.popleft()
# If the board has already been played in a different branch of the tree (these branches are merging)
# ignore and exit this iteration of the while loop
if board in gametree:
continue
# Pass the new board to the agent function to obtain that agents list of moves
try:
moves = agent(board)
except Exception as e:
raise Exception(f"Error while making moves on board={board!r}") from e
# We can also allow for an agent to return more than one preferred move. We would apply all the same
# thinking (adding the move to a queue and feeding it back to the agent) but play a branching game
# on both the engine and the agent side
if isinstance(moves, str):
moves = tuple([moves])
# If the moves are given as a list, recast as a tuple, note type checking occurs in `check_valid_moves`
if isinstance(moves,list):
moves = tuple(moves)
# Error and rule checking on the list of moves from a given board
check_valid_moves(board, moves)
# Add the board and the moves the agent would make to the game tree dictionary for later reference
gametree[board] = moves
# What pieces (/symbols) the agent is playing with on the current board
# Note this is a more compact version of the helper function in the agent file - they have identical
# output functionality in the compiler even though they differ on the page
symbol = "OX"[board.count(".") % 2]
# Now we loop over each board to determine if the game is concluded or if the next agent should take its turn
for move in moves:
# Check we haven't already considered this move
if move in gametree:
continue
# Check for a winner
# If the player won, increment the tally
if winner(move) == symbol:
wins += 1
# If the game was not won but is over (i.e. a loss)
elif winner(move) is not None:
# If we're generating a loss report (and don't have one - next line) create one
if loss_report is None:
loss_report = printable_move_sequance(
reverse_engineer_sequance(gametree, move, board))
# Increment the loss tally
losses += 1
# Given there is no winner, check if the board is fully played out
elif "." not in move:
draws += 1
# We've covered off all the conditions that would cause the game to end, any
# move that made it this far through the logic is a live game so we should have the opponent play
# their moves and add then to the queue for the agent to consider in future cycles of the outer loop
else:
# Pass each move to the opponent agent function and run the same checks for a winner
for reply in opponent(move):
# If the player won, increment the tally
if winner(reply) == symbol:
wins += 1
# If the game was not won but is over (i.e. a loss)
# If we're generating a loss report (and don't have one - next line) create one
elif winner(reply) is not None:
if loss_report is None:
loss_report = printable_move_sequance(
reverse_engineer_sequance(gametree, reply, move, board))
# Increment the loss tally
losses += 1
# Given there is no winner, check if the board is fully played out
elif "." not in reply:
draws += 1
# This time after covering off all the scenarios that would end a game after the opponent
# makes a move then add this new live game to the queue
else:
queue.append(reply)
# After the while loop is done (and we've played out every game) its time to, if asked, report what we've done
if print_report:
print("Shall we play every game!")
print(f"Good work - {agent.__name__} always makes valid moves!")
print(f"\nPlaying {agent.__name__} against {opponent.__name__}:")
print(f" losses: {losses}, draws: {draws}, wins: {wins}")
print(f" (total games played: {losses + draws + wins})")
print()
if loss_report:
print(" first game where you lost:")
print(f" (you were playing as {'OX'[((len(loss_report[0])+3)//6 )%2]})")
for line in loss_report:
print(" " + line)
print()
# The gametree is the total record from the engine, we pass it out for other code to pick up and unpack
return gametree
def reverse_engineer_sequance(gametree: MoveCache, *boards: str) -> Tuple[str, ...]:
"""
Describe the sequence of moves leading to `board`.
Takes the gametree and a particular board (with the option to specify some number of proceeding boards
through the *args syntax) and working backwards up the gametree gives *one* of the possible sequences
of moves to arrive at the given board
"""
# Flip the gametree to work backwards up it rather than the usual behaviour of working down
inverse: Dict[str, list] = defaultdict(list)
for b, moves in gametree.items():
for m in moves:
inverse[m].append(b)
# Compile the given board(s) into the start of a sequence (or cast a single board as a list)
seq = list(boards)
# The sequence starts at the final move and works back up the gametree, while the final board in the sequence
# is in the gametree keep working your way back to the top, adding each board to the end of the sequance as you go
while seq[-1] in inverse:
seq.append(inverse[seq[-1]][0]) # Note: here is the point we explicitly travel up just one of possible many paths
# up the tree with the slice into seq[-1] at [0] taking whichever board was
# arbitarily placed first in that list
# Flip the reverse sequance to give the game from start to given board
return tuple(reversed(seq))
def printable_move_sequance(seq: Tuple[str, ...]) -> Tuple[str, ...]:
"""
Takes a sequence of moves and returns a tuple which when printed/written to a file
is readily interpretable by a human
Paires with the `reverse_engineer_sequance` function to generate that sequance
"""
return tuple(
" ".join(m[s] for m in seq)
for s in [slice(0, 4), slice(4, 8), slice(8, 12), slice(12, 16)]
)
def lose_only_to_forks(board: str) -> Tuple[str, ...]:
"""Make all legal moves which cannot lose one turn later."""
# An example agent, which performs better than `all_possible_moves`. Still not optimal
# though, and more lookahead can get expensive...
op = "XO"[board.count(".") % 2]
moves = tuple(move_at(board, i) for i, c in enumerate(board) if c == ".")
noloss = tuple(m for m in moves if not any(winner(r) == op for r in all_possible_moves(m)))
return noloss or moves
My Cybernetics Journey – Hello World!