マルコフアルゴリズムで遊ぼう！
こんにちは
TGA23のたもと申します。今回はマルコフアルゴリズムを使って遊べるMarkov Algorithm Online (MAO) を紹介しようと思うのですが、このゲーム（パズル？）は数学的な側面が強く難易度が高いため、遊ぶ人を選ぶということだけ先に断っておきます。実際、これまでに行った友人への布教活動はことごとく失敗に終わっているのですが、刺さる人には刺さるゲームだと思っているので、この記事を読んで一人でも多くの方がMAOに興味を持ってくださるとうれしいです。
マルコフアルゴリズムとは？
マルコフアルゴリズムについて一から説明すると長くなりますし、上手く説明できる自信もないのですが、幸いなことにニコニコ大百科に非常にわかりやすい解説記事があるので参考にしてください。MAOの影響を受けて書かれた記事のようなので、MAO入門としても最適だと思います。
マルコフアルゴリズムで遊ぶ
上の解説記事でも述べられていたように、マルコフアルゴリズムはチューリング完全であることが知られています。つまり、マルコフアルゴリズムを使えばあんなことやこんなことができてしまうのです。MAOでは、そんなマルコフアルゴリズムを使って様々な問題を解いて競い合うことができます。では、具体的にどのような問題があるか見てみましょう。
※注：以下、問題の解答を含みます。
0006-Sort
'A', 'B', 'C' のみからなる文字列が与えられるので、ソートしてください。 制約 ・ 1 ≦ |S|（文字列の長さ） ≦ 15
基本的な問題です。バブルソートの考え方がそのまま使えて、次のようにすれば正解できます。
BA:AB CB:BC CA:AC
0009-Flip
bit列が与えられるので、各bitを反転してください。
要するに、10010のように1と0だけからなる文字列が与えられるので、1と0を反転して01101にしろ、という問題です。初めてだと何をすれば分からないと思うので、先に解答を示します。
s0:1s s1:0s s:: :s
例として、10010という文字列にこれらの規則を適用すると、下のように変化します。
10010 s10010 (4行目を適用) 0s0010 (2行目を適用) 01s010 (1行目を適用) 011s10 (1行目を適用) 0110s0 (2行目を適用) 01101s (1行目を適用) 01101 (3行目を適用, 停止)
これを見ると、初めに先頭に付け加えられたsが、移動しながら1文字ずつビットを反転するように振舞っていることがわかります。このように、カーソルのような役割を果たす文字を導入するのは典型的なテクニックです。同様のテクニックを使う問題を見てみましょう。
0010-Increment
二進数 X が与えられるので、インクリメントしてください。 制約 ・ 1 ≦ X < 2^30
インクリメントとは値を1だけ大きくすることです。つまり、この問題ではX+1を出力すればよいことになります。1を加えるには一番最後のビットを見る必要があるので、まずはカーソルを一番右に移動させればよさそうです。カーソルを1番右まで移動させた後は繰り上がりの有無によって処理が変わります。最後のビットが0の場合はカーソルの左の0を1に変えて処理を終わればいいですが、1の場合は0に変えたうえで、繰り上がりのためにもう1つ左のビットを見る必要があります。そのビットが0なら1に変えて処理を終了すればいいですが、1ならさらに左のビットを見る処理を繰り返す必要があります。つまり、最初に用いた右側に移動するカーソルとは別に、左に移動するカーソルを新たに導入する必要があります。これらを踏まえると、解答は以下のようになります。sが右に移動するカーソルで、tが左に移動するカーソルです。
s1:1s (右に移動) s0:0s (右に移動) s:t (カーソルの向きを変更) 0t::1 (値を増やして終了) 1t:t0 (左へ繰り上がる) t::1 (繰り上がりで桁が増える場合の処理) :s (右向きのカーソルを呼び出す)
この解答例では7つの規則を要しましたが、実は6つでも正解できます。上の解法の無駄なところは、sとtの2種類の文字を用いることでカーソルの移動方向を区別している点で、これを1種類の文字に統一できればs:tの命令を削減できそうです。1文字では当然区別できないので、右向きのカーソルをs、左向きのカーソルをssで表現することを考えると、解答は以下のようになります。
1ss:ss0 0ss::1 ss::1 s0:0s s1:1s :s
挙動がイメージし辛いですが、実行するとまず1つのsがビット列の一番右まで移動した後、新たなsが出現して一番右まで移動し、初めのsと隣り合ってssとなることで自動的に左向きのカーソルになります。
このように、MAOにはただ問題を解くだけでなく、できるだけ少ない規則で解くという楽しみ方もあります。他のプレイヤーがいくつの規則で解いたかを確認することができるのですが、最小の規則数で解いているプレイヤーは大抵人間ではないです。
終わりに
今回は基本的な問題しか紹介できませんでしたが、MAOにはこれらより遥かに難しく、解きごたえのある問題がたくさんあります。たとえば、
- ビット列が回文かどうか判定する問題（0015-Palindrome）
- 十進数の正整数が11の倍数かどうか判定する問題（0047-11）
- ビンゴができているかどうかを判定する問題（0057-BINGO）
- ニムの勝敗を調べる問題（0077-Nim）
といった解くだけで難しい問題もあれば、解くのは簡単でも規則数を減らそうとすると途端に難しくなる問題もあります。どの問題も発想力が必要で、いくらでも時間を溶かせるので、ぜひMAOで遊んでみてください。