マヤゲーム
パズル：スワップ・マシンの並列プログラミング - 檜山正幸のキマイラ飼育記 (はてなBlog)にコメントした件。マヤゲームってあまり知られていないのかな？と思って検索してみたら、確かにほとんど情報がない。ルールとヤング図の作り方ぐらいしか知らないけど、とりあえず書いてみる。
ゲームの名前を手持ちの本で改めて調べてみると、「マヤゲーム」「佐藤のゲーム」「ウェルターのゲーム」と、呼び名がいっぱいあるけど、マヤゲームで通す。
ルール
- 無限個(十分たくさんで可)の碁石を用意して一列に並べる。列の左方向には無限個の黒石、右方向には無限個の白石を並べる。
- 列の真ん中あたりは白黒適当に配置しておく。これが初期配置になる。
… ●●○○●●●○○●○●●○○○○○ …
- 2人のプレイヤーが次の操作を交互に行う
- 任意に白石を1つ選び、それより右にある黒石を任意に1つ選んで入れ替える。
- 石が選べなくなったら負け。つまり以下のような状態で手を渡されたら負け。
… ●●●●●●●●○○○○○○○○○○ …
で、この列をマヤ図形と呼んだわけであるが、調べてもこの言葉は出てこないなぁ。思い込みかな。
ヤング図
このマヤ図形は、ヤング図と一対一に対応する。対応付けは
- ●に↑、○に→を対応させる。
- 矢印を順につなぐ。
とすればよい。
上の初期配置は、
… ●●○○●●●○○●○●●○○○○○ … … ↑↑→→↑↑↑→→↑→↑↑→→→→→ …
となる。つなげると、
→→→→→ ↑ ↑ → ↑ →→ ↑ ↑ ↑ →→ ↑ ↑
となる。これをヤング図の輪郭と思って、タイルで埋めると
□□□□□ □□□□□ □□□□ □□ □□ □□
となる(派手に間違えていたので修正)。
マヤゲームとヤング図
マヤゲームの手、スワップは、ヤング図の方では、フック*1を外して詰める操作になる、そうだ。この操作をした後もやはりヤング図になるから well-defined。
改めて、ヤング図の方でのゲームのルールは、
- ヤング図を適当に作る。
- 2人のプレイヤーが交互に1つずつフックを外して詰める。
- ヤング図を消した方が勝ち。
となる。
マヤゲームと檜山さんのパズル
檜山さんのパズルの「A」を黒石、「B」を白石に対応に対応させると、ほとんどマヤゲームそのものになっている。違う点は
- 初期状態が決まっている。ヤング図にすると長方形。
- 隣接のスワップしか許されない。
- 黒石が右に行く事が許される。
- メモリ領域が制限されている。
- 並列実行が許されたりする。
というところぐらい。
2,3は、ヤング図の角のタイルを取る/凹みにタイルを入れる操作に対応している。また、3.1はヤング図の輪郭がX/Y軸上の特定の点を必ず通らなければならないという条件になる。
4の並列実行はイイカゲンに言えば、「干渉しない限り、同時にタイルを出し入れできる」ということになる。
パズルの方のAB列をヤング図に変換して、そのヤング図が座標の第4象限に乗っていると思う。ヤング図内の点で｜x｜＋｜y｜の最大値をヤング図のポテンシャルとでも呼ぶことにする。要するにポテンシャルとは、ヤング図の一番出っ張った所を通る傾き1の直線とx軸の切片。で、多分次が成り立つ。
並列実行を許す場合も許さない場合も、1ステップでポテンシャルは高々±1変化する。
並列実行に関してはより強く、
並列実行を許せば、1ステップでポテンシャルを1減らす(or 増やす)ことが可能。
証明はしない。ポテンシャルを定める傾き1の直線が触っている角を次々(or 同時に)消していけばいい。
これを認めれば、最短ステップ数は初期状態がAnBmのとき、n＋m になることが言えるし、その方法も同時に与えている。
オチ
実際はもう少し文字の数が（A, B以外に）増えるんですけど、
やっぱりか…。
文字をとりあえず2グループに分けてヤング図潰して…と、帰納的にやればいいのかな。最短とかきれいな表現とか自信を持って言えることが何もなくなった…。
まあ、ヤング図で表現してみたら個人的には分かりやすくなった、という話でした。
*1:あるタイルを決めて、そのタイル、その真右にあるタイル全部、真下にあるタイル全部をあわせた図形をフックという。
