25 October 2015

    新たに必要になった機能

     前回の続きです。「STATISTICS HACKS」の内容に沿って機械学習機能を付加した三目並べプログラムを作成したのですが、元々あった三目並べ対戦プログラムに対してどんな作業が必要だったのか、新たに付加した機能を列挙してみます。

    • 多分木データ(Player.trees)
       前回の記事で用意した全局面分のデータです。学習データを利用して手を決めることになるので評価関数は不要になりました。
    • 学習機能(Player.learning)
       勝った時は報酬を与えて(石の数を増やす)負けたら罰を与える(石の数を減らす)ことで学習効果を上げていくわけですが、「STATISTICS HACKS」には勝ちと引き分けに差をつけて、勝ちは+3、引き分けは+1がいいと書いてありますのでその通りにしています。そして、そこには負けた場合どうすればいいのか書いてありませんが、負けたら石を海に投げ込むという描写もあるので−1でいいだろうと思い負けは−1にしています。もしかしたら±0でいいのかもしれませんし、逆に負けを−3にする方法もありそうですがこの辺りは評価関数の調整と同じでキリがないのでとりあえずの値です。
       それと、実際に着手した局面の一手前の石の数(score配列)を操作するということに注意が必要です。
      例1
       各局面が持っている石の数(score配列)はその局面で打てる場所に存在し次の手を決めるためにあるので、ソフト側が先手(X)で上記のような経過を辿って負けた場合、5手目の局面でOが揃うのを防がなかったのが悪かったということで、一つ前の4手目の局面の石(score配列)を−1します。4手目の局面で先手(X)が”2”(配列の添え字は1)を選ばずに”6”を選んだことが負けの原因なので”6”の位置のscore配列の値を−1します。score配列の初期値は[10,10,10,10,10,10,10,10,10]なので、4手目の局面のscore配列を[10,10,10,10,10,9,10,10,10]にするということです。同様に2手目で”7”を選んだことが悪かった、0手目(初期盤面)で”5”を選んだことが悪かったと評価して2手目のscore配列を[10,10,10,10,10,10,9,10,10]、0手目のscore配列を[10,10,10,10,9,10,10,10,10]にして次回からその局面でその手が選ばれにくくなるようにします。
    • ファイル入出力機能(Player.prepare、Tree::read、Tree::save)
       前回の記事のスクリプトの例でinitメソッドとしていましたが、他でも使用しているのでprepareメソッドに名前を変えました。起動時にTreeオブジェクトのシリアライズデータ(trees.dump)がカレントディレクトリにあればそれを読み込み、無ければBFS探索で重複局面を省いた三目並べの全局面のツリーデータを生成します。オブジェクト指向言語には必ず用意されているシリアライズ機能はオブジェクトを丸ごと保存できるので便利です。
    • 指し手選択機能(Tree.apply)
       指定された局面を探し出して、その局面で選択可能な手毎に用意されている石ころの数(score配列の値)によって指し手を選ぶわけですが、いつも一番石ころが多い手を選ぶわけではありません。
       「その箇所にある石の数(score配列の値)/その局面の石の総数(score配列の合計値)」
      の頻度で指し手が選ばれるようにします。石ころの数が増えればその手が選ばれる頻度が上がる仕掛けです。
    • 指し手の履歴(Game.history)
       ゲーム終了後に指し手の評価をするために必要になりました。
    • 直近の指し手(Board.move)
       これもゲーム終了後に指し手の評価をするために必要になりました。

    指し手選択機能について

     指し手の選択機能は、指し手を無作為に選択するわけですが、石ころの報酬を受け取る(score配列の値が増加)ことによって学習し、徐々に良い手(score配列の数値が大きい手)を選択する確率を上げていくという仕様です。石ころの総数から乱数を生成して、その値から指し手(9箇所のマス目)の配列の添え字をダイレクトに導くデータ構造はどうすればいいのか、そして選んだ添え字の場所が打てる場所なのかどうかも判断しなければなりません。

      def idx(score)
        ret = nil
        index = rand(score.inject{|sum, n| sum + n})
        start = 0
        score.each_with_index{|v, i|
          start += v
          if start > index
            ret = i
            break
          end
        }
        return ret
      end
    

     最初は9箇所にそれぞれ石を持っているのだから2次元配列を使うのかとかMatrixを使えば変換できるかとか難しく考えたのですが、一番シンプルな一次元配列のまま、コンストラクタで打てる場所かどうか(打てない場所は0をセットしておく)を判断し、指し手選択時にscore配列分の9回ループするだけで添え字を求められることに気がついてこれはいい!と思いました。9箇所のマス目の内、打てない場所(既に駒がある場所)のscore配列の値を0にしておくことで、インクリメントに影響を与えないのがミソです。だから石の数(score配列)がマイナスになると動きがおかしくなります。

    学習効果

     以前RubyとShoesでGUIの将棋ソフトを作った時はObserverパターンを使ってソフト同士の対戦を眺めて楽しめるように作った1のですが、三目並べは一瞬で勝負がつくし見学しても楽しくないのでCUIでループで回してソフト同士対戦させて学習効果がどの程度出るのか確認してみました。
     乱数で手を選択する弱いプログラムと、これまでに記事で紹介していたDFS探索アルゴリズム(αβ法)を使った最強プログラム(絶対負けることがない)との対戦結果です。100回の対戦を1回として10回戦までの結果が以下の通りです。

    回 \ 対戦相手  最強プログラム    乱数プログラム  
    1回戦  0勝91敗 9分 42勝44敗14分
    2回戦  0勝88敗12分 51勝35敗14分
    3回戦  0勝83敗17分 41勝42敗17分
    4回戦  0勝74敗26分 41勝49敗10分
    5回戦  0勝62敗38分 44勝49敗 7分
    6回戦  0勝60敗40分 51勝41敗 8分
    7回戦  36勝53敗11分
    8回戦  44勝42敗14分
    9回戦  42勝40敗18分
    10回戦  48勝43敗 9分

     まず表の右側の乱数プログラムとの対戦結果を見ると、それほど勝率は上がってなさそうですが、上記1000回の対戦後に初期盤面のscore配列の値を確認すると

    [94, 32, 137, 98, 160, 95, 98, 84, 97]

    になっていました。9箇所のマス目の真ん中の値が160と最大になっていて、初期盤面で真ん中を選べば有利なことを学習しているように見えます。それでも勝率が伸びていないのは弱い相手と戦ってもあまり学習効果が得られないということでしょうか?
     それに対して左側の最強プログラムとの対戦ではどんどん負け数が減って強くなっている(三目並べはお互いに最善手を差し続ければ引き分けになるゲームなので、最強プログラムに対して0勝なのは仕方ありません)のがわかります。でも6回戦の途中から出現頻度の高い局面の石の数(score配列の値)が足りなくなっていたようで、動きがおかしくなったので中断しました。
     石の初期値が10個で足りなくなるのなら増やせばいいじゃないかという話ですが、石の数を増やすと分母が大きくなるわけですから学習効果が薄くなります。初期値を10個にしていたからこそ早く学習効果が出たとも言えるわけなので、この辺りはどうするのが一番いいのかわからなかったのですが、これについては後で書きます。
     ちなみに石の数(score配列)のどれかが0になるのがよくないわけではありません。[0,0,200,0,0,0,0,0,0]のような一箇所に石が集中した状態でも、その局面で唯一絶対の手だと学習したということなので問題ありません。極端な話、一箇所だけに一個しか石がない状態[0,0,1,0,0,0,0,0,0]でもそれが学習した結果であればいいのですが、すべてが0だと手の選びようがなくなるのでよくありません。
     とりあえずTreeクラスのコンストラクタに石の個数の引数を加えて、出現頻度が高い局面(初期盤面と一手目の局面)だけは石の初期値を50にして、石が足りなくならないようにして、学習データを削除(trees.dumpファイルを削除)してからあらためて今度は2000回対戦させてみました。

    回 \ 対戦相手  最強プログラム    乱数プログラム  
    1回戦  0勝88敗12分 41勝50敗9分
    2回戦  0勝86敗14分 44勝44敗12分
    3回戦  0勝90敗10分 42勝40敗18分
    4回戦  0勝83敗17分 40勝38敗22分
    5回戦  0勝87敗13分 42勝43敗15分
    6回戦  0勝89敗11分 47勝41敗12分
    7回戦  0勝81敗19分 47勝46敗7分
    8回戦  0勝79敗21分 45勝42敗13分
    9回戦  0勝88敗17分 45勝45敗10分
    10回戦  0勝75敗25分 45勝44敗11分
    11回戦  0勝68敗32分 42勝45敗13分
    12回戦  0勝64敗36分 41勝45敗14分
    13回戦  0勝70敗30分 51勝37敗12分
    14回戦  0勝64敗36分 49勝45敗6分
    15回戦  0勝68敗32分 51勝30敗19分
    16回戦  0勝70敗30分 41勝50敗9分
    17回戦  0勝54敗46分 42勝41敗17分
    18回戦  0勝63敗37分 53勝41敗6分
    19回戦  0勝57敗43分 41勝44敗15分
    20回戦  0勝55敗45分 50勝34敗16分

     最強プログラムとの対戦ではやはり良好な学習効果が得られているように見えます。
    ちなみにこの2000回対戦後の初期盤面の石の数(score配列の値)は、乱数プログラムの方は

    [282, 135, 219, 252, 357, 132, 270, 96, 277]

    で、やはり真ん中が最大値になっていました。
     最強プログラムの方は

    [14, 165, 8, 22, 81, 20, 5, 92, 1]

    で真ん中は3番目で、なぜか上辺(2の位置)が一番大きな値になっていたのですが、理由はよくわかりません。

    最後に

     石が無くならないようにするために、出現頻度の高い初期盤面(1局面)と一手目の局面(9局面)の石の数を50にしたわけですが、50という値には根拠がないですし、なんとなくすっきりしないので、負けたら−1という仕様を変更して、の主張とは少し違ってきますが、負けても罰しない仕様(勝ちは+3、引き分けは+1、負けたら±0)で試してみました。これなら石が無くなる心配もないしマジックナンバーが減ります。初期値は一応10で試しましたが、石が無くなる心配がないので1以上ならなんでもいいと思います。デスクトップPCで一晩かけて10万回対戦させてみました(もちろんtrees.dumpファイルを削除してから開始しています)。

    項目 \ 対戦相手  最強プログラム    乱数プログラム  
    対戦成績  0勝18,234敗81,766分 58,971勝30,103敗10,926分
    初期盤面の石の数 [537, 27512, 55, 4045, 9444, 297, 50, 3927, 37] [10779, 2666, 16245, 11403, 22578, 7644, 25519, 6646, 5529]

     最強プログラムとの対戦成績は8割以上引き分けるようになりました。負けを−1しなくても学習効果は今までのプログラムと同様の効果が出ているように見えます。乱数プログラムとの対戦成績も6割近くに伸びているのでもっと回数を増やせばいいのかもしれません。
     学習機能の説明のところで勝負に負けたからといって一律に全ての局面から減点(石を減らす)していくという仕様に違和感を感じた人もいると思いますが、私もに書いていたから最初はそうしてみたけど勝負に負けたからといって初手にどれほどの影響力があるのか疑問です。その意味でも負けた時は±0というのは理にかなっていると思います。但し、直接負けに繋がった一手は罰するべきかもしれません。にも序盤より終盤の手を重視する方法が紹介されています。まだまだ学習効果を上げる方法も学習機能の仕様を変える余地も大きく、検証方法もいろいろ考えられるので、また何かアイデアを思いつけばこのプログラムを使って記事を書くかもしれません。
     今回のソースは別ブランチ(machinelearning)を作りました。以下のコマンドでブランチ指定してソースを取得することが出来ます。

    git clone -b machinelearning https://github.com/happyclam/tictactoe_ruby
    

    1. 本来の使い方とは違うかもしれませんが、一方が一手指したらその通知を受け取ってもう一方が一手指すというような作りにしていました。またもう一箇所、双方が手を指した通知を受け取って棋譜を更新する部分もObserverを使用していました、これは本来の使い方と言えるでしょう。一つのプログラムで2種類のオブザーバーが問題なく動きました。 



    blog comments powered by Disqus