Как подойти к алгоритму игры в угадывание чисел (с твистом)?

Эту проблему решить невозможно.

Предположим, что вы точно знаете, для какого соотношения было увеличено количество элементов, а не только какое максимальное отношение для этого.

У пользователя есть N фруктов, а у вас есть D дней угадывания.

В каждый день Вы получаете N новых переменных, а затем у вас есть в общей сложности d * n переменных.

За каждый день можно сгенерировать только два уравнения. Одно уравнение представляет собой сумму n_item * цены, а другое основано на известном соотношении. В общей сложности у вас есть самое большее 2 * уравнения D, если все они независимы.

2*D 2

Отказ от ответственности: я резко изменил свой ответ после того, как временно удалил свой ответ и внимательно перечитал вопрос, поскольку я неправильно истолковал некоторые критические части вопроса. Хотя я все еще ссылался на аналогичные темы и алгоритмы, ответ был значительно улучшен после того, как я попытался решить некоторые проблемы в C# самостоятельно.

Голливудская версия

• задача является динамической проблемой удовлетворения ограничений (DCSP), вариацией на ограничении проблемы удовлетворенности (CSP.)
• используйтеМонте-Карло , чтобы найти потенциальные решения для данного дня, если значения и количественные диапазоны не являются крошечными. В противном случае используйте грубую силу, чтобы найти все возможные решения.
• используйтеЗапись ограничений (относящуюся к 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 попыток найти 1000 потенциальных решений с учетом наших ограничений.
Это занимает много времени: от 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.)

[DCSPs] полезны, когда исходная формулировка a проблема каким-то образом изменяется, как правило, потому, что набор ограничения для рассмотрения эволюционируют из-за окружающей среды. DCSPs рассматриваются как последовательность статических CSP, каждая из которых представляет собой преобразование предыдущий, в котором переменные и ограничения могут быть добавлены (ограничение) или снято (расслабление).

Один метод, используемый с CSPs, который может быть полезен для этой проблемы, называется Запись Ограничений:

• С каждым изменением среды (пользователь вводит значения для D_i+1), найдите информацию о новом ограничении: каковы возможные "используемые" величины для ограничения add-remove.
• примените ограничение к каждому предшествующему дню в каскаде. Эффект пульсации может значительно уменьшить количество возможных решений.

Чтобы это сработало, вам нужно каждый день получать новый набор возможных решений; используйте либо грубую силу, либо Монте Карло. Затем сравните решения D _i С D _i-1 и сохраните только те решения, которые могут следовать решениям предыдущих дней, не нарушая ограничений.

Вам, вероятно, придется вести историю того, какие решения приводят к каким другим решениям (вероятно, в направленном графе.) Запись ограничений позволяет вам запоминать возможные добавления-удаления количеств и отклонять решения, основанные на этом.

Есть много других шагов, которые можно было бы предпринять, чтобы дальнейшее улучшение вашего решения. Вот некоторые идеи:

• запишите ограничения для комбинаций товар-стоимость, найденных в предыдущих решениях дней. Немедленно отклоните другие решения (так как значения элементов не должны изменяться.) Вы можете даже найти меньшие наборы решений для каждого существующего решения, используя ограничения для конкретных решений, чтобы отклонить недействительные решения ранее.
• генерировать некоторые "мутантные", полные истории, решения каждый день, чтобы "исправить" случай, когда D₁ набор решений не содержит решения пользователя. Вы можете использовать генетический алгоритм для поиска популяции мутантов на основе существующего набора решений.)
• используйте эвристику, чтобы легко находить решения (например, когда найдено допустимое решение, попробуйте найти вариации этого решения, подставляя величины вокруг.)
• используйте поведенческие эвристики, чтобы предсказать некоторые действия пользователя (например, одинаковое количество для каждого элемента, экстремальные паттерны и т. д.)
• продолжайте делать некоторые вычисления, пока пользователь вводит новые количества.

Учитывая все это, попробуйте построить систему ранжирования, основанную на возникновении решений и эвристике для определения решения-кандидата.

Я написал программу, чтобы играть в эту игру. Конечно, я должен был автоматизировать человеческую сторону, но я считаю, что сделал все это таким образом, что я не должен был аннулировать свой подход, когда играл против реального человека.

Я подошел к этому с точки зрения машинного обучения и рассматривал проблему как скрытую Марковскую модель, где общей ценой было наблюдение. Мое решение-использовать фильтр частиц. Это решение написано на Python 2.7 с использованием NumPy и SciPy.

Я высказал любое предположения, которые я сделал либо явно в комментариях, либо неявно в коде. Я также установил некоторые дополнительные ограничения, чтобы заставить код работать в автоматическом режиме. Он не особенно оптимизирован, так как я пытался ошибиться на стороне понятности, а не скорости.

Каждая итерация выводит текущие истинные величины и предположение. Я просто передаю выходные данные в файл, чтобы я мог легко просмотреть их. Интересным расширением было бы построить выходные данные на графике либо 2D (для 2 фрукта) или 3D (для 3 фруктов). Тогда вы сможете увидеть, как фильтр частиц оттачивает раствор.

Обновление:

Отредактировал код, чтобы включить обновленные параметры после настройки. Включено построение графиков вызовов с использованием matplotlib (через pylab). Построение графика работает на Linux-Gnome, ваш пробег может варьироваться. Значение по умолчанию NUM_FRUITS равно 2 для поддержки построения графика. Просто закомментируйте все вызовы pylab, чтобы удалить построение графика и иметь возможность изменить NUM_FRUITS на что угодно.

Делает хорошую работу оценка текущего fxn, представленного неизвестными количествами X цены = TotalPrice. В 2D (2 фрукта) это линия, в 3D (3 фрукта) это будет плоскость. По-видимому, слишком мало данных для фильтра частиц, чтобы надежно отточить правильные количества. Нужно немного больше смекалки поверх фильтра частиц, чтобы действительно собрать воедино историческую информацию. Вы можете попробовать преобразовать фильтр частиц во 2-й или 3-й порядок.

Обновление 2:

Я играю с моим код, очень много. Я перепробовал кучу вещей и теперь представляю окончательную программу, которую я буду делать (начиная выгорать на этой идее).

Изменения:

Теперь частицы используют плавающие точки, а не целые числа. Не уверен, что это имело какой-либо значимый эффект, но это более общее решение. Округление до целых чисел производится только в том случае, если вы делаете предположение.

Построение графиков показывает истинные величины в виде зеленого квадрата, а текущее предположение-в виде красного квадрата. В настоящее время считается, что частицы показаны в виде синих точек (определяется тем, насколько мы им верим). Это позволяет действительно легко увидеть, насколько хорошо работает алгоритм. (Построение графика также протестировано и работает на Win 7 64-бит).

Добавлены параметры для отключения / включения изменения количества и изменения цены. Конечно, и то и другое "выключено" неинтересно.

Он делает чертовски хорошую работу, но, как уже отмечалось, это действительно сложная проблема, поэтому получить точный ответ трудно. Отключение функции CHANGE_QUANTITIES приводит к простейшему случаю. Вы можете получить оценка сложности проблемы путем запуска с 2 плодами с CHANGE_QUANTITIES off. Посмотрите, как быстро он оттачивает правильный ответ, а затем посмотрите, насколько это сложнее, когда вы увеличиваете количество фруктов.

Вы также можете получить представление о трудностях, сохраняя 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()

Для ваших начальных правил:

Из моих школьных лет я бы сказал, что если мы сделаем абстракцию из 5% изменений, мы каждый день получаем уравнение с тремя неизвестными значениями (извините, я не знаю математического словаря на английском языке), которые являются теми же значениями, что и в предыдущий день. На 3-й день у вас есть три уравнения, три неизвестных значения, и решение должно быть прямым.

Я думаю, что изменение 5% каждый день может быть забыто, если значения трех элементов достаточно различны, потому что, как вы сказали, мы будем использовать приближения и округлять числа.

Для ваших адаптированных правил:

Слишком много неизвестных - и изменяющихся-значений в этом случае, так что прямого решения я не знаю. Я бы доверился Лиору в этом; его подход выглядит прекрасно! (Если у вас ограниченный диапазон цен и количеств.)