题意：
游戏有A、B两人参与。A先走，每人每次任选一条虚线填成实线。而如果某人填完一条线段后，该线段与另外两条相邻的实线组成了一个单位三角形，该三角形被标记为该游戏者所有，且该游戏者必须接着再填一条虚线。当18条线段被填充完毕后，拥有三角形多的玩家获胜。
首先输入一个数 T ，表示试验次数；接着一个数 n，表示当前局面已经走了 n 条边；接着输入 n 对数，每对数字表示一条填充边，由 A 开始。问从给出的局面开始，双方都采取最优策略，最终谁会取胜。
【实验原理】
1 最单纯的极大极小算法
局面估价函数：我们给每个局面（state）规定一个估价函数值 f，评价它对于己方的有利程度。胜利的局面的估价函数值为 +oo，而失败的局面的估价函数值为–oo。
Max 局面：假设这个局面轮到己方走，有多种决策可以选择，其中每种决策都导致一种子局面（sub-state）。由于决策权在我们手中，当然是选择估价函数值 f 最大的子局面，因此该局面的估价函数值等于子局面 f 值的最大值，把这样的局面称为 max 局面。
Min 局面：假设这个局面轮到对方走，它也有多种决策可以选择，其中每种决策都导致一种子局面（sub-state）。但由于决策权在对方手中，在最坏的情况下，对方当然是选择估价函数值 f 最小的子局面，因此该局面的估价函数值等于子局面 f 值的最小值，把这样的局面称为 max 局面。
终结局面：胜负已分（假设没有和局）.
2.alpha-beta剪枝
简单地说就是用两个参数 alpha 和 beta 表示当前局面的父局面的估价函数值 f()。如果当前局面为 min 局面，则需要借助父局面目前已求得的 f() （即 alpha）来判断是否需要继续搜索下去；如果当前局面为 max 局面，则需要借助父局面目前已求得的 f() （即 beta）。
思路：
显然是博弈问题，也是 alpha-beta 搜索算法的基础应用。一个比较关键的问题是局面的存储。整个棋盘有18条边，因此可以用一个整型来存储一个局面
如果每条边用红色数字表示（当然也可以不这样排列），则用 2^0 = 1 表示 edge(1, 2) 或 edge(2, 1)，用 2^1 = 2(即二进制10)表示edge(2, 3) 或 edge(3, 2)，用2^2 =4(即二进制100)表示 edge(1, 3) 或 edge(3, 1) ...
【实验环境】
VS2012
【实验方案设计】
1. minimax算法
2. alpha-beta剪枝
【源程序】
1. minimax算法
#include<iostream>
#include<cstring>
using namespace std;
int mat[11][11] =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 2, 3, 4, 0, 0, 0, 0, 0 },
{ 0, 1, 2, 0, 0, 5, 6, 0, 0, 0, 0 },
{ 0, 0, 3, 0, 0, 7, 0, 9, 10, 0, 0 },
{ 0, 0, 4, 5, 7, 0, 8, 0, 11, 12, 0 },
{ 0, 0, 0, 6, 0, 8, 0, 0, 0, 13, 14 },
{ 0, 0, 0, 0, 9, 0, 0, 0, 15, 0, 0 },
{ 0, 0, 0, 0, 10, 11, 0, 15, 0, 16, 0 },
{ 0, 0, 0, 0, 0, 12, 13, 0, 16, 0, 17 },
{ 0, 0, 0, 0, 0, 0, 14, 0, 0, 17, 0 }
};
int tri[9] = { 7, 152, 52, 352, 34304, 3200, 71680, 12544, 155648 };
int STATUS = (1 << 18) - 1;
int bestmax=1<<20;
int bestmin=-1<<20;
int Get_Status(int old, int seg, int &cnt)
{
int now = old | seg;
for (int i = 0; i<9; i++)
{
if ((old & tri[i]) != tri[i] && (now & tri[i]) == tri[i])
cnt++;
}
return now;
}
int minimax(int player,int state,int ca,int cb)
{
if (ca >= 5)
return 1;
if (cb >= 5)
return -1;
if (state == STATUS)
return ca > cb ? 1 : -1;
int remain = (~state) & STATUS;
if(player==1)
{
int ans=-1;
while(remain)
{
int seg = remain & (-remain);
int ta = ca, tb = cb;
int now = Get_Status(state, seg, ta), tmp;
if(ta>ca)
tmp=minimax(player,now,ta,cb);
else
tmp=minimax(player^1,now,ta,cb);
if(tmp>ans)
ans=tmp;
remain-=seg;
}
return ans;
}
else{
int ans=1;
while(remain)
{
int seg = remain & (-remain);
int ta = ca, tb = cb;
int now = Get_Status(state, seg, tb), tmp;
if(tb>cb)
tmp=minimax(player,now,ca,tb);
else
tmp=minimax(player^1,now,ca,tb);
if(tmp<ans)
ans=tmp;
remain-=seg;
}
return ans;
}
}
int main()
{
int t, cas = 0;
cin>>t;
while (t--)
{
int n, u, v;
cin>>n;
int cnt = 0, state = 0;
int ca = 0, cb = 0;
while (n--)
{
cin>>u>>v;
int ta = ca, tb = cb;
state = Get_Status(state, 1 << mat[u][v], (cnt & 1) ? cb : ca);
if (ta == ca && tb == cb)
cnt++;
}
int ans;
if(cnt & 1)
ans=minimax(0,state,ca,cb);
else
ans=minimax(1,state,ca,cb);
char ch=(ans==1)?'A':'B';
cout<<"Game "<<++cas<<": "<<ch<<" wins."<<endl;
}
return 0;
}
2. alpha-beta算法
#include <iostream>
#include <cstdio>
using namespace std;
int mat[11][11] =
{
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 2, 3, 4, 0, 0, 0, 0, 0 },
{ 0, 1, 2, 0, 0, 5, 6, 0, 0, 0, 0 },
{ 0, 0, 3, 0, 0, 7, 0, 9, 10, 0, 0 },
{ 0, 0, 4, 5, 7, 0, 8, 0, 11, 12, 0 },
{ 0, 0, 0, 6, 0, 8, 0, 0, 0, 13, 14 },
{ 0, 0, 0, 0, 9, 0, 0, 0, 15, 0, 0 },
{ 0, 0, 0, 0, 10, 11, 0, 15, 0, 16, 0 },
{ 0, 0, 0, 0, 0, 12, 13, 0, 16, 0, 17 },
{ 0, 0, 0, 0, 0, 0, 14, 0, 0, 17, 0 }
};
int tri[9] = { 7, 152, 52, 352, 34304, 3200, 71680, 12544, 155648 };
int STATUS = (1 << 18) - 1;
int Get_Status(int old, int seg, int &cnt)
{
int now = old | seg;
for (int i = 0; i<9; i++)
{
if ((old & tri[i]) != tri[i] && (now & tri[i]) == tri[i])
cnt++;
}
return now;
}
int MaxSearch(int state, int alpha, int ca, int cb);
int MinSearch(int state, int beta, int ca, int cb)
{
if (ca >= 5)
return 1;
if (cb >= 5)
return -1;
if (state == STATUS)
return ca > cb ? 1 : -1;
int ans = 1;
int remain = (~state) & STATUS;
while (remain)
{
int seg = remain & (-remain);
int ta = ca, tb = cb;
int now = Get_Status(state, seg, tb), tmp;
if (tb > cb)
tmp = MinSearch(now, beta, ca, tb);
else
tmp = MaxSearch(now, ans, ca, tb);
if (tmp < ans)
ans = tmp;
if (tmp <= beta)
return ans;
remain -= seg;
}
return ans;
}
int MaxSearch(int state, int alpha, int ca, int cb)
{
if (ca >= 5)
return 1;
if (cb >= 5)
return -1;
if (state == STATUS)
return ca > cb ? 1 : -1;
int ans = -1;
int remain = (~state) & STATUS;
while (remain)
{
int seg = remain & (-remain);
int ta = ca, tb = cb;
int now = Get_Status(state, seg, ta), tmp;
if (ta > ca)
tmp = MaxSearch(now, alpha, ta, cb);
else
tmp = MinSearch(now, ans, ta, cb);
if (tmp > ans)
ans = tmp;
if (tmp >= alpha)
return ans;
remain -= seg;
}
return ans;
}
int main()
{
int t, cas = 0;
cin>>t;
while (t--)
{
int n, u, v;
cin>>n;
int cnt = 0, state = 0;
int ca = 0, cb = 0;
while (n--)
{
cin>>u>>v;
int ta = ca, tb = cb;
state = Get_Status(state, 1 << mat[u][v], (cnt & 1) ? cb : ca);
if (ta == ca && tb == cb)
cnt++;
}
int ans;
if (cnt & 1)
ans = MinSearch(state, -1, ca, cb);
else
ans = MaxSearch(state, 1, ca, cb);
char ch=(ans==1)?'A':'B';
cout<<"Game "<<++cas<<": "<<ch<<" wins."<<endl;
}
return 0;
}
【实验结果及结论】
结果：
1. minimax算法未剪枝时，能得出结果，但是耗时太大，特别是该检验数据都是5层以上。Oj平台测试如下，显示时间超出（TLE）
2. 加入alpha-beta剪枝后
耗时454ms,这也是poj的边界数据结果。
