ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて，そういえば組んだことがないなぁと思い立ち．

目的

パズドラのパズルにおいて，コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する．
今回は，ダメージ等については考慮しません．

方針

ビームサーチを使います．”ビームサーチ”で検索すれば良い記事が沢山出てくると思うので，詳細は割愛．

ビームサーチは下のをそのまま実装しました．

とりあえずビームサーチってこんな感じなんですよ。とりあえずまずこれが解るのが前提。https://t.co/uivkCk4LMD pic.twitter.com/ro4m5WhybE

— chokudai(高橋 直大) (@chokudai) 2016年3月27日

状態は，｛”パズルの盤面の状態”，”今動かしている部分の座標”，”何手動かしたか”｝とし，パズルを1手動かした状態を遷移状態としています（上下左右で4つの状態に遷移）．
コンボ数をそのまま状態の評価値として扱います．

初期状態は，パズルをスライドさせるスタートの位置を変えたもの，計30個に設定．
また，ビーム幅は40000，最大ターンは12として実行します．

ZobristHashで盤面のハッシュ値を生成し，同じ盤面を2回探索しないようにしています（出来てるかは謎）．

deleteしてないからヤバそうなC++コード
https://ideone.com/MbxQOR

まとめ

サクサクっと作った割には5,6コンボ出るので，凄いと思いました．
適当に作ったので（言い訳），全てにおいて杜撰なコードになっています．

記事の書き始めた時はもっとしっかり書こうと思っていたんだけど，途中で面倒くさくなってしまった．