📄 博弈.asp.htm
字号:
<html><head><script language="JavaScript">
helpstat = false;
stprompt = true;
basic = false;
function thelp(swtch){
if (swtch == 1){
basic = false;
stprompt = false;
helpstat = true;
} else if (swtch == 0) {
helpstat = false;
stprompt = false;
basic = true;
} else if (swtch == 2) {
helpstat = false;
basic = false;
stprompt = true;
}
}
function AddText(NewCode) {
document.myform.txtcontent.value+=NewCode
}
function openscriphtml()
{
newwin=window.open('htmledit/editor.html','','width=544,height=294');
newwin.focus();
}
function runEx(){
//alert('请注意，按下确定将生成页面，按下后请稍后....');
var winEx = window.open("", "winEx", "width=300,height=200,status=yes,menubar=yes,scrollbars=yes,resizable=yes"); winEx.document.open("text/html", "replace");
winEx.document.write(unescape(event.srcElement.parentElement.children[2].value));
winEx.document.close();
}
function openScript(url, width, height) {
var Win = window.open(url,"openScript",'width=' + width + ',height=' + height + ',resizable=1,scrollbars=yes,menubar=yes,status=yes' );
}
</script><script language="Javascript">
<!-- hide
function insertsmilie(smilieface){
document.frmAnnounce.body.value+=smilieface;
}
// -->
</script>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="大榕树编程世界Pascal,算法,数据结构,信息学竞赛">
<link href="%B2%A9%DE%C4.asp_files/style.css" rel="stylesheet">
<title>寻找必败态:博弈问题的快速解法—大榕树编程世界|Pascal,算法,数据结构,信息学竞赛</title><!-- base --></head>
<body topmargin="0" bgcolor="#ffffff">
<table align="center" border="0" cellpadding="0" cellspacing="1" height="78" width="755">
<tbody><tr>
<td align="center" valign="middle" width="120"><a href="http://www.mydrs.org/index.asp"><img src="%B2%A9%DE%C4.asp_files/drs.GIF" alt="大榕树——让我们共成长！" border="0" height="50" width="100"><br>
<span style="font-size: 12px;"><font color="#009900"><strong>大榕树 </strong>MyDrs.org</font></span></a></td>
<td align="center" valign="middle" width="520">
<!-- Banner广告代码 -->
<img src="%B2%A9%DE%C4.asp_files/banner.gif" height="60" width="468">
</td>
<td align="center" width="*">
</td>
</tr>
</tbody></table>
<table align="center" border="0" cellpadding="0" cellspacing="0" width="755">
<tbody>
<tr>
<td bgcolor="#333333">
<table border="0" cellpadding="4" cellspacing="1" width="100%">
<tbody><tr>
<td colspan="2" bgcolor="#a9d46d" height="21">您的位置：<a href="http://www.mydrs.org/" class="title1">首页</a>\<a href="http://www.mydrs.org/program/default.asp" class="title1">编程世界</a>
| <a href="http://www.mydrs.org/program/default.asp?classid=2">
Logo语言
</a> |
| <a href="http://www.mydrs.org/program/default.asp?classid=3">
<font color="red">Pascal语言</font>
</a> |
| <a href="http://www.mydrs.org/program/default.asp?classid=5">
信息学奥赛
</a> |
<a href="http://bbs.mydrs.org/list.asp?boardid=4" target="_blank">
入门论坛 </a> | | <a href="http://bbs.mydrs.org/list.asp?boardid=13" target="_blank">
提高论坛 </a> | </td>
</tr>
<tr> <form method="post" name="myform" action="ru_query.asp"></form>
<td colspan="2" bgcolor="#f4faed">
| <a href="http://www.mydrs.org/program/index.asp?classid=3">Pascal语言</a>>><a href="http://www.mydrs.org/program/index.asp?classid=3&Nclassid=6">算法与技巧</a>>>寻找必败态:博弈问题的快速解法
本站全文搜索:
<input name="action" value="content" type="hidden"><input name="keyword" size="20" value="" maxlength="50" onmouseover="this.focus()" onfocus="this.select()" class="txt1" style="border: 1px solid ;" type="text">
<input name="Submit" value="搜索" class="input1" type="submit">
<!--begin margeen-->
<marquee height="1" hspace="5" id="srcolltext" onmouseout="srcolltext.start()" onmouseover="srcolltext.stop()" scrollamount="2" scrolldelay="10" width="90%" align="center"><img src="%B2%A9%DE%C4.asp_files/new.gif" height="15" width="35">
友情提示：
<script language="javascript" src="%B2%A9%DE%C4.asp_files/movetxt.js"></script><a href="http://www.mydrs.org/program/list.asp?id=570" target="_self">NOIP2004普及组提高组官方<b>测试数据</b></a> <a href="http://www.mydrs.org/program/list.asp?id=566" target="_self">NOIP2004初赛提高组官方<b>参考答案</b></a> <a href="http://www.mydrs.org/contact.asp" target="_blank">积极投稿或发表精华帖子，就有机会发表在分区联赛指定刊物《学生计算机世界》！</a>
</marquee>
<!--end-->
</td>
</tr>
<tr>
<td colspan="2" bgcolor="#ffffff">
<center>
<b><font size="3">寻找必败态:博弈问题的快速解法</font></b><br>
<a href="http://www.mydrs.org/" target="_blank">http://www.mydrs.org</a> 2005-1-9 <a href="http://www.mydrs.org/" target="_blank">大榕树</a>
</center>
<p>
</p><blockquote> <br>
<strong>寻找必败态——一类博弈问题的快速解法<br></strong>
<p> 博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。寻找必败态即为针对此类试题给出一种解题思路。<br> 此类问题一般有如下特点：<br> 1、<font color="red">博弈模型为两人轮流决策的非合作博弈。</font>即两人轮流进行决策，并且两人都使用最优策略来获取胜利。<br> 2、<font color="red">博弈是有限的。</font>即无论两人怎样决策，都会在有限步后决出胜负。<br> 3、<font color="red">公平博弈。</font>即两人进行决策所遵循的规则相同。<br> 以下题目都属于这一类：<br> <a href="http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1740" target="_blank"><font color="#000000">POJ1740 A New Stone Game</font></a><br> <a href="http://acm.mipt.ru/judge/bin/problems.pl?problem=100&sort=ID&lang=en" target="_blank"><font color="#000000">MIPT100 Nim Game -- who is the winner? </font></a><br> <a href="http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1704" target="_blank"><font color="#000000">POJ1704 Georgia and Bob</font></a><br> <a href="http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=4163" target="_blank"><font color="#000000">POJ1067 取石子游戏</font></a><br></p><br>
<p> 本着先理论后实践的原则，本文先对“寻找必败态”做出理论上的解释：<br> 要理解这种思想，首先要明白什么叫必败态。说简单点，必败态就是<font color="red">“在对方使用最优策略时，无论做出什么决策都会导致失败的局面”</font>。其他的局面称为胜态，值得注意的是<font color="red">在胜态下做出错误的决策也有可能导致失败</font>。此类博弈问题的精髓就是<font color="red">让对手永远面对必败态。</font><br> 必败态和胜态有着如下性质：<br> 1、<font color="red">若面临末状态者为获胜则末状态为胜态否则末状态为必败态。</font><br> 2、<font color="red">一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。</font><br> 3、<font color="red">一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态</font><br> 这三条性质正是博弈树的原理，但博弈树是通过计算每一个局面是胜态还是必败态来解题，这样在局面数很多的情况下是很难做到的，此时，我们可以利用人脑的推演归纳能力找到必败态的共性，就可以比较好的解决此类问题了。</p><br>
<p><br> 下面就通过实际题目来做一些分析：<br> 例1 <a href="http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1740" target="_blank"><font color="#000000">POJ1740 A New Stone Game</font></a><br> 题目大意是：有N堆石子，两人轮流进行操作，每一次为“操作者指定一堆石子，先从中扔掉一部分（至少一颗，可以全部扔掉），然后可以将该堆剩下的石子中的任意多颗任意移到其他未取完的堆中”，操作者无法完成操作时为负。<br> 分析：<br> 只有一堆时先手必胜。<br> 有两堆时若两堆相等则后手只用和先手一样决策即可保证胜利，后手必胜。若不同则先手可以使其变成相等的两堆，先手必胜。<br> 有三堆时先手只用一次决策即可将其变成两堆相等的局面，先手必胜。<br> 有四堆时由于三堆必胜，无论先手后手都想逼对方取完其中一堆，而只有在四堆都为一颗时才会有人取完其中一堆，联系前面的结论可以发现，只有当四堆可以分成两两相等的两对时先手才会失败。<br> 分析到这里，题目好像已经有了一些眉目了，凭借归纳猜想，我们猜测必败态的条件为“堆数为偶数（不妨设为2N），并且可以分为两两相等的N对”。<br> 下面只需证明一下这个猜想。其实证明这样的猜想很简单，只用检验是否满足必败态的三条性质即可。<br> 首先，末状态为必败态，第一条性质符合。<br> 其次，可以证明任何一个胜态都有策略变成必败态（分奇数堆和偶数堆两种情况讨论）。<br> 最后，证明任何一个必败态都无法变成另一个必败态（比较简单）。<br> 由于篇幅关系，这里就不具体证明了，如果有兴趣可以自己试试∶Ｐ<br> 接下来的程序就相当简单了，只用判断一下即可。</p><br>
<p> 有些题则比这一题的条件隐蔽许多，例如：<br> 例2 <a href="http://acm.mipt.ru/judge/bin/problems.pl?problem=100&sort=ID&lang=en" target="_blank"><font color="#000000">MIPT100 Nim Game -- who is the winner? </font></a><br> 题目大意是：有N堆石子，两人轮流取，每次可以从任意一堆中取任意多颗（但至少一颗），谁先取完谁胜。<br> 分析：<br> 还是用按照“手推小数据=〉猜想=〉证明”的模式。<br> 一堆时先手必胜。<br> 两堆时若两堆相等则先手必败，否则先手胜。<br>
三堆的情况就有点复杂了，此时，我们只好借助博弈树来在小范围内求解，从这些解中我们可以
看出，对于由两个不同数字构成的两元组，都有且仅有一个三元必败态包含它，这又意味着什么呢？我们定义一个函数F(a,b)，表示“包含a,b的三元必败
态中的第三数”，则有<br> F(1,2)=3,F(1,3)=2,F(1,4)=5,F(1,5)=4,F(1,6)=7,F(1,7)=6...<br> F(2,1)=3,F(2,3)=1,F(2,4)=6,F(2,5)=7,F(2,6)=4,F(2,7)=5...<br> F(3,1)=2,F(3,2)=1,F(3,4)=7,F(3,5)=6,F(3,6)=5,F(3,7)=4...<br> ..................................................................................
<br> ..................................................................................
<br> 敏锐的选手马上会发现，这个F(a,b)不就是a XOR b的结果么？做到这里，答案就在眼前了，'XOR'运算恐怕就是本题的关键。<br> 继续求出一些四元必败态，这个性质仍然符合，于是我们猜想，必败态即为“所有堆的石子数XOR运算后结果为零的局面”。这也解释了为什么一堆石子必胜，两堆石子仅在相等时必败。<br> 接下来又是证明：<br> 依旧判断是否符合三条性质。<br> 第一条第三条显然满足，关键就是第二条。<br> 必胜态下，设所有堆石子XOR后结果为N，将其写成二进制，则至少有一堆石子写成二进制后在N的最高位上为一，则可以证明从这堆石子中取可以变成必败态，这里还是留给有兴趣的选手:)<br> 这一题就明显没有上一题轻松了，而且这是个经典问题，结论可以记下来。下面这个例子就是例2的强化版：</p><br>
<p> 例3 <a href="http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1704" target="_blank"><font color="#000000">POJ1704 Georgia and Bob</font></a><br> 题目大意是：一个1*M的棋盘上有N个棋子，初始位置一定，两人轮流操作，每次移动一枚棋子，要求只能向左移且至少移动一格，而且不能到达或经过以前有棋子的格子，谁无法移动棋子就算输。<br> 分析：<br> 乍一看这一题棋子移动还要受其他棋子的限制，好像无法求出通解，但仔细分析会发现别有洞天。<br>
一个棋子每一次向左移的最大步数是固定的，而且随着移动减少，不是和取石子很像么？那么和
取石子的区别在哪呢？就在于每一次移动时都会让右边相邻的那颗棋子移动空间变大，这样就和取石子只减不增有所不同了，我们应该怎样解决这个问题呢？<br> 我们并不放弃将其与我们熟悉的取石子对应，但我们将策略做小小的变动：<br>
将棋子从右端向左端每相邻两个分为一对，如果只剩一个就将棋盘左端加一格放一颗棋子与之配
对，这样配对后好像和以前没有什么区别，但决策时就方便多了，因为我们大可不必关心组与组之间的距离，当对手移动一组中靠左边的棋子时，我们只需将靠右的
那一颗移动相同步数即可！同时我们把每一组两颗棋子的距离视作一堆石子，在对手移动两颗棋子中靠右的那一颗时，我们就和他玩取石子游戏，这样就把本题与取
石子对应上了。<br> 本例说明有许多模型看似复杂，但经过一些巧妙的变换，便可以转化成一些我们熟悉的模型，同时也充分体现了博弈的灵活。<br> 如果说前面的例子是介绍这种思想的运用的话，下面的方法就是讲这种思路的优越性了，因为这一题并不是走的“手推小数据=〉猜想=〉证明”的老路，而是直接利用性质推导必败条件。<br> </p><br>
<p> 例4 url=http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=4163]POJ1067 取石子游戏[/URL]<br> 题目大意是：......题目本来就是中文的-_-b。<br> 分析：<br>
刚拿到这一题时，我不加思索的猜想必败态为“两堆石子的数目是2：1”，用性质判定：第一
条显然符合，第二条分情况讨论每一种“胜态”都有一种固定的方法变成“必败态”，再看第三条，设第一堆有N颗，第二堆有2*N颗，则无论怎样拿都无法让第
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -