Как выбрать хорошую структуру данных списка Python для хранения всех возможных игр Tic Tac Toe

Question

Я работаю над проектом на 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]]

Как я могу это исправить?

Answer 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]
   

2. Второй элемент - результат игры, закодированный в виде целого числа: 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()

Выход: