天体ショーについて

この記事はペンシルパズルI Advent Calendar 2021 - Adventarの16日目の記事である。

天体ショーについて書く。とりとめなく書くことを許されたい。

最初に

  • 想定読者:天体ショーを知っているものとする。

  • 前提:天体ショーは絵が出るパズルであるが、この記事の作者は絵を描くのが(まだ)あまりうまくないので、ノウハウ的なことはあまり書けない。

天体ショーにおける、特に基本的な形として、目と川を紹介する。

鉱物と生物

図1 鉱物

天体ショーを解き始める。図1のように盤面に星が密集している領域があるとする。この領域の情報だけから、この領域の星の形が確定する。これを鉱物と呼んでいる。

鉱物を構成するそれぞれのブロックを「単体」と呼んでいる。単体の形状は1x1、1x2、2x1、2x2のいずれかである。特に1x1を「石」、ドミノ(1x2と2x1)を「板」、2x2を「岩」と呼んでいる。

図2 生き生きとした生物

鉱物は「死んでいる」形であるため、鉱物だけではパズルにならない。そこで、パズルを作る際は図2のような生き生きとした形(「生物」)を用いる。

正確に書くと、ある星が、隣接する星との直接接触によって四方を完全にふさがれている時、その星を「死んでいる」と呼んでいる。生きているというのは死んでいないということだ。生きている星を含む星の集合(星群)を生物と呼ぶ(定義の上では生物が鉱物を真部分集合として含む場合があるが、星の下のマスの連結成分など、なんらかの分割を一つの単位として星群とみなすと考え、気にしない)。

天体ショーを作る際には、盤面に鉱物と生物を散りばめていく。鉱物は上記の通り複雑なロジックにはならないが、メリハリをつけて何かをアピールするのに適している。生物はそれ自体、どの程度生き生きしているかという自由度のパラメータを持つが、お互いに複雑な相互作用をすることによって予想のつかないような魅力的な展開や形が現れる。これが面白い。

生物を構成する重要な要素として、「目」が挙げられる。

図3 4つの目(A~D)を持つ生物

図3の生物は4つの「目」A~Dを持っている。「目」というのは、平らな壁(地面)の上に単体をつけた形であり、鉱物を生物にするものである。図3を見てわかるように、石を地面につけた形(A)、板を地面に寝かせた形(B)、板を地面からはやした形(C)、岩を地面につけた形(D)の4種類が存在する。

図4 立派な目

目だけで構成された生物として、図4のような形が挙げられる。目がたくさんあるというのはやはりどこか気持ち悪さがあるものだが、それはともかくとして、3つ以上目が並んだ形は特に「立派な目」と呼んで特別視している。

目は、耳や川や扇状地やパイプオルガンやバグパイプとも関係する重要な概念であるが、今回は特にパイプとの関係性について書く。

パイプ

空間と空間をつなぐ星をパイプと呼ぶ。

図5 目は空間をつなぐ

空間をつなぐという表現が適切かは不明だが、Aで意図が伝わるであろう。Bはつないでいるイメージではないが、この際、実際に空間をつないでいるイメージになっているかどうかは気にしない。Cの目もパイプである。定義がふわっとしているが、全ての生きている星はパイプであると言って良い。パイプという言い方を導入するのは、その星を、空間をつなぐ要素であると認識していることを明示するためである。

図6 生物の連結構造とパイプ

図3に載せた形を改めて図6で眺める。これは4つの目を持つ生物であった。星と星の直接接触によって生じる壁の連結成分は、目を挟んで存在している。この目は同時にパイプでもあり、緑色の線で示したように空間をつないでいる。これは双対グラフのような関係になっている。生物を分類して考察する上で有用な観点となるだろう。

グラフの構造と機能性の関係は、例えば次のように考えられる:

  • 図6のようなスターグラフになる場合には、近接しているパイプがお互いの機能を抑制する。つまり、どれか一つのパイプのブロックが巨大化すると、隣接しているパイプは大きくなることが困難になるだろう。
  • 直線のグラフの場合は本質的に立派な目と似たような機能性になる。つまり、まっすぐにブロックが大きくなる限りは、隣接しているパイプはお互いの巨大化を制限しない。

前者は直列的なパイプの配列で、後者は並列的なパイプの配列である。

図7 (左)直列的なパイプ配列と(右)並列的なパイプ配列

特に直列的なパイプは、チェーンと関連している。

チェーンの変形

パイプがつながった形をチェーンと呼んでいる*1

図8 チェーン

図8は典型的なチェーンの模式図である。この場合はX0からX4までの5つのノードが4つのパイプでつながっており、長さ4のチェーンと呼んでいる。

天体ショー研究Wikiではチェーンの内部構造に興味がなく大域的なふるまいだけを問題にする時、ワイヤーと呼ぶことにしている。ワイヤーの端のパイプが端のマスを回収する(⇔回収しない)とき、そのワイヤーは(そのマスに対して)出っ張った(⇔引っ張った)と言う。逆にワイヤーの外側から見た時は、マスがワイヤーを引き出した(⇔押し出した)と言う。

図9 (左)奇数チェーンの伸縮性と(右)偶数チェーンの耐震性

チェーンは長さの偶奇によって異なる性質を持つ。偶数チェーンの場合は両端の「出っ張り/引っ張り」が一致するのに対し、奇数チェーンの場合は逆になる。図9に奇数チェーンと偶数チェーンの例を(左右に)並べている。

特に一次元天体ショーの場合を考えると、奇数チェーン(図9の左)は、全体が伸縮しているとも解釈できる。対して偶数チェーン(図9の右)は、全体が振動しているように解釈ができる。一般にこのような「全体の変形」を伸縮性/耐震性と呼んで興味を持っている。

(例えば偶数チェーンと奇数チェーンを直列に連結すると当然奇数チェーンとなるが、これは伸縮性と耐震性がZ/2Z的な演算と自然に対応していると見ることもできるが、天体ショーの場合はもう少しだけ複雑な例を考えることが可能で、これはZ/2Z代数の一般化と考えることができないだろうか)。

一般に左側にx、右側にyだけ伸びる変形を(x, y)と書くことにする。図9左のパターンは{(1, 1), (0, 0)}である。図9右のパターンは{(1, 0), (0, 1)}である*2。x-y平面にプロットすると、前者はy=xの直線上に、後者はy+x=1の直線上にくる(図10)。

図10 伸縮性と耐震性は格子点の集合

上の議論をノードのマスがnの場合や連続的な変形を許す天体ショーへと一般化することは簡単な問題である。ここでは「川の氾濫」との関連性について書く。

川の氾濫

図11 (左)川と(右)川の氾濫

少し前に「目」という概念を紹介したが、立派な目がまっすぐに伸びると「川」の形になる。川とは高さの等しい長方形が並んだ形である。川の形は別解を持つ場合があり、図11のように川の内のいくつかが広がる形を川の氾濫と呼んでいる。

川の氾濫による別解の本質は、氾濫原(星が並んでいる列から外れた列)において星が消滅することができる点にある。例えば図11の右上の形は、中央の星が氾濫原で暴れることによって、左右の星が氾濫原で消滅している。図11の右下の形は、左から1番目、3番目と5番目の星が氾濫原で消滅している。消滅した星は、最初からなかったとしてもこの形には解が存在している。

川の氾濫はチェーンにおける変形の議論と関係している。図12を見よ。

図12 チェーンと川の氾濫

図12で(a)、(b)はこれまでの一次元天体ショーの議論とおおむね同じ話になるところである。(c)は川の氾濫(と、ついでに包み込み)が絡んでいる。

川の氾濫をこれまでの枠組みの拡張として考える(図13)。

図13 氾濫における変形

(b)の状態を基準として、幅をつぶす(a)の変形と、逆に幅を広げる(c), (d), ...の変形が考えられる*3。(b)は座標では(0, 0)、(c), (d), ...はそれぞれ(1, 1), (2, 2), ...と書くことができる。問題は(a)である。図13では(-0.5, -0.5)であるかのような矢印を描いているが、(-1, 0)や(0, -1)といった解釈をしても良いだろう。xとyの合計が-1となるこの変形を「[-1]」と表現することにする。

図14 消滅ライン[-1]

川の消滅は、xとyの合計が一定となる直線によって表現される。このライン[-n]を一般に消滅ラインと呼んでいる。

図15 氾濫の相互作用

川が複数並ぶといくらか面白くなってくる。図15に川が2つの例を載せる。

川と川が連結すると、2つの効果が生まれる。一つは連結によって格子点が殺される効果で、もう一つは消滅ラインによって格子点が特殊な点を生成する効果である。通常(i, j)と(l, m)がギャップkで連結する際はj+l=kの関係式を満たす場合にのみ結合が許容され、結果は(i, m)となるのだが、消滅ライン[-n]に関しては-nを都合の良いxとyに分解して演算することができる。このために特殊な格子点が生まれる。全ての川はちょうど一つの消滅ラインを持っており、消滅ラインどうしの演算によって新しい消滅ラインを求めることができる。もっとスマートなとらえ方がありそうだが、一つの考え方として紹介した。

誘導と推測

誘導と推測は密接に関係している対照的な(対称的な)概念である。ここでは天体ショーにおける推測と誘導について書く。

絵柄と推測:総合評価

天体ショーには大きく4つの要素がある。

  1. 描きたい対象
  2. 絵柄(構図等)による表現
  3. ドット絵
  4. パズル

天体ショーを作る際の標準的な(理想的な)流れは1.→4.という風に進む。

逆に解く場合の標準的な(理想的な)流れは4.→1.という風に進む。

というのが素直にパズルを楽しむやり方だが、あえてこの流れに沿わずに他の道を探してみるのも面白い。 そういった敢えての流れの一つが推測である。推測とは本来は「近道をする」ための道具の印象だが、ここでは敢えての話をしているので、わざと遠回りをするものも含めて考えている。

まず絵柄の推測について。 自然に思いつくのは、あるマスの色は、そのマスに一番近い星の色になる、というものである。これは、一般に知られている最近傍探索の手法、例えばkd-treeを用いて解くことができる。ただし、天体ショーの場合は星の配置が半整数座標、マスの配置が半奇数座標となるため、同じ距離に複数の点がある状況がしばしば生じることには注意する。kd-treeはデータ点の平面で分割をするため、少し怪しいかもしれない。今はいったん気にしないで、これを「最近傍着色」と呼ぶことにする。

最近傍着色はボロノイ着色(ボロノイ分割をしてから各領域に星の色をつける)をドット絵化したものとみることもできる。

もう2つほど簡単な推測方法を挙げる。

  • クエリから第三近傍まで星を求め、色について多数決を取る。
  • クエリから全ての星までの距離を求め、黒の平均と白の平均で小さい方を採用する。

実際のデータに対して試してみる。いくつか例を載せる(図16~図19)。

追記2022/1/12:プログラムにバグがあった。このため、図16~図19と、それ以降の記述に修正を加えている。

図16 仔馬の絵柄の推測
図17 ハンガー
図18 ロウソク
図19 ニコリ

結果を見ると(b)距離の平均による推測は使い物にならないことがわかった。一様分布の場合星はクエリの近くよりも遠くにたくさん存在する傾向を持つため、遠い点の寄与が多くなってしまう。このため距離に応じて減衰する重み(発散を抑えた逆数やガウシアンなど)を加えて平均することが考えられる。一方で、純粋に密度が高いところをその色にしたいと考えて、密度分布を作ってから、黒の密度分布と白の密度分布を比較する、という考え方もある。これは結局同じことになるが、直感的にはよりわかりやすい。もっと広く線形演算を二つ作って比較する枠組みに含むことができる。こう考えていくと徐々に議論が一般の方向に進んでいくが、どちらかというともっと単純な判定方法に興味があるのでこの話は掘り下げない。

最近傍着色と3近傍多数決の結果を正解の絵柄と比較すると、傾向として、細い線が消えやすいことがわかる。これは天体ショーを作問する際に、細い線を隠すことは簡単だが面積を持った構造を隠すのは難しいことを考えれば自然な結果と言える。

これらの推測はどの程度妥当な結果を与えるだろうか。

評価のために人工的に作成された天体ショーのデータを用いる。私がこれまでに作成した450問の(通常ルールの)天体ショーの内絵を描いている問題全49問と、私がこれまでに解いた469問の天体ショーデータの内絵を描いている問題全220問の、合計269問を用いて評価をする。結果、最近傍着色の正解率(accuracy)は0.86±0.08、3近傍多数決の正解率は0.70±0.12となった。

正解率はお世辞にも高いとは言えないが、90%を超えるようなら天体ショーを解くモチベーションが削がれてしまう、という観点で言えば、70~80%に留まったのはパズル作家群の頑張りの成果だろう。

追記2022/1/12:最近傍着色による正解率はバグの修正によって上昇して、80%を超えてきた。思ったよりも正解するという印象である。

全体としての評価は以上だが、もう少し個別に精度の良いところ悪いところに注目する。

絵柄と推測:個別の考察

例えば同一色の星に周囲が完全に囲まれた空間がある場合、そこでは推測が外れることはない。推測がはずれるのは、複数の色に囲まれた空間ということになる。空間内のある点に注目したとき、周囲がどのように囲まれているか、という(ある意味で非常に感覚的な)概念を「雰囲気」と呼んでいる。

図20 (左)同一色に囲まれた雰囲気と(右)2色に囲まれた雰囲気

図20左のように周囲一帯が白一色の場合は囲まれた領域は必ず白になる。一方で図20右のように複数の色に挟まれた雰囲気空間においては、中央が何色になるかは、近傍の情報だけからは分からないため、最近傍着色や3近傍多数決のような近傍に頼る手法では正しい色を推定できない。したがってこのような雰囲気では正解率がおおよそ半分になると考えられる。

図21 チェーンと色推測の面積均一化

チェーンの話を思い出す。図21(a), (b)のようにチェーンは面積が不均一となる可能性を持っているが、近傍に基づく判定では(c)のようなパターンが選択される傾向にある(境界面が垂直二等分線あたりに来やすい)。このため、面積が均一となる傾向を持つと考えられる。

その他、頂点が丸くなる現象や、線が分断される/結合する現象が挙げられるだろう。

絵柄を推測するアプローチとして、絵柄の絵柄らしさを用いるアプローチも存在する。典型的には、黒星が斜めに並んでいる場合に斜めに黒い線が走っていると推測してブロック形状を決める方法が挙げられる。誘導と推測が関係していると書いたように、これを逆手にとって斜めに黒い線が走っているように見せかけることは理論上は可能だが、かなり高度な作問力が求められると思われる。

対称性に基づく推測と誘導

絵柄に関する推測について書いてきたが、天体ショーには星の配置のみに基づく誘導/推測も存在する。

図22 疎疎マッチング

図22左では、X、Y、Zの領域で星の密度が低くなっている。このような状況では、疎な領域と疎な領域をつなぐようなブロックが存在する可能性がある。そこで事前に疎な領域どうしをマッチングしてやる、という考え方を「疎疎マッチング」と呼んでいる。

天体ショーは対称性をテーマとするパズルであり、これに似た推測のできるパターンがいくつか存在している。図23で説明する。

図23 対称輪郭誘導

図23の状況を見ると、緑色の部分が上下で類似した形をしており、「なんとなく」つながる構造が見えてくる。「なんとなく」で構造を見せるためには、天体ショーの場合、類似した形、特に輪郭線を入れるのがわかりやすい。右辺の青色の線のあたりも「なんとなく」で見えてくる部分である。 もちろん推測は当たるとは限らない。パズルの作り手側は、解き手の推測の可能性を踏まえた上で偽の誘導を仕込むことができる。例えば赤色の線のようにつながる可能性を先ほどの緑の線と合わせて二択にする。その場合、例えばXのあたりに星を置くと、赤線の誘導が強化される。

最後に

今回はここまでとしておく。あまり書けなかったが、天体ショーが面白いのだということが少しでも伝わっていると嬉しい。

*1:少し不正確な表現をしている。天体ショー研究Wikiではパイプとノードが交互につながった形と定義している。

*2:どこをゼロにするかという話も絡んでくるが、今は星のあるマスの端をゼロとしている。

*3:図12の例のような包み込みはここでは考慮しない。