仕組み (マジックチューリングマシン v5: 腐れ肺の再生術師 / 尖塔の大長)

(この記事は以下のページの翻訳です: http://www.toothycat.net/~hologram/Turing/HowItWorks.html)

あなたはきっとチューリングマシンとは何かは知っているだろう。マジックでそれを実現するためにはいくつかの部品が必要となる: いくつかの異なる「色」をしたセルを保持する、双方向に伸びるテープ; 現在位置のセルの色の読み書きができ、また必要とあらばそれ自身の状態を遷移させる事の出来るヘッド; そして「実質的に」双方向に無限に伸びるテープである。

戦場や他のゾーンにおいて必要となるカードの全リストはカードページにある; このページではそのリストを繰り返す事はせず、それぞれのカードが何故必要であるかを説明する。

チューリングテープ

テープは以下のようにして実現される。
Alexにコントロールされた一連のZombieトークンはヘッドの現在位置から右側にあるテープを表す: 例えばヘッドの一つ右にいるクリーチャーはあと1ダメージで死亡するだけのタフネスを持ち、さらに一つ右にいるクリーチャーはあと2ダメージで死亡するだけのタフネスを持つ。同様にAlexは一連のYetiトークンをコントロールしており、これはヘッドの左側にあるテープを表す。

それらのトークンは他にさらに2つクリーチャータイプをもっており、それがそのテープ位置の「色」を示している。簡単のために、以下の議論ではそれらのクリーチャータイプを実際のタイプの代わりにA1のようなコードで呼ぶことにする。タイプは以下のように割り振られる: (全てのタイプは公式のマジッククリーチャータイプリストから来ている。可能な限り「左側の」クリーチャータイプは名前にLを、「右側の」クリーチャータイプはRを、また「共通の」場合にはそのどちらも含まないよう配置した。)

色番号 共通クリーチャータイプ 左側クリーチャータイプ(Yetiに加えて) 右側クリーチャータイプ(Zombieに加えて) Messengerタイプとその方向
1 Ape (A0) Ally (A1) Archer (A2)
2 Bat (B0) Blinkmoth (B1) Bringer (B2) Basilisk (B1M)
3 Cat (C0) Camel (C1) Carrier (C2)
4 Demon (D0) Devil (D1) Dragon (D2)
5 Eye (E0) Elf (E1) Efreet (E2)
6 Fish (F0) Flagbearer (F1) Faerie (F2) Frog (F2M)
7 Giant (G0) Golem (G1) Gorgon (G2)
8 Hag (H0) Hellion (H1) Harpy (H2)
9 Imp (I0) Illusion (I1) Incarnation (I2) Insect (I1M)
10 Djinn (J0) Jellyfish (J1) Juggernaut (J2)
11 Kavu (K0) Kobold (K1) Kirin (K2) Knight (K2M)
12 Leech (L0) Licid (L1) Lizard (L2) Leviathan (L1M)
13 Mutant (M0) Moonfolk (M1) Myr (M2)
14 Ninja (N0) Noggle (N1) Nightmare (N2)
15 Ox (O0) Ooze (O1) Orc (O2)
16 Pegasus (P0) Plant (P1) Praetor (P2)
17 Rat (R0) Rebel (R1) Rigger (R2) Rhino (R2M)
18 Shade (S0) Slith (S1) Siren (S2) Sliver (S1M)

つまり、例えばあるトークンがArcher (A2)であるなら、それは常に同時にApe (A0)でもありZombieでもある。Zombieである事によって、その場所がヘッドの現在位置から右側にある事が示され、Apeである事によってその場所の色が1 (またはA)である事が示される。ヘッドの左側に同じ色をした場所があったなら、Ally Ape Yetiとなる。

「右側に一つ移動する」という操作は以下のように表される: 新たなYetiトークンを一つ生成し(これはヘッドの一つ左となる)、全てのYetiトークンのタフネスを1増加させ、全てのZombieトークンのタフネスを1減少させる。詳細は以下の通り:

http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=203945http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=205420http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=25678

マシンは新たに2/2 YetiトークンをAlexのコントロール下に生成し、以下の3つの能力が誘発される: Bobの有毒グール、Cathyの上天の閃光とAlexのカズールの大将軍である。現在はBobのターンなので、それらは説明した順序でスタックに乗る; つまりその逆の順序で解決される。まず初めに、人工進化でハックされたカズールの大将軍の能力が解決され、AlexのYeti達に+1/+1カウンターが置かれ、それぞれ死亡するために必要なダメージが1増える。新たに生成されたYetiトークンは3/3となる。次に、上天の閃光が新たに生成されたトークンに2ダメージを与え、それが死亡するためのダメージは望みどおり1となる。最後に、これもまた人工進化でハックされた有毒グールが全てのYetiでないクリーチャーに-1/-1修正を加え、最もタフネスの低いZombieが死亡する。この最もタフネスの低いZombieが持っていた他のクリーチャータイプによって、異なるイベントが誘発される。以上でマシンは一つ右に移動している。

もし新たに生成されたトークンがYetiでなくZombieであった場合は、また別のカズールの大将軍、さらに別の有毒グールと、これは上記で使用したのと同じ上天の閃光の能力が誘発される。つまりZombie達に+1/+1カウンターが置かれ、Yeti達が-1/-1修正を受ける事を除けば同じ事が起きる。マシンは一つ左に移動している。

トークンのパワーとタフネスは注意深く調整する必要がある。腐れ肺の再生術師は本来2/2のトークンを作る。読み込みヘッドによって作られたトークンは2つのドラルヌの十字軍に影響され、+2/+2の修正を受けるが、死の支配の呪いと1つの仕組まれた疫病によって、-2/-2の修正を受ける。

チューリングヘッド

Yurii Rogozhinの1996年の論文によって公開された、18色のテープからなる最も単純な2状態万能チューリング機械を使用する。このマシンのルールは、ある位置からある色が読まれたとき、マシンがどの状態であるかによって、何をするべきであるかを記述する。例えばルールの最後の数行は以下の通り:

  • 状態Bで色16を読んだとき: 状態Bを保ち、その位置を色18に変更し、一つ右に移動する。
  • 状態Bで色17を読んだとき: 状態をAに変更し、その位置を色18に変更し、一つ左に移動する。
  • 状態Bで色18を読んだとき: 状態Bを保ち、その位置を色13に変更し、一つ左に移動する。
  • 状態Aで色16を読んだとき: 状態をBに変更し、その位置を色17に変更し、一つ右に移動する。
  • 状態Aで色17を読んだとき: 停止！
  • 状態Aで色18を読んだとき: 状態Aを保ち、その位置を色3に変更し、一つ右に移動する

腐れ肺の再生術師と人工進化がチューリングマシンの中核となる重要なカードである。再生術師の大量のコピーが使用され、またそれらはそれぞれ異なるクリーチャータイプの組を監視・生成できるよう変更される。

事実、ヘッドのために43つの再生術師のコピーが使用されるのである! それらのルールテキストは上で示したルールをエンコードするために次のように変更される:

  • フェイズアウトしている再生術師16B: 「Pegasus (P0) が死亡するたび、Siren (S1)を1体生成する。」
  • フェイズアウトしている再生術師17B (事実上): 「Rat (R0) が死亡するたび、時空の満ち干を唱え、Slith (S1)を1体生成する。」
  • フェイズアウトしている再生術師18B: 「Shade (S0) が死亡するたび、Moonfolk (M1)を1体生成する。」
  • フェイズインしている再生術師16A (事実上): 「Pegasus (P0) が死亡するたび、時空の満ち干を唱え、Rigger (R2)を1体生成する。」
  • フェイズインしている再生術師17A (事実上): 「Rat (R0) が死亡するたび、マシンを停止する。」
  • フェイズインしている再生術師18A: 「Shade (S0) が死亡するたび、Carrier (C2)を1体生成する。」

(2, 18) チューリングマシンにおけるプログラミングとの対応を理解していただけるだろう。新たに生成されたトークンのタイプは、その場所をどの色に変更すべきか (A-Sまで、Qを飛ばして)、また左右どちらに移動するべきか(1 or 2)を示す。時空の満ち干を唱える事は状態の変更と対応する。

http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=39640http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=39923

もちろん、腐れ肺の再生術師を実際にハックして「Pegasusが死亡するたび、時空の満ち干を唱え、Riggerを一体生成する」ようにする事は出来ない。インスタント呪文を誘発効果として唱えられるようにする事はこのチューリングマシンが乗り越えねばならない最大の障害である。

状態の変更

このインスタントを繰り返し唱えるため、このバージョンのチューリング機械は尖塔の大長を使用する。これは呪文冊子もしくは梅澤俊郎を使用する必要があった以前のバージョンと比べてかなり簡単となった。
http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=3653http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=248739
屍滑りと標本集めを使い、尖塔の大長を繰り返し戦場に出し、荒廃の鎌を装備したタジュールの射手によってそれを殺す。大長は解決したインスタントをCathyの墓地に戻してくれるので、時空の満ち干を好きなタイミングで唱えるために特別な仕掛けは必要ない。

状態を変更するために必要とされる再生術師達は、通常のカズールの大将軍 / 有毒グールの組を誘発しないよう、異なるクリーチャータイプのトークンを生成する必要がある。これらの「messenger」クリーチャータイプを頭文字Mで示す。

  • 再生術師 17B は、実際には「Rat (R0) が死亡するたび、Sliver (S1M) を一体生成する。」
  • 再生術師 16A は、実際には「Pegasus (P0) が死亡するたび、Rhino (R2M)を一体生成する。」

これらの「messenger」トークンタイプ S1M, R2M等は、YetiでもZombieでもなく、Reflectionである。したがってそれらはカズールの大将軍や有毒グールは誘発しないが、Alexの、人工進化によってReflectionを監視するようハックされたタジュールの射手を誘発する。それらはその後、それらが死亡した際にさらに再生術師達を誘発することで、実際に要求されたトークンを生成する。標本集めによって腐れ肺の再生術師達がBobにコントロールされることで、それらの誘発能力をスタックの正しい場所に乗せる事ができる。

http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=401745http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=174122http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=398181

まとめると、状態を変更するために以下が行われる:

腐れ肺の再生術師がAlexにmessengerトークンを生成する。これをSliver (S1M)タイプであるとしよう。これはまた人工進化によってハックされたドラルヌの十字軍によってReflectionでもある。Cathyの上天の閃光と、Alexのタジュールの射手が誘発する。Alexの尖塔の大長が唯一の飛行を持つクリーチャーなので、対象は自動的に選ばれる。
Stack: ...[Cathyの上天の閃光→S1M] ; [Alexのタジュールの射手→尖塔の大長]

タジュールの射手の能力が解決され、またそれは荒廃の鎌を装備しているために萎縮を持つため、尖塔の大長にそれが死亡するのに十分なだけの-1/-1カウンターが置かれる。尖塔の大長の死亡によってCathyの屍滑りが誘発する。
Stack: ...[Cathyの上天の閃光→S1M] ; [Cathyの屍滑り→尖塔の大長]

屍滑りの能力が解決される。これは大長をCathyのコントロール下で戦場に戻そうとするが、Alexの標本集めによって、実際にはAlexのコントロール下で戻る。Cathyの上天の閃光が、また大長の戦場に入る際の能力がAlexの下で誘発する。大長の誘発能力の唯一の対象はCathyの墓地にある時空の満ち干である。
Stack: ...[Cathyの上天の閃光→S1M] ; [Cathyの上天の閃光→尖塔の大長] ; [Alexの尖塔の大長→時空の満ち干]

大長の能力が解決されAlexが時空の満ち干を唱える。
Stack: ..[Cathyの上天の閃光→S1M] ; [Cathyの上天の閃光→尖塔の大長] ; [Alexの時空の満ち干]

時空の満ち干が解決され、Cathyの墓地へと戻る。全てのフェイジング持ちの再生術師達がフェイズインまたはフェイズアウトする。
Stack: ...[Cathyの上天の閃光→S1M] ; [Cathyの上天の閃光→尖塔の大長]

上天の閃光の能力が解決され、尖塔の大長に無意味に2ダメージを与える。これは結果に影響を及ぼさない。
Stack: ....[Cathyの上天の閃光→S1M]

上天の閃光の能力が解決され、そもそもこれを誘発したSliver Reflectionを殺す。
これはBobの7体の腐れ肺の再生術師のうちmessengerトークンの死亡を監視していた1体を誘発する。
Stack: ...[Bobの腐れ肺の再生術師→S1M]

最後にBobの腐れ肺の再生術師の能力が解決される。ここで、それはSliver (S1M)の死亡を感知した再生術師なので、それはSlith (S1)でありShade (S0)でもありまたYetiであるトークンを生成する: これによりテープのその位置は色18となっている。Alexはこのターン標本集めを唱えているので、生成されたトークンはAlexのコントロール下に置かれる(つまりカズールの大将軍から見える)。これはカズールの大将軍、有毒グールと上天の閃光を誘発し、またいつもの処理が継続される。

テープ切れ

初期化したテープを使い切ってしまったらどうればよいか？もしチューリングマシンが以前訪れたことのない位置に到達した場合、通常処理ループは突然停止してしまう。我々が使用するチューリング機械のテープの初期色は1なので、空でApe (A0)である無限に伸びるテープをシミュレーションする必要がある - つまり、あたかもApeトークンがたった今殺されたかのようにマシンが振る舞うようにする必要がある。

解決は簡単である。スタックの一番下、他のどれよりも下に、Bobのコントロールするまた別の腐れ肺の再生術師の能力を置き、それがConstructを生成するようにする(それは標本集めによってAlexのコントロール下に置かれる)。このConstructはApeであるがYetiでもZombieでもない。そのためどのカズールの大将軍も有毒グールも誘発せず、従って上天の閃光により直ちに死亡する。これによって、Ape YetiもしくはApe Zombieがたった今死亡した場合と全く同じようにに、再生術師 1A または 1B が誘発する。そしてまたそれはBobのConstruct 再生術師を誘発してその能力をスタックの一番下に置き、次回テープ境界を超えた際にConstructを作る準備を整える。

停止

最後に、マシンが停止する必要がある場合にはどうすればよいか？状態AにいてRatを見たとき、それは処理の終わりを意味するので、計算を停止する必要がある。

私は、出来ればテープが完全に残るようなやり方で(計算結果がテープから読めるように)、マシンがゲームを終了させるようにしたいと思った。これは初めは一見とても複雑になるように思われるが、実際は極めて簡単だ。全てのプレイヤーのライフは1なので、Alexのコントロールする復讐に燃えた死者がハックされて「復讐に燃えた死者かAssassinが一体死亡するたび、各対戦相手はそれぞれライフを1失う」となっていればいい。

マシン状態がAであるときにRatが一体死亡すると、「Ratが1体死亡するたび、Assassinを1体生成する。」となった再生術師 17A を誘発する。Assassin が生成され、上天の閃光のみを誘発し直ちに死亡する。これは復讐に燃えた死者を誘発し、それが解決されるとき、Alex以外の全員が死にゲームが終了する。これでテープの最終状態を読み取る事ができる。

カード (マジックチューリングマシン v5: 腐れ肺の再生術師 / 尖塔の大長)

(この記事は以下のページの翻訳です: http://www.toothycat.net/~hologram/Turing/Cards.html)

ゲームの状態は以下のとおり:

4人対戦ゲームである。プレイヤーはAlex、Bob、CathyとDenzilとする。Alexはクリーチャートークンからなるチューリングテープをコントロールする。全てのプレイヤーのライフは1である。

一連の処理はBobのターンに起こる。これによってAP-NAPルールのおかげでに誘発能力をスタック上に正しく揃える事ができる。

戦場

これらのカードの多くは人工進化を1回以上唱えることでハックされている。(もし人工進化を4回よりも多く唱える事が気にかかるなら、啓発のジンやイゼットのギルド魔道士を使えばよい。) マシンの実行中に殺されないように、リスト上で*と印のついたクリーチャーは全て不自然な淘汰によってAssembly-Workersにタイプが変更されており、ハックされたドラルヌの十字軍によってそれらは追加でYetiでもZombieでもある。

戦場にあるカードは以下の通り:

  • カズールの大将軍*、 Alexがコントロールしている、ハックされて「カズールの大将軍か他のYetiが1体あなたのコントロール下で戦場に出るたび、あなたはあなたがコントロールする各Yetiクリーチャーの上に、それぞれ+1/+1カウンターを1個置いてもよい。」と読む。
  • カズールの大将軍*、 Alexがコントロールしている、ハックされて「カズールの大将軍か他のZombieが1体あなたのコントロール下で戦場に出るたび、あなたはあなたがコントロールする各Zombieクリーチャーの上に、それぞれ+1/+1カウンターを1個置いてもよい。」と読む。
  • 有毒グール*、 Bobがコントロールしている、元のテキスト通り「有毒グールか他のZombieが1体場に出るたび、全てのZombieでないクリーチャーはターン終了時まで-1/-1の修正を受ける。」と読む。
  • 有毒グール*、Bobがコントロールしている、ハックされて「有毒グールか他Yetiが1体場に出るたび、全てのYetiでないクリーチャーはターン終了時まで-1/-1の修正を受ける。」と読む。
  • 上天の閃光、Cathyにコントロールされている。
  • 36つの腐れ肺の再生術師*のコピー、全てAlexにコントロールされている、全て2回人工進化によってハックされている、全てテフェリーの呪いまたは不可視の外套によってフェイジングを付与されている、そして18体は次元のほころびによってフェイズアウトしている。初期状態でフェイズインしている18体は Yurii Rogozhinの (2, 18) 万能チューリング機械におけるq1プログラムをエンコードしている:
    • Ape (A0) が死ぬたび、 Siren (S1) を作る。
    • Bat (B0) が死ぬたび、 Elf (E2) を作る。
    • Cat (C0) が死ぬたび、 Slith (S1) を作る。
    • Demon (D0) が死ぬたび、 Archer (A2) を作る。
    • Eye (E0) が死ぬたび、 Devil (D1) を作る。
    • Fish (F0) が死ぬたび、 Harpy (H2) を作る。
    • Giant (G0) が死ぬたび、 Juggernaut (J2) を作る。
    • Hag (H0) が死ぬたび、 Flagbearer (F1) を作る。
    • Imp (I0) が死ぬたび、 Faerie (F2) を作る。
    • Djinn (J0) が死ぬたび、 Illusion (I1) を作る。
    • Kavu (K0) が死ぬたび、 Leviathan (L1M) を作る。
    • Leech (L0) が死ぬたび、 Insect (I1M) を作る。
    • Mutant (M0) が死ぬたび、 Basilisk (B1M) を作る。
    • Ninja (N0) が死ぬたび、 Orc (O2) を作る。
    • Ox (O0) が死ぬたび、 Praetor (P1) を作る。
    • Pegasus (P0) が死ぬたび、 Rhino (R2M) を作る。
    • Rat (R0) が死ぬたび、 Assassin (HALT) を作る。
    • Shade (S0) が死ぬたび、 Camel (C2) を作る。
  • フェイズアウトしている18体は同様にq2プログラムをエンコードしている:
    • Ape (A0) が死ぬたび、 Camel (C2) を作る。
    • Bat (B0) が死ぬたび、 Camel (C2) を作る。
    • Cat (C0) が死ぬたび、 Bringer (B1) を作る。
    • Demon (D0) が死ぬたび、 Efreet (E2) を作る。
    • Eye (E0) が死ぬたび、 Ally (A1) を作る。
    • Fish (F0) が死ぬたび、 Knight (K2M) を作る。
    • Giant (G0) が死ぬたび、 Harpy (H2) を作る。
    • Hag (H0)が死ぬたび、 Golem (G1) を作る。
    • Imp (I0) が死ぬたび、 Juggernaut (J2) を作る。
    • Djinn (J0) が死ぬたび、 Golem (G1) を作る。
    • Kavu (K0) が死ぬたび、 Frog (F2M) を作る。
    • Leech (L0) が死ぬたび、 Juggernaut (J2) を作る。
    • Mutant (M0) が死ぬたび、 Orc (O2) を作る。
    • Ninja (N0) が死ぬたび、 Orc (O2) を作る。
    • Ox (O0) が死ぬたび、 Noggle (N1) を作る。
    • Pegasus (P0) が死ぬたび、 Siren (S2) を作る。
    • Rat (R0) が死ぬたび、 Sliver (S1M) を作る。
    • Shade (S0) が死ぬたび、 Myr (M1) を作る。
  • 最初の16体の再生術師は普通の方法で唱えられ、バザールの交易商人で寄付される。残りの20体はクローンとヴェズーヴァの多相の戦士が再生術師をコピーしている。フェイジングを付与するためのエンチャントはテフェリーの呪い、不可視の外套、またはエンチャント複製を用いればよく、それらはいずれかのプレイヤーによって唱えられバザールの交易商人で寄付される。フェイズアウトする際トークンは消滅してしまうので、これらのクリーチャーやエンチャントはトークンであってはならない。以上で用いた全てのクリーチャー・タイプは公式のマジック・クリーチャータイプによる: 選択された理由については仕組みを読むこと。
  • かなりの数のドラルヌの十字軍、全てハックされている。これはトークンによるコピーでもよい: 十字軍を1つ、例えば銀白の突然変異とカーンの接触でクリーチャー化して、複製の儀式や瓜二つを使ってより多くを作る事ができる。それらは以下のように読む:
    • 全てのAssembly-Workersは同時にYetiでありZombieである。
    • 全てのA1は同時にYetiでありA0である。
    • 全てのA2は同時にZombieでありA0である。
    • 全てのB1は同時にYetiでありB0である。
    • 全てのB2は同時にZombieでありB0である。
    • 全てのC1は同時にYetiでありC0である。
    • 全てのC2は同時にZombieでありC0である。
    • …
    • 全てのS1は同時にYetiでありS0である。
    • 全てのS2は同時にZombieでありS0である。
    • 全てのB1Mは同時にReflectionである。
    • 全てのF2Mは同時にReflectionである。
    • 全てのI1Mは同時にReflectionである。
    • 全てのK2Mは同時にReflectionである。
    • 全てのL1Mは同時にReflectionである。
    • 全てのR2Mは同時にReflectionである。
    • 全てのS1Mは同時にReflectionである。
    • 全てのConstructは同時にA0である。
  • 死の支配の呪いがAlexをエンチャントしている。また仕組まれた疫病が2つあり、1つはYetiに、もう一つはZombieにセットされている。これらはドラルヌの十字軍によるパワー・タフネスの増加を取り消す役割を持つ。
  • 8体の腐れ肺の再生術師*、Bobにコントロールされている。これらはフェイズアウトしないので、トークンによるコピーでよい。これらはハックされて以下のように読む:
    • Basilisk (B1M)が死ぬたび、Blinkmoth (B1)を作る。
    • F2Mが死ぬたび、Fwを作る。
    • I1Mが死ぬたび、I1を作る。
    • K2Mが死ぬたび、K2を作る。
    • L1Mが死ぬたび、L1を作る。
    • R2Mが死ぬたび、R2を作る。
    • S1Mが死ぬたび、S1を作る。
    • Constructが死ぬたび、Constructを作る。
  • 尖塔の大長、Alexにコントロールされ所有されている。
  • タジュールの射手*、Alexにコントロールされている、ハックされて「タジュールの射手か他のReflectionが1体あなたのコントロール下で戦場に出るたび、飛行を持つクリーチャー1体を対象とする。あなたは「タジュールの射手はそれに、あなたがコントロールするReflectionの総数に等しい点数のダメージを与える。」を選んでもよい。」と読む、また荒廃の鎌を装備している。
  • 少なくとも6体のReflectionトークン*、Alexにコントロールされている。
  • 屍滑り、Cathyにコントロールされている。
  • 復讐に燃えた死者、Alexにコントロールされている、ハックされて「復讐に燃えた死者か他のAssassinが場からいずれかの墓地に置かれるたび、各対戦相手は1点のライフを失う。」と読む。
  • プレイヤーは土地をいくつコントロールしていてもよく、これらを準備する助けとなる。もし望むならば他にエンチャントやアーティファクトがあってもよく、またAssembly-Workersに変化しているならば他にクリーチャーがあってもよい。

他のゾーン

他のゾーンにも必要条件がある。
Cathyの墓地には時空の満ち干が一枚だけある。
他のプレイヤーの墓地にはインスタントやソーサリーが無い。

このターンでこれまでに行われたこと

以下が行われている必要がある:

  • Alexは標本集めを唱えた。
  • 使用されたインスタントカードはすべて追放されているか、例えば霊都の灯籠によって、既に墓地には無い必要がある。

それで、どういう仕組なの？

ここで一部始終を読んで！

概説 (マジックチューリングマシン v5: 腐れ肺の再生術師 / 尖塔の大長)

(この記事は以下のページの翻訳です: http://www.toothycat.net/~hologram/Turing/)

マジック・ザ・ギャザリングはチューリング完全である

マジック・ザ・ギャザリングが複雑なゲームであることは知られている。しかし今や証明されたのである: マジックのカードを使ってコンピューターをも組み立てられる事が。

「チューリング完全」とは何を意味するか?

「チューリング完全性」という概念がある。それは、あるシステムがある特定の複雑性を備えていることを示すのに用いられる。あらゆるチューリング完全なシステムは、理論上その他のあらゆるチューリング完全なシステムをエミュレートする事が出来る。あるシステムのチューリング完全性を示す一つの方法は、そのシステム内で「チューリング機械」を作ることである。これはチューリング完全性を示す唯一の方法ではないが、理解しやすい方法の一つではある。このサイトではマジック・ザ・ギャザリングのカードを用いて万能チューリング機械を組み立てる方法を解説する。

しかし、マジックはプレイヤーによる多くの選択を伴うのでは？

その通り、本来は。しかし通常のゲームプレーにおいても時たま、カードやゲームのルールに基いて、3、4つの一連のイベントが選択肢なしに立て続けに起こる事がある。これから説明する機械では、それを無数に続く強制的な選択へと拡張する。

私の考えるマジックチューリングマシンでは、ゲームが選択肢を提示する場合を除いて、プレイヤーは全く何もしない。

ひとたびゲーム内で「機械」が動き始めると、以下で説明するある種の例外を除いて、プレイヤーの選択を全く必要とせずに処理は継続する。例外: 機械が用いるカードのうちいくつかは「あなたは[Xを行う]を選んでもよい。そうしたなら、[Yが行われる]」と書かれている。そのような場合、機械はそのプレイヤーが必ず、また唯一の方法で、Xを行えるよう準備する。そしてプレイヤーは常に提示された選択肢を選ぶ。

(「してもよい」カードを取り除く可能性に関する議論については、「今後の方向性」を見ること。)

どういう仕組？

いいことを聞いてくれた！このサイトでは機械が必要とするカードの完全なリストと仕組みについての詳しい説明を読む事ができる。この奇怪なものを作り出した人物についてもっと知ることもできる。楽しんで！

[翻訳] マジック・ザ・ギャザリングはチューリング完全である

マジック・ザ・ギャザリングがチューリング完全である事はよく知られています。最近原文を読んで感銘を受けたので、作者のAlexさんに許可を得て翻訳しました。

大事なポイントは、

  • 実在するカードを組み合わせて、プレイヤーによる干渉（対象や効果の選択）を必要とせず *1に、カードのテキストとゲームのルールのみに基いて（誘発能力を多用して）チューリング機械を実行する。
  • Yurii Rogozhinによる、コンパクトな2状態18記号万能チューリング機械を実装する。テープはクリーチャートークンの列で、18個の記号はクリーチャータイプで、2つの状態はフェイジングで表現される。
  • スタックに誘発能力が正しい順序で乗るようにAP-NAPルールを駆使する。プレイヤーは4人必要。
  • キーカードは人工進化。これでかなりのカードを書き換える。

http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=39923http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=39640http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=214360

「概説」、「カード」と「仕組み」を訳しました。「カード」には「仕組み」を読んでからでないと理解できない内容が含まれているので、まず「概説」を読む→「仕組み」を読みながら疑問に思った場合に「カード」を眺める、の順序で読むといいです。

*1:実際にはまだ「してもよい」能力をする選択肢を選ぶ必要がある。今後の新しいカードによっては完全に取り除かれるかもしれない。そうするとMagic OnlineでMagic Onlineを走らせたり出来るようになる。

Chrodic - Google Chrome™で動くマウスオーバー辞書拡張

ChrodicはGoogle Chrome™で動くmouseover dictionary extensionです。


特徴

  • 英辞郎辞書対応（第七版の英辞郎で動作を確認）。
  • ローカルのIndexedDBに全辞書データをインストールするので、ネットワーク通信無しで動作。
  • 複数単語からなる成句も全て表示。
  • 気になる単語はAnkiwebに保存、もしくはlocalStorageに保存しておいてCSVにエクスポート可。

作ったわけ

Firefoxで愛用していたMouseoverDictionaryという素晴らしいextensionがあるのですが、それと同じようなものがGoogle Chrome™に無かった。Chromeを使い始めて以来ALCのウェブサイトで引いていたのだけど、タブ移動のコンテキストスイッチがわずらわしくなってきたので作りました。

使い方

英辞郎 第七版(辞書データVer.136/2013年1月8日版) (<CDーROM>)
英辞郎 第七版(辞書データVer.136/2013年1月8日版) ()
posted with amazlet at 13.12.01
アルク企画開発部
アルク
売り上げランキング: 2,585
Amazon.co.jpで詳細を見る

$ iconv -c -f SJIS -t UTF-8 EIJI-118.TXT > EIJI-118-utf-8.TXT

  • 任意のウェブサイトを開いて、単語の上でマウス左ボタンを長押しすると有効化、マウスの下の単語の意味を表示する。無効にするにはマウス左ボタンをクリック。

Ankiwebに単語を保存する場合

  • Ankiwebにログインしておく。
  • 保存先のDeckをChrodicのOptionsページで設定する。

  • 保存したい単語の横に出ている数字に対応したキーを押す。


ソース

githubで公開しています。git pull & Load unpacked extensionでインストールできます。

IEEEXtreme 2009 の賞品が届いた

programming

IEEEXtremeという、IEEE主催で1.5年に1回ほどのペースで開催されているプログラミングコンテストがあります。
今回で3回目となる本大会に、Konohanasakuyaというチーム名で@nodchipと@bonboriと一緒に参加しました。
二人のパワーのおかげで5位/700チームになれたので賞品が届きました。

コンテスト概要(@nodchip先生の記事）
http://topcoder.g.hatena.ne.jp/nodchip/20091026/1256527977

結果
http://www.ieee.org/web/membership/students/xtreme/2009results.html

賞品一覧

Tシャツ表

Tシャツ裏

ボールペン

ステッカー

POJ 1769 Minimizing maximizer

POJ programming

データ構造を工夫しないと通らない、かといって典型的なデータ構造を探してきて適用すれば良いわけではない。どうにかオーダーに間に合うように工夫するのが楽しかった問題。

長さn (2 <= n <= 50000)の任意の数列を入力として、最も大きな数を出力する機械(Maximizer)を作りたい。ただし部品として使える道具は、ある区間[i, j] (1 <= i, j <= n) を昇順ソートしてくれる機械(Sorter)だけ。何段かこのSorterを重ねる事でMaximizerを作る。例えばn=10の場合だと[1, 10]のSorterが一つあれば良いし、[1, 5]のSorterの下に[5, 10]のSorterがあっても良い。

問題は、ある完成品のMaximizerが与えられているとき、無駄を省いて最小いくつのSorterでMaximizerが実現できるか答えよというもの。与えられるSorterの数はm(1 <= m <= 500000)。もちろんSorterの順序を入れ替えてはいけない。n=10の場合[1, 5] -> [3, 6] -> [5, 10]は[1, 5] -> [5, 10]に出来るので答えは2。

右端に数列の最大要素が移動しさえすれば良いので、要は上から下に選んだSorterを見ていった時に、左端から右端へ連続して移動できれば良い。f(i)を「ある位置iに最大要素を移動させるための最小コスト(Sorterの数)」として更新していけば答えが求まるので、典型的なDPと言えばそうなんだけれど、問題は最小コストを保持するデータ構造。

int dp[n];  // dp[i] = 位置iへ最大要素を移動させるための最小Sorter数

のようにしてしまいたくなるが、nの更新をm回繰り返すと50000*500000=250憶になってTLE。ここは次のような構造体をsetに入れて更新してゆくことでdpの代用とするのが正解(なのかは分からないがぎりぎり間に合った)。

struct S {
  int l;  // 区間の左端
  int r;  // 区間の右端
  int cost;  // 区間の最小コスト
  bool operator<(const S& s) const {
    return l < s.l;
  }
};

初めにsetには(S){1, n, INT_MAX}を入れておく。各段階では新たなSorterによって更新可能な範囲を書き換えていく。要はdpの区間を圧縮したようなもの。新たなSorterで更新可能な範囲の右端と左端の検索はlog(n)程度で済むし、区間はプログラムの実行全体でO(m)ほどしか生成されないので、setの各区間を更新していってもO(m*log(n))の時間で済む。
計算量の考察とそこそこの実装を求める良い問題でした。