Jestem programowaniem (Python i algorytmy) i próbowałem pracować nad projektem, który uważam za interesujący. Stworzyłem kilka podstawowych skryptów Pythona, ale nie jestem pewien, jak podejść do rozwiązania do gry, staram się zbudować.

Oto jak działa gra:

Użytkownicy otrzymają przedmioty o wartości. Na przykład,

Apple = 1
Pears = 2
Oranges  = 3

Następnie pozbędą szansę wybrać dowolny kombinację ich lubią (tj. 100 jabłek, 20 gruszek i jedną pomarańczową). Jedynym wyjściem, który otrzymuje komputer jest całkowitą wartością (w tym przykładzie, obecnie 143 USD). Komputer spróbuje odgadnąć, co mają. Co oczywiście nie będzie w stanie poprawnie uzyskać pierwszej kolejności.

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

Następna obrót Użytkownik może modyfikować ich liczby, ale nie więcej niż 5% całkowitej ilości (lub niektóre inne procent, które mogliśmy wybrać. Wykorzystam 5% na przykład.). Ceny owoców mogą się zmienić (losowo), więc łączna wartość może się zmienić na podstawie tego (dla prostoty nie zmieniają się cen owoców w tym przykładzie). Korzystając z powyższego przykładu, w dniu 2 gry, użytkownik zwraca wartość 152 i 164 USD w dniu 3. Oto przykład:

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

* (Mam nadzieję, że stoły pojawią się w prawo, musiałem ręcznie przestrzenić ich, miejmy nadzieję, że nie tylko robi to na moim ekranie, jeśli nie działa, daj mi znać, a spróbuję wysłać zrzut ekranu).

Próbuję zobaczyć, czy mogę dowiedzieć się, jakie ilości są z czasem (zakładając, że użytkownik będzie miał cierpliwość wchodzić do numerów). Wiem, że teraz jedynym ograniczeniem jest całkowita wartość nie może być większa niż 5%, więc nie mogę być w ciągu 5% dokładności, więc użytkownik wejdzie na zawsze.

Co zrobiłem do tej pory

Oto moje rozwiązanie do tej pory (niewiele). Zasadniczo biorę wszystkie wartości i dowiem wszystkie możliwe kombinacje (skończyłem tę część). Następnie biorę wszystkie możliwe kombinacje i umieściłem je w bazie danych jako słownik (na przykład za 143 USD, może być wpis słownikowy {jabłko: 143, gruszki: 0, pomarańcze: 0} .. Cały sposób na {jabłko : 0, Gruszki: 1, Pomarańcze: 47}. Robię to za każdym razem, gdy otrzymuję nowy numer, więc mam listę wszystkich możliwości.

Tutaj utknęłam. W użyciu powyższych zasad, jak mogę zrozumieć najlepsze możliwe rozwiązanie? Myślę, że potrzebuję funkcji fitness, która automatycznie porównuje dane dwa dni i usuwa wszelkie możliwości, które mają ponad 5% wariancję danych poprzedniego dni.

Pytania:

Więc moje pytanie z użytkownikiem zmieniającym się całkowitą i mną listę wszystkich prawdopodobieństw, jak powinienem podejść? Co muszę się nauczyć? Czy są tam jakiekolwiek algorytmy lub teorie, których mogę użyć, ma zastosowanie? Albo, aby pomóc mi zrozumieć mój błąd, możesz sugerować, jakie zasady mogę dodać, aby ten cel był wykonalny (jeśli nie jest w swoim obecnym stanie. Myślałem, że dodałem więcej owoców i mówiąc, że muszą wybrać co najmniej 3 it.) ? Ponadto mam tylko niejasne zrozumienie algorytmów genetycznych, ale myślałem, że mogę ich użyć tutaj, jeśli jest coś, czego mogę użyć?

Bardzo chętnie się dowiem, więc każda rada lub wskazówki byłyby bardzo doceniane (po prostu nie mów mi, że ta gra jest niemożliwa).

Aktualizacja: Uzyskanie opinii, że trudno jest rozwiązać. Myślałem więc, że dodałem kolejny stan do gry, która nie przeszkadza w tym, co robi gracz (gra pozostaje taka sama dla nich), ale codzienna wartość owoce zmienia cenę (losowo). Czy ułatwiłoby to rozwiązanie? Ponieważ w ciągu 5% ruchu i pewnych zmian wartości owoców, tylko kilka kombinacji jest prawdopodobne w czasie.

Dzień 1, wszystko jest możliwe i uzyskanie wystarczającej ilości zasięgu jest prawie niemożliwe, ale ponieważ ceny zmian owoców i użytkownik może wybrać tylko 5% zmian, a następnie nie powinien (z czasem) zasięg był wąski i wąski. W powyższym przykładzie, jeżeli ceny są wystarczająco lotne, myślę, że mógłbym brutać wymusić rozwiązanie, które dało mi zalety, ale próbuję dowiedzieć się, czy istnieje bardziej eleganckie rozwiązania lub inne rozwiązania, aby zwężenie tego zakresu czas.

Aktualizacja2: Po przeczytaniu i pytaniu, wierzę, że jest to ukryty problem Markowa / Viterbi, który śledzi zmiany w cenach owocowych, a także całkowitą sumę (ważenie ostatnich punktów danych najcięższy). Nie jestem pewien, jak jednak zastosować związek. Myślę, że tak jest i może się mylić, ale przynajmniej zaczynam podejrzewać, że jest to jakiś rodzaj problemu uczenia maszynowego.

Aktualizacja 3: Utworzam sprawę testową (z mniejszymi numerami) i generator, który pomoże zautomatyzować dane wygenerowane przez użytkownika i próbuję utworzyć od niego wykres, aby zobaczyć, co jest bardziej prawdopodobne.

Oto kod, wraz z całkowitymi wartościami i komentarzami na temat tego, co użytkownicy faktycznie są owoce.

#!/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
62
Lostsoul 8 październik 2011, 09:20

4 odpowiedzi

Najlepsza odpowiedź

Łączymy teorię graficzną i prawdopodobieństwo:

W pierwszym dniu zbuduj zestaw wszystkich możliwych rozwiązań. Oznaczmy oznaczanie roztworów jako A1 = {A1 (1), A1 (2), ..., A1 (N)}.

Drugiego dnia możesz ponownie zbudować rozwiązania ustawione A2.

Teraz, dla każdego elementu w A2, musisz sprawdzić, czy można go osiągnąć z każdego elementu A1 (biorąc pod uwagę X% tolerancji). Jeśli tak - Podłącz A2 (N) do A1 (m). Jeśli nie można go osiągnąć z żadnego węzła w A1 (m) - możesz usunąć ten węzeł.

Zasadniczo budujemy podłączony skierowany wykres acykliczny.

Wszystkie ścieżki na wykresie są równie prawdopodobne. Można znaleźć dokładne rozwiązanie tylko wtedy, gdy występuje pojedyncza krawędź od AM do AM + 1 (z węzła w AM do węzła w AM + 1).

Jasne, niektóre węzły pojawiają się w więcej ścieżek niż inne węzły. Prawdopodobieństwo każdego węzła można bezpośrednio wyłączyć na podstawie liczby ścieżek zawierających ten węzeł.

Przypisując wagę do każdego węzła, który równa się liczbie ścieżek, które prowadzi do tego węzła, nie ma potrzeby utrzymania całej historii, ale tylko poprzedniego dnia.

Także spojrzeć na nie-negatywne- Wartości liniowe równania dipantynu - pytanie, zapytałem jakiś czas temu. Akceptowana odpowiedź jest świetnym sposobem na Enumarte wszystkich kombinacji w każdym kroku.

22
Community 23 maj 2017, 12:07

Ten problem jest niemożliwy do rozwiązania.

Powiedzmy, że wiesz dokładnie, jaki stosunek liczby przedmiotów został zwiększony, a nie tylko to, co jest maksymalny stosunek dla tego.

Użytkownik ma n owoce i masz dni odgadywania.

W każdym dniu otrzymujesz N Nowe Zmienne, a następnie masz w całkowitej D * N zmiennych.

Za każdym razem możesz generować tylko dwa równania. Jedno równanie to suma N_ITEM * Cena i innych opiera się na znanym stosunku. W sumie masz najwyżej 2 * d równań, jeśli są niezależne.

2 * d 2

8
Peter Mortensen 29 kwiecień 2018, 17:31

Napisałem program, aby grać w grę. Oczywiście musiałem zautomatyzować ludzką stronę, ale wierzę, że zrobiłem to wszystko w taki sposób, że nie powinienem unieważnić mojego podejścia, gdy grał z prawdziwym człowiekiem.

Podszedłem do tego z perspektywy uczenia maszynowego i traktowałem problem jako ukryty model Markowa, w którym obserwacja była obserwacją. Moim rozwiązaniem jest użycie filtra cząstek. To rozwiązanie jest napisane w Pythonie 2.7 przy użyciu numpy i Scipy.

Stwierdziłem, że wszystkie założenia wykonałem wyraźnie w komentarzach lub niejawnie w kodzie. Ustalam również dodatkowe ograniczenia dla doboru kodu do uruchomienia w automatycznej modzie. Nie jest szczególnie zoptymalizowany, ponieważ próbowałem błądzić po bokowej zrozumiałości, a nie szybkości.

Każda iteracja wynika bieżące prawdziwe ilości i domysł. Po prostu rurę wyjście do pliku, więc mogę go łatwo przejrzeć. Ciekawe rozszerzenie byłoby wykreślenie wyjścia na wykresie 2D (dla 2 owoców) lub 3D (dla 3 owoców). Wtedy byłbyś w stanie zobaczyć filtr cząstek na roztworze.

Aktualizacja:

Edytowano kod, który zawiera zaktualizowane parametry po ulepszeniu. Dołączono wywołania kreślarskie za pomocą MatplOTLIB (przez pylab). Knowanie działa na Linux-Gnome, twój przebieg może się różnić. Domyślnie num_fruits do 2 do wsparcia kreślenia. Po prostu skomentuj wszystkie połączenia pylab, aby usunąć kreśleć i być w stanie zmienić num_fruits do wszystkiego.

Czy dobra robota szacująca obecny fxn reprezentowany przez nieznane ceny x = totalsprice. W 2D (2 owoce) jest to linia, w 3D (3 owoce) byłaby samolotem. Wydaje się, że jest zbyt mało danych dla filtra cząstek, aby niezawodnie służyć na prawidłowych ilościach. Potrzebujesz trochę więcej smartów na górze filtra cząstek, aby naprawdę połączyć informacje historyczne. Możesz spróbować przekształcić filtr cząstek do 2 lub 3 rzędu.

Aktualizacja 2:

Bardzo grałem z moim kodem, dużo. Próbowałem kilka rzeczy, a teraz przedstawiam ostateczny program, który zrobię (zaczynam spalić na ten pomysł).

Zmiany:

Cząstki używają teraz pływających punktów niż liczb całkowitych. Nie jestem pewien, czy miał to jakiś znaczący wpływ, ale jest to bardziej ogólne rozwiązanie. Zaokrąglanie do liczb całkowitych jest wykonywane tylko przy zgadywania.

Pistolet pokazuje prawdziwe ilości jako zielony kwadrat i bieżące odgadnięcie jako plac czerwony. Obecnie uważa, że cząstki pokazane jako niebieskie kropki (wielkości, jak bardzo im wierzymy). To sprawia, że naprawdę łatwo jest zobaczyć, jak dobrze pracuje algorytm. (Pistolet również testowany i pracujący na wygranej 7 64-bit).

Dodano parametry do wyłączania / na zmianie ilości i zmiany cen. Oczywiście, zarówno "off" nie jest interesujący.

Wykonuje całkiem dobrą robotę, ale jak został zauważony, to naprawdę trudny problem, więc uzyskanie dokładnej odpowiedzi jest trudne. Wyłączenie zmiany_przedstawności wytwarza najprostszy przypadek. Można uzyskać uznanie dla trudności problemu, biegając z 2 owocami z RAND_QUANTITTS. Zobacz, jak szybko koncertuje na prawidłowej odpowiedzi, zobacz, jak trudniej jest, aby zwiększyć liczbę owoców.

Możesz również uzyskać perspektywę na poziomie trudności, utrzymując włączenie zmian zmiany_kwaterów, ale regulację max_quantity_change z bardzo małych wartości (0,001) do "dużych" wartości (0,05).

Jedna sytuacja, w której zmaga się, jeśli w wymiarze (jedna ilość owoców) zbliża się do zera. Ponieważ korzysta z średniej cząstek, aby odgadnąć, będzie on zawsze przekrzywa się od twardej granicy, takiej jak zero.

Ogólnie rzecz biorąc, robi to wielki samouczek filtra cząstek.


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()
4
Kyle 14 październik 2011, 22:57

dla początkowych reguł:

Z moich lat szkolnych powiedziałbym, że jeśli zrobimy abstrakcję zmian 5%, mamy codzienne równanie z trzema nieznanych wartości (przepraszam, że nie znam słownictwa matematyki w języku angielskim), które są te same wartości co poprzedni dzień. W dzień 3 masz trzy równania, trzy nieznane wartości, a rozwiązanie powinno być bezpośrednie.

Myślę, że każda zmiana 5% każdego dnia może zostać zapomniana, jeśli wartości trzech elementów są wystarczająco różne, ponieważ, jak powiedziałeś, użyjemy przybliżeń i zaokrąglenia liczb.

dla dostosowanych reguł:

Zbyt wiele nieznanych - i zmieniających się - wartości w tym przypadku, więc nie ma bezpośredniego rozwiązania, o którym znam. Ufałem to na to; Jego podejście wygląda dobrze! (Jeśli masz ograniczony zakres cen i ilości).

2
Peter Mortensen 29 kwiecień 2018, 17:33