Playing (more) Tic-Tac-Toe#
Hello everyone and welcome back! Last week, we discussed my live-coded approach (and improvements!) to the game of Tic-Tac-Toe. This week, I wanted to see how flexible my approach is going to be.
But, before we get into it, make sure you register for our next expert lab, “Word Games: An Expert’s Approach to Seemingly Simple Games.” During this session, we’ll unravel the mysteries of word unscrambling in Jumble and challenge ourselves with the strategic wordplay of Scrabble. You’ll witness firsthand how Python’s powerful string manipulation features and other data structures can simplify coding of these games.
Now, let’s get back into the game at hand!
Previous Requirements#
First, remind ourselves of the requirements we were working from:
Standard 3×3 game of Tic-Tac-Toe
Given a board, determine if a player won and which player it is.
That’s all well and good, but I want to see what happens when I push my code a bit further.
New Requirements#
4×4 (up to N×N) size boards
Given a board, determine if a player won and who that player is, but this time, accommodate:
More than 2 players
Players win by having continuous marks in ANY row, column, or diagonal
Players have to have at least three of these marks, up to and including N
Boards may be incomplete (e.g., have spaces still available)
The existing traversal code should serve us quite well for these new constraints. The primary change I am concerned about is that, currently, our code for the 3×3 board only considers the “main” diagonals for a win. This means that it only registers a diagonal that starts in a corner of the board. But, what if a player gets three diagonal spots in a row that start in a different square? We need to consider these “off” diagonals as valid wins.
3×3 Solution#
Let’s start by grabbing some of our previous code and see how it stacks up against the new requirements:
def transpose(board):
yield from zip(*board)
def winner(row):
uniq_row = set(row) - {'.'}
if len(uniq_row) == 1:
return True, next(iter(uniq_row))
return False, '.'
def rows(board):
yield from (tuple(row) for row in board)
def columns(board):
yield from transpose(board)
def ldiag(board):
diag = []
for i, row in enumerate(rows(board), start=0):
diag.append(row[i])
yield tuple(diag)
def rdiag(board):
diag = []
for i, row in enumerate(rows(board), start=1):
diag.append(row[-i])
yield tuple(diag)
def traverse(board):
for trav in [rows, columns, rdiag, ldiag]:
for i, group in enumerate(trav(board)):
yield trav, i, group
board = [
['o', 'o', 'o'],
['x', 'x', 'x'],
['x', 'o', 'o']
]
print(
*(f'{trav.__name__: <8} {i}: {group}'
for trav, i, group in traverse(board)),
sep='\n',
)
rows 0: ('o', 'o', 'o')
rows 1: ('x', 'x', 'x')
rows 2: ('x', 'o', 'o')
columns 0: ('o', 'x', 'x')
columns 1: ('o', 'x', 'o')
columns 2: ('o', 'x', 'o')
rdiag 0: ('o', 'x', 'x')
ldiag 0: ('o', 'x', 'o')
Now let’s see how this code stacks up against our larger board:
board = [
['x', 'o', 'o', 'x'],
['o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o'],
['x', 'o', 'o', 'x']
]
print(
*(f'{trav.__name__: <8} {i}: {group}'
for trav, i, group in traverse(board)),
sep='\n',
)
rows 0: ('x', 'o', 'o', 'x')
rows 1: ('o', 'o', 'o', 'o')
rows 2: ('x', 'x', 'x', 'o')
rows 3: ('x', 'o', 'o', 'x')
columns 0: ('x', 'o', 'x', 'x')
columns 1: ('o', 'o', 'x', 'o')
columns 2: ('o', 'o', 'x', 'o')
columns 3: ('x', 'o', 'o', 'x')
rdiag 0: ('x', 'o', 'x', 'x')
ldiag 0: ('x', 'o', 'x', 'x')
The row and column traversal seems fine to me, but it’s still only considering the main diagonals. Let’s see if we can update our ldiag/rdiag functions to extract these and rename them to make their application a little more accurate:
def major_diags(board):
# above major diagonals
for offset in range(1, len(board)):
yield tuple(
board[i][i - offset] for i in range(offset)
)
# major diagonal
yield tuple(row[i] for i, row in enumerate(rows(board)))
# below diagonals
for offset in reversed(range(1, len(board))):
yield tuple(
board[i - offset][i] for i in range(offset)
)
board = [
['x', 'x', 'o', 'x'],
['o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o'],
['x', 'o', 'o', 'x']
]
major = {
('x', ),
('o', 'o',),
('x', 'o', 'o',),
('x', 'o', 'x', 'x',),
('o', 'x', 'o',),
('x', 'o',),
('x',),
}
assert major == {*major_diags(board)}
We could improve the implementation by avoiding calls to functions like reversed, but, for this prototype, we’ll leave this approach as is.
With the major diagonals taken care of, implementing the off diagonals is fairly straightforward. We could copy and adapt the logic, but we can just rely on a small trick of flipping the board across the vertical axis (a long way of saying “reverse each row”).
def flip_lr(board):
"""reverses each row of the board
"""
yield from (r[::-1] for r in rows(board))
def minor_diags(board):
yield from major_diags([*flip_lr(board)])
board = [
['x', 'x', 'o', 'x'],
['o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o'],
['x', 'o', 'o', 'x']
]
minor = {
('x',),
('x', 'o',),
('o', 'o', 'x',),
('x', 'o', 'x', 'x',),
('o', 'x', 'o',),
('o', 'o',),
('x',),
}
assert minor == {*minor_diags(board)}
4×4 Traversal#
With the code for the diagonals figured out, we can recreate our traversal function to walk around our board better:
def transpose(board):
yield from zip(*board)
def flip_lr(board):
yield from (r[::-1] for r in rows(board))
def minor_diags(board):
yield from major_diags([*flip_lr(board)])
def rows(board):
yield from (tuple(row) for row in board)
def columns(board):
yield from transpose(board)
def major_diags(board):
# above major diagonals
for offset in range(1, len(board)):
yield tuple(
board[i][i - offset] for i in range(offset)
)
# major diagonal
yield tuple(row[i] for i, row in enumerate(rows(board)))
# below diagonals
for offset in reversed(range(1, len(board))):
yield tuple(
board[i - offset][i] for i in range(offset)
)
def minor_diags(board):
yield from major_diags([*flip_lr(board)])
def traverse(board):
for trav in [rows, columns, major_diags, minor_diags]:
for i, group in enumerate(trav(board)):
yield trav, i, group
board = [
['x', 'x', '.', 'x'],
['o', '.', 'x', 'o'],
['o', 'x', 'x', 'x'],
['o', 'o', 'o', 'x']
]
print(
*(f'{trav.__name__: <8} {i}: {group}'
for trav, i, group in traverse(board)),
sep='\n',
)
rows 0: ('x', 'x', '.', 'x')
rows 1: ('o', '.', 'x', 'o')
rows 2: ('o', 'x', 'x', 'x')
rows 3: ('o', 'o', 'o', 'x')
columns 0: ('x', 'o', 'o', 'o')
columns 1: ('x', '.', 'x', 'o')
columns 2: ('.', 'x', 'x', 'o')
columns 3: ('x', 'o', 'x', 'x')
major_diags 0: ('x',)
major_diags 1: ('.', 'o')
major_diags 2: ('x', 'x', 'x')
major_diags 3: ('x', '.', 'x', 'x')
major_diags 4: ('o', 'x', 'o')
major_diags 5: ('o', 'o')
major_diags 6: ('o',)
minor_diags 0: ('x',)
minor_diags 1: ('x', 'o')
minor_diags 2: ('.', '.', 'o')
minor_diags 3: ('x', 'x', 'x', 'o')
minor_diags 4: ('o', 'x', 'o')
minor_diags 5: ('x', 'o')
minor_diags 6: ('x',)
Now we just need to detect winners when they are present:
from itertools import islice, tee
def nwise(iterable, n=2):
return zip(
*(islice(g, i, None) for i, g in enumerate(tee(iterable, n)))
)
def winner(line, ignore={'.'}):
uniq_line = set(line)
if len(uniq_line) == 1 and uniq_line != ignore:
return True, next(iter(uniq_line))
return False, None
def find_winners(board, size=3):
for trav, i, group in traverse(board):
if len(group) < size: continue
for offset, line in enumerate(nwise(group, n=size)):
won, pl = winner(line)
if won:
yield trav, i, offset, pl
board = [
['x', 'x', 'x', 'x'],
['o', '.', 'x', 'x'],
['o', 'x', 'x', 'x'],
['o', 'o', 'o', 'x']
]
for size in range(3, len(board)+1):
print(
'\N{box drawings light horizontal}'*40,
f'{size} in a line constitutes a win!',
*(f'{pl!r} won on {trav.__name__: <14} {i}+{offset}'
for trav, i, offset, pl in find_winners(board, size=size)),
sep='\n',
)
────────────────────────────────────────
3 in a line constitutes a win!
'x' won on rows 0+0
'x' won on rows 0+1
'x' won on rows 2+1
'o' won on rows 3+0
'o' won on columns 0+1
'x' won on columns 2+0
'x' won on columns 3+0
'x' won on columns 3+1
'x' won on major_diags 2+0
'x' won on minor_diags 3+0
────────────────────────────────────────
4 in a line constitutes a win!
'x' won on rows 0+0
'x' won on columns 3+0
Wrap-Up#
We may be able to justify the size parameter to be a part of the traverse function instead of find_winners. Regardless, I think we have solved what we set out to do.
There we have it! That’s my take on Tic-Tac-Toe. What did you think? Is there anything you would have done differently? We’d love to hear your ideas and thought process!
Let us know on our Discord server: https://discord.gg/ZhJPKYSfNp
Until next time!