03 November 2016

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

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

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

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

    手数 \ 重複チェック  有り    無し  
    初期盤面 1 1
    1手目  9 9
    2手目  72 72
    3手目  252 504
    4手目  756 3,024
    5手目  1,260 15,120
    6手目  1,680 60,480
    7手目  0 -
    8手目  0 -
    9手目  0 -
    計  4,030 79,210

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

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

    消える三目並べゲーム木

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


    1. ここで言う最強プログラムとは従来のMIN-MAX法(αβ法)を使って作ったプログラムです 

    2. 「消える三目並べ」の最強プログラムは最低でも11手読みを必要とするため、テストするにも時間がかかって面倒なんです:weary: 

    3. 「三目並べ(tic tac toe)で遊んでみた(続き)」「9マス将棋(3×3将棋)と三目並べの変化形」参照 

    4. ここで言うAIとは「進化する三目並べ(Tic-tac-toe Evo)」で使用している機械学習によるAIです。 

    5. オセロと将棋に関しても、オセロは指し手が進む毎に盤面を駒が埋めていき必ず終局に向かうのに対して、将棋は駒が全て盤上を埋め尽くすわけではないので、必ずしも手数が増える毎に終局が近づくわけではないという違いがあります。オセロ、将棋、消える三目並べ、3つのゲームはそれぞれ微妙に違うわけです。こんな違いを意識している人は世の中にどれぐらいいるでしょうか:sweat_smile: 



    blog comments powered by Disqus