如果遍历的深度为n，每一层要对225个下棋的点进行遍历，每次遍历又是递归调用。因此每一次下棋就需要对\(225^n\)中棋盘进行分数评估，加上分数评估也需要时间，因此算法复杂度很高，一般\(depth=2\)的时候每一步的等待时间要超过10s。
\(\alpha\)-
\(\beta\) 剪枝算法：
为了针对上述MAX-MIN算法复杂度高的问题，\(\alpha\)-\(\beta\) 剪枝算法应运而生。
剪枝思想
考虑图中画圈的部分：
已知MAX要选择所有MIN已经造成的得分中最高的那一个位置落子；
对于图中的①号节点，其遍历过②号节点以及对应的子树之后目前的得分是4；
其开始遍历自己的第二棵子树，其根节点为③，节点③遍历自己的第一个子树后获得的值为40；
由于节点①取最大值，因此节点③目前的值有保留的必要。
继续搜索第二棵子树，发现第二棵子树的根节点对应的值为-36；
由于节点③对应的是MIN玩家，要选择最小的位置，因此MIN玩家更新自己落子的位置，节点③的值更新为-36；
由于节点③对应的是MIN玩家，其选择的落子位置得分不会比-36大；
而节点①是MAX玩家，其不可能选择落子得分为-36的局面；
因此节点③就没有往后搜索的必要了，因此后面的搜索都可以去掉。完成一个剪枝。
注意，这个搜索过程是在建立树的过程中剪枝的，是先剪枝，再有整个问题的完整搜索树
算法具体实现：
每一个节点维护一个\(\alpha\)和\(\beta\)值以及这个节点的估值\(v\)，表示该节点的估值应该在\([\alpha,\beta]\)区间内，一旦\(\alpha \ge \beta\)，这个节点就不再进行拓展，成为死节点。
\(\alpha\)和\(\beta\)的更新有两个来源：
如果目前考虑的节点为MAX玩家对应的节点，则它的\(\alpha\)值为目前所有孩子节点的值中的最大值（此时\(v == \alpha\)），如果目前考虑的节点为MIN玩家对应的节点，则它的\(\beta\)值为目前所有孩子节点中值的最小值（此时\(v == \beta\)）。
\(\alpha\)和\(\beta\)的初始值继承自其双亲节点。最初的根节点其\(\alpha = -\infin, \beta=\infin\)。
具体过程如图所示：
这里略过12张图片，具体看下面链接
图片引自：详解Minimax算法与α-β剪枝_文剑木然的专栏-CSDN博客_α-β剪枝
自己用笔画一遍就会了啦
算法伪代码：
分为三个函数，alpha_beta_search函数代表调用的入口，Max_Value函数代表Max的操作，Min_Value函数代表Min的操作。
cpp代码：
int chess_board::max_value(int deep,int alpha,int beta,QTextBrowser *detail_info)
{
if(deep==depth)
return cal_score(first_me);
int v = -0x3f3f3f3f;
int old_a = 0;
for(int l=0;l<board_col;l++)//启发式搜索
for(int r=0;r<board_row;r++)
{
if(board[r][l]==\'0\')//如果当前位置是空子的话
{
set_temp_chess(r,l,true);
v = max(v,min_value(deep+1,alpha,beta,detail_info));
if(v>=beta)
{
clear_temp_chess(r,l);//注意要回溯
return v;
}
alpha = max(alpha,v);
if(deep==0&&alpha==v&&alpha!=old_a)//如果是在最表层且有更新，则选择这一步
{
char tip_out[1005] = {0};
sprintf(tip_out,"update max:\n l = %d, r = %d \nv = %d\n",l,r,v);
detail_info->textCursor().insertText(tip_out);
next.set_rl(r,l);
old_a = alpha;
}
clear_temp_chess(r,l);//注意要回溯
}
}
return v;
}
int chess_board::min_value(int deep,int alpha,int beta, QTextBrowser *detail_info)
{
if(deep==depth)
return cal_score(first_me);
int v = 0x3f3f3f3f;
int old_a = 0;
vector<node>h_score;
for(int l=0;l<board_col;l++)//启发式搜索
for(int r=0;r<board_row;r++)
{
if(board[r][l]==\'0\')//如果当前位置是空子的话
{
set_temp_chess(r,l,false);
v = min(v,max_value(deep+1,alpha,beta,detail_info));
if(v<=alpha)
{
clear_temp_chess(r,l);//注意要回溯
return v;
}
beta = min(beta,v);
clear_temp_chess(r,l);//注意要回溯
}
}
return v;
}
void chess_board::alpha_beta_search(QTextBrowser *detail_info)
{
int alpha = -0x3f3f3f3f;
int beta = 0x3f3f3f3f;
score_next = max_value(0,alpha,beta,detail_info);
}
实现细节
注意要回溯，对的，基本上没什么了，注意要回溯。
有无
\(\alpha\)-
\(\beta\) 剪枝对比：
