东北大学人工智能大作业

机器博弈（Machine Game Playing）

注：维基百科和百度百科中对机器博弈的介绍较少，如有错误请多指教。 01 关于机器博弈 1.1 机器博弈的含义：

机器博弈就字面意思理解，即机器参与到博弈的过程当中，这不仅包括机器与机器之间的博弈，也包括机器与人类之间的博弈。 1.2 机器博弈的特征：

智力竞技——机器博弈过程中机器与对手之间存在着智力上的比拼，并以此区分胜负。 1.3机器博弈的目标：

击败对手——机器博弈涉及多个主体，其最后的结果为分出胜负，博弈双方的目标均为击败对手，

02 博弈问题的描述（以棋类游戏为例） 2.1 博弈问题的形式化

定义：博弈被定义为一个四元组：??G,?O,s(o),s(g)?其中：

(1) ?G ={c}：博弈空间 (棋局或博弈状态的集合) (2) ?O ={o}：算子空间 (操作或规则的集合) (3) c(o)??G：当前棋局或博弈状态 (最初即开局) (4) ?c(g)??G：胜局或博弈目标集合

应用 ?O 中的算子 (操作或规则) 对 c(o)进行操作，使其有利于转换为胜局 c(g)??c(g)的过程称为博弈。

2.2 博弈问题的三要素：c(o)和 c(g)以及O (1) 操作 (又称规则或算子)：

o: ?G ??G 或： c(j) = o(c(i)) (c(i),c(j)??G; o??O)

(2) 当前棋局 (最初是开局)： c(o)??G (机器当前面对的棋局) (3) k-步博弈树：

基于 c(o)的 k-步博弈规划图 03 机器博弈举例

3.1一字棋与极大极小算法 3.1.1Max-Min 博弈： Step1. 生成k-步博弈树

Max代表机器一方/ Min 代表敌方设 Max 面对的当前棋局为c(o)，以 c(o)为根，生成 k-步博弈树 Step2. 评估棋局(博弈状态)

估价函数：为特定的博弈问题定义一个估价函数 est(c)，用以评估 k-步博弈树叶节点对应的棋局 c??G，est(c) 的值越大，意味着棋局 c对 Max越有利。 Step3. 回溯评估

极大极小运算：由叶节点向根节点方向回溯评估，在Max处取最大评估值(或运算)，在Min处取最小评估值(与运算)。

注：Max 按取最大评估值的方向行棋 Step4. 递归循环

Max 行棋后，等待 Min 行棋；

Min 行棋后，即产生对于 Max 而言新的当前棋局 c(o); 返回 Step1.，开始下一轮博弈

3.1.2一字棋：

设有 3?3 棋格，Max 与 Min 轮流行棋，黑先白后，先将 3 颗棋子连成一线的一方获胜。 一字棋博弈空间 ：共有 9! 种可能的博弈状态

一字棋算子空间 ：博弈规则集合O={&*#!@^###+&%$$$} 一字棋博弈目标集合 (对 Max而言)： 定义估价函数：est(c)

(1)对于非终局的博弈状态 c估价函数为：est(c)=(所有空格都放上黑色棋子之后，3 颗黑色棋子连成的直线总数)－(所有空格都放上白色棋子之后，3 颗白色棋子连成的直线总数)。

例如：c=则est(c)=3–2=1

(2)若 c是 Max的胜局，则：est(c) = +?例如：c=

(3)若 c是 Min的胜局，则：est(c) = –?例如：c=

3.1.3Max-Min 博弈过程：

step1.以 c(o) =为根，生成 2-步博弈树： step2.评估博弈树叶节点对应的博弈状态