09 September 2014

    三目並べ(tictactoe)作成後

     前回の記事で自分で作った将棋ソフトが弱い原因を確認するために三目並べ(tictactoe)プログラムを作ったことを書きましたが、一応その後の結果を書いておこうと思います
     三目並べプログラムで先読み関数には問題ないと確認出来たので、将棋プログラムの先読み部分もそれと同じように修正してみました。将棋の前にオセロプログラムも作って確認したのですがここではその話は置いておきます。それと、三目並べと同じように修正したと言っても将棋には盤上の駒を動かす場合と持ち駒を打つ場合があったり、相手の駒を取ったりするので、三目並べと同じにはならないのですが、どういうパラメータを与えるかとかどこで評価関数を呼んでどこで再帰関数から抜けるのかとかそういう部分を同じにしたということです。将棋プログラムでは、評価関数を呼び出す場所を先読み再帰関数の先頭にしてみたりforループの中にしたり、評価部分の等号・不等号の違いや評価する局面の枝刈りをする場所変えたりいろいろ試行錯誤しているうちに正確に先読み・枝刈りが出来ているかどうかわからなくなってきたので、三目並べで確認したかったんです。
     この類のゲームを作ったことがある人なら分かると思いますが、自分の書いたプログラムが膨大な局面の評価値のtree構造をどのように遷移して結論を出したのか確認するのは結構面倒です。評価の遷移を出力して確認するためのテストコードを書くのが王道かもしれませんが、それより簡単そうで面白そうなので三目並べを作って確認し、それと同じ作りにしてしまおうということです。
     で、結論はどうだったかというと、先読み部分を三目並べと同じように変更しても将棋ソフトは全然強くなりませんでした。結局、先読み部分には大きな問題はなく、ソフトが弱い原因は先読み手順以外の部分(評価関数や読む深さ)にあるということがはっきりしたわけです。今の評価関数は駒の重み(飛車=85点、竜=100点、玉=9999点、金=50点、歩=10点…等)の合計値を使って局面を評価しているだけなので、いい結果が望めないのは当然といえばそうなのですが、前回の記事で書いたように、駒の重みだけの評価関数でオセロを作った場合には非常に強いソフトになるのに将棋だとなんでこんなに弱いのか納得出来なかったので念のため確かめたって感じです。
     仕方がないので疑問手を指した局面で、何でこんな手を指すのか地道にコードを追っていって調べたところ何となくオセロとの違いが分かってきましたので、実際にソフトが指した手を示しながら説明したいと思います。
     というか本当に強い将棋ソフトを作りたいのなら、今のご時世ならソースコードが公開されているらしいBonanzaのソースコードを調べてそれに倣うのが一番手っ取り早いと思いますが、それでは面白く無いのであくまで自己流でやってます。

    テスト局面の例

     本将棋もどうぶつ将棋もプレイ出来るような作りにしているのですが、本将棋(9×9)だと確認が大変なのでミニ将棋(5×5)で確認しました。

    • ケース1
      局面1-1
       先手=ソフト、後手=人間で上の図の初期配置から先読みをせずに、というか1手先を読む設定でソフトに初手を指させると「1二飛」と指します
      局面1-2
       ソフトは自分が一手指した局面で評価(自分の駒の重みの合計点ー相手の駒の重みの合計点)を計算しますので、この局面では歩を一枚得をした状態なので自分が有利と判断します。次の一手で後手に飛車を取り返されて大損するにもかかわらずです。

    • ケース2
      局面2ー1:
      局面2-1
       先手=ソフト、後手=人間で、既に後手有利な局面ですが、ここで5一の飛車を使うために4三角と指します。
      局面2ー2:
      局面2-2
       もし、ソフトが角を取れば4五飛車の一手詰という仕掛けです。3手先を読む設定にしたソフトで、この局面で指させると下図のように堂々と4三金と角を取ってしまいます。
      局面2ー3: 局面2-3
       ソフトからすると4三金(1手目)、4五飛(2手目)と進んでも4五同玉(3手目)とすれば自分が有利と計算することになるからです。
      局面2ー4: 局面2-4
       4五同玉と取った時点の駒の重みの合計点は飛車の分が加算されて先手のソフト側の点数がかなり高くなります。この飛車を取ることが出来るというところまで読んで「局面2ー2」の時点で4三金と角を取る手を選んでしまうわけです。その次の一手で後手に4五同馬と玉を取られるにもかかわらずです。ソフトを4手先を読む設定にすれば、その先で自玉が取られて合計点が大幅に減ることが分かるので「局面2ー2」で4三金とは指しません。

    オセロとの違い

     ケース1では飛車が取られる、ケース2では玉が取られるという、序盤であれ終盤であれ一手違うだけで評価値が激変するのが将棋のオセロに無い特徴だと思います。将棋以外のゲームでも勝ちか負けかという局面では評価値が激変するのは当然ですが、将棋は一手毎に駒を打つ場所が少なくなるオセロや囲碁と違って、徐々にゲームの終わりが近づいているわけではありません。いつ終了するか(いつ玉が詰まされるか)わかっていないので常に局面を厳しく評価する必要があるのです。オセロの評価関数は序盤でいい加減な評価関数を使用していたとしても、ゲームの終盤で残り15手とか20手になったときに最後まで読み切ることが可能なので強いソフトが比較的簡単に作れるのでしょう。三目並べも同様です。将棋の場合、読み切りと言えば詰みを探すということになりますが、初手から詰みを探しても時間の無駄ですし、オセロのように一手毎に終わりが近づいているわけではないので、残り何手になったら詰みを探すという作りにも出来ません。常に局面を正確に評価し、詰みがある局面ではそれを逃さないような作りにする必要があります。
     それともう一つオセロや三目並べは、手が進むに連れて徐々に手の選択肢が少なくなるので深く読むことが容易になっていきますが、将棋にはそういうことがありません。むしろ持ち駒が増えると読む手が増えていきます。
     ということで、まずはもっと深く読むことが必要だと思うので、クラスの構成やデータ構造も見直して作り直そうかと思っています。駒の働きや玉の固さなども考慮した凝った評価関数を作るとなると、結局速度が必要になるのでデータ構造も出来るだけ単純にすべきなのですが、そもそもRubyで実効速度は期待出来ないと思っていたし、ミニ将棋ならオセロより駒の数も少ないし特に凝ったことしなくても自然と強いソフトになるだろうなんて甘い見通しだったのがいけなかったようです。

    おまけ

     SDIN将棋のサイトで自分が作ったソフトとCPU対戦したところ、4手読みの設定でいい加減な評価関数でもレベル2には常に勝てるようです。レベル3には勝てませんので、これに勝つことを当面の目標にしてみます。
     それと、つい最近まで開発の動機なども含めてgithubのwikiに書いて「Shoes de shogi」という名前でgithubで公開していたのですが、とりあえずもう少し強くできるまで一時的に削除することにしました。



    blog comments powered by Disqus