我写了一个玩游戏的程序。当然,我必须使人的一面自动化,但是我相信我做到了这一点,以至于当我与一个真实的人对战时,我的方法不会失效。
我从机器学习的角度解决了这个问题,并将该问题视为隐藏的马尔可夫模型,其中总价格为观察值。我的解决方案是使用粒子过滤器。该解决方案是使用NumPy和SciPy用Python 2.7编写的。
我在注释中明确提出或在代码中隐含做出的任何假设。为了使代码以自动化方式运行,我还设置了一些其他约束。它并不是特别优化,因为我尝试在侧面理解而不是在速度方面犯错误。
每次迭代输出当前的真实数量和猜测值。我只是将输出通过管道传输到文件中,这样我就可以轻松对其进行查看。一个有趣的扩展是将输出绘制在2D(对于2个水果)或3D(对于3个水果)图上。然后,您将可以看到解决方案中的粒子过滤器已磨合。
更新:
调整后,编辑了代码以包含更新的参数。包括使用matplotlib(通过pylab)进行的绘图调用。绘图可在Linux-Gnome上进行,您的工作量可能会有所不同。默认的NUM_FRUITS为2,以支持绘图。只需注释掉所有pylab调用即可删除绘图,并能够将NUM_FRUITS更改为任何内容。
很好地估计由UnknownQuantities X Price = TotalPrice表示的当前fxn。在2D(2个水果)中,这是一条线;在3D(3个水果)中,这是一条平面。似乎数据太少,以至于粒子过滤器无法可靠地调整正确的数量。在粒子过滤器的顶部还需要更多的技巧,以真正收集历史信息。您可以尝试将粒子过滤器转换为2阶或3阶。
更新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()
0
我正在学习编程(Python和算法),并试图从事一个我觉得很有趣的项目。我已经创建了一些基本的Python脚本,但是不确定如何为我尝试构建的游戏找到解决方案。
游戏的运作方式如下:
将为用户提供带有值的项目。例如,
然后,他们将有机会选择自己喜欢的任何组合(即100个苹果,20个梨和一个橙子)。计算机获得的唯一输出是总价值(在此示例中,当前价值为143美元)。计算机将尝试猜测它们所拥有的。显然,第一轮将无法正确获得。
下回合,用户可以修改其号码,但不能超过总数的5%(或我们可以选择的其他百分比。例如,我将使用5%)。水果的价格可以(随机)变化,因此总价值也可以基于此变化(为简单起见,在此示例中,我不更改水果的价格)。使用上面的示例,在游戏的第2天,用户在第3天返回了$ 152和$ 164的值。这是一个示例:
*(我希望表格能正确显示,我必须手动将它们隔开,所以希望它不仅可以在屏幕上显示,如果无法正常工作,请告诉我,我将尝试上传屏幕截图。)
我正在尝试查看是否可以确定一段时间后的数量(假设用户将有耐心继续输入数字)。我现在知道,我唯一的限制是总值不能超过5%,所以现在我的精度不能超过5%,因此用户将永远输入该值。
到目前为止我做了什么
到目前为止,这是我的解决方案(不多)。基本上,我采用所有值并找出它们的所有可能组合(本部分已完成)。然后,我将所有可能的组合作为字典放入数据库(例如,对于$ 143,可能会有一个字典条目{apple:143,Pears:0,Oranges:0} ..一直到{apple :0,Pears:1,Oranges:47}。每当我得到一个新号码时,我都会这样做,因此我会列出所有可能性。
这就是我卡住的地方。在使用上述规则时,如何找出最佳解决方案?我认为我需要一个适应度函数,该函数自动比较两天的数据并删除前几天数据有超过5%的差异的所有可能性。
问题:
因此,我的问题是用户更改了总数,并获得了所有概率的列表,我该如何处理呢?我需要学习什么?是否有适用的算法或可以使用的理论?或者,为了帮助我理解我的错误,您能否建议我可以添加哪些规则以使该目标变得可行(如果它尚未处于当前状态。我正在考虑添加更多水果并说他们必须选择至少3个,等等。) ?另外,我对遗传算法只有一个模糊的理解,但是我想如果可以使用的话我可以在这里使用它们?
我非常渴望学习,所以任何建议或技巧都将不胜感激(只是请不要告诉我这个游戏是不可能的)。
更新:获得很难解决的反馈。因此,我想我会在游戏中添加另一个条件,即不会干扰玩家的行为(游戏对他们而言保持不变),但是每天水果的价值都会改变价格(随机)。这样会更容易解决吗?因为在5%的移动范围内,并且某些水果值发生了变化,所以随着时间的流逝,只有少数几种组合可能出现。
第1天,一切皆有可能,并且达到足够近的范围几乎是不可能的,但是随着水果价格的变化和用户只能选择5%的变化,那么(随着时间的流逝)不应将范围缩小。在上面的示例中,如果价格波动足够大,我认为我可以蛮力提出一个可以让我猜出一个范围的解决方案,但我试图找出是否有更优雅的解决方案或其他解决方案来将范围缩小时间。
UPDATE2:在阅读并询问后,我相信这是一个隐含的马尔可夫/维特比问题,可以追踪水果价格以及总金额的变化(对最后一个数据点加权最重)。我不确定如何应用这种关系。我认为是这种情况,可能是错误的,但至少我开始怀疑这是某种类型的机器学习问题。
更新3:我创建了一个测试用例(具有较小的数字)和一个生成器,以帮助自动执行用户生成的数据,并且我试图从中创建一个图形以查看更可能的图形。
这是代码,以及总值和关于用户实际收获数量的注释。