不完全情報ゲームのAIの論文を調べていて、たまたまハースストーンのAIコンペがあることを知ったので、試したいこともあったのでさくっとMCTSのプログラムを作って提出してみた。
ハースストーンは、相手の手札や山札は見ることができない不完全情報ゲームで相手の隠れた情報を予測するなどしないと探索を行うことができないという難しさがある。
また、行動の結果が、確率的な場合がある。
去年のプログラム
AIコンペは、2018年から毎年開催されているようで、昨年の優勝プログラムのソースコードも確認できる。
さぞかしすごいプログラムなのかと思って確認してみたら、拍子抜けするくらい簡単なコードだった。
ハースストーンは自分のターン内でも複数回行動が必要なため、自分のターン内だけでも探索するだけでも有効である。
昨年の優勝プログラムは、自分のターン内だけをMin-Max探索(自分ターン内だけなので実際Maxのみ)して、終端ノードで評価関数で評価するだけという単純なプログラムだった。
確率的状態遷移も考慮していない。
評価関数もヒーローのHP差、ミニオンのHPと攻撃の差をカウントしただけのシンプルなものである。
2位のプログラムは、MCTSを使用して、自分のターン内だけ探索するプログラムである。
ゲームの終端までシミュレーションを行わず、自分のターン内終わりで評価関数で評価した値をバックアップしている。
1ターンの途中で評価を行うと誤差が大きいため、自分のターン内終端まではロールアウトポリシーを使用してロールアウトを行っている。
評価関数とロールアウトポリシーのパラメータ数は、上記の優勝プログラムよりは多く、作りこまれている感じがする。
試したこと
AIコンペに気付いたのが締め切りの2週間前だったので、2位のMCTSのコードをベースにして、評価関数を優勝プログラムのものを使用して、試したかった内容だけ追加した。
試したのは、以下の内容である。
- 自分のターン内でカードを使用する順番が違うだけで同じノードになることが多いため、ハッシュマップでノードを合流できるようにする
- 自分のターン内ツリーの再利用する
ハッシュマップを使用することで、確率的な遷移がある場合も複数回シミュレーションされることで、親ノードには期待値がバックアップされることになる。
また、ツリーの再利用も行いやすくなる。
ハッシュコードの生成
将棋や囲碁では、座標と駒の組み合わせにゾブリストハッシュを使用して、XOR演算でハッシュコードを差分を計算していくことができる。
ハースストーンでは、ミニオンにHPやエンチャントや状態異常ステータスなどがある。
ハースストーンで同じようにゾブリストハッシュを使用しようとすると、位置×ミニオン、位置×HPの値、位置×エンチャントの種類などにゾブリストハッシュを割り当てることになる。
しかし、コンペでは、ゲームのシミュレータがエージェントからブラックボックスの扱いになっているので、差分計算のようなことはできない。
また、カードの種類も事前には分かっていない。
そのため、カードIDの文字列、HPの値、位置×エンチャントの種類などから、動的にハッシュコードを生成することにした。
具体的には、C#の文字列のハッシュコードを生成する処理を参考に、
((hash1 << 5) + hash1) ^ 値1 ((hash2 << 5) + hash2) ^ 値2 ... return hash1 + hash2 * * 1566083941
という処理で64bitのハッシュコードを生成するようにした。
1566083941は、線形合同法のランダム生成で使われる値で、この値に適当な数を掛けると上位ビットがランダム性のある値になる。
手札については順番が入れ替わっても同じ状態としたかったため、それぞれのカードのハッシュコードを生成して、それらの和を手札のハッシュコードとした。
（テストしたところ、ハッシュの衝突が起きることがわかったので、HPなどの値には1566083941を掛ける、「((hash2 << 5) + hash1)」としてhash1とhash2を関連させるなどして衝突がおきにくくした。）
ハッシュコードの衝突が起きないように実装できたところで力尽きたので、評価関数はいじることなく提出した。
去年の優勝プログラムには3割くらいしか勝てていないのでたいして強くないが、ハッシュコードについての知識が増えたので良しとしよう。
提出したコード：
HearthstoneAICompetition/MyAgent.cs at master · TadaoYamaoka/HearthstoneAICompetition · GitHub
