【League of Legends】どのレーンに誰が行くのが勝率がいいのか数学的に考える【Clash】
こんにちは,皆さんはClashを楽しんだでしょうか？
土日に予定が入っていたためClashに参加できなかった男Kamoです.
決してClashを一緒にやってくれる友人が5人もいなかったわけではない
今回はLOL(League of Legends)というゲームでだれがどのレーンに行くのがチームの勝率が高くなるのだろうか？ということについて数学的に考えてみます.
LOLって何？って人もいるかもしれないので,そもそもこの記事を見に来る人いないでしょ記事に必要な範囲で簡単に説明すると.
5対5の対戦ゲームであり「TOP」,「MID」,「ADC」,「SUP」,「JG」という5つのロール(役割)をそれぞれ分担するのがセオリーのゲーム.
ということになります.
普段、仲間内ではそのときやりたい役割をそれぞれやるという感じで遊んでいるのですが,もし全力で勝ちに行くならどのような役割分担がいいのか確認してみることにしました.
ということで技術記事？の一本目は「割り当て問題」になります
割り当て問題
まずは,割り当て問題とはいったい何なのか？ということで初めに確認していきましょう。
n 人の人に n 個の仕事を割り当てるとき、最も効率のよい割り当てを見つけるための問題です。それぞれの人がそれぞれの仕事をしたときに得られる利益 (かかるコスト) が予想されているとします。 そのとき、どの人にどの仕事を割り当てると全体の利益が最大になるか (全体のコストが最小になるか) という観点から定式化を行います。下で見るように、輸送問題の特別な形とも見ることができますが、整数計画問題の 1 つともいえます。ハンガリー法などの特別な解法があるため解きやすい問題 です。
ということなので理解を深めるためにも実際に手作業で計算してみます.
ちなみに東工大OCW(Open course ware)「確立と統計」の割り当て問題での文章をそのまま使用させていただきました (東工大ありがとう！)
みんなも勉強するときにOCW便利だから使おう！（提案）
方法
じゃあ実際どうやるの？って話なんで使うデータから確認していきます.
それぞれの役割における能力を「YOUR GG」
という成績分析サイトの見込み勝率を利用することにしました.
（なお、あまりやっていないロールの勝率は基本的にそれぞれがやりたくない,経験が少ないロールであるため勝率を0％とすることにしました）
5人のロール別見込み勝率値は以下
ちなみに筆者はメンバーEです。
(うーんこのメレーできないマン)
このデータからチーム全体を見てもっとも平均勝率が高くなる（負けるコストが最も低くなる）ような組み合わせを探します.
(調べなくてもわかるとか言わない)
今回は割り当て問題の効率的な解放であるハンガリー法を用いて確認していきます.
まず今回は勝率の最大値を求めたいのですがハンガリー法はコストが最小の組み合わせを選ぶためのそれぞれの値を100から引き大小関係を逆転させておきます.
下準備が終わったのでハンガリー法の手順を確認します
Step1. 各行の各要素からその行の最小値を引き,さらに各列から最小値を引く
Step2. 0 を各行各列から 1つずつ選ぶことができれば、その0の位置の組が割当案になり,操作を終わる
Step3. すべての 0 をできるだけ少ない数の縦または横の線で覆う.
Step4. 線で消されていない要素から、それらの最小値を引き、縦横の線の重なっている 要素に加える.
Step5.一連の動作が終了したらStep.2に戻る.
これだけ見ても何のこっちゃって話なので実際にデータを用いて確認していきます
Step1. 各行の各要素からその行の最小値を引き、さらに各列から最小値を引く
簡単な操作なのでサクサクやっていきます
まずは列から
続いて行
この操作を行うことで少なくとも各行、各列に0が生じます
Step2. ゼロ(０) を各行各列から 1つずつ選ぶことができれば,その0の位置の組が割当案になり,操作を終わる
今回は選べる組み合わせがないのでStep3. に行きます
Step3. すべての 0 をできるだけ少ない数の縦または横の線で覆う.
わかりにくいですね.図示しながらやっていきます.
灰色で網掛けした部分ですべての0を覆うことができました.
Step4. 線で消されていない要素から、それらの最小値を引き、縦横の線の重なっている 要素に加える.
言葉だけで言われても(ry というわけで,実際にやっていきます
この灰色でない部分の最小値は3なので灰色でない部分から3を引き,線の重なっている部分(赤い部分)に3足します
はい,できました.
ここで一連の動作が終わったのでStep2に戻り同じ動作を繰り返します
次のStep3では0を覆う部分(灰色),縦横重なっている部分(赤色)は次のようになります
またStep4の動作を行います
一連の動作が終わったのでStep.2に戻ると,今回は以下のような組み合わせで各行各列から0を選ぶことができます.
今回0を選ぶ組み合わせはこれ1つしかないため
これで理想的なチームの組み合わせは,メンバーAは「JG」,メンバーBは「ADC」,メンバーCは「TOP」,メンバーDは「SUP」,メンバーEは「MID」に行く組み合わせになります.(やる前から分かっていたという話は禁句)
割り当て問題は今回の問題のようにそれぞれのかかるコストや発揮されるパフォーマンスがわかっている場合には効果的な方法になります.
まとめ
・報酬やコストが分かっていればすごく効果的だよ
・手計算だと結構面倒だよ
・OCW(Open course ware)って神だよ
なお実際には勝利を目指して真剣にやっているわけではないので結果通りのレーンに行くことはないのであった…
記事を投稿する前にClash無期限延期…
な ん で や
