如何设计一个有趣的数字猜谜游戏算法？
更新（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美元，可能有一个字典条目{苹果:143，梨:0，橙子:0}，一直到{苹果:0，梨:1，橙子:47}。每次我得到一个新数字时，我都会这样做，所以我有一个所有可能性的列表。
这是我卡住的地方。根据上述规则，我该如何找出最佳解决方案？我觉得我需要一个适应度函数，自动比较两天的数据，并去除与前一天数据差异超过5%的可能性。
问题：
所以我想问的是，用户改变总数，而我有所有概率的列表，我该如何处理？我需要学习什么？有没有适用的算法或理论可以使用？或者，为了帮助我理解我的错误，你能建议我可以添加什么规则来使这个目标可行（如果它在当前状态下不可行。我在想增加更多水果，并要求他们至少选择3种等等）？另外，我对遗传算法只有模糊的理解，但我觉得我可以在这里使用它们，有没有什么可以用的？
我非常渴望学习，所以任何建议或提示都将非常感激（请不要告诉我这个游戏是不可能的）。
更新：收到反馈说这个问题很难解决。所以我想在游戏中添加另一个条件，这不会干扰玩家的操作（对他们来说游戏保持不变），但每天水果的价格会随机变化。这会让解决问题变得更容易吗？因为在5%的波动和某些水果价格变化下，随着时间的推移，只有少数组合是可能的。
第一天，任何组合都是可能的，得到一个足够接近的范围几乎是不可能的，但随着水果价格的变化，用户只能选择5%的变化，那么（随着时间的推移）范围应该会越来越窄。在上面的例子中，如果价格波动足够，我觉得我可以通过暴力破解找到一个范围来猜测，但我在试图找出是否有更优雅的解决方案或其他解决方案来不断缩小这个范围。
更新2：在阅读和询问后，我相信这是一个隐藏的马尔可夫/Viterbi问题，它跟踪水果价格的变化以及总和（加重最近的数据点）。但我不确定如何应用这个关系。我认为是这样，但可能错了，但至少我开始怀疑这是一种机器学习问题。
更新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
7 个回答
这个问题是无法解决的。
假设你确切知道物品数量增加的比例，而不仅仅是知道这个比例的最大值。
一个用户有 N 个水果，而你有 D 天的时间来猜测。
在每一天，你会得到 N 个新的变量，这样你总共有 D*N 个变量。
在每一天，你只能生成两个方程。一个方程是水果数量乘以价格的总和，另一个方程是基于已知比例的。总的来说，如果这些方程都是独立的，你最多可以有 2*D 个方程。
对于所有 N 大于 2 的情况，2*D 小于 N*D。
免责声明：在暂时删除我的回答并仔细重新阅读问题后，我对我的回答进行了重大修改，因为我误解了一些关键部分。虽然仍然参考了类似的主题和算法，但在我尝试用C#解决一些问题后，答案得到了很大改善。
好莱坞版
- 这个问题是一个动态约束满足问题（DCSP），是约束满足问题（CSP）的一个变种。
- 如果数值和数量范围不小，可以使用蒙特卡洛方法来寻找给定日期的潜在解决方案。否则，使用暴力破解来找到所有可能的解决方案。
- 使用与DCSP相关的约束记录，将其应用于前几天，以限制潜在解决方案的集合。
- 交叉你的手指，瞄准并射击（猜测），基于概率。
- （可选）布鲁斯·威利斯获胜。
原版
首先，我想说我看到这里有两个主要问题：
可能解决方案的数量庞大。仅知道物品数量和总价值，比如说3和143，将会产生很多可能的解决方案。而且，算法在选择有效解决方案时，不可避免地会尝试无效的解决方案（总和不等于143）。
当为某一天Di找到可能的解决方案时，必须找到一种方法来利用{ Di+1 .. Di+n }提供的附加信息来消除潜在解决方案。
让我们为接下来的例子奠定一些基础：
- 保持相同的物品价值，整个游戏可以是随机的，也可以由用户选择。
- 可能的物品价值限制在非常有限的范围[1-10]内，且没有两个物品可以有相同的价值。
- 任何物品的数量不能超过100。这意味着：[0-100]。
为了更容易解决这个问题我擅自改变了一个约束，这使得算法收敛得更快：
- 用这个规则覆盖“总数量”规则：你可以在一天内添加或移除任意数量的物品，范围在[1-10]内。然而，你不能在总数上添加或移除相同数量的物品超过两次。这也给游戏设定了20天的最大生命周期。
这个规则使我们更容易排除解决方案。而且，在非小范围内，使得回溯算法仍然无用，就像你最初的问题和规则一样。
在我看来，这个规则不是游戏的本质，而只是一个促进因素，使计算机能够解决问题。
问题1：寻找潜在解决方案
首先，问题1可以使用蒙特卡洛算法来找到一组潜在解决方案。这个技术很简单：为物品的价值和数量生成随机数（在各自的接受范围内）。重复这个过程，直到达到所需的物品数量。验证解决方案是否可接受。这意味着要验证物品是否具有不同的价值，并且总和是否等于我们的目标总和（比如说143）。
虽然这个技术的优点是易于实现，但也有一些缺点：
- 用户的解决方案不一定会出现在我们的结果中。
- 有很多“失误”。例如，在我们的约束条件下，找到1000个潜在解决方案大约需要300万次尝试。
- 需要很长时间：在我这台慢腾腾的笔记本上，大约需要4到5秒。
如何解决这些缺点呢？好吧……
- 将范围限制为更小的值，并且
- 找到适当数量的潜在解决方案，以便用户的解决方案有很大机会出现在你的解决方案集中。
- 使用启发式方法更容易找到解决方案（稍后会详细介绍）。
请注意，越是限制范围，蒙特卡洛算法的效果就越差，因为有效解决方案的数量会少到足以在合理的时间内遍历所有解决方案。对于约束{ 3, [1-10], [0-100] }，大约有741,000,000个有效解决方案（不限制目标总值）。在这里可以使用蒙特卡洛方法。对于{ 3, [1-5], [0-10] }，只有大约80,000个。没有必要使用蒙特卡洛；暴力循环for就可以了。
我认为问题1可以称为约束满足问题（CSP）。
问题2：限制潜在解决方案的集合
鉴于问题1是一个CSP，我会继续称问题2以及一般问题为动态CSP（DCSP）。
[DCSP]在某种程度上改变了问题的原始表述，通常是因为需要考虑的约束集因环境而变化。DCSP被视为一系列静态CSP，每一个都是前一个的变换，其中可以添加（限制）或删除（放松）变量和约束。
与CSP相关的一种可能对这个问题有用的技术是约束记录：
- 随着环境的每次变化（用户输入Di+1的值），找到关于新约束的信息：对于添加-移除约束，可能“使用”的数量是什么。
- 将约束级联应用于每个前一天。涟漪效应可能会显著减少可能的解决方案。
为了使其有效，你需要每天获取一组新的可能解决方案；使用暴力破解或蒙特卡洛方法。然后，将Di的解决方案与Di-1进行比较，仅保留能够成功满足前几天解决方案的解决方案，而不违反约束。
你可能需要保留一个历史记录，记录哪些解决方案导致了其他解决方案（可能在一个有向图中）。约束记录使你能够记住可能的添加-移除数量，并根据此拒绝解决方案。
还有很多其他步骤可以进一步改善你的解决方案。以下是一些想法：
- 记录在前几天解决方案中找到的物品-价值组合的约束。立即拒绝其他解决方案（因为物品价值不能改变）。你甚至可以为每个现有解决方案找到更小的解决方案集，使用特定于解决方案的约束来更早地拒绝无效解决方案。
- 每天生成一些“变异”的完整历史解决方案，以“修复”D1解决方案集中不包含用户解决方案的情况。你可以使用遗传算法根据现有解决方案集找到变异种群。
- 使用启发式方法更容易找到解决方案（例如，当找到有效解决方案时，尝试通过调整数量来寻找该解决方案的变体）。
- 使用行为启发式方法来预测一些用户行为（例如，每个物品相同数量、极端模式等）。
- 在用户输入新数量时，继续进行一些计算。
考虑到这一切，尝试根据解决方案的出现频率和启发式方法来制定一个候选解决方案的排名系统。
我们将结合图论和概率来讲解这个问题：
在第一天，建立一个所有可行解的集合。我们把这个解的集合称为 A1={a1(1), a1(2),...,a1(n)}。
在第二天，你可以再次建立解的集合 A2。
现在，对于 A2 中的每一个元素，你需要检查它是否可以从 A1 中的每一个元素到达（考虑 x% 的容忍度）。如果可以，就把 A2(n) 和 A1(m) 连接起来。如果从 A1(m) 中的任何节点都无法到达这个节点，那么你可以删除这个节点。
基本上，我们是在构建一个有向无环图，也就是一个连接起来的图。
图中的所有路径都是同样可能的。只有当从 Am 到 Am+1 之间有一条单一的边时，你才能找到一个确切的解（也就是从 Am 中的一个节点到 Am+1 中的一个节点）。
当然，有些节点出现在更多的路径中，而其他节点则较少。每个节点的概率可以直接根据包含这个节点的路径数量来推导。
通过给每个节点分配一个权重，这个权重等于通往这个节点的路径数量，你就不需要保留所有的历史记录，只需保留前一天的数据即可。
另外，可以看看 非负值线性丢番图方程 - 这是我之前问过的一个问题。被接受的答案是一个很好的方法，可以在每一步列举所有组合。