Hatena::ブログ(Diary)

tosの日記

2017-02-05

マリオメーカーのTuring完全性

22:40

ここ最近Turing完全性などに(細かい部分も含めて)興味を持っていたのは,実は,そー氏*1マリオメーカー*2研究がきっかけでした。今日公開された動画にちょっとだけ協力していたので宣伝します。

マリオメーカーはチューリング完全だった【万能計算機】

D

私はマリオメーカーについては素人で,計算コースの実装とかはできないのですが,確か,そー氏によって「最初の証明」*3のステージが作られたくらいのときに

  • 「Rule 110の完全性を用いているけど,その『有限』だとまずくない?」
  • 「Cyclic tag systemならすでにある(そー氏がマリオメーカー学会で発表済みの)テクで実装できるのでは」

みたいなことを伝えたら,数日しか経たないうちに「真の証明」のステージが返ってきたという……。

*1:っていうかyos

*2マリオの自作ステージが作れるWii Uソフト

*3:動画中での呼び方

2017-01-02

Wolfram's (2, 3)-Turing machineの「普遍性の証明」を読む

15:11

ここで,(2, 3)-Turing machineとはstateが2つ,テープalphabetsが3つのTuring machineのこと。alphabetsを{0, 1, 2}とおき,statesを{A, B}とおく。Wolframが次の遷移規則の(2, 3)-Turing machineが普遍 (universal) か否かに懸賞金25,000 USDをかけた。

A B
0 1, →, B 2, ←, A
1 2, ←, A 2, →, B
2 1, ←, A 0, →, A

(たとえば,左上の規則(A, 0; 1, →, B)は「state Aで0を読んだとき,1を書き,右に移動し,state Bに遷移する」と読む。)

2007年5月14日,Alex Smithの肯定的な答え (https://www.wolframscience.com/prizes/tm23/TM23Proof.pdf) にWolfram Research懸賞金を出したことが発表されたが,メーリングリストFOM -- Foundations of Mathematics議論によれば通常の意味でのuniversal Turing machineであることの証明にはなっていないという話もあったりして,どういうことか自分で読んで確かめてみることにした。

最初にこの日記の結論を書いてしまうと,まあまあ面白かったが,かなり駄目な感じ。当時学部学生だったAlex Smithは良いけど,何のフォローもしないままこれを大々的に発表したWolfram Researchははっきり言って【あとで書く

Turing machineの無駄を取り除く

Alex Smithの記法に従って,元の(2, 3)-Turing machineをsystem 0とよぶ。system 0と本質的に動作が同じで解析が簡単なsystem 3をまず構成している。Turing machineは現在のヘッドの位置のセルしか読み書きできないが,1つ右のセルも読み書きできるようなsystemを考えると今回は都合が良くなる。この部分の議論は3段階からなるので,勝手にa., b., c.とよぶことにする。

f:id:toslunar:20170102142655p:image:rightだいたい,図の青丸で囲んだ部分が「無駄」なことと,青線の前後で色が入れ替わるのが「見にくい」ことを対処している。

考察a. system 0でsystem 1を模倣*1:(B, 2; 0, →, A)の次の次に(A, 0; 1, →, B)で上書きする場合について3 stepsを1 stepにまとめる。

考察b. system 1でsystem 2を模倣:読み出し時にalphabetsの1, 2を入れ替えるhookがかかるstate Bを考え,それをstate Cとおく。system 1は右セルに依存して右セルを書き換えていたが,system 2は右セルに依存するものの右セルを書き換えなくなった。後の議論を考える上では,Cはcarry(繰り上がり)のCだと覚えると良さそう(ただし,原論文にはそう書かれてはいない)。

考察c. system 2でsystem 3を模倣:テープのうちヘッドの左側(state Aのときはinclusive,state B or Cのときはexclusive)の1, 2を入れ替える。これで,state Aの挙動が「0が現れるまで左に行って2を書いて右に1歩戻ってstate Bに遷移」になる。

ここで定義されたsystem 3は

A B C
0 2, →, B 2, ←, A 2, ←, A
1(右が1 or 2) 1, ←, A 1, →, B 2, →, C
1(右が0) 1, ←, A 1, →, B 0, →, A
2(右が1 or 2) 2, ←, A 2, →, C 1, →, B
2(右が0) 2, ←, A 0, →, A 1, →, B

となっていて,同じ文字での上書き,同じ状態への遷移を省略すると,

A B C
0 2, →, B 2, ←, A 2, ←, A
1(右が1 or 2) 2, →
1(右が0) 0, →, A
2(右が1 or 2) →, C 1, →, B
2(右が0) 0, →, A 1, →, B

となる。Alphabets 1, 2のみが現れる部分の見通しが良くなっているのがポイント。

補足

原論文の考察a.のところを少し変えて,(B, 2; 0, →, A)での0の書き込みを遅延させると考え,

A B C
0 2, →, B 2, ←, A ←, 0, →, A
1 2, →
2 →, C 1, →, B

とする方が分かりやすそう。さらに,alphabetsを{#, 0, 1}にして,

A B C
# 1, →, B 1, ←, A ←, #, →, A
0 1, →
1 →, C 0, →, B

system 3'とおく。以下ではこれをsystem 3の代わりに用いて(system 4までの)議論をする。

set, scan, parity

さて,system 3'でテープの左に戻るには#を他のalphabetsに書き換えなければならないことに注目する。テープの左右(無限にのびているところ)以外に#が「ほとんど」ない場合に限定して考察することになる。

Lemma 1では0, 1のみが並んでいる箇所に着目する。原論文ではalphabets 0, 1からなるL=2w個の並び(wは0以上の整数)を単にsetとよんだりしているが,ここでは,順不同な「集合」と区別するためにセットと表記する。ちなみに,Lemma 1.1以外では個数が2べきという制約が不要。

セットの左端のセルでstate B or Cになっていたときを考える。L steps後にセットの右に隣接するセルに到達し,この間state Aにはならない。このL stepsをスキャンとよぶ。(ただし原論文では,スキャンの開始時点のことをscanとよんでいる。)

スキャン前後のstatesについてB, Cをそれぞれ0, 1とみなすことで,stateとセット(Lセルからなる)のスキャンでの変化は線形写像

f: F2 × F2LF2 × F2L(ここで,F2 = Z/2Z

f(s, (xi)i=0…L-1) = (s + Σj=0…L-1 xi, (s + Σj=0…i xi)i=0…L-1)

となる。*2

Haskellっぽく書くと,

f 0 xs = (last ys, ys) where ys = scanl1 (+) xs

とくに,セットのparityを1の個数の偶奇(すなわち Σj=0…L-1 xi)として定めると,次が分かる(Lemma 2.2の言い換え):

  • parityが0 (mod 2)だったとき,スキャン前後のstateは等しく,
  • parityが1 (mod 2)だったとき,スキャン前後のstateはB, Cのうち逆のものとなる。

つまり,スキャンによってセットのparityを読み出すことができる。

自然数の集合のエンコード

スキャンによってセットは変化しているので,次に同じセットをスキャンするときには異なる(かもしれない)parityを読み出せる。セットのあるスキャンの終了時と次のスキャンの開始時のセットが等しいことが分かる。(なぜなら,考慮すべき唯一の場合は,スキャン終了直後にセットの右端のセルで1が#に書き換えられる場合だが,このセルにヘッドが通りがかるときに1に戻される。)

B, Cどちらのstateでスキャンするかによって次に読むときのparityに影響がある……と思いきや,L=2wのときは, 2w回以下のスキャンの結果は変わらない。(Corollary 0)

例えば,L=8=23のとき,0回目のスキャン前のstateの差が初めて影響するのは8回目となる(線形性より差のみを考えれば十分)。

  • f(1, (0, 0, 0, 0, 0, 0, 0, 0)) = (1, (1, 1, 1, 1, 1, 1, 1, 1))
  • f(0, (1, 1, 1, 1, 1, 1, 1, 1)) = (0, (1, 0, 1, 0, 1, 0, 1, 0))
  • f(0, (1, 0, 1, 0, 1, 0, 1, 0)) = (0, (1, 1, 0, 0, 1, 1, 0, 0))
  • f(0, (1, 1, 0, 0, 1, 1, 0, 0)) = (0, (1, 0, 0, 0, 1, 0, 0, 0))
  • f(0, (1, 0, 0, 0, 1, 0, 0, 0)) = (0, (1, 1, 1, 1, 0, 0, 0, 0))
  • f(0, (1, 1, 1, 1, 0, 0, 0, 0)) = (0, (1, 0, 1, 0, 0, 0, 0, 0))
  • f(0, (1, 0, 1, 0, 0, 0, 0, 0)) = (0, (1, 1, 0, 0, 0, 0, 0, 0))
  • f(0, (1, 1, 0, 0, 0, 0, 0, 0)) = (0, (1, 0, 0, 0, 0, 0, 0, 0))
  • f(0, (1, 0, 0, 0, 0, 0, 0, 0)) = (1, (1, 1, 1, 1, 1, 1, 1, 1))

また,この例で現れる2w個のセットはF22wの基底をなすので,

  • セットに書かれたalphabetsの列と
  • 0回目から2w-1回目のスキャンで読まれるparityの列

の間に全単射g: F22wF22wがある。*3よって,0以上2w未満の整数の集合を長さ2wのセットにエンコードすることができる。(Method 2)

例えば,w=3で,

  • {0} ↦ 10000000
  • {1} ↦ 11000000
  • {2} ↦ 10100000
  • {3} ↦ 11110000
  • {4} ↦ 10001000
  • {7} ↦11111111
  • {1, 4, 7} ↦ 11000000 xor 10001000 xor 11111111 = 11010111

などのようになる。

スキャンを遷移に

ここからは,長さが2べきのセットのみを考える。また,以後の議論はどのセットもスキャンが2w回以下しか行われないように注意しなければならない。

さらに,

  • ヘッドの左にあるセットの右端の1セル,または
  • ヘッドの右にあるセットの左端の1セル

に限り#が書かれていることを許すことにする。

  • 前者については,そのセットから読み出されるparitiesは#の代わりに1が書かれている場合と等しくなる。
  • 後者については,初めてそのセット(の左端の#が書かれたセル)に到達したときに,stateがBかCかで読み出されるparitiesが変わる。
    • State Bの場合,1, ←, Aが実行されるので,スキャンされなかっとみなし,#の代わりに1が書かれている場合と等しくなる。
    • State Cの場合,←, #, →, (A), 1, →, Bとなるので,(#の代わりに1が書かれていた場合に0, →, Bとなることと比較して,)今回読み出されるparityは等しく次にスキャンするときのセットは左端のセルが1か0かのみ異なる。よって,1回目(この日記では回数は0回目から数えていることに注意)のparityのみが変わることになる。

(p. 12から始まるWhy the initial condition worksの2, 4, 5でこのような議論がされている……と思う。)

この考察をまとめると,system 4が得られる:テープの各セルには,0以上2w-2未満の整数の集合または新しいalphabet *が書かれている。ただし*が書かれているセルが隣接してはならない。この*は#の書かれている位置を表す。遷移規則は

A B C
集合S (0 ∈ S) (S - 1), → (S - 1), →
集合S (0 ∉ S) (S - 1), →, C (S - 1), →, B
* セルを削除しながら← セルを削除しながら←, A →, (S xor {1})

where S - 1 = { n - 1 | n ∈ S, n ≥ 1 }, S xor {1} = (S ∪ {1}) \ (S ∩ {1})

system 3'での(あらかじめ決められたstep数の実行について,十分大きいwを適切に選んだ)system 4の模倣は次の例のようになる。この例ではw=3とする。

  • system 4の状態として,テープが… {3} * {1, 4} {1, 5} * {2} …であって,ヘッドが{1, 4}のところを指しているとする。
  • 2w-2=6, 2w-2=7で調整して,{3, 6, 7}, {1, 4, 7}, {1, 5, 7}, {2, 6, 7}をエンコードすると順に11100001, 11010111, 11110011, 10110001となる(それぞれのセットの両端が1となるようにした)。
  • system 3'のテープは,… 1110000# 11010111 11110011 #0110011 …(説明のために8セルからなるセットごとに空白で区切った)。ヘッドは8セル目({1, 4, 7}に対応するセットの左端のセル)を指している。

(帰着できていることを確かめるとき,system 4の遷移(C, *; →, (S xor {1}))では*の扱いが変わることに混乱してた。)

原論文では,この時点で(両側ではなく)右側のみ無限にのびているテープを考え,テープの左端については特殊な扱いをするが,省略。

これをさらに整理

特別なテープの状態に限定した場合のsystem 4を考え,system 5を得る。System 4によるsystem 5の模倣には十分大きいパラメータfをとる必要があるらしい。

System 5は1以上の整数の集合の非空有限列の書き換え規則。最初の集合と残りの集合は扱いが異なるのでそれを反映した記法にしておこう。

  • (S; R0, R1, …) → (S - 1; R0 + 1, R1 + 1, …) if 1 ∉ S
  • (S; R0, R1, …) → (((S - 1) \ {0}) xor (R0 + 1); R1 + 1, R2 + 1, …) if 1 ∈ S

この帰着ではsystem 4のヘッドがセミコロン(;)で表したあたりを往復する場合に限定されている。(*をはさまず)連続しているセットは続いてスキャンされるが,それらのスキャンをまとめて考えるとparitiesのxorとなることが主要な考察っぽい。この考察以外の原論文での議論をあまり追っていない。

system 5をcyclic tag systemに帰着しようとしている

あらかじめcyclic tag systemを次のように変換しておく:(110; 11, 0, 01, ε) ↦ (111100; 1111, ε, 00, ε, 0011, ε, ε, ε)

具体例でまず説明すると,working string 111100を{1, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16}に変換。3-1=2, 6-4=2, 9-7=2, 12-10=2, 14-13=1, 16-15=1を間をあけて並べた。また最初のrule 1111は{21, 24, 27, 30}, {19, 22, 25, 28}に変換される。(一般には,ruleで同じalphabet 2個ずつ並ぶように変換してあったことを使う。)

Cyclic tag systemの(111100; 1111, ε, 00, ε, 0011, ε, ε, ε) → (111001111; ε, 00, ε, 0011, ε, ε, ε, 1111)に対応して,system 5では

({1, 3, 4, 6, 7, 9, 10, 12, 13, 14, 15, 16}; {21, 24, 27, 30}, {19, 22, 25, 28}, {}, (中略), {})

→ ({2, 3, 5, 6, 8, 9, 11, 12, 13, 14, 15, 22, 25, 28, 31}; {20, 23, 26, 29}, {}, (中略), {})

→ ({1, 2, 4, 5, 7, 8, 10, 11, 12, 13, 14, 21, 24, 27, 30}; {21, 24, 27, 30}, {}, (中略), {})

→ ({1, 3, 4, 6, 7, 9, 10, 11, 12, 13, 20, 22, 23, 25, 26, 28, 29, 30}; {}, (中略), {})

となる。3-1=2だったので,8つの元が最初の(working setともいうべき)集合に追加されたが,この差が1だと打ち消しあってしまうので「追加しない」ことを表せる。

問題は使用したruleを後ろに戻していないことで,原論文では「ruleをcyclicにする部分は自分で十分な回数あらかじめ複製しておいてね」という議論をすることになる。この日記では,ruleがwrapping backしない「嘘cyclic tag system」のことをfinite tag systemとよぶことにする。一応,finite tag systemを正確に定義をしておくと,

  • (S; R0, …, Rr-1)の書き換え(S, Riは0, 1からなる文字列
    • (0S; R0, …, Rr-1) → (S; R1, …, Rr-1)
    • (1S; R0, …, Rr-1) → (SR0; R1, …, Rr-1)
    • (S; ) のとき完了
  • 完了までにSが空文字列εになったら停止
    • 後の都合のため,停止した場合は(ε; R0, …, Rr-1) → (ε; )の後に完了することにしておく

まあともかく,与えられたfinite tag systemについて,十分大きいパラメータ (w, f) のsystem 5で模倣できることが示されている。*4

ただし,finite tag system停止は,空集合エンコード*5となっていることで表されるため,停止判定はデコードされていない。つまり,特定のセル1つに書かれたalphabetを確かめればよいようになっていないどころか,模倣に必要なパラメータに応じた個数のセルのalphabetsを(何か別の機械で)デコードすることで停止かどうか分かる。

From arbitrary to infinite (p. 21)

とはいえ,Alex Smithも任意有限と無限の違いが問題となることはちゃんと認識していて「ある意味で無限にできる」ことを主張してくる。実は,system 0でfinite tag system模倣するとき以下のようになっているのでcyclic tag system模倣のstep数を0, 1, 2, …と増やしたものを左から並べればよい。

  • テープのうち有限長のみを初期化し,そのうち最も左のセル(alphabet 0が書かれている)からstate Aで始める。
  • System 0による模倣の間はヘッドは初期化範囲を出ない。
  • 模倣は(停止するかにかかわらず)完了し,そのとき初期化範囲のすぐ右セルに(初めて)到達しstate Aになる。

……ちょっと待て,そんな複雑な初期化(しかも無限長)をして良いの?

初期化がnon-universalか

勝手な初期化を許せば

A
0
1 停止

さえもuniversalと言えてしまう。実際,nセル目の初期化を「模倣されるTuring machineがn stepsで停止するときに1,そうでなければ0」とすれば良い。

Alex Smithもこういうまずさは考慮しようとしていて,「初期化をnon-universalに行ってから計算してuniversalになるから,systemがuniversal」という主張になっているようだ。

しかし,この「n stepsで停止するか」で初期化する例でも,nを固定するごとには,「Turing machineのn step後に停止しているか」は決定可能なためuniversalではない。原論文の議論もcyclic tag system模倣の制限step数ごとの議論なので,これを許してしまうようにみえる。

もちろん,system 0に与える初期テープへのcyclic tag systemからの変換は(すべてのnについて並べて無限文字列を作っているとはいえ),すべてのnについて並べてもあまりuniversalっぽくはないが,有限文字列から無限文字列へのこの変換がどういう定義でuniversalと考えられるかの定義を与えるべきだったように思う。

最初に書いたメーリングリストFOMでの議論を見てみると,universal Turing machineの定義で,たとえば,Turing machineを変換してテープの入力を作るときにtotal recursive functionを用いなければならないとするようだ。*6

It depends on what you mean by "universal". My definition of a "Universal TM" is

there exists a total recursive function which takes a triple (finite alphabet, set of quintuples of a 1-tape TM using that alphabet, initial tape configuration) to an initial tape configuration, such that the "Universal TM" halts if and only if the TM you build from the given quintuples and given tape configuration halts (and both tape configurations have the "blank" character in all but finitely many places).

https://www.cs.nyu.edu/pipermail/fom/2007-October/012125.html

まあ,今回はテープに無限長の文字列を書き込んだものを入力としているのでこの定義は使えないわけだが,例えば,1次元セルオートマトンRule 110の普遍性の(Matthew Cookによる)証明に対する批判は少ないように思う。

  • 1次元セルオートマトンがそもそも両側に無限な文字列の変換規則なので,「無限に並列」な計算能力を持って普通の計算を殴っていると考えることもできる。
  • 左右に十分遠いところでそれぞれ周期的な無限文字列初期化している。セルオートマトンの規則では,周期的な部分の変換結果は周期的なので,遠いところで周期的なテープに制限すれば,セルオートマトンを(入出力,1 stepでの計算が)有限なsystemと思うこともできる。

Turing machineの場合も,遠いところで周期的な入力テープを与える代わりに,Turing machineのstate数を増やして有限の入力で模倣できるはず。*7ただし,書き換えた後のTuring machineがuniversalなことをもってもとのTuring machineがuniversalとよぶのは良くないかもしれない。(調べるとweakly universalみたいな概念が出てくるし,別の名前でよぶのが良い?)

肯定的なまとめ

  • Wolfram's (2, 3)-Turing machineの動きについて良く調べられていた。
  • エンコードしてparitiesを読み出すことにするのは面白い。

否定的なまとめ*8

  • Wolfram's (2, 3)-Turing machineに無限長の入力をしている。
    • 問題点1. 周期的な入力になっているわけでもなく,入力を作る部分で仮定された計算能力の定義もない。
  • 無限に動き続けるが,ヘッドの位置を見ると現在何回目の模倣をしているかは分かり,それぞれの模倣は有限時間で終わって出力を残す。
    • n回目はcyclic tag systemの実行をn stepsに制限したものを模倣。どれかの回の結果が「停止」なら「停止」が答え。
    • 問題点2. それぞれの出力が「停止」を表しているかを読むのに計算が必要。出力は回を重ねるごとに長くなるが,この計算能力の評価もされていない。

問題点1.のせいで弱い意味でさえuniversalでないかもしれない。どんな意味でuniversalかの定義には問題点2.も解決すべき。

*1:ここでは極めて雑に「模倣 (simulate)」と書いてしまうが,「SがTを模倣する」意味は「Tの停止問題がSの停止問題に帰着できる」こととしておく。何を用いて帰着できるという定義にするかは日記の最後の方で。

*2:この考察を用いて原論文の証明を飛ばした。

*3:gはF2同型。ちなみに,Fourier変換やMöbius inversionっぽくg-1 = gになるが,これはなんて言うんだっけ。

*4:具体的なw, fの大きさも計算されているようだ。

*5:より正確には,十分大きく2wより十分小さい整数nをあらかじめ求めることができて,「最初n回のスキャンでのparitiesがすべて0 (mod 2)になるセット」

*6:あと,tupleの定義は標準的なもののどれかを用い,tupleの定義部分に計算を埋め込むことを防ぐべきっぽい。

*7:2-tape Turing machineを使うのが簡単そう。

*8:文を簡単にするため,「私の理解が正しければ」を省いて断定的に書いた。

2016-12-06

1次元3状態2近傍セルオートマトン

21:16

Processingで遊んだ。

f:id:toslunar:20161206201023p:image

f:id:toslunar:20161206201024p:image

f:id:toslunar:20161206201025p:image

f:id:toslunar:20161206201026p:image

f:id:toslunar:20161206201027p:image

f:id:toslunar:20161206201028p:image

f:id:toslunar:20161206201029p:image

f:id:toslunar:20161206201030p:image

f:id:toslunar:20161206201031p:image

f:id:toslunar:20161206201032p:image

f:id:toslunar:20161206201033p:image

f:id:toslunar:20161206201034p:image

f:id:toslunar:20161206201035p:image

f:id:toslunar:20161206201036p:image

f:id:toslunar:20161206201037p:image

f:id:toslunar:20161206201038p:image

f:id:toslunar:20161206201039p:image

f:id:toslunar:20161206201040p:image

f:id:toslunar:20161206201041p:image

f:id:toslunar:20161206201042p:image

今回の設定で考えられるルールは332=19683通り。鏡映と色の入れ替えで同値なものを除くとたぶん1734通り。4状態にすれば2状態3近傍のルールを埋め込めるので,Turing完全なものがあることが(Rule 110の完全性から)分かるが,3状態でできるのだろうか。

キーを押すたびにランダムなルールに更新されるようにしたのでガチャが楽しめる。日記を書くにあたって追加20連ガチャ:

  • N:単色
  • R:3色,真下に周期的
  • N:2色,右下に一定
  • N:3色,右下に周期的
  • N:2色,右下に一定
  • N:2色,右下に周期的
  • N:3色,右下に周期的
  • N:2色,右下に周期的
  • R:2色,カオス
  • SR:3色,カオス,ある程度の単色領域もある(上に貼った中で2番目みたいなの)
  • N:2色,右下に周期的
  • N:3色,右下に周期的,同色が繋がっていて楽しい(上に貼った中で13番目みたいなの)
  • R:2色,カオス
  • N:単色
  • N:3色,左下に周期的
  • R:3色,下寄りの右下(3列で半マスずれる)に周期的
  • R:3色,左下にのびる1色と右下にのびる1色が対消滅
  • N:3色,左下に周期的
  • N:2色,左下に周期的
  • N:単色

2016-11-29

Rule 110について(前編)

15:46

1次元セルオートマトンのRule 110がTuring完全と聞いて。

Tag system

まずCocke, John, and Marvin Minsky. ”Universality of tag systems with P=2.” Journal of the ACM (JACM) 11.1 (1964): 15-20.を読んだ。

そもそも,tag systemとは,文字列書き換え規則であって,「先頭P文字を消し,そのうちの1文字目にのみ依存して末尾に何文字か加える」ようなもの。これを繰り返して特別な文字が先頭に来たら停止。

さて,2-symbol Turing機械をP=2のtag system模倣するのだが,今回は計算可能性しか考えていないため指数爆発しても良い。具体的には,ヘッドの左右を2進法で読み(ヘッドに近い方が下の桁,十分遠くでは0が並んでいるので良い),その回数の文字列の繰り返しとして符号化する。

:… 0 0 0 0 1 1 0 q 1 1 0 1 0 0 0 0 … ↦ Ax(ax)6Bx(bx)11 = AxaxaxaxaxaxaxBxbxbxbxbxbxbxbxbxbxbxbx *1

Turing機械がヘッドを左右に動かすことは文字列の繰り返し回数を2倍や1/2倍にすることに対応するので,「2文字消して4文字書く」とか「2文字消して1文字書く」とかいった方針tag systemでも頑張れる。

Turing機械がテープを読み取るのは文字列の繰り返し回数を2で割った余りに対応するが,それによる条件分岐も実はtag systemで書ける。だいたい,

  • a2n → … → (bc)n → … → (hoge)n
  • a2n+1 → … → a(bc)n → (cb)nc → … → (fuga)nc

みたいにすれば良い。

Cyclic tag system

ここからtag systemをcyclic tag systemで帰着して,さらにgliderの何かに帰着し,Rule 110がそういう適切な性質を満たすgliderを持つことを示す流れのようだ。

セルオートマトンで最終的に模倣したいのだから,まず問題になりそうなのはtag systemで何種類の文字が使われるかに制約がないこと。Turing機械についてテープ文字集合が {0, 1} の2文字である場合に帰着するのは簡単だが,tag systemについて文字集合の大きさを2に帰着するのは上手くいかないように思える。

それが理由でかどうかは知らないが,文字列の書き換え規則を固定周期で変化させるようにすると,2-symbolな"tag system"に帰着できる。おまけにP=1にできて*2,しかも文字0の変換先を常に空文字列としても十分で,これをcyclic tag systemとよぶ。

実際,k-symbolのtag systemに使われる文字それぞれをcyclic tag systemでは「1箇所だけ1で残りk-1箇所が0の長さkの文字列」で模倣する。ただし,tag systemの停止文字をcyclic tag systemの停止文字としては模倣できていないことには注意が必要そう。

*1:正確には,状態 qi ごとに別の文字 Ai, xi, ai, … を用いる。

*2:もとのtag systemはP=1では文字列中の文字の出現順序にまったく意味がないため,「文字間の(非決定的)遷移規則」とみなしたときの到達可能性を調べる程度の計算能力しかない。

2016-11-25

自由意志を考えるときのメタレベル

14:50

これらは矛盾するように見えがちだけど,そうでもないよね。

「『自分が信じている世界』の中にいる自分」は対象化されていて,自己言及パラドックスがおきるような本当の「自分」ではない。自分の中に作られた「唯物論を満たす世界」は本当の「世界」をよく真似ることができることを経験的に知っているが,それが正しいのか,どこまで同一視できるのか,よく分からないような気がする。

有限的な手続きしかできなくても,無限集合(非可算無限さえも)が扱えるように。適当な算術が「有限的な手続き」を表すと考えられているが,その考え方自体は証明すべきものではないように。

2016-08-19

ICFP Programming Contest 2016 参戦記

08:17

今年も*1チームUnagiで参加しました。チームメイトの日記:

開始前

Unagiは例年iwi家に集まって戦っているのだが,残念ながら私は海外出張が重なってしまい,iwi家にいられるのは最初の1日ちょっとになってしまった。

公式ツイートのうちhttps://twitter.com/ICFPContest2016/status/757792006345150464の出題者が中野圭介先生だと予想。根拠

In this talk, I introduce an interesting property of B-terms, that is, whether repetitive right applications of a B-term circulates or not.

http://www.njpls.org/may16.html#keisuke

Unagiを倒しにくるという噂もあったけど,ICFPらしく関数型言語で倒しにきた?

1日目 (Lightning)

朝〜昼

‥‥と思いきや,関数型言語ということもなく,折り紙だった。ICFP 2016奈良開催のため日本人ジャッジによる出題で,なるほど日本らしい。

最初は,時間が無限にあれば解ける方法を話し合っていた。「合計面積1をナップサックすれば,何重に折られているかが分かる」みたいなことを言った気がする。実は「合計長1をたどると元の折り紙の1辺が分かる」ということの方がずっと大事だった。

折り紙についての論文を調べる。検索の結果,Erik Demaineが折り紙理論の権威っぽかったので,講義資料を読んだりするものの,今回の問題に直接つかえる内容はあまりなかった。(例えば,与えられた「骨格」に上手く肉付けして折り紙にする話題があったが,厳密に折りたい図形を作ることには応用できそうにない。)

chokudai, wataがソルバーを組みはじめる一方,手動でジャッジ出題の問題(「古事記」に載っている折り方という設定だった)を解いていた。問題番号30から33はI, C, F, Pの文字に折られていて,I(上下のserifつき)とかFとかは手動でも難しかった。後で振り返ると,このときに直角二等辺三角形のタイル張りに沿って折ることが分かっていても十分難しいという知見を得た。

昼〜夜

Lightning終了時から提出が始まる「折り紙の問題を(コンテスト参加チームが)出題する」パートに取り組むことにした。

折った結果の図形だけでなく,元の折り紙の4辺や折り線が問題のヒントとして与えられてしまうので,線を重ねると難しくなるのではと最初は考えていた。たとえば,同じ頂点を通る直線で何十回も折る作戦を思いついたが,

  • 座標が有理数という制約により角の2等分線が必ずしも折れないこと
  • 座標の分母の大きさを見ると何回目に折ったかのヒントになってしまいそうなこと
  • 結局凸多角形になってしまいそうなこと

などの対策を思いつかずに断念。

「1辺1の正方形をタイリングできるパーツがあるとそれだけで全部埋めようとして探索失敗する」という感じの内容をwataが言っていたので,普通に手動が難しかった問題がプログラミングで解くのも難しいらしいと予想し,45度単位でしか折らない作戦に切り替え。その制約の中でなるべく気持ち悪い折り方をする方法を考えることにする。

折り紙の「展開図」から平面的な折り紙が可能か(以下,「有効な展開図」と呼ぶ)は各頂点のまわりを調べるだけで判定できるので*2,現実的な折り手順があるかは完全に無視できる。また,どのように折った状態からも(少なくとも)全部まとめて折ることができるのと同様に,有効な展開図であることを保ったまま折り線を書き加えることは難しくない。

実際の出題データ生成は次のようなプログラムを書いた。

  1. N×Nのグリッドを準備。次をM回繰り返す
  2. 折り線がまだない格子点をランダムに選択した後,その点から折り線を適切に4本のばす。新しく書く折り線はすでに書かれた折り線にあたるたびに屈折させれば*3有効な展開図を維持できる。
  3. グリッド作業していたので,多角形のデータに直して出力。

f:id:toslunar:20160819074801p:image:w300:right

「点から折り線を4本のばす」ときに,90度+45度+90度+135度にわけるパターンが選ばれると「気持ち悪い折り方」になるというつもり。2日目以降に自分がいなくなっても最低限の編集(パラメータ調整とかデバッグとか)ができるようにC++で書いた。

夜〜朝

ジャッジに提出するデータは,

  • 折る前の頂点たちの座標
  • 多角形たち(何番目の頂点を用いるかで表す)
  • 折った後の頂点たちの座標

からなる。実は,上で生成した出題データはこのうち最初2パートしか作っていない。折った結果は展開図から(合同変換を除き)一意に定まるので,データの最初2パートから最後のパートを自動生成できる。iwiがソルバーに共通となる前処理・後処理を作っていたのだが,折った後の座標の自動生成はソルバーには必要なかったらしく自分が実装することになった。(冷静に考えれば,ソルバーは折った後の図形から解くわけで当然だった。)

「折り線は45度単位だけど,念のため任意の有理直線に対応しておこう」と思ったものの,C++の多倍長ライブラリを使った経験がほとんどなかったため,(こっそり*4Haskellで書いた。折るだけなのでoru.hsと命名。

oru.hsの完成により「出題」準備がととのう。imos, sulumeによるビジュアライザに投げると狙い通り気持ち悪い折り紙ができていたので一安心。

2日目

朝〜昼

出題データ生成プログラムに直書きしていたパラメータ引数で与えるようにしたり,ランダムで一度書いた折り線をちょっと消すこともする改造をしたりした。(gen3.cc)

出題データは多めに作って,チームメイトたちによる目視で難しそうなものが選ばれた。パラメータはひとまず N=24, M=7 としたが,他チームに解かれる気配はなく,最後までその設定で乱数seedだけ変えたものを提出していた。

ちょっと余った時間で実物の折り紙を折って解いていた問題の展開図を入力し,oru.hsを通して提出可能なデータにした。

その後

飛行機。

3日目

「国際会議の発表がひかえているからあまり参加できないかもしれない」と言っていたものの,

  • 経由地の空港で,古事記の22, 24番を手動で解く。(24番を解いていた唯一のチームが24番を回転させただけの問題を出題していた。)
  • 着いたホテルで,ソルバー用手動ヒントを作成。

後日

出題データに生成途中のものも追加してビジュアライズした*5出題データ | Unagi | ICFPC2016。動画版(imos):

D


他チームの参戦記より(追記)

fixstars(tomerunさん)

Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。

ICFP Programming Contest 2016 - TopCoderの学習のお時間 - TopCoder部
天羽々斬(osa_kさん)

Unagiが提出している問題を見ると、そもそも折っていくにしろ開いていくにしろダントツで難しい。そこで、Unagiは古事記くらいは解けるにしても、彼らが自分自身で出している問題は解けないんじゃないかという仮説を立て、同じような問題を作ることにする。が、そもそもUnagiの問題が手動でも解けない。

ICFPC2016 Team 天羽々斬 - osa_k’s diary

*1:去年の自分の日記:ICFP Contest 2015 参戦記 - tosの日記

*2:角度の交代和を見るだけ。現実の折り紙では,山折りと谷折りを適切に選んで紙が重ならないようにする必要があるが,このコンテストの設定ではそれは要求されない。

*3:屈折率は -1 で,すなわち,折って重なっている紙を同じ直線にそってまとめて折る操作に対応する。

*4:お風呂休憩時に「今回は自分がいなくなっても大丈夫なようにC++で書いてる」と言ったばかりだった……。

*5:滑らかに折っている雰囲気だけど,実はちょっとだけズルしてる。

2016-05-21

音ソシャゲーの比較

17:48

配信開始日順に並べましたが,現状で比較します。主観を多分に含みます。加点要素減点要素は色で示しました。

ラブライブ!スクールアイドルフェスティバル(スクフェス

  • 配信開始:2013/4/15
  • ボタン配置:半円形9ボタン(maimaiを下半分に詰め込んだ感じ)。多くの指を使うメリットがカーブのせいで小さく,持ちプレーと置きプレーの難易度差が減っている。
  • 判定幅:やや甘い(最良判定Perfectは体感40msくらい)。上位2判定でコンボがつながる。
  • 判定ズレ:ズレていると認識できる曲は1割くらい。(早ズレ曲と遅ズレ曲両方ある。15msくらいはズレてそう。)
    • 自動ズレ調節機能が用意されているが,それで調節すると早ズレ設定になる印象。
  • ノーツの種類:通常,ロング
    • ロングの終点は始点と同じ判定の厳しさ。*1
  • 譜面:親指2本でのプレーに配慮された譜面。(「思い切り」指を伸ばす必要のある譜面が1つだけあるが*2,そういう歌詞ネタ。)
    • 担当パート:伴奏にあわせていることが多い印象。
    • 難易度:難しい譜面が不足。しかも最高難度は常設されていない。全曲フルコン目標がちょうど良いくらい。(現在は1曲4難易度だが,この上に新難易度が設置される予定。)
    • 譜面表示:とても素直。同時押し表示があるものの,同心円の配置は認識しにくく,自然な難易度増加に貢献している。最近ハイスピード設定ができるようになった。
  • 得点計算:(音ゲー点)×(キャラステータス)+(キャラ特技)と考えて良い。
  • 曲傾向:擬J-POP,擬懐メロ(「まきちゃんがテレビを観て『アイドルソング』を勉強している」設定だと思うことにした)。作詞が畑亜貴でややワンパターン(「うみちゃんが恋愛の歌詞が恥ずかしくて適当に書いたり,そもそも恋愛じゃない歌詞を書くことにしたりしている」設定だと思うことにした)。
  • ガチャ:URは1%しかない。高レアリティ確率上昇のイベントなしカード重複で進化できる仕組み。
  • その他:みんなかわいい

CROSS×BEATS(クロビ)

  • 配信開始:2013/12/2
  • ボタン配置:画面全体にノーツが来る(実は主に格子点に来る)。
  • 判定幅:最良判定Flawlessはやや辛い(体感20msくらい)。コンボ継続のための判定は激甘。
  • 判定ズレ:(気付ける範囲では)なし。判定音の遅れは気になるので,判定音の方でタイミングあわせをしてしまう人には厳しい。
    • ズレ調節機能はms単位で親切。
  • ノーツの種類:通常,ロング,フリック
    • ロング終点で離す必要なし。フリックは押し直す必要なし。
  • 譜面音ゲーらしいと思う。タブレットを置いてのプレー前提で3つ以上の同時押しあり。
    • 担当パート:高難易度は混フレ楽しい。
    • 難易度:高難易度まで揃っている。ただし,譜面ごとの解禁作業が必要。
    • 譜面表示:慣れが必要*3手で隠れたり連打もある中で見やすく設計しようとした努力はうかがえる。ハイスピード設定可能。ただし,速度BPM依存。当然,BPM変化のある曲では見難くなるし,ランダム選曲も困る。
  • 得点計算:スコア自体は上位3判定の個数のみコンボボーナスなし)*4。これについてはFlawlessの個数が重要。
    • ただし,S+等で表される達成度については上位2判定の合計数とコンボが重要。フルコンのみで良ければ4番目までの判定で許される。「判定幅」の好み(というかプレーヤースキル)によっていろんな目標を設定できる。
  • 曲傾向:Cool
  • ガチャ:曲の入手が実質的にガチャ*5
  • その他:プレビューがちゃんとループしている

アイドルマスター シンデレラガールズ スターライトステージ(デレステ

  • 配信開始:2015/9/4
  • ボタン配置:画面下1列5ボタン
  • 判定幅:激甘(最良判定が60msくらいはありそう)。適当プレーでもPerfectの個数はMiss以外の判定個数と2桁違う。ただし,コンボに必要な判定は狭い*6。苦労した初フルコンが同時に初エクセのこともある。
  • 判定ズレ:ズレてる気がする譜面もあるが,判定幅広すぎでよく分からない。
    • ズレ調節は勘でやるしかない。
  • ノーツの種類:通常,ロング,フリック(左右)
    • フリックはロング終点のものと独立のものがある。独立したフリックは押し直す必要なし。(ロング終点のものは押し直すとミスになる。)
    • フリックに関して裏技が多数存在する*7。ここで裏技とは「あんみつ」のように譜面の指示通りに叩かないことを指すが,たとえば,
      • フリックは早めにとった方がコンボが繋がりやすい
      • 連続フリックは譜面上でもつながって表示されるが無視してよく,左右の手で分けるとやりやすい。
      • 「単押しの後の同じ位置から始まるフリック」はロングとその終端フリックのように扱ったほうが簡単。*8
  • 譜面:親指2本でのプレーに配慮しているようで,そうではない。同時押しは2つまでに制限されているが,暗記しなければ親指プレーのフルコンは不可能な譜面がある。
    • 担当パート:ボーカルの存在するところはボーカル。しかも歌詞の文字数を正確に守る*9
    • 難易度:限定イベントでそれなりに難しい譜面(MASTER+)が配信される。常設の高難易度譜面はクリアは簡単。フルコンはフリックが運ゲーになる。
    • 譜面表示:同時押しの表示がいわゆる「横認識」の助けになっている。それ以外は意図的に譜面認識を難しくしている要素あり。一部のノーツが斜めに降ってくる*10譜面が3Dなのでノーツは加速している。
  • 得点計算:複雑
  • 曲傾向:キャラソン。ネタ多め。
  • ガチャ:キャラ多すぎで推し*11がいる人には厳しい。逆に各キャラについてSSRは1種しかないので,手に入れれば終わりにできるかもしれない(たった今,期間限定で身代金3000円にサービスされている)。1枚引けばアイテム進化可能。
  • その他:MVに力が入っている(キャラの3Dモデルが踊る)。一度曲をクリアしておくと,MV鑑賞のみも可能。
  • その他:判定音が4種類から選べるが,どれを選んでも,(スクフェスの自然なタンバリン音と比べて,)高音を盛っている感じでうるさい。*12

これらの共通点

  • 判定音あり。判定音は曲の音ではない。(設定で消音可能。)
    • ロング終端も判定音あり。
  • スタミナ制。フレンド要素あり。ギルド要素なし(?)

スクフェスデレステのカードについて

  • 判定をPerfectにする特技も存在
  • イベントSRくらいで得点評価Sをとることは可能。スコアランキングは最高レアを必要個数揃えるのがスタートラインと思われる。

まとめ

現状,「これがイチオシの音ソシャゲー」とは言えない一長一短で,

その中でも,

*1:「ロングノーツは音をのばすことを表す」解釈では理不尽だが,スクールアイドルがしゃがんだり立ったりすることを表す解釈だとまあ良いかなという感じ。

*2Music S.T.A.R.T!! [HARD]

*3:「クロビの譜面形式慣れても,ある程度曲ごとに譜面を覚える必要がある」という声は聞く

*4IIDXのEXスコアに似ている。

*5:レアドロップという方が正確かもしれない

*6:キャラスキルなしでは上位2判定でコンボ継続だが,(jubeatの全Great以上と同様に)80msから90msくらいしか許されない印象。

*7:フリックの仕様変更が一度あったが,仕様変更以前の状況は知らない。

*8デレステはロング終端フリックが仕様にあるので譜面作者の意図に反する。クロビにはロング終端フリックの概念がないが,その代わりに「ロングの終端時刻に,フリックがロング判定位置限界あたりに配置されている」ことがあり,これはそんなに悪くない。

*9:拗音や英語をフリックにしている疑いすらある

*10:垂直方向の速度が一定な分,reflec beatよりもましか……。

*11im@sの世界では「推し」ではなく「担当」プロデューサーと言う。

*12アーケードのコイン投入音みたいな「あざとさ」がある。

2015-12-24

詐欺師になるしくみ

23:58

数学科の院生の進路として詐欺師という選択肢があるという噂を聞いたことがある。確かに,頭の良さを活かせる職業ではあるし,「社会の役に立つ」ことにこだわらない面でも数学科(のステレオタイプなイメージ)っぽい。まあ,そんな風に噂を聞いたときには感じたものだが,別の理由を思いついてしまった:「純粋な(社会)貢献をすることを諦めるなら,純粋な詐欺をしたくなるのではないか。」

ところで,仕組債というものがあることを最近知った。例えば,「年利3パーセント,2年契約,円・豪ドル・NZドルのいずれかでお受け取り」みたいなやつ。当然ながら,受け取る通貨を選ぶ権利はない。線形論理のresource interpretationで「100円⊕1ドル」の方。

経緯はというと,海外出張する予定があり,その前に外貨口座を開設してSony Bank WALLETを使おうとかいう感じ。私の場合は手数料が安いことが目的だけど,「外貨預金といえば資産運用」みたいなノリを感じたし,普通の銀行でも色んな取引ができるらしい。近況報告はおしまい。

話を戻すと,いかなる手口で素人にオプション取引させていたかを知った。金融のことは素人だが簡単に解説すると,大きな価格変動のリスクを負担することを見返りに支払われるオプション料を「金利」にすれば,「リスクはあるけど高金利」みたいに宣伝できるらしい。定期預金との違いが分からない人が大損したりして社会問題になるのも納得だった。確率論はそれなりに勉強して,確率過程の簡単な計算ができるようになっている目でオプション取引を眺めると,「こんなの素人に見積もれるわけがあるか」って思う。確率が直感にあわないことは結構あるし,確率論を完全に理解していても経済の知識がないから更なる落とし穴もきっとある。

すでに述べたようにプレミアは難しい。難しいものと関わりあいたがる人は少ないが,難しさを隠してしまえば売りやすい。別の例を挙げよう。

ある種のPCゲームは発売から1週間もたたないうちに中古品が半値で出回っていたりする。そうなってしまうと新品の売り上げが落ちるということで,メーカーはいかに予約購入してもらうかということに力をかけているらしい。ここで売りにくいのは新品プレミアであって,これに予約購入するリスクと予約特典を加えると,一層複雑になるにもかかわらず最難所の「新品か」の部分からは意識がそれるので簡単に見える。

難しさを解決するために,いろいろ加えて難しさを薄めるというのが常套手段なのだろう。まったく気に入らないことだが。別に,「困難に立ち向かえ」という言葉で指し示される内容のことを言いたいのではなく,ただ,「難しいものは嫌い」と言っている人たちが,実は,より難しいものを好き,ということが残念だ。「本当に難しいものはどこにもない」と言いたいのでもない。何かを足して解決することがあるとすれば,難しさを閉じ込めて管理することだという思いがあるだけだ。

2015-12-08

きのう,生活圏,コヒーレンス

19:59

気付くと,暗い建物の廊下のようなところにいる。

「気付いたから,」と説明した方が正確か。

いずれにせよ,視界は一面の黒に染まり,両足が地面についている感覚だけがある。


この消え入りそうな世界の中でも,体はいたって普通に動くはずだ。

だらんと下がっていた右腕を,ほら,前方に。

ただし,視界に変化はなく,腕が風をきった感覚もない。


そのまま右腕で,何も見えていない両目を覆い,擦るようにしてから腕を下ろす。

残念ながら,まるで目を閉じているままのように変化はない。

おまじないとはいえ,これで結構見えるようになったりすることもあるんだけど。


歩き出すことはできるが,上げた足が再びつく保証はない。

経験則として,世界が不確かなときは,まず私が確かになるべきだ。

私は世界。世界は私。


左の手首を右手で掴んでみる。

掴む感触,掴まれる感触。

足の裏に加えて新しく2箇所,存在感が得られた。


ブラックアウトの危険は減ったと考えてよい。

この存在感を頼りに,一歩ずつ進んでいく。

言葉通りの意味で世界に奥行きが出る。


……。

……。

……。


かすかに明るくなる。

外から光がさしてきたようだ。

いや,私は外に出ていた。


そのとき,ふわっとして,右足は宙を蹴り,左足もつかなくなった。

見えるのは人のいない住宅街。背中が暖かい。

右手で左手を掴んでいる感覚はそのまま。


最初から重力がおかしかったような気がする。

世界に身をゆだねる。夜明けのようだと思っていたのに,嘘みたいに明るくなった。

風景がゆっくりと流れ,遠ざかる。

2015-08-11

ICFP Contest 2015 参戦記

05:28

今年は海外出張中だったのですが,去年,一昨年と同じメンバー iwiwi, imos, sulume, wata, chokudai と参加していました(チーム Unagi)。

開始前

1日目 (Lightning)

  • 正六角形タイルでテトリスをしろという問題のようだ。量子はどこへ?
  • 移動のさせかたが特定の列(以下,「呪文」と呼ぶ)になっていると,得点が入る。呪文リストは隠されていて,呪文の得点は Lightning では関係ないが,Lightning 中からスコアボードには影響していて,でも,Final Round ではプログラムに呪文リストを貰える。でも,スコアボードである程度勝っていないと,Final Round に進めない。呪文にどのタイミングで取り組むかは謎だった。
    • 呪文に取り組むかは謎だったのだが,いろいろな事情で,早めに呪文当てをすることになる。
  • 開始直後,コンテストサーバー側での採点にバグがあり,早くも優勝ペース(参考: http://twitter.com/imos/status/629653593532928000)。
    • このバグに気づいていたチームは Unagi と Rabbit House だけだった気がする。
  • 例年の通り,wata, chokudai がマラソンマッチ的なことを担当し,imos, sulume がチーム内スコアボードとか複数のソルバーの統合とかの環境を担当。
  • ゲームの仕様で与えられる座標系がやばいので,まともな座標系に直す。ただし,ゲーム中で列を消したときの落下処理はやばい座標系に従うので,整合性をとる必要がある。仕様の (x,y) を (2*x+y%2,y) にうつすと直交座標になり(正規直交座標ではない),上記の問題とも相性が良さそうなので,それを使うことにした。
    • この判断が正しかったかは自信ないが,チームメンバーはあまり混乱してなかったようなので良しかな。変なルールがなければ,60度の斜交座標を用いるのが普通だと思う。
    • しかし,上のコードでは y が負のときにバグHaskell で rem, quot; div, mod が分けられてることへの感謝の気持ちを忘れてしまっていた。
  • 早くも自分の仕事がなくなりつつあるが,Lightning 後のために,呪文の詰め込みかたなどを考えることにする。
    • ルールでは同じテトを過去と同じ位置にするような移動が禁止。降ってくる個数が決まっているため,下(というか,Hex なので左下60度と右下60度)にあまり移動しないことが大事なので,左右で戻りたいときは回転してから戻すとか。
  • やはり仕事がなくなりつつあるので,imos, sulume がまだ手をつけていない visualizer を作りはじめる。
  • 勉強もかねて,GLUT か GLFW の Haskell 用バインドを使おうとしたが,無駄にコピペコードになりそうなのと,他の人が使うときに cabal でハマったりする可能性が怖かったのであきらめて,JavaScriptCanvas でやる。
    • JavaScript はそれなりに書いていた時期があったが, .length() でエラーが出て「これだから配列かどうかすら分からない言語は」と腹を立てたり(.length が正しいので筋違い),それを直したら,今度は Math.cos(i*Math.pi/3) などと書いていたところでエラーが出て,「Math.PI が正しいとか馬鹿じゃないの? なんで関数副作用がないかには気にしないくせに,double型が定数かどうかにはこだわるんだよ」と腹を立てたりした(これは C言語で PI だったレガシーを背負ってしまったとしか理解できていない)。
  • 遠隔参加なので,起きていても全部の会話が拾えていることもないし(ネット回線やマイクの位置の問題),オンサイトだった去年までと比べるとチームの状況があまり把握できない。
    • スコアボードが修正されてから,Unagi はなかなか解答を送信しないな。潜伏戦略なのかな」と思って聞いたら,「1位です」と返ってきて,自分がスコアボードの更新をしてなかっただけだと気づいたり。
  • 今年も wata, chokudai の力が発揮され,割と良い感じの成績っぽい。1位のチームは Lightning で得点にならない呪文で稼いでいるっぽいし,Lightning 部門勝利もあるな,という感じで初日は終了。

2日目

  • 日本にいるチームメンバーとの睡眠のタイミングを合わせられなくなってくる。
  • iwiwi 呪文の解析を頑張っていたので実際の呪文がいくつか特定されている。
  • 呪文まわりの戦略について chokudai と話す。"ia! ia!" は重複させられるので強そうに見えるが,"r'lyeh" の方が下への操作をあまり入れないので強い。ただし(60度対称で)回転できないテトだと結局 "ia! ia!" するしかない。
  • imos, sulume が書いている C++ シミュレーターを少し改造するが,どうビルドすれば良いのか分からない。GitHub の更新を検知して自動ビルドの結果が Slack に流れてくる仕組みがあったので,一発書きを commit, push した。
    • あまり良くないんだけど,担当の2人は寝ているし,破壊的に変更していないはずだし,push したらビルド通ったっぽいしまあいっか,みたいな。
  • JavaScript で書いたビジュアライザを,ゲームプレイに対応させていなかったところ,C++ シミュレーターの側にゲームプレイのアスキーアート出力がついた。自分がこれ以上 JavaScript で何かしようという気がなくなる。
  • テキスト表示を見ていると正六角形で美しく出力する意味があまりないことに気付く。テトが連結とかいう制約もないしグラフィカルにやるにしても円で十分では? wata, chokudai が自前のテキスト出力で大丈夫そうにしていたのも納得。
  • 呪文候補のローマ字列を入れると,対応する操作を矢印(←→↙↘↻↺)の列で出力するだけの簡単なプログラムを書く。矢印の列を Slack に貼ったら斜め矢印だけ絵文字に化けた(斜め下移動がある意味目立つべきといえばそうなので,偶然だが分かりやすかったとも言える)。
    • 例:↙↘↘↙↙↺↘↙↘↺↺→↘↙↺↘↻←↘→→↙↘↻→↙↻↘→↺↙↺↘↙↺↘↺↙↙↺↺↘↻↻→↙↘↙↘↙←
  • スコアボードで呪文を18個中9個も使えているチームがいることに驚く。
  • iwiwi が取り組んでいた呪文当てがツール化されて,誰でも使えるようになった。呪文を含む死なないようなプレイを適切な問題番号で探し,それを submit する仕組み。
  • ICFP 2015 accepted papers のタイトルに含まれる単語を iwiwi ツールにどんどん貼り付け。しかし,当たらない。
  • 呪文当てをする唯一の手段が公式スコアボードだったし,分かっている呪文の範囲での点数は自己採点できるため,必然的に「潜伏」戦略になる。
    • AIと自前のシミュレーターの採点が同時にバグっているという可能性を排除するために,「潜伏解除」もした。
  • どうせ "2015" とか "icfp" とか入っているんじゃないの? と思うものの,どちらも左右に行って戻る連続した移動があり,そこでテトを切り替えないと反則なので,死なない手順を自動で見つけるのは難しい。手作業で手順を作ったが,呪文ではなかった。残念。
  • 日本にいるチームメンバーとの睡眠のタイミングを全然合わせられなくなってくる。

3日目

  • 寝ている間に,結構,呪文が判明している。Twitter でヒント祭りがあったらしい。
  • 寝ている間に「全完」目標になっていた。
  • 内部スコアボードでは圧勝しているが,全問題で1位にする気らしい。
  • AI の動作をながめて「複数列消しを狙う方が良いのでは?」と言ってみたが,見当外れらしい。
    • そのときはあまり構ってもらえなかったが,冷静に考えて Lightning でないと本当にそう。盤の横幅が広くなっても,列を消す得点は変化しないし,複数列消しを待つために積むと呪文があまり入らなくなる。
  • web と twitter しか見ていなかったものの,IRC にもヒントが結構流れているらしいという話。IRC は入っていないとログが見れない。ログが置かれている場所があるらしいがつながらない。
    • それもそのはず,去年の ICFP Contest で使ったときのままの channel topic に「ログが置かれている場所」情報が放置されていたため,つながったとしても1年前のログだったのだ。
  • 公式 twitter 初期の謎の文字列プロットしてみると,やたらなめらか。楽譜っぽい,というところから解けた。というか,テトリスであることを知っていたので,解けた。解答を確信したのち,文字の選び方を合理化するためには rot13 するんだな,と分かった。順番が逆。
    • 解けてしまったことで,これはテトリスである情報しかないことが判明。呪文探しには役に立たない。(それでも,rot13 とか Ceaser とかを iwiwi ツールに投げていた。)
  • 「Problem 24 の街があやしい,本当に Vancouver(注:ICFP 2015 開催地)か? クトゥルフ的な街でないのか?」という疑問があったため,Vancouver の名所を画像検索。一番あやしげな塔に似た建物は発見。おそらく海側からの写真をもとに Problem 24 を描いているのだが,ちょうどその向きの写真は見つけられなかった。
  • 「全完」を諦め,浮上。Twitter でも報告,を自分だけしそこねた。スコアボードで圧勝しているので,IRC でも話題になるかと期待したが,そのころの IRC は過疎っていた。
  • そういうことで,呪文探しは18個中16個見つけた時点で終了。自分の戦果は,"cthulhu fhtagn!"(チームメンバーは感嘆符を入れては試していなかった)と,最大51文字とアナウンスされていたやつのもう1つの方。どちらも51文字なのはちょっと驚き。
  • あと2時間くらいで終了というところで眠くなって脱落。日本の音声をイヤホンに入れたまま寝るみたいなことをしていたので,なんか終了直前に起きた。

終了後

  • チームメンバーの打ち上げ映像。いいなあ。
  • 未発見の呪文の片方は謎解き力が足りなかったが,もう片方は完全に無理だった。意味不明な 10^63 は調べるべきだった(2^63の誤植だと思ったのが運のつき感もある)。