学習型三目並べプログラムの補足

　３回に渡って学習機能を持った三目並べプログラムに関する記事を書きましたが、２つの事柄について補足しておこうと思います。一つは前々回の記事で触れた多分木データに格納する局面の数をどれぐらいまで絞れるのかという点と、前回の記事で負けても罰を与えない仕様にしたことについてです。

287個の根拠は不明

マッチ箱２８７個
　各マッチ箱には、小さい引き出しがあり、開けることができる。Michieは、各マッチ箱にラベルを貼った。このラベルには、３目並べで考えられる２８７の異なる盤面が描かれている。実際はもっと多くのパターンがあることになるが、３行×３列構成の標準的な３目並べのレイアウトは上下左右を入れ替えても同じ内容なので、４つの異なるパターンを１つに集約できる。

　「STATISTICS HACKS」には上記のように書かれているので多分木データとして保持する必要がある局面の数は回転・対称形をとことん省いていけば6,046から287に絞れるのかと思って縦・横・斜めの対称形とそれぞれの局面を90度ずつ回転させた局面を省いてみても626局面までにしか絞れませんでした。どうすればいいのか見当がつかなかったのでネットで検索してみたところ「数学パズルにトドメをさす？！」と称するサイトを見つけました。そのサイトからダウンロードできる「三目並べの局面一覧」というファイルを確認してみると、すべての局面の数は447になるとのことです。私が計算した数とどこで食い違うのかを確認してみたのですが、どうやらこのデータはお互いに最善手を打つことを前提にしているようです。このサイトの注意書きに「自分や相手のリーチを見逃さない」と書いてありますが、局面を数えるときに先手・後手のお互いが最善手を選択することを前提にして（おそらくMIN−MAX法を使った深さ優先探索を使って）数えているのでしょう。

 |X|O|3|
 |X|O|6|
 |7|8|9|

　例えば上のような局面は相手のリーチ（あと一手で駒が揃う状態）を防がなかった時にしか発生しません。お互いが最善手を選択することを前提にすると、絶対現れない局面として省いているようです。
　でも機械学習プログラムの多分木データとして用意する局面データは発生し得るすべての局面を用意しておく必要があります。例えば乱数プログラムと対戦するときなどは、あと一手で一列揃うような時でも見逃すことはよくあるので、そういう時に最善手を打つことを前提にした局面しか用意していないと、まさに打つ手が無くなってしまいます。
　だから本に書いてある２８７個の局面というのは、おそらく上記サイトのように局面の先読みすることを考慮すれば２８７個にまで省略出来るということだと思います。上記サイトでは特に局面の数を減らすことを目的にしていないと思いますが、探せば「ここまで局面が進行すれば、相手がどう応じても引き分けに持ち込める」という感じの局面が相当数存在するのだと思います。例えば「自分がダブルリーチをかけたら勝ちが確定する」からそれ以後の局面は用意しなくてもいいというのも一つの例として挙げることができます。そういった手法で先読みを考慮してとことん局面を絞ればまだまだ省略可能な局面が存在するということでしょう。でも、そこまで考慮して事前に用意する局面を絞って学習プログラムを作ると前述したように指し手が選択できないケースが生じてしまいます。「STATISTICS HACKS」に例え話で書かれているように、無人島で人間が判断して局面を省略する分には問題ありませんが…。
　と、いうことで苦労して多分木データに格納する局面数を絞っても学習プログラムには使えないので追求するのはここまでにしました。この本は結構根拠を示さずに結論を書いているところがあるので、２８７という数字が、ちゃんと裏を取った根拠のある数字じゃない可能性もありますが私には何とも言えません。
　根拠がある数字と言えば、以前の記事で、３手目までを重みによる評価関数を使いそれ以降はDFSによる読み切り関数を使ったことを書きましたが、３手目までなら重みによる評価関数を使用しても負けないことを確認したからそうしたわけですが、４手目まで重みによる評価関数を使えば負けてしまうことがあるが、３手目までなら負けないようにすることが出来ることを、根拠を示して証明するのは結構大変です。件の本も、いちいち根拠を示していたら紙面が足りなくなるという事情があるのかもしれません。たかが三目並べでも突き詰めていくと奥が深いということでしょう。
　件のサイトでは「３目並べず¹」のデータとして最善手を選択することを前提としていないデータも用意してあって、そのファイルでは私が数えた626に近い数になっています（以下に比較表を用意しました）。でも私が数えたときの前提条件は「既に勝負がついた局面は省く」というものなので、微妙に数値が異なっています。私は機械学習プログラムで使用する多分木データに必要なデータということで考えているので、例えば９箇所すべてが埋まっている局面のデータはすでに勝ちか負けか引き分けかの勝負がついた局面なので、必要がないため９手目の局面は０になっています。

三目並べのすべての局面データ（ X が先手、回転・対称形は同一局面と見做して除く）

信賞必罰が基本だけど、目的を間違えてはいけない

　前回の記事で石の数が足りなくなるのを防ぐために負けても罰を与えない（石を減らさない）仕様にしたところで終わりました（勝ちが＋３、引き分けが＋１、負けが±０）が、やはりこれはよくないと思い直しました。

 |X|X|3|
 |4|O|6|
 |7|8|9|

　例えば上記の局面で O の手番だとすると、負けないためには”3”の場所に打つしかありません。この局面のscore配列は以下のように”3”の場所以外は 0 になっている状態が理想です²。

　でも負けても石を減らさない仕様だと、初期値でセットした石は永遠に残り続けるので理想の状態には絶対になりません。長い期間学習が強化され続けて、最善手（相手の石が揃うのを防ぐ手）を選ぶ確率がどんどん高くなっていっても石が残っている限り絶対１００％にはならないわけで、これは良くないと考えたわけです。
　しかし、よくよく考えてみると「この局面ではこの一手」というような手を指させたいのならその局面のscore配列を最初から上記のようにセットしておけばよい話で、なぜ学習させる必要があるのだろうという話になってきます。多分木データを生成する段階で、「次の一手で相手が石を揃えることが出来る」局面ではその箇所だけ１以上の値をセットしてそれ以外の箇所は０をセットしておけばいい話です。
　「STATISTICS HACKS」には以下のように書かれています。

　明確な改善は、間違った手を許さないことで、コンピュータを賢くする。つまり、ココナッツの中に、すぐに負けにつながるような小石を入れないことだ。この方法は、使用開始当初のコンピュータの弱さを改善できるが、実際は動物の学習方法を反映していない。よって、この方法で強い対戦相手が生まれても、教授は、このコンピュータの開発者が科学的な精密さを欠くことに失望するだろう。

　つまり、予め打たせたい手の場所にだけ小石（score配列）をセットしておくことは、いくらプログラムが強くなるとしても「学習プログラム」としての意味がなくなるということだと思います。プログラムを強くしたいだけなら「次の一手で相手の石が揃う」局面の他にも「次の一手で自分がラインを揃えることが出来る」局面ではそこしか選ばないように小石をセットしておけばいいし、先読み機能を付加して「ダブルリーチを狙える局面」では必ずその手を選ぶように小石をセットする方法も考えられます。でもこれらの方法は学習機能が無いプログラムがやっていることと同じで、本末転倒になっています。こういう方法は将棋プログラムで言えば定跡データを登録する作業に似ていると思います。学習しながら定跡データを更新してるからこそ「学習プログラム」と言えるわけで、予め定跡データをセットしておいて変更しないのなら「学習プログラム」とは言えません。

　ということで、とりあえず負けたら石を一つ減らして、もし減らすべき石が足りなくなったらその都度石を補充する仕様に変更しました。補充するときは足りなくなった箇所の石だけでなく９箇所全てに同数（１０個）ずつ補充します。そうしないと１箇所だけ補充してしまうと勝った時の報酬を受け取った形になってしまうので当然こうすべきところです。

　前回同様に最強プログラムと乱数プログラムとそれぞれ１０万回ずつ対局させた結果も前回の結果よりよくなったのでとりあえずこれで良しとします³。足りなくなれば小石を補充する仕様なので、結局いつまで経っても最初に言った理想の状態にはならないわけですが、前述の通り「学習プログラム」としてはこれで良しってことです。

まとめ

　三目並べの「学習プログラム」を強くしようとすればするほど、本末転倒な作業に帰結してしまうのは、ひとえに三目並べというゲームが既に正解がわかってしまっているゲームだからだと思います。一般に機械学習機能を使って学習させたいものは未知のものであるからこそプログラムに学習させて何らかの答えを導き出したいわけで、既に答えがわかっているのならそれを選ばせればいいだけです。だから三目並べの機械学習プログラムの題材としての役割は、かなり限定的だということでしょう。
　ということで次作るとすれば「オセロ」か「ミニ将棋」辺りを対象にして機械学習プログラムを作ってみようと思います。将棋であれば学習すべき特徴量（「玉の固さ」、「駒の働き」、「駒の損得」等）も多いので三目並べより工夫しがいがありそうですし、三目並べでもまだまだ学習効果を上げる工夫の余地があるのは分かっていますが、完全読み切りが可能なゲームだとやり甲斐もあまりありませんので実験はもう充分って感じです。
　でも、何かを試すときにその前段階としてまたこの三目並べプログラムを弄ることがあるかもしれません。そうしているうちにこの三目並べプログラムが「三目並べ」の新たな特徴量を発見することは無いと思いますが…。