更新(2020年7月):質問は9年前ですが、それでも私は深く興味を持っています。それ以来、機械学習(RNN、CNN、GANSなど)、新しいアプローチ、新しいアプローチを可能にする安価なGPUが登場しました。 。この質問をもう一度見て、新しいアプローチがあるかどうかを確認するのは楽しいだろうと思いました。
私はプログラミング(Pythonとアルゴリズム)を学んでいて、面白いと思うプロジェクトに取り組んでいました。いくつかの基本的なPythonスクリプトを作成しましたが、作成しようとしているゲームのソリューションにアプローチする方法がわかりません。
ゲームの仕組みは次のとおりです。
ユーザーには価値のあるアイテムが与えられます。例えば、
Apple = 1
Pears = 2
Oranges = 3
その後、好きな組み合わせ(つまり、リンゴ100個、梨20個、オレンジ1個)を選択する機会が与えられます。コンピューターが取得する唯一の出力は合計値です(この例では、現在$ 143です)。コンピュータは彼らが何を持っているかを推測しようとします。明らかに、最初のターンを正しく取得することはできません。
Value quantity(day1) value(day1)
Apple 1 100 100
Pears 2 20 40
Orange 3 1 3
Total 121 143
次のターン、ユーザーは自分の数を変更できますが、合計数量の5%以下(または他のパーセントを選択できます。たとえば、5%を使用します)。果物の価格は(ランダムに)変化する可能性があるため、それに基づいて合計値も変化する可能性があります(簡単にするために、この例では果物の価格を変更していません)。上記の例を使用すると、ゲームの2日目に、ユーザーは3日目に$152と$164の値を返します。例を次に示します。
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
*(テーブルが正しく表示されることを願っています。手動でスペースを空ける必要があったので、画面上でそれを行っているだけではないことを願っています。うまくいかない場合は、お知らせください。スクリーンショットをアップロードしてみます。)
私は、時間の経過とともに数量が何であるかを把握できるかどうかを確認しようとしています(ユーザーが数字を入力し続ける忍耐力があると仮定します)。現在のところ、私の唯一の制限は、合計値が5%を超えることはできないため、現在5%以内の精度にはできないため、ユーザーが永久に入力することです。
私がこれまでにしたこと
これがこれまでの私の解決策です(それほど多くはありません)。基本的に、私はすべての値を取り、それらのすべての可能な組み合わせを理解します(私はこの部分を完了しました)。次に、可能なすべてのコンボを取得し、それらを辞書としてデータベースに配置します(たとえば、$ 143の場合、辞書エントリ{apple:143、Pears:0、Oranges:0}..{appleまで:0、Pears:1、Oranges:47}。新しい番号を取得するたびにこれを行うので、すべての可能性のリストがあります。
これが私が立ち往生しているところです。上記のルールを使用する際に、どうすれば最善の解決策を見つけることができますか?2日間のデータを自動的に比較し、前日のデータと5%を超える分散がある可能性を排除する適応度関数が必要になると思います。
質問:
それで、ユーザーが合計を変更し、すべての確率のリストを持っているという私の質問ですが、これにどのようにアプローチする必要がありますか?何を学ぶ必要がありますか?そこに適用可能なアルゴリズムや使用できる理論はありますか?または、私の間違いを理解するのに役立つように、この目標を実現するために追加できるルールを提案できますか(現在の状態でない場合。果物を追加して、少なくとも3つ選択する必要があると言っていました)。 ?また、遺伝的アルゴリズムについては漠然としか理解していませんが、何か使えるものがあれば、ここで使えると思いました。
私は非常に学びたいと思っているので、アドバイスやヒントをいただければ幸いです(このゲームは不可能だと言わないでください)。
更新:これを解決するのは難しいというフィードバックを得る。だから私は、プレイヤーがしていることを妨げない(ゲームは彼らにとって同じままである)が、毎日果物の価値が(ランダムに)価格を変える別の条件をゲームに追加すると思いました。それは解決を容易にしますか?5%の動きと特定の果物の価値の変化の範囲内であるため、時間の経過とともに可能性が高い組み合わせはごくわずかです。
1日目は何でも可能で、十分に近い範囲を取得することはほとんど不可能ですが、果物の価格が変化し、ユーザーは5%の変更しか選択できないため、範囲を(時間の経過とともに)狭くしたり狭くしたりしないでください。上記の例では、価格が十分に変動する場合、推測できる範囲を与える解決策を総当たり攻撃できると思いますが、この範囲を狭め続けるためのより洗練された解決策や他の解決策があるかどうかを調べようとしています時間。
UPDATE2:読んで質問した後、これは隠れマルコフ/ビタビ問題であり、果物の価格の変化と合計(最後のデータポイントを最も重いものに重み付け)を追跡していると思います。しかし、関係をどのように適用するかはわかりません。これは事実であり、間違っている可能性があると思いますが、少なくとも、これはある種の機械学習の問題であると考え始めています。
更新3:ユーザーが生成したデータを自動化するのに役立つテストケース(数値が小さい)とジェネレーターを作成し、そこからグラフを作成して、より可能性が高いものを確認しようとしています。
これがコードと、ユーザーが実際に実を結ぶ量についての合計値とコメントです。
#!/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