図2
KFEndは、悪形となる手をなるべく指さないようにするために、"悪形チェック"と呼んでいる方法を用いている。悪形チェックは、単純で、プログラムする上で楽であり、ほとんど安易であるとさえ言える。それ故の限界は明白であるのだが、実用的には強力で、KFEndを強くするのに大きく貢献している。
将棋を計算機上に表現するデータ構造とそれらの基本的操作を実装し、静的評価関数と探索アルゴリズムを決めれば、将棋プログラムとなる。評価関数を駒の損得や働き、玉の安全度などを考慮して作成し、探索はよく知られたalpha-betaアルゴリズムを用いると、プログラムは特に苦労もなく動くようになるだろう。このような簡単なプログラムは当然、かなり弱いのだが、私の経験に照らすと、その弱さは異質なものを含む。人間なら弱くても決して指さないような、一見して変な手を指してしまう。
このような変な手には、水平線効果が原因であるものが含まれる。水平線効果はコンピュータ将棋における本質的な困難のひとつだが、この対策を取っていないプログラムの振るまいは、かなりひどいものになる。簡単なプログラムではこれは仕方が無いだろう。
もうひとつのタイプとして、いわゆる悪形にしてしまう手がある。これが悪形チェックの対象として問題にする手である。
例えば、図1で▲36飛、あるいは▲46飛と歩の上に飛を持って来てしまい、攻める態勢を作り難くしてしまう。また、△77角成と角を交換しに来られた図2で、▲77同金と取ってしまう。壁形を解消する▲77同銀が普通である。
ひどいのは、図3で▲18飛、さらに▲28銀として自ら飛を閉じ込めてしまう。特に目的も無いのに囲いを崩すこともよくやる。序盤ルーチンで囲いを完成させることはできるが、序盤ルーチンが終了した後におかしな手が出る。例えば、美濃に囲った図4で▲39玉、▲48玉としてしまう。玉は48にいる方が金銀が近くに位置するので評価値が高くなるためこうなる。
このような悪形にする手を悪形手と呼ぶことにする。なぜ悪形手と指すかと言うと、悪形になった局面の評価値が特に低くならないからだ。他に駒得するようなはっきり評価値が高くなるような手があるときはその手を指すが、そうでないとき、多くの手の評価値がほとんど同じになり、たまたま変な手が第1位になることがある。したがって、悪形手を無くすには評価関数を正確にして、悪形とみなす局面の評価値が低くなるようにすればよい。多くの将棋プログラムではこのような努力が行われているだろうし、KFEndでもある程度やっている。
前章で述べたように、評価関数を正確にすることによって悪形手を指さなくすることが、少なくとも理論的には可能である。しかし、これを行うには大きな困難がある。悪形とみなされる局面は非常に多くの種類があり、それらを全てカバーするような評価関数を作成するのは非常に手間であり、かりに作成できたとしてもそのような評価関数は実行するのに多くの時間を消費する恐れがある。また、様々な種類の局面に対応しなければならないため評価する項目が多くなり、それらの項目間の調整が難しい。すなわち、ある項目は(a)という種類の局面を正確に評価するのに有効に働くが、(b)という種類の局面の評価にはかえってじゃまになって評価を不正確にしてしまうということが生じる。
このような困難を克服して、悪形にしないような正確な評価関数を目指すという方針でプログラムを書くことは、十分有力だと考えられるが、KFEndでは違う方針を取っており、それが悪形チェックである。
現局面において指される手moveが悪形手であるときtrueを返す関数、
bool akukeiQ(CSST move);
を作成する。akukeiQ()は評価関数と同じように局面の静的条件をもとに計算して結果を返す。与えられた局面で指し手を決定するのにakukeiQ()を用いて、以下の手続きを行う。
探索を行って得られた最善手が悪形手であるとき、探索での評価値が最善手とあまり変わらない悪形手でない手があれば、その手を指すということだ。KFEndの歩の値段は10点なので歩を只で取られれば局面の評価値は20点下がる。したがって、上の手続き5の条件から、M1と比べて歩損する程度の差のある手M2は指されないことになる。
akukeiQ()は以下の処理を行う。悪形手の各項目ごとに判定ルーチンを設け、順にチェックしていく。どれか1つの項目で悪形手に該当すると判定されれば、即座にtrueを返す。1つも該当しなければfalseである。悪形手の具体的な項目は次章で説明する。akukeiQ()は、評価値を返すのではなくbool値を返すだけなので、作成が楽である。
悪形チェックにかかる計算コストは非常に小さい。akukeiQ()が呼ばれる回数は、最低で1回、多くても数回程度である。1秒当たり数万回呼ばれる評価関数と違って、akukeiQ()が少々複雑になっても全体の実行時間に影響はほとんど無い。
KFEndでチェックしている全ての悪形手の項目を以下に記す。
これらの項目は、KFEndの棋譜から悪形手とみなすべき手を選別し長年に渡って逐次的に追加して来たものである。変な手を見つけたら悪形チェックで回避できないかをまず検討するわけだ。また、悪形手とみなすべきでない手Mを悪形手としてしまい、悪形チェックがあるため手Mを指すことができない、という問題が生じることがある。そのときは、誤って悪形手にしてしまった項目を修正して、手Mが該当しないように条件を絞る。この作業を繰り返していく。
前章で示したような悪形手でも、駒を取る手は悪形手にしない方が良い場合が多い。例えば、図1で▲27飛は項目19の「飛を自陣3段目に移動する」に該当するが、もし、27に後手の駒があるなら▲27飛は当然の手になる。したがって、駒を取る手は悪形手にしないようにするのが良いが、単純にそのようにすると問題が生じる場合がある。それは、ある駒を取る手が複数あるときである。例えば、図2において▲77金は駒取りだが悪形手にしたい。これを実現するために前述の指し手を決める手続きを以下のように修正する。
強調表示したところを修正している。M1が駒を取る手のときは、M1と同じ駒を取る手の中から悪形手でない手を選ぶということである。
その手自体は悪形手だが、何手か進めた後に良い形になるということがあるが、これには対応できない。敵に悪形手を指さざるを得ない状態を強制するような手も指せない。また、悪形手を指さざるを得ない状況で、無駄な手を指してしまうということがある。
図5は第10回コンピュータ将棋選手権決勝リーグでの川端将棋-KFEnd戦で現れた局面である。ここで後手KFEndが探索で得た最善手は△92飛で評価値＝70、第2位の手は△38歩で評価値＝59であった。△92飛は項目28「自陣の端に移動する」に該当する悪形手になり、△38歩は悪形手でなく評価値の差、70-59=11が15より小さいので、△92飛はレジェクトされて△38歩が指された。しかし、△38歩の最善手順を見ると△38歩、▲同金、△92飛、…となっている。△38歩は取られた後また△92飛と指す予定なので、この手自体は全く無駄で意味が無い。本来指すべきは評価値＝56で第3位の△42飛であった。
もし評価関数で悪形を認識できていれば、このような問題は生じない。悪形チェックは初手のみを見ているので、2手目以降に現れる悪形には全く無力である。
ここで述べたような悪形を、探索で用いる静的評価関数で評価するのが困難であるため、それをあきらめ悪形チェックという簡単な方式を考案した。十分正確で高速な評価関数が作成できないので、それを補う機構として悪形チェックがあると言える。他の将棋プログラムでもこのような機構があるのか、非常に興味がある。ここであげたような多くの悪形を評価できる優秀な評価関数の作成は、私にとっては至難のわざに思えるからだ。
(2000.10.23)
