新たに必要になった機能

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

• 多分木データ（Player.trees）
  　前回の記事で用意した全局面分のデータです。学習データを利用して手を決めることになるので評価関数は不要になりました。
• 学習機能（Player.learning）
  　勝った時は報酬を与えて（石の数を増やす）負けたら罰を与える（石の数を減らす）ことで学習効果を上げていくわけですが、「STATISTICS HACKS」には勝ちと引き分けに差をつけて、勝ちは＋３、引き分けは＋１がいいと書いてありますのでその通りにしています。そして、そこには負けた場合どうすればいいのか書いてありませんが、負けたら石を海に投げ込むという描写もあるので−１でいいだろうと思い負けは−１にしています。もしかしたら±０でいいのかもしれませんし、逆に負けを−３にする方法もありそうですがこの辺りは評価関数の調整と同じでキリがないのでとりあえずの値です。
  　それと、実際に着手した局面の一手前の石の数（score配列）を操作するということに注意が必要です。
  
  　各局面が持っている石の数（score配列）はその局面で打てる場所に存在し次の手を決めるためにあるので、ソフト側が先手（X）で上記のような経過を辿って負けた場合、５手目の局面でOが揃うのを防がなかったのが悪かったということで、一つ前の４手目の局面の石（score配列）を−１します。４手目の局面で先手（X）が”2”（配列の添え字は1）を選ばずに”6”を選んだことが負けの原因なので”6”の位置のscore配列の値を−１します。score配列の初期値は[10,10,10,10,10,10,10,10,10]なので、４手目の局面のscore配列を[10,10,10,10,10,9,10,10,10]にするということです。同様に２手目で”7”を選んだことが悪かった、０手目（初期盤面）で”5”を選んだことが悪かったと評価して２手目のscore配列を[10,10,10,10,10,10,9,10,10]、０手目の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配列の数値が大きい手）を選択する確率を上げていくという仕様です。石ころの総数から乱数を生成して、その値から指し手（９箇所のマス目）の配列の添え字をダイレクトに導くデータ構造はどうすればいいのか、そして選んだ添え字の場所が打てる場所なのかどうかも判断しなければなりません。

  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

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

学習効果

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

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

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

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

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

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

最後に

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

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

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