スポンサード リンク

T.Ishii's Software Library

HTML5 レトロ風ゲーム館

無料ブログはココログ

« 今までの経緯を書いてみた | トップページ | 方針は大体決まった »

パターン評価の問題点

今は、新しいリバーシプログラムの開発フェーズなのだが、MasterReversiの作者である所の作者が、何故、新しいプログラムを作ろうとしているのか、というと、MasterReversiには、それなりの存在意義があるのだが、採用しているパターン評価には、問題もあるからだ。

ここ数日で書いてきた様に、MasterReversiの評価方式というのは、1997年に当時の人間の世界チャンピオンを破ったLOGISTELLOの評価方式と方式的には同一だ。

なので、普通の人間や巷の多くのリバーシプログラムよりも強いのだが、実際の所、このパターン評価というのは、最適な評価方法なのか、というと、そうでもない感じもする訳だ。

何故なら、作者的には、ここ数日で、幾つかのリバーシプログラムをダウンロードして対局相手にしてみているのだが、その中には、数日前に書いた「リバーシプログラムの作り方」のサンプルプログラム、VectorでMasterReversiと同じリバーシカテゴリの人気順一位になっているK-Reversi、リバーシプログラムのアルゴリズムなんかをネットで検索すると良く出てくるThell、なんかがある。

で、上記のプログラムは、その説明文からすると、全て、パターン評価を採用しているのだが、それほど強いという事もない訳だ。

まあ、上記のプログラムの思考ルーチンは、全て、10年以上前に開発されたモノなので、当時のPCの処理性能を鑑みた最大読み数になっている事、つまり、読みが浅いのも、弱さの要因になっている筈なのだが、読みの深さを同じくらいにしたMasterReversiにBookを使用させないようにして対局させてみても、MasterReversiが勝つ事の方が多い訳だ。

と、いう事で、上記を見ていると、パターンによる評価を採用すれば、それだけで強いプログラムが作れるのか、というと、そんな訳ではない事が判るのだが、これはつまり、パターン評価には問題もある、という事だ。

具体的には、パターン評価というのは、プログラム的な実装は簡単なのだが、実際の所、とてつもなく多くなる各パターンの全てに対して、評価値に寄与させる適切な重み係数を割り当てなければならない、というのが問題になる訳だ。

つまり、例えば、LOGISTELLOやMasterReversiと全く同じ局所パターンを評価する評価関数を持たせたプログラムを開発するのは容易なのだが、その局所パターンが勝利に寄与するのか悪影響するのかが判らなければ、意味のある評価関数とする事は出来ない訳だ。

と、いう事で、パターン評価というのは、その膨大な数の各パターンの重み係数を適切に設定しなければならない、という点が問題になる訳だ。

もっとも、この問題については、機械学習させる、という事で、ある程度は緩和されるのだが、この場合にも、学習させる為のデータをどうやって入手するのか、という問題が出てくる訳だ。

まあ、この問題についても、リバーシについては対局時間も短いし、過去に様々なプログラムが作られてきたので、それらの対局結果を教師データにする、という事にすれば、とりあえず、問題は回避できるのだが、この場合には、そもそも、そんな教師データを学習させて問題はないのか、という次の問題も出てくる訳だ。

もっとも、より大きな問題としては、少なくともLOGISTELLOが使用したパターンの種類は多いので、前述の教師データに、そのすべてのパターンが存在しているかどうかが怪しい、というか、普通は存在してないパターンもあると考える必要がある、という事だ。

と、いう事で、パターン評価を採用しようとする場合には、その学習データが適切か、という点と、その学習データに全てのパターンを学習させるのに十分な局面が存在しているか、という点が考慮されなければならない訳だ。

MasterReversiの場合には、学習データの終盤20手くらいまでは完全読みで置換してあるので、学習データの40手目以降については、最善手が打たれている事が保証されている。

なので、少なくとも、40手目以降の局所パターンの終局に対する影響度というのは、それなりに正しいと考えられるので、このデータを学習用に使うのは問題ないと思われる。

そして、MasterReversiには、学習データ中にパターンが存在しなかった場合、そのパターンを強制的に発生させた学習データを作成する補完機能もある。

なので、標準添付版として添付している評価データでは、全く学習用データが存在しなかったパターンは存在しない形にはなっている。

と、いう事で、学習データに気を使っている分、MasterReversiは、前述の同様にパターン評価を行っている筈のプログラムにも勝てたりすると思われるのだが、そんなMasterReversi的にも、巷のプログラムと対局させていると、序盤から中盤くらいでBookから外れた局面に持ち込まれると、簡単に負けてしまう事がチョクチョクある訳だ。

つまり、序盤から中盤にかけての局面評価は甘い訳なのだが、これはある意味、当然の事になる。何故なら、序盤から中盤くらいの局面では、石数が少ないので、局所パターンの組み合わせ数も少なくなるからだ。

つまり、学習データに学習すべきパターンが発生している回数は少ない筈なので、何かの間違いで、たまたま、本来なら悪い局面と判定されるべきパターンが良い局面と判定されて、そのままになっている場合もありえる訳だ。

更に言えば、普通に鑑みて、まだ、辺や角、更にその近隣にも石が無い序盤や中盤で、その時点で石が置かれている部分の局所パターンから、対局結果が正しく予測できるか、というと、そんな事は出来そうもない訳だ。

まあ、MasterReversiでは、レベル5では24手読みを行うので、Bookを使わない場合、初手の判定でも、24手先の局面の良し悪しを見ている。

なので、序盤での評価についても、パターン評価している局面は、そのずっと先の局面になるので、石数はそれなりにある事になるのだが、問題になるのは、それだけ先の局面を先読みするためには、前向き枝刈りが必須になる、という事だ。

つまり、24手読みするにしても、それ以前の局面の良し悪しをある程度正しく判定できなければならない訳なのだが、パターン評価では、そんな序盤の局面の良し悪しは判定できる気がしない訳だ。

まあ、だからこそ、MasterReversiでは、標準でBookを搭載していて、序盤では、少なくとも最善手進行については、評価関数に頼る必要をほぼ無くしているのだが、この進行から外されると、正しい評価値が得られる気がしない評価関数を使って、最善手を探索する必要が生じる。

その結果として、比較的序盤でBookから外されると、負けてしまう事もチョクチョクある訳だ。

と、いう事で、作者的には、この問題を何とかしたいので、今回、新しいリバーシプログラムを作って色々と実験してみている訳だ。

そのゴールは単純で、パターン評価による評価値が信用できない序盤の、少なくとも前向き枝刈り時には、パターン評価以外の評価で評価値を得られる様にしたい訳だ。

« 今までの経緯を書いてみた | トップページ | 方針は大体決まった »

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/534482/66367076

この記事へのトラックバック一覧です: パターン評価の問題点:

« 今までの経緯を書いてみた | トップページ | 方針は大体決まった »

2018年11月
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  

広告

プライバシーポリシー

  • 当サイトでは、第三者配信による広告(Google Adsense)サービスを利用しています。

    Google を含む第三者配信事業者は、Cookie を使用して、ユーザーのウェブサイトでの閲覧履歴に基づく広告を配信します。 Google 広告 Cookie を使用することにより、Google や Google のパートナーは当サイトや他のサイトへのアクセス情報に基づく広告をユーザーに表示できます。

    収集された情報がGoogleによってどの様に使用されるか、収集される情報をユーザーが管理する方法については、以下のリンクを参照下さい。

    ポリシーと規約 - Google