将棋ソフトの設定には大抵、「置換表サイズ」(ハッシュメモリ)というのがある。
これは、置換表としてどれだけのメモリを確保するかの設定である。
置換表とは、一度探索した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の倍が(勝率が落ちない)下限値になるだろう。
知性を取るか記憶を取るかという感じに見えます。
知性に極振りすれば端的な結果を得やすいでしょう。
記憶に極振りすれば深い詠みが得られるでしょう。
中途半端は駄目でしょうか？
人間の場合は記憶に振ったほうが楽しいと思いますが、ソルバーであるソフトはどうなんでしょうかね。
ネガティブ定跡でも復活しますか？
> ネガティブ定跡でも復活しますか？
(´ω｀)？
端的な検索になる場合、抜けが出ると思います。
目的の違う小さな置換表を複数持つって感じですか？
置換表は全スレッドで共用しているものが1つしかないです。置換表のエントリーに上書きするときにそこそこ賢い戦略で上書きするかどうかを決めるので、それで問題ないです。詳しくはやねうら王tt.cppのsave()関数をご覧を..。
L3キャッシュのことかな？
以前私も８、１６、３２、６４MBにしても何も変わらない気がするなと思ったことはあります。
> L3キャッシュのことかな？
L3とは限りませんけども。この本文ではL1,L2,L3含めてCPU cacheと呼んでいます。それぞれの役割については以下の記事でも。
http://gigazine.net/news/20160912-cpu-cache-level/
表題とまったく関係ないかもしれませんが、
ＳＭ、技巧、やねうら王共に８００手中１手くらい絶対に検討では出ない悪手を対局で指すことがあります。
８００分の１なら誤差でしょうと思うかもしれませんが、対局数で言えば１０局中１局出ますので気になっています。
もちろん悪手といっても軽微な評価値の差や、大勢が決している終盤で出ても気づかないことがありますが、中盤でタダ駒を打ったり目を疑う手を指すこともあります。
どのソフトでも出るのでＧＵＩの問題なのかなと考えたこともありますが、発生しやすい条件として１手当たりの指し手秒数を５秒とかに固定して、時間になる瞬間に指し手が変わった場合によく出ます。
心当たりがあれば別記事にでもお願いします。
直観的にですが、LAZYSMP 共通の潜在バグ？
がうるさん、よくご存知ですね。PV(読み筋)とNonPV(読み筋以外)とで枝刈りの量が違うんです。時間直前にPVが変わった場合、まだそのPVを十分に読めていないので、そういうことがあります。PVが変わった直後、それを十分読み直すべきなのですが、1手の指し手時間が固定ですとそれが出来なくて、そういう現象が起きやすいです。十分読めていないときにPVを変更すべきかという問題ではありますが、それでも変更したほうが強いようで、Stockfishはそうなっています。
なるほど明確な理由があったんですね。スッキリしました。ありがとうございます。
持ち時間制にすれば問題なさそうですね。
話は全然変わりますが私は、ＳＭ＋新評価関数のスレッド８、１手１０秒に居飛車ではまったく勝てませんが、四間飛車で勝てます。新評価関数って振り飛車に弱くなってませんか？
> 新評価関数って振り飛車に弱くなってませんか？
そのへんは私のほうではさっぱりわかりません。(そもそも将棋盤の画面すら出していなくて、勝率以外は見ていないので)
まあ、特定の戦型で弱くなっていることは十分ありえるでしょうね…。
何と言いますか、新評価関数になってソフトは自分が正しいと言わんばかりに一直線に攻めて来るようになった気がします。
なので一度自分の得意戦法から相手の猛攻を詰むまで受けてみて、何手あくのか、持ち駒は何が手に入るのかを調べ、その条件で相手を詰ませるにはどうすればいいかを逆算します。
一例をあげると、こちらが後手番で立石流四間飛車をやろうとしたら角交換を拒否されて、相銀冠になったパターンです。
1 ７六歩(77)
2 ３四歩(33)
3 ２六歩(27)
4 ４四歩(43)
5 ４八銀(39)
6 ３二銀(31)
7 ５六歩(57)
8 ４二飛(82)
9 ６八玉(59)
10 ６二玉(51)
11 ５七銀(48)
12 ９四歩(93)
13 ９六歩(97)
14 ７二銀(71)
15 ７八玉(68)
16 ７一玉(62)
17 ７七角(88)
18 ３三角(22)
19 ２五歩(26)
20 ４五歩(44)
21 ６六歩(67)
22 ８二玉(71)
23 ８八玉(78)
24 ８四歩(83)
25 ７八銀(79)
26 ７四歩(73)
27 ８六歩(87)
28 ８三銀(72)
29 ５八金(49)
30 ７二金(61)
31 ６七金(58)
32 ７三桂(81)
33 ８七銀(78)
34 ５二金(41)
35 ７八金(69)
36 ４三銀(32)
37 ６五歩(66)
38 ４四銀(43)
39 ６六銀(57)
40 ５四歩(53)
41 ３六歩(37)
42 ６二金(52)
43 ６八角(77)
44 ５五歩(54)
45 ２四歩(25)
46 同 歩(23)
47 同 角(68)
48 ２二飛(42)
49 ３三角成(24)
50 ２八飛成(22)
51 ４四馬(33)
52 ６九飛打
53 ５五馬(44)
54 ２九龍(28)
55 ７九銀打
56 ４九飛成(69)
57 ７五歩(76)
58 同 歩(74)
59 ５七角打
60 ５四歩打
61 １一馬(55)
62 ７六桂打
63 ９八玉(88)
64 ９五歩(94)
65 同 歩(96)
66 ５八龍(49)
67 ７七歩打
68 ９七歩打
69 同 桂(89)
70 ６九龍(29)
71 ７六歩(77)
72 ６七龍(69)
73 ６八香打
74 ５六龍(67)
75 ４四馬(11)
76 ９六歩打
77 同 銀(87)
78 ５三金打
79 同 馬(44)
80 同 金(62)
81 ９四桂打
82 同 香(91)
83 同 歩(95)
84 同 銀(83)
85 ９五香打
86 同 銀(94)
87 同 銀(96)
88 ６九角打
89 ８四銀(95)
90 ７四桂打
91 ８七銀打
92 ８五歩打
93 同 桂(97)
94 同 桂(73)
95 同 歩(86)
96 ８六桂打
97 同 銀(87)
98 同 桂(74)
99 ８七玉(98)
100 ７八桂成(86)
101 ８六玉(87)
102 ５七龍(58)
103 ７四桂打
104 ７一玉(82)
105 ８二金打
106 同 金(72)
107 同 桂成(74)
108 ６二玉(71)
109 ９五玉(86)
110 ８七龍(57)
111 ４二金打
112 ９三香打
113 同 銀(84)
４２手目まではよくある進行です。４３手目で６八角と角の突破を見せてきましたので、そのまま攻めさせます。
４４手目の５五歩が最初の狙いで、相手玉に最も近いと金を作る場所作りです。
５１手目までＳＭは馬を作って角＋銀を取り込み不満無しと言ったところでしょうか。
５２手目で龍が相手玉を睨んでいるので６九飛打で金を取りますよと打ち込み、５５歩を取らせます。これで５八歩打のと金作成の場所が出来ました。
５４手目で龍を逃がしながら桂馬を取り込み、下段に飛車２体という即詰みの形を作り、相駒で銀を消費させます。
５６手目でおそらくソフトは４六歩が出ますが、当初の予定通りと金作成のために４九飛成としておきます。
５７手目が最初のターニングポイントでソフトは自分が＋２００くらいと判断して、５一角打や４四角打と５五馬との挟撃を候補とあげますが、どちらも５八歩打のと金作成でこちらが早く詰ませることが出来ますので、より厳しい７五歩の変化を見て行きます。
５９手目の５七角打がかなりの好手でこちらの玉頭を睨んでいるだけではなく、３九に駒を差し込まれると龍が止まってしまいます。
６０手目はこのまま攻められると負けますので、５四歩打と馬をたたきます。ここでは、同馬、３七馬の変化もありますが、どちらもこちらの勝ちなので、一番厳しい１一馬で見て行きます。
６２手目の７六桂打で同金とする変化もあり、相手の７四歩打＋香打から真っ直ぐ貫かれますが、無視して攻めさせ５八金打で５七の角をやっつけます。こちらの玉がまっ裸になりますが、詰まないので勝てます。
後は端玉銀冠を倒す感じで端攻めと龍を寄せていけば勝勢です。９３手目は後の検討で７三銀のほうが評価値は良かったと思いますが、こちらの玉は全然詰まないので普通に寄せて勝ちです。
なぜ振り飛車のときは居飛車に比べて変化ルートが少ないのかは分かりませんが、昔の評価関数のときのほうが学習が荒いせいか変な手が混ざって翻弄されます。
> 新評価関数になってソフトは自分が正しいと言わんばかりに一直線に攻めて来るようになった気がします。
> 昔の評価関数のときのほうが学習が荒いせいか変な手が混ざって翻弄されます。
へ～。興味深いですね。私のほうでは勝率しか見てないので(棋風はまったくわからないので)大変参考になります。
千田五段からこの棋譜に関するコメントがありました。こちらを先にご覧になった方のために。
——————–
これは魔女+0917の中盤じゃないですね。少なくとも、26手目86歩，33手目87銀に関しては現れることはほぼないでしょう。
かなり進んだ途中図からの対局から、悪い特徴をつついている感じですか。
公開者がかなり詳しいのは確かだと思います。
https://twitter.com/mizumon_/status/779605146531618816
——————–
居飛車なのに振り飛車のキャッシュ持ってても永遠に使いませんわな。
将棋の局面展開は途中合流少ないので、古い置換表持っててもメモリと探索コストの無駄ってことですね。
ちなみにソース読めば分かること聞いてすみませんが、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万のエントリーくらいあったら、逆に使いきるのが困難な気がするのですが、その辺は問題ないのですか？
蓄積よりも上書きのほうが多いでしょうし、なんか飽和してる気がします。
置換表、使い切る必要は全くないのでは…。
層なんですけど、メモリが勿体ない病にかかりそうです。
200MB位の置換表があれば十分なのであれば、もう一個なんか細工を入れれそうな感じがしますね。必要ならばですが。
余ったメモリを違うことに使うといいのでないですか？
ありがとうございます。
たった20万局面では1手の検討中にもガンガン捨てることになりますがそれで大部分足りると言うことですね。
興味深い。
直観的には、1手考慮の2億局面分はほしい気がしますが、腐った枝の先はバッサリ忘れた方がいいと。
しかし、マルチスレッドだとスレッドごとに探索中の深さが違うでしょうし、深さが合わないと局面も合わないことが多いでしょうから、スレッドが増えるほど多目に取らないとヒット率が下がりそうです。
また、単純なFIFOではないんでしょうが、取っておくべきキーポイントの局面というのがあったりするんですかね。
ルートの評価値から双方ベストを尽くした±200点以内とか。
静的には根っこに近い方が再利用率高く、深いほど低いはずですが、動的には今調べてる局面のさっき作った周辺が再利用率高いというのも矛盾ですかね。
> スレッドが増えるほど多目に取らないとヒット率が下がりそうです。
はい、もちろんそうです。
> 取っておくべきキーポイントの局面というのがあったりするんですかね。
rehashのstrategyは以下のようになってます。
https://github.com/yaneurao/YaneuraOu/blob/master/source/tt.cpp#L76
これ、現状の盤面から先の良い手を持っておくのではなく、現状の盤面へ到達するための前の悪い手の方を持っていた方が良いとか、そんなことだったりするのかな？
知らんけどｗ
やねうら王のHashメモリー設定、デフォールトの１６MBで良い、という件ですが私の手元ではまったく異なる実験結果になりましたので一応ご報告いたします。
エンジン：Yaneuraou 4.79 64AVX2 Tournament
評価関数：elmo
設定：一手３秒８スレ(CPU Ryzen 7-1800x), tanuki-互角局面集使用。3000点で投了。
Hash 1024に設定したものと16に設定したものを対局。その他の条件はまったく同じ。
結果：(Hash 1024) 279-26-95 (Hash 16)
レート差173でHashを大きくしたもののほうが圧倒的に強いという結果となりました。
> Ryzen 7-1800x
これ16HTのところ物理コア数である8スレに制限して動かしているということですよね？実質、トータルのnpsは16HT相当分ぐらい出ているはずで、この点において私の想定より多いですし、あとスレッド数が増えてきたときに置換表が潰れてしまっているとLazy SMPでの探索自体が機能しなくなるので、この点でもマイナス。あと、この記事のころと比べると評価関数の質がずいぶん向上しているので、そのへんでも差が出ます。なので、いまuuunuuunさんの条件で計測して、結果がそうであっても、まあ、それはそんなものかなと思います。