こちら2023年伺かアドベントカレンダーの5日目の記事になります。
昨日はりすなさんの 生成AIについてのお話 です。
ゲーム搭載ゴ増えてくれ！という願望のもと、 リバーシゴーストを作った過程をつらつらと書きました。
リバーシで遊べるようにしたいけど作り方分からん、とか 作ったは良いけど簡単に勝てちゃってつまらん、という人の助けになれば。
「YAYAでリバーシ実装。ニューラルネットワークもあるよ！」
SAORIを使わずYAYAだけで動くようにしてあるので C言語？何それおいしいの？な人でも安心！ なお
-
リバーシ機能搭載ゴーストの作り方
-
MiniMax法とAlphaBeta法
-
YAYAでニューラルネットワーク動くんだ、という知見
とりあえず遊んでみたい！という方は リリースページ からどうぞ。
操作方法は本文の遊び方に記載しています。
明日は月波清火さんの YAYA用ツール公開 です。お楽しみに。
以下本文。
作って学ぶ！リバーシゴースト
伺か界隈にはリバーシで遊べる機能を搭載したゴーストで リバーシの腕を磨いたユーザが多数いるという。 そのようなユーザにとってはおまけ機能として載せたリバーシなぞ朝飯前なので、 こちらとしてもしっかりしたAIを載せなければ失礼かもしれない。 ということで、最終的にはNNを雑に使ってまあまあの強さのAIを作っていく。
SAORIを使えばもっと強いものが作れるが、そうすると コードを弄って遊ぶのが難しくなるので 可能な限りSHIORIのみで開発を行う。
SHIORIは基本的にはYAYAを使っていくが、 評価関数を強化するではPythonを使う。 理論上はYAYAでも出来るので、 Python分からんという人はYAYAで作ってみてもいい...いいのか？
里々、華和梨はほとんど使ったことが無いので取り扱わない。 既存のゴーストにリバーシを実装しているゴーストはいるので、 他人のゴーストの辞書を見ることに抵抗が無ければ 中身を見るべし。
この本で紹介するコードは ネット上にアップ しているので、 ダウンロードして遊んでみるのもまた一興。 コードが極力きれいになるよう心掛けはしたものの、 ウンコードな部分があることには目を瞑ってほしい。
-
盤と石の画像
-
SHIORI
本書では、シェルでリバーシを遊べるようにするが、 バルーン上で遊べるようにする方がGUI部分の作成が楽。
盤の各マスに石を表示できるようにするが、 盤面をSakuraScript(\![bind,...])で操作することを考えて、 次のような命名規則にする。
まずはカテゴリ名。 例えば、左から2マス、上から4マスの位置に黒石を置くときは
\![bind,24_REVERSI,...]
のようにする。 この11〜88の64個が必要なカテゴリとなる。
つづいてパーツ名について、まずはパーツはいくつ必要なのかを考える。 1マス当たりに必要な状態は次の4つ。
-
何も置かれていない
-
黒石が置かれている
-
白石が置かれている
-
何も置かれていないが、当たり判定が存在する
何も置かれていない状態はパーツをつけていない状態と同等なので、 必要なパーツ名はBLACK、WHITE、COLLISIONの3つになる。
以上をふまえてsurfaces.txtとdescript.txtを作る。 手打ちは大変なので自動化すると良いだろう。
石の画像の大きさは24x24pxとし、左上のマスの座標が14,14から始まるものとする。 当たり判定名は後のOnMouseClickで処理しやすいように 「XY_REVERSI_COLLISION」とする。 ただし、X、Yはそれぞれ左、上から何マスかを表す数字だ。
- surfaces.txt
descript
{
version,1
}
surface0
{
element0,base,board.png,0,0
}
surface10
{
element0,base,collision.png,0,0
}
surface1
{
element0,base,black.png,0,0
}
surface2
{
element0,base,white.png,0,0
}
surface3
{
element0,base,collision.png,0,0
}
surface.append0
{
animation0.interval,bind
animation0.pattern0,overlay,2,0,14,14
animation1.interval,bind
animation1.pattern0,overlay,3,0,14,14
animation2.interval,bind
animation2.pattern0,overlay,1,0,14,14
animation2.collision2,14,14,38,38,11_REVERSI_COLLISION
animation3.interval,bind
animation3.pattern0,overlay,2,0,14,38
animation4.interval,bind
animation4.pattern0,overlay,3,0,14,38
animation5.interval,bind
animation5.pattern0,overlay,1,0,14,38
animation5.collision5,14,38,38,62,12_REVERSI_COLLISION
...
}
- descript.txt
type,shell
name,master
seriko.use_self_alpha,1
sakura.menu.hidden
sakura.seriko.alignmenttodesktop,free
sakura.bindgroup0.name,11_REVERSI,BLACK
sakura.bindgroup1.name,11_REVERSI,WHITE
sakura.bindgroup2.name,11_REVERSI,COLLISION
sakura.bindgroup3.name,12_REVERSI,BLACK
sakura.bindgroup4.name,12_REVERSI,WHITE
sakura.bindgroup5.name,12_REVERSI,COLLISION
...
フローチャートを作ってリバーシの処理を整理しておく。
必要な変数は、各マスの情報を持つ配列boardと手番を表す変数colorだ。 boardは数値の配列で、3つの状態を持つ。
-
0: 石が置かれていない
-
1: 黒石が置かれている
-
-1: 白石が置かれている
黒石が1、白石が-1なのは後の評価関数での計算を書きやすくするためだ。
例えば、初期局面のboardは次のような配列になる。
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
見やすいように8x8の表にしているが実際は長さ64の配列だ。
変数colorは、黒石、白石と同様に1(先手)と-1(後手)で管理する。 手番の変更を
color = -color
で行えるのもポイントだ。
以上をふまえて、実際にコードを書いてみる。
前章でリバーシの操作部分を作成したので、いよいよ思考部分を作っていく。
完全読み(現局面から最終局面まですべての手を読むこと) は出来ないので、まずは評価関数を作っていく。
評価関数とは、 「ある局面の良し悪しを数値で表したもの(=評価値)を計算するためのもの」 である。
関数の名の通りy=f(x)で表すと
評価値 = 評価関数(局面の状態)
という関係性になっている。
この章では簡単な評価関数として、 1マス1マスに重み(ポイント)を設定して、 その合計を評価値とするものを作ってみる。 例えば次のような重みの設定を行う。
重みの数値については
http://www.geocities.co.jp/SiliconValley-Bay/4543/Osero/Value/Value.html
https://www.info.kindai.ac.jp/~takasi-i/thesis/2012\_09-1-037-0133\_S\_Shiota\_thesis.pdf
を参照のこと。
| 45 | -11 | 4 | -1 | -1 | 4 | -11 | 45 |
| -11 | -16 | -1 | -3 | -3 | -1 | -16 | -11 |
| 4 | -1 | 2 | -1 | -1 | 2 | -1 | 4 |
| -1 | -3 | -1 | 0 | 0 | -1 | -3 | -1 |
| -1 | -3 | -1 | 0 | 0 | -1 | -3 | -1 |
| 4 | -1 | 2 | -1 | -1 | 2 | -1 | 4 |
| -11 | -16 | -1 | -3 | -3 | -1 | -16 | -11 |
| 45 | -11 | 4 | -1 | -1 | 4 | -11 | 45 |
例えば、左上の角を取れば自分が45点プラス、その右隣を取れば自分に-11点、という感じだ。 全体的にマイナスの値が多いのは、 「序中盤は出来るだけ自分の石が少ない(=相手の手を限定させられる)方がいい」 という考えによるもの。 この表を先ほど用意した配列を掛け合わせれば評価値が算出出来る。 初期局面においては、次のような計算が行われる。
評価値 = 45 x 0 + (-11) x 0 + ... +
0 x 1 + 0 x (-1) + ... +
0 x (-1) + 0 x 1 + ... +
0 x (-11) + 0 x 45
非常に分かりにくいが、 「(1,1)の重みx(1,1)に置かれている石」+ 「(2,1)の重みx(2,1)に置かれている石」+ ...となっている。
さて、具体的な実装方法だが、この重み設定も変数boardと同じように 1次元配列pointに保存することで、 評価関数を簡単に実装することが出来る。
ただし、探索部の実装の都合上、ソースコードにおける評価値は 「先手が有利ならプラス、不利ならマイナス」というものではなく 「手番が有利ならプラス、不利ならマイナス」というものになっている。
前章で作ったAIは初心者バイバイの強さをしているが、まだまだ弱い。 この章ではAIを強くするもう1つの要素、「読み」の強化を行う。 作ったAIは「1手先を読んで一番評価が高い手を選ぶ」としていたところを、 今度は「N手先を読んで、一番評価が高い手を選ぶ」とする。
紹介するのは、MiniMax法とその改良版AlphaBeta法だ。
MiniMax法はざっくり説明すると
「自分の最善手は、1手先の相手の最善手の中で評価が一番悪くなる手」
というのをN手先まで繰り返す探索方法だ。
「最善手なのに一番悪くなるってなんじゃらほい」
と思うかもしれない。
まずは、次の図を見てほしい。
上が現局面、下が1手先の局面で、数値は1手先の局面の評価値を表している。 この説明では、評価値はプラスなら先手、マイナスなら後手が有利であることを 表しているものとする。 さて、先手が選ぶべき手は何だろうか。もちろん一番数値の高い指し手3だ。
では次。
この図では現局面から2手先の評価値が分かっている。 さて、ここで先手はどの手を選ぶべきかを考えるわけだが、 この状態ではわからないのでまずは1手先の後手番での状況を考える。
指し手1に進んだ状況で後手の立場になって考えると、 数値がマイナスに振れているほど後手にとって良い手なので、 -4の指し手Aを選ぶべきだ。 指し手2、指し手3についても同様のことを行うと、 指し手1-3の局面の実質的な評価値が分かる。
こうなれば先手が何を選ぶべきかは明解、指し手2だ。
今度は3手先のもので考えてみる。
先ほどのように、まずは2手先の先手番での状況を考えると
となり、次に1手先の後手番での状況を考えると図のようになる。
以上から、先手の選ぶべき手は指し手1となるのである。
このやりとりをプログラム上で表現するのがMiniMax法である。
(この、先手は評価の高い手を選ぶ(Max)、後手は評価の低い手を選ぶ(Min)というところからMiniMax法という名がついている...はず)
MiniMax法では、_score、_moveの初期化や更新時に先手の時と後手の時に 分岐したが、これを無くす方法がある。それがNegaMax法である。
MiniMax法では、 「先手は先手にとって良い手を選び、後手は後手にとって良い手を選ぶ」 という処理を行っていたが、NegaMax法では、 「手番が手番にとって良い手を選ぶ」となる。 先手後手を区別せずにうまく処理を行うことで、簡潔に書くことが出来る。
この変更でコードがすっきりするため、MiniMaxからNegaMaxへの変換は ぜひ覚えておきたい。
AlphaBeta法は、「MiniMax法で計算する必要の無い部分をとばす」 探索法である。
MiniMax法(3手)の部分図で考える。
評価値の計算は左から順番にしていくものとする。
指し手bの評価値が分かった時点で、後手が指し手Aを選んだら最終的な評価値は 1(先手は指し手bを選ぶ)となることがわかる。 さて、次は指し手cを計算して4という結果を得るわけだが、 この瞬間、指し手dの評価値がいくつであろうと指し手Bを選んだときの 最終的な評価値が4以上になるのがお分かり頂けるだろうか。 図のように、指し手dの評価値が指し手c以下である場合は、 先手は指し手cを選び、指し手dの評価値が指し手cより大きい場合は 先手は指し手d(=4以上が保障されている)を選ぶためである。 そうなると、後手は指し手AとBの最終的な評価値を比べたとき、 指し手Aは1が、指し手Bは4以上が確定しているので 指し手Aを選んだ方が良いことになる。
するとどうだろうか、指し手dについては評価値を計算することなく MiniMaxと同じ結果が得られるのだ。
(このように計算する必要の無い指し手を計算しない方法を「枝刈り」と呼び、 特に枝刈りする前と後で計算結果が変わらないものを「後ろ向き枝刈り」と呼ぶ。)
これをAlphaBeta法と呼ぶ。
それでは、実際のコードを見ていこう。
AlphaBeta法もMiniMaxと同じように、NegaAlpha法が存在する。
YAYAだからか分からないが深さ3程度までしか実用的な速度が出ないので 今回はNegaAlpha法を使うが、これを改良したものに NegaScoutやMTD-fなどがあるので、興味があったら調べてみると良き。
この章では、評価関数にニューラルネットワーク(=NN)を雑に使用して 局面評価の正確さを強化していく。
この章では楽をするためにPythonを使って評価関数の学習を行う。 ぶっちゃけ何をやってるかあんまり分かってない。
さっそくNNのモデルを作っていく。
各マスにどの石が置かれているか、を入力としたいので、入力層のノード数は
ノード数 = 2(手番/相手の石が置かれているか) x 64(マス目の数)
となる。 各ノードの内容は以下の通り。
| ノード | 内容 | 取りうる値 |
|---|---|---|
| 0 | 手番の石が(1, 1)に置かれているか | 0 or 1 |
| 1 | 相手の石が(1, 1)に置かれているか | 0 or 1 |
| 2 | 手番の石が(2, 1)に置かれているか | 0 or 1 |
| 3 | 相手の石が(2, 1)に置かれているか | 0 or 1 |
| ... | ... | ... |
| 126 | 手番の石が(8, 8)に置かれているか | 0 or 1 |
| 127 | 相手の石が(8, 8)に置かれているか | 0 or 1 |
隠れ層は1層で、ノード数は適当に入力層と同じ128にする。 出力層はノード数1で、出力はその局面での勝率とする。
図にするとこうなる。
(出力を64個にして、どこに打つかを出力させる形式もあるらしいが、 AIを強くしていく方法が分からないので選ばなかった。)
全結合とか活性化関数とか知らない単語が出てきたが、 筆者もよく分かってない。 とりあえず、入力層や隠れ層ではSigmoidよりReLUの方が 学習速度が下がりにくいらしいので採用して、 出力は勝率(0 < x < 1)なのでSigmoidを使っている...くらい。
強化学習のような何かで学習を行う。 現局面の評価値を、お互い最善手を指した N手先の局面の評価値に近づける手法だ。
ざっくりと、次の図のような処理を繰り替えしていくことになる。
学習部分はすべてPythonで書いて 出来上がったモデルの利用をYAYAで行うことにする。
YAYA側では、Python側で生成したmodel.txtを読み込み、 evaluateでPython側が行っているモデルの演算処理と同等の処理を行う。
Python側では、前述のとおり、大きく2つの処理に分かれている。
1つめは教師局面の生成だ。 対局を100回行い、それぞれの局面で 盤面情報+1手先の評価値をrecord.txtに書き込む。
盤面情報は、モデルの入力をそのまま出力するものとする。
初期局面で評価値が0.51だった場合は、 次のような文字列をrecord.txtに書き込む。
000000000000000000000000000000000000000000000000000000011000000000000010010000000000000000000000000000000000000000000000000000000.51
同一局面があるとその局面だけ他の局面より学習されて偏りが出るので、 uniq処理をかけてから出力を行う。
もう1つは、学習する処理だ。 record.txtを元に学習を行い、 学習したモデルをmodel.txtへ書き込む。
あとはひたすら学習を行うのみ。 数時間も学習させれば十分な強さになっていると思う。
サンプルは弄ってなんぼなので色々考えてみる。 まずは遊び方から。
Sキーで対局開始、Oキーでオプションの表示/変更。
ghost/master/reversi/_loading_order.txtを弄るとAIの変更が出来る。
dicdir, base_ai
#dicdir, improve_search
#dicdir, improve_evaluate
\end{lstlisting}
で基本的なAIを作るのAI、
dicdir, base_ai
dicdir, improve_search
#dicdir, improve_evaluate
で読みを強化するのAI、
#dicdir, base_ai
#dicdir, improve_search
dicdir, improve_evaluate
で評価関数を強化するのAIと戦うことが出来る。
基本的なAIを作る で使ったpointの値を弄ってみる。 マイナスになっている部分をプラスにしてみたり、値の大小を変えてみたり。
序盤は相手の手を限定するのが重要で、終盤は自分の石をどれだけ確保出来るかが 重要になることから、例えば40手までとそれ以降で 使う評価関数を変える。
// Note: 値は適当
C.point2 {
(100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100,/
100, 100, 100, 100, 100, 100, 100, 100)
}
OnReversiTurnBegin {
tesuu++
...
}
Reversi.AI.BaseAI.evaluate {
if tesuu <= 40 {
// C.pointを使って評価値を求める
...
}
else {
// C.point2を使って評価値を求める
...
}
}
基本的なAIを作ると 読みを強化するのAIは 毎回同じ手を指すので、勝ちの手順を1つでも覚えてしまえば 必ず勝つことが出来てしまいゲームとしては面白くない。
そこで、AIがランダムに指し手を変えるようにしてみる。 ただし、単純にランダムにすると弱くなってしまうので、 評価値のいい手は選ばれやすいようにしたい。
指し手を評価値の高い順に並べ替えて、 最初の3つの内からランダムで選ぶ、とか 評価値をもとに重みつけして乱数で指し手を選ぶ、とか。
評価関数を強化する で作ったAIのモデルは 高々数時間CPUをぶん回したもので そこまで評価値の精度が煮詰まってないと思うので、 自分で作ってみるのも一興。
Pythonをインストールしてcmdで
pip install pytorch
とすれば依存関係にあるものはインストール出来るはず。
学習用のコードはutil以下にある。
あとは
python learn.py
python record.py
python learn.py
python record.py
python learn.py
python record.py
...
のように繰り返し実行することでモデルの強化を行える。 utilフォルダにmodel.txtが生成されるはずなので、 ghost/master/model.txtに上書きすれば良い。
この文書では3つのAIを作ってきたが、 評価関数を強化するのAIにもなればまあまあ骨のあるものに仕上がっていると思う。 YAYAではこれくらいの強さが限界だと思うので、 もっと強いAIを作りたい！という人は 「bitboard」や「リバーシ パターン 評価」あたりを 調べると幸せになれるかもしれない。
というわけで、うっかりここまで読んでしまった君！ 今すぐゲーム搭載ゴーストを作る作業に入るんだ！