遺伝的アルゴリズムを使用したオセロAIの作成
遺伝的アルゴリズムを使ってオセロAIを作ったお.
この記事は筑波大学アドベントカレンダー13日目の記事です.
最初に
今回作成したオセロAIとはここから遊べます. 遊びながらこの記事を読んでくれると嬉しいです.
概要
この記事では盤面の評価のパラメータ調整において遺伝的アルゴリズムを適用したオセロAIでくのぼうの詳細な解説記事となります.
この記事では最初に遺伝的アルゴリズムを適用しやすいようにした評価関数の仕様を解説し, 次にその仕様に基づいた遺伝的アルゴリズムの適用方法を一般的な遺伝的アルゴリズムの方法と合わせ解説します.
最後に, Webで公開した際の構成を解説します.(あとで追記する)
この記事では一般的なオセロAIと同様の機能(探索や盤面管理など)についての詳細な解説は行わないつもりです.
こちらについての詳細な手法を知りたい方はにゃにゃん氏(@Nyanyan_Cube)が書かれているオセロAIの教科書を一読されることをおすすめします.
また, AIのソースコードはこちらで公開しています. この記事と合わせてお読みいただけると幸せになれるかもしれません.
評価関数の仕様
一般にオセロや将棋のような対戦型のゲームAIは以下の手順で指し手を生成し, 1ターンプレイします.
- ルールに基づいて次にプレイすることのできる手を生成する(合法手の生成).
- 生成した合法手からn手進める(探索, nは自然数).
- n手進めた先の局面に得点をつける(評価).
- 得点が最も高くなる手を着手する
このうち, 3.における局面への得点の付け方のことを評価関数と呼んでいます.
評価関数は最も工夫がしやすく, 開発者によって個性がでて面白いところです.
今回作成したオセロAIの評価関数は以下の式で定義しています.
\begin{align}
L _ {i} & :\ 盤面の辺の石の並びの評価値\\
M _ {i} & :\ 盤面の斜め方向の石の並びの評価値\\
R & :\ 盤上の石のうち自石の占める割合\\
\alpha & :\ 定数(20手ごとに値が変わる)\\
評価値& = \sum_ {i=1} ^8 L _ {i} + \sum _ {i=1} ^4 M _ {i} + 12\alpha R
\end{align}
ここで定義されている$L _ {i}$, $M _ {i}$, $\alpha$はすべて正確な値を計算することができないため, これらの値を調整する必要があります.
辺の石の並びの評価
辺の石の並びは, 図1のように角から行方向, または列方向に4マス分抽出して評価します.
ここでは, 例として縦方向の辺を抽出します.
ここで, オセロの盤面の各マスの状態を考えると以下の3通りのみであることがわかります.
- 何も石が置かれていない
- 先手の石(黒石)が置かれている
- 後手の石(白石)が置かれている
この事実から, 何も置かれていないマスを0, 先手の石(黒石)を1, 後手の石(白石)を2と表現すると辺の石の並びは3進数として表現できることがわかります.
これをもとに, 図2を3進数で表すと$1200_ {(3)}$となります.
ここでそれぞれの石の並びのパラメータを配列で保持しておき, 石の並びの評価値を前に示した3進数に対応するインデックスに格納されている値とすることで辺の石の並びの評価ができることになります.
これを図3に示す8箇所全てに対して行い, 総和を取ります.
斜め方向の石の並びの評価
こちらは手法自体は辺の石の並びの評価方法と変わりません.
ただし, 辺の石の並びの評価値とは別のインデックスから評価値を取ってくるようにしています.
こちらは図4に示す4箇所について行い, 総和を求めます.
遺伝的アルゴリズムの適用
今回, 先に述べた評価関数で必要なパラメータ数は, \begin{align} & 81(辺の石の並びのパターン数)+\\ & 81(斜め方向の石の並びのパターン数)+\\ & 3(盤上に占める自石の割合)=165個 \end{align} となります. この全てを最適(AIが最も強くなるよう)に調整することはほぼ不可能です. そのため, これらのパラメータをAIが強くなるように調整するために遺伝的アルゴリズムを使用します.
遺伝的アルゴリズムとは
遺伝的アルゴリズムとは, 確率的探索アルゴリズムのひとつであり, 組み合わせ問題に対する最適解を求めることが計算量的に困難であるときに有効な手法です. 最適解が求められる保証はありませんが, ある程度の時間を費やせばそこそこの解が得られることで知られています. 「遺伝」というワードが入っているところから想像がつくかもしれませんが, 生物の進化から着想を得ています.
遺伝的アルゴリズムは以下の手順により行われます.
- 集団を構成する個体群を生成する.
- 交叉(個体群から2個体を取り出し親として, 子孫を生成する)
- 突然変異
- 選択
ここからはこれらの手順を今回作成したオセロAIでの手法をもとに具体的に説明していきます. 詳細な実装はこちらをご覧ください.
1. 集団を構成する個体群の生成
今回定義した評価関数では全部で165個のパラメータが必要なので, 1つの個体は長さが165の配列とします. また, 評価値計算時に発生するであろうオーバーフローを防止するため, 各パラメータは-1以上1以下の浮動小数点数を取ることにします. 個体群の数は今回は1024個とし, 最初に生成するときはすべて-1以上1以下の乱数で初期化します.
2. 交叉
交叉では最初に1.で生成した個体群からランダムに2個体選び出します(それぞれ便宜的に親A, 親Bと呼びます).
その後, 図5のように任意の2点で個体を切断し, その間の値を入れ替えて子を生成します(親Aをベースにした子孫を子A, 親Bをベースにした子孫を子Bと呼びます).
この2点はランダムに決定します.
3. 突然変異
突然変異では2.で生成した子A, 子Bそれぞれに対して, すべての配列の要素を1%の確率でランダムな値に書き換えています.
4. 選択
選択では親A, 親Bと子A, 子Bのどちらを淘汰するかを決定します. 今回は強いオセロAIを作ることが目的なので, 弱い方を淘汰する必要があります. どちらが強いかを判定するためには直接戦わせてみるのが1番簡単です. そのため, 選択では親Aと子A, そして親Bと子Bでそれぞれ手番を入れ替えながら何回か対戦させます. そして, 子の方が親に対し一定以上の勝率があるのであれば親を淘汰し, ないようであれば子を淘汰します. 今回は全部で30回対戦させ, 55%以上の確率を基準に淘汰するかどうか判定しています. 対戦回数を多くすると交叉に時間がかかってしまう一方で対戦回数が少なすぎると偶然の要素が強くなってしまうため, 実際に測定してみて偶然の要素が少なくなるであろうギリギリのラインとして対戦回数を30回にしています. また, 勝率の基準を55%にしているのは, 例えば勝率51%は本当に実力に差があるのかというと疑問が出てくるため, 体感的に実力の差が出そうな基準が勝率55%であろうと考えたからです.
ここで紹介した2. 交叉～4. 選択を100回繰り返し, これを1回のループとして長い時間をかけて何度もこのループを回し, 評価関数のパラメータ調整を行っています. 短くても7時間はかかっています.
結果・課題
生成した評価関数をもとに, 先読みの機能等を実装し, webで遊べるようにしました. 開発者が対戦してみたところ, ぼこぼこにされるまで強くなりました.
全消しされて泣いてる pic.twitter.com/xrMJpjrFo1
— JJ1GUJ@研究の進捗がまずい (@jj1guj) 2021年11月26日
一方で, 他のAIに対してはまだまだ勝率が低いことが課題となっており, まだまだ改善の余地があります. 勝率が低い原因として以下の事が挙げられます.
- 先読みの性能が低い(一定時間で読める局面の数が少ない)
- 序盤の精度が悪い
先読みの性能の低さはより高速な探索アルゴリズムを実装することで, 序盤の精度の低さはあらかじめ定石を用意しておき, 最初はその定石に載っている手を打つようにすることで改善できると考えられます. 尚, 今回作成したAIは序盤は弱いものの中盤は強いという評価を聞いていたりするので評価関数が弱いことが原因とは言い切れないと思っています.
今後の展望
今後は, 課題点を改善していき, 余裕があったら評価関数の仕様も少し変えてみようと思います. また, オセロAI以外にコンピュータ将棋のfloodgateのようなオセロAI用の連続対局場所を作り, 大会を開きたいと思っています.
最後に
現在, オセロAI開発者用のDiscordサーバーを運営しています. オセロAIの開発やオセロAI用の連続対局場所の開発に興味がある方は@jj1gujにDMを送ってくだされば招待します.
