简述：
研究 MCTS 过程中， 需要用到树结构。 baidu google 了一番， 找不到自己能满足自己的库或代码参考，只好再造个*出来
我造的树用来下五子棋 和 围棋用的， 有其它不同的应用场合， 那就需要在此基础上改造了。
本树的特点：
1. 支持多子节点 （ 网络上很多代码都是二叉树，不符合我的需求 ）
2. 支持树的存储 和 读取， 网上很少看到。
正文：
下面按照 应用场景， 数据结构和接口 ， 代码， 三个部分 自上向下说明。
应用场景：
一： 画一个根节点， 再加三个叶子的树 （参考 Tree.demo1()）
data = ['{}'.format( random.random() * 10000 )]
self.addSubNodeToCur_Data( data )
self.moveUp();
data = ['{}'.format( random.random() * 10000 )]
self.addSubNodeToCur_Data( data )
self.moveUp();
data = ['{}'.format( random.random() * 10000 )]
self.addSubNodeToCur_Data( data )
self.save()
初始化出来的树，只有一个根节点 tree = Tree()
然后在根下面，加一个节点， 内容是 data ，必须是 list 结构， list 里的元素只能是 字符，数字， True/False , 不允许 object , list , ()
moveUp 是当前节点往上移动一层， 如果已经是根节点了，会返回False
addSubNodeToCur_Data(self, data, NodeId = 0, isMoveToSub = True ) 在当前节点下，增加一个节点，节点内容是 Data ; isMoveToSub 当前节点移到新增节点
NodeId 一般不需要设置， 如果你的树结构是清楚的时候， 知道NodeId 的情况下设置。
二： 保存树，读取树
self.load(self, filename = None) ， load 之后 ，生成树
self.save(self, filename = None)
默认文件名 ./data.npy 可指定文件名 ， .npy 结尾
三：生成棋谱树
该棋局， 只有 4个 落子点 ， [(0, 0), (0, 1), (1, 0), (1, 1)] ， 一个人下
根据数理分析， 会形成这样一棵树：
0 root_node 根节点
1 4 × node 第一步 节点数
2 3 x 4 x node 第二步节点数
3 2x 3x4xnode 第三步节点数
4 1x 2x3x4xnode 第四步节点数
下一局，形成的一个棋谱
# 下一局， 随机选一个点， 下满棋盘
def WzOne( tree ):
tree.reset() #让树当前节点回到根节点
avilAction = [(0, 0), (0, 1), (1, 0), (1, 1)] # 4个落子点
while( len(avilAction) >0 ): #无落子点
action = random.choice(avilAction) #随机一个落子点
avilAction.remove(action) data = list( action )
# 遍历当前前节点的子节点， 如果已经存在该落子点， 则跳到子节点
# 如果当前节点的子节点， 无该落子点， 则增加一个子节点
isExist = False
for node in tree.cur_Node.children :
if( node.getData() == data ):
isExist = True
tree.moveToNode_byNode( node )
break
if( isExist == False ):
tree.addSubNodeToCur_Data(data) pass
下100局，形成100局的棋谱
# 下100局， 拓展棋谱
def testWzTree():
'''
生成 落子树
'''
tree = Tree()
for i in range(100):
WzOne( tree ) tree.printTree()
tree.save() #读取树
print '------------------------------------------------'
tree2 = Tree()
tree2.load()
tree2.printTree()
pass
最多生成 24 个叶子（最低层）的树； 也就是 24个棋谱
三：生成10x10 的五子 对弈 棋谱树
理论最大棋谱数 100 x 98 x 96x 94 x ...... （不考虑五子成线） 貌似好几百亿
试验了一下 7 x7 对弈五子棋， 10000 局， 形成 195719 个节点的树
github :
https://github.com/rehylas/play_chess/blob/master/standTree/wuzi.py
待补充
数据结构和接口
本代码输出两个类：Node 和 Tree
节点保存的信息有两部分：
nodeInfo = [ nodeid, level, parentNodeid, [ node1,node2,node3 ] ]
data = [data1, data2,data3,data3 ] 随应用定义
Node 输出接口：
create
setData(Data)
setParent(Node)
addSubNode(Node)
getSubNodeList()
Tree 输出接口：
def __init__(self):
def reset(self):
def load(self, filename = None ):
def save(self, filename = None ):
def printTree(self):
def getRootNode(self):
def getCurNode(self):
def addSubNodeToCur_Node(self, subNode, isMoveToSub = True ):
def addSubNodeToCur_Data(self, data, NodeId = 0, isMoveToSub = True ):
def moveToNode(self,nodeId ):
def moveToNode_byNode(self, node ):
def serachNodeId(self, thisNode, nodeId):
def moveUp(self):
代码：
gitHub： https://github.com/rehylas/play_chess/blob/master/standTree/Tree.py
代码：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: hylas zhang import numpy as np;
import random ''' Node class data
data： []
nodeinfo： id, level, parentId, childrenIdList [ 0, 0, 0, [] ]
childrenIdList save to file : [1,2,3,4] ==> 1,2,3,4 export function：
create
setData(Data)
setParent(Node)
addSubNode(Node)
getSubNodeList() in function: ''' class Node():
def __init__(self, info=None, data=None, infodata = None ):
if( infodata != None ):
info = infodata[0:3] +[[]]
data = infodata[3:]
self.info = info
self.data = data
pass self.data = [''] #[ 0,0, '' ] #times, wins, values
if( data != None ):
self.data = data
self.nodeInfo=[ 0, 0 ,0, [] ] #Nodeid, level , parentId, childrenIdList
if( info != None ):
self.nodeInfo = info self.parent = None
self.children = []
pass def setData(self,data):
self.data = data def setParent(self, parentNode):
self.parent = parentNode def addChild(self, childNode ):
self.children += [ childNode ] def getSubNodeList(self):
return self.children def getDataInfo(self):
dataList = [self.nodeInfo[0],self.nodeInfo[1],self.nodeInfo[2]] +self.data
return dataList def getData(self):
return self.data def getInfo(self):
return self.nodeInfo def __repr__(self):
return "nodeInfo: {}, ".format(self.nodeInfo ) def __eq__(self, other):
selfVal = "{}".format(self.nodeInfo )
otherVal = "{}".format(other.nodeInfo) if hash(selfVal) == hash(otherVal):
return True
return False '''
Tree
export function：
1.create
2.getRootNode
3.getCurNode
4.reset（ 一般 回溯之后 ）
5.loadFile
6.saveFile
7.addNewNodeInCurNode 7.获取usb最优节点
8.增加新节点
9.移动当前节点 内部： ''' class Tree():
###### 输出
def __init__(self):
self.root_Node = Node()
self.cur_Node = self.root_Node
self.NodeCount = 1 # 节点+ 叶子数 + 1
pass def reset(self):
self.cur_Node = self.root_Node
pass def load(self, filename = None ):
if( filename == None ):
filename = './data.npy'
npData2 = np.load( filename )
lst2 = npData2.tolist()
for node in lst2:
info = node[0:3]
data = node[3:]
if( info[0] == 0 ):
continue
print 'want to add:'
print node if( info[2] == self.cur_Node.nodeInfo[0] ):
self.addSubNodeToCur_Data(data, NodeId = info[0] )
continue #self.cur_Node
count = 10
while( info[2] != self.cur_Node.nodeInfo[0] ) : ret = self.moveUp() if( ret == False ):
print 'error ......'
return continue self.addSubNodeToCur_Data(data, NodeId = info[0]) self.printTree()
pass def save(self, filename = None ):
if (filename == None):
filename = './data.npy' nodeLst = self.fetchAllNode()
dataList =[]
for node in nodeLst :
print node
dataList += [ node.getDataInfo() ]
# Node.
pass npData = np.array( dataList )
np.save(filename, npData ) '''
npData2 = np.load( './data.npy' )
lst2 = npData2.tolist()
print 'lst2:', lst2
''' def printTree(self):
nodeLst = self.fetchAllNode()
for node in nodeLst :
print node.getDataInfo()
pass def getRootNode(self):
return self.root_Node; def getCurNode(self):
return self.cur_Node; # nodeinfo： id, level, parentId, childrenIdList[0, 0, 0, []]
def addSubNodeToCur_Node(self, subNode, isMoveToSub = True ):
newNodeId = self.NodeCount
self.NodeCount += 1
self.cur_Node.children += [subNode]
self.cur_Node.nodeInfo[3] += [ newNodeId ] subNode.parent = self.cur_Node
subNode.nodeinfo[0] = newNodeId
subNode.nodeinfo[1] = self.cur_Node.nodeInfo[1] +1
subNode.nodeinfo[2] = self.cur_Node.nodeInfo[0]
subNode.nodeinfo[3] = []
if( isMoveToSub ):
self.cur_Node = subNode pass def addSubNodeToCur_Data(self, data, NodeId = 0, isMoveToSub = True ):
subNode = Node(data=data) if(NodeId == 0 ):
newNodeId = self.NodeCount
else:
newNodeId = NodeId
self.NodeCount += 1
self.cur_Node.children += [subNode]
self.cur_Node.nodeInfo[3] += [ newNodeId ] subNode.parent = self.cur_Node subNode.nodeInfo[0] = newNodeId
subNode.nodeInfo[1] = self.cur_Node.nodeInfo[1] +1
subNode.nodeInfo[2] = self.cur_Node.nodeInfo[0]
subNode.nodeInfo[3] = []
#print 'addSubNodeToCur_Data, now in :', self.cur_Node.nodeInfo[0]
if( isMoveToSub ):
self.cur_Node = subNode #print 'addSubNodeToCur_Data, now in :', self.cur_Node.nodeInfo[0] def moveToNode(self,nodeId ):
node = self.serachNodeId( self.root_Node, nodeId)
if (node!= None):
self.cur_Node = node
return node
else:
return None
pass def moveToNode_byNode(self, node ):
self.cur_Node = node
pass def fetchAllNode(self):
return self.touchAllNode( self.getRootNode() )
pass # in function
def touchAllNode(self, thisNode):
allNode = [ thisNode ]
for node in thisNode.children :
allNode += self.touchAllNode( node ) return allNode def serachNodeId(self, thisNode, nodeId):
if( thisNode.nodeInfo[0] == nodeId ):
return thisNode
else:
for node in thisNode.children :
ret = self.serachNodeId(node , nodeId )
if( ret != None ):
return ret return None ###### 内部函数
def moveUp(self):
if( self.cur_Node.nodeInfo[0] == 0 ):
print 'moveUp error'
return False self.cur_Node = self.cur_Node.parent;
return True ######## test
def demo1(self):
data = ['{}'.format( random.random() * 10000 )]
self.addSubNodeToCur_Data( data ) self.moveUp();
data = ['{}'.format( random.random() * 10000 )]
self.addSubNodeToCur_Data( data ) self.save()
pass def deom2(self):
self.load() # 下100局， 拓展棋谱
def testWzTree():
'''
生成 落子树
'''
tree = Tree()
for i in range(100):
WzOne( tree ) tree.printTree()
tree.save() #读取树
print '------------------------------------------------'
tree2 = Tree()
tree2.load()
tree2.printTree()
pass # 下一局， 随机选一个点， 下满棋盘
def WzOne( tree ):
tree.reset() #让树当前节点回到根节点
avilAction = [(0, 0), (0, 1), (1, 0), (1, 1)] # 4个落子点
while( len(avilAction) >0 ): #无落子点
action = random.choice(avilAction) #随机一个落子点
avilAction.remove(action) data = list( action )
# 遍历当前前节点的子节点， 如果已经存在该落子点， 则跳到子节点
# 如果当前节点的子节点， 无该落子点， 则增加一个子节点
isExist = False
for node in tree.cur_Node.children :
if( node.getData() == data ):
isExist = True
tree.moveToNode_byNode( node )
break
if( isExist == False ):
tree.addSubNodeToCur_Data(data) pass def test():
testWzTree()
return tree = Tree()
tree.test()
return if __name__ == "__main__":
test()