[Python]パックマンを遺伝的アルゴリズムしてみた
GDD(Google Developer Day)のQuizが終わりました。
その中にパックマンという問題がありました。これはパックマンの敵の動きを示されその中でいかにドットを多く取っていくかという問題でした。
敵の動きのシミュレートは(めんどくさいけど)すぐにできたので、あとは自機の動きをどのように導き出すかがポイントとなります。
うーんと唸りましたが、なんとなーく遺伝的アルゴリズムを使って計算機に導き出してもらうこととしました。
pyevolve
ありがたいことにpythonには、 pyevolve という遺伝的アルゴリズムを簡単に使えるライブラリがあります。これを使わせてもらうことにしました。
ちなみに、今回はじめて遺伝的アルゴリズムを勉強したので、たぶんいろいろ間違っていると思います。ご指摘がありましたらぜひお願いします。(というか、どうやろうかな、と思ったときにこれを機会にちょっとGAを勉強してみようと思ったのです)
以下にコードを示します。
from pyevolve import GAllele
from pyevolve import G1DList
from pyevolve import Mutators
from pyevolve import Selectors
from pyevolve import Crossovers
from pyevolve import GSimpleGA
from pyevolve import Initializators
from pyevolve import Consts
GENERATIONS = 10000 # 最大世代数
POPULATION_SIZE = 100 # 1世代あたりの標本数
CROSSOVER_RATE = 1.0 # 交配率
MUTATION_RATE = 0.10 # 突然変異発生確率
base_status = None
def main(path):
global base_status
base_status = read_input(path) # 問題文読み込み
setOfAlleles = GAllele.GAlleles(homogeneous=True)
a = GAllele.GAlleleList(["h","j","k","l", "."]) # 使用する遺伝子 *1
setOfAlleles.add(a)
genome = G1DList.G1DList(base_status.max_time) # 遺伝子のサイズ *2
genome.setParams(allele=setOfAlleles)
genome.evaluator.set(eval_func) # 使用する関数をセット
genome.initializator.set(Initializators.G1DListInitializatorAllele)
genome.mutator.set(Mutators.G1DListMutatorAllele)
genome.crossover.set(Crossovers.G1DListCrossoverSinglePoint)
ga = GSimpleGA.GSimpleGA(genome)
ga.setGenerations(GENERATIONS)
ga.setPopulationSize(POPULATION_SIZE)
ga.setCrossoverRate(CROSSOVER_RATE)
ga.setMutationRate(MUTATION_RATE)
ga.selector.set(Selectors.GTournamentSelector)
ga.setElitism(True)
ga.setMinimax(Consts.minimaxType["maximize"]) # scoreを最大にする
ga.evolve(freq_stats=100) # 100世代ごとに表示する
# 最良のchromosomeを表示
print ga.bestIndividual()
def eval_func(chromosome):
'''
gaから呼ばれる評価関数
引数のchromosomに遺伝子がlistで入っている
'''
st = copy.deepcopy(base_status) # 今回の計算に使用する状態を初期状態からコピー
movement_list, dot_count, life_time = run_one(st, chromosome) # 一回実行
return dot_count # 取ったdotの数をscoreとする
遺伝的アルゴリズム部分はこれだけです。なお、run_oneの中でchromosomeの中に詰まった自機の動きリストを取り出して動かしています。
解説
今回の問題では自機の動きは上下左右に加えて動かないの5種類です。GAllele.GAlleleList()を使ってこの5種類から遺伝子を選ぶようにします(*1の部分)。ただし、動かない”.”は必要ないと思いますし、実際に外して計算しました。
G1DList.G1DList()で遺伝子のサイズを決定します(*2の部分)。max_timeはつまりTの値になるのですが、後述するように毎tごとに移動先を決めるようにはしなかったので実際にはこんなに大きくは必要ないと思います。また、遺伝子はランダムなので、壁に向かって歩こうとしてしまいます。これは時計回りに開いている方向を探すことで一応の解決をしました。
さて、これで実行したところ、5時間ぐらい4万世代ほど計算しても90点止まりで全然でした。なのでもう少し頭良くしようと以下のように改良しました。
- 交差点まで可能な限り(モンスターがいない限り)直進するように
こうしたところ、1000世代計算すれば200点を取れるようになりました(それまではtごとに動きを計算してたわけです)。しかし、最初のGとeの所はどうやっても取れないです。で、動きをよーく見るとVとHは常に自機を追いかけているわけで、eは最初に、Gは最後になる必要があるのかなぁ、と思い、最初と最後は人力で取るようにしました。
さらにここで
- なるべくドットを取りに行くように * 一定時間取れない場合はscoreを下げる
という評価を付け加えたところ、230点ほど取れるようになったので、あとは人力で解いてクリア(全部のドットを取る)となりました。得点は380点でした。
今のところの結論
Twitterを見ていると、10秒で答えを出したりしている人もいるようです。しょせんにわか勉強なので、遺伝的アルゴリズムで使用するアルゴリズムの選択が間違っているのかもしれません。まあ、問題的に遺伝的アルゴリズムを適用するべきものではないような気もしますが。
とはいえ、この「なにも考えないでいい」というお気楽さはかなりいいなぁ、と思いました。まる。