はじめに

静的リバーシ AI を作成しました． 経緯や詳細は以前の記事をご覧ください．

静的リバーシ AI とは，リバーシの 64 マスに対して事前に着手する優先度が決められた AI です． ゲーム中はその優先度に従い，着手できるマスのうち，最も優先度が高いマスを選びます．

つくりかた

手でパラメータを調節してもそれなりに良さげな優先度マップを作ることはできるでしょう． ですが，折角なのでプログラムを書いて，良いマップを探索することにしました．

計算コストについて

優先度マップは $64!$ 通り存在します（最初に置いてある 4 マスを考えると $60!$ 通り）． 戦略として，これら全ての総当たりをして一番勝利数が多い優先度マップを採用することが考えられます．

しかし，愚直に総当たりを行うと，到底計算は終わりません．約 $\frac{(60!)^2}{2} \approx 4 \times 10 ^ {81}$ 対戦が行われる計算ですが，現行の計算機では $1$ 秒間にざっくり $10^{10}$ 回程度しか計算を行うことができません． 仮に，$500$ 回の計算で $1$ つの対戦が行えるとしましょう． すると，$1$ 秒間に約 $2 \times 10^7$ 対戦を行うことができるので，全ての対戦を終えるには約 $2 \times 10^{74}$ 秒，年に直すと約 $6 \times 10^{66}$ 年です． 宇宙誕生から現在まで約 138 億年と言われています．指数表記にすると $1.38 \times 10^{10}$ 年，これに対して文字通り桁違いな計算時間が要求されています．地球滅亡どころか宇宙滅亡しても計算は全くもって終わりません．

このように，組み合わせは簡単に爆発します．我々の持っている計算資源は遅すぎるので，最良の解を求めるのは，よほど単純な問題でないと不可能なのです．

なので，最強の優先度マップを作ることは不可能であり，ある程度のところで妥協する必要があります．そこで，ヒューリスティック（概ね良い回答を見つける手法）を用います．

ヒューリスティック：遺伝的アルゴリズム

今回用いたのは，遺伝的アルゴリズム（Genetic Algorithm，GA）です． いろいろやり方はあると思いますが，個人的に GA は好きなアルゴリズムで，かつ丁度使える問題だったので使ってみました．

GA そのものの解説は長くなりすぎるので割愛します．ここでは，遺伝子をどう設計したかについて書きます．

優先度マップと先ほどは書きましたが，求めたいのは 64 マスの優先度の順序です． 今回の問題設定の場合，この順序が多少前後しようと，性能はほとんど変化しないという特性があると考えられます．そのため，GA が有効に働く問題設定であると考えました．

さて，この場合，遺伝子としての持ちかたとして以下の 2 通りが考えられます．

• 順序を持つ
• 内部的な優先度を持つ

今回は，内部的な優先度を持つ手法で実装を行いました．

交叉として，BLX-α を用いました． これは，ある成分について，それぞれの親の値が $x$，$y$ である（$x \leqq y$ とする）とき， 子のその成分の値を $\left[x - (y - x)\alpha, y + (y - x)\alpha\right]$ から一様ランダムに選ぶ手法です．

今回は $\alpha = 0.5$ としました． また，値の範囲が $[0,1]$ に収まるようにクリップを行いました．

突然変異として，ある要素について，低確率で $[0,1]$ の範囲から一様ランダムで選ばれた値に置き換えることを行いました．

世代内のランク付けは，世代内で総当たりを行うことで行いました．

詳細な実装についてはこちらをご覧ください． 最終世代の最良個体を採用するのではなく，揺らぎを考慮して最後数百世代の最良個体で総当たりして最終的に採用することを行なっています．

結果

通常のリバーシ向け（なるべく多く石をとることを目指す）の静的 AI と，逆リバーシ向け（なるべく最終的な石の数を少なくする）静的 AI の両方を作成しました．

以下が通常リバーシ向けに作成した AI の優先度マップです．

54,12,32,20,16,42, 9,47
 8, 7,25,29,13,11, 2, 3
60,26,62,50,44,59,21,53
27,36,58,28,52,30,33,31
22,19,40,35,39,61,34,48
45,18,49,37,56,55,38,51
 0, 1,24,43,14,15, 4, 5
46,10,41,23,17,57, 6,63

隅自体の優先度は高く，その周りが低いです． 辺については，真ん中の 2 マスよりその隣の 2 マスの方を優先するようです． 用語を用いると，C や X を避けています．また，辺では B より A を優先するようです．

次に，逆リバーシ向けに作成した AI の優先度マップは以下です．

 5,15,11,31,23,16,44, 3
60,10,12,35,62,17,13,34
 8, 9,56,61,43,48,14, 7
30,24,45,55,52,26,42, 2
27,33,54,51, 1,46,57,59
18,20,47,41,40,38,19,25
50,21,28,63,53,32,22,58
 4,37,39,29,36,49, 0, 6

隅の優先度が低いというところは想像通りですが，いくつか不思議な箇所がみられます． まず，右上や右下隅周辺について，隅の隣のマスの優先度は片方が低く，片方が高いというアンバランスな結果になっています．隅の隣というのは同条件に思えますが，辺の攻防においてこれが有利なのでしょう．興味深いです．

おわりに

これらの優先度マップはそのうち静的 AI と対戦できるリバーシ盤面のプリセットに組み込んでおきます．

次回，作った AI で対戦します．