項目応答理論を用いた音楽ゲームの譜面難易度推定における一次元性の確認

導入

心理学的な量を測定するための理論の1つである項目応答理論においては、(多次元拡張されていなければ)応答が一次元性を持つこと、すなわち測定しているただ1つの量のみによって応答が説明できることを仮定しています。例えば TOEFL は項目応答理論を用いて語学力という心理量を測定する試験ですが、すべての問題について、それが解けるかどうかは各人が持つ語学力によって決まっているという仮定をおいていることになります。

項目応答理論の応用としては、語学力の他にも音ゲーの譜面難易度推定というものがあります*1。こちらにおける一次元性はどうでしょう、地力という心理量があってそれを測定していると考えてもよいのでしょうか。SOUND VOLTEX なら地力はつまみ力・鍵盤力・片手力などの要素に分解して議論することが一般的です。IIDX 出身のプレイヤーが14 *2 が半分も埋まらないうちにあっさり大宇宙ステージ [EXH] をクリアするなど、一次元性に反しそうな例も知られています。ボルテの応答は先に挙げた要素からなる多次元量によって説明するほうがよいという考え方もありえます。果たしてボルテのデータセットに一次元の項目応答理論をそのまま適用するのは妥当なのか、検討しました。

手法

プレイデータに対して主成分分析を行い、それぞれの主成分の解釈を行いました。

SDVX III のスコアツールに登録されているデータのうち twitter 上で収集できたものをもちいました (プレイヤー数 2375) 。このデータ上でクリアレート *3 が 95% 以下の 351 譜面を対象として、プレイヤーが譜面を通常ゲージでクリアしていれば 1、そうでなければ 0 とした反応行列を生成しました。プレイヤーをデータ点とし、各譜面のクリア反応が説明変数です。

このデータをもちいて、各譜面のクリア反応のペアの相関を求めて相関行列とし、これの固有ベクトルを計算しました。

結果

寄与率(各固有値固有値の総和に対する割合)は次のとおりです。

f:id:pepsin-amylase:20170317040856p:plain

寄与率が低い順にソートしています。とても偏っていることがお分かりいただけるかと思います。

f:id:pepsin-amylase:20170317040900p:plain

こちらが上位 5 成分について拡大したものです。第1主成分だけで 0.5 以上ありますし、この 5 つの寄与率の和は 0.722 にもなります。

各プレイヤーの第1主成分得点を横軸に、第2主成分得点を縦軸に取った散布図は次のようになります。

f:id:pepsin-amylase:20170317041402p:plain

なんだかものすごくきれいな曲線が見えます。

同様に、縦軸を第3主成分得点や第4主成分得点に置き換えると次のようになります。

f:id:pepsin-amylase:20170317041607p:plain

f:id:pepsin-amylase:20170317041640p:plain

ここにもきれいな曲線が見えます。

また、各種成分ベクトルの要素は、第1主成分については全て正、それ以外は正の要素と負の要素がだいたい半々でした。

議論

寄与率のグラフを見ると、全体の分散のほとんどは少数の主成分で説明できることがわかります。特に、第1主成分の寄与率が0.5を超えており、これだけでも一次元性が成り立っていると言ってもいいかもしれません。

しかも、この第1主成分はただひとつ要素が全て正です。これはクリア力の主成分であると解釈できます。

より興味深いのは主成分得点です。主要主成分の方向に射影するととてもきれいな曲線が出てきます。この現象を説明する1つの仮説を以下に説明します。

簡単のため、レベル14・レベル15・レベル16の3譜面からなるデータセットで同様の実験をしたと考えます。これらの譜面の難易度には十分な一次元性があるとすると、データ点の分布は次のようになるはずです。

f:id:pepsin-amylase:20170317044424p:plain

ここに主成分、つまり分散が大きくなる方向を書き加えると、

f:id:pepsin-amylase:20170317044452p:plain

こうなります。これは第1・第2主成分得点の散布図に近い感じがします。第3主成分は、15と16の軸を取り替えて *4

f:id:pepsin-amylase:20170317044643p:plain

こんな感じになっている気がします。

結論

主成分分析を行うことにより、寄与率 0.5 を持ち、しかも地力と解釈できる主成分を得ました。第2主成分以下についても、一次元性を仮定すれば難易度を別の形で表現したものであるとして説明できる可能性を示しました。SOUND VOLTEX のクリアデータは一次元性を仮定して解析してもよさそうです。

今後の課題

  • 他の反応(ハードクリア、UC *5 など)での一次元性
  • 他のゲームに置ける一次元性
  • 譜面属性は経験的には明らか。今回はノイズとの分離に失敗しただけかもしれない。一般的に考えられている属性が偏った譜面だけをデータセットに集めたら主成分にそれが現れるかも *6
  • 「仮説」は主成分得点の散布図が特定の曲線上以外にも点を持つことを完全には説明できていない。

 

 

 

*1:強引な導入です

*2:III 基準。実験をしていた頃は IV はリリースされていませんでした。

*3:プレイしたことのあるプレイヤーのうちクリアした人の割合

*4:どちらか一方の重みをマイナス1倍することに対応する?

*5:フルコンボのことです

*6:簡便な実験法としてはボルテでテカリと松戸の譜面を集めてくるなどが考えられます

ISUCON6: Team イーグルジャンプ

ISUCON6 の予選に ICFPC のときのチームのサブセット (osa_k, mkut) で出ていました。

予選大敗北で、個人的にはデータに基づかずに適当に改善していっていた & ログ解析環境の準備を軽視した結果ボトルネック (クソデカ正規表現) に取り組むのがとても遅くなったのが敗因だと思っています。来年参加する人や実務で高速化する人は気をつけようね!

 

以下、チーム Slack で展開されたイーグルジャンプの心温まる会話集です(チーム名に合わせたアイコンを使ってるうちに気分がノッてきてなりきりをやっていました)。

イーグルジャンプの日常

f:id:pepsin-amylase:20160922001436p:plain

今までなりきりをやるのは頭のネジが足りない人だと思っていたのですが、いざやってみるとあたかも自分が美少女になったような気分になり、やってる人の気持ちがわかりました。 みんなもやりましょう。

f:id:pepsin-amylase:20160922001926p:plain

デプロイは osa_k 謹製 hubot aoba によって自動化されていましたが、本番時にうまく動かなかったのが残念。

f:id:pepsin-amylase:20160922002042p:plain

いやあ素敵な会社だなあ、おっとこんなところに Javascript のコードがあるぞ、実行してみよう……?

f:id:pepsin-amylase:20160922002335j:plain

ところがどっこいっ... 現実ですっ...これが現実っ…!

ICFPC 2016: Team 天羽々斬

EDIT 2016/9/22: !!! 最終順位も2位でした !!! やったぜ

 

ICFPC 2016 に出ていました。ランキング凍結時点で2位でした。優勝してるといいな〜、1位は凍結前で我々の3倍だったり1問を除いて全問解いたりしてますが。

 

ぼくは基本的にはアルゴリズムを考えて実装する係でした。この記事では自分のやったことについて書きます。インフラ周りについては @osa_k がきっと何か書いてくれると思います。

EDIT 2016/8/12: @osa_k が書いてくれました。さすが!

osak.hatenablog.jp

問題: http://icfpc2016.blogspot.jp/2016/08/task-description.html

凍結前のランキング: http://2016sv.icfpcontest.org/leaderboard

ソースコードhttps://github.com/osak/ICFPC2016

書いたツール

今年は SOUND VOLTEX からツール名を取りました。

rasis

チーム slack 用のコマンドラインインターフェイス。各人が思い思いの口調で喋らせてキャラ崩壊してたのがおもしろかったです。

ちなみにこのツールはコンテスト開始前に @osa_k が slack を立てた時に作りました。準備は大事。

f:id:pepsin-amylase:20160809070122p:plain

 

maxima

汎用ソルバー。facet(折り紙の折れ線で作られる多角形)が何枚重なっているのかやそれらの表裏や接続関係を全探索して正方形に復元できるかをチェックするアルゴリズムです。

コンテスト開始3時間後のお昼ごはんを食べている頃に思いついてチームメイトに言ってみると軒並み「確かに解けそうだけどバグる要素しかない(線分アレンジメント・双対グラフ構成・動的計画法による重なり枚数の列挙・全域木の全列挙・折り紙の復元)」という反応でしたが開始直後でやる気にあふれていたこともあり気合で実装しました。

Lightning が終了してもバグが取りきれず、一眠りしたあとでデバッグがおおまかに完了しましたが、結局折る回数が2回を超えると計算量が爆発してまともに解けませんでした。凸でないケースが解けるという強みがありましたが、それも @yuusti 作の天空の夜明けで解ける範囲であってこのツールは結局得点にほとんど貢献しませんでした。

いくらやる気にあふれていても事前に実装難易度や計算量を見積もっていれば結末はある程度予測できたはずで、今回の反省点になりました。

grace

すでに解いた問題とシルエットが合同(すなわち平行移動・回転・鏡像反転して得られる)な問題を探してきて解くソルバー。回転行列の導出がやや面倒である以外は、solution の生成で mkut が作った gideon が利用できたこともあってサクッと実装できました。

他のチームが古事記の再利用やそれらに少し手を加えただけの合同な問題を出していることが多かったので、少ない労力で高い効果を得ることができ maxima とは対照的な存在となりました。

また、この合同性を用いてまだ解かれていない問題をクラスタリングし、そのクラスターから得られる得点が多い順に我がチームが誇る折り紙職人が解いていくという戦略にも使用され、こちらも高い効果を発揮しました。

f:id:pepsin-amylase:20160809072948p:plain

grace cluster を報告する rasis

逆羅刹 (@osa_k 作の管理用サーバー) にもクラスタ一覧を見るページを付けてもらい、最終的にはぼくが何もしなくても職人が解くべき問題を探せる状態になっていました。

tsumabuki

@yowa さんチームが出した問題専用のソルバー。

すべての問題をビジュアライズして眺めていた @yuusti が、Team yowa からの問題は合同でなく grace では効率的に処理できないけれどもかなり規則的な生成法で生成されていることを発見しました。

他のチームもあまり解いていなかったこともあり、専用ソルバーを開発することになって書かれたのがこのツールです。終了8時間前くらいから実装を始めましたが、コンテスト終了までにバグを取り切って目標の問題を全部解き切れました。

反省

maxima をすぐに書き始めずに考え続ける精神力と判断力が必要でした。実装しているときは結構楽しかったけどね。

職人用に grace でクラスターを生成するとかすべてのビジュアライズされた問題をまとめて表示して比較・研究するというアイデアを出すなど、問題そのものでなく問題を解きやすくするための考察をできたのはよかった点です。チームに TopCoder 赤い人が2人もいるので問題考察力以外での貢献をすべきだと考えていましたが、無事達成できました。

来年は Unagi が殿堂入りしてくれたら優勝できるんですかね……。

 1位だったときにチームで出前の寿司をとって食べました。この時は楽しかったなあ。

kawatea 問題

今年の ICPC 国内予選が終わりました。選手の皆さん、そして運営に携わった皆さん、本当にお疲れ様でした。

さて、ぼく界隈で大変注目すべきこととして、今年から審判団に大学の同期であった kawatea がいます!!!! どこで差がついたのか、慢心、環境の違い……。

 かわてぃーぷろ!!!!

ところで、こちらの問題をご覧ください。

indeednow-finala-open.contest.atcoder.jp

無向の辺に適宜向きを定めてある値を最適化する??? 今年の国内予選の H か??? という疑念がこれまたぼく界隈で話題になりました。

というわけで、思い出せる限りで過去の kawatea 問題を集めました。アジア地区予選対策にご活用ください*1

2012年 JAG夏合宿 2日目 not_shiokawa + tokoharu セット

Treasure Hunt | Aizu Online Judge

House Moving | Aizu Online Judge

UTPC (FY) 2013

G: 夏休みの掃除当番 - 東京大学プログラミングコンテスト2013 | AtCoder

I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder

 

CODE FESTIVAL 2014

あさぷろ

D: 枕決め - CODE FESTIVAL 2014 Easy | AtCoder

C: 宝探し 2 - CODE FESTIVAL 2014 Hard | AtCoder

チーム対抗リレー

F: ループを探せ - CODE FESTIVAL 2014チーム対抗早解きリレー | AtCoder

J: Color Game - CODE FESTIVAL 2014チーム対抗早解きリレー | AtCoder

indeed なう 本戦A

A: Table Tennis - Indeedなう(オープンコンテスト) | AtCoder

D: Longest Path - Indeedなう(オープンコンテスト) | AtCoder

UTPC (FY) 2014

C: 最小カットと最大カット - 東京大学プログラミングコンテスト2014 | AtCoder

E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder

J: 看板の塗り替え - 東京大学プログラミングコンテスト2014 | AtCoder

 

*1:という建前でかわてぃーの作問センスを鑑賞していってください

SOUND VOLTEX の TOTAL 値

結論

SOUND VOLTEX の Effective Rate (通常ゲージ) は PUC すれば 210 % 増加すると思われます。

解説

基礎資料

SDVX 譜面保管所様の次のプレイ動画を資料とします。

www.youtube.com

 

I'm so Happy の NOVICE 譜面は全 408 チェイン、そのうちショートチップと直角つまみ(以下、これらをまとめてショートと呼びます)による分は 122 で、残りの 286 はロングと直角でないつまみ(以下、これらをまとめてロングと呼びます)によります。

仮定1: ショートとロングの回復量比は 4:1

NOVICE 譜面を見ていると、ショートを 1 つ取るたびにゲージがだいたい 1 % 増えて、ロングを1小節分取るとチェインが 16 増えてゲージがだいたい 4 % 増えることに気が付きます。

このことから、ショートとロングの回復量比は 4:1 であると考えられ、これはミス時の減少量の比と一致するので妥当な推測といえます。

bemaniwiki.com

仮定2: ゲージ量が x' % と表示されている時、真のゲージ量 x は x' ≦ x < x' + 1 (切り捨て)

EXHAUST 譜面での開始直後の変化を観察すると、1 つ目のオブジェクトで 1 %にならないので切り上げではないことがわかります。 

またゲージ最高の状態からロングで 1 ミスすると 99 %表示になることから四捨五入でもないと考えられるので、ゲージ表示が素直に実装されていれば切り捨てと考えられます。

考察

基礎資料と仮定 1 から、I'm so Happy [NOV] において、合計増加量 t とロング 1 チェイン当たり増加量 x の関係は t = 122 * (4x) + 286 * x = 774t です。

動画において 181 チェイン時点でゲージは 94 %と表示されていて、ここまでに登場したショートは 56 個です (つまりロングは 125 チェイン)。この事実と仮定 2 から 94 < 56 * 4x + 125 * x < 95 という評価を得ますので、これらを解いて 208.46 < t < 210.69 を得ます。

条件を満たす t の中では、クリア基準の 3 倍である 210 はとてもキリがよいのでこれが総増加量ではないかと考えられます。

また、別の難易度の譜面もおおよそ 500 万点の少し前でゲージが最高値に達していることから、この設定は他の譜面にも適用されていると考えてよさそうです。

今後の課題

ハードゲージの回復量とか。

Girls und Panzer ep.10-12

決勝前の準備から決勝戦。11話と12話は戦闘シーンが多くて英語的には非常に簡単。

気になった表現など

10話

swear: 誓う、ののしる

put out: (明かりなどを)消す

spare time: 空き時間

IRL: In Real Life

<-> OLO: OnLine Only

alma mater: 出身校、母校

on the house: 店のおごりで

Operation Bagration: バグラチオン作戦。独ソ戦における赤軍の最大の反攻作戦で、これによりドイツ軍は独ソ戦開始前の位置まで押し戻されることとなった。ソ連の戦車で戦うプラウダとドイツの戦車で戦う黒森峰の関係を意識した引用。

back then: その時には、その当時には

11話

brat: 子供、ガキ

repel: 撃退する、拒絶する

choke: 窒息させる

tease: からかう、(主に米)ねだる

-> Operation Teasy Tease: おちょくり作戦

pacify: なだめる

12話

enormous: 巨大な

valor: 勇気

provoke: いらいらさせる、扇動する

dizzy: めまいがする、ふらふらする

-> Operation Dizzy Dizzy: ふらふら作戦

harsh: 不快な、どぎつい

 

基本的には首を出してても安全だよと言いつつ正面から近くで撃ち合うときなど危険なときにはちゃんと西住殿が隠れてることに気がついた。

 

Girls und Panzer ep.7-9

1回戦後の戦力増強タイム (7話) とプラウダ戦 (8, 9話)

気になった表現など

7話

invalid: 1. 病弱な、病人、病弱にする(動詞は通例受け身)) 2. 無効な

病弱引数例外

antisocial: 反社会的な、非社交的な

あんたいそしある、みたいな感じで言われたので聞き取り不能だった。綴りと音が一切一致しない英語は本当にクソだと思う。

yell: 大声で叫ぶ、叫び声。エール

ICPC に YellowYell って京大のチーム名がありましたね。

get anywhere: 成功する。役に立つ。 any- なのでなんか平叙文ではあまり使わなさそうな感じがする。

be held back: 足止めを食らう

本編では(麻子が)留年をするという意味で登場

supposedly: (文修飾で)……と想像される。

grandly: 雄大に

pull it off: うまくやる、なんとかする

butt: 棒などの太い方の端、根本、(米口語)おしり

slack off: 勢いを緩める

cowards: 臆病者共

生徒会の人が使っててほんとこわいと思いました(小並感)

dandy: (口語) すてきな

pumped up: アドレナリンの活性化から来る興奮と熱狂で緊張する (pumped upの意味 - 英和辞典 Weblio辞書)

divination: 占い

<- divine: 占う、神聖な

-> divine rights: 神授王権 Civ4では大した効果がない上に宗教キチが神学から速攻で取りに行くせいで交換材料にすらならない残念な技術だったような。

8話

suck: なめる、(米俗)嫌気がさす

仕事で Javascript sucks. ばっかり言ってたので後者の意味は知ってた。

The race is not given to the swift, nor the battle to the strong. 脚が速いものが競争に勝つとは限らないし、強いものが戦いに勝つとも限らない。聖書からの引用。

laid back: くつろいだ、リラックスした

mallard: マガモ。カモさんチームのことですね。

arrogant: 傲慢な

<-> modest: 謙虚な。大学院生の頃に謙虚で優秀という言葉を乱用していたのを思い出す。

thoroughly: 徹底的に、まったく

liver: 肝臓

remnisce: 追想する、思い出を語る

burden: 重荷

cocky: (口語) 生意気な

HE shell: 榴弾 (High Explosive)

nuts: (米俗) (憎悪や落胆の意味で) ばかな、くだらない

intact: 手付かずで

9話

consolidate: 合併整理する

endowment: 寄付金、天分

本編では(文部科学省の)助成金の意味で使用されていた。

all on the table plan: ところてん作戦 なんでこの訳なんだろう。

deliberate: わざと、故意の

pierce: 貫通する

hibernate: 冬眠する、引きこもる

root for: 応援する

underdog: (試合などで) 負けそうな方

-> rooting for the underdog: 判官贔屓

daft: (口語) ばかな、まぬけな

tracer round: 曳光弾

<- round: この場合は(弾薬の)一発の意味

hall monitor: 風紀委員

lure: 誘惑する、誘い出す、ルアー

pursuit: 追跡、追求

<- pursue: 追跡する、追求する。名詞形の綴が予測不能。英語はクソ。