23 December 2016

    Project: 「三目並べ」: machinelearning

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

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

     |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|

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

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

    |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|

     座標変換用のテーブル(90度毎に4種類、左右対称、上下対照、斜め対照2種類)を用意して、ゲーム木データを検索する時にすべての座標変換を試しながら検索して対象の局面を見つけ出し、そこにある報酬データ(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]
      ]
    

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

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

    |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|  |1|2|3|
    |4|5|6|=>|4|5|6|=>|4|X|6|
    |X|8|9|  |X|8|O|  |X|8|O|

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

    局面の数

    手数 \ 局面の数 重複チェック無し 重複チェック有り 回転・対照形とゲーム終了局面を省略
    初期盤面 1 1 1
    1手目  9 9 3
    2手目  72 72 12
    3手目  504 252 38
    4手目  3,024 756 108
    5手目  15,120 1,260 153
    6手目  60,480 1,680 183
    7手目  181,440 1,260 95
    8手目  362,880 630 34
    9手目  362,880 126 0
    計  986,410 6,046 627

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

    対戦結果(学習効率)比較

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

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

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

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

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

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

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


    1. 初回起動時にゲーム木データを生成するやり方だと2分ぐらい待たされるから動的に生成するやり方にしたのですが、データを小さくすることが出来たので初回起動時にデータを作るようにしようと思ってます。 

    2. そもそも前回試しに作った「消える三目並べ」のプログラムは局面の検索に局面データは役に立たないので、指し手の手順を含めたデータを使っています。このプログラムもいずれgithubで公開するつもりです。 



    blog comments powered by Disqus