博弈树例题

博弈树的启发式搜索问题A方、B方必须是完备博弈，它有三个条件：1、A，B双方轮流博弈。

博弈的结果只有三种情况：A胜，B败；A败，B胜；A，B平手。

2、任一方都了解当前的棋局和历史的棋局。

3、任一方都分析当前的棋局，并能作出有利于自己，而不利于对方的策略。

我们描述博弈过程采用与/或树1、博弈的初始棋局作为初始节点2、‘或’节点与‘与’节点逐层交替出现。

自己一方扩展节点之间是‘或’，对方扩展节点之间是‘与’。

双方轮流扩展。

3、所有能使自己获胜的终局都是本原问题，相应的节点是可解节点。

本问题其实是一个构造博弈树的问题。

对给定的棋局，该棋局中A，B方的棋子数相等，并且轮到A方下。

这样构成一个初始棋局，称一个状态。

当A或B下一个棋子后，又形成一个新的状态。

任何一方都希望自己取得胜利，因此当某一方有多个方案可供选择时，他总是跳最有利于自己而最不利对方的方案。

此时我们站在A的立场上看，可供A选择的方案之间是‘或’的关系，可供B的方案之间是‘与’的关系。

因为主动权在A上，A必须考虑任何一个可能被B选中的方案。

极大极小分析方法的特点：1、它是为其中一方寻找一个最优的行动方案的方法2、为了当前最优的方案，需要对各个方案能产生的后果进行比较，具体地说就是考虑每个方案实施后，对方可能采取的行动，并计算可能的得分4、为了计算得分，需要根据问题的特性定义一个估价函数，用来计算当前博弈树端节点的得分，该得分也称静态估值5、当端节点估值后，再推算父节点的得分，推算方法是对于‘或’节点，选择子节点中最大的得分作为自己的得分，对于‘与’节点，选择子节点中最小的得分作为自己的得分，父节点得得分也称倒退值6、若某一个行动方案能获得最大得倒退值，则它就是当前最好得方案在本问题中，假设棋盘为4*4的矩阵，A方的棋子为1，B方的棋子为－1，空格为0。

我们定义估价函数为：在某一棋局状态，A方棋子可能占满的整行，整列，整斜线总和与B 方棋子可能占满的整行，整列，整斜线总和的差。

信息经济学作业5、解：个，D类型的节点有两个，T类型的节点有6个。

2）博弈树如下：在这个博弈中，I类型的节点只有1个，D类型的节点有两3个，T类型的节点有9个。

3）博弈树如下：I如图，在这个博弈中，I类型的节点只有1个，D类型的节点有4个，T类型的节点有8个。

6、解：博弈树如图所示：如图，在这个博弈中，I类型的节点只有1个，D类型的节点有8个，T类型的节点有24个。

7、解：在此博弈中，I类型的节点只有1个，D类型的节点有32个，T类型的节点有48个。

8、解：按首次行动顺序原则，这个博弈的支付向量的分量排列为：（甲的支付，乙的支付，丁的支付，丙的支付）。

12、解：博弈树如下图所示：根据倒推法,第一步先分析波音公司的行动选择，如果空中客车公司选择研发的话，那么波音公司选择容忍的得益为3，选择价格战的得益为-1，所以波音公司是理性的话，它一定会选择容忍；如果空中客车公司选择不研发，那么波音公司的得益为10。

因此，这个两阶段博弈可以简化为：在这个等价博弈中，空中客车公司选择研发的得益是3，选择不研发的得益是0，因此它肯定会选择研发。

博弈的最终结果为，空中客车公司选择研发，波音公司选择容忍，最终得益为（3,3）.13、解：比如两位家电零售商进了同一种家电，在同一市场上进行销售。

同一种家电的质量正常情况下应该都是差不多的，即对消费者来说，只有价格的区别。

那么，后定价的商人可以根据前一商人的定价，定略低一点的价格，从而获得更高的销量，最终获得更大的总利润，在这场竞争中获胜。

14、解：先动优势例子：（1）在某一门课上，班级中每个小组都要选一个题目做presentation，题目中有难有易，那么提前报名的人就可以抢到比较容易的题目，也能选择本组成员比较感兴趣的题目，那样会给后面的presentation带来很多便利，获得了先动优势，而后选的小组选项越来越少，需求就得不到充分满足了；（2）两个情侣周末准备一起去外面游玩，景点很多，他们还没决定去哪玩，一般先提建议的一方说出自己想去哪玩，只要要求合理一般都会被采纳，，对于先提建议的人来说，他（她）的需求被满足了，获得更大的收益，具有先动优势。

博弈论经典题目
1. 背包问题：
背包问题是贪婪算法求解的一个经典例子，也是动态规划常出现的一个经典最优化算法问题。

背包问题描述是这样的：有一个背包，背包容量限制为V，现有n种物品，每种物品的体积分别是w1, w2, w3, ... wn，而价值分别是v1, v2, v3, ... vn，问如何挑选物品装入背包以使物品价值总和最大。

2. 钓鱼游戏：
钓鱼游戏是由John Von Neumann及Oskar Morgenstern于1944年出版的游戏理论研究的经典题目，它用简单的游戏表示了一个有价值的决策问题：一对捕鱼人去钓鱼，他们的成功机会各不相同，而他们的收入有几乎相同的可能性。

游戏设定两个捕鱼者就一道鱼池进行渔获，鱼库只能容纳两种鱼，一种种鱼可以产生相同价值，不过每个捕鱼者只能抓一种鱼。

他们可以在淘到鱼前决定他们抓取的鱼种以及机率。

3. 亚当斯密矩阵博弈：
亚当斯密矩阵博弈也称为亚当斯博弈，是一种两边博弈，也就是说每一方都可以改变策略，古腾堡武器竞赛中使用的最佳策略最终也确定了该博弈结果。

它是一种形式上可以实时解决的游戏，每一种游戏具有一组有限的可能性。

游戏中，双方都拥有一种完全不同的收益，这些收益对两者来说都是实际易变涉及各自的利益、代价及限制，最终
目的是达到一个最佳方案，也就是哪一方收益最大。

4. 棋盘问题：
棋盘问题是建模和强化学习算法的经典问题，是一种几何回溯问题，主要指一个棋盘下怎样移动国王，使其最终能够到达标记点，而不经过被标记的地方，并且时间费用最少。

棋盘中任何一个标记点在边框联想能表示出一种折线状的运动方式，这样的运动方式通常分为八个半径块，而国王的最终目的地则被标记在其中的任何一个格子上。

完全信息动态博弈习题1、空中客车与波音两家公司在研发新型商业客机方面展开激烈竞争。

波音公司在研发过程中已经处于领先地位，而空中客车正考虑是否参与这场竞争。

加入空中客车不参与竞争，那么它的收益为0，而波音公司将会获得垄断地位，获得10亿美元的收益。

加入空中客车决定参与竞争，则波音公司就不得不决定与空中客车进行和平竞争，还是打价格战。

如果和平竞争，双方各自获得3亿美元的收益；如果打价格战，则客机价格下滑，双方都无法收回研发成本，各损失1亿美元。

请画出博弈树，找出子博弈精炼纳什均衡。

2、考虑可乐行业，可口可乐与百事可乐是两家主要公司，市场规模为80亿美元。

每家公司可以选择是否做广告，广告成本为10亿美元；如果一家企业做广告而另一家不做，则前者强的所有市场；如果两家企业都做广告，则各占一半市场，并付出广告成本；如果两家公司都不做广告，也各占一般市场，但不支付广告成本。

（a）画出博弈支付表，并找出当两家公司同时行动时的纳什均衡（b）假定博弈序贯进行，画出可口可乐公司率先行动时该博弈的博弈树。

（c）在（a）、（b）均衡中，从可口可乐与百事可乐的共同观点来看，哪一个是最佳的，这两家公司要怎样才会有更好的结果？3、假设巨人、太阳神、弗里达三大百货公司正考虑在波士顿两个新的大型购物中心中的一个开设分店。

其中，城市购物中心靠近人口密集的富人区，规模不大，最多只能以两家大百货商场为龙头。

而郊区购物中心地处较远的郊外，相对较穷，能以三家百货商场为龙头。

三家百货公司都不想在两个地方同时开店，因为顾客有相当部分重复，两处都开店无疑是同自己竞争。

每家百货公司都不愿意在一个地方独家经营，拥有多家商场的购物中心能够吸引更多的顾客，顾客总量的增加自然会使商场利润增加。

此外，它们都偏向争夺富人群体的城市购物中心，所以它们必须在城市购物中心（如果这个尝试失败了，它们将会尝试在郊区建立商场）和郊区购物中心（不争取城市市场而直接进入郊区市场）之间作出选择。

博弈问题总结（基础篇）博弈问题总结（基础篇）前⾔最近做的博弈问题的题⽐较多，所以我就汇总了⼀下博弈问题的⼏种题型，⽅便之后的做题博弈论定义博弈论就是指有若⼲个⼈进⾏⼀些对弈，并且默认每个⼈都是最聪明的，不会失误，都可以找到当前的最优解，然后来寻找有没有哪个⼈有必胜/必败的的策略。

A、尼姆博弈为什么叫尼姆博弈呢？因为这是尼姆（英⽂名：Nimm Game）发明的数学游戏。

博弈模型有n堆各若⼲个物品，两个⼈轮流从某⼀堆取任意多的物品，规定每次⾄少取⼀个，多者不限，最后取光者得胜。

分析我们先考虑简单的情况1、n=1这时先⼿必胜，因为他只需要把唯⼀的这⼀堆⽯⼦取⾛就可以了2、n=2若a[1]=a[2]，先⼿必败，因为⽆论先⼿在哪⼀堆⽯⼦中取⾛⼏个，后⼿总能在另⼀堆⽯⼦中取⾛相同的个数若a[1]!=a[2]，我们假设a[1]>a[2]，此时先⼿必胜，因为先⼿可以在第⼀堆⽯⼦中取⾛a[1]-a[2]个，这时两堆⽯⼦的个数相同，下⼀次⽆论后⼿取⾛多少个，先⼿都可以在另⼀堆取⾛同样多个，因此先⼿必胜若a[1]<a[2]，同上，先⼿必胜3、要是n=3或者更⼤呢？我们显然不能像上⾯⼀样去枚举每种情况，所以我们要得出⼀个更为⼀般的结论我们设总共有n堆⽯⼦，每⼀堆⽯⼦的个数分别为a[1]、a[2]、a[3]……a[n]若a[1] ^ a[2] ^ a[3] ^ …… ^ a[n] =0先⼿必败，反之先⼿必胜下⾯是证明如果异或和的最⾼位为i，那么必定有⼀堆⽯⼦的第 i 位为1我们设这⼀堆⽯⼦的个数为k，其它所有⽯⼦的异或和为m，总异或和为x则必定有k ^ m=x，我们把这⼀堆⽯⼦变成k^x（k ^ x） ^ m=0这时，所有⽯⼦的异或和都变成了0举个例⼦:11001 ^ 11100=00101，则有（11001 ^ 00101）^ 11100=0如果当前所有数字的异或和为0，那么下⼀次⽆论你怎么取⽯⼦，异或和⼀定不会为0这样我们可以得出结论：如果先⼿异或和不为0，可以⼀步让后⼿的情况为异或和为0；如果先⼿异或和为0，那么后⼿异或和就不为0这样，我们不断进⾏游戏，最终⼀定会达到所有的数都为0的情况，⽽最后⾯对这种情况的⼀定会输所以我们可以得出结论：若a[1] ^ a[2] ^ a[3] ^ …… ^ a[n] =0先⼿必败，反之先⼿必胜例题洛⾕P2197模板题（好裸的板⼦）题意甲，⼄两个⼈玩 Nim 取⽯⼦游戏。

贝叶斯博弈例题及答案贝叶斯博弈是概率论和数理统计中研究决策理论的一个重要方面。

它是游戏理论的一种集合，可以将概率论和统计学与决策理论结合，从而使决策者能够在不确定的环境中作出正确的决策。

贝叶斯博弈的主要术语有：贝叶斯博弈矩阵、贝叶斯博弈策略和贝叶斯博弈操作。

贝叶斯博弈矩阵是一个3行3列的二维数组，分别是玩家A的策略，玩家B的策略和数值。

玩家A与玩家B之间的博弈情况就是通过贝叶斯博弈矩阵来描述的，每一行代表一个玩家，每一列代表另一个玩家，并且每一个单元格都是一个数值，表示该玩家在该情况下所获得的效益程度。

贝叶斯博弈策略是指玩家在贝叶斯博弈中可以采取的不同策略，如:攻击策略，防御策略，逃跑策略等。

贝叶斯博弈操作是指玩家在不同情况下根据自身可获得的信息，以及结合玩家之间的战略，运用贝叶斯博弈策略和贝叶斯博弈矩阵的数据，作出不同的博弈决策，以追求自身最大利益。

下面是一个贝叶斯博弈例题：有两个玩家，A和B，A有两种选择，攻击和逃跑，B有三种选择，攻击，防御和逃跑。

A选择攻击，B选择防御，结果是A得到2点，B得到1点；A选择攻击，B选择逃跑，结果是A得到3点，B得到0点；A选择逃跑，B选择攻击，结果是A得到0点，B得到2点；A选择逃跑，B选择防御，结果是A得到1点，B得到1点。

以上例题的贝叶斯博弈矩阵如下：A 击跑B 击 2 0防御 1 1逃跑 3 0利用贝叶斯博弈矩阵，当双方玩家都想获取最大利益时，A玩家最好选择攻击策略，而B玩家最好选择防御策略。

这样，两个玩家的效益都能达到最大值，A获得2点，B获得1点。

贝叶斯博弈是一种数学模型，它可以让玩家在贝叶斯博弈矩阵的基础上，根据不同的信息量和策略结合，使玩家在不确定的情况下作出最优选择，最终获得最大收益。

贝叶斯博弈可以在生活中得到广泛运用，从商业谈判中到家庭冲突，都可以使用贝叶斯博弈分析，以便更好地分析环境，并做出最优决策。

此外，贝叶斯博弈也可用来分析投资和经济行为，以及社会政治等。

博弈论2、可口可乐与百事可乐（参与者）的价格决策：双方都可以保持价格不变或者提高价格（策略）；博弈的目标和得失情况体现为利润的多少（收益）；利润的大小取决于双方的策略组合（收益函数）；博弈有四种策略组合，其结局是：（1）如果双方都不涨价，各得利润10单位；（2）如果可口可乐不涨价，百事可乐涨价，可口可乐利润100，百事可乐利润-30；（3）如果可口可乐涨价，百事可乐不涨价，可口可乐利润-20，百事可乐利润30；（4）如果双方都涨价，可口可乐利润140，百事可乐利润35；求纳什均衡。

博弈的稳定状态有两个：都不涨价或者都涨价（均衡），均衡称为博弈的解。

3、猪圈里有一头大猪和一头小猪，猪圈的一头有一个饲料槽，另一头装有控制饲料供应的按钮。

按一下按钮就会有10个单位饲料进槽，但谁按谁就要付出2个单位的成本。

谁去按按纽则谁后到；都去按则同时到。

若大猪先到，大猪吃到9个单位，小猪吃到一个单位；若同时到，大猪吃7个单位，小猪吃3个单位；若小猪先到，大猪吃六个单位，小猪吃4个单位。

各种情况组合扣除成本后的支付矩阵可如下表示（每格第一个数字是大猪的得益，第二个数字是小猪的得益）：小猪按等待大猪按 5，1 4，4等待 9，-1 0，0求纳什均衡。

在这个例子中，我们可以发现，大猪选择按，小猪最好选择等待，大猪选择不按，小猪还是最好选择等待。

即不管大猪选择按还是不按，小猪的最佳策略都是等待。

也就是说，无论如何，小猪都只会选择等待。

这样的情况下，大猪最好选择是按，因为不按的话都饿肚子，按的话还可以有4个单位的收益。

所以纳什均衡是（大猪按，小猪等待）。

4、根据两人博弈的支付矩阵回答问题：a bAB(1)写出两人各自的全部策略，并用等价的博弈树来重新表示这个博弈（6分）(2)找出该博弈的全部纯策略纳什均衡，并判断均衡的结果是否是Pareto有效。

(3)求出该博弈的混合策略纳什均衡。

（7分）(1)策略甲：ＡＢ乙：ａｂ博弈树（草图如下：(2)Pure NE (A, a); (B, b)都是Pareto 有效，仅(B, b)是Ｋ－Ｈ有效。

伯川德博弈例题
伯川德博弈（Bertrand Competition）是一个经典的博弈论模型，常用于描述价格竞争的场景。

以下是一个简单的伯川德博弈例题：
假设市场上只有两家公司A和B，生产和销售相同的产品。

每个公司可以选择自己的产品价格，目标是最大化自己的利润。

公司A的边际成本为cA，公司B的边际成本为cB。

假设cA 和cB是不同的，且都大于零。

如果两家公司选择相同的价格p，那么他们各自获得的利润为πA=p−cA和πB=p−cB。

如果两家公司选择不同的价格pA和pB，那么他们各自获得的利润为πA=pA −cA和πB=pB−cB。

由于市场上只有两家公司，如果他们选择相同的价格，那么他们获得的利润会更高。

但是，如果一家公司选择低于另一家公司的价格，它将获得所有的市场份额，因此获得的利润会更高。

现在，假设两家公司都选择低价策略，那么他们将陷入低价竞争的困境，最终导致两家公司的利润都很低。

因此，公司应该采取合理的价格策略来避免这种情况的发生。

这是一个经典的博弈论问题，可以用纳什均衡来求解。

假设两家公司都选择价格p作为最优策略，那么纳什均衡的价格就是使得两家公司的利润相等的价格。

以上是一个简单的伯川德博弈例题介绍，具体求解方法可以参考博弈论相关书籍或咨询专业人士。

博弈树例题摘要：一、博弈树的定义和基本概念1.博弈树的起源和发展2.博弈树的定义和组成3.博弈树的重要性和应用场景二、博弈树的构建方法1.状态转移方程2.决策节点和动作节点3.博弈树的深度优先搜索和广度优先搜索三、博弈树搜索算法1.盲目搜索（Upper Confidence Bound, UCB）2.启发式搜索（Exploration-Exploitation Tradeoff, EET）3.蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）四、博弈树在实际应用中的案例1.棋类游戏（围棋、象棋等）2.电子游戏（游戏AI、游戏设计等）3.人工智能领域（自动对弈、决策支持等）正文：博弈树（Game Tree）是一种在博弈类游戏中用来表示游戏过程和状态的树形数据结构。

它起源于博弈论，经过多年的发展，已经成为计算机科学、人工智能等领域中的重要工具。

博弈树的定义和组成主要包括根节点、内部节点和叶节点，其中根节点表示初始状态，叶节点表示游戏结束的状态，内部节点表示决策和动作。

博弈树的重要性和应用场景广泛，例如在棋类游戏中，可以通过博弈树来表示棋局的发展过程，帮助玩家进行决策；在人工智能领域，博弈树可以用于自动对弈、决策支持等方面。

构建博弈树的方法有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着一条路径一直向下搜索，直到遇到叶节点或者搜索达到预设深度。

广度优先搜索则是从根节点开始，同时搜索所有可能的子节点，直到搜索达到预设宽度。

博弈树搜索算法有盲目搜索（UCB）、启发式搜索（EET）和蒙特卡洛树搜索（MCTS）。

UCB 算法是基于探索和利用平衡的启发式搜索算法，通过选择动作节点的期望收益和置信度来选择下一步动作。

EET 算法则是在UCB 算法的基础上加入了启发式信息，通过比较动作节点的期望收益和启发式信息来选择下一步动作。

MCTS 算法则是通过多次随机模拟进行搜索和选择，逐步优化搜索策略。

博弈树3.3 博弈树搜索3.3.1 博弈概述诸如下棋、打牌、竞技、战争等⼀类竞争性智能活动称为博弈。

博弈有很多种，我们讨论最简单的"⼆⼈零和、全信息、⾮偶然"博弈，其特征如下：(1) 对垒的MAX、MIN双⽅轮流采取⾏动，博弈的结果只有三种情况：MAX⽅胜，MIN⽅败；MIN⽅胜，MAX⽅败；和局。

(2) 在对垒过程中，任何⼀⽅都了解当前的格局及过去的历史。

(3) 任何⼀⽅在采取⾏动前都要根据当前的实际情况，进⾏得失分析，选取对⾃已为最有利⽽对对⽅最为不利的对策，不存在掷骰⼦之类的"碰运⽓"因素。

即双⽅都是很理智地决定⾃⼰的⾏动。

在博弈过程中，任何⼀⽅都希望⾃⼰取得胜利。

因此，当某⼀⽅当前有多个⾏动⽅案可供选择时，他总是挑选对⾃⼰最为有利⽽对对⽅最为不利的那个⾏动⽅案。

此时，如果我们站在MAX⽅的⽴场上，则可供MAX⽅选择的若⼲⾏动⽅案之间是"或"关系，因为主动权操在MAX⽅⼿⾥，他或者选择这个⾏动⽅案，或者选择另⼀个⾏动⽅案，完全由MAX⽅⾃已决定。

当MAX⽅选取任⼀⽅案⾛了⼀步后，MIN⽅也有若⼲个可供选择的⾏动⽅案，此时这些⾏动⽅案对MAX⽅来说它们之间则是"与"关系，因为这时主动权操在MIN⽅⼿⾥，这些可供选择的⾏动⽅案中的任何⼀个都可能被MIN ⽅选中，MAX⽅必须应付每⼀种情况的发⽣。

这样，如果站在某⼀⽅(如MAX⽅，即MAX要取胜)，把上述博弈过程⽤图表⽰出来，则得到的是⼀棵"与或树"。

描述博弈过程的与或树称为博弈树，它有如下特点：(1) 博弈的初始格局是初始节点。

(2) 在博弈树中，"或"节点和"与"节点是逐层交替出现的。

⾃⼰⼀⽅扩展的节点之间是"或"关系，对⽅扩展的节点之间是"与"关系。

双⽅轮流地扩展节点。

博弈论练习题二1.囚徒困境：假设警察局抓住了两个合伙犯罪的嫌疑犯，但获得的证据并不十分确切，对于两者的量刑就可能取决于两者对于犯罪事实的供认。

警察局将这两名嫌疑犯分别关押以防他们串供。

两名囚徒明白，如果他们都交代犯罪事实，则可能将各被判刑5年；如果他们都不交代，则有可能只会被以较轻的妨碍公务罪各判1年；如果一人交代，另一人不交代，交代者有可能会被立即释放，不交代者则将可能被重判8年。

（1）请写出这两名嫌疑犯博弈的支付矩阵；（2）假设这两名嫌疑犯都是极其精明的会打小算盘的自私自利不讲“江湖义气”的人，同时被分别审查不能够进行沟通。

请给出每个嫌疑犯的最佳策略；（3）假设允许这两名嫌疑犯在审讯室一起单独呆上10分钟，然后再决定是否坦白。

他们能否建立一个攻守同盟，从而双方都只被判一年？（4）若其中一名囚徒不知道对手是否理性，则他的最佳策略是什么？（5）说明这两个囚徒的困境在哪里？从“囚徒困境”博弈中你得到了什么启示？（6）利用“囚徒困境”博弈从下面两个现象中选取一个进行解释：①恋人们在恋爱中海誓山盟，最终还是分手；②美苏两国经常会晤，甚至签订核不扩散条约，但军费一年高过一年。

（7）请试举一例“囚徒困境”博弈。

（8）请指出一种走出“囚徒困境”的方法。

2. 商家价格战出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱。

请解释这个现象，并站在商家的立场上给出一些避免“价格大战”的方法。

3. 智猪博弈猪圈中有一头大猪和一头小猪，在猪圈的一端设有一个按钮，每按一下，位于猪圈另一端的食槽中就会有10单位的猪食进槽，但每按一下按钮会耗去相当于2单位猪食的成本。

如果大猪先到食槽，则大猪吃到9单位食物，小猪仅能吃到1单位食物；如果两猪同时到食槽，则大猪吃7单位，小猪吃3单位食物；如果小猪先到，大猪吃6单位而小猪吃4单位食物。

（1）给出这个博弈的支付矩阵；（2）找出这两头理性“智猪”的最佳策略；（3）该“智猪博弈”博弈给你的启发是什么？（4）有些广告具有“外部性”，如假设伊利宣传牛奶能强健国人的体质的广告就不仅仅增加了人们对伊利牛奶的需求，也增加了对其他品牌牛奶的需求。

〔一〕巴什博奕〔Bash Game〕：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。

最后取光者得胜。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。

因此我们发现了如何取胜的法那么：如果n=〔m+1〕r+s，〔r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k 〔≤m)个，那么先取者再拿走m+1-k个，结果剩下〔m+1〕〔r-1〕个，以后保持这样的取法，那么先取者肯定获胜。

总之，要保持给对手留下〔m+1〕的倍数，就能最后获胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。

取石子〔一〕时间限制：3000 ms | 存限制：65535 KB难度：2描述一天，TT在寝室闲着无聊，和同寝的人玩起了取石子游戏，而由于条件有限，他/她们是用旺仔小馒头当作石子。

游戏的规那么是这样的。

设有一堆石子，数量为N〔1<=N<=1000000〕，两个人轮番取出其中的假设干个，每次最多取M个〔1<=M<=1000000〕，最先把石子取完者胜利。

我们知道，TT和他/她的室友都十分的聪明，那么如果是TT先取，他/她会取得游戏的胜利么？输入第一行是一个正整数n表示有n组测试数据输入有不到1000组数据，每组数据一行，有两个数N和M,之间用空格分隔。

输出对于每组数据，输出一行。

如果先取的TT可以赢得游戏，那么输出“Win〞，否那么输出“Lose〞〔引号不用输出〕样例输入样例输出最优解：#include<iostream> using namespace std;int main(){int k;long m,n;cin>>k;while(k--){cin>>n>>m;if(n%(m+1)==0)cout<<"Lose"<<endl;elsecout<<"Win"<<endl;}}巴什博弈变形：有两种解，依实际情况而定：取石子〔七〕时间限制：1000 ms | 存限制：65535 KB难度：1描述Yougth和Hrdv玩一个游戏，拿出n个石子摆成一圈，Yougth和Hrdv分别从其中取石子，谁先取完者胜，每次可以从中取一个或者相邻两个，Hrdv先取，输出胜利着的名字。

【1】有1001根火柴放在盒子里，甲、乙两人轮流各取1根或2根，取到最后一根者为胜。

必胜的最佳对策是什么？【2】在黑板上写下一列连续的自然数：2、3、4、…、1999、2000，甲先擦去其中一个数，然后乙再擦去一个数。

如此轮流地擦下去。

若最后剩下两个质数时，甲取胜；若最后剩下两个数不互质时，乙取胜。

这个游戏中谁取胜的可能性最大？【3】两人轮流在圆桌面上摆硬币，每次摆一枚，各个不能互相重叠，也不能有一部分在桌面的边缘以外。

这样经过反复多次以后，谁先摆不下硬币就算输。

谁有必胜的策略？取胜的策略是什么？【4】请你参加一种游戏：有1996个棋子，两人轮流取棋子，每次允许取其中2个、4个或8个，谁最后把棋子取完，就算获胜。

如果你先取，那么第一次你取多少个？先取的人有一个必胜的方法，如果你已想出这个办法，请写出来。

【5】桌子上有a颗棋子，甲、乙两人轮流拿棋子，他们规定：假如甲先拿，可以拿任意颗棋子，但不能拿光。

接着乙拿，乙拿的棋子数最多只能比甲拿的多一个。

接着甲拿，最多只能比乙刚才拿的数目多一个。

接着乙拿，最多只能比甲刚才拿的数目多一个。

如此下去，最后一步谁把棋子拿光就算胜者。

例1：一个木盒中有101个塑料球，甲乙两人轮流从中取球，但每人每次只能从中取走1个球或2个球，谁能先取得木盒中最后一个球就谁胜。

例2：有两堆相等的棋子，甲乙两人轮流在其中任意一堆里取，多取不限制，但是不能不取。

谁取到最后一枚棋子为胜。

如果甲先取，他一定能获胜吗？例3：在一张有40个小方格的棋盘上（如图1），甲持黑子置于A处，乙持白子置于B处，随后两人轮流走，每次可沿一条横线或一条纵线至少走一格，并要遵守如下规则：（1）不可和对方的棋子处在同一条线上；（2）走时不能越过对方所在棋子的线。

轮到谁无路可走就算失败。

怎样才能取胜？例4：甲乙两人轮流地往一张圆桌面上放一枚伍分硬币，规定任何硬币不能重叠。

谁放完一枚之后而使得对方无法再往桌子面上放硬币时，谁就是胜利者。

A.逻辑推理2、请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。

3、小明一家过一座桥，过桥时是黑夜，所以必须有灯。

现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。

每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。

问：小明一家如何过桥？4、一群人开舞会，每人头上都戴着一顶帽子。

帽子只有黑白两种，黑的至少有一顶。

每个人都能看到其他人帽子的颜色，却看不到自己的。

主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。

第一次关灯，没有声音。

于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。

一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。

问有多少人戴着黑帽子？5、请估算一下ＣＮＴＯＷＥＲ电视塔的质量。

7、U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。

一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。

手电筒是不能用丢的方式来传递的。

四个人的步行速度各不同，若两人同行则以较慢者的速度为准。

Bono需花1分钟过桥，Edge 需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。

他们要如何在17分钟内过桥呢？11、有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？13、你有两个罐子，50个红色弹球，50个蓝色弹球，随机选出一个罐子，随机选取出一个弹球放入罐子，怎么给红色弹球最大的选中机会？在你的计划中，得到红球的准确几率是多少？14、想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒上下？16、如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出4夸脱的水？21、假设一张圆盘像唱机上的唱盘那样转动。