博弈论又被称为对策论(games

《博弈论又被称为对策论(games》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、博弈MDZfirst2008.7.12博弈论又被称为对策论（GamesTheory),是研究具有斗争或竞争性质现象的理论和方法，它既是现代数学的一个新分支，也是运筹学的一个重要学科。我们研究的是“双人全信息零和博弈”。胜败NIM(1)一排石头的游戏N块石头排成一行，每块石头有各自固定的位置。两个玩家依次取石头，每个玩家每次可以取其中任意一块石头，或者相邻的两块石头，石头在游戏过程中不能移位（即编号不会改变），最后能将剩下的石头一次取光的玩家获胜。问：是否有必胜策略？NIM(2)一堆石头的游戏一共有N块石头。两个玩家依次取石头，每个

2、玩家每次至少取1块，至多取k块。最后能将剩下的石头一次取光的玩家获胜。问：是否有必胜策略？NIM(2)一堆石头的游戏一共有N块石头。两个玩家依次取石头，每个玩家每次至少取1块，至多取k块。与前面的规定相反，最后取光石头的玩家输。问：是否有必胜策略？NIM(3)“拈”游戏分析有k堆石头，第i(0<=i

3、ABA……的顺序轮流取石头。每次选择任意一堆，并且可以在该堆中取任意块石头（至少取1块），能将剩下的石头一次取光的玩家获胜。问：A应该如何分堆，才能保证必胜？NIM(3)“拈”游戏分析有k堆石头，第i(0<=i0)块，第二堆有M(M>0)块。两个玩家轮流取石头，每次可以从任一堆中取任意块石头（至少取1块），也可以

4、从两堆中各取相同数量的石头（至少各取1块）。最后能将剩下的石头一次取光的玩家获胜。问：是否有必胜策略？一般而言，第n组不安全局面(an,bn)可以由以下定义得到：(1)a1=1，b1=2。(2)若a1，b1，a2，b2，……，an-1，bn-1已经求得，则定义an为未出现在这2n-2个数中的最小整数。(3)bn=an+n。不安全局面表N12345678910…an13468911121416…bn25710131518202326…可以证明，有下述公式可以计算出全部不安全局面：a=(1+sqrt(5))/2b=(3+sqrt(5)

5、)/2an=[a*n]bn=[b*n]n012345678Fn1235813213455Fibonacci数列各个bn恰好是an后面加一个0，每个an最右边有偶数个连续的0。POJ1067取石子游戏POJ1740ANewStoneGamePOJ2234MatchesGamePracticePOJ1082.CalendarGame游戏从一个日期开始，范围是从January1,1900到November4,2001，Adam和Eve轮流走，Adam先走。每次可以把当前的日期移动到第二天或下个月的同一天（如果存在的话，并且不能超过200

6、1年11月4日）。最后能把这个日期移动到November4,2001的人获胜。两个人都非常聪明，都遵循最佳策略。问题：给定起始日期，求Adam能否获胜。POJ1143.NumberGame两个人轮流从2到20这19个数中取数，每次取一个。已经被取过的数的倍数和已经被取过的若干个数的倍数的和都不能被取。最后无数可取的人输。问题：给定当前不能取的数，求如果想必胜，下一步该取什么。极大极小过程POJ3317.StakeYourClaim有一个n*n大小的棋盘，两个玩家0和1轮流在棋盘的空白处画0和1，玩家0先画。棋盘被画满后，每个玩家的

7、得分等于棋盘上等于他编号的最大的连通分量，他所获得的积分等于他们俩个得分的差值。问题：假设这两个玩家都是最好的玩家。给定游戏的中间状态，下一个玩家应画在哪里才能保证得分最多，最高的得分是多少。