自分の勉強も兼ねてモンテカルロ法について書いていきます。
何か間違いがあったら指摘してくださると嬉しいです。
前回の記事
から色々試してランダム君に100%勝利を目指したものの、中々成果が出ないので、
素直に探索アルゴリズムを組もうかと思っています。
オセロはmin-max法が主流ですが、alpha go zero でも使われたモンテカルロが面白そう尚且つ、プログラマーが楽できそうな方法なので、そちらを試してみたいと思います。
原始モンテカルロはある局面から、ひたすらランダムで対局を重ね、勝率の統計を取り、一番高い勝率をその局面の手として採用する方法ですが、完全にランダムだと最善手に行き着く事は中々ありません。
そこでモンテカルロUCTと言われている方法で探索したいと思います。
ただ今回はオセロの探索アルゴリズムとしてではなく、
モンテカルロ法でよく取り上げられていたスロット問題として、実装してみます。
import random
import numpy as np
def machine1():
return random.randint(1, 10)#期待値 5.5
def machine2():
return random.choice([0] * 8 + [10, 20]) #期待値 3
def machine3():
return random.choice([2, 3, 5]) #期待値 3.3333...
def machine4():
return random.choice([3, 4]) #期待値 3.5
def machine5():
return random.choice([0] * 49 + [100]) #期待値 2
def ucb(mean, total_coin, coin, X):
return mean + X * np.sqrt((2*np.log(total_coin)/coin))
def main(X, play_num):
#最初は全てに1枚ずつ投資してから開始する
machines = [machine1, machine2, machine3, machine4, machine5]
total_values = [machine() for machine in machines]
mean_values = total_values.copy()
total_coin = len(mean_values)
coins = [1] * len(mean_values)
search_num = [1] * len(mean_values)
for i in range(play_num):
#どのマシーンのucb値が最大なのかを見る
max_ucb = \
np.argmax([ucb(mean, total_coin, coin, X) \
for mean, coin in zip(mean_values, coins)])
#ucbが最大値のマシーンにコインを投資し、値を更新する。
coins[max_ucb] += 1
total_coin += 1
value = machines[max_ucb]()
total_values[max_ucb] += value
mean_values[max_ucb] = total_values[max_ucb] / coins[max_ucb]
search_num[max_ucb] += 1
print(search_num)
if __name__ == "__main__":
main(10, 10000)
調べればすぐに出てくると思いますが、スロット問題(多腕バンディット問題とも言われている)についても触れていきます。
スロット問題とはいくつかのスロットマシーンがあったとして、
なるべく損失する事無く、どのマシーンにコインを投資すれば、儲かる期待値が高いのかを調べるという問題です。
当然それらのマシーンはどのように設定されているかは不明です。
原始モンテカルロの場合、全てのマシーンに均等に投資しますが、これだと質の悪いスロットがあった場合、大損します。
儲けたいのであれば、やはり儲かりそうなスロットに重点的に投資したいですね。
しかし、その儲かりそうなスロットを見つけるには、ある程度の投資が必要です。何故なら1枚コインを入れて結果が悪かったとしてもたまたまの可能性があるからです。
だからと言って、儲かりそうなスロットを見つける為に、投資ばかりをしたら、損する可能性も出てきます。
つまり、探索と経験のバランスが大事になってくるわけです。
じゃあどうすればバランスよくコインを投資出来るの？
という疑問に答えてくれるのがUCBになります。
def ucb(mean, total_coin, coin, X):
return mean + X * np.sqrt((2*np.log(total_coin)/coin))
(式間違ってたら教えてください)
引数のmeanはそのマシーンに投資して、コインが戻って来た平均値です。
total_coinは全てのマシーンに投資したコインの枚数です
coinはそのマシーンに投資したコインの枚数
Xは経験と探索のバランスを決める定数です。
後はこの式をマシーン別に割り当て、式の結果の値が一番大きいマシーンに投資すれば、経験と探索をバランスよく取る事が出来るようになります
この式の結果の値をucb値と言うようです。
この式の性質として、定数Xが大きいほど、探索を重視し、小さいほど、経験を重視します。
また平均値が大きいほど、当然ucb値も増えていきます
しかしcoinの枚数が増えれば、増えるほど、ucb値は小さくなっていきます。
つまりこれは良さそうなマシーンだけど、いっぱい投資したし、別のものも試してみるかという事が起きます。
では実行結果を見てみましょう。
[9792, 44, 61, 71, 37]
このリストは各マシーンに投資した数になります。
期待値通りの投資数になっていますね
では次にmain(1, 10000)とし、定数Xを減らした結果を見てみます。
[9994, 7, 1, 2, 1]
探索数が減っているのがわかりますね。
次にmain(50, 10000)とし定数Xを増やした結果を見てみます。
[7460, 551, 807, 863, 324]
今度は探索数が増えているのがわかりますね。
この定数をどう決めるかは問題によると思いますが、alpha goは5だったようです。
さて、今回はここまでにします。
次回は、オセロの探索としてUCBを取り入れていきたいと思います。
追記1
コメントを受けてコードを修正しました。