阿尔法贝塔剪枝——中国象棋人机对战

阿尔法贝塔剪枝——中国象棋⼈机对战

alpha-beta 剪枝算法实现中国象棋⼈机对战

问题介绍

本实验要求编写⼀个中国象棋博弈程序，使⽤alpha-beta剪枝算法，实现⼈机对弈。因为是⼈机博弈，因此我们需要使得电脑⽐较聪明，⽽⽅法就是要电脑选择⾛⽐较好的步骤。机器是基于搜索来下棋的，我们需要让机器考虑⽐较长远的情况，然后做出⽐较好的选择，⽽为了提⾼搜索效率，就应⽤到了alpha-beta剪枝算法。

算法介绍

对于博弈问题，我们⾸先考虑的是极⼩极⼤搜索算法。我们规定：MAX代表程序⽅，MIN代表对⼿⽅，P代表⼀个棋局（即⼀个状态）。有利于MAX的势态，取正值；有利于MIN的势态，取负值；势态均衡，取零。的⼤⼩由棋局势态的优劣来决定。评估棋局的静态函数要考虑两个⽅⾯的因素：双⽅都知道⾃⼰⾛到了什么程度

双⽅都知道下⼀步能够做什么

基于这个前提，博弈双⽅要考虑的问题是：如何产⽣⼀个最好的⾛步，能尽快获胜。因此，就引出来极⼩极⼤搜索算法。极⼩极⼤搜索的基本思想是：

1. 当轮到MIN⾛步的节点时，MAX应考虑最坏的情况（因此，取极⼩值）。

2. 当轮到MAX⾛步的节点时，MAX应考虑最好额情况（因此，取极⼤值）。

3. 当评价往回倒退时，相应于两位棋⼿的对抗策略，不同层上交替地使⽤1、2两种⽅法向上传递倒推值。

MIN、MAX过程将⽣成后继节点与估计格局两个过程分开考虑，即需要先⽣成全部搜索树，然后再进⾏每个节点的静态估计和倒推值计算。实际上，这种⽅法效率极低。⽽alpha-beta基于这个过程，给了我们⼀个⾼效的算法。在极⼤层中定义下界值，它表明该MAX节点向上的倒推值不会⼩于；在极⼩层中定义上界值，它表明该MIN节点向上的倒推值不会⼤于。

剪枝规则如下：

1. 剪枝。若任⼀极⼩层节点的值不⼤于它任⼀前驱极⼤层节点的值，即（前驱层）（后继层），则可以中⽌该极⼩层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个值。

2. 剪枝。若任⼀极⼤层节点的值不⼩于它任⼀前驱极⼩层节点的值，即（后继层）（前驱层），则可以中⽌该极⼤层中这个MAX节点以下的搜索过程。这个MAX节点最终的倒推值就确定为这个值。

算法实现

本次项⽬的UI是参考了⽹上的代码，使⽤Java实现。重点分析alpha-beta剪枝算法，关于UI部分就不详细分析了。

⾸先我们来看棋局的评估，能否对棋局有⼀个好的评估是这个算法很关键的⼀环。我们需要对棋局做出合适的评估，以确定最好的⾛步。评估的⽅⾯有三个，⼀个是下⼀步的棋⼒，第⼆个是下⼀步能做什么，第三个是棋⼦的价值。先看棋⼒，棋⼒的评估主要是根据棋⼦所在的位置来分析。这⾥我们写好了每个棋⼦在不同位置的棋⼒，这是参考了⼀些论⽂得出来的。第⼆个是下⼀步能做什么，我们可以根据下⼀步能做什么来判断这个⾛步的好坏。在象棋游戏中，⼀个好的⾛步我们期望是能够吃掉对⽅的棋，⽽且吃掉的棋⼦价值越⼤，这个⾛步越好。当然，如果下⼀步能够将军，那么这个⾛步很有可能就是我们想要的。于是我们对下⼀步能做什么做⼀个估值：如果下⼀步能将军，那么它的估值将⼤⼤增加（+9999）；如果下⼀步能吃掉对⽅的棋⼦，那么它的估值将会有⼀定的增加（车：+500，马或炮：+100）；如果下⼀步只能吃掉对⽅的卒，那么它的估值就会下降（-20），因为多数情况下吃掉对⽅的卒都没什么好处。最后是棋⼦的价值，这是⽐较固定的因素，因为我们普遍认为某些棋⼦的价值是⽐其他棋⼦⼤的（⽐如车的价值⼀般来说都⽐卒要⼤）。

每次估值都需要分开两⽅的棋⼦来进⾏估值。即算出程序⽅棋局的总体价值和对⼿⽅棋局的整体价值。⽤程序⽅估值-对⼿⽅估值作为这个状态下的估值。如果这个估值⼤于0，说明程序⽅占优势；反之，说明对⼿⽅占优势。

f (P )f (P )f (P )f (P )f (P )f (P )ααββαβαα≥βββαβα≥βα

完成好估值后，就可以开始alpha-beta的剪枝算法了。⾸先确定博弈树的深度，通俗来说就是要让程序往后推演⼏步。当然推演的步数越多，越能到⼀个好的⾛步，但是所需的时间也就越多。然后我们需要使⽤⼀个标记来表⽰当前是极⼤层还是在极⼩层，根据标记来计算当前节点的或。如果在极⼤层，我们需要获得它下⾯所有极⼩层的倒推值的极⼤值（实际上不是所有）；如果在极⼩层，就需要获得它下⾯所有极⼤层的倒推层的极⼩值（实际上不是所有）。这⾥就牵涉到了剪枝。以在极⼤层为例，如果当前MAX节点提供的倒推值⼤于其前驱极⼩层MIN节点的，那么说明这个MAX节点以下搜索提供的值不可能⼩于，也就没有继续搜索的意义了，所以就可以直接结束这个MAX节点的搜索，这就是剪枝。

关键代码分析

1. 棋⼦本⾝的价值评估：

int [] BasicValue = { 80, 0, 0, 300, 500, 300, 100}; 将军：80⼠：0象：0马：300车：500炮：300

卒：100

1. 棋⼦位置的价值评估：

将军

int [][] JiangPosition = new int [][] {

{0, 0, 0, 1, 5, 1, 0, 0, 0},

{0, 0, 0, -8, -8, -8, 0, 0, 0},

{0, 0, 0, -9, -9, -9, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0}

};

⼠

int [][] ShiPosition = new int [][] {

{0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 3, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0}

};

象

int [][] XiangPosition = new int [][] {

αβαβα

{-2,0,0,0,3,0,0,0,-2},

{0,0,0,0,0,0,0,0,0},

广水四中{0,0,0,0,0,0,0,0,0}

};

马

int[][] MaPosition =new int[][]{ {0,-3,2,0,2,0,2,-3,0},

{-3,2,4,5,-10,5,4,2,-3},

{5,4,6,7,4,7,6,4,5},

{4,6,10,7,10,7,10,6,4},

{2,10,13,14,15,14,13,10,2}, {2,10,13,14,15,14,13,10,2}, {2,12,11,15,16,15,11,12,2}, {5,20,12,19,12,19,12,20,5}, {4,10,11,15,11,15,11,10,4}, {2,8,15,9,6,9,15,8,2},

{2,2,2,8,2,8,2,2,2}

};

车

int[][] JuPosition =new int[][]{

{-6,6,4,12,0,12,4,6,-6}, {5,8,6,12,0,12,6,8,5},

{-2,8,4,12,12,12,4,8,-2}, {4,9,4,12,14,12,4,9,4},

{8,12,12,14,15,14,12,12,8}, {8,11,11,14,15,14,11,11,8}, {6,13,13,16,16,16,13,13,6}, {6,8,7,14,16,14,7,8,6},

{6,12,9,16,33,16,9,12,6}, {6,8,7,13,14,13,7,8,6}

};

炮

int[][] PaoPosition =new int[][]{ {0,0,1,3,3,3,1,0,0},

{0,1,2,2,2,2,2,1,0},

{1,0,4,3,5,3,4,0,1},

{0,0,0,0,0,0,0,0,0},

{-2,0,-2,0,6,0,-2,0,-2},

{3,0,4,0,7,0,4,0,3},

{10,18,22,35,40,35,22,18,10}, {20,27,30,40,42,40,30,27,20}, {20,30,45,55,55,55,45,30,20}, {20,30,50,65,70,65,50,30,20}, {0,0,0,2,4,2,0,0,0}

};

卒

int[][] BingPosition =new int[][]{ {0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0},

{10,18,22,35,40,35,22,18,10},

{20,27,30,40,42,40,30,27,20},

{20,30,50,65,70,65,50,30,20},

{0,0,0,2,4,2,0,0,0}

};

1. 对下⼀步吃⼦进⾏估值：

private int estimate_myself(Piece piece){

乐益民

// System.out.println(piece.Info);

if(piece.Info =="bb0"|| piece.Info =="rb0")return0;

int totalValue =0;

ArrayList<int[]> next = NextMove(piece.Info, piece.pos, Board);

for(int[] n : next){

Piece p = Piece(n);

旧金山中华总会馆if(p != null && Piece(n).character =='b'){

totalValue +=9999;

break;

}

if(p != null && Piece(n).character =='j'){

totalValue +=500;

break;

李谷一五十年演唱会}

if(p != null && Piece(n).character =='m'&& Piece(n).character =='p'){ totalValue +=100;

}

if(p != null && Piece(n).character =='z'){

totalValue -=20;

}

return totalValue;

}

下⼀步能将军，估值+9999（相当于直接选择这个值了）

下⼀步能吃【车】，估值+500

下⼀步能吃【马】或【炮】，估值+100

下⼀步能吃【卒】，估值-20

1. 对每个状态的估值

public int estimate(ChessBoard Board){

int[][] totalValue =new int[2][3];

for(Map.Entry<String, Piece> pieceEntry : Set()){

Piece piece = Value();

switch(piece.character){

case'b':

lor =='b'){

totalValue[0][0]+=estimate_value(0);

totalValue[0][1]+=estimate_position(0, piece.pos);

}else{

totalValue[1][0]+=estimate_value(0);

totalValue[1][1]+=estimate_position(0,getOppositePos(piece.pos));

}

break;

case's':

lor =='b'){

totalValue[0][0]+=estimate_value(1);

totalValue[0][1]+=estimate_position(1, piece.pos);

Obama speech in Shanghai

totalValue[1][0]+=estimate_value(1);

totalValue[1][1]+=estimate_position(1,getOppositePos(piece.pos));

}

break;

case'x':

lor =='b'){

totalValue[0][0]+=estimate_value(2);

totalValue[0][1]+=estimate_position(2, piece.pos);

}else{

totalValue[1][0]+=estimate_value(2);

totalValue[1][1]+=estimate_position(2,getOppositePos(piece.pos));

}

break;

case'm':

lor =='b'){

totalValue[0][0]+=estimate_value(3);

totalValue[0][1]+=estimate_position(3, piece.pos);

}else{

totalValue[1][0]+=estimate_value(3);

totalValue[1][1]+=estimate_position(3,getOppositePos(piece.pos));

}

break;

case'j':

lor =='b'){

totalValue[0][0]+=estimate_value(4);

totalValue[0][1]+=estimate_position(4, piece.pos);

}else{

totalValue[1][0]+=estimate_value(4);

totalValue[1][1]+=estimate_position(4,getOppositePos(piece.pos));

}

break;

case'p':

lor =='b'){

totalValue[0][0]+=estimate_value(5);

totalValue[0][1]+=estimate_position(5, piece.pos);

}else{

totalValue[1][0]+=estimate_value(5);

totalValue[1][1]+=estimate_position(5,getOppositePos(piece.pos));

}

break;

case'z':

lor =='b'){

totalValue[0][0]+=estimate_value(6);

totalValue[0][1]+=estimate_position(6, piece.pos);

}else{

totalValue[1][0]+=estimate_value(6);

totalValue[1][1]+=estimate_position(6,getOppositePos(piece.pos));

}

break;

}

totalValue[0][2]+=estimate_myself(piece);

totalValue[1][2]+=estimate_myself(piece);

}

int red = totalValue[1][0]+ totalValue[1][1]+ totalValue[1][2];

int black = totalValue[0][0]+ totalValue[0][1]+ totalValue[0][2];

int result_value = black - red;

return result_value;

}

对每个状态的估值包含了上⾯三种估值，然后⽤程序⽅估值-对⼿⽅估值得出最终结果。

刘桂苏

2. alpha-beta剪枝算法。

// alpha-beta algorithm.

本文发布于:2024-09-21 00:38:31，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/30301.html

上一篇：毕业设计(论文)-计算机五子棋游戏对弈系统设计[管理资料]

下一篇：五子棋--需求分析

标签：估值节点搜索棋局程序需要算法

留言与评论（共有 0 条评论）