pythonlistdata-structurestic-tac-toe2d-games
How to choose a good Python list data structure to store every possible Tic Tac Toe game
I am working on a python project where I generate every possible tic-tac-toe game, and then draw conclusions, based on those games (ie. what is the best first move, in order to win the most games). I have a function to generate a possible game, then append two arrays with that game, one if the game is winning, and one for every single game. When I append the arrays, and print the last element in those arrays, I get the game that was just generated. However, once the function finished, and I check the arrays, they are all filled with multiples of the same element. My code is below:
print("running...")
allGames = []
winningGames = []
winningFirstMoves = [0] * 9
wins = {
"top horizontal": 0,
"middle horizontal": 0,
"bottom horizontal": 0,
"left vertical": 0,
"middle vertical": 0,
"right vertical": 0,
"backward diagonal": 0,
"forward diagonal": 0
}
def checkFirstMove():
print("checking winning first moves...")
global winningGames
global winningFirstMoves
for game in winningGames:
print(game) #this line is only here to test, I know it slows it down
for move in range(len(game)):
if (game[move][1] == 1):
winningFirstMoves[move] += 1
def checkWin(gameToCheck):
if (gameToCheck[0][0] == gameToCheck[1][0] == gameToCheck[2][0] and gameToCheck[0][0] != 10):
wins["top horizontal"] += 1
return "top horizontal"
elif (gameToCheck[3][0] == gameToCheck[4][0] == gameToCheck[5][0] and gameToCheck[3][0] != 10):
wins["middle horizontal"] += 1
return "middle horizontal"
elif (gameToCheck[6][0] == gameToCheck[7][0] == gameToCheck[8][0] and gameToCheck[6][0] != 10):
wins["bottom horizontal"] += 1
return "bottom horizontal"
elif (gameToCheck[0][0] == gameToCheck[3][0] == gameToCheck[6][0] and gameToCheck[0][0] != 10):
wins["left vertical"] += 1
return "left vertical"
elif (gameToCheck[1][0] == gameToCheck[4][0] == gameToCheck[7][0] and gameToCheck[1][0] != 10):
wins["middle vertical"] += 1
return "middle vertical"
elif (gameToCheck[2][0] == gameToCheck[5][0] == gameToCheck[8][0] and gameToCheck[2][0] != 10):
wins["right vertical"] += 1
return "right vertical"
elif (gameToCheck[0][0] == gameToCheck[4][0] == gameToCheck[8][0] and gameToCheck[0][0] != 10):
wins["backward diagonal"] += 1
return "backward diagonal"
elif (gameToCheck[2][0] == gameToCheck[4][0] == gameToCheck[6][0] and gameToCheck[2][0] != 10):
wins["forward diagonal"] += 1
return "forward diagonal"
else: return False
def cleanGame(gameToClean, moveNumber):
for j in range(9):
if (gameToClean[j][1] >= moveNumber):
gameToClean[j] = [None, 0]
def generateGames():
global allGames
global winningGames
currentGame= [[None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0]]
for a in range(9):
if (a == 0):
print("generating games.", end="")
elif (a == 8):
print(".")
else:
print(".", end="")
cleanGame(currentGame, 1)
currentGame[a] = [1, 1]
for b in range(9):
cleanGame(currentGame, 2)
if (currentGame[b] == [None, 0]):
currentGame[b] = [0, 2]
for c in range(9):
cleanGame(currentGame, 3)
if (currentGame[c] == [None, 0]):
currentGame[c] = [1, 3]
for d in range(9):
cleanGame(currentGame, 4)
if (currentGame[d] == [None, 0]):
currentGame[d] = [0, 4]
for e in range(9):
cleanGame(currentGame, 5)
if (currentGame[e] == [None, 0]):
currentGame[e] = [1, 5]
if (checkWin(currentGame) != False):
winningGames.append(currentGame)
allGames.append(currentGame)
else:
for f in range(9):
cleanGame(currentGame, 6)
if (currentGame[f] == [None, 0]):
currentGame[f] = [0, 6]
if (checkWin(currentGame) != False):
winningGames.append(currentGame)
allGames.append(currentGame)
else:
for g in range(9):
cleanGame(currentGame, 7)
if (currentGame[g] == [None, 0]):
currentGame[g] = [1, 7]
if (checkWin(currentGame) != False):
winningGames.append(currentGame)
allGames.append(currentGame)
else:
for h in range(9):
cleanGame(currentGame, 8)
if (currentGame[h] == [None, 0]):
currentGame[h] = [0, 8]
if (checkWin(currentGame) != False):
winningGames.append(currentGame)
allGames.append(currentGame)
else:
for i in range(9):
cleanGame(currentGame, 9)
if (currentGame[i] == [None, 0]):
currentGame[i] = [1, 9]
allGames.append(currentGame)
if (checkWin(currentGame) != False):
winningGames.append(currentGame)
generateGames()
print("Number of Possible Games:", len(allGames))
print("Number of Winning Games:", len(winningGames))
checkFirstMove()
print(winningFirstMoves)
print("completed...")
A normal game would look something like this:
[[1, 1], [0, 2], [None, 0], [1, 3], [0, 4], [0, 6], [1, 7], [None, 0], [1, 5]]
However after the function completes, the arrays are filled with:
[[None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [1, 1]]
How can I fix this?
Solution
Idea:
I changed the format of the data which stores the game information to a tuple which consists of two elements:
The first element is a list which contains the sequence of player moves. We don't need to store which player is at which position because the order is always the same: first player, then second player, then first player again, and so on. So every odd element index is a move from the first player, every even element index from the second player. The board is indexed from left to right and top to bottom:
[0][1][2] [3][4][5] [6][7][8]Example for some first 4 moves:
[0, 2, 8, 4]Assuming
Xis the first player andOis the second player:[X][ ][ ] [X][ ][O] [X][ ][O] [X][ ][O] [ ][ ][ ] -> [ ][ ][ ] -> [ ][ ][ ] -> [ ][O][ ] [ ][ ][ ] [ ][ ][ ] [ ][ ][X] [ ][ ][X]The second element is the game outcome encoded as an integer:
0for draw,1for first player win,2for second player win.
Example:
Again, assuming X is the first player and O is the second player. Examples:
[X][O][X]
([0, 1, 2, 3, 4, 5, 6], 1) -> [O][X][O] -> First player won
[X][ ][ ]
[X][O][X]
([0, 1, 2, 3, 8, 7, 6, 4], 2) -> [O][O][ ] -> Second player won
[X][O][X]
[X][O][X]
([0, 1, 3, 8, 2, 6, 7, 4, 5], 0) -> [X][O][X] -> Draw
[O][X][O]
Implementation:
def draw_board(board):
template = ("[{}]" * 3 + "\n") * 3
print(template.format(*board))
def has_winner(sequence):
board = [" "] * 9
for n, move in enumerate(sequence):
board[move] = "X" if n % 2 == 0 else "O"
#draw_board(board)
tests = [
board[0] == board[1] == board[2] != " ",
board[3] == board[4] == board[5] != " ",
board[6] == board[7] == board[8] != " ",
board[0] == board[3] == board[6] != " ",
board[1] == board[4] == board[7] != " ",
board[2] == board[5] == board[8] != " ",
board[0] == board[4] == board[8] != " ",
board[2] == board[4] == board[6] != " ",
]
return any(tests)
def no_moves_left(sequence):
return len(sequence) == 9
def generate_games(sequence):
if has_winner(sequence):
winner = 2 - len(sequence) % 2
return [(sequence, winner)]
if no_moves_left(sequence):
return [(sequence, 0)]
games = []
open_spaces = [i for i in range(9) if i not in sequence]
for new_move in open_spaces:
new_sequence = sequence.copy()
new_sequence.append(new_move)
new_games = generate_games(new_sequence)
games.extend(new_games)
return games
games = generate_games([])
This implementation is definitely not fully optimized! However, I think it's fast enough while still maintaining a simple code structure.
Minimal statistics:
statistics = [[0] * 9 for _ in range(3)]
for sequence, outcome in games:
statistics[outcome][sequence[0]] += 1
print(*statistics, sep="\n")
Output:
[5184, 5184, 5184, 5184, 4608, 5184, 5184, 5184, 5184]
[14652, 14232, 14652, 14232, 15648, 14232, 14652, 14232, 14652]
[7896, 10176, 7896, 10176, 5616, 10176, 7896, 10176, 7896]
Plotting:
import matplotlib.pyplot as plt
import numpy as np
colors = "#6bc86b", "#5a9bd3", "#ed7d33"
labels = "Draw", "First player wins", "Second player wins"
explode = 0.05, 0.05, 0.05
data = list(map(sum, statistics))
plt.pie(data, colors=colors, labels=labels, explode=explode,
autopct="%1.1f%%", shadow=True)
plt.axis("equal")
plt.title("Outcome for all {} possible Tic-tac-toe games".format(sum(data)))
plt.show()
plt.close()
colors = "#6bc86b", "#5a9bd3", "#ed7d33"
labels = "Draw", "Win", "Lose"
width = 0.3
for i, (data, color, label) in enumerate(zip(statistics, colors, labels)):
index = [j + i * width for j in range(9)]
plt.bar(index, data, width, color=color, label=label)
plt.xlabel("Space of the first move")
plt.ylabel("Number of games")
plt.title("Outcome depending on first player's first move")
plt.xticks([i + width for i in range(9)])
plt.gca().set_xticklabels(map(str, range(9)))
plt.legend()
plt.tight_layout()
plt.show()
plt.close()
Output:
