东北大学人工智能大作业

机器博弈（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.评估博弈树叶节点对应的博弈状态

step3.进行极大极小运算(Max-Min运算) Max 按取最大评估值的方向行棋

step4.等待 Min行棋，产生新的 c(o)返回 step1. 3.2五子棋机器博弈问题

varmaxmin = function(board, deep) { var best = MIN;

var points = gen(board, deep); //这个函数的作用是生成待选的列表，就是可以下子的

空位

for(vari=0;i

board[p[0]][p[1]] = R.com; //尝试下一个子 var v = min(board, deep-1); //找最大值

//如果跟之前的一个好，则把当前位子加入待选位子 if(v == best) {

bestPoints.push(p); }

//找到一个更好的分，就把以前存的位子全部清除 if(v > best) { best = v; bestPoints = []; bestPoints.push(p); }

board[p[0]][p[1]] = R.empty; //记得把尝试下的子移除 }

var result = bestPoints[Math.floor(bestPoints.length * Math.random())]; //在分数最高的几个位置中随机选择一个 return result; }

var min = function(board, deep) {

var v = evaluate(board); //评价函数，这个函数返回的是对当前局势的估分。 if(deep <= 0 || win(board)) { return v; }

var best = MAX;

var points = gen(board, deep);

for(vari=0;i

board[p[0]][p[1]] = R.hum; var v = max(board, deep-1); board[p[0]][p[1]] = R.empty; if(v < best ) { best = v; } }

return best ; }

var max = function(board, deep) { var v = evaluate(board); if(deep <= 0 || win(board)) { return v; }

var best = MIN;

var points = gen(board, deep);

for(vari=0;i

board[p[0]][p[1]] = R.com; var v = min(board, deep-1); board[p[0]][p[1]] = R.empty; if(v > best) { best = v; } }

return best; }

var min = function(board, deep, alpha, beta) { var v = evaluate(board); total ++;

if(deep <= 0 || win(board)) { return v; }

var best = MAX;

var points = gen(board, deep);

for(vari=0;i

board[p[0]][p[1]] = R.hum;

var v = max(board, deep-1, best < alpha ? best : alpha, beta); board[p[0]][p[1]] = R.empty; if(v < best ) { best = v; }

if(v < beta) { //AB剪枝 ABcut ++; break; } }

return best ; }

var max = function(board, deep, alpha, beta) { var v = evaluate(board); total ++;

if(deep <= 0 || win(board)) {

return v; }

var best = MIN;

var points = gen(board, deep);

for(vari=0;i

board[p[0]][p[1]] = R.com;

var v = min(board, deep-1, alpha, best > beta ? best : beta); board[p[0]][p[1]] = R.empty; if(v > best) { best = v; }

if(v > alpha) { //AB 剪枝 ABcut ++; break; } }

return best; }

本文来源：https://www.bwwdw.com/article/jhdd.html