一、建模

1. 玩家：

用1和2表示。

2. 状态集S：

合法棋局的集合，两个棋局相等当且仅当：
a)两个棋局盘面完全一致。
b)两个棋局的下一落子者相同。
状态集的元素用s表示。

3. 后继关系：

设s, s’∈S，(s’,s)在后继关系中，当且仅当s’经过某一步合法落子可以达到s，简称为s为s’的后继。

4. 完全博弈树T和映射m：

T = (V,E)， m: V→S。T和S利用归纳定义构造：
a)构建v₀，令m(v₀)为S的初始状态，令v₀∈V，令v₀的父节点为空
b)设v∈V，对m(v)所有的后继s’，构建节点v’，令m(v’) = s’，令v’∈T，令v’的父节点为v。根据先手，可构造出两棵不同的完全博弈树T₁和T₂，分别对应玩家1先手和玩家2先手。
显然：
a)叶节点代表分出胜负或和的状态，一条从根节点到叶节点的路径代表一个合法的落子过程。
b)m不是单射，但m为满射。

5. 博弈树：

如果完全博弈树的某个子图T’也为一棵树，则称T’为博弈树。显然，完全博弈树为博弈树。

6. 主路径：

博弈树T’的一条从根节点到叶节点的路径P。P代表棋局的进程。

7. 终结点：

若v∈T，且m(V)已分出胜负或和，则称v为终结点。显然v为终结点等价于v为T中的叶节点。

8. 全拓展节点：

若v∈T’，并且v在T’中的所有子节点与v在T中的所有子节点一致，则称v为全拓展节点。

9. 拓展：

若v∈T’，并且v非全拓展节点，则向v加入子节点v’的过程称为拓展。对v经过若干次拓展，v会变成全拓展节点。

10. 节点参数：

根据完全博弈树的定义，每个节点都有参数m，m(v)返回的是节点对应的棋盘状态。
其他的参数有：
parent，记录节点的父亲。
childs，记录节点的孩子。
total，记录节点总的模拟次数。
win、lose，记录节点模拟中胜利次数、失败的次数

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！