先日の電竜戦、長時間マッチで現れたやねうら王のバグについて

投稿日時: 2021年8月17日投稿者: やねうらお

二日前に電竜戦 dlshogiと水匠の長時間マッチが開催された。

最高峰将棋AIによる長時間対局、プロ棋士3名が解説 : https://yaneuraou.yaneu.com/2021/08/03/long-time-game-by-the-best-shogi-ai/

イベント的には大成功で、多くのニュースメディアでも取り上げていただいたようである。

水匠のバグについて

さて、その1局目で水匠がバグと思わしき読み筋が現れた。成れないところに飛車を成るというものだ。水匠の読みの錯覚であり、それによって大きく形勢を損ねて敗北を喫した。

水匠 vs dlshogi、先手番をともに制す(コンピュータ将棋協会blog) : http://blog.computer-shogi.org/denryu-sen_channel_opening-matches_and_conference/

水匠の探索部はほぼやねうら王であり、このバグはやねうら王でも生じるものであった。それも、どうも1年以上前から存在するバグのようである。非合法手を指すというものではなく、非合法手を読み筋のなかで読んでいるので、その通りに進行するとかなりの確率で形勢を損ねるというものだ。

原因はこれらではない

まず、プログラムのわからない人向けにまず大雑把に、これらの原因ではないというものを書いておく。

指し手生成のバグ(ここにバグがあれば、自己対局の時にassert(正当性のチェック)に引っかかるので気づく)
合法手判定のバグ(ここにバグがあれば、探索開始局面で非合法手を指すのでレーティング計測の自己対局の時にエラーになるので気づく)
並列化のバグ(LazySMPを採用しているので並列化のバグは起きにくい)
変数の未初期化のバグ(これも何十万局と自己対局させているので、この手のバグがあるとアクセス違反等で落ちるので普通気づく)

なんとかちゃんねるでは、1から4のいずれかが原因ではないかと推測する人たちがわりと多かったわけであるが、全部ハズレである。私に言わせれば、そんなところにバグが残っているはずがないのである。

いつこのバグが現れるのか？

このバグは本来、滅多に現れない。たぶん通常の(15分切れ負け)対局を数万回ぐらいやって、読み筋がおかしいことが1度あるかないかぐらいの確率だと思う。

それが何故、こんな大一番で生じたのであろうか。

これには、原因が4つある。

１つ目は、このバグは、メモリが逼迫している時(or 長時間思考させて置換表(調べた局面を保存しておく表)のメモリが枯渇した時)に現れやすいということである。本局のように長時間マッチだとこの条件に当てはまる。

２つ目は、この手のバグは確率的に生じる事象であるため、たくさんの局面を読めば読むほど現れる確率は上がるということである。本局は長時間マッチなので、この条件にも当てはまる。

３つ目は、dlshogi側は、自己対局によって教師棋譜を生成する時に、他のソフトとリーグ対局も行っており、そのソフトのなかにやねうら王系のソフトも含まれているということである。つまり、dlshogiはやねうら王系に対して勝率の高い局面に誘導するように序盤を学習している可能性がある。本局は双方定跡なしでの対局であったため、モロにそれを食らった可能性がある。

４つ目は、このバグの罪深いところであるが、成れないところに飛車を成るので評価値が爆上がりするのである。爆上がりするので、当然そこを目指して対局を進行させてしまう。成りを錯覚するバグは将棋ソフトでは非常に罪が重いのである。

そんなわけで、わりと必然的にこのバグが大一番で発覚したという風に私は考えている。

このバグがどれくらい発見しにくいのか

読み筋がおかしいという報告はここ1年で数件あったのだが、再現性に乏しく、私の手元の環境では再現させることができなかった。また、やねうら王のソースコードはオープンソースであり、公開されていて多くの開発者にも利用(改造・改良)されている状況なのだが、1年以上に亘り、誰もこのバグを発見することができなかった。

そのくらいこのバグは発見しにくく、複雑な挙動の結果である。

プログラマ向けに原因を詳しく書くが…

ここから、プログラマ(主に将棋ソフト開発者)向けに詳しく原因を書くが、上にも書いたように原因はとても複雑なので、将棋ソフトに詳しくないプログラマの人は理解できないと思う。そんなわけで、以下は興味のある人だけ読んで欲しくて、読んでもわからないであろう人は、「世の中には理解できない不思議なことで満ち溢れているんだな」と記憶に留めた上でこの時点でブラウザを×ボタンで閉じて欲しいわけである。

詳しいバグの原因

原因を詳しく書く前に、前提知識としていくつか書いておくことがある。

pseudo-legality(疑似合法性)とlegality(合法性)

合法手の判定には、pseudo-legal(疑似合法手)の判定と、legal(合法手)の二段階判定である。それぞれそれらしき名前の関数がPosition(局面)クラスに実装されている。また、指し手生成部で生成された指し手は、pseudo-legalであることは保証されている。pseudo-legalはlegalの簡易チェック版ではない。例えば、あるランダムな指し手が与えられた時には、少なくともpseudo-legalのチェックとlegalの２つのチェックが必要だと思って欲しい。(legalのチェックだけだと不可。pseudo-legalとlegalはそれぞれ異なる項目をチェックしている。)

このことから通常は、指し手生成部で指し手を生成するのでpseudo-legalのチェックは不要で、legalのチェックだけで十分である。

pseudo-legalの判定では、移動させる駒が自分の駒であるかだとか、成りの指し手ならば移動元の駒は成っていない駒であるかだとか、そういうことをチェックしている。指し手生成部は、成っている駒をさらに成るような指し手は当然ながら生成しない。

そうするとpseudo-legalの判定なんてものはそもそも要らないんじゃないかと思うかも知れないが、これが必要なのだ。兄弟局面の指し手を適用してうまくいくか試したいことがある。例えば、詰み手順を発見したならば、兄弟局面でも同じ手順で詰むか調べたいことがある。そのためには、その手順が、兄弟局面で合法であるか判定しなくてはならないが、この時には、pseudo-legalのチェックが必要だ。

MoveとMove16

指し手構造体は、16bitのもの(Move16)と32bitのもの(Move)が存在する。
Move16は、移動元の升、移動先の升、成り/打ちフラグを持つ。
Moveは、Move16をそのまま下位16bitに持ち、上位16bitには、移動後の駒(先手が飛車を成りなら、先手の龍)を保持している。

置換表から指し手の復元

置換表には指し手をMove16で格納している。メモリがもったいないからである。置換表から取り出す時に現在の局面を見て、Moveの上位16bit(移動後の駒)を復元している。これは、Position::to_move(Move16)で行われる。

pseudo-legalのチェックで実施していない項目

pseudo-legalのチェックとして、その駒が本当に成れるための条件を満たしているか(移動元が敵陣、もしくは移動先が敵陣であること)はチェックしていない。なぜなら、指し手は、指し手生成部で生成された指し手であり、指し手生成部では、移動元が敵陣か、もしくは移動先が敵陣である時しか、成りの指し手を生成しないからである。

でもそれが先手の指し手であるか後手の指し手かの区別はMove16ではつかない。Move(32bit)では移動後の駒種が格納されているので、その駒を見れば手番はわかる。(Moveに格納されている移動後の駒が「先手の龍」であれば、このMoveは先手の指し手である)

なので、先手の指し手を後手の指し手として適用してしまうとまずいことになる。先手の83飛成を後手の指し手だと思ってpseudo-legalを呼び出すと、合法手として扱われてしまう。これは仕様であり、高速化のためにそういう仕様にしてあるということである。先手の指し手と後手の指し手を混同してはならないということである。

置換表の指し手は先後領域が分かれている。

置換表には、Zobrist Hashをkeyとしてアクセスする。Zobrist Hashが何かわからん人はググって欲しい。(このブログが上位に来るかも知れないが)

ところが、やねうら王ではhash keyのbit 0を先後フラグにしている。このアイデアはApery(オープンソースの将棋ソフト)に依るものである。そこで、置換表のアドレスを計算するときに、hash keyのbit 0は必ず配列の添字のbit0に反映されるようになっている。



	// keyを元にClusterのindexを求めて、その最初のTTEntry*を返す。
	TTEntry* first_entry(const Key key) const {

		// indexのbit0は、keyのbit0(先後フラグ)が反映されなければならない。
		// →　次のindexの計算ではbit0を潰して計算するためにkeyを2で割ってからmul_hi64()している。

		// (key/2) * clusterCount / 2^64 をするので、indexは 0 ～ (clusterCount/2)-1 の範囲となる。
		uint64_t index = mul_hi64((u64)key &gt;&gt; 1, clusterCount);

		// indexは0～(clusterCount/2)-1の範囲にあるのでこれを2倍すると、0～clusterCount-2の範囲。
		// clusterCountは偶数で、ここにkeyのbit0がbit-orされるので0～clusterCount-1が得られる。
		return &amp;table&#91;(index &lt;&lt; 1) | ((u64)key &amp; 1)].entry&#91;0];
	}

// keyを元にClusterのindexを求めて、その最初のTTEntry*を返す。

TTEntry* first_entry(const Key key) const {

// indexのbit0は、keyのbit0(先後フラグ)が反映されなければならない。

// →　次のindexの計算ではbit0を潰して計算するためにkeyを2で割ってからmul_hi64()している。

// (key/2) * clusterCount / 2^64 をするので、indexは 0 ～ (clusterCount/2)-1 の範囲となる。

uint64_t index = mul_hi64((u64)key >> 1, clusterCount);

// indexは0～(clusterCount/2)-1の範囲にあるのでこれを2倍すると、0～clusterCount-2の範囲。

// clusterCountは偶数で、ここにkeyのbit0がbit-orされるので0～clusterCount-1が得られる。

return &table[(index << 1) | ((u64)key & 1)].entry[0];

}

そこで、先手の局面で置換表に書き出した(先手の)指し手が後手の局面で(後手の指し手として)置換表から取り出されることはないのである。

但しそのためには「先手の局面で先手の指し手しか置換表に書き出していない」という条件が必要である。

そんなこと、当然満たしているように思えるのだが、なんと言うことだろう。今回は、ここをすり抜けていたのだ…。

後手が先手の指し手(81にいた飛車を83に成る)を指してしまう例

これをtanuki-さん(たぬきシリーズの開発者の野田さん)が発見した。

具体的なシナリオとしては、次のようになる。

先手が81に打った飛車を83に移動させて成る(83飛成)を置換表のTTEntry(置換表の1 record)に登録
先手が置換表の衝突により、81に後手の飛車がある局面において、1.で書き出したTTEntryにhitしてしまう。
置換表に登録されているのはMove16なので、これを現在の局面情報に基づいてMoveに復元すると後手の指し手に見える指し手となってしまう。(81にいるのが後手の飛車なので)
やねうら王の探索部は、TTEntryから取り出した値が非合法手であるかのチェックより前に、TTEntryに登録されている局面のvalue(≒評価値)で枝刈りをしているので、枝刈り(βcut)されるケースがある。(この段落の末尾のコード)
4.で枝刈りされた時に、この指し手(Move16ではなくMove)で統計情報(Killer Move,Counter Move等)を更新する。
そうすると統計情報を格納する配列にこの指し手(後手の指し手に見える83飛成)を書き出してしまう。
後手の局面でたまたま81に飛車がいて83に移動できるときに、6.で書き出した統計情報から指し手を選んだときにpseudo-legalのチェックをすり抜けてしまう。
その結果、81にいる後手の飛車を83に移動させて成る83飛成が合法手とされてしまう。

【4.の実際のコード】

// 置換表の指し手でbeta cutが起きたのであれば、この指し手をkiller等に登録する。
			// ただし、捕獲する指し手か成る指し手であればこれは(captureで生成する指し手なので)killerを更新する価値はない。
			if (ttMove)
			{
				if (ttValue &gt;= beta)
				{
					if (!pos.capture(ttMove))
						update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth);

【4.の実際のコード】

// 置換表の指し手でbeta cutが起きたのであれば、この指し手をkiller等に登録する。

// ただし、捕獲する指し手か成る指し手であればこれは(captureで生成する指し手なので)killerを更新する価値はない。

if (ttMove)

{

if (ttValue >= beta)

{

if (!pos.capture(ttMove))

update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth);

バグの原因

こうして見ると、原因は4.が悪くて、非合法手で統計情報を更新するのが良くないということになる。そもそも、上のケースにおいては非合法手なのだから、それで統計情報を更新しているのもでたらめであれば、そのような指し手の評価値を以てβcutしているのもでたらめである。

そう考えると、ttMoveが非合法手である時は、ttMoveはMOVE_NONE(指し手なし)として扱うか、あるいは置換表にhitしなかったとして扱う必要がある。

Stockfish(チェスのソフト)も、βcutの処理は、やねうら王同様、上のようなコードになっており、要するに上のバグはそもそもはStockfishのコードがおかしいのである。

しかし、なぜStockfishがそのようなコードになっているのかと言うと非合法手かどうかの判定は、わりと重たい処理であるからだ。legalチェックは移動元と移動先の間の升に駒がないかを確認しないといけない。これを置換表から指し手を取り出すごとにしたくはないのである。置換表が衝突するのは(メモリがふんだんにあれば)レアケースだから、そこでCounter Moveに先後異なる指し手が混入したところで棋力に影響はないであろうという考えなのだと思われる。(そのあと、pseudo-legal のチェックできちんと先後を考慮してチェックを行うのであれば)

Stockfishは、実際に自己対局によってレーティングを計測して強い方のコードを採用するので、置換表から取り出す度にlegalチェックでスローダウンするコードより、極めて低い確率で後手の局面で先手で良かった指し手を試みるコードのほうが強かったのであろう。

バグの修正案

そこで、やねうら王の修正だが、pseudo-legalのチェックに本当に(現在の手番を考慮して)その駒が成れるかの判定を追加する方法と、置換表から取り出した時にpseudo-legalかを判定するか二通りの修正方法が考えられる。(後者は、場合によってはlegalチェックもすべきであるが、legalチェックは重いし、統計情報に指し手を先後を間違えて登録しなければ良いだけなのであれば、pseudo-legalの判定に留めたほうがスローダウンせずに済む)

前者は、Stockfishに近づける方法。後者は、Stockfishとは異なる実装になるが、誤ったβcutを少しでも減らす方法だ。最初にも書いたように、成りの指し手を錯覚するのは探索において非常に罪が重いため、このようなβcutは棋力に大きく影響している可能性がある。そこで、やねうら王では後者の方法で修正することにした。

バグ修正のプルリク

以上の調査は、すべてtanuki-さん(nodchip)の調査に基づく。tanuki-さんがすでにやねうら王の方にプルリクをくれていて、現在、有志によって動作検証がなされている状況である。問題がなければ今週中にマージする予定である。ありがとう！tanuki-さん！

nodchipさんとやねさんのやりとり見てましたが、まじ天才かってなってました！
バグって技術力を映す鏡な気がしますが、こんなバグあるんですか、っていう。 https://t.co/FQUFecBnYq
— たややん＠水匠(COM将棋) (@tayayan_ts) August 17, 2021

追記 2021/08/31

        // === tanuki-さんによる解説
        // 第2回世界将棋AI電竜戦エキシビジョン 電竜戦長時間マッチ 第1局 水匠 vs dlshogi において、
        // 水匠が自陣で飛車を成る手を読んだ。
        // 当日起こったと考えられる現象をローカルで調査したところ、原因として以下が浮かんだ。
        // (実験条件・環境の違いにより、指し手は異なっている。)
        // 1. 先手番、局面 A、先手の飛車が８一にいる。８一の飛車を４一に移動させ、かつ成る指し手が指される。
        //    この指し手が置換表に保存される。
        // 2. 先手番、局面 B、後手の飛車が８一にいる。局面 A と局面 B のハッシュが衝突している。
        //    直前の後手の指し手の移動先は１二。置換表の指し手が読み込まれる。 Move16 から Move に変換される。
        //    このとき、８一には後手の飛車がいるため、 Move の上位 16 - bit には、
        //    後手の飛車が移動されて成る、という情報が格納される。
        // 3. 局面 B、置換表の指し手によるβカットが起きる。このとき、指し手が Counter Move に登録される。
        // 4. 後手番、局面 C、後手の飛車が８一にいる。直前の後手の指し手は null move。１二には後手の駒がいる。
        //    Counter Move の指し手が読み込まれる。直前の手が null move だったため、
        //    １二に移動した指し手として扱われる。１二には後手の駒がいるため、後手の指し手として扱われる。
        //    Counter Move から後手の指し手の次の手として、
        //    後手の８一の飛車を４一に移動させ成るという手が読み込まれる。後手番で後手が指す手を指すことになるので、
        //    pseudo_legal() に引っかからない。
        // 5. Counter Move の手が指され、後手の飛車が自陣で成る。
        // 上記を回避するため、非合法手をCounter Moveに記録しないようにする。

// === tanuki-さんによる解説

// 第2回世界将棋AI電竜戦エキシビジョン電竜戦長時間マッチ第1局水匠 vs dlshogi において、

// 水匠が自陣で飛車を成る手を読んだ。

// 当日起こったと考えられる現象をローカルで調査したところ、原因として以下が浮かんだ。

// (実験条件・環境の違いにより、指し手は異なっている。)

// 1. 先手番、局面 A、先手の飛車が８一にいる。８一の飛車を４一に移動させ、かつ成る指し手が指される。

// この指し手が置換表に保存される。

// 2. 先手番、局面 B、後手の飛車が８一にいる。局面 A と局面 B のハッシュが衝突している。

// 直前の後手の指し手の移動先は１二。置換表の指し手が読み込まれる。 Move16 から Move に変換される。

// このとき、８一には後手の飛車がいるため、 Move の上位 16 - bit には、

// 後手の飛車が移動されて成る、という情報が格納される。

// 3. 局面 B、置換表の指し手によるβカットが起きる。このとき、指し手が Counter Move に登録される。

// 4. 後手番、局面 C、後手の飛車が８一にいる。直前の後手の指し手は null move。１二には後手の駒がいる。

// Counter Move の指し手が読み込まれる。直前の手が null move だったため、

// １二に移動した指し手として扱われる。１二には後手の駒がいるため、後手の指し手として扱われる。

// Counter Move から後手の指し手の次の手として、

// 後手の８一の飛車を４一に移動させ成るという手が読み込まれる。後手番で後手が指す手を指すことになるので、

// pseudo_legal() に引っかからない。

// 5. Counter Move の手が指され、後手の飛車が自陣で成る。

// 上記を回避するため、非合法手をCounter Moveに記録しないようにする。

2021/09/03 6:30 追記

上記バグは、やねうら王V6.04で修正されました。