先日(2022/11/18)にうえのんEDAXのバージョン0.70bを公開して、合流を考慮した海亀数を計算する機能が追加されました。合流海亀数についてはこのページでざっくり説明しているのですが、今回の記事では数学的にちゃんとした定義をします。よって上級者向けです。前の記事を読んでない人は読んできてください。
まずは合流がない場合の海亀数の復習をします。
上の図において、黒い●は黒の手番であること、白い〇は白の手番を表しています。
黒の必要暗記数は2（例：初手でStephensonを選択し、コンポス＆ノーカンを対策すればいい）、
白の必要暗記数も2（例：黒がStephensonで来たならコンポス、虎大量で来たならFJT）なので
海亀数は (手番側=黒の暗記数) : (手番がない側の暗記数) = 2:2 となります。
以下、海亀数（暗記数のペア）を考えると煩雑なので、単に根ノード（木の根元。「虎定石」の部分）での手番側の必要暗記数だけを考えることとします。
黒の暗記数は、上の図のようにゲーム木の上での再帰的な計算で求めることができます。
・黒の番であれば、2通り、3通りのうち暗記数が少ない進行を選ぶ権利があるのでmin(2,3)
・白の番であれば、どこに打たれるかわからないので配下の暗記数の和になる
では、ここまでを前提知識として合流がある場合の暗記数について考察してみましょう。
ここからが本番です。
問題：
上の場合の根元の黒の必要暗記数はいくらでしょうか？
答えは3通りで、初手で下の経路（赤い矢印）を選ぶことで、白がどんな選択をしようとも赤丸の局面どこかにたどり着けるはずです。
全局面の必要暗記数を計算すると以下のようになります。
緑枠の部分に注目してください。合流がない場合であれば、白〇での暗記数は3+1=4になるはずですが、合流がある場合はこの式が破れます。なぜなら、黒●の③の暗記する盤面の内訳は{a,b,c}、①の内訳は{c}なので、白〇の暗記盤面は{a,b,c}∪{c}={a,b,c}で3通りになります。3+1で計算するとcの盤面を重複して数えてしまうんですね。
以上の議論より、全てのleafにa,b,c,....と記号を付与して集合として扱いカウントすることで分岐考慮の暗記数を計算することができます💪
・・・
・・・
・・・
これで済むのであればどんなに楽だったことか・・・
■問題は何か
上記のアルゴリズムは確かに正しい結果を計算することができます。が、計算にかかる時間を考えてみましょう。
L: 木のleafの数(leafはリバーシプログラムedaxの用語。木の末端=一番右の事)
C: 合流の原因になる局面の数(Confluentの頭文字)、要するに親が複数いるノードの数
N: 木のノード全ての数
とします。ここで、オセロのゲーム木のノード数は1手進むごとに数倍に等比数列的に増えていくので、LとNは比例するとしていいでしょう。つまり、大体N≈4Lで、計算量のオーダーを見たいのでN≈Lとします。先ほどの例では L=4,C=2,N=13ですね。また、各ノードについて子の数はオセロにおいて着手可能な最善の数なので高々数個、O(1)とします。
・分岐を考慮しない旧来のアルゴリズムの計算量
min(...)やsum(...)の計算を大体N回行うので O(L)となる
※O(?)は数学の記号で、?に比例するくらいの計算量がかかるという意味
・分岐考慮の計算量
集合{a,b,e,......}と{a,d,e,......}の共通集合を求めるためには大体片方の集合の要素数くらいの時間がかかります。(c++のunordered_setなどで実装した場合)よって、一回当たり最大でO(L)の時間がかかります。この計算をN回行うので全体でO(L^2)の計算時間がかかります。
ところで、有段者が使うそれなりに大きいedaxのbook(序盤データベースのこと)を考えると（ファイルサイズ≈200MB）、Lは1000万くらいなので、分岐を考慮すると最大で1000万倍くらい遅くなります！これは最大値の見積もりなのでここまでではないのですが、どちらにせよこれだけの差があると全く使い物になりません。
また、今のアルゴリズムのもう一つの悪い点は、実際には合流がない場合であってもO(L^2)の時間がかかってしまうことです。合流がない場合は、今まで通りO(L)くらいで計算できてほしいものです。
■ここで問題です
「合流を考慮した分岐数をなるべく少ない計算量で計算するアルゴリズムを実装せよ。病的な場合はO(L^2)になるのは仕方がないにしても、合流無しではO(L)で計算でき、オセロのbook程度の合流では合流を考慮しない場合に比べ10倍以内の計算量であることが望ましい。」
難易度は競技プログラミング(数学的に難しいプログラムを素早く実装するeスポーツ)のAtCoder換算で600点くらいでしょう。東大入試の数学よりは明らかに難しいレベル（超難問は除く。120点中60～80点取れる人がギリギリ解けるレベルの問題よりは難しい）。自分は実装するのに1週間以上かかりました。
（以下、答え）※自分でやりたい人は自分で考えてみてください。君ならできるよ
■新しいアルゴリズムの提案
これから提案するアルゴリズムは、合流を考慮した分岐数を大体の場合はO((C+1)×L)の計算量で計算することができます。うえのんEDAXでは、このアルゴリズムが採用されています。
（基本的な考え方）
古いアルゴリズムでは文字a,b,...をleaf(L個)に対応させていたが、これをさぼって高々C個の文字で計算することを考える。
※これだけであれば簡単であるが、途中で計算が詰まるポイントがある。
木をケツ（手数が深いほう）から見ていきます。まず、合流が発生するノード以外では今までの海亀数と同じ計算をします。緑色で囲った部分が合流発生ノードで、親（左側に伸びる線）が複数あることがわかります。合流発生ノードは、後で重複して数えられることを防ぎたいので文字式(a)で置きます。a=1であるので、どこか別の場所に忘れないように書いておきます。
木の浅いほうに一手進みます。また合流発生ノードがあるので、結果をbとします。白いノードでは海亀数は和を取るルールであったので、b=1+1+a=2+aです。結果を置換表に書いておきます。
さて、深さ5で変数a、深さ4で変数bを導入しました。変数を導入した目的は、「複数ノードで参照されている同一盤面を保持する」です。具体例を挙げると、深さ4で導入されたbという盤面は、深さ3の2つの盤面から暗記数bを言う形で参照されています。逆に言うと、文字への参照が1になった時点で文字は数字に戻すことができます。
文字を数字に縮約できるかどうか順にみてみましょう。深さ5でaが導入され、深さ4でbが導入されました。深さ3の時点で、bは2ノードに共有されているので縮約できません。aについては、一見1か所にしか出てきていないように見えますがbはaに依存することを考えると結局3か所から参照されています。深さ2についてもa,bともに2か所から参照されています。
深さ1は、ノードが1つしかないので当然縮約可能です。bはaに依存することを考えまずはbから代入していきます。
min(1+b,a+b)にb=a+2を代入してmin(3+a,a+a+2)となりますが、
ここで、a+aは要するに{a}∪{a}のことを指しているのでa+a=aとなります。普通の数学と違って同じ文字を足すと係数は1になります。よって黒の分岐数は
min(3+a,a+2)
となりa=1を代入することでmin(4,3)となり3と求めることができます。
最後に、実装上で詰まりやすいポイントです。各ノードでは計算結果を文字式で持っていますが、文字式は以下の形式で管理すれば十分です。
min( 1+a+b+c , 2+a+c+e , 0+b+c+d , ...... )
要するに、「(整数と(文字のセット))の可変長配列」を持っていれば足りるということですが、これに気づくのがかなり難しいです。海亀数はminとsumがネストしていくので
min(a,min(1+b+c,min(3,d)+min(1+a,....)))
みたいなminが入れ子になっている構造が必要と普通は思うのですが、なんとこんなものは必要なく高々1個のminで表せるというかなり強いことを言っています。このことを証明します。
（証明）
min( 1+a+b+c , 2+a+c+e , 0+b+c+d , ...... )の構造が、minとsum(足し算)の演算に対し閉じている（入れ子にならない）ことを示せばいい。
minについてはほぼ自明で、min(min(a,b,c,....) , min(x,y,z,....) )=min(a,b,c,....,x,y,z,.....)より従う。
sumについては、min(a,b)+min(x,y,z)がmin(a+x,a+y,a+z,b+x,b+y,b+z)と展開を行えばいい。
最後に、計算量を見積もります。
■計算量の見積もり(厳密じゃない)
基本的にはC種の文字をL回演算するのでO((C+1)L)くらいでできるはずだが、上記（証明）にあるとおりminのsumを取るときにminの中身の要素数が掛け算で増えていくケースがありここがネックになる可能性がある。min(1+a ,2+a,...)みたいなケースで2+aは明らかに最小にならないため落とすなど、工夫をすることで計算量はある程度抑制できる。実用上は、普通のbookで深さ30などであれば分岐を考慮しない場合に比べ、おおよそ10倍以内の計算時間で実際に計算できることが多い。
もっといいアルゴリズムがあったら誰か教えてください。
まずは合流がない場合の海亀数の復習をします。
上の図において、黒い●は黒の手番であること、白い〇は白の手番を表しています。
黒の必要暗記数は2（例：初手でStephensonを選択し、コンポス＆ノーカンを対策すればいい）、
白の必要暗記数も2（例：黒がStephensonで来たならコンポス、虎大量で来たならFJT）なので
海亀数は (手番側=黒の暗記数) : (手番がない側の暗記数) = 2:2 となります。
以下、海亀数（暗記数のペア）を考えると煩雑なので、単に根ノード（木の根元。「虎定石」の部分）での手番側の必要暗記数だけを考えることとします。
黒の暗記数は、上の図のようにゲーム木の上での再帰的な計算で求めることができます。
・黒の番であれば、2通り、3通りのうち暗記数が少ない進行を選ぶ権利があるのでmin(2,3)
・白の番であれば、どこに打たれるかわからないので配下の暗記数の和になる
では、ここまでを前提知識として合流がある場合の暗記数について考察してみましょう。
ここからが本番です。
問題：
上の場合の根元の黒の必要暗記数はいくらでしょうか？
答えは3通りで、初手で下の経路（赤い矢印）を選ぶことで、白がどんな選択をしようとも赤丸の局面どこかにたどり着けるはずです。
全局面の必要暗記数を計算すると以下のようになります。
緑枠の部分に注目してください。合流がない場合であれば、白〇での暗記数は3+1=4になるはずですが、合流がある場合はこの式が破れます。なぜなら、黒●の③の暗記する盤面の内訳は{a,b,c}、①の内訳は{c}なので、白〇の暗記盤面は{a,b,c}∪{c}={a,b,c}で3通りになります。3+1で計算するとcの盤面を重複して数えてしまうんですね。
以上の議論より、全てのleafにa,b,c,....と記号を付与して集合として扱いカウントすることで分岐考慮の暗記数を計算することができます💪
・・・
・・・
・・・
これで済むのであればどんなに楽だったことか・・・
■問題は何か
上記のアルゴリズムは確かに正しい結果を計算することができます。が、計算にかかる時間を考えてみましょう。
L: 木のleafの数(leafはリバーシプログラムedaxの用語。木の末端=一番右の事)
C: 合流の原因になる局面の数(Confluentの頭文字)、要するに親が複数いるノードの数
N: 木のノード全ての数
とします。ここで、オセロのゲーム木のノード数は1手進むごとに数倍に等比数列的に増えていくので、LとNは比例するとしていいでしょう。つまり、大体N≈4Lで、計算量のオーダーを見たいのでN≈Lとします。先ほどの例では L=4,C=2,N=13ですね。また、各ノードについて子の数はオセロにおいて着手可能な最善の数なので高々数個、O(1)とします。
・分岐を考慮しない旧来のアルゴリズムの計算量
min(...)やsum(...)の計算を大体N回行うので O(L)となる
※O(?)は数学の記号で、?に比例するくらいの計算量がかかるという意味
・分岐考慮の計算量
集合{a,b,e,......}と{a,d,e,......}の共通集合を求めるためには大体片方の集合の要素数くらいの時間がかかります。(c++のunordered_setなどで実装した場合)よって、一回当たり最大でO(L)の時間がかかります。この計算をN回行うので全体でO(L^2)の計算時間がかかります。
ところで、有段者が使うそれなりに大きいedaxのbook(序盤データベースのこと)を考えると（ファイルサイズ≈200MB）、Lは1000万くらいなので、分岐を考慮すると最大で1000万倍くらい遅くなります！これは最大値の見積もりなのでここまでではないのですが、どちらにせよこれだけの差があると全く使い物になりません。
また、今のアルゴリズムのもう一つの悪い点は、実際には合流がない場合であってもO(L^2)の時間がかかってしまうことです。合流がない場合は、今まで通りO(L)くらいで計算できてほしいものです。
■ここで問題です
「合流を考慮した分岐数をなるべく少ない計算量で計算するアルゴリズムを実装せよ。病的な場合はO(L^2)になるのは仕方がないにしても、合流無しではO(L)で計算でき、オセロのbook程度の合流では合流を考慮しない場合に比べ10倍以内の計算量であることが望ましい。」
難易度は競技プログラミング(数学的に難しいプログラムを素早く実装するeスポーツ)のAtCoder換算で600点くらいでしょう。東大入試の数学よりは明らかに難しいレベル（超難問は除く。120点中60～80点取れる人がギリギリ解けるレベルの問題よりは難しい）。自分は実装するのに1週間以上かかりました。
（以下、答え）※自分でやりたい人は自分で考えてみてください。君ならできるよ
■新しいアルゴリズムの提案
これから提案するアルゴリズムは、合流を考慮した分岐数を大体の場合はO((C+1)×L)の計算量で計算することができます。うえのんEDAXでは、このアルゴリズムが採用されています。
（基本的な考え方）
古いアルゴリズムでは文字a,b,...をleaf(L個)に対応させていたが、これをさぼって高々C個の文字で計算することを考える。
※これだけであれば簡単であるが、途中で計算が詰まるポイントがある。
木をケツ（手数が深いほう）から見ていきます。まず、合流が発生するノード以外では今までの海亀数と同じ計算をします。緑色で囲った部分が合流発生ノードで、親（左側に伸びる線）が複数あることがわかります。合流発生ノードは、後で重複して数えられることを防ぎたいので文字式(a)で置きます。a=1であるので、どこか別の場所に忘れないように書いておきます。
木の浅いほうに一手進みます。また合流発生ノードがあるので、結果をbとします。白いノードでは海亀数は和を取るルールであったので、b=1+1+a=2+aです。結果を置換表に書いておきます。
さて、深さ5で変数a、深さ4で変数bを導入しました。変数を導入した目的は、「複数ノードで参照されている同一盤面を保持する」です。具体例を挙げると、深さ4で導入されたbという盤面は、深さ3の2つの盤面から暗記数bを言う形で参照されています。逆に言うと、文字への参照が1になった時点で文字は数字に戻すことができます。
文字を数字に縮約できるかどうか順にみてみましょう。深さ5でaが導入され、深さ4でbが導入されました。深さ3の時点で、bは2ノードに共有されているので縮約できません。aについては、一見1か所にしか出てきていないように見えますがbはaに依存することを考えると結局3か所から参照されています。深さ2についてもa,bともに2か所から参照されています。
深さ1は、ノードが1つしかないので当然縮約可能です。bはaに依存することを考えまずはbから代入していきます。
min(1+b,a+b)にb=a+2を代入してmin(3+a,a+a+2)となりますが、
ここで、a+aは要するに{a}∪{a}のことを指しているのでa+a=aとなります。普通の数学と違って同じ文字を足すと係数は1になります。よって黒の分岐数は
min(3+a,a+2)
となりa=1を代入することでmin(4,3)となり3と求めることができます。
最後に、実装上で詰まりやすいポイントです。各ノードでは計算結果を文字式で持っていますが、文字式は以下の形式で管理すれば十分です。
min( 1+a+b+c , 2+a+c+e , 0+b+c+d , ...... )
要するに、「(整数と(文字のセット))の可変長配列」を持っていれば足りるということですが、これに気づくのがかなり難しいです。海亀数はminとsumがネストしていくので
min(a,min(1+b+c,min(3,d)+min(1+a,....)))
みたいなminが入れ子になっている構造が必要と普通は思うのですが、なんとこんなものは必要なく高々1個のminで表せるというかなり強いことを言っています。このことを証明します。
（証明）
min( 1+a+b+c , 2+a+c+e , 0+b+c+d , ...... )の構造が、minとsum(足し算)の演算に対し閉じている（入れ子にならない）ことを示せばいい。
minについてはほぼ自明で、min(min(a,b,c,....) , min(x,y,z,....) )=min(a,b,c,....,x,y,z,.....)より従う。
sumについては、min(a,b)+min(x,y,z)がmin(a+x,a+y,a+z,b+x,b+y,b+z)と展開を行えばいい。
最後に、計算量を見積もります。
■計算量の見積もり(厳密じゃない)
基本的にはC種の文字をL回演算するのでO((C+1)L)くらいでできるはずだが、上記（証明）にあるとおりminのsumを取るときにminの中身の要素数が掛け算で増えていくケースがありここがネックになる可能性がある。min(1+a ,2+a,...)みたいなケースで2+aは明らかに最小にならないため落とすなど、工夫をすることで計算量はある程度抑制できる。実用上は、普通のbookで深さ30などであれば分岐を考慮しない場合に比べ、おおよそ10倍以内の計算時間で実際に計算できることが多い。
もっといいアルゴリズムがあったら誰か教えてください。
コメント