北京大学ACM暑期课讲义-lcc-博弈

ACM中的博弈北京大学ACM队最常见情况：SG博弈1二人博弈2对于同一局面,两个游戏者可操作的集合完全相同3游戏总可以在有限步之内结束4假定:两个人都"足够聪明"5无法进行任何操作时游戏结束,不能操作的一方为负----5的反面条件：不能操作胜为另一种博弈取石子类经典问题取石子1：有一堆n个石子两人轮流取每次可以取1..m个没得取的判负取石子2：有K堆石子，每堆ni个，两人轮流取，每次可以从某一堆中取1..m个没法取石子的判负N局面和P局面必在有限步结束在双方都采用最佳策略的前提下,任一局面不是先手必胜就是后手必胜规定:先手胜为N局面,后手胜为P局面此类问题一般问某一个局面是先手必胜还是先手必败附加问题：先手必胜时，输出当前一步可选步最终局面都是P局面对于一个局面,若至少有一种操作使它变为P局面,则它是N局面如果当前是我的回合，我有一种操作选择，使得下回合对方面对的局面是个必输局面，那么我的局面就是必胜局面问题：如何寻找这一步操作选择？（输出解）对于一个局面,无论如何操作都使它变为N局面,则它是P局面如果当前是我的回合，无论怎么做，轮到对方时，对方都存在一种必胜策略，那么当前我面对的局面就是必败局面例：取石子问题有一堆n个石子两人轮流取每次可以取1..m个没得取的判负在游戏中，n不断变化，m是定值一个局面可以用当前的石子数n来表示n=0必败n=1..m都是必胜局面n=m+1是必败局面（为什么？）n=m+2..2m+1是必胜局面（为什么？）将博弈游戏看做图将游戏中间的状态看做顶点性质2：对于同一局面,两个游戏者可操作的集合完全相同点对当前执行者是无差别的将状态的转移看做边

性质3：游戏总可以在有限步之内结束

这是一个有向无环图N=0N=2N=mN=m+1N=1取石子问题示例顶点与必胜必败态每个顶点都会对应N局面必胜或/P局面必败N点（必胜点）或者P点（必败点）如果顶点有边指向P点，则该点为N点（必胜点）如果顶点没有边指向P点（所有出边指向N点）则该点为P点（必败点）N=0N=2N=mN=m+1N=1取石子问题示例N=0N=1N=2N=mN=m+1判断先手必胜还是必败图是有向无环图通过拓扑排序对图的每个点进行染色，从而确定每个点的状态必胜时要输出一步可行解：寻找该状态对应的N节点指向的P节点的那条边（一定存在）算法复杂度和状态数有关一堆石子的状态数为NK堆石子的状态是一个K维向量<n1,n2,…nk>状态数为n1*n2*…*nk太多了吃不消！SG函数对顶点赋一个SG值设顶点v，有v->v1,v->v2,…v->vtsg(v)=min(N–{sg(v1),sg(v2),…,sg(vt)})sg(v)定义为没有出现在{sg(v1)..sg(vt)}中的最小自然数同样可以用拓扑序对节点计算sg值SG函数与NP局面的关系初始节点（必须是P节点）没有出边， sg=0若v有边指向某sg(vi)=0的vi，则sg(v)>0若v没有边指向某sg(vi)=0的vi，则sg(v)=0所有P节点sg=0所有N节点sg>0N=0N=2N=mN=m+1N=1取石子问题示例N=0N=1N=2N=mN=m+1Sg(0)=0Sg(1)=1Sg(2)=2Sg(m)=mSg(m+1)=0取石子游戏一维：只有一堆石子sg(n)=min(N–{sg(n-1),sg(n-2),…sg(n-m)})n先手必胜当且仅当sg(n)>0二维的石子游戏:两堆石子n1,n2状态：<n1,n2>sg(<n1,n2>)=?断言：sg(<n1,n2>)=sg(n1)^sg(n2)为两个一维sg函数的异或sg(<n1,n2>)=sg(n1)^sg(n2)证明要点：sg(<n1,n2>)=sg(n1)^sg(n2)满足sg函数的性质1若sg(<n1,n2>)=x则存在操作使得 <n1,n2>-><n3,n4>且sg(<n3,n4>)=0..x-12若sg(<n1,n2>)=x不存在操作使得 <n1,n2>-><n3,n4>且sg(<n3,n4>)=x1若sg(<n1,n2>)=x则存在操作使得<n1,n2>-><n3,n4>且sg(<n3,n4>)=0..x-1

归纳法：

设a1=sg(n1)a2=sg(n2)

假设对子状态成立，sg(<n3,n4>)=sg(n3)^sg(n4)

那么必然有n3=n1,n4<n2

或n3<n1,n4=n2 (对应从某一堆里面取走一些石子)

根据sg函数的定义

存在n3使得sg(n3)=0..a1-1

存在n4使得sg(n4)=0..a2-1

对0<=y<x存在sg(n3)^a2=y或a1^sg(n4)=y扩展到K维的情况若a1^a2^…^ak=x,任取y<x存在i，使得存在bi<ai，且a1^a2^..^a(i-1)^bi^a(i+1)…^ak=y这要求：bi=ai^(x^y)如何找出ai?设x^y的最高位是t位（有t+1比特）X的t位必须是1（为什么？注意y<x）a1..ak中必须有一个ai的t位是1ai^(x^y)<ai（为什么？）当y=0时注意这里我们解决了“输出一个解的问题”<n1,n2…nk>的子状态的sg函数形成的集合包含{0..x-1}但是2：不包含x为什么？令y=xai^(x^x)=ai<ai矛盾这样一来就有sg(<n1,n2,..nk>)=x=sg(n1)^..^sg(nk)成功降维维度变化的局面取石子问题3：有n个石子排成一列每次可以拿走1..m个连续的石子<10><4,4><4,1,2>Sg函数的应用场景多维理解：一个游戏局面经过一步变换后可以变成几个同样规则的子游戏一般是一维变成多维每个子游戏是一维类比：递归思想？DP中的重复子结构？双方每步可以从并行存在的多个子游戏中选择一个操作维度可以进一步变得更多可能存在一个子游戏，由同一个玩家连续两次对其操作对sg函数来说：怎么变都无所谓，它只关心所有子局面的异或值Sg(x)的变量x永远是一维的。竞赛中的博弈题策略利用最简单的N-P图染色来判定博弈搜索：用搜索方式来对图染色

可以看做α-β剪枝的特例转化为规则的sg函数类问题

如果还是状态太多，需要进一步寻找sg函数的规律，而不是直接用公式算打表寻找P局面的规律其他类型的博弈Sg函数的博弈是最基础的博弈问题竞赛中常出现非sg函数问题前面提到的没有办法操作反而获胜的情况需要现场构造策略的问题有些问题与斐波那契数列，黄金分割数有关思考题加强版取石子有K堆每堆ni个每人可以每次选最多P堆从选出的每堆取走不超过m个石子没得取的输思考：p=1变成sg异或P的时候这一位上的变数从0-1变到0-P将异或操作改为：对每个二进制位单独累加mod(P+1)2011成都赛区A题AliceandBobK堆石子两人操作可以1从某一堆拿走一个如果该堆在此之后没有石子了，就消失2合并