「YSS 7.0」 --- そのデータ構造、及びアルゴリズムについて ---

山下 宏

私が将棋プログラムに興味を持ったのは1987年の頃であった。当時、古本屋で見つけた1984年発売の「MICRO」という雑誌に掲載されていた将棋プログラム「ESS」 *[9] の記事を読み、以後、将棋プログラム「YSS(Yamashita Shogi System)」を作りはじめた。そして1991年の第2回コンピュータ将棋選手権 *[8] に初参加。以降、連続で参加し、5,4,4,3,4位の後、1997年2月の第7回選手権において「YSS 7.0」が金沢将棋2の5連覇を阻止して初優勝した。
以下では「YSS 7.0」の仕組みと、優勝のきっかけとなった探索アルゴリズムについて説明する。なお、「YSS 7.0」は1997年4月アスキーサムシンググッドより「AI将棋2」として発売されている。

       歩    香    桂    銀    金    角    飛  
        1     2     3     4     5     6     7  
 王    と  成香  成桂  成銀    --    馬    龍  
  8     9    10    11    12    13    14    15  

/* スタックの内容 */
kn_stoc[1][0] = 0 （未使用）
kn_stoc[1][1] = 25
kn_stoc[1][2] = 33
kn_stoc[1][3] = 36
kn_stoc[1][4] = 27  使われていない歩は４枚

kn_stn[1] = *kn_stoc[1][4] (を示している）

より、

kn[27][0] = 0x01      駒番号27番は先手の歩になる
kn[27][1] = 0x76      その位置は 0x76 (=47歩)
kn_stn[1]--           スタックを減らす。[1]は歩、[2]は香車になる

となる。

追記：2004年03月07日

失敗した、と今では思っていることに先手、後手の駒の種類に
フラグを立てていなかったことがあります。 

YSSでは先手の歩〜王を0x01-0x07、後手を0x81-0x87、盤外を0xff、空白を0x00としているのですが 
駒が動けるか、の判定は 
if ( board[z] < 0x80 && board[z] != 0 ) 先手は動けない 
if ( board[z] > 0x80　　　　　　　　　) 後手は動けない 
となります。 

もし先手を歩〜王を0x11-0x17としておけば、後手を0x21-0x27、盤外を0x40とかにしておけば 
if ( board[z] & (0x40 | 0x10) ) 先手の駒は動けない 
if ( board[z] & (0x40 | 0x20) ) 後手の駒は動けない 
と先手も一度の判定で済みます。 


表２  主な YSS のデータ構造用の配列（型は全て int)

ban[256]       その位置にある駒の駒番号。
init_ban[256]  その位置にある駒の種類
               (何もないときは 0、盤外は 0xff、先手の駒は0x01〜0x0f,後手の駒は0x81〜0x8f)
mo_m[8]        MAN（先手）の持ち駒の数。
mo_c[8]        COM（後手）の持ち駒の数。
kiki_m[256]    その位置におけるMANの利きの数。
kiki_c[256]                    COM
kb_m[256][32]  その位置におけるMANの利きの内容（どういった駒が利いているか）。
               なお、利きの最大数は18である。
kb_c[256][32]
kn[41][2]      駒番号のテーブル。[][0]...駒の種類、[][1]...駒の位置。
kn_stoc[8][32] 駒の種類別の空いている駒番号。
*kn_stn[8]     上の配列用のポインタ。

sasite[64][64][8]  各深さにおける指し手。64手先まで読み、64手まで生成。手の情報の他に仮評価などが入る。
saizen[64][64][4]  最善応手手順を記憶 最大深さ64。
                   手は移動元、移動先、取った(打った)駒の種類、成りフラグの４つで表す。
ret_fukasa[64]     評価値の決定した深さを記録
fukasa_add         探索限界深さの小数点部分
depth_max          探索深さ限界
*tejun[64]         今までの手順が入ったポインタ。sasite[][][] の場所を示す。

Ｃ言語では、配列の添字に２のべき乗を使うと、内部計算がビットシフトで表現され 高速化されるので、配列はすべて２のべき乗にするとよい。

                図１

kiki_c[0x62]  = 3;         利きの数は３。
kb_c[0x62][0] = 26;        26番の歩が利いている。
kb_c[0x62][1] =  3 + 0x80;  3番の飛が利いている（間接なので0x80を足している）。
kb_c[0x62][2] = 19 + 0x80; 19番の香が利いている（間接なので0x80を足している）。

            再掲、図１

                            図２

                  図３

表３ 駒の価値

                歩   香   桂   銀   金   角   飛
基本価値       100  430  450  640  690  890 1040
駒が成る価値   320  200  190   30    0  260  260
持駒の付加価値  15   50   60   80   90  220  230

駒交換用(基本) 200  860  900 1280 1380 1780 2080
        (成駒) 520 1060 1090 1310    0 2040 2340

−−−  表４  −−−

先手の玉に対する後手の駒の相対位置による増減割合。Ｘ軸については対称である。
        0   1   2   3   4   5   6   7   8 (Ｘ距離)

  +8   50  50  50  50  50  50  50  50  50
  +7   50  50  50  50  50  50  50  50  50
  +6   62  60  58  52  50  50  50  50  50
  +5   80  78  72  67  55  51  50  50  50
  +4  100  99  95  87  78  69  50  50  50
  +3  140 130 110 100  95  75  54  50  50
  +2  170 160 142 114  98  80  62  55  50  <--- ２段真上を最大とする。
  +1  170 165 150 121  94  78  58  52  50
   0  170 145 137 115  91  75  57  50  50  <--- 中心。左隅(0 0)に王がいるとする
  -1  132 132 129 102  84  71  51  50  50
  -2  100  97  95  85  70  62  50  50  50
  -3   90  85  80  68  60  53  50  50  50
  -4   70  66  62  55  52  50  50  50  50
  -5   54  53  51  50  50  50  50  50  50
  -6   50  50  50  50  50  50  50  50  50
  -7   50  50  50  50  50  50  50  50  50
  -8   50  50  50  50  50  50  50  50  50

(Ｙ距離)

−−−  表５  −−−

人間王に対する人間駒の価値

        0   1   2   3   4   5   6   7   8 (Ｘ距離)

  +8   50  50  50  50  50  50  50  50  50
  +7   56  53  50  50  50  50  50  50  50
  +6   64  61  55  50  50  50  50  50  50
  +5   79  77  70  65  54  51  50  50  50
  +4  100  99  95  87  74  58  50  50  50
  +3  116 117 101  95  88  67  54  50  50
  +2  131 129 124 114  90  71  59  51  50
  +1  137 138 132 116  96  76  61  53  50
   0  142 142 136 118  98  79  64  52  50  <--- 中心
  -1  132 132 129 109  95  75  60  51  50
  -2  121 120 105  97  84  66  54  50  50
  -3   95  93  89  75  68  58  51  50  50
  -4   79  76  69  60  53  50  50  50  50
  -5   64  61  55  51  50  50  50  50  50
  -6   56  52  50  50  50  50  50  50  50
  -7   50  50  50  50  50  50  50  50  50
  -8   50  50  50  50  50  50  50  50  50

(Ｙ距離)

−  図５  −

後手の持駒：飛  桂  歩二  
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香 ・ ・ ・ 銀v飛 ・v桂v香| 一 -324 -303 -262 -207 -103  -34  -20    0  -20
| ・ ・ ・ ・v銀 金 ・ ・ ・| 二 -269 -248 -200 -110   13  200  220  220  220
|v歩 ・ ・ ・ ・ ・ ・v玉v歩| 三 -158 -144 -158  -62  103  255  310  483  310
| ・v歩 銀v歩v歩 ・ 歩v歩 ・| 四   -6    0   -6  -34  144  345  448  483  448
| ・v桂 金 ・ ・v歩 金 ・ ・| 五  117  110  117    6   96  289  414  483  414
| ・ ・ ・ 歩 歩 ・ ・ 銀 ・| 六  200  213  200  165   96   69  207  276  207
| 歩 歩 ・ 金 ・ 歩 ・ ・ 歩| 七  262  255  262  220  110  -27   -6    0   -6
| ・ 玉 ・ ・ ・ ・ ・v馬 角| 八  289  289  289  248  124  -13 -144 -138 -151
| 香 桂 ・ ・ ・ ・ ・ ・ 香| 九  220  220  220  200   62  -34 -172 -262 -276
+---------------------------+
先手の持駒：歩二

自玉の近くの点数は高すぎるので、現在は＋を3分の1の値まで下げています。
また自玉の近くの金銀の枚数が4枚以上は減点されるようにしています。

Singular Extensionsはちょっと誤解していました。
末端だけで突出した手を1手延長するのではなく、深さが浅いところでも全て突出しているかどうか、を調べる方法です。

・正確な評価値、v がわかっているPVノード(Principal Variation）では それ以外のノードを v - S 、という
  マージン(S)をつけた値でNull Window探索。残りのノードが全て悪いことが分かれば延長。

・正確な評価値が分からず、上から伝えられたαβの範囲を上に超えてしまう場合。
  （Maxノードではβ以上、Minノードではα以下の値が返って来る場合。Fail-High）
  通常はこの1手ですぐに枝刈りされるのですが、この手がSingular、であることを示すために
  残りの手に対しても探索を行います。ただ普通の深さで読むとMinMax探索になってしまって効率が悪すぎるので
  Maxノードならば β - Sh というマージン(Sh)で読みの深さを r だけ減らした D - r の探索を行い、
  残りのノードが全て悪いことを確認します。

CHIPTEST(DEEP BLUEの前のDEEP THOUGTのそのまた前のバージョン）では
マージン(S)はポーン4分の1（25点）でマージン(Sh)はポーン4分の3(75点）を使い、
読みを減らすrは r=2 という値を使って2手浅い探索をしています。

詳しくは原論文を参照のこと。
T.S. Anantharman, M.S. Campbell, F.-h. Hsu,
 Singular extensions: Adding selectivty to brute-force searching,
Artificail Intelligence 43 (1) (1990) 99-110
または、
ICCA Journal, Vol. 11, No. 4, (1988) p. 135-143

−表６−

深さ  時間  最大
----------------
 2 |  1.04   3 |
 3 |  1.14   5 |
 4 |  1.28   7 |
 5 |  1.46   9 |
 6 |  1.70  11 |
 7 |  2.00  13 |
 8 |  2.35  15 |
 9 |  2.79  17 |
10 |  3.32  19 |
----------------
分岐数20で、１手のみ 0.5手延長した場合のかかる時間と最大探索深さ

現在のYSSでは最善手が入れ替わるたびにもう一度0.5手延長しなおす方法＋多重反復深化（この局面から後5手探索するのに、 ハッシュに4手前の結果がなかったら、そこから深さ1,2,3,4,5と反復深化させる）を組み合わせています。
最善手が切り替わった場合に深く読めるかどうかが0.5手延長では重要なのではないかと思います。

欠点としては全ての手を探索する局面では0.5手延長も意味が大きいのですが、 1手だけ探索してその手で枝刈りが起こる場合、最善手である確率が低い（浅い探索での最善手に過ぎない） にも関わらず0.5点延長をかけていることです。

進歩の２では校正の段階で効果があったことを追加したのですが、こっちには反映させてませんでした。 下は1手1秒での自己対戦の結果です。

--- 連続対戦 1168_half_ext_0 - YSS 11.68, 対戦数=1000 --- 2004-02-17 12:34:32
679: 居左 144手で YSS 11.68 の勝, (YSS 11.68 の454勝225敗) YSS=01:59,02:31,(1329:21,1189:05)
0.5手延長なし。ありが圧勝！勝率=0.67。もっともかなり特化されてるので微妙だが。

--- 連続対戦 YSS 11.69b - 1169b_half_ext_1, 対戦数=1000 --- 2004-02-20 10:19:24
178: 居左 66手で 1169b_half_ext_1 の勝, (1169b_half_ext_1 の89勝89敗) YSS=00:58,00:43,(182:22,203:54)
完全0.5手と通常0.5手では差異は見られない。

上の結果では分かりにくいのでまとめますと、まず、以下の3種類を比較してます。

1. 完全0.5手延長(前回の最善手は最初から0.5手延長して、途中で切り替わった最善手も再度0.5手延長しなおす）
2. 通常0.5手延長(前回の最善手だけ0.5手延長して、途中で切り替わった最善手はそのまま）
3. 0.5手延長なし。文字通り延長しない。

そして結果は、
完全0.5手 − 0.5手延長なし 454勝225敗 勝率 0.67
完全0.5手 − 通常0.5手延長 89勝 89敗 勝率 0.50

ちょっと通常0.5手の検証回数が少ないのですが、0.5手延長をかけた方が明確に勝ち越してます。 もっとも内部では0.5手延長されてる時は詰将棋を少し深く読む、とか特化されている部分があるので これだけで絶対に効果がある、とは言えないですが。そもそも完全0.5手延長で強くなるように 調整してきたので、その影響も大きいと思います。

−  表７  −
深さ ％
 0: 0.0:
 1: 0.0:
 2: 0.0:
 3: 0.2:
 4: 0.5:
 5: 1.2:**
 6: 3.3:******
 7:10.7:*********************
 8:21.0:*****************************************
 9:25.7:***************************************************
10:20.3:****************************************
11:10.1:********************
12: 3.9:*******
13: 1.7:***
14: 0.9:*
15: 0.4:
16: 0.1:
17: 0.0:
18: 0.0:
19: 0.0:
20: 0.0:

手数=140,総探索局面=78436893、総思考時間 = 37分30秒(2250)。
基本深さ８、40秒で打ち切り(CPU Alpha500MHz)。

図７  − 通常のαβ法で用いる max 関数 −

int f_max( int alpha, int beta )
{
    if ( depth >= depth_max ) return(評価値);

    指し手を生成する。

    for ( i=0 ; i < 生成した手数 ; i++ ) {

        手を進める
        depth++;

        k = f_min( alpha, beta );

        手を戻す
        depth--;

        if ( k > alpha ) alpha = k;
        if ( alpha >= beta ) return(alpha);
    }

    return(alpha);
}


図８  − YSS で用いている min 関数 −

int f_min( int alpha, int beta )
{
    この局面から後何手探索するかでハッシュテーブルをチェック。
    探索済み、又は上限値がα以下ならば評価値が決定した深さとその最善手を返して終了。

    if ( depth >= depth_max && 王手ではない ) {
        評価値が決定した深さを設定。
        評価関数に、取れそうな駒の点を付加して終了。
    }

    if ( 王手である ) 受ける手を生成。
    else {
        １手詰を調べる。
        残りの探索深さの大きさにより詰将棋を呼ぶ。
        直前に移動した駒を取る手を生成。
        駒を取る手を生成。
        １手パスして相手の最善手を求め、それを防ぐ手を生成。
        その他の指し手を生成。
    }

    同一手をカット。
    前回の最善手を先頭に持ってくる。
    この局面で２手延長するべきか判定する。

    for ( i=0 ; i < 生成した手数 ; i++ ) {

        手を進める
        depth++;

        if ( i==0 ) depth_max += 0.5;

        k = f_max( alpha, beta );
        
        if ( k < beta && ２手延長する ) {
            depth_max += 2;
            k = f_max( alpha, beta );
            depth_max -= 2;
        }

        手を戻す
        depth--;

        if ( k < beta ) {
            beta = k;
            評価値が決定した深さをコピー。
            最善応手手順をコピー。
        }

        if ( i==0 ) depth_max -= 0.5;

        if ( alpha >= beta ) {
            ハッシュテーブルに登録。
            return(beta);
        }
    }

    王手が解除されていない時は打ち歩詰めをチェック。
    if ( 一度でもbeta値が更新された ) ハッシュに登録。

    return(beta);
}

−表８−

ハッシュテーブルに登録する値

 1. ハッシュコード 64 bit
 2. 持ち駒コード（後手の持ち駒の枚数）32 bit
 3. 思考用評価値（上限、下限、正確な値）
 4. 評価値が上限か、下限か、又は正確な値かを示すフラグ
 5. 探索深さ（この局面から何手読んだか）256の倍数で小数点を表す
 6. 先手用詰将棋の相対的な探索深さ
 7. 先手用詰将棋の評価値（詰、打歩詰、不明、切れ）
 8. 後手用詰将棋の相対的な探索深さ
 9. 先手用詰将棋の評価値（詰、打歩詰、不明、切れ）
10. 最善手

後手の持駒：金　歩三　
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香v桂v玉v金v香 ・ ・ ・v香|一
| ・ ・v銀 ・ ・ ・ ・ ・ ・|二
|v歩v歩v歩v歩v飛 ・ ・v歩v歩|三
| ・ ・ ・ ・ 桂 角 ・ ・ ・|四
| ・ ・ ・ 桂 歩v歩 ・ 歩 ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| 歩 歩 ・ 金v歩 歩 歩 ・ 歩|七
| ・v馬 ・ ・ ・ 銀 ・ ・ ・|八
| 香 ・ ・ 玉 ・ ・ ・v全 ・|九
+---------------------------+
先手の持駒：飛　金　銀　桂　
先手：YSS
後手：極

上の書き方は嘘がありました。▲71銀▽同金と指した後に、▲72金、と指した手が評価値を更新しようとしている場合に その手のみを2手延長しています。現在ではNullWindowで探索して評価値が更新するかどうかだけを確認し、 またいきなり2手も延長するのではなく、1手延長して評価が下がらないかを確認してから2手延長しています。 また、▲79銀が既に前回の最善手である場合には（もう有効なことが判明した）と考えて2手延長はしません。
にしても2手延長は重すぎます。ほとんどの無意味駒捨てを防げますし、駒を捨てた後に新たに駒当たりが発生する、といった場合にも 多少は有効だったりするのですが、・・・やはり重すぎです。 将皇の佐藤健一さんがWebで公開されている類似局面を利用した方法のほうが 優秀だと思います。

2手の交換をする前の最善手順を利用した地平線効果の判定は読みが浅い段階では かなり有効なのですが、読みが深くなるとやはり無理がたくさん出てきます。 歩を叩いたために歩切れで最善手順中の自分の歩が打てない場合、 歩を叩いて同〜と取らせたために相手の合駒が出来なくなる場合、 など、双方の手が指せななるケースでも一概に地平線を判定するのは難しいと思います。 鶴岡さんがCSAの例会で発表されていた相手の手を1手、に固定してNullWindowで試す、とかが効果がありそうですがどうでしょう。

ちなみに謎的将棋の高橋さんの指摘によると図９の局面は実は詰があるそうです。 ▲62銀、▲53角成、どちらでも長手順の詰があります。

  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
| ・ ・ ・ ・ ・ ・ ・v玉v香|一
| ・ ・ ・ ・ ・ 龍 ・ ・ ・|二
| ・ ・ ・ ・ ・ ・ ・ ・ ・|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五

図11

題名：第29手、△４四歩に▲５五銀です。
後手：YSS
後手の持駒：角  
  ９ ８ ７ ６ ５ ４ ３ ２ １    
+---------------------------+   
|v香v桂 ・ ・ ・ ・ ・v桂v香| 一
| ・v飛 ・v銀 ・v金v金v玉 ・| 二
|v歩 ・v歩 ・v歩 ・v銀v歩v歩| 三
| ・v歩 ・v歩 ・v歩v歩 ・ ・| 四
| ・ ・ ・ ・ 銀 ・ ・ 歩 ・| 五
| ・ ・ 歩 歩 歩 ・ ・ ・ ・| 六
| 歩 歩 銀 ・ ・ 歩 歩 ・ 歩| 七
| ・ ・ 金 ・ 金 ・ ・ 飛 ・| 八
| 香 桂 玉 ・ ・ ・ ・ 桂 香| 九
+---------------------------+   
先手：金沢将棋
先手の持駒：角  

図12

題名：第63手、△５二銀に▲７五歩です。
後手：YSS
後手の持駒：角  銀  桂  
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香 ・ ・ ・ ・ ・ ・v桂v香| 一
| ・ ・ ・ ・v銀v飛v金v玉 ・| 二
|v歩 ・ ・ ・ ・ ・ ・v歩v歩| 三
| ・v歩v歩v歩v歩 ・ 歩 ・ ・| 四
| ・v桂 歩 ・ ・v歩 ・ 歩 ・| 五
| ・ 銀 ・ 歩 歩 ・ ・ 銀 ・| 六
| 歩 歩 ・ 金 ・ 歩 ・ ・ 歩| 七
| ・ 玉 金 ・ ・ ・ ・ 飛 角| 八
| 香 桂 ・ ・ ・ ・ ・ ・ 香| 九
+---------------------------+
先手：金沢将棋
先手の持駒：金  歩  

図13

題名：第87手、△４一飛に▲４二金打です。
後手：YSS
後手の持駒：飛  桂  歩二  
  ９ ８ ７ ６ ５ ４ ３ ２ １
+---------------------------+
|v香 ・ ・ ・ 銀v飛 ・v桂v香| 一
| ・ ・ ・ ・v銀 金 ・ ・ ・| 二
|v歩 ・ ・ ・ ・ ・ ・v玉v歩| 三
| ・v歩 銀v歩v歩 ・ 歩v歩 ・| 四
| ・v桂 金 ・ ・v歩 金 ・ ・| 五
| ・ ・ ・ 歩 歩 ・ ・ 銀 ・| 六
| 歩 歩 ・ 金 ・ 歩 ・ ・ 歩| 七
| ・ 玉 ・ ・ ・ ・ ・v馬 角| 八
| 香 桂 ・ ・ ・ ・ ・ ・ 香| 九
+---------------------------+
先手：金沢将棋
先手の持駒：歩二

参考文献

[1] David Levy, Monty Newborn著, 小谷善行監訳「コンピュータチェス」サイエンス社 1994
[2] 松原仁 編著「コンピュータ将棋の進歩」共立出版 1996
[3] 小谷善行、他「コンピュータ将棋」サイエンス社 1990
[4] Avron Barr 他「人工知能ハンドブック（第１巻）」共立出版 1983
[5] P.H.ウィンストン 長尾真 他訳「人工知能」培風館 1980
[6] Stephen K.Park, Keith W.Miller 西村恕彦訳「乱数生成系で良質なものはほとんどない」bit 1993年4月号
[7] 近藤嘉雪 「Ｃプログラマのためのアルゴリズムとデータ構造」ソフトバンク 1992
[8] コンピュータ将棋協会資料集 vol.2〜9
[9] 若林宏「将棋プログラム"ESS"」 MICRO 1984年3月号