乱数プログラムとの対戦テスト結果は良好だったけど

　前回の記事で「消える三目並べ」（３手前に打った自分の駒が消えるルールの三目並べ）なら保持する局面の数（ゲーム木）を通常の三目並べより少なく出来るなんて書いてしまいましたが、「消える三目並べ」では局面のデータだけを記憶していても次にどの駒が消えるかによって最善手が違ってくるので通常の三目並べのように局面の組み合わせだけで学習させることは出来ないことに気づきました。
　あまり深く考えずに「消える三目並べ」のルールをプログラムに反映させて、学習機能の部分は変更せずに乱数プログラムとの対戦テストをしたところ、最初は２０％程だった勝率が徐々に上がり、10,000回対戦後の最後の１００回の対戦は勝率６０％以上に上がったので、これだけの修正でいいのか？と疑問に思いながらも、前回の記事を書いてしまいました。「進化する三目並べ（Tic-tac-toe Evo）」でも、最強プログラムとの対戦では急速に学習が進みますが、乱数プログラムとの対戦では学習効果が低いため10,000回対戦後でも勝率が６０％程度でしたので、同じ結果が得られたと早合点してしまいました。
　でも「消える三目並べ」の最強プログラム¹を作って対戦テストをしてみたところ²、学習機能を変更しないままでは、全く勝てるようになりませんでした。以前の記事³でも書いたように「消える三目並べ」は先手必勝なので少なくともAI側⁴が先手の時は勝てるようにならなければおかしいはずなのに、５千回程対戦させても１回も勝てません。とりあえず最強の「消える三目並べ」プログラムに先手の時はある程度勝てるようにならなければ「進化する」とは言えないでしょう。
　では、なぜ乱数プログラムとの対戦テストでは勝率が上がっていったのか？乱数プログラムはまったく出鱈目に指し手を決めるので、ラインを揃えようとさえしないので、少なくとも現在の局面だけを見て（例え次にどの駒が消えるかまでは考慮していないにしても）ラインを揃えれば報酬がもらえることを学習したプログラムの方が勝率が上がっていくのは当たり前ということでしょう。してみると、乱数プログラムとの対戦テストなんて学習効果を図るためには不要なテストなのかもしれません。テスト結果が良好だったので、簡単な修正で済んだことに驚きながらも「思ったより楽勝だな」なんて思ってました。しかし、このままのプログラムでは、人間や最強プログラムを相手にした場合はまったく学習効果が感じられない偽AIプログラムと言われそうです。
　一応スマホにインストールして自分で数百回対戦してみましたが「消える三目並べ」自体あまりやったことがなく特に強いわけでもない自分にとっては、強くなってるのかどうかわからないというのが正直な感想ですが、少なくともデータ上で強くなることを確認する必要があるでしょう。

組み合わせではなく、順列

　冷静に考えれば当たり前なんですが、「消える三目並べ」では通常の三目並べと違い６手目以降は駒が消えていくので現在の局面（９箇所の配置）を見ただけでは最善手の判断が付きません。オセロや将棋では現局面の駒の配置と手番がわかればその局面での最善手は判断できるはずです⁵が、「消える三目並べ」では自分が新たに着手する際にどの駒が消えるのかを知っていなければ判断できません。「消える三目並べ」のルールをプログラムに反映した段階で当然指し手の手順は記憶しているのですが、学習データを保存するためのゲーム木データにも記憶しておく必要があるということです。つまり、局面の組み合わせの数ではなく、順列の数の分だけ局面データを保持する必要があります。

　上の表で手順を含めた局面データをゲーム木に含めないといけないので、前回の記事にゲーム木に必要なデータ数は左の列の4,030で済むようなことを書きましたが、正しくは右の列の合計79,210個の局面データを記憶しておく必要があります。通常の三目並べと違い、局面の重複チェックは必要ないというか、重複チェックをしてはいけなかったわけです。同じ局面でもどういう経緯でその局面に至ったかによって最善手が変わるのですから。

手数が増えてもデータは増えない

　上の図は、手数がいくら増えたとしても６手目以降の局面は、６手目の局面60,480種類の中に手順が違う局面として必ず含まれていることを示しています。プログラムとの対戦テストでは手数は２０手を超えることもあるのですが、一局面に存在する駒の数は最大６個（×が３つ、○が３つ）までなのでいくら手数が増えてもデータが無制限に増える心配がないことは前回の記事に書いた通りですが、アプリを作る場合思っていたより大幅にデータ量が増えてしまうことになりそうです。
　試しにゲーム木データをPCで作成したところ12MB程度になりました。画像をいっぱい使用する昨今のアプリに比べればそれ程でもないかもしれませんが、現在の「進化する三目並べ（Tic-tac-toe Evo）」の1MB程度に較べて大幅増量になりそうです。androidアプリもiosアプリも100MBまで大丈夫なようなので、サイズ的には問題ないのですが、スマホ標準のブラウザ（WebView）内のデータ制限（androidは2MB、iosは5MB）を超えるのでアプリの作りを変える必要がありそうです。自分としてはこれが一番面倒くさい、今までMacbookでブラウザ上で開発出来ていたのに、パワーの有るPCで実機やエミュレータを使いながらの開発作業が必要になりそうです。
　また、データ量の問題はどうにかなるにしても、６手目以降の局面を検索する場合、上の図の限定した範囲のゲーム木に含まれているとはいっても、今までのように単純にツリーを辿るだけでは駄目で、６手目以降に関してはツリーのルートから再検索しなければいけませんし、上の図の６手目の局面の手番はすべて同じ先手番になっています（×○×○×○で次は先手の×の手番）が、実際には後手の手番で上の図の６手目の局面を迎えることもあるので、対戦結果を学習データとして格納する時の処理が複雑で煩わしい処理になりそうです。それにAIの学習が進んでいるかどうかの指標（どれだけ進化したか現在イラストで表示している機能）をどうやって実現するかも現在手探り中です。
　乗りかかった船なので何とかリリースまで漕ぎ着けたいと思ってますが、思っていたより時間かかりそうです。