How to approach the number guessing algorithm (using twisting)?

Question

I study programming (python and algos) and tried to work on a project that interests me. I have created some basic python scripts, but I'm not sure how to approach the solution of the game I'm trying to create.

Here's how the game will work:

Users will be provided with items with a value. for example

Apple = 1 Pears = 2 Oranges = 3 

Then they will be able to choose any combination of them that they like (for example, 100 apples, 20 pears and 1 orange). The only result that the computer gets is the total value (in this example, $ 143). The computer will try to guess what they have. Obviously, he will not be able to correctly understand the first turn.

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

The next time the user can change their numbers, but not more than 5% of the total (or some other percent that we can choose. For example, I use 5%). Fruit prices can change (randomly), so the total cost can change based on this (for simplicity, I do not change the price of fruits in this example). Using the above example, on the second day of the game, the user returns $ 152 and $ 164 on day 3. Here is an example.

 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 

* (I hope that the tables appear correctly, I had to manually place them, so I hope that this does not just do this on my screen, if this does not help, let me know and I will try to upload a screenshot).

I'm trying to figure out if I can determine what the number is over time (assuming the user has the patience to keep typing in numbers). I know that now my only limitation is that the total amount cannot exceed 5%, so I cannot be within 5% accuracy right now, so that the user logs into it forever.

What have i done so far

Here is my solution so far (not so much). Basically I take all the values ​​and figure out all the possible combos from them (I do this part). Then I take all possible combos and put them into the database in the form of a dictionary (for example, for $ 143, maybe an entry in the dictionary {apple: 143, Pears: 0, Orange: 0}) up to {apple: 0, Pears: 1 , Orange: 47} I do this every time I get a new number, so I have a list of all the features.

That's where I am stuck. Is using the rules above how can I find the best solution? I think I need a fitness function that automatically compares data for two days and removes any features that have more than 5% variance of data from previous days.

Questions:

So, my question is, when the user changes the total number, and I have a list of all the probabilities, how can I approach this? What do i need to know? Are there any algorithms or theories that I can use that are applicable? Or, to help me understand my mistake, can you suggest what rules I can add to make this goal feasible (if it is not in its current state. I thought to add more fruits and say that they should choose at least 3 and etc.).? Also, I only have a vague understanding of genetic algorithms, but I thought I could use them here if there is something that I can use?

I really want to learn, so any advice or advice will be very grateful (just please do not tell me that this game is impossible).

Thanks in advance.

UPDATE: getting feedback that is hard to solve. Therefore, I thought that I would add another condition to the game, which will not interfere with what the player does (the game remains the same for them), but every day the value of fruits changes the price (randomly). Would this help? Because within 5% of the movement and some changes in the value of the fruit, only a few combos are likely over time. Day 1, everything is possible, and getting a fairly close range is almost impossible, but since fruit prices are changing, and the user can only choose a 5% change, then the range should not be (over time) narrow and narrow. In the above example, if the prices are volatile enough, I think I could put brute force on a solution that gave me an opportunity to guess, but I'm trying to find out if there is a more elegant solution or other solutions to narrow this range of time.

UPDATE2: after reading and polling, I believe that this is a hidden markov / Viterbi problem that tracks changes in fruit prices, as well as the total amount (weighing the latest data, the most difficult). I am not sure how to apply the relationship. I think this may be wrong, but at least I'm starting to suspect that this is some kind of machine learning problem.

Update3: I created a test case (with smaller numbers) and a generator to help automate user-generated data, and I'm trying to create a graph from it to find out which is more likely. Here is the code along with full values ​​and comments on what the actual quantities of users' fruits are.

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

Combine graph theory and probability:

On the first day, create a set of all possible solutions. We denote the solutions given as A1 = {a1 (1), a1 (2), ..., a1 (n)}.

On the second day, you can again create solution set A2.

Now, for each element in A2, you will need to check whether it can be reached from each element of A1 (taking into account the tolerance x%). If so, connect A2 (n) with A1 (m). If it is impossible to reach it from any node in A1 (m) - you can delete this node.

Basically we build a connected directed acyclic graph.

All paths in the graph are equally likely. The exact solution can be found only when there is one edge from Am to Am + 1 (from node in Am to a node in Am + 1).

Of course, some nodes appear in more paths than other nodes. The probability for each node can be directly derived based on the number of paths containing this node.

Assigning weight to each node, which is equal to the number of paths that lead to this node, there is no need to store the entire history, but only on the previous day.

Also, take a look at the linear equations of diphantines with a negative value - a question I asked a while ago. The accepted answer is a great way to list all combos at every step.

Answer 2

This problem cannot be solved. Lets say that you know exactly how many elements have been increased, and not just what the maximum ratio is for this.

The user has N fruits, and you have D days of guessing.

Every day you get N new variables, and then you have the sum of the variables D * N.

You can only generate 2 equations per day. One equation is the sum of the price n_item *, and the other is based on the ratio. In general, you have no more than 2 * D equations, if they are all independent.

2 * D <N * D for all N> 2

Answer 3

Disclaimer: I greatly changed my answer after temporarily deleting my answer and carefully re-reading the question, as I misunderstood some important questions. While still referring to similar topics and algorithms, the answer was greatly improved after I tried to solve part of the problem in C # myself.

Hollywood version

• The problem is the Dynamic Constraint Satisfaction Problem (DCSP), a variant of Constraint Constraint Issues (CSP.)
• Use Monte Carlo to find potential solutions for a given day if the values ​​and ranges of values ​​are not tiny. Otherwise, use brute force to find all possible solutions.
• Use the Constraint Recording (DCSP-related) binding used in the cascade until the previous days to limit the possible set of solutions.
• Cross your fingers, aim and shoot (Guess) based on probability.
• (Optional) Bruce Willis wins.

Original version

First, I would like to point out that I see two main problems here:

• A huge number of possible solutions. Knowing only the number of objects and the general value, say, 3 and 143, for example, will give many possible solutions. In addition, it is not easy to ensure that the algorithm collects the correct solution without the inevitable use of invalid solutions (total number not equal to 143.)

• When possible solutions are found for a given day D _i , you need to find a way to eliminate potential solutions with the added information given by {D _{i + 1} .. D _{i + n} }.

We will lay some foundations for the following examples:

• Allows you to keep the same values ​​of the elements, the whole game. It can be random or selected by the user.
• Possible values ​​of elements are tied to a very limited range [1-10], where none of the two elements can have the same value.
• No element can have a value greater than 100. This means: [0-100].

To solve this problem easier , I took the liberty of changing one restriction , which speeds up the algorithm:

• The "total" rule is overridden by this rule: you can add or remove any number of elements within the range [1-10], in just one day. However, you cannot add or remove the same number of elements, more than two times in total. It also gives the game a maximum life cycle of 20 days.

This rule allows us to more easily rule out decisions. And with small ranges, rendering makes backtracking algorithms useless, just like your original problems and rules.

In my humble opinion, this rule is not the essence of the game, but only a facilitator that allows the computer to solve the problem.

Task 1: Search for Potential Solutions

To begin with, problem 1. can be solved using the Monte Carlo algorithm to find a set of potential solutions. The method is simple: generate random numbers for position values ​​and values ​​(within their respective range). Repeat the process for the required number of elements. Check if the solution is acceptable. This means that if the elements have different meanings, and the total amount is equal to our common goal (say, 143.)

Although this method has the advantage of being easy to implement, it has some disadvantages:

• Custom solutions are not guaranteed in our results.
• There are many “misses”. For example, more or less than 3,000,000 attempts are required to find 1,000 potential solutions, subject to our limitations.
• It takes a long time: 4 to 5 seconds on a lazy laptop.

How to get around these shortcomings? Well...

• Limit the range to smaller values ​​and
• Find enough potential solutions, so there is a good chance that a custom solution will appear in your solution set.
• Use heuristics to find solutions more easily (more on this later).

Please note that the more you limit the ranges, the less useful it is to use the Monte Carlo algorithm, as there will be enough correct solutions to repeat them all in a reasonable amount of time. For constraints {3, [1-10], [0-100]} there are about 741 million valid solutions (not limited by the target total value.) Monte Carlo can be used there. For {3, [1-5], [0-10]} only about 80,000. No need to use Monte Carlo; the brute force of for will do everything perfectly.

I believe that problem 1 is what you would call the constraint restriction problem (or CSP.)

Task 2: Limit the range of potential solutions

Given the fact that problem 1 is CSP, I would go and cause problem 2, and the problem in general, Dynamic CSP (or DCSP.)

[DCSP] are useful when the original wording of a problem changes in some way, usually because a set of constraints that need to be taken into account develop because of the environment. DCSPs are considered as a sequence of static CSPs, each of which represents a previous transformation, in which variables and constraints (restriction) or deletion (relaxation) can be added.

One method used with CSP that may be useful for this problem is called Constraint Recording:

• Each time you change the environment (the user enters values ​​for D _{i + 1} ), find information about the new restriction: what possible values ​​are used to limit the add-delete.
• Apply a limit on every previous day in the cascade. Shaking effects can significantly reduce possible solutions.

To do this, you need to receive a new set of possible solutions every day; Use either brute force or Monte Carlo. Then compare the solutions of D _i with D _i-1 and save only the solutions that can succeed in the decisions of the previous days without violating the restrictions.

You will probably have to keep a history of which decisions lead to some other decisions (possibly in a directed schedule). Recording constraints allows you to remember possible add-delete values ​​and reject decisions based on this.

There are many other steps you can take to further improve your decision. Here are some ideas:

• Record restrictions for combinations of elements and values ​​found in previous versions of solutions. Reject other solutions immediately (because element values ​​should not change.) You can even find smaller sets of solutions for each existing solution, using solution-specific constraints to reject previously invalid solutions.
• Generate some “mutant”, full-blown solutions every day in order to “restore” the case when the solution set D ₁ does not contain a custom solution. You can use the genetic algorithm to search for a mutant population based on an existing set of solutions.)
• Use heuristics to easily find solutions (for example, when a valid solution is found, try to find options for this solution by replacing the values ​​around.)
• Use behavioral heuristics to predict certain user actions (for example, the same amount for each element, extreme patterns, etc.).
• Continue to do some calculations as the user enters new quantities.

Given all this, try to figure out a ranking system based on the appearance of solutions and heuristics to determine the candidate’s decision.

Answer 4

I wrote a program for the game. Of course, I had to automate the human side, but I believe that I did all this in such a way that I did not violate my approach when I played against a real person.

I approached this from the point of view of machine learning and saw the problem as a hidden Markov model, where the total price was an observation. My solution is to use a particle filter. This solution is written in Python 2.7 using NumPy and SciPy.

I outlined any assumptions made explicitly in the comments or implicitly in the code. I also set some additional restrictions in order to run the code in automatic mode. This was not particularly optimized, as I tried to err on the side of understanding, not speed.

Each iteration displays the current true values ​​and fortune telling. I just pass the output to a file so that I can easily view it. An interesting continuation will be the construction of the output on the chart either 2D (for 2 fruits) or 3D (for 3 fruits). Then you can see how the particle filter is honed in the solution.

Update:

Edited the code to include updated settings after configuration. Calls using matplotlib (via pylab) are included. Planning runs on Linux-Gnome; your mileage may vary. By default, NUM_FRUITS is 2 for building support. Just comment out all pylab calls to delete the schedule and you can change NUM_FRUITS to something.

Is it good at evaluating the current fxn represented by UnknownQuantities X Prices = TotalPrice. In 2D (2 Fruits) this is a line, in 3D (3 Fruits) it would be a plane. There seems to be too little data for a particle filter to reliably hone the right amounts. You need a few more emoticons on top of the particle filter to really collect historical information. 2- 3- .

2:

. , ( ).

Changes:

, . , - , . .

, - . , ( , ). , . (Plotting 64- Win 7).

/ . , "" .

, , , , . CHANGE_QUANTITIES . , 2 CHANGE_QUANTITIES. , , , , .

, 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 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

: , 5%, (, -), , , 3- 3 , 3 , .

I think that a 5% change every day can be forgotten if the values ​​of the three elements are quite different, because, as you said, we will use approximations and round numbers.

For your adapted rules: Too many unknown and changing values ​​in this case, so there is no direct solution that I know of. I would believe Lior in this, his approach looks great! (if you have a limited price and quantity range)