21 October 2016

    無理とは分かっていても何とかしたい

     「進化する三目並べ(Tic-tac-toe Evo)」をリリースした後、このアプリと同じAIの作り方(勝ったらご褒美、負けたら罰を与える)でオセロや将棋を作れないだろうかと考えてみました。同じコードを再利用して(楽して)他のゲームが作れるなら作る側の人ならやってみたいと思うでしょう。使う側のユーザーも、なんで「進化する将棋」や「進化するオセロ」じゃないの?「三目並べでは簡単すぎて楽しめない」という人もいるかもしれません。でも、想像つくとは思いますが、三目並べなのには理由があります。ネットで検索してみたところ、オセロで出現し得る局面の数は約で、将棋はだそうです。私が作った三目並べは以前記事にも書きましたが、局面の数は以下で詳細は次の表の通りです。

    手数 \ 重複チェック  有り    無し  
    初期盤面 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手目  1,260 181,440
    8手目  630 362,880
    9手目  126 362,880
    計  6,046 986,410

     三目並べだからこそ比較的容易に作れたってことです1。三目並べでは重複局面を省けばわずか6,046通りの局面データを保持すれば済みます。100,000回対戦テスト後の手元の学習ファイル(ゲーム木データを保存したファイル)のサイズを見ると重複チェック用のデータと合わせて約800KBですので、一局面分のデータ(約130バイト)× 6,046局面 = 800KBって感じでしょうか。もしオセロの全局面を保存しようとすると、1テラバイトが(=約)なのでというオセロの局面数(重複局面を省けばもっと減ると思いますが)を保存するためには、とんでもないディスク容量が必要です。スマホでは全然容量が足りませんし、局面の検索の時間もかかるでしょうし、今のやり方そのままではオセロや将棋のアプリを作るのは現実的ではないということです。
     でも、「進化する三目並べ(Tic-tac-toe Evo)」はゲーム木(全局面の分岐を木構造で表現したデータ)を動的に生成するので、オセロの局面がいくら多いといっても1ゲームごとに少しずつノード(局面データ)を追加していくのであればとりあえずディスク容量に余裕があるPCで動かすソフトは作れるんじゃないか、なんて考えてとりあえず試しに作ってみようかと思ったりしたのですが、ゲーム木のノードの数が多いと一回のゲームで得られる学習効果が非常に薄まるのでいくら対戦しても全然強くならない(学習効果が実感できない)ものになるでしょう。プログラム同士で対戦させて予め学習を進めてからリリースするという方法も考えられますが、それにしてもデータを小さくしなければならないという問題は解決する必要があります。
     データを小さくする(ゲーム木を小さくする)ために回転・対照形を同一局面と見做して省略する記事は以前も書きましたが、この時は局面の数を求めるためだけに力技でプログラムを改変したのですが、AIに組み込むとなると、処理に手間取って操作性に影響が出るのも嫌なので手付かず状態です。機種にもよりますが現状でもAI側が指し手を決める時に動作が少し重いのを感じると思いますが、これは局面の先読みをする必要がない代わりに、検索と数値計算処理に手間がかかっているからです。

    「消える三目並べ」なら何とかなりそう

     「無限三目並べ」、「無限まるばつ」、「Arrange Line」いろんな名前でリリースされているゲームで、正式名称は分かりませんが、「消える三目並べ」というのは、三つまでは普通に置けるけど、四つ目を置くと最初に置いた自分の駒が消えるというルールの三目並べのことです。

    「消える三目並べ」のゲーム進行の一例

    例1

     上の図の進行を見ていただければルールはすぐにわかると思いますが、5手目でダブルリーチを掛けている先手(X)が勝ちかと思いきや、次の手を打つと自分の3手前の駒が消えるのでダブルリーチを掛けたにも関わらず先手(X)が負けになっています。

     このゲームに関しては以前にも「ちょっと変わった三目並べ」というアプリの記事として書きました。思いつきの汚いコードを晒しています:grin:が、指し手をキュー(queue)に格納するようにコードを書き直して、どれぐらいの局面の数になるのか確認してみました。

    手数 \ 重複チェック  有り    無し  
    初期盤面 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 -

     そうすると、思惑通りというか予想通りというか当たり前というか、Xが3手Oが3手の計6手進んだあとは、局面の数は増えることがありません。重複チェック無しだとカウント処理が終わらないので-としましたが、上の表でわかる通り、通常の三目並べよりデータ量は少なくて済みます。ゲーム終了までの手数は増えていきますが、AIに報酬や罰を与えるのはゲーム終了時の1回だけなので、局面の重複チェックさえしていればデータが無制限に増えることもありません。
     おまけにAIに勝つためには通常の三目並べより頭を使うので、三目並べじゃ物足りないという人にとっても楽しめそうな気がします。初めのうちは簡単に勝てていたのにだんだん勝てなくなるというのがAI(人工知能)の醍醐味だと思うので自分の思惑通りのアプリが出来そうです。それともう一つ、通常の三目並べはお互い最善手を選択し続けると引分になりますが、このゲームは引分にはならない(千日手はあり得る)ので、その点も良さそうです。「進化する三目並べ(Tic-tac-toe Evo)」をプレイしていて、「人」に進化するまでやってみようと思ってますが、引分ばかりでは辛いなと思っていたところなので、まずこれを作ってリリースしようかなと思っています。
     これが完成すれば次はミニ将棋(3X3将棋、5X5将棋、9マス将棋)辺りに挑戦しようかと思ってます。


    1. 名前を忘れてしまったのですが、20年以上前に対戦する度に強くなると謳った将棋ソフト(シェアウェア)があったと思うのですが、どのような仕組みだったのかよく知りません。今でもあるのでしょうか? 



    blog comments powered by Disqus