HACKS」の内容に沿って機械学習機能を付加した三目並べプログラムを作成したのですが、元々あった三目並べ対戦プログラムに対してどんな作業が必要だったのか、新たに付加した機能を列挙してみます。木データ(Player.trees)前回の記事で用意した全局面分のデータです。学習データを利用して手を決めることになるので評価関数は不要になりました。HACKS」には勝ちと引き分けに差をつけて、勝ちは+3、引き分けは+1がいいと書いてありますのでその通りにしています。そこには負けた場合どうすればいいのか書いてありませんが、負けたら石を海に投げ込むという描写もあるので−1でいいだろうと思い負けは−1にしています。したら±0でいいのかもしれませんし、逆に負けを−3にする方法もありそうですがこの辺りは評価関数の調整と同じでキリがないのでとりあえずの値です。それと、実際に着手した局面の一手前の石の数(score配列)を操作するということに注意が必要です。各局面が持っている石の数(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箇所のマス目)の配列の添え字をダイレクトに導くデータ構造はどうすればいいのか、そして選んだ添え字の場所が打てる場所なのかどうかも判断しなければなりません。end最初は9箇所にそれぞれ石を持っているのだから2次元配列を使うのかとかMatrixを使えば変換できるかとか難しく考えたのですが、一番シンプルな一次元配列のまま、コンストラクタで打てる場所かどうか(打てない場所は0をセットしておく)を判断し、指し手選択時にscore配列分の9回ループするだけで添え字を求められることに気がついてこれはいい!と思いました。9箇所のマス目の内、打てない場所(既に駒がある場所)のscore配列の値を0にしておくことで、インクリメントに影響を与えないのがミソです。石の数(score配列)がマイナスになると動きがおかしくなります。以前RubyとShoesでGUIの将棋ソフトを作った時はObserverパターンを使ってソフト同士の対戦を眺めて楽しめるように作った1のですが、三目並べは一瞬で勝負がつくし見学しても楽しくないのでCUIでループで回してソフト同士対戦させて学習効果がどの程度出るのか確認してみました。乱数で手を選択する弱いプログラムと、これまでに記事で紹介していたDFS探索アルゴリズム(αβ法)を使った最強プログラム(絶対負けることがない)との対戦結果です。100回の対戦を1回として10回戦までの結果が以下の通りです。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回対戦させてみました。最強プログラムとの対戦ではやはり良好な学習効果が得られているように見えます。277]で、やはり真ん中が最大値になっていました。1]で真ん中は3番目で、なぜか上辺(2の位置)が一番大きな値になっていたのですが、理由はよくわかりません。最後に石が無くならないようにするために、出現頻度の高い初期盤面(1局面)と一手目の局面(9局面)の石の数を50にしたわけですが、50という値には根拠がないですし、なんとなくすっきりしないので、負けたら−1という仕様を変更して、本の主張とは少し違ってきますが、負けても罰しない仕様(勝ちは+3、引き分けは+1、負けたら±0)で試してみました。これなら石が無くなる心配もないしマジックナンバーが減ります。初期値は一応10で試しましたが、石が無くなる心配がないので1以上ならなんでもいいと思います。デスクトップPCで一晩かけて10万回対戦させてみました(もちろんtrees.dumpファイルを削除してから開始しています)。5529]最強プログラムとの対戦成績は8割以上引き分けるようになりました。負けを−1しなくても学習効果は今までのプログラムと同様の効果が出ているように見えます。乱数プログラムとの対戦成績も6割近くに伸びているのでもっと回数を増やせばいいのかもしれません。学習機能の説明のところで勝負に負けたからといって一律に全ての局面から減点(石を減らす)していくという仕様に違和感を感じた人もいると思いますが、私も本に書いていたから最初はそうしてみたけど勝負に負けたからといって初手にどれほどの影響力があるのか疑問です。その意味でも負けた時は±0というのは理にかなっていると思います。負けに繋がった一手は罰するべきかもしれません。本にも序盤より終盤の手を重視する方法が紹介されています。学習効果を上げる方法も学習機能の仕様を変える余地も大きく、検証方法もいろいろ考えられるので、また何かアイデアを思いつけばこのプログラムを使って記事を書くかもしれません。今回のソースは別ブランチ(machinelearning)を作りました。以下のコマンドでブランチ指定してソースを取得することが出来ます。https://github.com/happyclam/tictactoe_ruby本来の使い方とは違うかもしれませんが、一方が一手指したらその通知を受け取ってもう一方が一手指すというような作りにしていました。一箇所、双方が手を指した通知を受け取って棋譜を更新する部分もObserverを使用していました、これは本来の使い方と言えるでしょう。一つのプログラムで2種類のオブザーバーが問題なく動きました。