python - 手动检查井字游戏状态的数量

Question

我事先知道完全生成的井字游戏树总共包含 255 168 种不同的游戏，但我想通过实现计算状态数的 python 程序来说服自己。

出于某种原因，我得到的结果太多（611 146）或（269 388）。我已经使用深度优先搜索算法实现了游戏树生成，该算法将新分支保存到打开列表并将探索分支保存到关闭列表。

这是我可以为这个问题生成的最简单的程序。

import copy

# Creates an empty board 
def create_board(): 
    return([[0, 0, 0], [0, 0, 0], [0, 0, 0]])

# Check for empty places on board 
def possibilities(board): 
    l = []     
    for i in range(len(board)): 
        for j in range(len(board)):               
            if board[i][j] == 0: 
                l.append((i, j)) 
    return(l) 

# Checks whether the player has three  
# of their marks in a horizontal row 
def row_win(board, player):
    for x in range(len(board)): 
        win = True        
        for y in range(len(board)):
            if board[x][y] != player: 
                win = False
                continue                
        if win == True: 
            return(win) 
    return(win) 

# Checks whether the player has three 
# of their marks in a vertical row 
def col_win(board, player): 
    for x in range(len(board)): 
        win = True          
        for y in range(len(board)): 
            if board[y][x] != player: 
                win = False
                continue               
        if win == True: 
            return(win) 
    return(win) 

# Checks whether the player has three 
# of their marks in a diagonal row 
def diag_win(board, player): 
    win = True    
    for x in range(len(board)): 
        if board[x][x] != player: 
            win = False
    return(win) 

# Evaluates whether there is 
# a winner or a tie  
def evaluate(board, counter): 
    winner = 0   
    for player in [1, 2]: 
        if (row_win(board, player) or col_win(board,player) or diag_win(board,player)):               
            winner = player
            counter += 1
    flat_board = [item for sublist in board for item in sublist]            
    if (flat_board.count(0) <= 0) and winner == 0: 
        winner = -1
        counter += 1
    return winner, counter

# Main function to count number of games 
def play_game():
    counter = 0
    initialized_board, first_player = create_board(), 1
    openlist = []
    closedlist = []
    openlist.append([initialized_board, first_player])
    while len(openlist) > 0:
        board, player = openlist.pop()
        winner, counter = evaluate(board, counter)
        closedlist.append(board)
        if winner != 0:
            winner = 0
            continue
        legal_moves = possibilities(board)
        for legal_move in legal_moves:
            newboard = copy.deepcopy(board)
            newboard[legal_move[0]][legal_move[1]] = player
            openlist.append([newboard, 3-player])

    print(len(closedlist))
    print(counter)

play_game()

首先，我认为最终计算封闭列表的长度就足够了，但我不再确定了。我还计算了终端状态的数量。在我看来，这两个数字都不正确。

标签： python

Answer 1

编辑 3：我将这部分移到答案的顶部，因为它可能会通过更正您的代码以更直接的方式回答您的问题。有关我对问题的解决方案，请参见下文

---

我可以在您的算法中指出的一个明显错误是您只考虑了获胜条件中 2 条对角线中的 1 条。也许如果你改变：

def diag_win(board, player): 
    win = True    
    for x in range(len(board)): 
        if board[x][x] != player: 
            win = False
    return(win) 

到我的代码中使用的东西：

def diag_win(board, player): 
    diag1 = []
    diag2 = []
    for i in range(0, len(board)):
        diag1.append(board[i][i])
        diag2.append(board[len(board) - i - 1][i])
    return all(tile == player for tile in diag1) or all(tile == player for tile in diag2)

...您的算法可以与此一起使用！

---

我对您的tictactoe谜语和原始答案的解决方案：

我还没有弄清楚你的代码有什么问题，但我对你的问题进行了破解并解决了它。我正在使用带有生成器的面向对象的方法，以便在浏览树时内存不会爆炸。我的方法是让树中的每个节点保存棋盘的状态，棋盘可以告诉您哪些动作是可能的，从而允许节点生成自己的子节点。也许你会觉得我的方法很有趣？代码如下，结果是 255168 所以我猜它是正确的。如果您的机器可以承受它，它应该能够扩展到任何板尺寸。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from copy import deepcopy


class GameIsFinishedError(Exception):
    pass


class NonEmptyTileError(Exception):
    pass


class OutOfBoundsError(Exception):
    pass


class Board:

    CROSS = "X"
    CIRCLE = "O"

    def __init__(self, board_size):
        self.board_size = board_size
        self.tiles = [[None for _ in range(0, self.board_size)] for _ in range(0, self.board_size)]
        self.moves = {self.CROSS: [], self.CIRCLE: []}
        self.turn = 1

    def play(self, x, y):
        if x >= self.board_size or y >= self.board_size:
            raise OutOfBoundsError()

        if self.game_has_ended:
            raise GameIsFinishedError()

        tile_value = self.CROSS if self.turn % 2 == 1 else self.CIRCLE

        if self.tiles[x][y] is not None:
            raise NonEmptyTileError(f"Tile ({x},{y}) is not empty")

        self.tiles[x][y] = tile_value
        self.moves[tile_value].append((x, y))
        self.turn += 1

    @property
    def board_is_full(self):
        return all(tile is not None for row in self.tiles for tile in row)

    @property
    def someone_won(self):
        # Get values in diagonals
        diag1 = []
        diag2 = []
        for i in range(0, self.board_size):
            diag1.append(self.tiles[i][i])
            diag2.append(self.tiles[self.board_size - i - 1][i])

        for player in (self.CIRCLE, self.CROSS):
            # Check rows
            for row in self.tiles:
                if all(tile == player for tile in row):
                    return player

            # Check columns
            for col in zip(*self.tiles):
                if all(tile == player for tile in col):
                    return player

            # Check diagonals
            if all(tile == player for tile in diag1) or all(tile == player for tile in diag2):
                return player

        return False

    @property
    def possible_moves(self):
        res = []
        for i, row in enumerate(self.tiles):
            for j, tile in enumerate(row):
                if tile is None:
                    res.append((i, j))
        return res

    @property
    def game_has_ended(self):
        return self.board_is_full or self.someone_won

    def print_board(self):
        for i, row in enumerate(self.tiles):
            row = [elem if elem is not None else " " for elem in row]
            row_str = " " + " | ".join(row) + " "
            print(row_str)
            if i != self.board_size - 1:
                print("-" * (self.board_size * 3) + "-" * (self.board_size - 1))
        print()

    def copy_board(self):
        return deepcopy(self)

###################################################################################################
class Node:
    def __init__(self, board, parent=None):
        self.board = board
        self.parent = parent

    def children(self):
        for x, y in self.board.possible_moves:
            new_board = self.board.copy_board()
            new_board.play(x, y)
            yield self.__class__(new_board, parent=self)

###################################################################################################
class Tree:

    UNIQUE_GAME_COUNTER = 0

    def __init__(self, root):
        self.root = root

    @classmethod
    def step(cls, node):

        if node.board.game_has_ended:
            cls.UNIQUE_GAME_COUNTER += 1
            return

        for child in node.children():
            cls.step(child)

    def browse(self):
        self.step(self.root)

###################################################################################################
#                                            MAIN                                                 #
###################################################################################################
if __name__ == '__main__':

    b = Board(3)
    root = Node(b)
    tree = Tree(root)
    tree.browse()
    print(tree.UNIQUE_GAME_COUNTER)

编辑：作为旁注，这个算法在你的记忆中很容易（因为在给定的时间它只保存当前探索分支的板的状态）但它是 CPU 密集型的。在我的机器上运行大约需要 1 分钟。如果您想探索更大的电路板，我建议您使用多线程。您可以轻松地为每个线程指定一个不同的起始节点，并在最后将结果相加。