斉次多項式の決定問題
変数次多項式は異なる個の点における値を決めることで常に一意に定まります。(実数上で考えるとします。)
多変数にした場合はどうなるでしょうか。 「常に」は成り立たなくなり、多項式を決定するためにはうまく点を選ぶ必要があります。 必要条件はいくつか想像できると思います。例えば変数がとたくさんあるのに選ぶ点が全て軸上にあっては困るだろう、など。 では、必要十分条件は?...
調べるとこの問題はMultivariate Polynomial Interpolationと呼ばれ、それなりに研究もされているようです。
必要十分条件や、それより簡潔な十分条件も調べられているようで、例えば
https://kluedo.ub.uni-kl.de/frontdoor/deliver/index/docId/3566/file/PhD_Thesis_Stahl.pdf
の2章に記述があります。(私は部分的にしか理解していませんが。)
では考える多項式を斉次多項式に限定したらどうなるか。 問題は少し単純化される気もしますが、考えてみると意外と難しく、ネットにもほぼ情報が見つかりません。 そんな中関係がありそうな情報を見つけたのでまとめることにしました。
与えたいくつかの点が変数次斉次多項式を決定できる十分条件およびそのような点の構成方法をまとめています。 需要は分かりませんが、もしこれを読んで間違いに気付いたりもっと詳しいことを知っているなどあれば是非とも教えていただけたらと思います。
2020/10/11 追記:
PDF内で使用していた「一般の位置」という用語が少し不適切で、この用語もあまり使われないようなので表現を変更しました。
なお、点が一般の位置にあるとは、個の位置ベクトルが一次独立になることです。
元の文で「点が一般の位置にある」と言っていた部分は「点に原点を加えた点が一般の位置にある」と言うべきでした。
2020/10/27 追記:
読んで頂いた方から指摘を頂き、補題の(i)の証明の中にあった誤りを修正しました。
その他日本語がおかしかった文など数ヶ所を修正しました。
ゼータ変換とメビウス変換の関係
競技プログラミングでたまに使われるゼータ変換とメビウス変換について、逆変換だというのがどうもピンと来なかったので確かめてみる事にしました。
(多分探せばもっと高度でエレガントな証明があるんだろうなぁと思っています。)
これらの変換は、集合上の関数を同じ集合上の関数に変換します。 定義を確認しておきます。
ゼータ変換
メビウス変換
つまり、ゼータ変換はある集合を含む集合全体にわたる和で、メビウス変換は同様の全体に対して足したり引いたりします。(笑) (多分あとで例を出します。)
これが逆変換になるらしいのですが、眺めていてもよくわからない。という事で計算してみました。
計算
まずはを示したい。
一応断っておきますが、ここでは集合の大きさが有限だったりして和の順番は自由に入れ替えて良いとします。
はい。
なんか途中でいろいろなことが起こりましたがなんとか結論まで持って来れました。
途中で行った式変形のほとんどは和の順番を変更するという操作です。
間違い探しパズルだと思えば式変形を追えないこともないんじゃないかなと思います。
そして最後の部分で、二項係数の交代級数の和が0になるということを利用しました。
ちなみにこれは、二項展開の式
にを代入することで簡単に示せます。
計算その2
さきほどはゼータ変換してからメビウス変換すると元に戻ることを示しました。
ということで次は反対のを示すために計算をしていきます。
(上の結果を利用して楽をする方法をしばらく考えたのですが、無理そうでした。)
やってみたら上とほとんど同じでした。 ということでめでたくゼータ変換とメビウス変換は逆変換の関係になっていることが示せました。
おまけ
ここではゼータ変換、メビウス変換を
と定義しましたが、別の定義というか別のゼータ変換、メビウス変換として次のようなものがあります。
との関係が逆になっていますが、これらも逆変換の関係にあります。
ちゃんとは確認していませんが、多分補集合をとるなどして関数と変数を適当に変換してやれば互いに移りあうと思います。
ちょっとした例
今更感ありますが、ちょっとした例を出してみます。
の値からの値を求めたいとします。
中学入試問題みたいなところでよく見るタイプの問題ですね。
答えは簡単で、
です。 包除原理などとも呼ばれるらしいです。
ここで、とおいてみれば、
となってメビウス変換で表すことができます。
ちなみに、の定義をとすると、
と、ゼータ変換で表すこともできます。
(この例を出したのはこれが言いたいだけだったり。)
あとがき
ゼータ変換とメビウス変換は互いに逆変換だということを確認しました。
ここまで頑なに「変換」という言葉を使ってきましたが、写像と考えることもできるはずです。
集合上の関数全体の集合をとすると、ゼータ変換やメビウス変換は写像となり、逆写像があるので同型写像だと言えます。
ほかにも、畳み込みに対して特別な性質を持っていたり、この2つの変換の裏にはまだいくらか世界が広がっているのではないかと思っているのですが、今はそこまで踏み込む余裕はないのでこのあたりで終わろうと思います。
ゴドマチの詰め探索アルゴリズム
ゴドマチの詰め探索をするプログラムを書きました。
結構頑張ったのと、個人的に面白かったので使ったアルゴリズムについて書いてみようと思います。
ゴドマチって?
2人用の対戦型パズルゲームです。
ルールは考案された方のページでまとめられています。
単純なルールで気軽にできるゲームなので、やったことないという方は是非遊んでみてください。
と、宣伝をしたところで本題へ。
ゴドマチは完全情報ゲームで引き分けがないので、あらゆる局面は先手勝ちか後手勝ちか、両者最善を尽くした場合の結果が決まっています。
そう言われるとどんな局面がどっち勝ちか知りたくなってきますよね? ...
少なくとも僕はなりました。
それで5単位(ペントミノ)の全組合せ66通りと6単位(ヘキソミノ)の全組合せ595通りを手作業で解析したりしていたのですが*1、そんなことをするくらいならプログラムを書けばいいじゃないかということで探索プログラムを書き始めました。
詰め探索プログラム
作成したプログラムは、局面を入力すると、先手後手ともに最善手をとった場合にどちらが勝つか、何手で勝つかを出力するというものです。
言語は当時勉強しようとしていたHaskellで書きました。
え?Haskell?と不安になった方も、この記事ではコードは出てこないので安心してください。
コードはGitHubに置いてあります。 あまり分かりやすいコードにはなっていませんが、Haskellが読めて実装を見たいという方はどうぞ。
GitHub - rkat0/Godomachi: A checkmate search program of Godomachi.
ここでは使用したアルゴリズムについてざっくりと説明したいと思います。
細かいことはいろいろあるのですが、
あたりが主要なアルゴリズムだと思うのでこの辺をまとめたいと考えています。
ポリオミノの列挙
このゲームでは合同かどうかだけが重要なので、ここでやりたいことは、回転・反転した関係のものを同一視する、両面ポリオミノと呼ばれるものの列挙です。
回転や反転を同一視しない、向きを考慮したポリオミノの列挙はRedelmeierのアルゴリズムという効率の良さそうなアルゴリズムがありますが、両面ポリオミノの列挙は特に効率の良いものはないようです。
いろいろ調べていたらこんなものを見つけました。
Free polyominoes enumeration - Rosetta Code
いろんな言語でコードが載っています。
アルゴリズムはこのようなものです:
- モノミノを用意する。
- 今、(-1)-オミノが列挙できているとする。それぞれに対し、どこかに1個ブロックを追加したものを列挙することで-オミノを作る。
- 回転、反転の変換によって同じとなるものは1つを残して除去する。
- 2,3を繰り返し、-オミノになったら終了。
何も難しいことはしていなくて、1マスのモノミノから始めて1つずつ大きいポリオミノを作っていくという方法です。
細かい部分で効率化できそうな気もしますが、とりあえず先へ進みます。
ポリオミノの切り方の列挙
この記事のメインです。
ある局面から次の手を生成するとき、お互いのポリオミノに対して2つの連結部分に切り分ける方法を列挙し、その中から合同な破片を持つ組を探すという方法をとりました。
ここで、ポリオミノの切り方を列挙することが必要になります。
アルゴリズムその1
まず、ポリオミノのブロックの隣接関係をグラフで表現します。
具体的には、ポリオミノの各ブロックを頂点とし、隣接しているブロックを枝で結んだグラフを作ります。
切り方の特別な場合として、ポリオミノから1マスを切り取る場合を考えてみます。
を切り取ることは、グラフでは対応する頂点を取り除くことに対応します。
このとき、残りのグラフ(=残りの図形)は連結でないといけないので、を取り除けるのはがグラフの結節点*3でないときだといえます。
(ちなみに、結節点の列挙は線形時間のアルゴリズムが存在します。)
では次に、1マスの切り方を元に2マスの切り方を考えてみます。
1マス切り取れる各ブロックに対し、隣接するブロックを1つくっつけたものを列挙します。
ここから重複を除けば2マスの候補が列挙ができます。
これが切り取れる条件は、くっつけた方のブロックが、1マス切り取った後のグラフで結節点になっていないことです。
同じようにしてどんどん大きな切り方をつくることができます。
ポリオミノを2つに分けるとき、必ず片方は元の半分以下のサイズになることから、切り取る図形は元の半分の大きさまで調べればOKです。
そして最後に、同等な切り方(同じ形に分ける切り方)を除去します。*4
これで終わり、だと楽だったんですが、さすがにそんなことはなかったです。
アルゴリズムその2
2マス取る方法はないけど3マス取ることはできる、みたいなものがあります。
なぜこのようなことが起こるかというと3つ以上の連結成分を繋ぐような結節点があるからです。 このような結節点は1方向から攻めている限りは切り取ることができません。
そこで、3つ以上の連結成分を繋ぐ結節点それぞれに対し、それを切り取るために必要な最小の塊*5を計算します。
その中で大きさが元(-オミノとします。)の半分以下のもの、例えば大きさ ()のものが見つかったとしたら、上の方法でマス取る方法を列挙した後にリストに付け加えてやります。
結節点を切り取るために必要な最小の塊はどう計算するのかですが、
注目する結節点からつながっている各方向に向けて探索を行い、いくつのブロックがあるかを数えます。
別の方向から出発したものが途中で合流したらまとめて1つとします。
その中で一番大きいものを残した全てが最小の塊です。
さて、これで今度こそアルゴリズム完成
...だと結構長い間信じてました。
これでも上手くいかないケースがありました。
アルゴリズムその3
この形。8単位、オクトミノで初めて現れる形です。
これを4マスのLテトロミノ2つに分解してくれないのです。
原因は、プログラムの気持ちになって考えてみると分かります。
まず、結節点となるのは中央の4マスです。 各結節点を取るための最小の塊である2マスの取り方は見つけられるのですが、そこから伸ばせる先は全て残りのグラフで結節点なので、そこで終了してしまいます。
どうすればいいか考えた結果、最初のグラフに対して結節点を取り除くための最小の塊を計算していたところを、切り取った残りのグラフから結節点を取ろうとしたときに計算することにしました。 ここでは「3つ以上に分かれる〜」という条件はつけません。
少し無駄がある方法のような気もしますが、それがどの程度なのかは正直よく分からないです。
おそらくこれで間違いは無いと思いますが、証明はしてないのでもしかしたら上手くいかない場合があるかもしれません。
今のところは上手くいっています。
最終的なアルゴリズム:
- ポリオミノの各ブロックを頂点とし、隣り合っているブロックを枝で表現したグラフを作る。
- の結節点でない頂点を列挙し、1マスの切り方を列挙。
- マスを切り取る方法が列挙できているとき、個のブロックのどこかに接していて、残りのグラフで結節点になっていないものを列挙してくっつけることでkマスの切り取り方を列挙。
- 3.で結節点を見つけた場合、からその結節点を切り取るための最小の塊を計算し、マスと足して全体の半分以下なら、そのマス数の切り方候補として覚えておく。
- 3.4.を繰り返しての半分の大きさまで切り方を探す。
- 同等な切り方を除去する。
アルゴリズムその4?
...今また別のアルゴリズムを思いつきました。検証ができたらまとめたいと思います。
詰め探索
いよいよ最後です。
コンピュータ将棋の(実戦の)詰め探索では証明数、反証数を用いた方法が使われたりするのですが、これで最短手数の詰みが見つかるのかなどよく分かっていない部分があるのでmini-max法で探索します。
今まで以上にざっくりな説明になりますが、ゲーム木の探索についての解説はいろいろなところにあるので、必要ならそのようなものを参照していただければと思います。
mini-max法
mini-max法は、各局面に対して評価値が計算できるときに次の手を決めるアルゴリズムです。 先手と後手の有利不利が対称的であることを利用し、先手は評価値が最大となる手を、後手は評価値が最小となる手を選んでいきます。 つまり、お互いが最善の手を選ぶということですね。
ゴドマチは先後で取れる手が同じで、同じ最終局面を目指すので、詰み筋が奇数手で終わるなら先手勝ち、偶数手なら後手勝ち*6となります。 そこで、評価値は、
となるようにします。
具体的な評価値の計算方法ですが、まず、
単位マッチの場合は決着までの手数が必ず手未満になります。
これを利用し、手で詰んだ場合の評価値は、が奇数なら、が偶数ならと計算しました。
ある局面の評価値は、先手の場合は次に移れる局面の中で最大の評価値、後手の場合は最小の評価値とし、最終局面に対してはそこまでの手数に対して上の計算式で点数をつけます。 これであとは正しい実装をすれば詰め探索ができます。
よくあるmini-maxのイメージ:
法*7
詰め探索は可能になりましたが、mini-maxだけでは全探索してしまうので、枝刈りをして高速化を図ります。
例えば、先手が5手詰めを見つけている場合、他の3手目を探索するときに、その時点で詰まなければその先は調べる必要はありません。4手目以降で負けるか、良くても5手詰めで、今より評価値が上がることはないからです。 さらに、3手詰めを見つけた場合は、その3手目の探索を続ける必要はなくなります。 後手に対しても全く同じことがいえるため、先後に関係なく、ある深さの探索をする中で手の詰みを見つけたら、それ以降は手目で詰むかどうかを見ればよく、手詰めを見つけたらその深さの探索は終了してしまってOKです。(他の手順での深さの探索は打ち切れません。)
枝刈りのイメージ:
四角は先手番、丸は後手番を表し、数字はその局面から最善手をとったときの全体の詰み手数です。
評価値ではないので注意してください。
さらに細かい点ですが、手を探すときに大きく切る方法から試していくと短い手数の詰みが初期に見つかりやすくなり、枝刈りがより効率的に働くと思われます。
まとめ
最初に示した3つのアルゴリズムについてざっくりとですが説明しました。
ポリオミノの切り方の列挙は他にもいろいろなやり方があると思います。
これを書きながら新しいアルゴリズムを思いついたりしたので、そちらも実装して検証ができたらまとめてみようと思います。