コンピューター将棋におけるベストな置換表サイズとは?

将棋ソフトの設定には大抵、「置換表サイズ」(ハッシュメモリ)というのがある。
これは、置換表としてどれだけのメモリを確保するかの設定である。

置換表とは、一度探索したnode(局面)の評価値などを記憶しておいて、再度、そのnodeに訪問したときに、そこ以降の探索を省略するためのものである。

例えば、やねうら王や魔女では新規node(新しく到達した局面=置換表にない局面)で必ず1手詰め判定を行なう。逆に、新規nodeではない(=置換表に存在する局面)ならば、すでに1手詰め判定を行なったことは保証されるので、もしそのnodeに関して詰みのスコアが置換表に書かれていないなら、その局面は1手では詰まない。

1手詰め判定を再度呼び出す必要があるかどうかという観点だけで見ても、置換表は大きければ大きいほどいいように思われる。同じnodeに再訪問したときに情報が失われていると、再度1手詰め判定を呼び出さなければならないからである。

ところが、4スレッド、1手10秒程度の思考時間においては置換表サイズを8MB~32768MBにどのように変化させてみても勝率は1万局程度の対局で計測できるほどの差は産まないのだ。

現実は小説より奇なり、である。

この理由を簡単に説明する。

まず、同じnodeに再訪問するということが実はあまりないのだ。反復深化法で少しずつ探索を深くしていくが、前回に1手詰みを見つけた局面はその2手前の局面から見て3手詰めだったりして、自分にとっての3手詰めは回避しようとするから、そこで枝刈りされる。実際に1手詰めの局面まで再訪問する必要がないのだ。

わかりやすく詰みの局面を例に出したが、詰みでなくとも同様の原理により、前回の反復深化のイテレーションで調べた末端のnodeにまで再訪問はほとんどしないのだ。

なので、置換表のエントリーが多少失われていても問題とならない。しかも、あるnodeの情報が破損していたとしても、そのnodeから1手展開したnode(要するに1手先)については前回のイテレーションで調べているはずだから、ある程度置換表上に情報が残っているはずで、その情報を用いて枝刈り出来ることが多い。

結局、置換表のエントリーが多少破損して(上書きによって失われて)いても、それについてさしたる被害を被るわけではない。

このような理由により、置換表サイズを8MBぐらいにまで小さくしても勝率の低下が確認できない。

「でも大きければ大きいほど、置換表のエントリーが破損する確率が下がるので良いのは良いんでしょ?」

とあなたは言うかも知れない。ところが、それがそうとも言えない。

これには、CPU cacheという問題がある。普通、置換表はSDRAMなどの(CPUの外側にある)メモリに格納される。ところが、一度アクセスしたところは、CPU cacheに読み込まれる。CPU cacheへのアクセスはSDRAMへのアクセスよりは格段に速いので、CPU cacheに載っているとこの恩恵にあずかることが出来る。しかしCPU cacheはそんなに大きくはないので、新しい情報がやってくると古い情報は追い出されてしまう。

そのため、置換表サイズは小さいほうがCPU cacheに載りやすくて高速にアクセスできるというメリットがある。

このへんのバランスが絶妙で、実際、置換表サイズを小さくしたとき、エントリーが破損する確率が上がり探索効率が低下することと、CPU cacheに載ることで高速化できることとがちょうどいい具合に相殺されるのかも知れない。

結局、4スレッド、1手10秒程度の思考時間なら、8MBから32768MBにいたるまで、どのように変えても棋力は変わらない。2MB以下だとさすがに少し勝率が落ちるようである。8MBというのが(勝率が落ちない)下限値だと私は思っている。対局時間やスレッド数を倍にするなら、この8MBの倍が(勝率が落ちない)下限値になるだろう。

コンピューター将棋におけるベストな置換表サイズとは?” への23件のコメント

  1. 知性を取るか記憶を取るかという感じに見えます。
    知性に極振りすれば端的な結果を得やすいでしょう。
    記憶に極振りすれば深い詠みが得られるでしょう。
    中途半端は駄目でしょうか?
    人間の場合は記憶に振ったほうが楽しいと思いますが、ソルバーであるソフトはどうなんでしょうかね。
    ネガティブ定跡でも復活しますか?

      • 端的な検索になる場合、抜けが出ると思います。
        目的の違う小さな置換表を複数持つって感じですか?

        • 置換表は全スレッドで共用しているものが1つしかないです。置換表のエントリーに上書きするときにそこそこ賢い戦略で上書きするかどうかを決めるので、それで問題ないです。詳しくはやねうら王tt.cppのsave()関数をご覧を..。

  2. L3キャッシュのことかな?

    以前私も8、16、32、64MBにしても何も変わらない気がするなと思ったことはあります。

  3. 表題とまったく関係ないかもしれませんが、
    SM、技巧、やねうら王共に800手中1手くらい絶対に検討では出ない悪手を対局で指すことがあります。
    800分の1なら誤差でしょうと思うかもしれませんが、対局数で言えば10局中1局出ますので気になっています。
    もちろん悪手といっても軽微な評価値の差や、大勢が決している終盤で出ても気づかないことがありますが、中盤でタダ駒を打ったり目を疑う手を指すこともあります。
    どのソフトでも出るのでGUIの問題なのかなと考えたこともありますが、発生しやすい条件として1手当たりの指し手秒数を5秒とかに固定して、時間になる瞬間に指し手が変わった場合によく出ます。
    心当たりがあれば別記事にでもお願いします。

    • がうるさん、よくご存知ですね。PV(読み筋)とNonPV(読み筋以外)とで枝刈りの量が違うんです。時間直前にPVが変わった場合、まだそのPVを十分に読めていないので、そういうことがあります。PVが変わった直後、それを十分読み直すべきなのですが、1手の指し手時間が固定ですとそれが出来なくて、そういう現象が起きやすいです。十分読めていないときにPVを変更すべきかという問題ではありますが、それでも変更したほうが強いようで、Stockfishはそうなっています。

      • なるほど明確な理由があったんですね。スッキリしました。ありがとうございます。
        持ち時間制にすれば問題なさそうですね。

        話は全然変わりますが私は、SM+新評価関数のスレッド8、1手10秒に居飛車ではまったく勝てませんが、四間飛車で勝てます。新評価関数って振り飛車に弱くなってませんか?

        • > 新評価関数って振り飛車に弱くなってませんか?

          そのへんは私のほうではさっぱりわかりません。(そもそも将棋盤の画面すら出していなくて、勝率以外は見ていないので)
          まあ、特定の戦型で弱くなっていることは十分ありえるでしょうね…。

      • 何と言いますか、新評価関数になってソフトは自分が正しいと言わんばかりに一直線に攻めて来るようになった気がします。
        なので一度自分の得意戦法から相手の猛攻を詰むまで受けてみて、何手あくのか、持ち駒は何が手に入るのかを調べ、その条件で相手を詰ませるにはどうすればいいかを逆算します。
        一例をあげると、こちらが後手番で立石流四間飛車をやろうとしたら角交換を拒否されて、相銀冠になったパターンです。

        1 7六歩(77)
        2 3四歩(33)
        3 2六歩(27)
        4 4四歩(43)
        5 4八銀(39)
        6 3二銀(31)
        7 5六歩(57)
        8 4二飛(82)
        9 6八玉(59)
        10 6二玉(51)
        11 5七銀(48)
        12 9四歩(93)
        13 9六歩(97)
        14 7二銀(71)
        15 7八玉(68)
        16 7一玉(62)
        17 7七角(88)
        18 3三角(22)
        19 2五歩(26)
        20 4五歩(44)
        21 6六歩(67)
        22 8二玉(71)
        23 8八玉(78)
        24 8四歩(83)
        25 7八銀(79)
        26 7四歩(73)
        27 8六歩(87)
        28 8三銀(72)
        29 5八金(49)
        30 7二金(61)
        31 6七金(58)
        32 7三桂(81)
        33 8七銀(78)
        34 5二金(41)
        35 7八金(69)
        36 4三銀(32)
        37 6五歩(66)
        38 4四銀(43)
        39 6六銀(57)
        40 5四歩(53)
        41 3六歩(37)
        42 6二金(52)
        43 6八角(77)
        44 5五歩(54)
        45 2四歩(25)
        46 同 歩(23)
        47 同 角(68)
        48 2二飛(42)
        49 3三角成(24)
        50 2八飛成(22)
        51 4四馬(33)
        52 6九飛打
        53 5五馬(44)
        54 2九龍(28)
        55 7九銀打
        56 4九飛成(69)
        57 7五歩(76)
        58 同 歩(74)
        59 5七角打
        60 5四歩打
        61 1一馬(55)
        62 7六桂打
        63 9八玉(88)
        64 9五歩(94)
        65 同 歩(96)
        66 5八龍(49)
        67 7七歩打
        68 9七歩打
        69 同 桂(89)
        70 6九龍(29)
        71 7六歩(77)
        72 6七龍(69)
        73 6八香打
        74 5六龍(67)
        75 4四馬(11)
        76 9六歩打
        77 同 銀(87)
        78 5三金打
        79 同 馬(44)
        80 同 金(62)
        81 9四桂打
        82 同 香(91)
        83 同 歩(95)
        84 同 銀(83)
        85 9五香打
        86 同 銀(94)
        87 同 銀(96)
        88 6九角打
        89 8四銀(95)
        90 7四桂打
        91 8七銀打
        92 8五歩打
        93 同 桂(97)
        94 同 桂(73)
        95 同 歩(86)
        96 8六桂打
        97 同 銀(87)
        98 同 桂(74)
        99 8七玉(98)
        100 7八桂成(86)
        101 8六玉(87)
        102 5七龍(58)
        103 7四桂打
        104 7一玉(82)
        105 8二金打
        106 同 金(72)
        107 同 桂成(74)
        108 6二玉(71)
        109 9五玉(86)
        110 8七龍(57)
        111 4二金打
        112 9三香打
        113 同 銀(84)

        42手目まではよくある進行です。43手目で6八角と角の突破を見せてきましたので、そのまま攻めさせます。
        44手目の5五歩が最初の狙いで、相手玉に最も近いと金を作る場所作りです。
        51手目までSMは馬を作って角+銀を取り込み不満無しと言ったところでしょうか。
        52手目で龍が相手玉を睨んでいるので6九飛打で金を取りますよと打ち込み、55歩を取らせます。これで5八歩打のと金作成の場所が出来ました。
        54手目で龍を逃がしながら桂馬を取り込み、下段に飛車2体という即詰みの形を作り、相駒で銀を消費させます。
        56手目でおそらくソフトは4六歩が出ますが、当初の予定通りと金作成のために4九飛成としておきます。
        57手目が最初のターニングポイントでソフトは自分が+200くらいと判断して、5一角打や4四角打と5五馬との挟撃を候補とあげますが、どちらも5八歩打のと金作成でこちらが早く詰ませることが出来ますので、より厳しい7五歩の変化を見て行きます。
        59手目の5七角打がかなりの好手でこちらの玉頭を睨んでいるだけではなく、3九に駒を差し込まれると龍が止まってしまいます。
        60手目はこのまま攻められると負けますので、5四歩打と馬をたたきます。ここでは、同馬、3七馬の変化もありますが、どちらもこちらの勝ちなので、一番厳しい1一馬で見て行きます。
        62手目の7六桂打で同金とする変化もあり、相手の7四歩打+香打から真っ直ぐ貫かれますが、無視して攻めさせ5八金打で5七の角をやっつけます。こちらの玉がまっ裸になりますが、詰まないので勝てます。
        後は端玉銀冠を倒す感じで端攻めと龍を寄せていけば勝勢です。93手目は後の検討で7三銀のほうが評価値は良かったと思いますが、こちらの玉は全然詰まないので普通に寄せて勝ちです。

        なぜ振り飛車のときは居飛車に比べて変化ルートが少ないのかは分かりませんが、昔の評価関数のときのほうが学習が荒いせいか変な手が混ざって翻弄されます。

        • > 新評価関数になってソフトは自分が正しいと言わんばかりに一直線に攻めて来るようになった気がします。
          > 昔の評価関数のときのほうが学習が荒いせいか変な手が混ざって翻弄されます。

          へ~。興味深いですね。私のほうでは勝率しか見てないので(棋風はまったくわからないので)大変参考になります。

        • 千田五段からこの棋譜に関するコメントがありました。こちらを先にご覧になった方のために。
          ——————–
          これは魔女+0917の中盤じゃないですね。少なくとも、26手目86歩,33手目87銀に関しては現れることはほぼないでしょう。
          かなり進んだ途中図からの対局から、悪い特徴をつついている感じですか。

          公開者がかなり詳しいのは確かだと思います。

          https://twitter.com/mizumon_/status/779605146531618816
          ——————–

  4. 居飛車なのに振り飛車のキャッシュ持ってても永遠に使いませんわな。
    将棋の局面展開は途中合流少ないので、古い置換表持っててもメモリと探索コストの無駄ってことですね。
    ちなみにソース読めば分かること聞いてすみませんが、2MBの置換表って何局面分なんでしょうか?
    1局面320ビットくらいで5万局面?

    • > 2MBの置換表って何局面分なんでしょうか?

      やねうら王/魔女/Aperyは、1 TTEntry(≒1局面)が10バイトで、それを3つ組にしてTTClusterとしています。このときにCPUのcache lineに載せるために2バイトpaddingして1 TTCluster 32バイトにしています。これは、rehash用です。(TTEntryのsave()のときに、すでにTTEntryが使われていたら、TTCluster内の他のTTEntryを用いるの意味) そんなわけで、2MB / 32 = 64K TTClusterですので、いっぱいまで書き込むとしたら、65536×3局面分だと思って良いのではないでしょうか。

      • 人間的な感覚で言うと、1000万のエントリーくらいあったら、逆に使いきるのが困難な気がするのですが、その辺は問題ないのですか?
        蓄積よりも上書きのほうが多いでしょうし、なんか飽和してる気がします。

      • ありがとうございます。
        たった20万局面では1手の検討中にもガンガン捨てることになりますがそれで大部分足りると言うことですね。
        興味深い。

        直観的には、1手考慮の2億局面分はほしい気がしますが、腐った枝の先はバッサリ忘れた方がいいと。

        しかし、マルチスレッドだとスレッドごとに探索中の深さが違うでしょうし、深さが合わないと局面も合わないことが多いでしょうから、スレッドが増えるほど多目に取らないとヒット率が下がりそうです。

        また、単純なFIFOではないんでしょうが、取っておくべきキーポイントの局面というのがあったりするんですかね。
        ルートの評価値から双方ベストを尽くした±200点以内とか。

        静的には根っこに近い方が再利用率高く、深いほど低いはずですが、動的には今調べてる局面のさっき作った周辺が再利用率高いというのも矛盾ですかね。

  5. これ、現状の盤面から先の良い手を持っておくのではなく、現状の盤面へ到達するための前の悪い手の方を持っていた方が良いとか、そんなことだったりするのかな?
    知らんけどw

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です