我试图将蒙特卡洛算法应用于二叉树，但我的印象是算法中有错误，因为它返回了我的默认值。
这是树的图形结构：
10
/ \
6 14
/ \ / \
5 8 11 18
您可以在 GitHub 上找到代码，但这里是：
# Attempt to apply a Nested Monte Carlo Algorithm to binary trees
from random import *
import numpy as np
MaxPlayoutLength = 20 # what ?
# Class for construct the nodes of the tree. (Subtrees)
class Node:
def __init__(self, key, parent_node = None):
self.left = None
self.right = None
self.key = key
if parent_node == None:
self.parent = self
else:
self.parent = parent_node
# Class with the structure of the tree.
# I'm not sure if this Tree is balanced.
class Tree:
def __init__(self):
self.root = None
# Insert a single element
def insert(self, x):
if(self.root == None):
self.root = Node(x)
else:
self._insert(x, self.root)
# place it at the right palce
def _insert(self, x, node):
if(x < node.key):
if(node.left == None):
node.left = Node(x, node)
else:
self._insert(x, node.left)
else:
if(node.right == None):
node.right = Node(x, node)
else:
self._insert(x, node.right)
# Given a element, return a node in the tree with key x.
def find(self, x):
if(self.root == None):
return None
else:
return self._find(x, self.root)
def _find(self, x, node):
if(x == node.key):
return node
elif(x < node.key):
if(node.left == None):
return None
else:
return self._find(x, node.left)
elif(x > node.key):
if(node.right == None):
return None
else:
return self._find(x, node.right)
# Given a node, return the node in the tree with the next largest element.
def next(self, node):
if node.right != None:
return self._left_descendant(node.right)
else:
return self._right_ancestor(node)
def _left_descendant(self, node):
if node.left == None:
return node
else:
return self._left_descendant(node.left)
def _right_ancestor(self, node):
if node.key <= node.parent.key:
return node.parent
else:
return self._right_ancestor(node.parent)
# Delete an element of the tree
def delete(self, x):
node = self.find(x)
if node == None:
print(x, "isn't in the tree")
else:
if node.right == None:
if node.left == None:
if node.key < node.parent.key:
node.parent.left = None
del node # Clean garbage
else:
node.parent.right = None
del Node # Clean garbage
else:
node.key = node.left.key
node.left = None
else:
x = self.next(node)
node.key = x.key
x = None
# a tree with a selected node at a given time
class Board:
'''a Board is a tree with a node selected which gives a score'''
def __init__(self, btree, node):
self.root = node
self.root.left = node.left
self.root.right = node.right
# length = NULL; //TO-DO : number of nodes which have leaves BUT how to count them ?
moves = np.zeros(2)
if(node.left != None):
self.moves[0] = node.left #/DONE? array of the left and right positions from current state //node *left; and node *right;
self.moves[1] = node.right
score = node.key
def legalMoves(self, moves):
if(moves != None):
return 2
else:
return 0
def terminal(self):
if(self.root.left == None):
print("board terminal")
print(self.root.left)
return True
else:
return False
def score(self):
return node.key
def getLegalMoves(self,node):
if(node.left != None):
self.moves[0] = node.left
self.moves[1] = node.right
return moves
# length = NULL; //TO-DO : number of nodes which have leaves BUT how to count them ?
def playout(board):
moves[2] # shoudln't we get them from the board ?
while(True):
nb = board.legalMoves(self.moves)
if((nb == 0) or board.terminal()):
return board.score()
n = random.randint(0, nb) # chose a number between 0 and the number of legal moves
board.play(moves[n]) # play a random move
if(board.length >= MaxPlayoutLength -20):
return 0
bestScoreNested = -9999
DBL_MAX = -9999
arraySize = 10
lengthBestRollout = np.zeros(10) # array of size 10
scoreBestRollout = np.zeros(10) # array of size 10
bestRollout =np.zeros((10,MaxPlayoutLength)) # 2 dimensional array of size 10*MaxPlayoutLength
def nested(board, n):
'''Nested Monte Carlo algorithm
a general name for a broad class of algorithms that use random sampling to obtain numerical results.
It is used to solve statistical problems by simulation.'''
nbMoves = 0
moves = np.zeros(2)
lengthBestRollout[n] -1
scoreBestRollout[n] - DBL_MAX
res = -DBL_MAX
while(True):
# if it's over we've reached the bottom of the tree
if(board.terminal()):
return 0.0
nbMoves = board.legalMoves(moves) # moves is empty here
# otherwise
for i in range(0,nbMoves):
b = board
b.play(moves[i])
if(n==1):
playout(board)
else:
nested (board, n-1)
score = board.score()
if(score > scoreBestRollout [n]):
scoreBestRollout [n] = score
lengthBestRollout [n] = board.length
for k in range(0,board.length):
bestRollout[n][k]=board.rollout[k]
if(n>3):
for i in range(0,t<n-1):
print("n =", n,"progress =", board.length, "score =", scoreBestRollout [n])
depth = 0
# board.print(stderr) # what
print("")
bestBoard = board
if ((n > 1) and (score > bestScoreNested)):
bestScoreNested = score
print("best score = ", score)
print("")
bestBoard = board
board.play(bestRollout[n][board.length])
return 0.0
if __name__ == "__main__":
# tests
t = Tree()
t.insert(5)
t.insert(6)
t.insert(8)
t.insert(10)
t.insert(11)
t.insert(14)
t.insert(18)
b = Board(t,Node(5))
score = nested(b,3)
print("the algorithm score is ",score)
# Remember: Find method return the node object.
# To return a number use t.find(nº).key
# But it will cause an error if the number is not in the tree.
问题是，当我尝试运行此代码时，它会返回：
$ python3 main.py
board terminal
None
the algorithm score is 0.0
这意味着它没有正确开始：从一开始我们就直接通过终端状态而无法启动第一个节点。
# if it's over we've reached the bottom of the tree
if(board.terminal()):
return 0.0
nbMoves = board.legalMoves(moves)