最新要闻

广告

手机

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

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

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

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

家电

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

剪刀石头布的算法

来源：博客园

作者: Daniel Lu原文: https://daniel.lawrence.lu/programming/rps/时间: 2011

1. 简介

剪刀石头布是一个关于预测对手的游戏。这是一个很难的问题。初次接触的人可能会问，"为什么不直接玩随机的呢？" 众所周知，稳定地击败随机玩家是不可能的。那为什么还要费心呢？事实证明，一个随机策略只能赢得50%的比赛。然而，一个好的预测算法可以利用不那么随机的对手（包括人类）的模式，更经常地击败他们。事实上，排行榜上一些最强的引擎的胜率超过了80%!

假设你有10个对手，其中9个随机下，1个总是下石头。如果你也是随机玩的，你会赢50%的时间。然而，如果你总是玩纸牌，你将赢得55%的时间，因为你总是能打败那个总是玩石头的家伙，而在面对随机玩家时，你的表现仍然是一样的。55%的胜率比50%的胜率要好。重要的是，只要池子里有哪怕一个非随机玩家，利用模式的算法总是会做得更好。


(相关资料图)

另外，正如《纽约时报》的一篇文章所报道的，人类在随机性方面相当糟糕。

为此，本页面是关于描述编写石头剪刀布算法的各种方法。在 "剪刀石头布 "编程竞赛中，我的参赛作品或其变体一直在排行榜上排名靠前。

2. 主要策略

有一些基本的策略，大致上是按实力从高到低排列的。

2.1 固定移动

最简单的策略是总是下同一步棋。一个例子是 Always Rock。不是很有趣...

2.2 频率统计

这种算法计算对手以前的动作，以确定对手是否喜欢下一种类型的棋而不是其他。从本质上讲，它为石头、纸和剪刀各保留一个 "分数"。在每一步棋之后，对手的棋的分数都会被增加。

这样的算法会很容易打败固定移动的算法。一个例子是 The Frequentist。

有可能对这一策略做出更复杂的变体。例如，波尔兹曼计数器的算法有一个衰减的分数。这使它更多地受到最近的结果而不是过去的结果的影响，并使它能够适应缓慢变化的对手。它还进一步减少了本来会输的那步棋的得分。因此，举例来说，如果对手下的是石头，纸的得分会增加，但剪刀的得分会减少。

2.3 旋转

在 "石头剪刀布 "中，旋转是一种模块化的加法。

MOVEROTATION BY 0ROTATION BY 1ROTATION BY 2
RRPS
PPSR
SSRP

以0（或等同于以3、6或任何0模3的数字）旋转的棋步，只是棋步本身。以1旋转的棋步是击败它的棋步。以2旋转的棋步是输给它的棋步。

一个例子是 "最后输入"（Beat Last Input），它以1的旋转来回复对手的前一步棋。

2.4 抗旋转

这个算法假定对手使用的是三种可能的旋转之一。它计算从自己之前的棋中得到对手最后一步棋所需的旋转，并确定对手一定使用的旋转。然后，它对自己的最后一步棋进行旋转。例如，如果对手将最后一步棋旋转了1，这个算法将把自己的最后一步棋旋转2，只是为了超过对手。

一个例子是 Probably not very strong 3.3.

2.5 历史字符串匹配

这可以被认为是通过部分匹配进行预测的最简单案例。该算法记录了迄今为止所下的所有棋步，例如以一个字符串的形式。为了确定下一步棋，它使用子串匹配算法来找到最近一次下过的棋步序列的最新时间。然后，它下出与对手在该序列后最后一次下出的棋子相对应的棋子。在Python中，函数rfind对于进行这样的搜索很有用。例如，如果历史看起来像这样:

RPSRRPRSPRPSRPRSPSPSPRRPSRPR         RPSRPR       RPSRPR

为了清楚起见，我在第二行重复了上一序列的最新匹配。匹配后的字母是一个S，所以你可能会猜到对手接下来可能会下S。

rfind就是一个例子。存在许多变体，包括匹配自己的棋步、自己的棋步和对手的棋步的组合、寻找最早的而不是最新的匹配，或者寻找所有的匹配。

3. 元策略

前面讨论的每一种策略都有一个对策。要反击它们中的任何一个都很容易，因为它们的行为都是可以预测的。但即使是纯粹的反击，也可以通过再次旋转结果来进行反击。事实上，对于每个策略，有六种可能的使用方法。这样的元策略被用于丹-埃格诺（Dan Egnor）的Iocaine Powder程序中。

METASTRATEGYDESCRIPTION
P0天真地玩法.
P’0: 战胜 P0交换你和你的对手的位置。然后，在对手的位置上打出天真策略的输出
P1: 战胜 P’0将P0旋转两圈，也就是下出输给P0的输出的那一步
P’1: 战胜 P1将P"0旋转两圈，与上述相同
P2: 战胜 P’1将P1旋转两圈
P’2: 战胜 P2将P"1旋转两圈

请注意，P0击败了P"2，从而绕了一圈。

3.1 元策略的选择

如果每个策略都有六个可能的元策略，我们如何选择使用哪一个？如果我们一开始也有多个策略呢？方法是根据过去的表现来选择。如果一个策略一直很成功，我们就使用这个策略。如果一个策略总是亏损，我们就不使用它。这里有一些实现这一目标的方法。

  • 天真的打分: 每个预测者都存储一个数字。每轮结束后，如果预测者成功预测了对手的棋，其分数就会增加1。如果预测输给了对手的行动，其分数就会减一。一个例子是Variable Turbine Geometry。

  • 衰减计分: 这与天真的评分法一样，只是所有的分数在每一轮之后也要乘以一个0到1的数字（通常是0.9左右），这样它就会逐渐 "忘记 "很久以前每个预测器的表现。因此，如果对手偶尔切换策略，这应该能够应对。一个例子是DNA werfer 2。

  • 丢弃开关: 就像天真的计分法一样，只是如果预测者哪怕输了一次，其分数就会被重置为零。这使得对有转换策略的对手的反应比衰减计分快得多，但如果对手增加了某种噪音（例如每十步走一步随机棋），就会很脆弱。一个例子是DNA werfer 5 M0。

  • 随机掉线开关: 就像掉线开关一样，只是预测者的分数只被随机重置为零，概率为，比如说，0.5。一个例子是Random Drop-Switch。

当然，得分最高的预测器被选择使用。还有一些其他的选择器，比如只要预测器没有获胜（即即使是平局），就将分数重置为零。其他一些选择器的工作方式与天真评分或衰减评分类似，但也会在平局时将分数递减一个小值。值得注意的是，算频策略实际上只是一个固定棋步策略加上一个天真的得分选择器。

请注意，一些基本策略实际上是带有元策略的更简单的策略。例如，"频率计算 "只是带有天真的计分的 "固定动作 "策略：它在 "固定动作 "策略（总是玩石头，总是玩纸，或者总是玩剪刀）中选择哪一个最成功。

3.2 选择器选择

有这么多的策略选择方法可供选择，我们如何选择哪一个是最好的？因此，我们还有一个层次：选择器选择。

这些的实现方式与以前相同。例子是离心大黄蜂13和开关18。

4. 防御机制

一个众所周知的事实是，真正的随机策略不可能一直输下去。因此，一旦算法检测到它正在输掉，切换到一个随机策略是很有用的。做到这一点的一个方法是简单地将随机策略作为预测因素之一，与其他策略（如历史匹配）并列。那么，如果其他策略都开始输了，它们都会有相当负的分数，除了随机策略，它的分数大概会接近于零。在这种情况下，选择者会选择随机策略而不是其他策略，并希望能避免一场可怕的损失。

译者注

作者策略试玩, 很厉害: http://www.rpscontest.com/human/498002作者策略源码: http://www.rpscontest.com/entry/498002

关键词：