如何选择一个好的Python列表数据结构来存储所有可能的Tic-Tac-Toe-gam

Question

我正在做一个python项目，在这个项目中，我生成每一个可能的tic-tac-toe游戏，然后根据这些游戏得出结论（即，为了赢得大多数游戏，什么是最好的第一步）。我有一个函数来生成一个可能的游戏，然后用这个游戏附加两个数组，如果游戏赢了，一个数组，每个游戏一个。当我附加数组并打印这些数组中的最后一个元素时，我得到了刚刚生成的游戏。但是，一旦函数完成，我检查数组，它们都被同一元素的倍数填充。我的代码如下：

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...")

正常的游戏应该是这样的：

^{pr2}$

但是，函数完成后，数组将填充：

[[None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [None, 0], [1, 1]]

我该怎么解决这个问题？在

Answer 1

创意：

我将存储游戏信息的数据格式更改为一个由两个元素组成的元组：

1. 第一个元素是一个包含玩家移动顺序的列表。我们不需要存储哪个玩家在哪个位置，因为顺序总是一样的：第一个玩家，然后第二个玩家，然后又是第一个玩家，依此类推。所以每个奇数元素索引都是第一个玩家的移动，第二个玩家的每个偶数元素索引。板从左到右和从上到下索引：

   [0][1][2]
   [3][4][5]
   [6][7][8]
   

   前4步的例子：

   ^{pr2}$

   假设X是第一个玩家，O是第二个玩家：

   [X][ ][ ]    [X][ ][O]    [X][ ][O]    [X][ ][O]
   [ ][ ][ ] -> [ ][ ][ ] -> [ ][ ][ ] -> [ ][O][ ]
   [ ][ ][ ]    [ ][ ][ ]    [ ][ ][X]    [ ][ ][X]
   

2. 第二个元素是编码为整数的游戏结果：0表示平局，1表示第一个玩家获胜，2表示第二个玩家获胜。

---

示例：

{{cd2>又假设第二个玩家是{cd2}。示例：

                                      [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()

输出：