「入玉指向の将棋プログラムの作成」の改善案
GPWSで発表された田中哲郎先生の「入玉指向の将棋プログラムの作成」について思うところがありまして、以下にだらだらと書いておきます。なお、本論文は以下のURLから読めるようです。
元の論文のアイデアは、「王の入玉に関する機動性(?)を評価して評価関数に加点しよう」というものでして、玉は左上・真上・右上にのみ進めて、相手の利きおよび自駒がある場所には移動できず、入玉できる経路があるかどうかを調べるというものです。
入玉に関して、入玉を阻止している駒で評価するのではなく玉の入玉経路の有無を評価関数に反映させたところが元の論文の目新しいところで小さな計算量で済む、面白い特徴因子だと思います。
疑問点1) この入玉経路を調べるコストはゼロに近いのか？ゼロに近くなければ、滅多に出現しない入玉将棋のために評価関数の計算コストが増大するので勝率自体は下がるのではないか。
疑問点2) 入玉する場所がどこでもいいというのはおかしいのではないか。盤面の左上とか右上のような隅のほうがポイントが高くなっているべきではないのか。
まず疑問点1)を解消するために、以下ではこの経路探索の発見がすこぶる小さなコストで出来る擬似コードを示し、また疑問点2)を解消するために、疑問点1)で示した擬似コードに基づく改善案を提案します。
■ 入玉経路の探索の高速化
敵の利きは事前にmake_moveのときに利きを表現するBitboardに反映しているものとします。
いま、玉が7段目の中央(5筋)にいるとします。6段目のうち、玉のいける場所は次図のようになります。
□□□■■■□□□
■ = 行ける場所
□ = 行けない場所
これは、ビットパターンで言うと、
次段 = ( (前段<<1) | 前段 | (前段>>1) ) & 0x1ff ;
のようなパターンです。最後の1ffは、演算結果を9マス(9bit)に制限するためのマスクです。
この計算は、テーブルをlook upしても良いでしょう。こうなります。
次段 = next_table[前段];
// next_tableは512byte × sizeof u16 = 1MBのサイズ。
あとは簡単ですね。これをループで回して、入玉できるか見るだけです。
i = 1 << 現在の玉の筋(0..8);
foreach 現在の玉の次の段から入玉だとする段まで
{
i = next_table[i];
i = i & (move_to >> その段のビットパターンが得られるシフト回数 ) & 0x1ff;
if (i==0) break;
}
// iに入玉できる場所を示すビットパターンが得られた
これだけですね。極めて小さな計算量で入玉だとする段のどこの筋に到達できるのかまで調べることが出来ます。
また玉が最下段のときはこのような加点せず、2段目(8段目)より上にいるときにのみ評価関数に加点するならば、調べる段は3〜9段目のみですみますから、これは64bitに収まり、私が以前提案したRBBを用いると片側64bitの盤面を見るだけです。
ゆえに上の処理はBonanza6の評価関数の1〜2%程度のコストで済むのではないかと思います。
■ 入玉できる場合、どう加点するか
仮に最上段まで入玉できるとして、そのときに入玉できる場所によって点数は異なるべきです。
すなわち、さきほど求めた入玉できる場所を示すビットパターンをそのまま加点したいわけです。
score += 入玉評価テーブル[i];
これで済めば簡単この上ないのですが、問題は512通りきちんと棋譜から学習できるかということです。
しかしよく考えると
a) ■□□□□□□□□
b) ■□■□□□□□□
c) ■■■□□□□□□
d) ■□□■□□□□□
a)よりはb)のほうが優れていることは自明であり、a) < b)のような順序関係がなりたちます。同様に b) < c)ですが、b) と d)の関係についてはよくわかりません。隅のほうが評価値が高くなるべき!という原則からすれば4筋よりは3筋のほうが価値が高いはずで b) > d)でしょうか。
まあ、このような半順序関係を利用していけば、棋譜から学習させられなくはないのかも、と思います。(よくわかりません…)
続きは誰かお願いします…(←人任せ)
