TAS 試行錯誤を極力抑えて追記を減らす

過去ブログの転載です。

ゲームを専用のツールを使ってスーパープレイしてタイムアタックを競うものにTASというのがありますけど、そのTASを作ることに関する記事です。

TASでは主に好きなタイミングで好きな操作を記憶させ、間違えたらやり直し（追記）ができるような、そんなことを繰り返してスーパープレイを実現します。

お遊びでRPGツクールのゲームのTASをHourglassというツールで作っていたのですが、プレイのやり直し操作である追記でハマってしまうことがありました。うまくいっているときは数フレーム前からやり直し、みたいなことが出来ていたのですが、運が悪いとデシンクしてしまい、今まで作ったTASをもう一度最初から再生して、やり直した時点になるまで待っていなきゃならない状況になってしまいました。これがものすごい長くだるくて、追記のたびに何分も待たされるのはたまったもんじゃないなと思ってました。

こういう事情があって追記は極力抑えたいのですが、試行錯誤しないといけない場面になると追記だらけになって大変です。

そこで、次のような状況になったときにどうすれば追記を抑えられるか調べました。

スイッチがあります。これを最速で押さなければなりません。ただし、スイッチがどのタイミングで現れるかが不明です。

最速で押すためには、スイッチが現れた瞬間に押す必要があるので、最速のタイミングである1フレーム（1／60 秒）を探す必要があります。

どうすれば効率的に発見できるでしょう？

タイミングが早すぎるとスイッチは現れていないので確実に失敗ですが、逆に遅すぎてもスイッチは押せてしまうので、最速かどうか分からないのです。

例えばスイッチを押すタイミングを次のようにしたとします。２０フレーム目でジャンプをしてみるとタイミングが遅くて失敗してしまい、もっとタイミングを早める必要があると分かった場合には、「２０フレーム目：遅」と記しました。

１４フレーム目：（未調査）
１５フレーム目：早
１６フレーム目：（未調査）
１７フレーム目：（未調査）
１８フレーム目：（未調査）
１９フレーム目：（未調査）
２０フレーム目：遅
２１フレーム目：（未調査）
２２フレーム目：遅

このとき、特定のタイミングは何フレームにあるかというと、１６フレーム目～２０フレーム目の間であることは分かります。

上から順に、１６フレーム目、１７フレーム目、……としていくのも良いですが、２０フレーム目が正解であった場合、結局すべて開けなければならず、非効率です。

例えば１８フレーム目が最速のタイミングだったら、

１６フレーム目：早
１７フレーム目：早
１８フレーム目：遅
１９フレーム目：遅
２０フレーム目：遅

のようになるということですね。遅は「遅いかもしれない」の記号で、その直前が早だったら最速だと分かります。

調査を進めれば確実に探し当てることができますが、調べるたびに追記するので、調べる回数をなるべく少なくする必要があります。

また、

１６フレーム目：早
１７フレーム目：早
１８フレーム目：（未調査）
１９フレーム目：遅
２０フレーム目：遅

という状況のときに１８フレーム目が最速であれば、１８フレーム目を調査するとともに、その最速なフレームを用いてゲームを進行することが出来るため、手数を一回分省くことができます。

もし、

１６フレーム目：早
１７フレーム目：（未調査）
１８フレーム目：遅
１９フレーム目：遅
２０フレーム目：遅

であったなら、１７フレーム目を調査することによって早と判明し、１８フレーム目が最速だとは分かりますが、ゲームを進行するためにはもう一度追記して、最速である１８フレーム目を選択する必要があります。この場合は追記が１回分余計に必要なのです。

探索方法は単純に、バイナリサーチをするのが良いです。範囲の真ん中を試すことで速いか遅いかが決まれば、正解のタイミングは前半にあるか、後半にあるかが分かるので、範囲を半分にすることが可能です。すなわち、１７か１８フレーム目を調べるのが最善と言えます。

この状況では結論として１７、１８フレームどちらを選択しても最善となりますが、
一般にどこを選択すれば良いか確かめておきましょう。

【追記のまとめ】
未調査フレームがｎ個あるとき、
ｎが奇数なら真ん中のフレームを選択。
ｎが偶数なら真ん中２フレームのうち時刻の早い方を選択。
これを繰り返せば確率的に最短で目的のタイミングを発見可能である。

以上がまとめです。これの導出方法と例をそれぞれ以下に記します。

導出（追記関数）

まず、次のように記号化しておきます。

×が早、○が遅です。？は（未調査）を表わします。時間は上から下へ流れています。この？を消していくことが目的となります。

このとき、最短手数で発見できる手数の期待値をt(n)と表し、これを追記関数と呼ぶことにします。追記の回数に関係しますね。（必要な追記回数はt(n)－1かな？）

上の図では×と○の直後に仕切りがありますが、この仕切りの間n＋1の範囲のどこかに最善のタイミングがあるという意味になります。範囲を狭めることにより探索します。

まずはt(0)を求めます。未調査部分がないときですね。

これはもう自明です。○の部分が最善のタイミングですから、迷わず○を選択すればOKです。手数は1回なので、t(0)＝1となります。

次はt(1)を求めましょう。

未調査部分が1つあります。これを調査すべきか？といわれたら、するに決まってます。？の部分が○かもしれず、それなら？が最善のタイミングになるので、しなきゃいけません。実際調査をすると、2つのパターンがそれぞれ1／2の確率で発生します。

青矢印はいま調査した所、赤い範囲は、最善のタイミングがある範囲です。調査によって、どちらも最善のタイミングは発見できましたが、手数に違いが出ます。

①の場合はいま調査した部分ではないタイミングが最善でしたから、もう一度追記して○の方を選択しなければなりません。手数は2になります。

一方、②は調査したタイミングと最善のタイミングが一致しているので、手数は1で済みます。手数の期待値は1／2×2＋1／2×1＝3／2となるわけですね。n＝1の場合はこれが最善手になるので、t(1)＝3／2となります。

これらをベースにして、次は飛んでt(4)を考えてみます。

これには5つのパターンがありますね。

このどれかがそれぞれ1／5の確率で発生していることになります。ここで例えば2番目の？を開いてみたとしましょう。それぞれの範囲はこう変化します。

↑かっこつきの○×は、未調査のフレームを表わします。2番目の？を開いた結果が×になるのは①～③、○になるのは④～⑤ですね。それぞれの確率は3／5, 2／5となります。

①～③だった場合は、その直後の3フレーム分が範囲になり、
④～⑤だった場合は、自分を含んだ前2フレーム分が範囲になります。

④～⑤で新しく出来た範囲を眺めてみると、これはt(1)のときの範囲にソックリだと気づきます。同じ確率で？部分が×と○になっているのです。よって、④～⑤になった際の手数は1＋t(1)となることが分かります。1足すのは、④～⑤を開いてそれが最善とは確定できなかったため、もう一度追記が必要だからです。2番目の？じゃなくて1番目の？を選択して、⑤のパターンだったとしたら、調査と同時に最善のタイミングを発見できるので、1足す必要はありません。

①～③の場合も考えておきましょう。これは同様に考えると、t(2)の状況のすべてのパターンが列挙されていますので、1＋t(2)で良いことが分かりますね。

よって、2番目の？を開いたときの期待値は
3／5 (1＋t(2))＋2／5 (1＋t(1))
となります。

一般に、i番目の？を開いたときの期待値は
i／(n＋1) (α＋t(i－1))＋(n－i＋1)／(n＋1) (1＋t(n－i))
となります。αはi＝1なら0、それ以外なら1です。

さっき書いたように、i＝1のときは最善のタイミングを発見できる可能性があるので、1足さないときがあるためです。

t(n)は、1≦i≦nの範囲で上の式を計算したときの最小値となります。
↓こういうことですね。
t(n)＝min[1≦i≦n]{i／(n＋1) (α＋t(i－1))＋(n－i＋1)／(n＋1) (1＋t(n－i))}

バイナリサーチするなら、
nが奇数：i＝(n＋1)／2
nが偶数：i＝n／2 or n／2＋1
のときをそれぞれ調べればOKです。

nが偶数のときはどちらのiを選んでも基本同じになりますが、iが小さい方がα＝0になる可能性がありますから、i＝n／2を選択するようにした方が良いでしょう。

nが奇数：i＝(n＋1)／2
nが偶数：i＝n／2

このときのiを代入して得られるのが最善手です。バイナリサーチするからですが、何でなのでしょうね？細かい証明はしてません。それぞれ代入することにより、t(n)は次のようにして表示できます。

【追記関数】
t(0)＝1
t(1)＝3／2
t(2)＝2
t(n)＝1＋t( (n－1)／2 )（nは奇数, n≠1）
t(n)＝1／(n＋1) {(n／2＋1) (1＋t(n／2))＋n／2 (1＋t(n／2－1))}（nは偶数, n≠2）

例えばt(4)だったら、
t(4)＝1／5 {3(1＋t(2))＋2(1＋t(1))}
となって、さっきと同じ式が出てきます。

t(2)はα＝0になるという理由で別に書いていますが、t(2)＝2になりますので
t(4)＝1／5 {3(1＋2)＋2(1＋3／2)}
＝1／5 (9＋5)
＝14／5
と求まります。未調査フレームが4個あったら、3回ちょっと調べる必要があるということですね。

例

未調査フレームが奇数個なら真ん中、偶数個なら真ん中のうち早い方をそれぞれ選び続ければ良いのでした。実際にやってみましょう。

１８フレーム目が最善だとします。

【０回目】

１４フレーム目：（未調査）
１５フレーム目：早
１６フレーム目：（未調査）
１７フレーム目：（未調査）
１８フレーム目：（未調査）
１９フレーム目：（未調査）
２０フレーム目：遅
２１フレーム目：（未調査）
２２フレーム目：遅

未調査フレームは１６～１９フレームの範囲です。偶数個なので、真ん中のうち早い方を選択します。１７フレーム目ですね。

【１回目】

１４フレーム目：（未調査）
１５フレーム目：早
１６フレーム目：（未調査）
１７フレーム目：早
１８フレーム目：（未調査）
１９フレーム目：（未調査）
２０フレーム目：遅
２１フレーム目：（未調査）
２２フレーム目：遅

早いことが分かりました。範囲は１８～１９フレームに絞られます。
また偶数個なので、真ん中のうち早い方ということで１８フレーム目を選択します。

【２回目】

１４フレーム目：（未調査）
１５フレーム目：早
１６フレーム目：（未調査）
１７フレーム目：早
１８フレーム目：遅
１９フレーム目：（未調査）
２０フレーム目：遅
２１フレーム目：（未調査）
２２フレーム目：遅

遅いことが分かりました。これで確定です。直前のフレームではもっと早いよ、と言っているので、その直後である１８フレーム目が最善のタイミングだと判明します。

こんな感じで調査していけば、追記回数を少なく済ませられます。デシンクにお悩みの方はぜひやってみてください。