计算机科学

首页 > 计算机科学

博弈树

2018-07-27 09:47:27     所属分类:人工智能

博弈树game tree)是指组合博弈理论中用来表达一个赛局中各种后续可能性的树,一个完整的博弈树(complete game tree)会有一个起始节点,代表赛局中某一个情形,接着下一层的子节点是原来父节点赛局下一步的各种可能性,依照这规则扩展直到赛局结束。博弈树相同于扩展形式的博弈理论中的树。博弈树中形成的叶节点代表各种游戏结束的可能情形,例如井字游戏会有26,830个叶节点。

一个井字游戏的博弈树示例

博弈树在人工智能的应用相当重要,若要查找某赛局中最佳的步法的一个方式,是利用极小化极大算法在博弈树中搜索最佳解[1][2],例如在井字游戏中电脑可以很快速地找到最佳解并做出决策,但是对于象棋、围棋这一类大型的博弈游戏,列出完整博弈树可能使电脑计算能力难以应付,因此对这类游戏通常会采用部分的博弈树(partial game tree)来进行搜索,典型的部分博弈树通常是限制博弈树的层数,并剔除不佳的步法(例如自杀),一般而言搜索的层数越多,能走出较佳步法的机会也越高。

若是两人游戏,除了可以用博弈树表达之外,也可以用And–or tree表示。

相关条目

  • 人工智能
  • 扩展形式的博弈
  • 图论

参考资料

  1. ^ http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
  2. ^ 极小化极大算法

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


上一篇:电脑象棋
下一篇:第五代电脑
相关推荐