2019-10-16

poj 1085 Triangle War 极小化极大+alphabeta剪枝

缘起

今天来研究一下极大极小搜索+alphabeta剪枝算法. poj 1085 Triangle War

分析

1	A和B两个玩家在下面的图中玩三角形战争游戏.

1
2
3

玩法是A和B用火柴棒轮流填充图中的虚线.A先填. 每根虚线只能被填充一次. 如果一个三角形的最后一条边被某个
选手填充了, 则该三角形被该选手赢得了并且该选手可以继续填. 游戏在所有的虚线被填充之后结束. 赢得三角形
数量最多的选手将赢得比赛. 例如

A填充2--5, 则A将赢得三角形A, 并且还能继续填充(即下一轮还是A走的而不是B), A下一步就填充了3--5.
然后B要走的话, 可以选择填充2--3, 5--6, 6--9, 这样B就赢得了3个三角形.

在本问题中, 你被给定了游戏开始的几步. 也就是给你一个三角形游戏的残局. 从这个残局出发, 你要推测哪个
选手将获胜——假设每个选手都按照最理想的走法.

【输入】
多样例
第一行是样例数. 每个样例都会以m（6 <= m <= 18）开头. 表示已经走的步数. 然后m行表明已经走的步数.
每行是 i j 这个样子. 表示此步是将 i--j 连在了一起.

【输出】
对每个样例，输出A wins. 或者  B wins.

【样例输入】
4 
6 
2 4 
4 5 
5 9 
3 6 
2 5 
3 5 
7 
2 4 
4 5 
5 9 
3 6 
2 5 
3 5 
7 8 
6 
1 2 
2 3 
1 3 
2 4 
2 5 
4 5 
10 
1 2 
2 5 
3 6 
5 8 
4 7 
6 10 
2 4 
4 5 
4 8 
7 8 

【样例输出】
Game 1: B wins. 
Game 2: A wins. 
Game 3: A wins. 
Game 4: B wins.

【限制】
1s

本题因为两个都是理智的选手, 所以本题考查的算法很明显就是极大极小搜索之alphabeta剪枝。不懂极大极小搜索+alphabeta剪枝原理的童鞋可以参考【1】

首先, 我们要考虑如何压缩状态（因为总共18条边, 三边就能组成一个三角形, 如果这都没想到状态压缩的话, 你题目怕是做少了~ ^_^）

首先用mat[11][11]矩阵, 其中 mat[i][j] = k （0<=k<18）表示顶点i和顶点j连线是第几条边（边的索引从0开始, 一直到17, 为什么从0开始? 因为状态压缩，比特位从0开始的）

然后既然我们已经维护起来了 0~ 17 这18条边, 我们就可以使用

1	int FULL = (1<<18)-1

表示所有边都已经连上了. 对于中间状态, 我们维护一个int cur（0<=cur<=FULL）表示当前哪些边已经连上了.

然后，我们可以使用int triangle[9] 刻画9个三角形（每个三角形就是三条边，而这三条边都有索引）.

使用两个变量cnta和cntb维护一下A和B拥有的三角形数量以及一个bool变量player表示当前是谁走棋.

好了, 现在读入数据, 每次读入一条边, 首先是A先填. i–j, 我们就用位运算维护cur, 怎么知道出现了三角形呢? 只需要用cur和这9个三角形做&运算就知道了. 一旦发现某位选手赢得了某个三角形, 我们就维护相应的cnta或者cntb变量, 并且维护相应的flag变量.

读入数据完毕之后, 开始真正的博弈部分. 此时cur、cnta、cntb、player 变量都有自己各自的值了，他们共同刻画了当前的残局.

首先要明白, 本游戏不可能平局. 因为总共9（奇数）个三角形. 而且对于本题，极大极小搜索不设置搜索深度. 因为本题深度比较浅. 那么根据【1】，搜索递归的出口就只能是终局. 也就是

cnta、cntb中的一个已经>=5（超过了9的一半）,如果是cnta>=5, 返回1，表示A胜, 否则返回0表示B胜
达到了FULL, 此时根据cnta和cntb的大小定胜负. 返回cnta>cntb

所以概括起来, 本题就是先模拟, 得到残局的状态刻画——cnta、cntb、cur、player

然后调用【1】中的alphabeta算法对当前局面进行评估, 评估结果是1的话, 打印 A胜, 评估结果是0的话, 则打印B胜.

//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int FULL = (1<<18)-1, inf = 0x3f3f3f3f; // 所有边都连上了
int mat[11][11]={ //10个顶点之间的连线编号, 0索引不用, 这个二维数组仅仅在读取数据模拟的时候有用, 例如 mat[1][2]=0 表示连接1和2的边是0号边, 这时一个对称矩阵
	{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}; //9个三角形组成的边状态压缩一下
int cur, cnta, cntb,m; // 当前哪些边连上了, cnta是A赢取的三角形数量. cntb是B赢取的三角形数量
bool player; // true表示当前是A走棋, false表示当前是B走棋

void simulate()
{
	cnta = cntb = cur = 0;
	player = true; // 初始化局面四元组(cnta,cntb, cur, player)
	scanf("%d", &m);
	while(m--)
	{
		int i,j, nxt;
		bool flag = false; // 此步有没有形成三角形?
		scanf("%d%d", &i, &j); // 连mat[i][j]这条边
		nxt = cur | (1<<mat[i][j]); // 连上边之后cur变成的样子
		for (int i = 0; i<9; i++)
		{
			if ((cur & tri[i]) != tri[i] && (nxt & tri[i]) == tri[i]) // 原先没有形成三角形tri[i], 现在形成了
			{
				flag = true; // 形成三角形了
				player?++cnta:++cntb; // 给当前棋手增加赢得的三角形数目
			}
		}
		if (!flag) // 如果此步没有形成三角形的话, 则棋手更换
		{
			player = !player;
		}
		cur = nxt; // 不论有没有形成三角形, cur都要变成nxt了.
	} // 最后 cnta、cntb、player、cur都形成了. 即这四个东西共同刻画了一个残局
}

int ck(int x, int node, int &nxt) // 检查在node的基础上添加边x会不会增加三角形, 返回true表示会, false表示不会. 并且得到下一步的状态nxt 返回此次增加的三角形个数(注意,连一条边未必只增加一个三角形哦~)
{
	nxt = node | x; // 连线状态改变为nxt
	int ans =0; 
	for (int i = 0;i<9; i++)
	{
		if ((node&tri[i])!=tri[i] && (nxt & tri[i])==tri[i]) // 增加了三角形tri[i]
		{
			++ans;
		}
	}
	return ans;
}
int Min(int, int, int, int); // 要声明函数原型, 不然编译报错
int Max(int node, int alpha, int a, int b) // a(b)是迄今（不包括node这一步）A(B)赢得的三角形个数,
{
	if (a>=5)
	{
		return 1;
	}
	else if (b>=5) 
	{
		return 0;
	}
	else if (node==FULL)
	{
		return a>b;
	} // 三种终局
	int ans = 0;
	int remains = FULL & ~node; // 如果尚未分出胜负, 就首先看看还有哪些边没连上
	while(remains) // 遍历所有可行状态
	{
		int lowbit = remains & (-remains), nxt, d, val; // 此次可行的走法——即连接lowbit这条边
		if (d=ck(lowbit, node, nxt)) // 如果连上lowbit之后导致产生了新的三角形, 并且状态更新为nxt, 并且因为连接lowbit而新增的三角形个数是d
		{
			val = Max(nxt, alpha, a+d, b); // 因为产生了新的三角形, 所以继续是A走,注意, 对于这种情形, 我们要继续传入alpha
		}
		else
		{
			val = Min(nxt, ans, a, b); // 没有新的三角形产生, 换B走
		}
		ans = max(ans, val);
		if (ans>=alpha) // beta剪枝
		{
			return ans;
		}
		remains-=lowbit;
	}
	return ans;
}

int Min(int node, int beta, int a, int b)
{
	if (a>=5)
	{
		return 1;
	}
	else if (b>=5) 
	{
		return 0;
	}
	else if (node==FULL)
	{
		return a>b;
	} // 三种终局
	int ans = 1;
	int remains = FULL & ~node; 
	while(remains)
	{
		int lowbit = remains & (-remains), nxt, d, val; 
		if (d=ck(lowbit, node, nxt))
		{
			val = Min(nxt, beta, a, b+d); // 因为产生了新的三角形, 所以继续是B走
		}
		else
		{
			val = Max(nxt, ans, a, b); // 没有新的三角形产生, 换A走
		}
		ans = min(ans, val);
		if (ans<=beta) // alpha剪枝
		{
			return ans;
		}
		remains-=lowbit;
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		simulate(); // 模拟
		int ans = player?Max(cur, 1, cnta, cntb):Min(cur, 0, cnta, cntb); // 如果是A走,调用Max计算得分, 如果是B走, 调用Min计算得分, 计算的得分都是站在A(先行者)的角度进行评判的得分, 这里的alpha上界选用1,下界beta选用0
		ans?printf("Game %d: A wins.\n", i):printf("Game %d: B wins.\n", i);
	}
	return 0;
}

ac情况

Status	Accepted
Time	172ms
Memory	100kB
Length	3358
Lang	C++
Submitted	2019-10-17 15:21:10
Shared
RemoteRunId	20966667

注意, 本题极大极小搜索的模型其实和【1】中还是有些出路的~ 因为本题不一定是极大极小交替进行的!!! 但是为什么【1】中的板子依旧可行呢?

也就是我们的极大极小搜索树可能是下面这个样子

但是不用慌, 对于子节点继续是求同样属性的极值的（即最大节点的子节点依旧是最大节点）, 则只需要将相应的alpha、beta继续传入即可~ 该剪枝依旧剪枝. 没关系的~ 仔细想想就知道是正确的了~

参考

【1】https://yfsyfs.github.io/2019/10/17/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2%E4%BB%A5%E5%8F%8Aalphabeta%E5%89%AA%E6%9E%9D%E4%BC%98%E5%8C%96/