为了方便其他人帮助我， 我将所有代码都放在这里https://pastebin.com/WENzM41k 它将从 2 个代理相互竞争开始。
我正在尝试实现蒙特卡洛树搜索以在 Python 中玩 9 板井字游戏。游戏规则类似于常规井字游戏，但有 9 个 3x3 子板。最后一块的放置位置决定了放置你的一块的子板。这有点像终极井字游戏，但如果其中一个子板获胜，则游戏结束。
我正在尝试学习 MCTS，我在这里找到了一些代码：http: //mcts.ai/code/python.html
我在网站上使用了节点类和 UCT 类，并添加了我的 9 板井字游戏状态类和一些其他代码。所有代码都在这里：
from math import log, sqrt
import random
import numpy as np
from copy import deepcopy
class BigGameState:
def __init__(self):
self.board = np.zeros((10, 10), dtype="int8")
self.curr = 1
self.playerJustMoved = 2 # At the root pretend the player just moved is player 2 - player 1 has the first move
def Clone(self):
""" Create a deep clone of this game state.
"""
st = BigGameState()
st.playerJustMoved = self.playerJustMoved
st.curr = self.curr
st.board = deepcopy(self.board)
return st
def DoMove(self, move):
""" Update a state by carrying out the given move.
Must update playerJustMoved.
"""
self.playerJustMoved = 3 - self.playerJustMoved
if move >= 1 and move <= 9 and move == int(move) and self.board[self.curr][move] == 0:
self.board[self.curr][move] = self.playerJustMoved
self.curr = move
def GetMoves(self):
""" Get all possible moves from this state.
"""
return [i for i in range(1, 10) if self.board[self.curr][i] == 0]
def GetResult(self, playerjm):
""" Get the game result from the viewpoint of playerjm.
"""
for bo in self.board:
for (x,y,z) in [(1,2,3),(4,5,6),(7,8,9),(1,4,7),(2,5,8),(3,6,9),(1,5,9),(3,5,7)]:
if bo[x] == [y] == bo[z]:
if bo[x] == playerjm:
return 1.0
else:
return 0.0
if self.GetMoves() == []: return 0.5 # draw
def drawboard(self):
print_board_row(self.board, 1, 2, 3, 1, 2, 3)
print_board_row(self.board, 1, 2, 3, 4, 5, 6)
print_board_row(self.board, 1, 2, 3, 7, 8, 9)
print(" ------+-------+------")
print_board_row(self.board, 4, 5, 6, 1, 2, 3)
print_board_row(self.board, 4, 5, 6, 4, 5, 6)
print_board_row(self.board, 4, 5, 6, 7, 8, 9)
print(" ------+-------+------")
print_board_row(self.board, 7, 8, 9, 1, 2, 3)
print_board_row(self.board, 7, 8, 9, 4, 5, 6)
print_board_row(self.board, 7, 8, 9, 7, 8, 9)
print()
def print_board_row(board, a, b, c, i, j, k):
# The marking script doesn't seem to like this either, so just take it out to submit
print("", board[a][i], board[a][j], board[a][k], end = " | ")
print(board[b][i], board[b][j], board[b][k], end = " | ")
print(board[c][i], board[c][j], board[c][k])
class Node:
""" A node in the game tree. Note wins is always from the viewpoint of playerJustMoved.
Crashes if state not specified.
"""
def __init__(self, move = None, parent = None, state = None):
self.move = move # the move that got us to this node - "None" for the root node
self.parentNode = parent # "None" for the root node
self.childNodes = []
self.wins = 0
self.visits = 0
self.untriedMoves = state.GetMoves() # future child nodes
self.playerJustMoved = state.playerJustMoved # the only part of the state that the Node needs later
def UCTSelectChild(self):
""" Use the UCB1 formula to select a child node. Often a constant UCTK is applied so we have
lambda c: c.wins/c.visits + UCTK * sqrt(2*log(self.visits)/c.visits to vary the amount of
exploration versus exploitation.
"""
s = sorted(self.childNodes, key = lambda c: c.wins/c.visits + 0.2 * sqrt(2*log(self.visits)/c.visits))[-1]
return s
def AddChild(self, m, s):
""" Remove m from untriedMoves and add a new child node for this move.
Return the added child node
"""
n = Node(move = m, parent = self, state = s)
self.untriedMoves.remove(m)
self.childNodes.append(n)
return n
def Update(self, result):
""" Update this node - one additional visit and result additional wins. result must be from the viewpoint of playerJustmoved.
"""
self.visits += 1
self.wins += result
def __repr__(self):
return "[M:" + str(self.move) + " W/V:" + str(self.wins) + "/" + str(self.visits) + " U:" + str(self.untriedMoves) + "]"
def TreeToString(self, indent):
s = self.IndentString(indent) + str(self)
for c in self.childNodes:
s += c.TreeToString(indent+1)
return s
def IndentString(self,indent):
s = "\n"
for i in range (1,indent+1):
s += "| "
return s
def ChildrenToString(self):
s = ""
for c in self.childNodes:
s += str(c) + "\n"
return s
def UCT(rootstate, itermax, verbose = False):
""" Conduct a UCT search for itermax iterations starting from rootstate.
Return the best move from the rootstate.
Assumes 2 alternating players (player 1 starts), with game results in the range [0.0, 1.0]."""
rootnode = Node(state = rootstate)
for i in range(itermax):
node = rootnode
state = rootstate.Clone()
# Select
while node.untriedMoves == [] and node.childNodes != []: # node is fully expanded and non-terminal
node = node.UCTSelectChild()
state.DoMove(node.move)
# Expand
if node.untriedMoves != []: # if we can expand (i.e. state/node is non-terminal)
m = random.choice(node.untriedMoves)
state.DoMove(m)
node = node.AddChild(m,state) # add child and descend tree
# Rollout - this can often be made orders of magnitude quicker using a state.GetRandomMove() function
while state.GetMoves() != []: # while state is non-terminal
state.DoMove(random.choice(state.GetMoves()))
# Backpropagate
while node != None: # backpropagate from the expanded node and work back to the root node
node.Update(state.GetResult(node.playerJustMoved)) # state is terminal. Update node with result from POV of node.playerJustMoved
node = node.parentNode
# Output some information about the tree - can be omitted
if (verbose): print(rootnode.TreeToString(0))
else: print(rootnode.ChildrenToString())
return sorted(rootnode.childNodes, key = lambda c: c.visits)[-1].move # return the move that was most visited
def UCTPlayGame():
""" Play a sample game between two UCT players where each player gets a different number
of UCT iterations (= simulations = tree nodes).
"""
state = BigGameState() # uncomment to play OXO
while (state.GetMoves() != []):
state.drawboard()
m = UCT(rootstate = state, itermax = 1000, verbose = False) # play with values for itermax and verbose = True
print("Best Move: " + str(m) + "\n")
state.DoMove(m)
if state.GetResult(state.playerJustMoved) == 1.0:
print("Player " + str(state.playerJustMoved) + " wins!")
elif state.GetResult(state.playerJustMoved) == 0.0:
print("Player " + str(3 - state.playerJustMoved) + " wins!")
else: print("Nobody wins!")
if __name__ == "__main__":
""" Play a single game to the end using UCT for both players.
"""
UCTPlayGame()
运行代码，它将在 2 个代理相互竞争时启动。但是，代理不能很好地玩游戏。糟糕的比赛是不能接受的。例如，如果 ai 在子棋盘中连续获得 2，并且再次轮到他，则他不会下获胜棋步。我应该从哪里开始改进以及如何改进？我试图更改 Node 类和 UCT 类的代码，但没有任何效果。
更新：如果棋盘处于以下状态，则轮到我的 AI（打 X）在棋盘 8（第三排中间子棋盘）上棋。我应该编写特定的代码让 AI 不玩 1 或 5（因为那样对手会赢）还是应该让 AI 来决定。我尝试编写代码告诉 AI，但这样我必须遍历所有子板。
--O|---|---
-O-|---|---
---|---|---
-----------
---|-O-|---
---|-O-|---
---|---|---
-----------
---|---|---
---|---|---
---|---|---