Hatena::ブログ(Diary)

Bonanzaソース完全解析ブログ

2010-01-13 私が評価関数について考えているすべてのこと このエントリーを含むブックマーク このエントリーのブックマークコメント

私は、いまやコンピュータ将棋トレンドである「棋譜からの学習」を使わずになんとかならないかと考えています。それは、もうそろそろプロにも迫る勢いであるコンピュータ将棋にとってプロの棋譜にそんなに価値はないだろうと思うからです。


私の考えている方法は大きくわけて2つあります。


1) うまく将棋というゲームをモデル化すれば、パラメータは計算でなんとかして算出できるのではないか?

2) 棋譜からの学習ではなく、自己対戦をしながら、(たとえば)探索深さ20手での最善手を教示信号として自動学習できないか。


2) は、保木さんに相談したところ、次のようにアドバイスをいただきました。

オセロの Logistello も中盤の学習でこのような方法を用いています。しかし、チェス

ではこのような方法ではうまくいかないようです。15手程度の探索結果を教師データと

して、1手探索結果を最適にするように学習する等して有る程度上手くいくかもしれませ

ん。このように自分自身を教師として学習していく方法は、柿木さんが55将棋でやって

いて、ある程度成功しているようです。

ただ、将棋の場合は質の高い棋譜が大量にあるので、これを教師にする方が良いです。

自己完結的な学習では矢倉や銀冠に組む事を良しと認識するのが難しそうです。

私も過去に、棋譜が手に入りにくい入玉形等を学習する場合はこのような方法が使える

のではないかと考えたのですが、まだ試していません。そもそも、棋譜に現れないような

状況にはなりにくいので、プログラムの強さを測るのも困難なはずです。

そりゃそうだなという感じで、20手では囲いの良さを学習するのは難しいと私も思いました。(囲いは終盤への貯金なのでplay outまで調べないと善し悪しが判断できない)


そこで、1) の方法について考え中のアイデアをだらだら書いていきます。


では将棋というゲームのモデル化をしていきましょう。


私が考える究極の(←中二病だと思ってください)評価関数は「駒割 + 位置評価」です。Bonanzaと変わらないじゃないかと言われるかも知れませんが、そうです。私はBonanzaの評価関数が究極の評価関数だと思っています。詳しい理由は書きませんが、序盤・中盤においてはこれがベストだと思っています。(これについて詳しい理論的なことは機を改めて書きます…が、以下の説明を読めばだいたいの理由はつかんでもらえると思います。)


では、この位置評価をいかにして自動的に得るかという問題になります。

将棋の手駒は盤上の好きな場所に打つことが出来る。例外として、すでに駒のある場所には打てないというのと、打ったあと移動させることが出来ない場所には駒は打てない、そして、二歩と打ち歩詰めになる歩は打てないというのがあるが、ここではそれらは考えない。


盤上の駒は(チェスに比べると)のろのろで、目的の場所まで移動させるのにかなりの手番が必要である。


このことから、手駒はかなりidealな状態であることがわかる。

終盤では、小駒は自玉の付近か敵玉の付近にしか打たない。それ以外の場所はたいてい意味をなさないからである。


手駒の価値とは攻め駒として使うなら「敵玉を詰ませる能力」とみなすことができるし、守り駒として使うなら「自玉を守る能力」とみなすことができる。


将棋方程式を発見した!(2) (やねうらおblog)

http://d.hatena.ne.jp/yaneurao/20080411


「攻め駒であれば何手で敵玉に到達できるのか」で盤上の位置評価を算出するのは、なかなか良い発想だと思います。GMA0BNさんもこの点において同じ考えだと思います。


将棋を「敵玉に自駒を整然と殺到させて詰ますゲーム」と捉えるなら重要なのは自駒から敵玉までの移動手数であり、駒の価値もそこから導かれるのでは、という考えに取り憑かれた漏れはその考えに基づき2.の部分を作った


差分生成しようとしたが一向に上手く動かないから、非差分方式で高速化する方向で形にした


この方向でとことんつきつめれば取ったり打ったり守ったりといった一見距離概念とは縁遠いような事象も移動手数に折り込むことが可能であり、進行度評価手段としても鉄板である(見込み)


また、終盤に生じ得る種々の複雑な状況も、移動手数を軸に整理すればそこそこ理想的に扱い得るんではないか、とも思う{要実証}


マイルストーンその1(思うだけで学ばない日記)

http://d.hatena.ne.jp/GMA0BN/20100111#1263154959

ところが、このモデル化によって将棋というゲームの性質がうまく反映できていない点がいくつもあります。これをただしく捉えなければなりません。



「攻め駒であれば何手で敵玉に到達できるのか」で盤上の位置評価を算出するという方法の何がまずいのかを書いていきます。


1)

それはまず、障害駒の取り扱いです。敵玉に4手で到達できる自分の銀があったとして、いくまでの経路に自分の歩が邪魔していて敵玉に実際は4手で行けないとしたらどうでしょう?その歩をどかす(移動させる)時間(手数)を要します。


単純に位置の評価値を敵玉までの手数のみで決めてしまうと「歩をどかす時間」が含まれていません。

これでは大きな誤差を伴っていることは明白です。


Bonanzaの3駒関係ですと、間にある駒も評価に入りますので、より正確になります。攻め駒に関してはその駒と玉へ到達するまでに存在する駒を含めた位置関係(4駒関係〜8駒ぐらいの位置関係)も見たほうがさらに正確になることもおわかりいただけるでしょう。


ただし棋譜からの学習では、サンプルが少なすぎて4駒以上の関係は学習できないでしょう。私が棋譜からの学習を避けたいのは、そのようなパラメータの調整が棋譜からの学習では不可能だからです。


2)

二つ目は、玉を詰ませるのには最低でも2駒必要だということです。1駒だけですとその駒を玉で取られるので1駒だけでは詰まないのです。桂で吊るす場合や、逃げ場所がなく合駒がない場合は1駒で済むことがありますが実戦ではまず現われないでしょう。


仮に2駒で詰むとして考えます。その2駒のうち片方の駒は、玉への距離(何手で玉に到達できるか)は2以上です。例えば次のような図です。

玉
金
歩

なぜなら、2駒の両方が玉への距離1だとしたら、その2駒の両方で王手されていることになり、合法手を指している限りそのような局面には到達できないからです。この王への距離が2以上あるほうの駒を(詰ませるための)補助駒とここでは呼ぶことにします。


よって、補助駒は敵玉への移動手数ではなく、詰ますことを念頭に置くとその駒を敵玉の24近傍への移動手数で評価されるべきです。(例えば、15にいる敵玉にとって39にいる香はとてもよく利いていますが、39の香を15の地点に運ぶ手数で考えてしまうとこの評価を誤ります。)


すなわち、駒を補助駒とみなすのか、直接詰ませるための駒としてみなすのかで二つの評価の仕方が必要になるということです。



3)

三つ目は、駒は上下の利きに対称性がないということです。ほとんどの駒は前方に特化されています。後方にはほとんど利きません。金なども後方は1箇所しか利きません。銀は後方には2箇所です。後方に利かすという意味では金より銀のほうが価値が高いのです。この意味で「入玉には銀を残せ」はなかなかの格言かも知れません。


話を戻しますと、金で王手した場合、その金の敵玉への移動距離は1ですが、玉の上から打つのと下から打つのとでは全然意味が違います。玉を下段に落とす価値のほうが、玉を上段に逃がす価値より上回るからです。また、この意味で、次のように敵玉の後方にある金と敵玉の前方にある金とでは同じように敵玉に2手で到達できますが、その意味はまったく違います。

□金□
□□□
□玉□
□□□
□金□

玉の前方に到達できる駒ほど評価する必要があります。別の言い方をすれば、玉の8近傍に何通りの方法で近づくことが出来るのか、その組み合わせがたくさんあるほど有効な「金」だと言えます。すなわち、敵玉に最短で何手で到達できるかではなく、「3手で到達できる方法が1つ + 4手で到達できる方法が3つ + 5手で到達できる方法が7つ」のような重ね合わせで盤上の駒の価値が決まるということです。


しかもそのときに障害駒のある/なしで到達できる手数が変わりますから、これも考慮に入れる必要があります。また、障害駒は自分の駒ならばどかせばいいだけですが、敵の駒ですとその駒を取って、かつ、取るために使った駒をどかせる必要があり、都合2手要します。また、取ったあとその駒を取り替えされたりするので、そう簡単な話ではありません。結局、このへんを正確に静止評価で計算するのは不可能だという結論になります。


4)

四つ目は、手駒の価値です。手駒は盤上にある駒より価値が高いのか、低いのか、ということです。


普通、手駒のほうが盤上の駒より価値が高いと思われていますが、実際はそうではありません。盤上の駒に変換するために1手を要するからです。無仕掛けで玉を詰ませるのと、掛かり駒があって玉を詰ませるのとでは全然意味が違います。


すなわち、1手の価値が限りなく低い序盤においては、盤上の駒に変換するコストが限りなく0なので、手駒の価値は高いのですが、1手の価値が高まってくる終盤においては手駒のほうが盤上の攻め駒より優れているとは言えないのです。


この部分を正しく理解していないとモデル化を誤ります。


5)

上の4)とも多少重複しますが、終盤は、駒のわずかな位置関係で詰む/詰まないが変わります。それは玉との部分的な位置関係ではなく、盤面全体に及ぶ関係です。3手詰みですら、pinされているかいないかで詰む/詰まないが変わることはざらにあり、それは部分的な位置関係では表現できません。


よって、N駒の位置関係は、詰みには全く無力なのです。「駒割り + 位置関係」という評価関数を、終盤では末端ノードの(短い手数の)詰め将棋探索で補ってやらなければならないのは、この理由によるものです。


6)

11にいる敵玉にとって、攻め方の13金と23金とでは、どちらがより"働いて"いるかということです。私は、間違いなく23金だと思います。13金だと21に玉を逃げられたときに銀を打っても詰みませんが、23金ならば22銀打ちで詰みます。


このように玉は容易に移動できるので、逃げられたときに追いかけるための効率、詰ませるためのコストみたいなものを評価しなければなりません。


例えば、片側からだけ2枚の金で攻めた場合、敵玉に反対方向に逃げられるとその二枚の駒を運ぶ必要があるので敵の1手に対してこちらは2手かかります。挟撃形なら敵玉は逃げにくいので事情が違ってきます。あと、2枚の駒で迫る場合でも、盤面の端だと玉は逃げ場がないので話が違ってきます。


このへんを正しく評価できるモデルが必要なのです。


「攻め駒であれば何手で敵玉に到達できるのか」で盤上の位置評価を算出するためには多くの課題があることがわかりました。しかし上の1)〜6)は多くの示唆を含んでいると思います。

トラックバック - http://d.hatena.ne.jp/LS3600/20100113