探索手法の一つである反復深化法の改良案として0.5手延長アルゴリズムを提案する。この方法は反復深化法において前回の最善手を読む場合にのみ、探索限界を0.5手延長していく方法である。これにより、良い手だけを深く探索することが出来る。

　一般的に読みの深さは深い方が強いが、それがどの程度の強さか、の判定は困難である。そこで、このような中途半端な探索の延長を行った場合の棋力の向上について、探索時間と勝率の関係を調べる。対象としては、実際の将棋プログラム(YSS)と、全幅探索の将棋プログラムを使用する。

Half ply extension algorithm is a variation of iterative deepening.

In iterative deepening, when depth N search finished, all N-1 depth position have a best move. By using big hash (transposition) table, those all best moves is memorized.

And next N+1 depth search, program searches the memorized best move at first.

When half extension is used, program searches the memorized best move at first and depth max is added 0.5 ply only first move. Two 0.5 ply extension make one (real) ply extension. So a move that is thought good is searched deeper.

When basically N plies search, program can search 2N-1 plies in the maximum. The feature of this algorithm is that time (number of end position) takes only 2〜3 times in comparison with normal search. For instance, search time takes only 2.35 times when basically depth max is 8, maximum is 15, and branching factor is 20.

However, it became clear that half extension algorithm was not effective by this paper.

ゲーム木探索においては、読みの深さを深くすることは非常にリスクを負う。αβ法で探索した場合、局面での平均可能手が80手程の将棋では、もう1手深く探索するためには9倍の時間をかけねばならない。いかに時間をかけずに本筋の手のみを深く読ませるか。これは将棋プログラマが評価関数の改良と同時に直面する問題である。

反復深化法とは、ある固定の深さｎまで縦型に読む方法ではなく、深さ1,2,3,…,nと順次、深さを増して探索していく方法である。最初に１手の深さまでの探索を行い、最善手を見つける。次に2手の深さまでの探索を行う。この時、1手の探索で見つけた最善手から先に読みはじめる。以下、同様に3,4,5,…,n手、と探索の深さを１手づつ深くしていく。前回の探索で得られた最善手を最初に読むことによりαβ法での枝刈りの回数を増やし、読みの量を減らすことが出来る。この探索方法は思考時間に制限がある場合に有力に働く。ある深さｎの探索途中で時間が切れた場合、それが1番目の指し手（n-1の探索での最善手）の探索途中だった場合は、その手を。2番目の途中だった場合は、その手の正確な評価値がまだ判明していないので1番目の手を。3番目以降で、最善手が入れ替わっていた場合は、その手を選ぶようにする。

　0.5手延長アルゴリズムとは、反復深化法において、前回の最善手を読む場合にだけ、探索深さ限界を0.5手延長する方法である。これにより基本深さnの探索を行った場合に、もっともらしい手の探索を最大2n-1の深さまで探索する事が出来る。

　例として図１を示す。この図は固定深さ3の探索を0.5手延長アルゴリズムで行った場合である。各局面（ノード）における可能な手の数（分岐数）は2とし、左側の手が（枝が）最善手だとする。ノードの横の数字はその局面における探索深さ限界（depth_max）を示している。各ノードから左の枝をたどって下がっていくとdepth_maxは0.5プラスされる。右に下がる場合は、depth_maxはそのままである。探索開始局面（depth_max=3）から、左に3回下がっていくと、depth_maxは +0.5 +0.5 +0.5されて depth_max=4.5となる。通常の探索ならば、この深さ3のノードで読みが打ち切られるはずである。しかし、ここでは depth_max=4.5なので後1.5手、探索を続ける事になる。さらに左の枝を1回下がると+0.5 で depth_max=5.0となり、もう1手深く探索できる。さらに左の枝を下がった場合、depth_max=5.5となり、これが6を超えていないので、ここで探索は打ち切られる。

逆に、開始局面から右の枝を3回下がった場合は、depth_maxは3のままであり、探索は延長されることなく、ここで打ち切られる。

Fig. 1: Three depth game tree of half extension algorithm

図１　基本的な３手の探索をした場合の延長のされ方

太線は最善手を示す。ノードの横の数値は最大探索深さを示す。

このように、左の枝を下がるたびに（最善手を選ぶたびに）depth_maxは0.5づつ足されていく。その結果、基本深さn(=3)の探索をした場合に、もっともらしい手の探索が最大2n-1 (=5)の深さまで可能となる。　このアルゴリズムの特徴は最大 2n-1 の深さまで探索する可能性を持ちながらそれにかかる時間は（末端局面の数は）、通常の2〜3倍程度で済む、ということである。例えば 各局面の分岐数を20とし、固定深さ8の探索をした場合、最大15手先まで読むにもかかわらず、探索時間は2.35倍にしかならない（表１）。分岐数が多いほどかかる時間は少なくなる。

Table 1: Time and maximum depth. Branching factor is 20.

表１ 0.5手延長した場合のかかる時間と最大探索深さ

分岐数20で、最善手１手のみを延長。

　実際のYSSでは局面の分岐数は6〜80程度であり、そのうち延長される手は最善の手、１手だけである。どの手が最善手かは、反復深化法による前回のn-1の深さの探索で得られた最善手をハッシュテーブルに登録しておいて調べている。最善手が登録されていない場合は、第１番目の指し手を前回の最善手と仮定して延長を行っている。

前回の最善手以外の手が、新たに最善手と判明した場合、もう一度その手を0.5手延長しなおす事はせず、ハッシュテーブルに登録されている最善手を書き換えて終了する。なお、新たな最善手を全て0.5手延長しなおす場合（完全0.5手延長）にかかる時間は、しない場合の３倍程度であった。単に１手深く探索するためにかかる時間は約６倍であった。

また、0.5手延長を行った場合に得られる最善応手手順は 5手読みで6手から7手。7手読みで8手から10手程であった。

この探索方法を有効に働かせるには、、コンピュータの速度に対して充分なメモリがあることが必要である（最善手が判明している全ての局面を記憶する必要があるため）。また、残りの探索深さに依存した指し手生成ルーチンを持つ必要がある。

駒の価値を表２に示す。これはYSSで使っている値と同一である。

Table 2: Value of piece

表２ 駒の価値

対戦の条件は以下の通りである。

・反復深化法を用い、αβ法で探索する。・ハッシュテーブルを用いる。・千日手は可能な限り打開する。・300手を超えたら引き分けとする。・100局対戦させる。・王手がかかっている局面はもう１手深く探索する。

• 末端の評価値に歩の価値(100)の半分程度(64)の乱数を加える。乱数は現在時間を元に初期化し、a=16807, m=2^31-1の乗数合同法で出している。ほとんどの対局が初手からの数手でまったく異なる棋譜になっている。YSSでは序盤のみ(8)の乱数を加えている。
• 全幅探索では手を生成する順番は自分から見て盤面の右下から左上にかけて下から順番に、移動手、駒打ち、と生成している。手の並び替えはハッシュテーブルに保存されている前回の最善手を最初に読む以外はそのままである。
• 制限時間内まで探索する。基本は１秒。

　基本的な読みの深さを同一の条件に使用した場合、将棋では序盤と終盤で可能手の範囲が大きく変動するので、序盤で深さ６手から７手まで読めるのに対して、終盤では４手から５手程度しか読むことができない。そこで、思考時間に制限をつけ、これを条件とした。制限時間内であれば、プログラムは可能な限り深く探索する。

対戦に用いたコンピュータは Alpha500MHz、Pentium133MHzの２台で、速度の違い(約3.7倍)を考慮して133MHz側の思考時間を変動させている。制限時間の１秒が短い、と感じられるだろうが、Alpha上で全幅探索ならば毎秒15万局面、YSSで4万局面を読めるのでそれほど少ない時間ではない。

先後は交互に対戦させている。参考までに最初の10局における先後での勝率のばらつきを見ると、先手から見て

合計490勝491敗19引 勝率0.50

といった感じで、ばらつきはあるものの平均すると５割となる。よって、勝率４割から６割までは誤差の範囲として、成績は互角、と考える。以下のデータでは先後の情報は示さない。

　0.5手延長をしたプログラムの 13勝83敗3引。この結果は予想に反して意外であった。原因としては、単純な全幅探索のプログラムでは、無謀な駒取りの手が末端での最善手となり（取り返しを考慮しないため）、延長が有効に働かないため、と考えられる。

　そこで、部分的な駒交換で損となる手は一切読まないプログラムで効果を試した。このプログラムが指す手は全て表面上は損でない手なので地平線効果の影響もほとんど現れない。これを「捨駒なし」と呼ぶ。

　「捨駒なし」、と「純粋全幅探索」との対戦結果は94勝6敗で「捨駒なし」が圧勝した。しかし、「捨駒なし」で、0.5手延長と通常を比較したが27勝71敗で、0.5手延長がはっきり劣勢となった。

思考時間を長くすれば（読みの深さを深くすれば）、0.5手延長の効果が現れるのでは、と考え、思考時間を40倍に増やしたが、結果は2勝11敗（時間不足のため全13局）、と大差ない結果に終わった。

　「捨駒なし」のモデルでは、けっして乱暴な手は読まないため、先に駒損する手などは一切読まない。そこで、モデルとしては、探索限界の半分の深さまでは全幅で読み、それ以上の深さでは「捨駒なし」の「半分捨駒」モデルが強いのでは、と考えたが「半分捨駒」と「捨駒なし」では30勝69敗1引で、単純な「捨駒なし」が優勢であった。

　では、実際の「まとも」なプログラムであるYSSではどうであろうか。YSSを1秒、「捨駒なし」を10秒の差をつけて対戦させたがYSSが10戦全勝した。内容的にも大差であったので100戦させても全勝するであろう。評価関数の差が大きいと思われる。

Table3. :Winning rate of YSS Half Extension

表３　YSSで0.5手延長した場合の勝率

　思考時間を20倍まで増やした (３日間連続で計算させた)が、結果は0.5手延長の43勝53敗4引、と互角に近い。YSSの場合では、0.5手延長と通常では、明確な差は得られなかった。

では、完全に0.5手延長させた場合はどうだろうか。これは、新たに最善手となった手を再び0.5手延長しなおす方法である。

　結果は完全0.5手延長の 54勝45敗1引。これも互角としか言えない。

　0.5手延長が効果的に働かないのは、同一プログラム同士の戦いのため、とも考えられる。そこで他のプログラムとして柿木将棋�U(Windows95)のレベル５と対戦させた。対局数は少ないがそれぞれ10局づつである。YSSはPentium90MHz上で打切時間5秒である。柿木将棋にも乱数が入っているため同一の棋譜は生じていない。先後は交互である。

Table4. :Result of YSS vs. Kakinoki Shogi95 L5

表４　柿木将棋との対戦結果

　これからも、0.5手延長した場合に強くなっているとは言えない（逆に弱い）。

　同じプログラム同士で思考時間に差をつけた場合の勝率の変化を調べる。全幅探索のプログラムは「捨駒なし」で使用する。

思考時間 捨駒なし 勝率 YSS 勝率

　 2倍 58-38-3 0.59 64-36-0 0.64

　 3倍 70-29-1 0.71 77-20-3 0.79

5倍 85-15-0 0.85 91- 9-0 0.91

10倍 84-14-2 0.86 88-12-0 0.88

　思考時間が同じ場合の勝率を0.50としてグラフにしたのが図２である。５倍の思考時間までは、どちらもほぼ比例して勝率が上昇している。またYSSの勝率の方がやや上回っていることより、強いプログラムほど時間に対する勝率が高い、と言えそうである。

Fig. 2: Thinking time and Winning rate

図２　思考時間と勝率

　読みの深さを５に固定した場合の0.5手延長と通常の対局はYSSで76勝24敗、勝率0.76であった。思考時間は0.5手延長側が2.1倍かかっているので3.4の結果から比較すると若干有効に働いているとも考えられる。

　図３に評価関数を呼んだ深さの割合を示す。

これは同じプログラム同士を１局対局させた場合の評価関数を呼んだ深さの割合で、初手から投了までの全ての合計である。制限時間は40秒である。

図３ 評価関数を読んだ深さの割合

Fig. 3: Depth rate of evaluation function

Table 5: Most searched depth and Maximum depth

表５　もっとも数多く探索した深さと、最大探索深さ

　YSSの読みの深さが際だって深い。YSSでは序盤では浅い深さで読みが打ち切られるため、総探索局面の大部分は中盤以降の探索が占める。最大20手の深さまで探索しているのは、0.5手延長の他に王手による延長や駒損変化防止の２手延長が入っているためである。

「捨駒なし0.5手」と「全幅0.5手」では形がいびつである。これは手数が短い、もしくは長いために序盤、終盤のみの影響を受けているためと思われる。

全幅探索のプログラムは将棋では高々5,6手の深さしか読めない。現在のコンピュータの速度では、チェスで成功した「しらみつぶし」での棋力の向上は難しいだろう。が、一方では5,6手まで読めるのであれば評価関数を工夫しさえすれば、ある程度の強さのプログラムは作れる、という事ではある。

　0.5手延長アルゴリズムを用いた場合、勝率は下がりこそすれ、明確に上がることはなかった。全幅探索のモデルでは、延長する手のほとんどが最善の手ではなく、無駄な時間を延長に割いてしまうために逆に弱くなる、と考えられる。YSSでは、ほとんど勝率に変化は見られなかった。結論として効果はほとんどないと言える。棋力向上に効果があったのは評価関数の改良やハッシュテーブルの使用なのであろう。

　全幅探索モデルでは、表面上有効な手しか指さない「捨駒なし」が強かった。将棋では派手な好手を指すプログラムよりも致命的な悪手を指さない安定したプログラムの方が強い、と言える。

本稿で用いた全幅探索のプログラムは以下のホームページからダウンロード出来る。

[1] David Levy, Monty Newborn著, 小谷善行監訳「コンピュータチェス」サイエンス社 1994

[2] 松原仁 編著「コンピュータ将棋の進歩」共立出版 1996

[3] コンピュータ将棋協会資料集 vol.2〜9