竞赛树
博弈理論中用來表達一個賽局中各種後續可能性的樹
竞赛树(game tree)是指组合博弈理论中用来表达一个赛局中各种后续可能性的树,一个完整的竞赛树(complete game tree)会有一个起始节点,代表赛局中某一个情形,接著下一层的子节点是原来父节点赛局下一步的各种可能性,依照这规则扩展直到赛局结束。竞赛树相同于扩展形式的博弈理论中的树。竞赛树中形成的叶节点代表各种游戏结束的可能情形,例如井字游戏会有26,830个叶节点。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Tic-tac-toe-game-tree.svg/220px-Tic-tac-toe-game-tree.svg.png)
竞赛树在人工智慧的应用相当重要,若要寻找某赛局中最佳的步法的一个方式,是利用极小化极大演算法在竞赛树中搜寻最佳解[1][2],例如在井字游戏中电脑可以很快速地找到最佳解并做出决策,但是对于象棋、围棋这一类大型的博弈游戏,列出完整竞赛树可能使电脑计算能力难以应付,因此对这类游戏通常会采用部分的竞赛树(partial game tree)来进行搜寻,典型的部分竞赛树通常是限制竞赛树的层数,并剔除不佳的步法(例如自杀),一般而言搜寻的层数越多,能走出较佳步法的机会也越高。
若是两人游戏,除了可以用竞赛树表达之外,也可以用And–or tree表示。
相关条目
编辑参考资料
编辑- ^ http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html. [2011-07-07]. (原始内容存档于2021-03-29).
- ^ 极小化极大演算法