リゼット(14新)推奨日記

旧はてなダイアリー(http://d.hatena.ne.jp/risette14/ )から移行しました。

IIDXのランダム配置について・その2(CS EMPRESS編)

IIDX

スマートフォンからは表が正しく表示されないようです。ブラウザを"PC版"表示にしてご覧ください。

1.はじめに

　前回の記事では、AC環境(beatmania IIDX 27 HEROIC VERSE)におけるランダム配置分布について分析し、一定の偏りが存在する可能性は否定できないが、プレイヤーが通常のプレー中に感知できるような偏りとはなっていない、と考察した。

　引き続き今回の記事では、AC環境以外の他環境における分析として、長年CS環境の中核を担ってきたPS2用ゲームソフト”beatmania IIDX 16 EMPRESS + PREMIUM BEST”におけるランダム配置について分析と考察を行う。

　先に結論を述べておくと、本ソフトのランダム配置には明らかな偏りが見られ、またその有力な原因についても推測することができた。以下ではその詳細を述べていく。

 

2.検証方法

　今回の記事のデータについては、全面的に@yonexun氏から頂戴した。その検証方法については以下の通りである。

　PS2版 beatmania IIDX 16 EMPRESS + PREMIUM BESTのEMPRESS DISCを用いて、2種類のモードで調査を行った。

 

(1) TRAININGモード 

　“Marie Antoinette“SPAの131小節目を表示させ、ボタン自動連射機能の付いたコントローラ（連射機）を用いてRANDOMオプションのON/OFF切り替え操作を繰り返し、その様子を動画撮影することでランダムの配置を取得した。“Marie Antoinette“SPAの131小節は、”朧”SPAと同様に正規レーンで1234567の階段のみが配置されており、本調査に適している*1。

　なお、連射機にはPS用アスキーパッドV2を用いた。連射速度は約27回/秒の性能であり、約3分の撮影で2450回のランダム配置を取得することができた。撮影した動画からフレーム単位で画像を抽出し、画像解析から配置を取得した。

 

(2) FREEモード

　“BITTER CHOCOLATE STRIKER” SPAをHARDゲージにてプレーを開始し、放置状態でクイックリトライ連奏している様子を動画撮影することでランダムの配置を取得した。

　“BITTER CHOCOLATE STRIKER” SPAは開幕に正規レーンで「765432」の階段配置が繰り返されるため、ゲージが無くなって途中終了する前に全てのレーン配置先を確認することができ、本検証に適している。

　1回約9秒のプレーを約7時間撮影し、2744回のランダム配置を取得することができた。

　なお、CS EMPRESSのクイックリトライは、AC同様に途中終了時に所定のボタンを押し続けることで実行可能であるが、ACとは違って途中で強制終了する操作とクイックリトライの操作が異なるため、クイックリトライのボタンだけを押しっぱなしにしておくことで、自動的にレーン配置先を確認しながら連奏する状況を作り出すことが可能である*2。

 

 

3.「偏り」の定義について

　前回の記事同様、個々の配置傾向を確認する「独立的偏り」および、前回配置による影響を確認する「従属的偏り」の2つの観点から検討を行う。

 

4.検証結果

　TRAININGモードおよびFREEモードそれぞれについて、正規レーンに対する移動先分布および前回配置に対する今回配置分布を表に示す。表は前回の記事同様、等確率である場合の期待値を黄色、期待値+20％を赤、期待値-20%を緑とする3色カラースケールで表現し、期待値±10%以上の場合は太字とする。

スマートフォンからは表が正しく表示されませんので、以下、ブラウザを"PC版"表示にしてご覧ください。

(1)TRAININGモード

①正規レーンに対する移動先分布(横軸:配置先鍵盤、縦軸:その鍵盤に対して配置された正規のレーン)
  1 2 3 4 5 6 7
1 346 363 350 347 340 353 351
2 324 323 384 348 359 356 356
3 356 357 345 324 353 358 357
4 384 345 336 357 335 348 345
5 396 352 338 325 373 328 338
6 308 374 320 370 346 370 362
7 336 336 377 379 344 337 341
②前回配置に対する今回配置分布(横軸:今回配置鍵盤、縦軸:前回配置鍵盤)
  1 2 3 4 5 6 7
1 348 449 381 368 317 308 278
2 360 301 449 372 357 289 321
3 355 339 284 410 348 362 351
4 346 328 303 336 421 385 330
5 349 316 350 312 323 422 377
6 341 355 330 326 344 299 454
7 350 361 352 325 339 384 338

(2)FREEモード

①正規レーンに対する移動先分布(横軸:配置先鍵盤、縦軸:その鍵盤に対して配置された正規のレーン)
  1 2 3 4 5 6 7
1 406 497 424 396 382 326 313
2 380 399 486 425 372 353 329
3 381 325 347 451 421 426 393
4 367 365 364 341 463 433 411
5 396 388 372 370 320 471 427
6 403 366 372 374 387 351 491
7 411 404 379 387 399 384 380
②前回配置に対する今回配置分布(横軸:今回配置鍵盤、縦軸:前回配置鍵盤)
  1 2 3 4 5 6 7
1 419 378 405 374 380 403 384
2 352 403 389 386 425 389 399
3 384 403 400 392 420 366 378
4 436 393 343 378 420 395 378
5 399 424 424 381 336 387 392
6 360 378 385 422 382 400 416
7 393 364 397 410 380 403 396

 

　(1)②のTRAININGモードの前回配置に対する今回配置分布、(2)①のFREEモードの正規レーンに対する移動先分布については、AC環境の分布と比較して明らかに偏りが見られることがわかる。いずれも1～6鍵について、TRAININGモードでは、移動元と同じ鍵盤には配置されにくく一つ隣の鍵盤に配置されやすい傾向があること、FREEモードでは、正規と同じ鍵盤には配置されにくく、一つ隣の鍵盤に配置されやすい傾向があることが明らかである。それぞれカイ二乗検定を行うと、p値=4.98E-30、p値=2.93E-30と極めて特異であり、まったく等確率ではないと言える。

　一方で、(1)①TRAININGモードの正規レーンに対する移動先分布および、(2)②のFREEモードの前回配置に対する今回配置分布についてもカイ二乗検定を行うと、それぞれp値=0.123、p値=0.019となり、後者については等確率とは言い難いと考えられる。

　これはどのような原因なのだろうか。本記事では、その一つの推測として、本ソフトにおけるランダム配置生成アルゴリズムが偏りを生んでいる、という仮説を論ずる。

 

5.Fisher-Yates法について

　ある配列をランダムにシャッフルするための著名なアルゴリズムとして、Fisher-Yates法が存在する*3。このアルゴリズムは、(乱数生成に問題がない限りにおいて)偏りを生むことなく、計算量O(n)で配列をシャッフルすることができるため、広く利用されている。

　その具体的方法は、以下のとおりである*4。

　要素数が n の配列 a をシャッフルする(添字は1からn):

①i を n から 1 まで減少させながら、以下を実行する

② j に 1 以上 i 以下のランダムな整数を代入する

③a[j] と a[i]を交換する

 　これを図解すると以下のようになり、結果としてn!通りの分岐により配列a(n)の取りうる組み合わせn!通りを等しい頻度で網羅している。

初期状態            
添字 1 2 3 4 5 6 7
要素 1 2 3 4 5 6 7
               
入替1回目          
入替先(i=7)
添字 1 2 3 4 5 6 7
要素 1 2 3 4 7 6 5
               
  入替元をランダムに選択(j=1～7)
入替2回目        
入替先(i=6)
  
添字 1 2 3 4 5 6 7
要素 1 6 3 4 7 2 5
               
 

入替元をランダムに選択(j=1～6)

以下7回目まで同様に入替

 

 

 　n=7のケース(IIDXのケースに相当する)について、初期配置を「1234567」(正規配置に相当する)とし、本アルゴリズムを用いて1000万回のシミュレーションを行うと、レーンごとの配置確率分布は下表のとおりとなり、偏りを生んでいないことがわかる。

  1 2 3 4 5 6 7
1 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
2 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
3 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
4 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
5 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
6 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%
7 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%

 

6.Fisher-Yates法の誤った実装について

　5.で扱ったFisher-Yates法は、しばしば誤った形で実装される。その代表的な誤りとして、上に引用した手順を、②でjの値として1以上n以下から選択するようにしたものが挙げられる。図解すると以下のとおりとなる。

初期状態            
添字 1 2 3 4 5 6 7
要素 1 2 3 4 5 6 7
               
入替1回目          
入替先(i=7)
添字 1 2 3 4 5 6 7
要素 1 2 3 4 7 6 5
               
  入替元をランダムに選択(j=1～7)
入替2回目        
入替先(i=6)
  
添字 1 2 3 4 5 6 7
要素 1 2 3 4 7 5 6
               
 
ランダムに選択して入替(j=1～7)
範囲を狭めず毎回全範囲から選択している！
以下7回目まで同様に入替
 

　これは、一見問題なくシャッフルが機能しているように見えるが、実際にはシャッフル後の各配列が等確率で生成されることはない。なぜなら、この手順で生まれる分岐はn^n通りである一方、配列a(n)の取りうる組み合わせはn!通りであり、n≧3である場合、n!はn^nを常に割り切れない。このため、特定の配列が特定の配列に比べて生成されやすいという問題が生じるのである。

　さて、n=7のケース(IIDXのケースに相当する)について、初期配置を「1234567」(正規配置に相当する)とし、この誤った実装を用いて1000万回のシミュレーションを行うと、レーンの移動関係はどのような結果となるだろうか。その確率分布を以下に示す。

  1 2 3 4 5 6 7
1 14.3% 17.9% 16.2% 14.7% 13.4% 12.3% 11.3%
2 14.3% 13.2% 17.1% 15.6% 14.3% 13.2% 12.3%
3 14.3% 13.4% 12.6% 16.7% 15.4% 14.3% 13.4%
4 14.3% 13.5% 12.9% 12.3% 16.7% 15.6% 14.7%
5 14.3% 13.8% 13.3% 12.9% 12.5% 17.1% 16.2%
6 14.3% 14.0% 13.8% 13.5% 13.4% 13.2% 17.9%
7 14.3% 14.3% 14.3% 14.3% 14.3% 14.3% 14.3%

　この誤った実装では、上記(1)②TRAININGモードの前回配置に対する今回配置分布、(2)①FREEモードの正規レーンに対する移動先分布にかなり近似する配置分布を生み出すことがわかった。確率分布に対してカイ二乗検定を行うと、それぞれp値=0.292、p値=0.756となり、十分に尤もらしいと言える。

　ここから、FREEモードでRANDOMを使用した場合には正規配置に対してこの誤った実装でランダム配置を生成しているのではないか、TRAININGモードでRANDOMを使用した場合には、前回配置に対してこの誤った実装でランダム配置を生成しているのではないかと考えられる。データ構造については完全に憶測となるが、レーンの配置を保持する変数について、FREEモードの場合はステージごとに正規配置に一度初期化し、TRAININGモードの場合は初期化されず前回配置をそのまま保持しているのではないだろうか。

 

7.結論

　PS2用ゲームソフト”beatmania IIDX 16 EMPRESS + PREMIUM BEST”のEMPRESS DISCでは、ランダム配置に明確な偏りが存在しており、FREEモードでは、各レーンが正規レーンと同じ鍵盤に配置されにくく、一つ隣の鍵盤に配置されやすい。また、TRAININGモードでは、各レーンが前回と同じ鍵盤に配置されにくく、一つ隣の鍵盤に配置されやすい。

　その原因は、ランダム配置を作成するシャッフルアルゴリズムの実装誤りであると考えられ、有力なシャッフルアルゴリズムであるFisher-Yates法の実装誤り時における配置分布とほぼ一致していることから、同種の誤りが生じている可能性が高い。

　FREEモードでは正規配置を元に誤ったアルゴリズムによるシャッフルを行っていること、TRAININGモードでは前回配置を元に誤ったアルゴリズムによるシャッフルを行っていると推測される。

　データセットについてはこちら(TRAININGモード、FREEモード)に公開するので、統計に詳しい方にぜひ詳細な分析を行っていただきたい。

 

　検証・考察にご参加いただいた方　サークル"AA(A)AAA"メンバーおよび関係各位(@capue、@yonexun、@SIG49san、@genmi___san、@rice_Place、@t_cha_n、@robo_taisho、@norimisoIIDX、@radio613、@smania0711)　およびBOOTHにてカンパいただいた皆様

 

　BOOTHにて、ビートマニアの統計・歴史などをまとめた本を販売しています。売上は今後の検証資金とさせていただきますのでご興味のある方はぜひ。

 

 

*1:なお、TRAININGモードの仕様について説明を補足しておく。TRAININGモードは、選択した譜面の任意の小節を静止状態でプレビューすることができる。また、RANDOMオプションについては、適用した瞬間にプレビュー表示中の譜面のレーン配置が入れ替って表示される。通常のプレーとは異なり、このランダム配置状態でプレーを繰り返してもレーン配置は再配置されず、プレビュー表示された配置で固定されたままであるため、ランダムを再配置させるにはオプションでRANDOMのON/OFFを切り替える（一度外して付け直す）必要がある。

*2:※途中で強制終了はSTART+SELECTを長押し、クイックリトライはL1+R1（アナログコントローラ）または白鍵+黒鍵（専用コントローラ）を長押し

*3:これは元来紙とペンの利用を意識したアルゴリズムであるため、以下ではその現代的実装方法としてのDurstenfeld法を指してFisher-Yates法と呼ぶ

*4:以下はwikipediaより引用するが、IIDXに置き換えてイメージしやすいよう、添字番号は引用元で「0からn-1」となっているところ、「1からn」に振り替える。また、①でi=1のループは実際には行う必要はないが、後の説明を簡略化するため行うものとする。