¿Cómo acercarse a un algoritmo de juego de adivinanzas de números (con un giro)?

Este problema es imposible de resolver.

Digamos que usted sabe exactamente para qué relación se aumentó el número de elementos, no solo cuál es la relación máxima para esto.

Un usuario tiene N frutas y usted tiene D días de adivinar.

En cada día obtienes N variables nuevas y luego tienes en total D*N variables.

Para cada día solo se pueden generar dos ecuaciones. Una ecuación es la suma de n_item * price y otra se basa en una relación conocida. En total tienes a lo sumo Ecuaciones 2 * D si todas son independientes.

2 * D 2

Descargo de responsabilidad: Cambié mi respuesta dramáticamente después de borrar temporalmente mi respuesta y volver a leer la pregunta cuidadosamente ya que malinterpreté algunas partes críticas de la pregunta. Si bien todavía se hace referencia a temas y algoritmos similares, la respuesta se mejoró mucho después de que intenté resolver algunos de los problemas en C# yo mismo.

Versión de Hollywood

• El problema es un Dynamic constraint satisfaction problem (DCSP), una variación de Constraint problemas de satisfacción (CSP.)
• Use Monte Carlo para encontrar soluciones potenciales para un día dado si los valores y los rangos de cantidad no son pequeños. De lo contrario, usa la fuerza bruta para encontrar todas las posibles soluciones.
• Use Registro de restricciones (relacionado con DCSP), aplicado en cascada a días anteriores para restringir el conjunto de soluciones potenciales.
• Cruza los dedos, apunta ydispara (Adivina), basado en la probabilidad.
• (Opcional) Bruce Willis ganar.

Versión original

En primer lugar, me gustaría exponer lo que veo dos problemas principales aquí:

1. El gran número de posibles soluciones. Sabiendo solo el número de elementos y el valor total, digamos 3 y 143 por ejemplo, dará un montón de posibles soluciones. Además, no es fácil tener un algoritmo que elija una solución válida sin probar inevitablemente soluciones inválidas (el total no es igual a 143.)

2. Cuando las soluciones posibles son encontrado para un día dado D _i , uno debe encontrar una manera de eliminar soluciones potenciales con la información añadida dada por { D _i+1 .. D_i+n }.

Vamos a sentar algunas bases para los próximos ejemplos:

• Mantengamos los mismos valores de objetos durante todo el juego. Puede ser aleatorio o elegido por el usuario.
• Los posibles valores de los elementos están vinculados al rango muy limitado de [1-10], donde no hay dos elementos que puedan tener el mismo valor.
• No el artículo puede tener una cantidad mayor que 100. Que significa: [0-100].

Para resolver esto más fácilmente me tomé la libertad de cambiar una restricción, que hace que el algoritmo converja más rápido:

• La regla de "cantidad total" es anulada por esta regla: Puede agregar o eliminar cualquier número de artículos dentro del rango [1-10], total, en un día. Sin embargo, no puede agregar o eliminar el mismo número de elementos, total, más de dos veces. Esto también le da al juego un máximo ciclo de vida de 20 días.

Esta regla nos permite descartar soluciones más fácilmente. Y, con rangos no pequeños, hace que los algoritmos de retroceso sigan siendo inútiles, al igual que su problema y reglas originales.

En mi humilde opinión, esta regla no es la esencia del juego, sino solo un facilitador, que permite al ordenador resolver el problema.

Problema 1: Encontrar soluciones potenciales

Para empezar, problema 1. se puede resolver usando un Algoritmo de Monte Carlo para encontrar un conjunto de soluciones potenciales. La técnica es simple: Generar números aleatorios para los valores y cantidades de los artículos (dentro de su respectivo rango aceptado). Repita el proceso para el número requerido de elementos. Verifique si la solución es aceptable o no. Eso significa verificar si los elementos tienen valores distintos y el total es igual a nuestro total objetivo (digamos, 143.)

Si bien esta técnica tiene la ventaja de ser fácil de implementar, tiene algunos inconvenientes:

• No se garantiza que la solución del usuario aparezca en nuestros resultados.
• Hay un montón de "misses". Por ejemplo, se necesitan más o menos 3,000,000 intentos para encontrar 1,000 soluciones potenciales dadas nuestras limitaciones.
• Toma mucho tiempo: alrededor de 4 a 5 segundos en mi computadora portátil perezosa.

¿Cómo evitar estos inconvenientes? Bien...

• Limite el rango a valores más pequeños y
• Encontrar un número adecuado de soluciones potenciales para que no es una buena probabilidad de que la solución del usuario aparezca en su conjunto de soluciones.
• Use la heurística para encontrar soluciones más fácilmente (más sobre eso más adelante.)

Tenga en cuenta que cuanto más restrinja los rangos, menos útil será el algoritmo de Monte Carlo, ya que habrá pocas soluciones válidas suficientes para iterar sobre todas ellas en un tiempo razonable. Para limitaciones { 3, [1-10], [0-100] } hay alrededor de 741,000,000 soluciones válidas (no limitadas a un valor total objetivo.) Monte Carlo es utilizable allí. Para { 3, [1-5], [0-10] }, solo hay alrededor de 80.000. No es necesario usar Monte Carlo; los bucles de fuerza bruta for funcionarán bien.

Creo que el problema 1es lo que se llamaría un Problema de satisfacción con restricciones (o CSP.)

Problema 2: Restringir el conjunto de soluciones potenciales

Dado el hecho de que problema 1 es un CSP, me gustaría seguir adelante y llamar problema 2, y el problema en general, un CSP dinámico (o DCSP.)

[DCSPs] son útiles cuando la formulación original de un problema se altera de alguna manera, por lo general porque el conjunto de las limitaciones a considerar evolucionan debido al medio ambiente. DCSPs se ven como una secuencia de CSP estáticos, cada uno una transformación de el anterior en el que se pueden agregar variables y restricciones (restricción) o eliminado (relajación).

Una técnica utilizada con CSP que podría ser útil para este problema se llama Grabación de restricciones :

• Con cada cambio en el entorno (los valores ingresados por el usuario para D _i+1), encuentre información sobre la nueva restricción: Cuáles son las cantidades posiblemente "usadas" para la restricción add-remove.
• Aplique la restricción a cada día anterior en cascada. Los efectos ondulantes podrían reducir significativamente las posibles soluciones.

Para que esto funcione, necesita obtener un nuevo conjunto de posibles soluciones todos los días; Use fuerza bruta o Monte Carlo. Luego, compare las soluciones de D_i a D_i-1 y mantenga solo las soluciones que pueden tener éxito a las soluciones de días anteriores sin violar las restricciones.

Probablemente tendrá que mantener un historial de qué soluciones conducen a qué otras soluciones (probablemente en un gráfico dirigido.) El registro de restricciones le permite recordar posibles cantidades de adición y eliminación y rechaza soluciones basadas en eso.

Hay muchos otros pasos que podrían tomarse para mejore aún más su solución. He aquí algunas ideas:

• Restricciones de registro para combinaciones elemento-valor encontradas en soluciones de días anteriores. Rechace otras soluciones inmediatamente (ya que los valores de los elementos no deben cambiar.) Incluso podría encontrar conjuntos de soluciones más pequeños para cada solución existente utilizando restricciones específicas de la solución para rechazar soluciones no válidas antes.
• Generar algunas soluciones "mutantes", historia completa, cada día con el fin de "reparar" el caso donde el D₁ set de soluciones no contiene la solución del usuario. Podría usar un algoritmo genético para encontrar una población mutante basada en un conjunto de soluciones existente.)
• Use heurística para encontrar soluciones fácilmente (por ejemplo, cuando se encuentra una solución válida, intente encontrar variaciones de esta solución sustituyendo cantidades alrededor.)
• Use heurística de comportamiento para predecir algunas acciones del usuario (por ejemplo, la misma cantidad para cada elemento, patrones extremos, etc.)
• Seguir haciendo algunos cálculos mientras el usuario está introduciendo nuevas cantidades.

Dado todo esto, tratar de averiguar un sistema de clasificación basado en la ocurrencia de soluciones y heurística para determinar una solución candidata.

Escribí un programa para jugar el juego. Por supuesto, tuve que automatizar el lado humano, pero creo que lo hice todo de tal manera que no debería invalidar mi enfoque cuando se juega contra un humano real.

Abordé esto desde una perspectiva de aprendizaje automático y traté el problema como un modelo de markov oculto donde el precio total era la observación. Mi solución es usar un filtro de partículas. Esta solución está escrita en Python 2.7 usando NumPy y SciPy.

Declaré cualquier suposiciones que hice explícitamente en los comentarios o implícitamente en el código. También establecí algunas restricciones adicionales para que el código se ejecute de manera automatizada. No está particularmente optimizado, ya que traté de errar en la comprensibilidad lateral en lugar de la velocidad.

Cada iteración produce las cantidades reales actuales y la conjetura. Solo canalizo la salida a un archivo para poder revisarla fácilmente. Una extensión interesante sería trazar la salida en un gráfico ya sea 2D (para 2 frutas) o 3D (para 3 frutas). Entonces usted sería capaz de ver el filtro de partículas afilar en la solución.

Actualización:

Editó el código para incluir parámetros actualizados después de retocar. Incluye el trazado de llamadas usando matplotlib (vía pylab). El trazado funciona en Linux-Gnome, su kilometraje puede variar. Por defecto NUM_FRUITS a 2 para soporte de trazado. Solo comente todas las llamadas de pylab para eliminar el trazado y ser capaz de cambiar NUM_FRUITS a cualquier cosa.

Hace un buen trabajo estimando el fxn actual representado por cantidades desconocidas X Precios = Precio total. En 2D (2 Frutas) esta es una línea, en 3D (3 Frutas) sería un plano. Parece que hay muy pocos datos para que el filtro de partículas pueda afinar de forma fiable en las cantidades correctas. Necesita un poco más de inteligencia en la parte superior del filtro de partículas para reunir realmente la información histórica. Usted podría intentar convertir el filtro de partículas a 2do-o 3rd-orden.

Actualización 2:

He estado jugando con mi código, mucho. He intentado un montón de cosas y ahora presentar el programa final que voy a hacer (empezando a quemar en esta idea).

Cambios:

Las partículas ahora usan puntos flotantes en lugar de enteros. No estoy seguro de si esto tuvo algún efecto significativo, pero es una solución más general. El redondeo a enteros se hace solo cuando se hace una conjetura.

El trazado muestra las cantidades verdaderas como un cuadrado verde y la conjetura actual como un cuadrado rojo. Actualmente se cree que las partículas se muestran como puntos azules (dimensionado por cuánto les creemos). Esto hace que sea muy fácil ver qué tan bien está funcionando el algoritmo. (Trazado también probado y trabajando en Win 7 de 64 bits).

Se agregaron parámetros para desactivar/activar el cambio de cantidad y el cambio de precio. Por supuesto, tanto ' off ' no es interesante.

Hace un trabajo bastante bueno, pero, como se ha señalado, es un problema realmente difícil, por lo que obtener la respuesta exacta es difícil. Desactivar CHANGE_QUANTITIES produce el caso más simple. Usted puede conseguir un apreciación por la dificultad del problema corriendo con 2 frutas con CHANGE_QUANTITIES apagado. Vea lo rápido que se afina en la respuesta correcta y luego vea lo difícil que es a medida que aumenta el número de frutas.

También puede obtener una perspectiva de la dificultad manteniendo CHANGE_QUANTITIES activado, pero ajustando el MAX_QUANTITY_CHANGE a partir de valores muy pequeños (.001) a valores" grandes" (.05).

Una situación en la que lucha es si on dimension (una cantidad de fruta) se acerca a cero. Porque está usando un promedio de partículas para adivinar que siempre se desviará de un límite duro como cero.

En general esto hace un gran tutorial de filtro de partículas.

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()

Para sus reglas iniciales:

De mis años escolares, diría que si hacemos una abstracción de los cambios del 5%, tenemos todos los días una ecuación con tres valores desconocidos (lo siento, no conozco el vocabulario de matemáticas en inglés), que son los mismos valores que el día anterior. En el día 3, tienes tres ecuaciones, tres valores desconocidos, y la solución debe ser directa.

Supongo que el cambio del 5% cada día puede olvidarse si los valores de los tres elementos son lo suficientemente diferentes, porque, como dijiste, usaremos aproximaciones y redondearemos los números.

Para sus reglas adaptadas:

Demasiadas incógnitas - y valores cambiantes - en este caso, por lo que no hay una solución directa que yo sepa. Yo confiaría en Lior en esto; su enfoque se ve bien! (Si tiene un rango limitado de precios y cantidades.)