この話、内容がややこしすぎてうまく文章にまとめる自信がない。間違ったことを書いているかも知れない。
※ 結論だけさらっと書くので、わからない人は読み飛ばしてください。
協力詰めにおいて幅優先探索(+反復深化)をしているわけなので元来、(連続王手の)千日手は枝刈りできるはずであった。
※ 先手側は王手しか生成していないので千日手は自動的に連続王手の千日手であり、非合法手である。
なぜなら、連続王手の千日手で同じ局面に至ったということは、探索の浅いところ(＝残り探索深さが多いところ)でその局面が一度出ているわけで、そのときより残り探索深さが少ないとこれで詰まないことは自明だからだ。(前回の反復深化のiterationにおいて、その局面がその残り探索深さで詰まないことは証明されていると考えられる。)
「連続王手の千日手が枝刈りできる」というのは、上記の原理に支えられていた。
ところが、これが並列化を考えたときに簡単には枝刈りできないのである。
今回、並列化をlazy SMPを採った。これはスレッドごとに反復深化の探索深さをバラつかせて投機的に実行することで並列性を稼ぐという方法である。
協力詰め自体はAND/ORグラフではなくOR/ORグラフなので、こんなことをすると効率があまりよろしくないのであるが、簡単な方法で並列化できるので良いかと思ったのだ。しかし、「前回の反復深化のiterationにおいて、その局面がその残り探索深さで詰まないことは証明されている」という前提が崩れてしまったのである。
では、YBWCならいいのかという良いのかという話になるのだが、実はYBWCでも(単純には)駄目なのである。
簡単に理由を説明する。
並列化のために、probe() (置換表のエントリーに登録されているかの確認)とsave() (置換表のエントリーへの書き戻し)のときに置換表のentryのlock〜unlockはしているものとする。
このとき、GHI問題を引き起こすのだ。あるスレッドが循環局面だからということで枝刈りして、その手前の局面を詰まないと判定してしまったとしよう。これを置換表に登録する。そうするとその局面は詰まないことになっているから、他のスレッドがprobe()したときに詰まないと判定されてしまうのだ。
「いやいや、それはおかしい。それで詰まないと判定されるなら、1スレッドのときは何故うまく行くのか？1スレッドのときも同じ問題は起こりうるのではないのか。」
もっともである。
1スレッドであってもこの問題は生じている。
しかし、1スレッドの場合は、この問題は巧妙に自動的に回避されているのだ。
これが、実は、df-pnでのサイクル問題の解決法でもあるので秘匿しておきたかったのだが、なんとかちゃんねるの住人にこれだけデバッグを協力してもらったからには彼らのためにも書かねばならない。
長手数の協力詰めsolver書いた経験からかdf-pnの論文見ると一瞬で理解できた。しかも、df-pnのサイクル回避問題、df-pnよりシンプルに書けて、df-pnより少しだけ効率のいいアルゴリズム閃いた。 てか、df-pn自体要らないな。こんなものに俺は頭を悩ましてたのか…。
— やねうら王 (@yaneuraou) January 3, 2016
経路の循環が絡むスコアが上位のどのノードにまで遡及するのかという問題である。
A→B→C→D→E→B
例えばこのような経路で循環しているとする。EからBにいく以外は詰まされてBへは連続王手の千日手だから行けないとする。このときEの局面が詰まされる局面であるとは限らない。他の経路からEに来ればBに行けるかも知れないからだ。
そこでこの経路でのEでの値(評価値等)は、(置換表上で一貫性を保ちたいなら)置換表に書き出すべきではない。経路依存のスコアだからだ。
ではこの経路依存性はどこで断ち切れるのかという問題を考える。
実は、無限に上位nodeまで連鎖はしないのだ。
上のケースの場合、D,Cの局面では同じ理由で置換表に書くべきではないが、(1回目の)Bの局面ではそこ以前の経路に依存していないので経路依存のスコアではない。だからBの局面ではそのスコアを置換表に書き込んでも問題はない。
このように経路依存のスコアが上位nodeに伝播するのはリミットがある。上の図ならBまでだ。
それで、協力詰めの1スレッドのときもまた、経路依存スコアが置換表に書き出されて確かに置換表上、一貫性が一時的になくなるのであるが、しかし上位nodeでその局面に対してsave()するのでそのときに正しい値で上書きされて一貫性が保たれる。(ようである。私には証明は出来ていない。)
並列化したときは、この置換表上で一貫性がなくなっているタイミングで他のスレッドがこの値を読みだしてしまうことがあるのでどうもまずいようである。
かくの如く、非常に発見しにくいバグであった。そして、協力詰めsolverの並列版では連続王手の千日手を枝刈りできなくなってしまったので解図が遅くなってしまった。
なんとかちゃんねるの住人たちに感謝しつつ、この記事を終えたい。
遅くなるけど、フェーズを分けるとかそういう話なのですかね。2パスで解くとか。
特性因子を抜けるのであれば、限定場面としてゴリゴリ回避するとかしないとダメなのかなぁ。
マルチスレッド系のバグは怖いですね。
なんとかちゃんねるの住人がどう言ったのか分かりませんが何かおかしいように思えます。
例えば、以下の迷路。Ｓからスタートしてゴールにたどり着けるか。答えは「たどり着けない」です。
人間なら１秒で答えを出せますが、これを深さ優先探索（ヘビ君）で探すと大変なことになる。
ヘビ君がクネクネ形を変えて這いずり回って、やっと「袋小路です」という事が分かる。
┏━┳━┳━┓
┃Ｓ□□□□┃
┣□╋□╋□┫
┃□□□□□┃
┣□╋□╋□┫
┃□□□□□┃ ゴール
┗━┻━┻━┛
（□は空白です。）
やねうら氏の主張は「ヘビ君が自分の体に最初にぶつかった時点で、この迷路は袋小路だ」と判定すると言っているようにみえる。
図がずれてしまう・・・
図で解析するとそうかもしれませんが、省力化とはある程度見切りをつけて最低条件かつ必要条件を満たす方法を模索することです。
そうしないと、プログラムが現実的な時間では終わらないのですよ。
その図においてプログラムが閉路だと気付くためには全パターン列挙が必要に思いますが、将棋のパターンを全部列挙するのは現実的ではありませんね、今のところ。
> やねうら氏の主張は「ヘビ君が自分の体に最初にぶつかった時点で、この迷路は袋小路だ」と判定すると言っているようにみえる。
その例えで言うと、私の主張は「ヘビ君が自分の体に最初にぶつかった時点で、これは自分の体だと認識して、他の道を探そう」と判断しようと言っているのです。
しかし、並列探索しているときは、ヘビ君が複数いるので、本当にそれが自分の体であるか怪しい、みたいな話。(厳密な話ではありません。あくまで例えとして、です。)
＞なぜなら、連続王手の千日手で同じ局面に至ったということは、探索の浅いところ(探索残り深さが多いところ)でその局面が一度出ているわけで、探索の残り深さが浅いとこれで詰まないことは自明だからだ。
これは実は
連続王手（の千日手）で同じ局面に至ったということは
（ ）の中がいらないのでは？
それで、教えていただきたいのですが、
「連続王手の千日手」成立は同じ局面が２回現れるとNG判定になるのでしょうか？
普通の千日手は同じ局面が４回現れるとNGと理解しておりますので、、、。
> （ ）の中がいらないのでは？
そこは要るのだけど、言い回しが紛らわしい気がしたので修正しておきました。(｀･ω･´)ゞ
> 「連続王手の千日手」成立は同じ局面が２回現れるとNG判定になるのでしょうか？
2回現れた時点で(そのサイクルを繰り返し続けると千日手になるので)、プログラムの内部的にはこれを千日手扱いにします。通常探索時も同様です。
回答ありがとうございます。
それで、次の文章ですが、
＞１：A→B→C→D→E→B
＞２：例えばこのような経路で循環しているとする。EからBにいく以外は詰まされてBへは連続王手の千日手だから行けないとする。このときEの局面が詰まされる局面であるとは限らない。他の経路からEに来ればBに行けるかも知れないからだ。
２：の文章は「従って、１：の経路で来たときは（先手は）このサイクルには入ってはいけない、つまりDはチョイスできない」と。
「Dをチョイスして後手がEをチョイスしたら先手の負け」、、、となる。
「でも別の経路からEに来たときはE→B→F→G・・・の可能性がある」と。
「だからEに（先手の負け）というフラッグを立ててはいけない」、、、
つまりE以降の探索を中止（or枝刈り)してはいけない、、、ということでいいのでしょうか？
> つまりE以降の探索を中止（or枝刈り)してはいけない、、、ということでいいのでしょうか？
「無条件に中止(枝刈り)するわけにはいかない」が近いのでは。どのみち、2回目にBに到達したときに、置換表に前回の反復深化のときのBの値が残っているなら、前回の反復深化ではA→B→C→D→E あたりまでは来ているはずで(来ているとしたら)、Bから3手では詰まないことは置換表に記録が残っています。
ということは、A→B→C→D→E→Bと行ったときにこの2回目のBから3手では詰まないので仮に残り探索深さが3手未満しかなければ、これをもって2回目のBで枝刈りが出来ます。
このように2回目に同じnodeに到達しても置換表を見れば、そこでの残り深さでは詰まないことが大抵は記録されているのでここで枝刈りされます。
なるほど。
そうやって置換表は使うのですね。
でも、そのためには（何手では詰まない）情報をnodeが持っていないといけません。
そして、確定局面（@連載やねうら王miniを強くしよう！7日目)nodeの上方伝搬なら話は単純そうです。
でもそうでない、確定局面でないnodeに対しては・・・
＞すなわち、あるnodeのTTEntryに書き込むべきdepthの値は、子のnodeが置換表に書いたdepth (これは子のnodeの数だけある)の最小値 + 1 ということがわかります。（@同上）
という作業を毎回の反復深化終了時に、なにやらものすごい数のnodeに対して行う必要がありそうにみえるのですが、、、。
実際にそうやっておられるのでしょうか？
> という作業を毎回の反復深化終了時に、なにやらものすごい数のnodeに対して行う必要がありそうにみえるのですが、、、。
残り探索深さが1手以上残っていれば、あるnodeに対して子nodeはすべて展開する(それぞれの子nodeへの指し手でdo_moveして実際に局面を進める)必要があるので、そのときに自動的に「子のnodeが置換表に書いたdepth (これは子のnodeの数だけある)の最小値 + 1 」という値は求まるのでは。
協力詰めのソースコードのsearch関数を再帰的に呼び出しているあたりを見ればそれがわかるはず…。
ただ、12HTで1秒間に1〜2千万nodeぐらいは調べていますが…。