时间戳

首页 > 解决方案 > 生成所有可能的井字棋棋盘位置

python - 生成所有可能的井字棋棋盘位置

问题描述

这有点类似于这个问题：Python 在“板”上生成所有可能的数字配置，但我正在尝试在 Python 中实现，我想包括生成的板，这些板只是部分完成。

在井字游戏中有 3^9 (19683) 个棋盘位置。

这是我生成每个板的代码，其中板数组的每个元素都是一个板：

boards = []
temp_boards = []

for i in range(0 , 19683) : 
    c = i
    temp_boards = []
    for ii in range(0 , 9) : 
        temp_boards.append(c % 3)
        c = c // 3
    boards.append(temp_boards)

我会错过任何职位吗？

标签： pythonalgorithm

解决方案

如果您考虑玩家轮流，当有人获胜时游戏停止，那么可能的棋盘将少于 X、O 和空白单元格的最大组合所建议的数量。您也不能计算填充了所有 X 或所有 Os 或任何组合的板，这些组合在 X 和 Os 的数量之间的差异大于 1。

您可以通过递归模拟从 X 开始并以 O 开始的移动来获得该数字：

axes = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]

def isWin(board):
    return any("".join(board[p] for p in axis) in ["XXX","OOO"] for axis in axes)

def validBoards(board="."*9,player=None):
    if player == None:
        yield board  # count the empty board
        for b in validBoards(board,player="X"): yield b # X goes 1st
        for b in validBoards(board,player="O"): yield b # O goes 1st
        return
    opponent = "XO"[player=="X"]
    for pos,cell in enumerate(board):
        if cell != ".": continue
        played = board[:pos]+player+board[pos+1:] # simulate move
        yield played                              # return the new state
        if isWin(played): continue                # stop game upon winning
        for nextBoard in validBoards(played,opponent):
            yield nextBoard # return boards for subsequent moves

输出：

distinctBoards = set(validBoards())  # only look at distinct board states

allStates = len(distinctBoards)
print(allStates)  # 8533 counting all intermediate states

winningStates = sum(isWin(b) for b in  distinctBoards)
print(winningStates) # 1884  (so 942 for a specific starting player)

filledStates  = sum(("." not in b) for b in distinctBoards)        
print(filledStates) #  156 states where all cells are filled 

finalStates  = sum(isWin(b) or ("." not in b) for b in distinctBoards)        
print(finalStates) #  1916 end of game states (win or draw) 

earlyWins = sum(isWin(b) and ("." in b) for b in distinctBoards)
print(earlyWins) # 1760 wins before filling the board

draws  = finalStates - winningStates        
print(draws) #  32 ways to end up in a draw 

lastWins = filledStates-draws
print(lastWins) # 124 wins on the 9th move (i.e filling the board)

fastWins = sum( isWin(b) and b.count(".") == 4 for b in distinctBoards)
print(fastWins) # 240 fastest wins by 1st player (in 3 moves)

fastCounters = sum( isWin(b) and b.count(".") == 3 for b in distinctBoards)
print(fastCounters) # 296 fastest wins by 2nd player (in 3 moves)

如果您需要更快的实现，这里是函数的优化版本，它只返回不同的状态并利用它来跳过移动序列树的整个分支：

def validBoards(board="."*9,player=None,states=None):
    if player == None:
        result  = {board}  # count the empty board
        result |= validBoards(board,player="X",states=set()) # X goes 1st
        result |= validBoards(board,player="O",states=set()) # O goes 1st
        return result
    opponent = "XO"[player=="X"]
    for pos,cell in enumerate(board):
        if cell != ".": continue
        played = board[:pos]+player+board[pos+1:] # simulate move
        if played in states : continue            # skip duplicate states
        states.add(played)                        # return the new state
        if isWin(played): continue                # stop game upon winning 
        validBoards(played,opponent,states)       # add subsequent moves 
    return states

推荐阅读