如何选择一个好的 Python 列表数据结构来存储每一个可能的井字游戏
How to choose a good Python list data structure to store every possible Tic Tac Toe game
我正在做一个 python 项目，我会生成所有可能的井字游戏，然后根据这些游戏得出结论（即最好的第一步是什么，以便赢得最多的比赛）。我有一个函数可以生成一个可能的游戏，然后在该游戏中附加两个数组，一个用于游戏获胜，一个用于每场游戏。当我附加数组并打印这些数组中的最后一个元素时，我得到了刚刚生成的游戏。然而，一旦函数完成，我检查了数组，它们都充满了相同元素的倍数。我的代码如下：
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...")
一个普通的游戏看起来像这样：
[[1, 1], [0, 2], [None, 0], [1, 3], [0, 4], [0, 6], [1, 7], [None, 0], [1, 5]]
但是在函数完成后，数组中填充了：
[[None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [1, 1]]
我该如何解决这个问题？
想法：
我将存储游戏信息的数据格式更改为由两个元素组成的元组：
第一个元素是一个包含玩家移动顺序的列表。我们不需要存储哪个玩家在哪个位置，因为顺序始终相同：第一个玩家，然后是第二个玩家，然后是第一个玩家，依此类推。所以每个奇数元素索引都是来自第一个玩家的移动，每个偶数元素索引来自第二个玩家。该板的索引从左到右，从上到下：
[0][1][2]
[3][4][5]
[6][7][8]
前 4 步的示例：
[0, 2, 8, 4]
假设X是第一个玩家，O是第二个玩家：
[X][ ][ ] [X][ ][O] [X][ ][O] [X][ ][O]
[ ][ ][ ] -> [ ][ ][ ] -> [ ][ ][ ] -> [ ][O][ ]
[ ][ ][ ] [ ][ ][ ] [ ][ ][X] [ ][ ][X]
第二个元素是编码为整数的游戏结果：0表示平局，1表示第一位玩家获胜，2表示第二位玩家获胜。
示例：
同样，假设 X 是第一个玩家，O 是第二个玩家。示例：
[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]
实施：
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([])
这个实现绝对没有完全优化！但是，我认为它足够快，同时仍然保持简单的代码结构。
最少的统计数据：
statistics = [[0] * 9 for _ in range(3)]
for sequence, outcome in games:
statistics[outcome][sequence[0]] += 1
print(*statistics, sep="\n")
输出：
[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]
绘图：
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()
输出：
我正在做一个 python 项目，我会生成所有可能的井字游戏，然后根据这些游戏得出结论（即最好的第一步是什么，以便赢得最多的比赛）。我有一个函数可以生成一个可能的游戏，然后在该游戏中附加两个数组，一个用于游戏获胜，一个用于每场游戏。当我附加数组并打印这些数组中的最后一个元素时，我得到了刚刚生成的游戏。然而，一旦函数完成，我检查了数组，它们都充满了相同元素的倍数。我的代码如下：
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...")
一个普通的游戏看起来像这样：
[[1, 1], [0, 2], [None, 0], [1, 3], [0, 4], [0, 6], [1, 7], [None, 0], [1, 5]]
但是在函数完成后，数组中填充了：
[[None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [1, 1]]
我该如何解决这个问题？
想法：
我将存储游戏信息的数据格式更改为由两个元素组成的元组：
第一个元素是一个包含玩家移动顺序的列表。我们不需要存储哪个玩家在哪个位置，因为顺序始终相同：第一个玩家，然后是第二个玩家，然后是第一个玩家，依此类推。所以每个奇数元素索引都是来自第一个玩家的移动，每个偶数元素索引来自第二个玩家。该板的索引从左到右，从上到下：
[0][1][2] [3][4][5] [6][7][8]前 4 步的示例：
[0, 2, 8, 4]假设
X是第一个玩家，O是第二个玩家：[X][ ][ ] [X][ ][O] [X][ ][O] [X][ ][O] [ ][ ][ ] -> [ ][ ][ ] -> [ ][ ][ ] -> [ ][O][ ] [ ][ ][ ] [ ][ ][ ] [ ][ ][X] [ ][ ][X]第二个元素是编码为整数的游戏结果：
0表示平局，1表示第一位玩家获胜，2表示第二位玩家获胜。
示例：
同样，假设 X 是第一个玩家，O 是第二个玩家。示例：
[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]
实施：
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([])
这个实现绝对没有完全优化！但是，我认为它足够快，同时仍然保持简单的代码结构。
最少的统计数据：
statistics = [[0] * 9 for _ in range(3)]
for sequence, outcome in games:
statistics[outcome][sequence[0]] += 1
print(*statistics, sep="\n")
输出：
[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]
绘图：
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()
输出：