如何处理数字猜测游戏（一个扭曲）algorithm？

我正在学习编程（python和algorithm），并试图在一个我觉得有趣的项目上工作。 我已经创build了几个基本的Python脚本，但我不知道如何解决我正在尝试构build的游戏的解决scheme。

以下是游戏的运作方式：

用户将被赋予具有价值的项目。 例如

Apple = 1 Pears = 2 Oranges = 3 

他们将有机会select他们喜欢的任何组合（即100个苹果，20个梨子和1个桔子）。 计算机唯一的输出是总价值（在这个例子中，目前是143美元）。 电脑会试图猜测他们有什么。 这显然不能够正确的第一回合。

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

接下来用户可以修改他们的数量，但不超过总数量的5％（或者我们可能select的其他百分比，例如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 

*（我希望表格显示正确，我不得不手动将它们放在空间上，所以希望它不只是在我的屏幕上做，如果它不工作，让我知道，我会尝试上传截图）。

我试图看看能否计算出数量随时间的变化（假设用户将有耐心继续input数字）。 我现在知道我唯一的限制就是总价值不能超过5％，所以现在我的准确率不能超过5％，所以用户会永远进入。

我到目前为止所做的

这是我的解决scheme迄今（不多）。 基本上我把所有的价值都拿出来，弄清楚他们所有可能的组合（我完成了这部分）。 然后，我把所有可能的组合，并把它们放在一个数据库作为一个字典（例如为143美元，可能是一个字典条目{苹果：143，梨：0，橙子：0} ..一路{苹果：0，Pears：1，Oranges：47}。每当我得到一个新的数字时，我都会这样做，所以我列出了所有的可能性。

这是我卡住的地方。 正在使用上面的规则，我怎样才能找出最好的解决scheme？ 我想我需要一个适应度函数来自动比较两天的数据，并消除前几天数据差异超过5％的可能性。

问题：

所以我的问题与用户改变总数和我有一个所有的概率列表，我应该如何处理这个？ 我需要学习什么？ 有没有什么algorithm或我可以使用的理论是适用的？ 或者，为了帮助我理解我的错误，你能提出一些我可以添加的规则来实现这个目标吗（如果它不是目前的状态，我想增加更多的水果，并且说他们必须至lessselect3个）。 ？ 此外，我只是对遗传algorithm有一个模糊的理解，但是我想我可以在这里使用它们，如果有什么我可以使用的？

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

提前致谢。

更新：获得反馈，这是很难解决的。 所以我想我会给游戏添加另一个条件，不会干扰玩家的行为（游戏保持不变），但是每天水果的价值会随着价格的变化而变化。 这会更容易解决吗？ 因为在5％的运动和某些水果价值的变化，只有less数组合可能随着时间的推移。 第一天，任何事情都是可能的，并且接近足够的范围几乎是不可能的，但是随着水果价格的变化和用户只能select5％的变化，那么不应该（随着时间的推移）范围狭窄和狭窄。 在上面的例子中，如果价格足够波动，我想我可以蛮横的强制给我一个猜测范围的解决scheme，但我试图找出是否有更优雅的解决scheme或其他解决scheme来缩小这个范围时间。

更新2：在阅读和询问后，我认为这是一个隐藏的马尔可夫/维特比问题，跟踪水果价格的变化以及总额（加权最后一个数据点）。 我不知道如何应用这种关系。 我认为是这样，可能是错的，但至less我开始怀疑这是一种机器学习问题。

Update3：我创build了一个testing用例（数字较小）和一个生成器来帮助自动生成用户生成的数据，我试图从中创build一个图表来查看更可能的情况。 这里是代码，以及用户实际水果数量的总值和评论。

 #!/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 

Answer 1

我们将结合图论和概率：

第一天，build立一整套切实可行的解决scheme。 让我们表示解为A1 = {a1（1），a1（2），…，a1（n）}。

在第二天，你可以再次build立解决schemeA2。

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

基本上我们正在build立一个连接的有向无环图。

图中所有path的可能性相同。 只有当从Am到Am + 1（从Am中的节点到Am + 1中的节点）存在单个边时，才能find确切的解。

当然，有些节点出现在比其他节点更多的path上。 每个节点的概率可以根据包含该节点的path的数量直接推导出来。

通过给每个节点分配一个权重（等于通向这个节点的path数量），不需要保留所有历史，而只需要保留前一天。

另外，看看非负值的线性双模式方程 – 前一个问题。 接受的答案是一个伟大的方式来鼓励所有的组合在每一步。

Answer 2

这个问题是不可能解决的。 让我们说，你确切地知道什么比例的项目数量增加，而不是什么是最大的比例。

用户有N个水果，你有D天的猜测。

在每一天你得到N个新的variables，然后你总共有D * N个variables。

每天只能生成2个方程。 一个方程是n_item *价格的总和，另一个方法是基于已知比率。 如果它们都是独立的，那么总共至多有2 * D个方程。

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

Answer 3

免责声明：我暂时删除了我的答案，并仔细地重读了这个问题，因为我误解了一些关键的问题。 虽然仍然参考了类似的主题和algorithm，但是在我尝试自己解决C＃中的一些问题之后，答案大大改善了。

好莱坞版本

• 问题是dynamic约束满足问题 （DCSP）， 约束满足问题 （CSP）的变体
• 如果数值和数量范围不是很小，那么使用蒙特卡罗（Monte Carlo）来查找给定date的潜在解决scheme。 否则，用蛮力find每一个可能的解决scheme。
• 使用约束logging （与DCSP相关），以前几天级联应用来限制潜在的解决scheme集。
• 交叉你的手指，瞄准和射击 （猜测），基于概率。
• （可选）布鲁斯·威利斯获胜。

原始版本

首先，我想说明我在这里看到两个主要问题：

1. 可能的解决scheme的绝对数量。 只知道物品的数量和总价值，比如说3和143会产生很多可能的解决scheme。 另外，如果没有不可避免地尝试无效解决scheme（总数不等于143），select有效的解决scheme并不容易。

2. 当在给定dateD _i中find可能的解决scheme时，必须find一种消除具有由{D _{i + 1} ，D _{i + n} }给出的附加信息的潜在解的方法。

让我们为即将到来的例子奠定一些基础：

• 让我们保持相同的项目值，整个游戏。 它可以是随机的或由用户select。
• 可能的项目值被绑定到[1-10]的非常有限的范围，其中没有两个项目可以具有相同的值。
• 没有项目的数量可以大于100.这意味着：[0-100]。

为了更容易地解决这个问题， 我冒昧地改变了一个约束 ，这使得algorithm更快地收敛：

• “总量”规则被以下规则覆盖：您可以在一天内添加或删除[1-10]范围内的任意数量的项目。 但是，您无法添加或删除相同数量的项目，总计超过两次。 这也给了游戏20天的最大生命周期。

这一规则使我们能够更容易地排除解决scheme。 而且，在非微小范围内，渲染回溯algorithm仍然无用，就像您原来的问题和规则一样。

在我看来，这个规则不是游戏的本质 ，而只是一个引导者，使计算机能够解决问题。

问题1：find潜在的解决scheme

对于初学者来说，可以使用Monte Carloalgorithm来解决问题1 ，以find一组潜在的解决scheme。 技巧很简单：为项目值和数量生成随机数（在各自可接受的范围内）。 重复所需数量的项目的过程。 validation解决scheme是否可接受。 这意味着要validation项目是否具有不同的价值，总额是否等于我们的目标总额（比如143.）

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

• 用户的解决scheme不保证出现在我们的结果中。
• 有很多“错过”。 例如，考虑到我们的限制，需要或多或less地尝试find1000个潜在的解决scheme。
• 这需要很长的时间：懒惰的笔记本电脑需要4到5秒。

如何解决这些缺点？ 好…

• 将范围限制为较小的值
• find足够数量的潜在解决scheme，以便用户的解决scheme出现在您的解决scheme集中。
• 使用启发式方法更容易地find解决scheme（稍后再介绍）。

请注意，限制范围越多，蒙特卡罗algorithm的有用性就越低，因为在合理的时间内将不会有足够的有效解决scheme来迭代它们。 对于约束{3，[1-10]，[0-100]}，大约有741,000,000个有效解（不限于目标总值）。蒙特卡罗在那里可用。 对于{3，[1-5]，[0-10]}，只有大约80,000。 不需要使用蒙特卡罗; 蛮力for循环会做得很好。

我相信问题1就是你所说的约束满足问题 （或CSP）。

问题2：限制一套潜在的解决scheme

考虑到问题1是一个CSP的问题 ，我会继续讨论问题2 ，而一般的问题是dynamicCSP （或DCSP）。

当一个问题的原始expression式以某种方式被改变时，[DCSPs]是有用的，通常是因为由于环境而考虑的一组约束条件会发生变化。 DCSP被看作是一系列静态CSP，每一个都是前一个variables和约束可以被添加（限制）或去除（放宽）的变换。

与CSP一起使用的一种可能对这个问题有用的技术叫做约束logging ：

• 随着环境的每一次改变（用户为D _{i + 1}input的值），find关于新约束的信息：添加移除约束可能“使用”的量是多less。
• 将约束应用于前一天的级联。 涟漪效应可能显着减less可能的解决scheme。

为了这个工作，你需要每天获得一套新的可能的解决scheme; 使用蛮力或蒙特卡洛。 然后，将D _i的解与D _{i-1进行比较} ，只保留能够成功解决前几天解的解决scheme而不违反约束条件。

您可能需要保留哪些解决scheme的历史logging（可能是有向图）。约束logging使您能够记住可能的添加 – 删除数量，并拒绝基于此的解决scheme。

还有许多其他步骤可以用来进一步改进您的解决scheme。 这里有一些想法：

• logging在前几天解决scheme中find的项目 – 价值组合的限制。 立即拒绝其他解决scheme（因为项目值不能改变）。您甚至可以使用特定于解决scheme的约束来为每个现有解决schemefind更小的解决scheme集，以便早日拒绝无效解决scheme。
• 每天生成一些“突变”的完整历史解决scheme，以便“修复”D ₁解决scheme集不包含用户解决scheme的情况。 您可以使用遗传algorithm来find基于现有解决scheme集的突变体群体。）
• 使用启发式方法可以很容易地find解决scheme（例如，当find有效的解决scheme时，试着通过将周围的数量replace来find该解决scheme的变体）。
• 使用行为启发式来预测一些用户行为（例如，每个项目的相同数量，极端模式等）
• 在用户input新的数量时继续进行一些计算。

鉴于所有这些，试着找出一个基于解决scheme和启发式发生的排名系统来确定候选解决scheme。

Answer 4

我写了一个程序来玩游戏。 当然，我必须让人类自动化，但是我相信我是这样做的，所以我不应该把我的方法与真正的人类对抗。

我从机器学习的angular度来看待这个问题，并把这个问题看作一个隐藏的马尔可夫模型，其总价就是观察值。 我的解决scheme是使用粒子滤波器。 这个解决scheme是使用NumPy和SciPy在Python 2.7中编写的。

我说明了在评论中明确提出的或隐含在代码中的任何假设。 为了让代码以自动化的方式运行，我还设置了一些额外的约束条件。 这并不是特别优化，因为我试图在侧面理解而不是速度上犯错。

每次迭代输出当前的真实数量和猜测。 我只是输出到一个文件，所以我可以很容易地审查。 一个有趣的扩展将是在2D（2果）或3D（3果）上绘制输出。 然后，您将能够看到解决scheme中的粒子滤波器。

更新：

编辑代码以包含调整后的更新参数。 包括使用matplotlib绘图调用（通过pylab）。 在Linux-Gnome上绘制工程，你的里程可能会有所不同。 默认NUM_FRUITS为2来绘制支持。 只是注释掉所有的pylab调用来删除绘图，并能够将NUM_FRUITS更改为任何内容。

估算由UnknownQuantities X Prices = TotalPrice表示的当前fxn是否做得好。 在二维（2果实）这是一个线，在三维（3果实）这将是一架飞机。 似乎是粒子滤波器的数据太less，无法正确地处理正确的数量。 在粒子滤波器上需要更多的智能来真正汇集历史信息。 您可以尝试将粒子滤波器转换为二阶或三阶。

更新2：

我一直在玩我的代码，很多。 我尝试了一堆东西，现在提出我将要制作的最终节目（开始烧掉这个想法）。

变化：

粒子现在使用浮点而不是整数。 不知道这是否有任何有意义的效果，但这是一个更一般的解决scheme。 舍入到整数仅在猜测时才完成。

绘图显示为绿色方块和当前猜测的真实数量为红色方块。 目前认为颗粒显示为蓝色点（根据我们相信它们的大小）。 这使得很容易看出algorithm运行得如何。 （绘图也testing和Win 7的64位工作）。

添加了closures/打开数量变化和价格变化的参数。 当然，“关”不是很有意思。

它做得很好，但是，正如已经指出的那样，这是一个非常棘手的问题，所以得到确切的答案是很难的。 closuresCHANGE_QUANTITIES会产生最简单的情况。 你可以通过closuresCHANGE_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() 

Answer 5

For your initial rules : From my school years, I would say that if we make abstraction of the 5% changes, we have everyday an equation with 3 unknown values (sorry I don't know the maths vocabulary in english), which are the same values as previous day. At day 3, you have 3 equations, 3 unknown values, the solution should be direct.

I guess the 5% change each day may be forgotten if the values of the 3 elements are different enough, because, as you said, we will use approximations and round the numbers.

For your adapted rules : Too many unknown – and changing – values in this case, so there is no direct solution I know of. I would trust Lior on this, his approach looks fine! (if you have a limited range for prices and quantities)