Project: 「三目並べ」: machinelearning

ゲーム木から回転、対照形を間引く

　以前から懸案だったプログラム内に保持している局面データの省略をやってみました。この件については以前から何度か記事を書いています（「対戦型ソフトでの幅優先探索（BFS）の使い途」、「強化学習の修正」）が面倒そうなので放置してたのですが、手を付け始めたら案外すぐに出来ましたと言うのも勝ったら報酬を与えて負けたら罰するという強化学習の部分がうまく機能するのか心配だったので放置していたのですが、とりあえず作ってテストしてみると報酬の与え方の部分は変更せずに局面データの変換だけでうまく機能しているようです。

 |X|2|3| |1|X|3| |1|2|X| |1|2|3| |1|2|3| |1|2|3| |1|2|3| |1|2|3| |1|2|3|

 |4|5|6| |4|5|6| |4|5|6| |X|5|6| |4|X|6| |4|5|X| |4|5|6| |4|5|6| |4|5|6|

 |7|8|9| |7|8|9| |7|8|9| |7|8|9| |7|8|9| |7|8|9| |X|8|9| |7|X|9| |7|8|X|

　一手目の局面に関して言うと、今までゲーム木データ内に１手目の局面は上のように９種類保持していたのを、回転・対照形を省いて以下の３局面だけ保持するようになっています。

プログラム内に保持している１手目の全局面データ


 |X|2|3| |1|X|3| |1|2|3|

 |4|5|6| |4|5|6| |4|X|6|

 |7|8|9| |7|8|9| |7|8|9|

 

　座標変換用のテーブル（９０度毎に４種類、左右対称、上下対照、斜め対照２種類）を用意して、ゲーム木データを検索する時にすべての座標変換を試しながら検索して対象の局面を見つけ出し、そこにある報酬データ（score配列）を使って指し手を決め、実際の盤面の座標に変換して駒（×、○）を打ちます。ゲーム終了後には実際の局面からゲーム木データが保持している局面に座標変換して報酬データを書き込むようにします。

class Board < Array
  @@restore_table = [0, 3, 2, 1, 4, 5, 6, 7]
  @@rotate_sym = [
    [0, 1, 2, 3, 4, 5, 6, 7, 8],
    [2, 5, 8, 1, 4, 7, 0, 3, 6],
    [8, 7, 6, 5, 4, 3, 2, 1, 0],
    [6, 3, 0, 7, 4, 1, 8, 5, 2],
    [2, 1, 0, 5, 4, 3, 8, 7, 6],
    [6, 7, 8, 3, 4, 5, 0, 1, 2],
    [0, 3, 6, 1, 4, 7, 2, 5, 8],
    [8, 5, 2, 7, 4, 1, 6, 3, 0]
  ]

　例えば２手目の局面は以下の１２種類しか保持していませんが

プログラム内に保持している２手目の全局面データ


 |X|O|3| |X|2|O| |X|2|3| |X|2|3| |X|2|3| |O|X|3| |1|X|3| |1|X|3| |1|X|3| |1|X|3| |O|2|3| |1|O|3|

 |4|5|6| |4|5|6| |4|O|6| |4|5|O| |4|5|6| |4|5|6| |O|5|6| |4|O|6| |4|5|6| |4|5|6| |4|X|6| |4|X|6|

 |7|8|9| |7|8|9| |7|8|9| |7|8|9| |7|8|O| |7|8|9| |7|8|9| |7|8|9| |O|8|9| |7|O|9| |7|8|9| |7|8|9|

　ゲームが以下のように進行した場合、

 １手目　　　２手目　　３手目 

 |1|2|3|  |1|2|3|  |1|2|3|

 |4|5|6|=>|4|5|6|=>|4|X|6|

 |X|8|9|  |X|8|O|  |X|8|O|

１手目は実際の局面を右に９０度回転させた局面として見つけ出すことが出来、２手目は上下反転したもの、３手目はまた別の変換というように、一手毎に座標変換の仕方が異なるわけですが、一つの局面データに対して一つしか持ってない報酬データ（score配列）に対して加算（報酬）、減算（罰）していけば問題なく強化学習が進みます。

局面の数

　今回の改良で回転・対照形の局面は同一局面としてプログラム内に一つしか保持しないようにしたのと同時に、マス目が全て埋まっている局面や、既に勝ち負けが決まっている局面もゲーム木データから除いています。一番右の欄の９手目の局面が０になっているのはそのため（既に勝敗が決まっているから）です。
　ゲーム木データを格納したファイル（trees.dump）のサイズは50Kバイト程度で今までの１０分の１以下になりました。リリース中のandroidアプリにも反映させようと思っているのですが、現行バージョンに採用しているゲーム木を動的に生成する方法¹と今回の方法を併用するのは難しいのでデータの互換性は無くなりそうです。

対戦結果（学習効率）比較

　従来のプログラムと今回修正したもので改めてデータを取り直して、学習の進捗度をグラフにしてみました。回転・対照形をゲーム木から除いた点以外はまったく同じプログラムで比較しています。

– 最強プログラムとの対戦結果 –

　三目並べの特性上、完全読み切りを行っている最強プログラムに勝つことは出来ませんが、変更前のプログラムより何割か増しで引分に持ち込む頻度が上がり、学習の速度が上がっていることがわかります。

– 乱数プログラムとの対戦結果 –

　乱数で指し手を決める弱いプログラム相手でも、今までより対戦回数が少ない段階で勝率が上がっていることがわかります。

「消える三目並べ」に応用出来るか？

　前回の記事で「消える三目並べ」（３手前に打った自分の駒が消えるルールの三目並べ）はデータ量が増えすぎて、強化学習型のスマホアプリにするのは難しいと書きました。そこで今回の方法で回転・対照形を省けば保持する局面データ量が減って問題解決に繋がるかといえば残念ながらそうはいきません。これも以前書きましたが「消える三目並べ」は局面（と手番）だけでは最善手が決まりません。将棋、オセロ、囲碁など多くのテーブルゲームは局面と手番が決まれば最善手を決めることが出来ますが、「消える三目並べ」はその局面に至った経過が大事（順列データ）なので単純に今回のように局面データを省略しても駄目そうです²。通常の配列データではなくもっと物理的に小さなデータ（ビットパターン）で局面を保持するしかないかなと考えてますが、これについてはもう少し模索しようと思います。「どうぶつしょうぎ」を完全解析したプログラムは一つの局面を整数データとして（ビットパターンで）保持していたそうですが、有名な将棋ソフトなどもソースコードを追ったことは無いのですが、すべてそうやっているのでしょう。
　と、この記事を書いている最中にlibshogiというビットパターンで将棋盤を生成するライブラリがあることをTwitterで知りました。こういうライブラリの三目並べ用があればいいのですが、有るわけないですね