如何处理一个带有变化的数字猜测游戏算法？

Question

更新（2020年7月）：这个问题已经有9年了，但我仍然深感兴趣。在此期间，机器学习（如RNN、CNN、GAN等）、新方法和廉价的GPU已经涌现出来，使得新方法成为可能。我认为重新探讨这个问题会很有趣，看看是否有新的方法。

我正在学习编程（Python和算法），并尝试着做一个我觉得有趣的项目。我已经创建了几个基本的Python脚本，但我不确定该如何解决我正在尝试构建的游戏的问题。

以下是游戏的运作方式:

用户将被赋予具有价值的物品。例如,

Apple = 1
Pears = 2
Oranges  = 3

然后他们将有机会选择任何套餐（即100个苹果、20个梨和一个橙子）。计算机唯一得到的输出是总价值（在本例中，它目前为$143）。计算机将尝试猜测他们所选的内容。很明显，它第一轮不可能猜对。

         Value    quantity(day1)    value(day1)
Apple      1        100                100
Pears      2         20                 40
Orange     3          1                  3
Total               121                143

下一轮用户可以修改他们的数字，但不能超过总数量的5％（或我们选择的其他百分比。我将使用5％作为示例）。水果的价格可能会改变（随机），因此总价值也可能会因此而改变（为简单起见，在此示例中不更改水果价格）。使用上面的示例，在游戏的第二天，用户返回了$152和第三天的$164。以下是一个示例：

Quantity (day2)   %change (day2)    Value (day2)   Quantity (day3)   %change (day3)   Value(day3)
 104                                 104            106                                106
  21                                  42             23                                 46
   2                                   6              4                                 12
 127               4.96%             152            133               4.72%            164

*(希望表格正确显示，我必须手动排版，所以希望它不仅仅在我的屏幕上有效，如果不行，请告诉我，我会尝试上传截图。)

我正在尝试弄清楚随着时间的推移数量是什么（假设用户有耐心继续输入数字）。 我知道现在我的唯一限制是总价值不能超过5％，因此现在我无法精确到5％，因此用户将永远输入。

目前为止我做了什么

以下是我的解决方案（不多）。 基本上，我获取所有值并计算出它们的所有可能组合（我已经完成了这部分）。 然后，我将所有可能的组合作为字典放入数据库中（例如，对于$143，可能存在一个字典条目{apple:143，Pears:0，Oranges :0}..一直到 {apple:0，Pears:1，Oranges :47}。每次我获得一个新号码时都要这样做，所以我拥有所有可能性的列表。

我现在卡住了。在使用上述规则时，如何找出最佳解决方案？ 我认为我需要一个适应度函数，自动比较两天的数据并删除任何具有前一天数据超过5％差异的可能性。

问题：

用户更改总价值时，我如何处理这种情况？ 我需要学习什么？ 是否有适用的算法或理论可供使用？或者为了帮助我理解我的错误，您可以建议我添加哪些规则以使此目标实现（如果当前状态不可行。我正在考虑添加更多水果并说他们必须至少选3个等等）。 此外，我对遗传算法的理解非常模糊，但是我认为我可以在这里使用它们，是否有其他可以使用的东西？

我非常渴望学习，所以任何建议或提示都将不胜感激（只是请不要告诉我这个游戏不可能）。

更新：得到反馈称这很难解决。 所以我想增加游戏的另一个条件，这不会干扰玩家正在做的事情（对他们来说游戏保持不变），但是每天水果的价值会发生变化（随机）。 那会让解决变得更容易吗？ 因为在5％的移动范围内和某些水果价值的变化下，随着时间的推移，只有几种组合是可能的。第1天，任何事情都有可能，并且获得足够接近的范围几乎是不可能的，但是随着水果价格的变动和用户只能选择5％的变化，那么（随着时间的推移）范围不断缩小。在上面的示例中，如果价格足够波动，我认为我可以强制解决方案并给出一个猜测范围，但是我正在尝试弄清楚是否有更优雅的解决方案或其他解决方案来不断缩小这个范围。

更新2：经过阅读和询问周围人，我认为这是一个隐藏的马尔可夫/维特比问题，它跟踪水果价格的变化以及总和（最后一个数据点的权重最重）。我不确定如何应用这种关系。我认为这可能是这种情况，并可能是错误的，但至少我开始怀疑这是某种类型的机器学习问题。

更新3：我创建了一个测试案例（使用更小的数字）和生成器来自动化用户生成的数据，并尝试从中创建一个图形来看出什么更有可能。

这里是代码，以及总值和有关用户实际水果数量的注释。

#!/usr/bin/env python
import itertools

# Fruit price data
fruitPriceDay1 = {'Apple':1, 'Pears':2, 'Oranges':3}
fruitPriceDay2 = {'Apple':2, 'Pears':3, 'Oranges':4}
fruitPriceDay3 = {'Apple':2, 'Pears':4, 'Oranges':5}

# Generate possibilities for testing (warning...will not scale with large numbers)
def possibilityGenerator(target_sum, apple, pears, oranges):
    allDayPossible = {}
    counter = 1
    apple_range = range(0, target_sum + 1, apple)
    pears_range = range(0, target_sum + 1, pears)
    oranges_range = range(0, target_sum + 1, oranges)
    for i, j, k in itertools.product(apple_range, pears_range, oranges_range):
        if i + j + k == target_sum:
            currentPossible = {}

            #print counter
            #print 'Apple', ':', i/apple, ',', 'Pears', ':', j/pears, ',', 'Oranges', ':', k/oranges
            currentPossible['apple'] = i/apple
            currentPossible['pears'] = j/pears
            currentPossible['oranges'] = k/oranges

            #print currentPossible
            allDayPossible[counter] = currentPossible
            counter = counter +1
    return allDayPossible

# Total sum being returned by user for value of fruits
totalSumDay1=26 # Computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the day
totalSumDay2=51 # Computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the day
totalSumDay3=61 # Computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the day
graph = {}
graph['day1'] = possibilityGenerator(totalSumDay1, fruitPriceDay1['Apple'], fruitPriceDay1['Pears'], fruitPriceDay1['Oranges'] )
graph['day2'] = possibilityGenerator(totalSumDay2, fruitPriceDay2['Apple'], fruitPriceDay2['Pears'], fruitPriceDay2['Oranges'] )
graph['day3'] = possibilityGenerator(totalSumDay3, fruitPriceDay3['Apple'], fruitPriceDay3['Pears'], fruitPriceDay3['Oranges'] )

# Sample of dict = 1 : {'oranges': 0, 'apple': 0, 'pears': 0}..70 : {'oranges': 8, 'apple': 26, 'pears': 13}
print graph

- Lostsoul

---

你可以尝试在http://math.stackexchange.com/上发布这个问题。 - Ilmari Karonen

stats.stackexchange.com比数学更相关。 - cyborg

Answer 1

我们将结合图论和概率：

第一天，构建所有可行解的集合。我们将解集表示为A1={a1（1），a1（2），...，a1（n）}。

第二天，您可以再次构建解集A2。

现在，对于A2中的每个元素，您需要检查它是否可以从A1的每个元素到达（给定x％的容差）。如果可以-将A2（n）连接到A1（m）。如果无法从A1（m）中的任何节点到达，则可以删除此节点。

基本上，我们正在构建一个连通的有向无环图。

图中的所有路径具有相等的可能性。仅当从Am到Am + 1（从Am中的一个节点到Am + 1中的一个节点）存在单个边缘时，您才能找到精确的解决方案。

当然，某些节点出现在更多的路径中，而其他节点则出现在更少的路径中。可以根据包含该节点的路径数量直接推导出每个节点的概率。

通过为每个节点分配权重，该权重等于导致该节点的路径数，无需保留所有历史记录，而只需保留前一天即可。

还要看看非负值线性同余方程——我一段时间以前问的一个问题。接受的答案是枚举每个步骤中所有组合的好方法。

- Lior Kogan

---

@LiorKogan 我理解你的解决方案，但在尝试成功实现它时遇到了困难。我理解你的逻辑并且很有道理，但我开始思考，由于所有数字都有相等的成功概率，它如何能够从众多可能性中区分出正确的解决方案。最终我研究了隐马尔可夫模型，它似乎是正确的，但它只对最后一个成功匹配（而不是A1、A2等）进行加权。 - Lostsoul

我还不是100%确定，但我开始认为我需要使用隐马尔可夫模型来分配正确答案的概率，然后使用图形导航并尝试找到基于总和历史记录的最佳当前答案。你觉得呢？ - Lostsoul

非常感谢你，Lior。我正在努力解决这个问题，但我不是最好的程序员（因此正在尝试学习）。我更新了问题，包括我正在使用的生成器和字典中的所有可能值。今晚我将花时间学习如何在图形中实现查找路径。我可以找到图中的最短路径，但我认为这并不适用，因为它们都不是真正的短路径（而且都很可能），这就是为什么我认为HHM会有所帮助，因为它似乎加权了概率。图表看起来很有前途，所以今晚我会专注于它们，并分享结果。 - Lostsoul

顺便说一下，如果你有时间的话，可以看看http://en.wikipedia.org/wiki/Viterbi_algorithm#Example。他们在例子中所做的似乎是游戏试图做的，只是我不确定如何训练它，以便随着获取更多数据，它变得更加准确（这似乎只是使用最后的结果作为查找隐藏变量的基础），这就是我认为可以使用图表来跟踪整体进展的地方。 - Lostsoul

维基百科的示例假设有两个状态（雨天、晴天）。请注意，在您的问题中，存在未知数量（甚至是无限）的状态（长期而言）。您需要使用HDP-HMM（请参阅维基百科上的HMM文章）。 - Lior Kogan

Answer 2

免责声明：我在暂时删除回答并仔细重新阅读问题后，大幅度修改了我的答案，因为我误读了一些关键部分的问题。尽管仍然涉及类似的主题和算法，但在我尝试自己用C#解决问题之后，答案得到了很大的改进。

好莱坞版

• 该问题是动态约束满足问题（DCSP），是约束满足问题（CSP）的一个变体。
• 如果值和数量范围不是很小，则使用Monte Carlo查找给定日期的潜在解决方案。否则，使用暴力方法查找每个潜在解决方案。
• 使用约束记录（与DCSP相关），应用于之前的几天以限制潜在解决方案集。
• 交叉你的手指，瞄准并射击（猜测），基于概率。
• （可选）布鲁斯·威利斯获胜。

原始版本

首先，我想说这里有两个主要问题：

1. 可能的解决方案实在是太多了。例如，仅知道物品数量和总值——比如3和143——就会产生非常多的可能解。而且，很难编写算法来筛选有效的解决方案，避免尝试无效的方案（总价值不等于143）。

2. 当找到特定日期D_i的可能解决方案时，必须找到一种方法来利用{ D_i+1 .. D_i+n }给出的附加信息消除潜在的解决方案。

让我们为即将到来的示例设置一些基础：

• 保持相同的物品价值，整个游戏。它可以是随机的或由用户选择。
• 可能的物品价值范围非常有限，为[1-10]，没有两个物品可以具有相同的价值。
• 任何物品的数量都不能大于100。也就是说：[0-100]。

为了更轻松地解决这个问题，我做了一个约束条件的改变，使得算法更快地收敛:

• "总量"规则被以下规则取代：你可以在一天内添加或删除[1-10]范围内的任意数量的物品，但是你不能添加或删除相同数量的物品超过两次。这也使得游戏的最大生命周期为20天。

这个规则使我们能够更轻松地排除解决方案。而且，对于非微小的范围，回溯算法 仍然无用，就像你的原始问题和规则一样。

在我看来，这个规则不是游戏的精髓，只是一个辅助工具，使计算机能够解决问题。

问题1：寻找潜在解决方案

首先，可以使用 蒙特卡罗算法 找到一组潜在解决方案来解决问题1。这种技术很简单：为物品值和数量（在各自接受的范围内）生成随机数。重复此过程以获取所需数量的物品。验证解决方案是否可接受。这意味着验证物品是否具有不同的价值，并且总和等于我们的目标总和（例如，143）。

虽然这种技术有易于实现的优点，但也有一些缺点：

• 用户的解决方案不能保证出现在我们的结果中。
• 有很多“失败”。例如，根据我们的约束条件，需要尝试大约3,000,000次才能找到1,000个潜在解决方案。
• 需要很长时间：在我的慢笔记本电脑上大约需要4到5秒钟。

如何克服这些缺点？好吧...

• 将范围限制在较小的值内
• 找到足够数量的潜在解决方案，以便用户的解决方案有很好的机会出现在您的解决方案集中。
• 使用启发式方法更轻松地找到解决方案（稍后详细介绍）。

请注意，您限制的范围越大，蒙特卡罗算法就越不实用，因为有效解决方案数量足够少，无法在合理时间内迭代所有解决方案。对于约束条件{3，[1-10]，[0-100]}，大约有7.41亿个有效解决方案（未受限于目标总值）。可以使用蒙特卡罗算法。对于{3，[1-5]，[0-10]}，只有大约80,000个解决方案。不需要使用蒙特卡罗算法；暴力for循环就可以胜任。

我相信问题1是您所谓的约束满足问题（或CSP）。

问题2：限制潜在解决方案集合

考虑到问题1是一个CSP，我会称呼问题2和整个问题为动态CSP（或DCSP）。

[DCSPs]在环境发生变化时非常有用，通常是因为要考虑的约束集合发生了变化。DCSP被视为一系列静态CSP，每个CSP都是前一个CSP的转换，在其中可以添加（限制）或删除（放宽）变量和约束。

与CSP一起使用的一种技术可能对这个问题有用，称为约束记录:

• 随着环境的每一次变化（用户输入D_i+1的值），查找有关新约束的信息: 添加-删除约束的可能“使用”数量是什么。
• 将约束应用于级联中的每一天。涟漪效应可能会显著减少可能的解决方案。

为了使其工作，您需要每天获得一组新的可能解决方案; 使用暴力搜索或蒙特卡罗方法。然后，将D_i的解决方案与D_i-1进行比较，并仅保留可以成功地到达先前几天的解决方案而不违反约束条件的解决方案。

您可能需要保留哪些解决方案导致了哪些其他解决方案的历史记录（可能是在有向图中）。约束记录使您能够记住可能的添加-删除数量，并基于此拒绝解决方案。

还有许多其他步骤可以采取以进一步改进您的解决方案。以下是一些想法:

• 记录上一天解决方案中的项目-值组合约束条件。立即拒绝其他解决方案（因为项目值不能改变）。甚至可以使用特定于解决方案的约束条件找到每个现有解决方案的更小的解决方案集，以更早地拒绝无效的解决方案。
• 每天生成一些"突变的"完整历史解决方案，以"修复" D₁ 解决方案集不包含用户解决方案的情况。可以使用遗传算法基于现有解决方案集找到突变种群。
• 使用启发式方法轻松找到解决方案（例如，在找到有效的解决方案时，尝试通过替换数量来找到此解决方案的变化）。
• 使用行为启发式方法来预测某些用户操作（例如，每个项目相同数量，极端模式等）。
• 在用户输入新数量时继续进行一些计算。

考虑基于解决方案和启发式方法的发生率来确定候选解决方案的排名系统。

- Bryan Menard

---

我明天会尝试，但我不太擅长正式证明。然而，我可以肯定地说这个问题看起来像是一个优化问题，通常情况下是NP而不是P。 - Bryan Menard

我最终移除了NP-hard的假设（并对我的答案进行了大量重构），因为起初我认为这个问题是一个优化问题。这个问题可能仍然具有NP-某种复杂度，但我不确定。 - Bryan Menard

Answer 3

这个问题是无法解决的。

假设你知道增加了多少比例的物品数量，而不仅仅是这个最大比例。

一个用户有N个水果，你有D天的时间来猜测。

每天你会得到N个新变量，总共有D*N个变量。

对于每一天，你只能生成两个方程式。一个方程式是n_item*price的总和，另一个基于已知的比例。如果它们都是独立的，你最多有2*D个方程式。

对于所有N > 2，2*D < N*D。

- Luka Rahne

---

谢谢Ralu，数学网站上的某个人说了类似的话，所以我更新了问题，添加了一个新条件（不改变用户的流程）。如果水果的价值每天随机变化（我无法控制它，因为我可以轻松地放置极端值来隔离可能性），那该怎么办？如果水果价格在变化，某些可能性是否会变得不太可能，并且随着时间的推移，可能性实际上会减少到更准确的结果？ - Lostsoul

不存在更可能或更不可能的事情，只有可能或不可能的事情。如果你知道它们是整数解，那么你可能可以排除一些解决方案，但仅此而已。 考虑用户从1000000、1000000和1000000开始，然后每次可以将每个值更改+/- 50000。因此，限制每个步骤的差异并不重要。 - Luka Rahne

我同意你的观点并感谢你的解释。我在思考有两件事情需要解决才能得出答案。一是要限制可能性。如果总价值为5美元，而苹果价格飙升到100美元，那么显然用户没有苹果，所以我可以排除这种情况，以此类推，直到我得到一个范围。一旦我有了这个范围，我认为可以进行一个简单的猜谜游戏结构。不过，这个问题的重点并不是得到最精确的答案（虽然这很好），而是如何实现最窄的范围。 - Lostsoul

Answer 4

我写了一个程序来玩这个游戏。当然，我必须自动化人类方面，但我相信我做到了这一点，使得在与真正的人类对战时不会使我的方法无效。

我从机器学习的角度来处理这个问题，并将问题视为一个隐马尔可夫模型，其中总价格是观察值。我的解决方案是使用粒子滤波器。此解决方案使用Python 2.7编写，使用NumPy和SciPy库。

我在注释中明确说明了我所做的任何假设或者隐含在代码中的假设。我还设置了一些额外的限制，以便以自动化方式运行代码。它不是特别优化的，因为我试图在易懂性和速度之间取得平衡。

每次迭代都会输出当前真实数量和猜测值。我只是将输出导向文件，以便我可以轻松地查看它。有趣的扩展将是在二维（两种水果）或三维（三种水果）图上绘制输出。然后，您将能够看到粒子滤波器如何磨合出解决方案。

更新：

编辑了代码以包括调整后的参数。包括使用matplotlib（通过pylab）进行绘图调用。绘图在Linux-Gnome上可用，您的里程可能会有所不同。将NUM_FRUITS默认为2以支持绘图。只需注释掉所有pylab调用即可删除绘图并能够更改NUM_FRUITS为任何值。

在估计由未知量X价格表示的当前函数方面表现良好。在二维（两种水果）中，这是一条线，在三维（三种水果）中，它将是一个平面。粒子滤波器似乎缺少足够的数据来可靠地磨合出正确的数量。需要在粒子滤波器之上添加一些智能才能真正整合历史信息。您可以尝试将粒子滤波器转换为二阶或三阶。

更新2：

我一直在玩我的代码。我尝试了很多东西，现在呈现最终程序（开始对这个想法感到厌倦）。

更改：

现在，粒子使用浮点数而不是整数。不确定是否有任何有意义的影响，但这是一个更通用的解决方案。仅在进行猜测时进行四舍五入取整。

绘图显示真实数量为绿色方块，当前猜测为红色方块。当前信任的粒子显示为蓝色点（按我们相信它们的程度大小）。这使得很容易看出算法的工作效果。 （绘图在Win 7 64位上测试并正常工作）。

添加了关闭/打开数量更改和价格更改的参数。当然，两者都关闭是无聊的。

它做得相当不错，但正如已经指出的那样，这是一个非常棘手的问题，因此很难得到精确的答案。关闭CHANGE_QUANTITIES可以产生最简单的情况。您可以通过使用CHANGE_QUANTITIES关闭并带有2种水果来运行，以了解问题的难度。然后看看它如何迅速锁定正确的答案，再看看在增加水果数量时它变得更加困难。

您还可以通过保持CHANGE_QUANTITIES打开，但将MAX_QUANTITY_CHANGE从非常小的值（.001）调整为“大”值（.05），来了解问题的难度。

它遇到困难的一种情况是如果一个维度（一个水果数量）接近于零。因为它使用粒子的平均值来猜测，所以它总是会偏离像零这样的硬边界。

总的来说，这是一个很好的粒子滤波器教程。

from __future__ import division
import random
import numpy
import scipy.stats
import pylab

# Assume Guesser knows prices and total
# Guesser must determine the quantities

# All of pylab is just for graphing, comment out if undesired
#   Graphing only graphs first 2 FRUITS (first 2 dimensions)

NUM_FRUITS = 3
MAX_QUANTITY_CHANGE = .01 # Maximum percentage change that total quantity of fruit can change per iteration
MAX_QUANTITY = 100 # Bound for the sake of instantiating variables
MIN_QUANTITY_TOTAL = 10 # Prevent degenerate conditions where quantities all hit 0
MAX_FRUIT_PRICE = 1000 # Bound for the sake of instantiating variables
NUM_PARTICLES = 5000
NEW_PARTICLES = 500 # Num new particles to introduce each iteration after guessing
NUM_ITERATIONS = 20 # Max iterations to run
CHANGE_QUANTITIES = True
CHANGE_PRICES = True

'''
  Change individual fruit quantities for a random amount of time
  Never exceed changing fruit quantity by more than MAX_QUANTITY_CHANGE
'''
def updateQuantities(quantities):
  old_total = max(sum(quantities), MIN_QUANTITY_TOTAL)
  new_total = old_total
  max_change = int(old_total * MAX_QUANTITY_CHANGE)

  while random.random() > .005: # Stop Randomly    
    change_index = random.randint(0, len(quantities)-1)
    change_val = random.randint(-1*max_change,max_change)

    if quantities[change_index] + change_val >= 0: # Prevent negative quantities
      quantities[change_index] += change_val
      new_total += change_val

      if abs((new_total / old_total) - 1) > MAX_QUANTITY_CHANGE:
        quantities[change_index] -= change_val # Reverse the change

def totalPrice(prices, quantities):
  return sum(prices*quantities)

def sampleParticleSet(particles, fruit_prices, current_total, num_to_sample):
  # Assign weight to each particle using observation (observation is current_total)
  # Weight is the probability of that particle (guess) given the current observation
  # Determined by looking up the distance from the hyperplane (line, plane, hyperplane) in a
  #   probability density fxn for a normal distribution centered at 0 
  variance = 2
  distances_to_current_hyperplane = [abs(numpy.dot(particle, fruit_prices)-current_total)/numpy.linalg.norm(fruit_prices) for particle in particles]
  weights = numpy.array([scipy.stats.norm.pdf(distances_to_current_hyperplane[p], 0, variance) for p in range(0,NUM_PARTICLES)])

  weight_sum = sum(weights) # No need to normalize, as relative weights are fine, so just sample un-normalized

  # Create new particle set weighted by weights
  belief_particles = []
  belief_weights = []
  for p in range(0, num_to_sample):
    sample = random.uniform(0, weight_sum)
    # sum across weights until we exceed our sample, the weight we just summed is the index of the particle we'll use
    p_sum = 0
    p_i = -1
    while p_sum < sample:
      p_i += 1
      p_sum += weights[p_i]
    belief_particles.append(particles[p_i])
    belief_weights.append(weights[p_i])

  return belief_particles, numpy.array(belief_weights)

'''
  Generates new particles around the equation of the current prices and total (better particle generation than uniformly random)
'''
def generateNewParticles(current_total, fruit_prices, num_to_generate):
  new_particles = []
  max_values = [int(current_total/fruit_prices[n]) for n in range(0,NUM_FRUITS)]
  for p in range(0, num_to_generate):
    new_particle = numpy.array([random.uniform(1,max_values[n]) for n in range(0,NUM_FRUITS)])
    new_particle[-1] = (current_total - sum([new_particle[i]*fruit_prices[i] for i in range(0, NUM_FRUITS-1)])) / fruit_prices[-1]
    new_particles.append(new_particle)
  return new_particles


# Initialize our data structures:
# Represents users first round of quantity selection
fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])
fruit_quantities = numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)])
current_total = totalPrice(fruit_prices, fruit_quantities)
success = False

particles = generateNewParticles(current_total, fruit_prices, NUM_PARTICLES) #[numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) for p in range(0,NUM_PARTICLES)]
guess = numpy.average(particles, axis=0)
guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)])

print "Truth:", str(fruit_quantities)
print "Guess:", str(guess)

pylab.ion()
pylab.draw()
pylab.scatter([p[0] for p in particles], [p[1] for p in particles])
pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s')
pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s')
pylab.xlim(0, MAX_QUANTITY)
pylab.ylim(0, MAX_QUANTITY)
pylab.draw()

if not (guess == fruit_quantities).all():
  for i in range(0,NUM_ITERATIONS):
    print "------------------------", i

    if CHANGE_PRICES:
      fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])

    if CHANGE_QUANTITIES:
      updateQuantities(fruit_quantities)
      map(updateQuantities, particles) # Particle Filter Prediction

    print "Truth:", str(fruit_quantities)
    current_total = totalPrice(fruit_prices, fruit_quantities)

    # Guesser's Turn - Particle Filter:
    # Prediction done above if CHANGE_QUANTITIES is True

    # Update
    belief_particles, belief_weights = sampleParticleSet(particles, fruit_prices, current_total, NUM_PARTICLES-NEW_PARTICLES)
    new_particles = generateNewParticles(current_total, fruit_prices, NEW_PARTICLES)

    # Make a guess:
    guess = numpy.average(belief_particles, axis=0, weights=belief_weights) # Could optimize here by removing outliers or try using median
    guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) # convert to integers
    print "Guess:", str(guess)

    pylab.cla()
    #pylab.scatter([p[0] for p in new_particles], [p[1] for p in new_particles], c='y') # Plot new particles
    pylab.scatter([p[0] for p in belief_particles], [p[1] for p in belief_particles], s=belief_weights*50) # Plot current particles
    pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s') # Plot truth
    pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s') # Plot current guess
    pylab.xlim(0, MAX_QUANTITY)
    pylab.ylim(0, MAX_QUANTITY)
    pylab.draw()

    if (guess == fruit_quantities).all():
      success = True
      break

    # Attach new particles to existing particles for next run:
    belief_particles.extend(new_particles)
    particles = belief_particles
else:
  success = True

if success:
  print "Correct Quantities guessed"
else:
  print "Unable to get correct answer within", NUM_ITERATIONS, "iterations"

pylab.ioff()
pylab.show()

- Kyle

---

哇..我正要写一个回答我的问题，说这些答案很好，但我认为解决方案是一个隐马尔可夫或维特比算法。我收到一条消息说有一个新的答案被发布了，然后我刷新到了这个页面。非常好的答案。我会进行一些测试，并让你知道它的结果..谢谢Kyle。 - Lostsoul

看起来很有趣。我理解你的逻辑，但是我有几个问题。它似乎是随机猜测的。是否有一种方法可以包括不仅过去的总和，而且所有过去的总和（最后一个更加重要）？似乎每个答案都只接近上一个答案，但是如果回顾几个总和，建议的结果似乎与之前的无关。 - Lostsoul

它只代表了一个一阶隐马尔可夫模型，因此只关心一步。改进可以将其变为2阶或3阶。现在我正在调整参数以获得更好的结果。理论上，调整良好的一阶HMM应该是可以的，因为粒子“代表”它们来自哪里的历史记录。希望很快就会有调整良好且效果更好的更新。 - Kyle

@Kyle..非常感谢。我在其他论坛上询问了有关实现的问题，阅读了你的代码后，事情变得更加清晰。让它超过一个订单我认为会很有趣，因为我的最终目标是从虚构商店中为用户提供数百个选项，并让他们选择任意数量（我将尝试在hadoop上执行此操作并扩展到我家中的3台机器，但它能够快速解决问题就更好了）。非常感谢。 - Lostsoul

经调整参数后，我已经成功使粒子滤波器运行良好，但是它需要更聪明的东西。它能很好地估计通过未知量X价格=总价所表示的当前函数。 (当NUM_FRUITS==2时，这是一条线，3->平面)。因此，我的下一个想法是先估计线，然后从该线上采样新的粒子(而不是均匀采样)。这可能就足够了。或者您可能需要在其之上加入更智能的东西。我将更新我的代码，包括使用matplotlib进行可视化绘图(非常有帮助)。 - Kyle

Answer 5

对于您的初始规则：

从我的学校时代开始，如果我们抽象出5%的变化，我们每天都有一个具有三个未知值（抱歉我不知道英语中的数学词汇）的方程，这些值与前一天相同。在第三天，您有三个方程式，三个未知值，解决方案应该是直接的。

我想，如果这三个元素的值足够不同，每天的5％变化可能会被遗忘，因为如您所说，我们将使用近似值并四舍五入数字。

对于您的调整后的规则：

在这种情况下，有太多未知值且值发生更改，因此我不知道任何直接的解决方案。如果价格和数量的范围有限，我会信任Lior；他的方法看起来很好！

- Pierre Sevrain

Answer 6

我意识到我的答案变得相当冗长，因此我将代码移到了顶部（这可能是大多数人感兴趣的）。 在它下面有两件事情：

1. 为什么（深度）神经网络不是解决这个问题的好方法的解释
2. 为什么我们不能通过给定的信息唯一确定人类的选择的解释。

对于那些对任一主题感兴趣的人，请参见以下内容。 对于其余的人，这里是代码。

---

查找所有可能解决方案的代码

正如我在回答中进一步解释的那样，你的问题是欠定的。在平均情况下，存在许多可能的解决方案，并且随着天数的增加，这个数量至少呈指数级增长。这对于原始问题和扩展问题都是正确的。尽管如此，我们可以（在某种程度上）有效地找到所有解决方案（它是NP难问题，所以不要期望太多）。

回溯算法（来自20世纪60年代，因此并不是现代算法）是此处的首选算法。在Python中，我们可以将其编写为递归生成器，实际上相当优雅：

def backtrack(pos, daily_total, daily_item_value, allowed_change, iterator_bounds, history=None):
    if pos == len(daily_total):
        yield np.array(history)
        return

    it = [range(start, stop, step) for start, stop, step in iterator_bounds[pos][:-1]]
    for partial_basket in product(*it):
        if history is None:
            history = [partial_basket]
        else:
            history.append(partial_basket)

        # ensure we only check items that match the total basket value
        # for that day
        partial_value = np.sum(np.array(partial_basket) * daily_item_value[pos, :-1])
        if (daily_total[pos] - partial_value) % daily_item_value[pos, -1] != 0:
            history.pop()
            continue

        last_item = (daily_total[pos] - partial_value) // daily_item_value[pos, -1]
        if last_item < 0:
            history.pop()
            continue

        basket = np.array([*partial_basket] + [int(last_item)])
        basket_value = np.sum(basket * daily_item_value[pos])
        history[-1] = basket
        if len(history) > 1:
            # ensure that today's basket stays within yesterday's range
            previous_basket = history[-2]
            previous_basket_count = np.sum(previous_basket)
            current_basket_count = np.sum(basket)
            if (np.abs(current_basket_count - previous_basket_count) > allowed_change * previous_basket_count):
                history.pop()
                continue

        yield from backtrack(pos + 1, daily_total, daily_item_value, allowed_change, iterator_bounds, history)
        history.pop()

这种方法基本上会将所有可能的候选项构造成一棵大树，然后在违反约束条件时进行修剪的深度优先搜索。每当遇到一个叶节点时，我们就会产生结果。

（通常情况下）可以并行进行树搜索，但这超出了本文的范围。这将使解决方案更难读，而又不会提供更多的见解。同样的道理也适用于减少代码中的常数开销，例如将“if ...: continue”限制条件转换为“iterator_bounds”变量，并进行更少的检查。

我将完整的代码示例（包括游戏人类方面的模拟器）放在了本答案底部。

---

这个问题的现代机器学习方法

虽然这个问题已经有9年了，但我仍然对它深感兴趣。在此期间，随着机器学习（如RNN、CNN、GAN等）、新方法和廉价GPU的出现，出现了一些新的方法。我认为重新审视这个问题是很有趣的，看看是否有新的方法。

我非常喜欢你对深度神经网络世界的热情，但不幸的是，它们在这里并不适用，原因有几个：

1. (精确性) 如果您需要一个精确的解决方案，比如用于游戏，神经网络无法提供。
2. (整数约束) 目前主导的神经网络训练方法是基于梯度下降的，因此问题必须可微分，或者您需要能够重新表述它，使其变得可微分；将自己限制在整数上会扼杀梯度下降方法。您可以尝试使用进化算法来搜索参数化。这种方法确实存在，但目前还没有被广泛应用。
3. (非凸性) 在典型的公式中，训练神经网络是一种局部方法，这意味着如果您的算法收敛，您将找到恰好1个（局部最优）解决方案。在平均情况下，您的游戏对于原始和扩展版本都有许多可能的解决方案。这不仅意味着 - 平均而言 - 您无法弄清人类的选择（篮子），而且您无法控制神经网络将找到哪个解决方案中的众多解决方案。当前的神经网络成功案例遭受同样的命运，但它们往往不真正关心，因为它们只想要一些解决方案而不是特定的解决方案。一些还算可以的解决方案胜过没有解决方案。
4. (专家领域知识) 对于这个游戏，您拥有许多可以利用以改善优化/学习的领域知识。充分利用神经网络中的任意领域知识并不容易，对于这个游戏来说，构建一个自定义的机器学习模型（而不是神经网络）会更容易和更有效。

---

为什么游戏无法唯一解决 - 第1部分

首先考虑一个替代问题，并取消整数要求，即篮子（人类选择给定日期的N个水果）可以有分数水果（0.3个橙子）。

总价值约束np.dot(basket, daily_price) == total_value限制了篮子的可能解；它将问题减少了一个维度。自由选择N-1个水果的数量，您总是可以找到第N个水果的价值以满足约束条件。因此，尽管似乎每天有N个选择，但实际上我们只能自由地进行N-1个选择，最后一个选择将完全由我们之前的选择确定。因此，对于游戏进行的每一天，我们需要估计额外的N-1个选择/变量。

我们可能希望强制所有选择都大于0，但这只会减少我们可以选择数字的区间；任何实数的开区间都有无限多的数字，因此我们永远不会因此耗尽选择。仍然需要做N-1个选择。

在两天之间，总篮子体积np.sum(basket)最多只会变化不超过前一天的some_percent，即np.abs(np.sum(previous_basket) - np.sum(basket)) <= some_percent * np.sum(previous_basket)。在某一天，我们所做的一些选择可能会使篮子比前一天增加some_percent以上。为确保不违反此规定，我们可以自由地进行N-2次选择，然后必须选择第N-1个变量，以便将其添加并使得添加N个变量（这是从我们先前的选择中固定的）仍保持在some_percent之内。（注意：这是一个不等式约束条件，因此它只会减少选择的数量，如果我们有相等的情况，即篮子的变化恰好为some_percent。在优化理论中，这被称为约束条件处于激活状态。）

我们再次考虑所有选择都应大于0的约束条件，但是这个论点仅改变了我们现在可以自由选择N-2个变量的区间。

所以在D天后，我们只剩下N-1个选择来估计第一天（没有改变约束），每个接下来的一天有(D-1)*(N-2)个选择来进行估计。不幸的是，我们已经用完了进一步减少这个数字的约束条件，并且未知数每天至少增加N-2个。这基本上就是Luka Rahne所说的“对于所有N>2，2*D < N*D”。我们可能会找到许多同样可能的候选解决方案。

每天的确切食品价格并不重要。只要它们具有某些价值，它们就会限制其中一个选择。因此，如果您按照指定的方式扩展游戏，则始终存在无限多个解决方案的机会；无论天数多少。

---

为什么游戏仍然无法被唯一解决-第二部分

有一个我们没有考虑过的限制，可能会帮助解决这个问题：只允许整数解。整数约束的问题在于它们处理起来非常复杂。然而，我们主要关心的是，如果添加这个限制，是否足以在足够的天数内唯一解决问题。对此，有一个相当直观的反例。假设你有3天连续时间，在第1天和第3天，总价值约束只允许一个篮子。换句话说，我们知道第1天和第3天的篮子，但不知道第2天的篮子。在这里，我们只知道它的总价值，它在第1天的某个百分比范围内，并且第3天在第2天的某个百分比范围内。这些信息足以始终确定第2天篮子里的东西吗？

some_percent = 0.05
Day 1: basket: [3 2]  prices: [10 7]  total_value: 44
Day 2: basket: [x y]  prices: [5  5]  total_value: 25
Day 3: basket: [2 3]  prices: [9  5]  total_value: 33

Possible Solutions Day 2: [2 3], [3 2]

上面是一个例子，我们通过总价值约束条件知道了两天的价值，但这仍然无法让我们计算出第二天篮子的确切组成。因此，虽然在某些情况下可能可以计算出来，但通常情况下是不可能的。添加第3天之后的更多天数根本无法帮助我们弄清第2天的情况。它可能有助于缩小第3天的选项（从而缩小第2天的选项），但我们对第3天只剩下1个选择，所以没有用处。

---

完整的代码

import numpy as np
from itertools import product
import tqdm


def sample_uniform(n, r):
    # check out: http://compneuro.uwaterloo.ca/files/publications/voelker.2017.pdf
    sample = np.random.rand(n + 2)
    sample_norm = np.linalg.norm(sample)
    unit_sample = (sample / sample_norm)
    change = np.floor(r * unit_sample[:-2]).astype(np.int)
    return change


def human(num_fruits, allowed_change=0.05, current_distribution=None):
    allowed_change = 0.05
    if current_distribution is None:
        current_distribution = np.random.randint(1, 50, size=num_fruits)
    yield current_distribution.copy()

    # rejection sample a suitable change
    while True:
        current_total = np.sum(current_distribution)
        maximum_change = np.floor(allowed_change * current_total)

        change = sample_uniform(num_fruits, maximum_change)
        while np.sum(change) > maximum_change:
            change = sample_uniform(num_fruits, maximum_change)

        current_distribution += change
        yield current_distribution.copy()


def prices(num_fruits, alter_prices=False):
    current_prices = np.random.randint(1, 10, size=num_fruits)
    while True:
        yield current_prices.copy()
        if alter_prices:
            current_prices = np.random.randint(1, 10, size=num_fruits)


def play_game(num_days, num_fruits=3, alter_prices=False):
    human_choice = human(num_fruits)
    price_development = prices(num_fruits, alter_prices=alter_prices)

    history = {
        "basket": list(),
        "prices": list(),
        "total": list()
    }
    for day in range(num_days):
        choice = next(human_choice)
        price = next(price_development)
        total_price = np.sum(choice * price)

        history["basket"].append(choice)
        history["prices"].append(price)
        history["total"].append(total_price)

    return history


def backtrack(pos, daily_total, daily_item_value, allowed_change, iterator_bounds, history=None):
    if pos == len(daily_total):
        yield np.array(history)
        return

    it = [range(start, stop, step) for start, stop, step in iterator_bounds[pos][:-1]]
    for partial_basket in product(*it):
        if history is None:
            history = [partial_basket]
        else:
            history.append(partial_basket)

        # ensure we only check items that match the total basket value
        # for that day
        partial_value = np.sum(np.array(partial_basket) * daily_item_value[pos, :-1])
        if (daily_total[pos] - partial_value) % daily_item_value[pos, -1] != 0:
            history.pop()
            continue

        last_item = (daily_total[pos] - partial_value) // daily_item_value[pos, -1]
        if last_item < 0:
            history.pop()
            continue

        basket = np.array([*partial_basket] + [int(last_item)])
        basket_value = np.sum(basket * daily_item_value[pos])
        history[-1] = basket
        if len(history) > 1:
            # ensure that today's basket stays within relative tolerance
            previous_basket = history[-2]
            previous_basket_count = np.sum(previous_basket)
            current_basket_count = np.sum(basket)
            if (np.abs(current_basket_count - previous_basket_count) > allowed_change * previous_basket_count):
                history.pop()
                continue

        yield from backtrack(pos + 1, daily_total, daily_item_value, allowed_change, iterator_bounds, history)
        history.pop()


if __name__ == "__main__":
    np.random.seed(1337)
    num_fruits = 3
    allowed_change = 0.05
    alter_prices = False
    history = play_game(15, num_fruits=num_fruits, alter_prices=alter_prices)

    total_price = np.stack(history["total"]).astype(np.int)
    daily_price = np.stack(history["prices"]).astype(np.int)
    basket = np.stack(history["basket"]).astype(np.int)

    maximum_fruits = np.floor(total_price[:, np.newaxis] / daily_price).astype(np.int)
    iterator_bounds = [[[0, maximum_fruits[pos, fruit], 1] for fruit in range(num_fruits)] for pos in range(len(basket))]
    # iterator_bounds = np.array(iterator_bounds)
    # import pdb; pdb.set_trace()

    pbar = tqdm.tqdm(backtrack(0, total_price,
                               daily_price, allowed_change, iterator_bounds), desc="Found Solutions")
    for solution in pbar:
        # test price guess
        calculated_price = np.sum(np.stack(solution) * daily_price, axis=1)
        assert np.all(calculated_price == total_price)

        # test basket change constraint
        change = np.sum(np.diff(solution, axis=0), axis=1)
        max_change = np.sum(solution[:-1, ...], axis=1) * allowed_change
        assert np.all(change <= max_change)

        # indicate that we found the original solution
        if not np.any(solution - basket):
            pbar.set_description("Found Solutions (includes original)")

- FirefoxMetzger

Answer 7

当玩家选择一种组合，可以将可能性减少到1时，计算机将获胜。否则，玩家可以在总体变化在一定百分比的约束下选择组合，这样计算机就永远不会获胜。

import itertools
import numpy as np


def gen_possible_combination(total, prices):
    """
    Generates all possible combinations of numbers of items for
    given prices constraint by total
    """
    nitems = [range(total//p + 1) for p in prices]
    prices_arr = np.array(prices)
    combo = [x for x in itertools.product(
        *nitems) if np.dot(np.array(x), prices_arr) == total]

    return combo


def reduce(combo1, combo2, pct):
    """
    Filters impossible transitions which are greater than pct
    """
    combo = {}
    for x in combo1:
        for y in combo2:
            if abs(sum(x) - sum(y))/sum(x) <= pct:
                combo[y] = 1

    return list(combo.keys())


def gen_items(n, total):
    """
    Generates a list of items
    """
    nums = [0] * n
    t = 0
    i = 0
    while t < total:
        if i < n - 1:
            n1 = np.random.randint(0, total-t)
            nums[i] = n1
            t += n1
            i += 1
        else:
            nums[i] = total - t
            t = total

    return nums


def main():
    pct = 0.05
    i = 0
    done = False
    n = 3
    total_items = 26  # np.random.randint(26)
    combo = None
    while not done:
        prices = [np.random.randint(1, 10) for _ in range(n)]
        items = gen_items(n, total_items)

        total = np.dot(np.array(prices),  np.array(items))
        combo1 = gen_possible_combination(total, prices)

        if combo:
            combo = reduce(combo, combo1, pct)
        else:
            combo = combo1
        i += 1
        print(i, 'Items:', items, 'Prices:', prices, 'Total:',
              total, 'No. Possibilities:', len(combo))

        if len(combo) == 1:
            print('Solution', combo)
            break
        if np.random.random() < 0.5:
            total_items = int(total_items * (1 + np.random.random()*pct))
        else:
            total_items = int(
                np.ceil(total_items * (1 - np.random.random()*pct)))


if __name__ == "__main__":
    main()

- Pramote Kuacharoen