最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

每日动态!【2023.02.16】威佐夫博弈详解

来源：博客园

威佐夫博弈详解

威佐夫博弈（Wythoff"s game）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。——百度百科

威佐夫博弈，是博弈论的一道经典例题，题目大意是两个人在进行取子游戏，石子分为两堆，每堆有若干个石子，两个人按规则轮流取石子，先取完全部石子的人获胜。其中，规则如下：

  • 每个人可以选择在同一堆石子中取任意个石子（可以全部取完），也可以在两堆石子中同时取相同个数的石子，但不可以不取。

那么，现在你作为先手，是否能够必胜呢（两人都具有绝对的智慧做出对自己最有利的选择）？


(相关资料图)

首先我们可以来分析一下这个问题中的奇异局势：

  1. 那么第一种想到必败的情况，肯定是（0,0）了。在（0,0）的情况中无论先手怎么走都不可能赢（他压根走不了；

  2. 第二种奇异局势的话通过计算可以得出是（1,2），当先手碰到（1,2）这种情况时，可以做出以下4种选择：

    • 在第一堆石子中取一个石子，局面变为（0,2）；这时，后手只需将第二堆全部的石子都取走便可获得胜利。

    • 在第二堆石子中取一个石子，局面变为（1,1）；这时，后手只需在两堆同时取走1个石子便可获得胜利。

    • 在第二堆石子中取两个石子，局面变为（1,0）：这时，后手只需将第一堆全部的石子都取走便可获得胜利。

    • 在两堆中同时取走一个石子，局面变为（0,1）：这时，后手只需将第二堆全部的石子都取走便可获得胜利。

      分析过后想必你也能看出来这是种必败的情况吧！

  3. 第三种奇异局势的话经过计算可以得出是（3,5），当先手碰到（3,5）这种情况时，可以做出以下11种选择：

    • 在第一堆石子中取一个石子，局面变为（2,5）：这时，后手只需在第二堆石子中取四个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在第一堆石子中取两个石子，局面变为（1,5）：这时，后手只需在第二堆石子中取三个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在第一堆石子中取三个石子，局面变为（0,5）：这时，后手只需将第二堆全部的石子都取走便可获得胜利。

    • 在第二堆石子中取一个石子，局面变为（3,4）：这时，后手只需在两堆中同时取两个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在第二堆石子中取两个石子，局面变为（3,3）：这时，后手只需在两堆中同时取三个石子，局面变为（0,0），先手必败。

    • 在第二堆石子中取三个石子，局面变为（3,2）：这时，后手只需在两堆中同时取一个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在第二堆石子中取四个石子，局面变为（3,1）：这时，后手只需在第一堆中取一个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在第二堆石子中取五个石子，局面变为（3,0）：这时，后手只需将第一堆石子全部取走便可获得胜利。

    • 在两堆石子中同时取走一个石子，局面变为（2,4）：这时，后手只需在第二堆石子中取走三个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在两堆石子中同时取走两个个石子，局面变为（1,3）：这时，后手只需在第二堆石子中取走一个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在两堆石子中同时取走三个石子，局面变为（0,2）：这时，后手只需将第二堆石子中的全部石子都取走，便可获得胜利。

      自然，你也可以看出（3,5）这种情况先手是必败的！

  4. 第三种奇异局势经过计算我们可以得出是（4,7），先手碰到这种情况可以做出以下15种情况：

    • 在第一堆石子中取一个石子，局面变为（3,7）：这时，后手只需在第二堆石子中取两个石子，局面变为（3,5），上文已经推理过了，先手必败。

    • 在第一堆石子中取两个石子，局面变为（2,7）：这时，后手只需在第二堆石子中取六个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在第一堆石子中取三个石子，局面变为（1,7）：这时，后手只需在第二堆石子中取五个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在第一堆石子中取四个石子，局面变为（0,7）：这时，后手只需将第二堆石子全部都取走便可获得胜利。

    • 在第二堆石子中取一个石子，局面变为（4,6）：这时，后手只需在两堆中同时取一个石子，局面变为（3,5），上文已经推理过了，先手必败。

    • 在第二堆石子中取两个石子，局面变为（4,5）：这时，后手只需在第一堆石子中取一个石子，局面变为（3,5），上文已经推理过了，先手必败。

    • 在第二堆石子中取三个石子，局面变为（4,4）：这时，后手只需在两堆中同时取四个石子便可获得胜利。

    • 在第二堆石子中取四个石子，局面变为（4,3）：这时，后手只需在两堆中同时取两个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在第二堆石子中取五个石子，局面变为（4,2）：这时，后手只需在第一堆石子中取三个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在第二堆石子中取六个石子，局面变为（4,1）：这时，后手只需在第一堆石子中取两个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在第二堆石子中取七个石子，局面变为（4,0）：这时，后手只需将第一堆石子全部都取走即可获得胜利。

    • 在两堆石子中同时取走一个石子，局面变为（3,6）：这时，后手只需在第二堆石子中取走一个石子，局面变为（3,5），上文已经推理过了，先手必败。

    • 在两堆石子中同时取走两个石子，局面变为（2,5）：这时，后手只需在第二堆石子中取走四个石子，局面变为（2,1），上文已经推理过了，先手必败。

    • 在两堆石子中同时取走三个石子，局面变为（1,4）：这时，后手只需在第二堆石子中取走两个石子，局面变为（1,2），上文已经推理过了，先手必败。

    • 在两堆石子中同时取走四个石子，局面变为（0,3）：这时，后手只需将第二堆石子全部都取走即可获得胜利。

关键词： 获得胜利 这种情况