Wie geht man mit einem Zahlen-Ratespiel (mit einem Twist) um?

Ich lerne Programmierung (Python und Algorithmen) und versuchte an einem Projekt zu arbeiten, das ich interessant finde. Ich habe ein paar grundlegende Python-Skripte erstellt, bin mir aber nicht sicher, wie ich eine Lösung für ein Spiel angehen soll, das ich erstellen möchte.

So funktioniert das Spiel:

Benutzer erhalten Artikel mit einem Wert. Beispielsweise,

Apple = 1 Pears = 2 Oranges = 3 

Sie erhalten dann die Möglichkeit, eine beliebige Kombination auszuwählen (z. B. 100 Äpfel, 20 Birnen und eine Orange). Die einzige Ausgabe, die der Computer erhält, ist der Gesamtwert (in diesem Beispiel sind es derzeit 143 $). Der Computer versucht zu erraten, was sie haben. Was offensichtlich nicht in der Lage sein wird, die erste Kurve richtig zu machen.

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

In der nächsten Runde kann der Benutzer seine Zahlen ändern, aber nicht mehr als 5% der Gesamtmenge (oder ein anderes Prozent, das wir wählen können. Ich werde zum Beispiel 5% verwenden.). Die Preise für Früchte können sich (zufällig) ändern, so dass sich auch der Gesamtwert ändern kann (in diesem Beispiel ändere ich aus Gründen der Einfachheit die Fruchtpreise nicht). Unter Verwendung des obigen Beispiels gibt der Benutzer an Tag 2 des Spiels an Tag 3 einen Wert von $ 152 und $ 164 zurück. Hier ist ein Beispiel:

 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 

* (Ich hoffe, dass die Tabellen richtig angezeigt werden, ich musste sie manuell platzieren, also hoffe ich, dass es nicht nur auf meinem Bildschirm geschieht, wenn es nicht funktioniert, lass es mich wissen und ich werde versuchen, einen Screenshot hochzuladen.)

Ich versuche zu sehen, ob ich herausfinden kann, wie sich die Mengen im Laufe der Zeit entwickeln (vorausgesetzt, der Benutzer wird die Geduld haben, weiter Zahlen einzugeben). Ich weiß jetzt, meine einzige Einschränkung ist, dass der Gesamtwert nicht mehr als 5% betragen kann, also kann ich nicht innerhalb von 5% Genauigkeit sein, so dass der Benutzer es für immer eingeben wird.

Was ich bisher gemacht habe

Hier ist meine Lösung bisher (nicht viel). Grundsätzlich nehme ich alle Werte und finde alle möglichen Kombinationen von ihnen (ich bin diesen Teil getan). Dann nehme ich alle möglichen Kombinationen und lege sie in einer database als Wörterbuch ab (zum Beispiel für $ 143, könnte es einen Wörterbucheintrag geben {Apfel: 143, Birnen: 0, Orangen: 0} .. bis hin zu {Apfel : 0, Birnen: 1, Orangen: 47} Ich mache das jedes Mal, wenn ich eine neue Nummer bekomme, also habe ich eine Liste aller Möglichkeiten.

Hier bin ich festgefahren. Wie kann ich anhand der obigen Regeln die bestmögliche Lösung finden? Ich denke, dass ich eine Fitnessfunktion benötige, die die zwei Tagesdaten automatisch vergleicht und alle Möglichkeiten entfernt, die mehr als 5% Abweichung von den Daten der vorhergehenden Tage haben.

Fragen:

Also meine Frage mit dem Benutzer die Summe ändern und ich habe eine Liste aller Wahrscheinlichkeiten, wie soll ich das angehen? Was muss ich lernen? Gibt es irgendwelche Algorithmen oder Theorien, die ich anwenden kann? Oder, um mir zu helfen, meinen Fehler zu verstehen, können Sie vorschlagen, welche Regeln ich hinzufügen kann, um dieses Ziel durchführbar zu machen (wenn es nicht in seinem aktuellen Zustand ist. Ich dachte mehr Früchte hinzufügen und sagen, sie müssen mindestens 3, etc ..) ? Außerdem habe ich nur ein vages Verständnis von genetischen Algorithmen, aber ich dachte, ich könnte sie hier benutzen, wenn ich etwas benutzen kann?

Ich bin sehr sehr begierig zu lernen, also würden irgendwelche Ratschläge oder Tipps sehr geschätzt werden (nur bitte sag mir nicht, dass dieses Spiel unmöglich ist).

UPDATE: Rückmeldung, dass dies schwer zu lösen ist. Also dachte ich, ich würde dem Spiel eine weitere Bedingung hinzufügen, die sich nicht auf das auswirkt, was der Spieler macht (das Spiel bleibt für sie gleich), aber jeden Tag ändert sich der Preis der Früchte (zufällig). Wäre das leichter zu lösen? Da bei einer Bewegung von 5% und bestimmten Fruchtwertänderungen nur wenige Kombinationen im Laufe der Zeit wahrscheinlich sind.

Tag 1, alles ist möglich und eine nahe genug Reichweite ist fast unmöglich, aber wie die Preise der Früchte ändern und der Benutzer kann nur eine 5% Änderung wählen, dann sollte (im Laufe der Zeit) die Palette eng und eng sein. In dem obigen Beispiel, wenn die Preise volatil genug sind, denke ich, dass ich eine Lösung brodeln könnte, die mir einen Spielraum zum Raten gab, aber ich versuche herauszufinden, ob es eine elegantere Lösung oder andere Lösungen gibt, um diesen Bereich weiter einzuschränken Zeit.

UPDATE2: Nach dem Lesen und Nachfragen glaube ich, dass dies ein verstecktes Markov / Viterbi-Problem ist, das die Veränderungen der Fruchtpreise sowie der Gesamtsumme verfolgt (wobei der letzte Datenpunkt am schwersten gewichtet wird). Ich bin mir nicht sicher, wie ich die Beziehung anwenden soll. Ich denke, dass dies der Fall ist und könnte falsch sein, aber zumindest beginne ich zu vermuten, dass dies eine Art von Lernproblem ist.

Update 3: Ich habe einen Testfall (mit kleineren Zahlen) und einen Generator erstellt, um die vom Benutzer generierten Daten zu automatisieren, und ich versuche ein Diagramm daraus zu erstellen, um zu sehen, was wahrscheinlicher ist.

Hier ist der Code, zusammen mit den Gesamtwerten und Kommentaren zu den tatsächlichen Fruchtmengen der Benutzer.

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

Wir kombinieren Graph-Theorie und Wahrscheinlichkeit:

Erstellen Sie am ersten Tag eine Reihe aller möglichen Lösungen. Lässt die Lösungen als A1 = {a1 (1), a1 (2), …, a1 (n)} bezeichnen.

Am zweiten Tag können Sie wieder den Lösungssatz A2 erstellen.

Nun müssen Sie für jedes Element in A2 prüfen, ob es von jedem Element von A1 (mit x% Toleranz) erreicht werden kann. Wenn ja – verbinden Sie A2 (n) mit A1 (m). Wenn es von keinem Knoten in A1 (m) aus erreicht werden kann, können Sie diesen Knoten löschen.

Im Grunde erstellen wir einen verbundenen gerichteten azyklischen Graphen.

Alle Pfade im Diagramm sind gleich wahrscheinlich. Sie können eine exakte Lösung nur finden, wenn es eine einzelne Kante von Am bis Am + 1 gibt (von einem Knoten in Am zu einem Knoten in Am + 1).

Sicher, einige Knoten erscheinen in mehr Pfaden als andere Knoten. Die Wahrscheinlichkeit für jeden Knoten kann direkt basierend auf der Anzahl der Pfade, die diesen Knoten enthalten, abgeleitet werden.

Indem jedem Knoten eine Gewichtung zugewiesen wird, die der Anzahl der Pfade entspricht, die zu diesem Knoten führen, muss nicht der gesamte Verlauf, sondern nur der vorherige Tag gespeichert werden.

Schauen Sie sich auch die linearen diphantischen Gleichungen mit nicht negativen Werten an – Eine Frage, die ich vor einiger Zeit gestellt habe. Die angenommene Antwort ist eine großartige Möglichkeit, alle Combos in jedem Schritt darzustellen.

Dieses Problem ist unmöglich zu lösen.

Nehmen wir an, Sie wissen genau, für welches Verhältnis die Anzahl der Artikel erhöht wurde, nicht nur, was das maximale Verhältnis dafür ist.

Ein Benutzer hat N Früchte und Sie haben D Tage des Ratens.

In jedem Tag erhalten Sie N neue Variablen und dann haben Sie insgesamt D * N Variablen.

Für jeden Tag können Sie nur zwei Gleichungen generieren. Eine Gleichung ist die Summe von n_item * Preis und andere basiert auf einem bekannten Verhältnis. Insgesamt haben Sie höchstens 2 * D-Gleichungen, wenn sie alle unabhängig sind.

2 * D 2

Disclaimer: Ich änderte meine Antwort dramatisch, nachdem ich meine Antwort vorübergehend gelöscht und die Frage erneut gelesen hatte, da ich einige kritische Teile der Frage falsch gelesen hatte. Während ich immer noch auf ähnliche Themen und Algorithmen Bezug nahm, wurde die Antwort stark verbessert, nachdem ich versucht hatte, einige der Probleme in C # selbst zu lösen.

Hollywood-Version

  • Das Problem ist ein Problem der dynamischen Constraint-Zufriedenheit (DCSP), eine Variation von Constraint-Zufriedenheitsproblemen (CSP).
  • Verwenden Sie Monte Carlo , um mögliche Lösungen für einen bestimmten Tag zu finden, wenn Werte und Mengenbereiche nicht klein sind. Andernfalls verwenden Sie rohe Gewalt, um alle möglichen Lösungen zu finden.
  • Verwenden Sie die Constraint-Aufzeichnung (bezogen auf DCSP), die in Kaskade auf die vorherigen Tage angewendet wurde, um die mögliche Lösungsmenge einzuschränken.
  • Überkreuze deine Finger, ziele und schieße auf die Wahrscheinlichkeit.
  • (Optional) Bruce Willis gewinnt.

Originalfassung

Zunächst möchte ich feststellen, dass ich hier zwei Hauptprobleme sehe:

  1. Die schiere Anzahl möglicher Lösungen. Wenn wir nur die Anzahl der Elemente und den Gesamtwert kennen, sagen wir beispielsweise 3 und 143, ergeben sich viele mögliche Lösungen. Außerdem ist es nicht einfach, einen Algorithmus zu verwenden, der eine gültige Lösung auswählt, ohne unausweichlich ungültige Lösungen auszuprobieren (insgesamt ungleich 143).

  2. Wenn mögliche Lösungen für einen gegebenen Tag D i gefunden werden , muss man einen Weg finden, potentielle Lösungen mit der zusätzlichen Information zu eliminieren, die durch {D i + 1 .. D i + n } gegeben ist.

Lassen Sie uns einige Grundlagen für die kommenden Beispiele aufstellen:

  • Lassen Sie die gleichen Werte, das ganze Spiel. Es kann entweder zufällig sein oder vom Benutzer gewählt werden.
  • Die möglichen Artikelwerte sind an den sehr begrenzten Bereich von [1-10] gebunden, wo keine zwei Artikel den gleichen Wert haben können.
  • Kein Artikel kann eine Menge größer als 100 haben. Das bedeutet: [0-100].

Um dies leichter zu lösen, habe ich mir die Freiheit genommen, eine Einschränkung zu ändern , wodurch der Algorithmus schneller konvergiert:

  • Die Regel “Gesamtmenge” wird durch diese Regel außer Kraft gesetzt: Sie können innerhalb eines Tages beliebig viele Artikel innerhalb des Bereichs [1-10] hinzufügen oder entfernen. Sie können jedoch nicht die gleiche Anzahl von Elementen hinzufügen oder entfernen, insgesamt mehr als zweimal. Dies gibt dem Spiel einen maximalen Lebenszyklus von 20 Tagen.

Mit dieser Regel können wir Lösungen leichter ausschließen. Und mit nicht winzigen Bereichen macht Backtracking-Algorithmen immer noch nutzlos, genau wie Ihr ursprüngliches Problem und Regeln.

Meiner bescheidenen Meinung nach ist diese Regel nicht die Essenz des Spiels, sondern nur ein Vermittler, der es dem Computer ermöglicht, das Problem zu lösen.

Problem 1: Finden von möglichen Lösungen

Zu Beginn kann Problem 1 mit einem Monte-Carlo-Algorithmus getriggers werden, um eine Reihe von möglichen Lösungen zu finden. Die Technik ist einfach: Generieren Sie Zufallszahlen für Artikelwerte und -mengen (innerhalb des jeweils akzeptierten Bereichs). Wiederholen Sie den Vorgang für die erforderliche Anzahl von Elementen. Überprüfen Sie, ob die Lösung akzeptabel ist. Das bedeutet, zu überprüfen, ob Elemente unterschiedliche Werte haben und die Summe gleich unserer Zielsumme ist (z. B. 143).

Während diese Technik den Vorteil hat, einfach zu implementieren, hat sie einige Nachteile:

  • Die Lösung des Benutzers wird nicht garantiert in unseren Ergebnissen angezeigt.
  • Es gibt viele “Misses”. Zum Beispiel braucht es mehr oder weniger 3.000.000 Versuche, 1.000 mögliche Lösungen zu finden, die unseren Beschränkungen entsprechen.
  • Es braucht viel Zeit: ungefähr 4 bis 5 Sekunden auf meinem faulen Laptop.

Wie umgehen Sie diese Nachteile? Gut…

  • Begrenzen Sie den Bereich auf kleinere Werte und
  • Suchen Sie nach einer angemessenen Anzahl möglicher Lösungen, sodass die Wahrscheinlichkeit besteht, dass die Lösung des Benutzers in Ihrem Lösungssatz angezeigt wird.
  • Verwenden Sie Heuristiken, um leichter Lösungen zu finden (mehr dazu später).

Beachten Sie, dass je mehr Sie die Bereiche einschränken, desto weniger nützlich ist der Monte-Carlo-Algorithmus, da es nur wenige gültige Lösungen gibt, um alle in angemessener Zeit zu iterieren. Für Constraints {3, [1-10], [0-100]} gibt es etwa 741.000.000 gültige Lösungen (nicht beschränkt auf einen Zielgesamtwert). Monte Carlo ist dort verwendbar. Für {3, [1-5], [0-10]} gibt es nur etwa 80.000. Keine Notwendigkeit, Monte Carlo zu verwenden; Brute for Loops wird gut funktionieren.

Ich glaube, das Problem 1 ist das, was man als Constraint-Zufriedenheitsproblem (oder CSP) bezeichnen würde.

Problem 2: Beschränken Sie die Menge der möglichen Lösungen

Angesichts der Tatsache, dass Problem 1 ein CSP ist, würde ich weitergehen und Problem 2 und das Problem im Allgemeinen ein Dynamic CSP (oder DCSP.)

[DCSPs] sind nützlich, wenn die ursprüngliche Formulierung eines Problems in irgendeiner Weise geändert wird, typischerweise weil sich die zu berücksichtigenden Einschränkungen aufgrund der Umgebung entwickeln. DCSPs werden als eine Abfolge von statischen CSPs angesehen, jede eine Transformation der vorherigen, in der Variablen und Beschränkungen hinzugefügt (Einschränkung) oder entfernt (Entspannung) werden können.

Eine Technik, die für CSPs verwendet wird, die für dieses Problem nützlich sein könnten, heißt Constraint Recording :

  • Mit jeder Änderung in der Umgebung (vom Benutzer eingegebene Werte für D i + 1 ) finden Sie Informationen über die neue Einschränkung: Was sind die möglicherweise “verwendeten” Größen für die Add-Remove-Einschränkung.
  • Übernehmen Sie die Einschränkung für jeden vorhergehenden Tag in Kaskade. Riffelungseffekte können mögliche Lösungen erheblich reduzieren.

Damit dies funktioniert, müssen Sie jeden Tag neue Lösungen erhalten. Verwenden Sie entweder Brute Force oder Monte Carlo. Vergleichen Sie dann die Lösungen von D i mit D i-1 und behalten Sie nur Lösungen bei, die zu den Lösungen früherer Tage erfolgreich sein können, ohne Einschränkungen zu verletzen.

Wahrscheinlich müssen Sie einen Überblick darüber behalten, welche Lösungen zu welchen anderen Lösungen führen (wahrscheinlich in einem gerichteten Graphen). Die Beschränkungsaufzeichnung ermöglicht es Ihnen, sich an mögliche Add-Remove-Mengen zu erinnern und darauf basierende Lösungen abzulehnen.

Es gibt viele andere Schritte, die unternommen werden könnten, um Ihre Lösung weiter zu verbessern. Hier sind ein paar Ideen:

  • Record Constraints für Element-Wert-Kombinationen, die in Lösungen von vorherigen Tagen gefunden wurden. Lehnen Sie andere Lösungen sofort ab (da sich die Werte der Elemente nicht ändern dürfen.) Sie können sogar kleinere Lösungssätze für jede vorhandene Lösung finden, indem Sie lösungsspezifische Einschränkungen verwenden, um ungültige Lösungen früher zurückzuweisen.
  • Generieren Sie jeden Tag einige “mutierte” Lösungen mit vollständiger Historie, um den Fall zu “reparieren”, in dem der Lösungssatz D 1 die Lösung des Benutzers nicht enthält. Sie könnten einen genetischen Algorithmus verwenden, um basierend auf einer vorhandenen Lösungsmenge eine Mutantenpopulation zu finden.)
  • Verwenden Sie Heuristiken, um einfach Lösungen zu finden (zB wenn eine gültige Lösung gefunden wird, versuchen Sie, Variationen dieser Lösung zu finden, indem Sie Mengen ersetzen).
  • Verwenden Sie Verhaltensheuristiken, um einige Benutzeraktionen vorherzusagen (z. B. gleiche Menge für jeden Gegenstand, extreme Muster usw.)
  • Führen Sie einige Berechnungen durch, während der Benutzer neue Mengen eingibt.

In Anbetracht all dessen sollten Sie versuchen, ein Ranking-System zu finden, das auf dem Auftreten von Lösungen und Heuristiken basiert, um eine Kandidatenlösung zu bestimmen.

Ich habe ein Programm geschrieben, um das Spiel zu spielen. Natürlich musste ich die menschliche Seite automatisieren, aber ich glaube, dass ich alles so gemacht habe, dass ich meine Herangehensweise nicht verfälschen sollte, wenn ich gegen einen echten Menschen gespielt werde.

Ich näherte mich aus einer Perspektive des maschinellen Lernens und behandelte das Problem als ein verstecktes Markov-Modell, bei dem der Gesamtpreis die Beobachtung war. Meine Lösung ist ein Partikelfilter zu verwenden. Diese Lösung wurde in Python 2.7 mit NumPy und SciPy geschrieben.

Ich habe irgendwelche Annahmen gemacht, die ich entweder explizit in den Kommentaren oder implizit im Code gemacht habe. Ich habe auch einige zusätzliche Einschränkungen festgelegt, damit Code automatisiert ausgeführt werden kann. Es ist nicht besonders optimiert, da ich versucht habe, eher die Seitenverständlichkeit als die Geschwindigkeit zu irren.

Jede Iteration gibt die aktuellen wahren Mengen und die Schätzung aus. Ich übertrage einfach die Ausgabe in eine Datei, damit ich sie leicht überprüfen kann. Eine interessante Erweiterung wäre, die Ausgabe in einem Diagramm entweder 2D (für 2 Früchte) oder 3D (für 3 Früchte) zu zeichnen. Dann könnten Sie den Partikelfilter in der Lösung sehen.

Aktualisieren:

Bearbeitete den Code, um aktualisierte Parameter nach dem Optimieren hinzuzufügen. Enthaltene Plotaufrufe mit matplotlib (via pylab). Plotten funktioniert auf Linux-Gnome, Ihre Laufleistung kann variieren. NUM_FRUITS wurde auf 2 gesetzt, um Unterstützung zu plotten. Kommentieren Sie einfach alle pylab-Aufrufe, um das Plotten zu entfernen und NUM_FRUITS zu ändern.

Ist ein guter Job, der das aktuelle fxn schätzt, das durch UnknownQantitates X Prices = TotalPrice dargestellt wird. In 2D (2 Früchte) ist dies eine Linie, in 3D (3 Früchte) wäre es ein Flugzeug. Scheint zu wenig Daten für den Partikelfilter zu sein, um zuverlässig die richtigen Mengen einlesen zu können. Brauchen Sie ein bisschen mehr Intelligenz auf dem Partikelfilter, um die historischen Informationen wirklich zusammen zu bringen. Sie könnten versuchen, den Partikelfilter in die 2. oder 3. Ordnung umzuwandeln.

Update 2:

Ich habe viel mit meinem Code herumgespielt. Ich habe eine Menge Dinge ausprobiert und stelle nun das endgültige Programm vor, das ich machen werde (diese Idee brennt aus).

Änderungen:

Die Partikel verwenden jetzt Gleitkommazahlen statt Ganzzahlen. Ich bin mir nicht sicher, ob dies einen sinnvollen Effekt hatte, aber es ist eine allgemeinere Lösung. Das Runden auf Ganzzahlen erfolgt nur beim Raten.

Das Plotten zeigt die wahren Mengen als grünes Quadrat und die aktuelle Schätzung als rotes Quadrat. Derzeit angenommene Partikel werden als blaue Punkte angezeigt (nach Größe sortiert, an die wir sie glauben). Dies macht es sehr einfach zu sehen, wie gut der Algorithmus funktioniert. (Plotten auch getestet und arbeitet an Win 7 64-Bit).

Parameter für das Ein- / Ausschalten von Mengenänderungen und Preisänderungen hinzugefügt. Natürlich sind beide “Aus” nicht interessant.

Es macht einen verdammt guten Job, aber wie bereits erwähnt, ist es ein wirklich schwieriges Problem, also ist es schwierig, die genaue Antwort zu bekommen. Das Ausschalten von CHANGE_QUANTITIES erzeugt den einfachsten Fall. Sie können die Schwierigkeit des Problems erkennen, indem Sie mit 2 Früchten mit CHANGE_QUANTITIES auslaufen. Sehen Sie, wie schnell es auf die richtige Antwort einschlägt, dann sehen Sie, wie viel schwerer es ist, wenn Sie die Anzahl der Früchte erhöhen.

Sie können auch eine Perspektive auf die Schwierigkeit erhalten, indem Sie CHANGE_QUANTITIES beibehalten, aber MAX_QUANTITY_CHANGE von sehr kleinen Werten (.001) auf “große” Werte (.05) anpassen.

Eine Situation, in der es kämpft, ist, wenn die Dimension (eine Fruchtmenge) nahe Null kommt. Weil es einen Durchschnitt von Partikeln verwendet, um zu raten, wird es immer von einer harten Grenze wie Null abweichen.

Im Allgemeinen macht dies ein großartiges Partikelfilter-Tutorial.


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

For your initial rules:

From my school years, I would say that if we make an abstraction of the 5% changes, we have everyday an equation with three 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 three equations, three unknown values, and the solution should be direct.

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

For your adapted rules:

Too many unknowns – 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.)