从人落子开始到出现胜负或者和局，之间所落的子，构成了一个解。而解空间就是一个树，解就是这解空间中的一条路径。只不过这个解空间是电脑的选择和人的选择共同构成的（奇数层是电脑（由于轮到电脑落子么），偶数层是人）。算法
极大极小值搜索算法，来搜索（回溯）这个解空间：它假设人和电脑都是极其聪明的，他们都会选择出最优的一步。数组
可是搜索整棵树是不现实的，16*16！指数级，因此只回溯n步，即这个AI考虑的是N步以内的最优解，它是考虑了n步以后的状况的ide
-------------------------------------------------------------------我是分割线-------------------------------------------------------------------------函数
假设玩家执黑子，电脑执白子lua
评估函数：评估函数将对棋盘上的全部黑子作出评分（连成线的等级越高，数量越多，估分就越高）做scorehumber；也将对棋盘上的全部白子作出评分（连成线的等级越高，数量越多，估分就越高）做scorecomputer。而后评估值为【scorecoputer-scorehumber】。它将认为，这个评估值越高，整个局面对电脑越有利；这个评估值越低，整个局面对玩家越有利。spa
max-min搜索最优解，即向后回溯depth步，轮到电脑时，电脑作出最有利于本身的选择（选择最高的评估值），轮到玩家时，玩家作出最有利于本身的选择（选择最低的评估值）。（他们的选择将被推迟，叶子节点先作出选择，而后层层往上推出那一层的最优解）。伪码：.net
int MinMax(int depth) { // 函数的评估都是以白方的角度来评估的
if (SideToMove() == WHITE) { // 白方是“最大”者
return Max(depth);
} else { // 黑方是“最小”者
return Min(depth);
}
}
int Max(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Min(depth - 1);
UnmakeMove();
if (val > best) {
best = val;
}
}
return best;
}
int Min(int depth) {
int best = INFINITY; // 注意这里不一样于“最大”算法
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1);
UnmakeMove();
if (val < best) { // 注意这里不一样于“最大”算法
best = val;
}
}
return best;
}
-------------------------------------------------------------------我是分割线-------------------------------------------------------------------------
计分板code
| 成五 | +100000 |
| 活四 | +10000 |
| 死四 | +1000 |
| 活三 | +1000 |
| 死三 | +100 |
| 活二 | +100 |
| 死二 | +10 |
| 活一 | +10 |
int max_noalphabeta(int depth,int i1,int i2);//轮到电脑走步时，电脑做的选择
int min_noalphabeta(int depth,int i1,int i2);//轮到人走步时，人做的选择
void generatepoint(vector< pair<int,int> > &v);//产生空子序列
int scoretable(int number,int empty1);//积分表
int countscore(vector<int> n,int turn); //算单个数组分
bool hasne(int x,int y);//周围是否有子存在，无子的就加考虑
bool hasne(int x,int y)//空子只算旁边有子的
{
int i,j;
for(i=(x-3>0?x-3:0);i<=x+3&&i<16;++i)
for(j=(y-3>0?y-3:0);j<=y+3&&j<16;++j)
if(i!=0||j!=0)
if(pos[i][j]!=0)
return true;
return false;
}
void generatepoint(vector< pair<int,int> > &v)//产生空子序列
{
for(int i=0;i<16;++i)
for(int j=0;j<16;++j)
if(pos[i][j]==0&&hasne(i,j))
{
pair<int,int> p;
p.first=i;
p.second=j;
v.push_back(p);
}
}
//按照成五100000、活四10000、活三1000、活二100、活一十、死四1000、死三100、死二10的规则
//给棋盘上的全部棋子打分，之和为电脑的单方面得分scorecomputer，而后对玩家的棋子一样打分，之和为scorehumber
//scoreComputer-scorehumber即为当前局势的总分数
int scoretable(int number,int empty1)//计分板
{
if(number>=5) return 100000;
else if(number==4)
{
if(empty1==2) return 10000;
else if(empty1==1) return 1000;
}
else if(number==3)
{
if(empty1==2) return 1000;
else if(empty1==1) return 100;
}
else if(number==2)
{
if(empty1==2) return 100;
else if(empty1==1) return 10;
}
else if(number==1&&empty1==2) return 10;
return 0;
}
int countscore(vector<int> n,int turn)//正斜线、反斜线、横、竖，均转成一维数组来计算
{
int scoretmp=0;
int len=n.size();
int empty1=0;
int number=0;
if(n[0]==0) ++empty1;
else if(n[0]==turn) ++number;
int i=1;
while(i<len)
{
if(n[i]==turn) ++number;
else if(n[i]==0)
{
if(number==0) empty1=1;
else
{
scoretmp+=scoretable(number,empty1+1);
empty1=1;
number=0;
}
}
else
{
scoretmp+=scoretable(number,empty1);
empty1=0;
number=0;
}
++i;
}
scoretmp+=scoretable(number,empty1);
return scoretmp;
}
int evaluate_minmax_noalphabeta()//评估函数，评估局势
{
int scorecomputer=0;
int scorehumber=0;
//横排们
for(int i=0;i<16;++i)
{
vector<int> n;
for(int j=0;j<16;++j)
n.push_back(pos[i][j]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
//竖排们
for(int j=0;j<16;++j)
{
vector<int> n;
for(int i=0;i<16;++i)
n.push_back(pos[i][j]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
//上半正斜线们
for(int i=0;i<16;++i)
{
int x,y;
vector<int> n;
for(x=i,y=0;x<16&&y<16;++x,++y)
n.push_back(pos[y][x]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
//下半正斜线们
for(int j=1;j<16;++j)
{
int x,y;
vector<int> n;
for(x=0,y=j;y<16&&x<16;++x,++y)
n.push_back(pos[y][x]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
//上半反斜线们
for(int i=0;i<16;++i)
{
vector<int> n;
int x,y;
for(y=i,x=0;y>=0&&x<16;--y,++x)
n.push_back(pos[y][x]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
//下半反斜线们
for(int j=1;j<16;++j)
{
vector<int> n;
int x,y;
for(y=j,x=15;y<16&&x>=0;++y,--x)
n.push_back(pos[x][y]);
scorecomputer+=countscore(n,2);
scorehumber+=countscore(n,1);
n.clear();
}
return scorecomputer-scorehumber;
}
int min_noalphabeta(int depth,int i1,int i2)//玩家落子时 //当min（人）走步时，人的最好状况
{
int res=evaluate_minmax_noalphabeta();
Chess cc;
cc.chess_isover(i1,i2,2);
if(isover!=0||depth<=0)
{
isover=0;
return res;
}
vector< pair<int,int> > v;
generatepoint(v);
int len=v.size();
int best=INT_MAX;
for(int i=0;i<len;++i)
{
pos[v[i].first][v[i].second]=1;
int tmp=max_noalphabeta(depth-1,v[i].first,v[i].second);
if(tmp<best) best=tmp;//玩家落子时选择最有利本身的局面，将推迟，叶子节点作出选择后，层层往上推
pos[v[i].first][v[i].second]=0;
}
return best;
}
int max_noalphabeta(int depth,int i1,int i2) //当max（电脑）走步时，max（电脑）应该考虑最好的状况
{
int res=evaluate_minmax_noalphabeta();
Chess cc;
cc.chess_isover(i1,i2,1);
if(isover!=0||depth<=0)
{
isover=0;
return res;
}
vector< pair<int,int> > v;
generatepoint(v);
int len=v.size();
int best=INT_MIN;
for(int i=0;i<len;++i)
{
pos[v[i].first][v[i].second]=2;
int tmp=min_noalphabeta(depth-1,v[i].first,v[i].second);
if(tmp>best) best=tmp;//电脑落子时，选择最有利于本身的局面，将推迟
pos[v[i].first][v[i].second]=0;
}
return best;
}
void Chess::chess_ai_minmax_noalphabeta(int &x,int &y,int depth)//极大极小值算法搜索n步后的最优解
{
vector< pair<int,int> > v;
generatepoint(v);
int best=INT_MIN;
int len=v.size();
vector< pair<int,int> > v2;
for(int i=0;i<len;++i)
{
pos[v[i].first][v[i].second]=2; //选该子，将该子置白，防止后面递归时，再递归到
int tmp=min_noalphabeta(depth-1,v[i].first,v[i].second);
if(tmp==best)
v2.push_back(v[i]);
if(tmp>best)
{
best=tmp;
v2.clear();
v2.push_back(v[i]);
}
pos[v[i].first][v[i].second]=0; //假设完以后，该子须要从新置空，恢复原来的样子
}
len=v2.size();
int i=(int)(rand()%len);
x=v2[i].first;
y=v2[i].second;
}
http://blog.csdn.net/lihongxun945/article/details/50625267blog
http://blog.csdn.net/kingkong1024/article/details/7639401
递归