这里头歌平台上两题都能过。由于本人的python非常渣，代码可能有点繁琐，没有体现python的简洁，可以改进的地方自行改造
MinMax算法对弈游戏时，假定两人都足够聪明，下一步都是对自己最有益、对对手最坏。那么针对这种情况，在A要下下一步时，存在一个针对A的对局势的判别函数，A肯定会向函数值大的下，而对手B势必会下在函数值下的地方。
1、题目描述给出一个井字棋的棋盘状态，下一步为‘x’开始走步，给出‘x’下一步最佳走步列表。
2、踩坑- 首先这里的’x’和‘o’都是小写
- 其次出现无法胜利（根节点无法得到1），答案应该为空集。
- 最后个人走的一点小坑：那就是建立节点的时候没有设置children为空列表，也就是
GameNode(map, val=0, deepID=0, parent=None, children=[])
递归建树，同时在建树过程中调用minmax中min_value和max_value函数求出每个节点的value值。get_value函数主要针对叶子节点（没有子节点的节点）求值（也就是判断谁赢的问题）。is_terminal函数主要时判断是否为叶子节点（也就是下满了和出现三子连线的情况）。
4、 测试主函数自己可以在钟意的编译器里将头歌代码写好后加上下面这段代码，然后就可以调试了
（ps：一定要用头歌的原题代码框架）
if __name__ == '__main__':
# 读取棋盘状态，下一步执 x
map = [['x','o','x','\r'],['x','o','o','\r'],['_','_','_','\r']]
# 创建一个根结点
root = GameNode(map, val=0, deepID=0, parent=None, children=[])
# 创建一颗博弈树
game_tree = GameTree(root)
game_tree.buildTree(game_tree.root)
# 创建一个MinMax算法解决方案的对象
min_max = MinMax(game_tree)
# 调用MinMax算法，获取最优行动
best_move = min_max.minmax(game_tree.root)
# 打印最优行动
for id_, move in enumerate(sorted(best_move)):
print('best move way:')
for i in range(3):
for j in range(3):
print(move[i][j])
print('')
# -*- coding:utf-8 -*-
import copy # 注意对象的深拷贝和浅拷贝的使用！！！
class GameNode:
'''博弈树结点数据结构
成员变量：
map - list[[]] 二维列表，三子棋盘状态
val - int 该棋盘状态对执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
deepID - int 博弈树的层次深度，根节点deepID=0
parent - GameNode，父结点
children - list[GameNode] 子结点列表
'''
def __init__(self, map, val=0, deepID=0, parent=None, children=[]):
self.map = map
self.val = val
self.deepID = deepID
self.parent = parent
self.children = children
class GameTree:
'''博弈树结点数据结构
成员变量：
root - GameNode 博弈树根结点
成员函数：
buildTree - 创建博弈树
'''
def __init__(self, root):
self.root = root # GameNode 博弈树根结点
def buildTree(self, root):
'''递归法创建博弈树
参数：
root - GameNode 初始为博弈树根结点
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
##创建root的子节点
###fuc用来调用判断是否最终状态的函数
mm=MinMax(False)
if mm.isTerminal(root):
root.val=mm.get_value(root)
return
##递归遍历创造新的节点
li=root.map
val=0
for i in range(3):
for j in range(3):
if li[i][j]=='x' or li[i][j]=='o':
continue
newLi=copy.deepcopy(li)
newLi[i][j]='o' if root.deepID%2>0 else 'x'
newNode=GameNode(map=newLi,parent=root,deepID=(root.deepID+1),children=[],val=0)
root.children.append(newNode)
self.buildTree(newNode)
if root.deepID%2>0:
root.val=mm.min_value(root)
else:
root.val=mm.max_value(root)
#********** End **********#
class MinMax:
'''博弈树结点数据结构
成员变量：
game_tree - GameTree 博弈树
成员函数：
minmax - 极大极小值算法，计算最优行动
max_val - 计算最大值
min_val - 计算最小值
get_val - 计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
isTerminal - 判断某状态是否为最终状态：无空闲棋可走
'''
def __init__(self, game_tree):
self.game_tree = game_tree # GameTree 博弈树
def minmax(self, node):
'''极大极小值算法，计算最优行动
参数：
node - GameNode 博弈树结点
返回值：
clf - list[map] 最优行动，即x棋子的下一个棋盘状态GameNode.map
其中，map - list[[]] 二维列表，三子棋盘状态
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
val=node.val
result=[]
if val>0:
for i in node.children:
if i.val==val:
result.append(i.map)
return result
#********** End **********#
def max_value(self, node):
'''计算最大值
参数：
node - GameNode 博弈树结点
返回值：
clf - int 子结点中的最大的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
li=node.children
max=-1
for i in node.children:
max=i.val if i.val>max else max
return max
#********** End **********#
def min_value(self, node):
'''计算最小值
参数：
node - GameNode 博弈树结点
返回值：
clf - int 子结点中的最小的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
li=node.children
min=1
for i in node.children:
min=i.val if i.val<min else min
return min
#********** End **********#
def get_value(self, node):
'''计算某棋盘状态中：执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
参数：
node - GameNode 博弈树结点
返回值：
clf - int 执x棋子的评估值，1表示胜利，-1表示失败，0表示平局
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
li=node.map
isEndI=1
isEndJ=1
##判断行列上是否存在直线
for i in range(3):
isEndI=0 if li[i][0]=='_' else 1
isEndJ=0 if li[0][i]=='_' else 1
for j in range(3):
if li[i][j]=='_' or (isEndI>0 and li[i][j]!=li[i][0]):
isEndI=0
if li[j][i]=='_' or (isEndJ>0 and li[j][i]!=li[0][i]):
isEndJ=0
if isEndI+isEndJ<1:
break
if isEndI>0:
return 1 if li[i][0]=='x' else -1
if isEndJ>0:
return 1 if li[0][i]=='x' else -1
##判断斜线上是否存在直线
isEndR=0 if li[0][0]=='_' else 1
isEndL=0 if li[2][0]=='_' else 1
for i in range(3):
if li[i][i]=='_' or (isEndR>0 and li[i][i]!=li[0][0]):
isEndR=0
if li[2-i][i]=='_' or (isEndL>0 and li[2-i][i]!=li[2][0]):
isEndL=0
if isEndR+isEndL<0:
break
if isEndR>0:
return 1 if li[0][0]=='x' else -1
if isEndL>0:
return 1 if li[2][0]=='x' else -1
return 0
#********** End **********#
def isTerminal(self, node):
'''判断某状态是否为最终状态：无空闲棋可走（无子结点）
参数：
node - GameNode 博弈树结点
返回值：
clf - bool 是最终状态，返回True，否则返回False
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
li=node.map
##判断是否还有空位
isFull=1
for i in range(3):
for j in range(3):
if li[i][j]=='_':
isFull=0
break
if isFull==0:
break
if isFull>0:
return True
isEndI=1
isEndJ=1
##判断行列上是否存在直线
for i in range(3):
isEndI=1
isEndJ=1
for j in range(3):
if li[i][j]=='_' or (isEndI>0 and li[i][j]!=li[i][0]):
isEndI=0
if li[j][i]=='_' or (isEndJ>0 and li[j][i]!=li[0][i]):
isEndJ=0
if isEndI+isEndJ<1:
break
if isEndI+isEndJ>0:
return True
##判断斜线上是否存在直线
isEndR=1
isEndL=1
for i in range(3):
if li[i][i]=='_' or (isEndR>0 and li[i][i]!=li[0][0]):
isEndR=0
if li[2-i][i]=='_' or (isEndL>0 and li[2-i][i]!=li[0][2]):
isEndL=0
if isEndR+isEndL<0:
break
if isEndR+isEndL>1:
return True
return False
#********** End **********#
在MinMax算法基础上，如果A行步的时候，已经知道下在一个特定位置，评估函数的值有多大，那么下一步行步选择的>=当前评估函数值。同理可得预测B行步时。
alpha剪枝：若任意极小值层节点的beta值小于或者等于它任一先辈极大值层节点的alpha值时候，可以中止该节点的搜索，最终该节点的倒退值确定为这个beta值
beta剪枝：若若任意极大值层节点的alpha值大于或者等于它任一先辈极大值层节点的beta值时候，可以中止该节点的搜索，最终该节点的倒退值确定为这个alpha值
设置剪枝函数，减少决策树的搜索时间
2、主要想法因为没有设置TreeNode记录深度的属性，所以采用max_value和min_value相互调用的设置，可以实现切换。
而max_value中拿到子节点的min_value返回值，判断是否更新下界为返回值（当前的子节点的评估值更大），然后判断下界是否超过上届（该节点的值比已经扫描过的兄弟节点小）则直接结束搜索，将当前节点的value设置为下界，返回当前节点的value。
而min_value中拿到子节点的max_value返回值，判断是否更新上界为返回值（当前的子节点的评估值更小），然后判断上界是否小于下届（该节点的值比已经扫描过的兄弟节点大）则直接结束搜索，将当前节点的value设置为上界，返回当前节点的value。
if __name__ == '__main__':
# 数据输入
raw_list = ['A', ['B', ('E', 3), ('F', 12), ('G', 8)], ['C', ('H', 2), ('I', 100), ('J', 100)], ['D', ('K', 14), ('L', 5), ('M', 2)]]
# 把数据还原成它本身或者是能够转化成的数据类型
#raw_list = literal_eval(raw)
# 创建一棵博弈树
game_tree = GameTree()
game_tree.root = GameNode(raw_list[0])
game_tree.buildTree(raw_list, game_tree.root)
# AlphaBeta 剪枝算法
alpha_beta = AlphaBeta(game_tree)
best_node = alpha_beta.minmax_with_alphabeta(alpha_beta.game_tree.root)
# 输出最优结点及其评估值
print(best_node.name, best_node.val)
# -*- coding:utf-8 -*-
import copy # 注意对象的深拷贝和浅拷贝的使用！！！
class GameNode:
'''博弈树结点数据结构
成员变量：
name - string 结点名字
val - int 结点值
children - list[GameNode] 子结点列表
'''
def __init__(self, name='', val=0):
self.name = name # char
self.val = val # int
self.children = [] # list of nodes
class GameTree:
'''博弈树结点数据结构
成员变量：
root - GameNode 博弈树根结点
成员函数：
buildTree - 创建博弈树
'''
def __init__(self):
self.root = None # GameNode 博弈树根结点
def buildTree(self, data_list, root):
'''递归法创建博弈树
参数：
data_list - list[] like this ['A', ['B', ('E', 3), ('F', 12)], ['C', ('H', 2)], ['D', ('K', 14)]]
root - GameNode
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
del data_list[0]
for i in data_list:
if isinstance(i,int):
root.val=i
else:
new_data_list=list(i)
new_node=GameNode(name=new_data_list[0],val=0)
self.buildTree(new_data_list,new_node)
root.children.append(new_node)
return root
#********** End **********#
class AlphaBeta:
'''博弈树结点数据结构
成员变量：
game_tree - GameTree 博弈树
成员函数：
minmax_with_alphabeta - 带AlphaBeta剪枝的极大极小值算法，计算最优行动
max_value - 计算最大值
min_value - 计算最小值
get_value - 返回结点的值
isTerminal - 判断某结点是否为最终结点
'''
def __init__(self, game_tree):
self.game_tree = game_tree # GameTree 博弈树
def minmax_with_alphabeta(self, node):
'''带AlphaBeta剪枝的极大极小值算法，计算最优行动
参数：
node - GameNode 博弈树结点
返回值：
clf - GameNode 最优行动的结点
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
self.max_value(node,1000,-1000)
for i in node.children:
if i.val==node.val:
return i
#********** End **********#
def max_value(self, node, alpha, beta):
'''计算最大值
参数：
node - GameNode 博弈树结点
alpha - int 剪枝区间下限值
beta - int 剪枝区间上限值
返回值：
clf - int 子结点中的最大的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if self.isTerminal(node):
return node.val
for i in node.children:
new_beta=self.min_value(i,alpha,beta)
beta=new_beta if new_beta>beta else beta
if alpha<beta:
break
node.val=beta
return beta
#********** End **********#
def min_value(self, node, alpha, beta):
'''计算最小值
参数：
node - GameNode 博弈树结点
alpha - int 剪枝区间下限值
beta - int 剪枝区间上限值
返回值：
clf - int 子结点中的最小的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if self.isTerminal(node):
return node.val
for i in node.children:
new_alpha=self.max_value(i,alpha,beta)
alpha=new_alpha if new_alpha<alpha else alpha
if alpha<beta:
break
node.val=alpha
return alpha
#********** End **********#
def get_value(self, node):
'''返回结点的值
参数：
node - GameNode 博弈树结点
返回值：
clf - int 结点的值，即 node.val
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
return node.val
#********** End **********#
def isTerminal(self, node):
'''判断某结点是否为最终结点（无子结点）
参数：
node - GameNode 博弈树结点
返回值：
clf - bool 是最终状态，返回True，否则返回False
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if len(node.children)>0:
return False
return True
#********** End **********#
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）