チェスや将棋のAIについて調べてみた

　MTGの最適プレイに向けたシミュレーションを行うため、既存のゲームAIの手法と研究の進展状況について調べてみた。

　調べてみると、やはり完全情報ゲームのほうが研究は進んでいるようで、完全情報ゲームだる将棋はプロと対等に戦えるレベルまできている一方で、多人数不完全情報ゲームのポーカーはヘッズアップ（１対１で分岐が小さい）ならばプロレベルという程度のようだ。

ゲームAIを作る上での難易度はそのゲームの探索空間の大きさ（＝複雑さ）に強く依存する。オセロ＜チェス＜将棋の順に探索空間が大きい。オセロは完全に木の探索が終わっており、完全な解がわかっている。チェスはチャンピオンを倒しており、将棋もプロと渡り合えるレベルまで来ているようである。

チェスのＡＩ

　チェスでは、木探索と評価関数を使用するだけのAIでプロを破るまでになった。木探索とは展開ゲームの枝分かれをたどって行き、どう動くと何ターン先にどういう状態になるかを調べることである。当然いきつく先が一番いい状態になる手をプレイするのだが、この良い状態なのかどうかを判断するのが評価関数である。相手の駒を減らしたら加点、自分の駒を減らしたら減点、という具合に評価するのだが、駒の配置がよくなったということに対して何点与えるのかといったことが難しそうである。

将棋のＡＩ

　将棋においても中盤戦ではチェスと同様に木探索と評価関数が用いられ、主要な研究はこのふたつに当てられているようである。

　木探索の研究では、余計な探索を減らして必要な探索を深く行う方法の研究が多く、「激指」というAIではもっともらしいを見積もった後に、もっともらしいものから深く探索していく手法がとられている。

　評価関数の研究では、BonanzaというAIは、評価関数のパラメーターをできるだけプロの棋譜と同じように打つように調整されていて、その調整に多量の棋譜を読み込んで機械学習を行うという手法がとられた。

MTGとの対比

　MTGのほうが評価関数はいわゆるアドバンテージを数式化したものである。幸い、MTGにはカードアドバンテージやテンポアドバンテージ、ライフアドバンテージといった用語がすでに存在し、序盤はカード・テンポに重きをおき、ゲームが進むにつれてライフを気にするようになることを知っている。これらのアドバンテージの比重はお互いのデッキタイプや展開によって異なる。これらをどう数式化するかが課題である。

　探索については、将棋と違いランダムの要素がある。将棋では相手もベストの手を打つとして考えることで結果が一意的に決まるがランダムが入ることでそうはいかないだろう。次は不完全性ゲームについて調べ、探索方法についてのアルゴリズムを探さがしてみる。