ランクマで勝つにはどんなデッキを使うべき？？

こんにちは、くりりんです。

この記事はメカオーは大会に強い？弱い？の続きのつもりで書いたものになります。先の記事ではランクマッチに二つのデッキのみが半分ずつ存在すると仮定して、どのようなデッキを使うべきかを考えたが、今回はもう少し実際のランクマッチに近い状況を考えてみる。

注意点として先の記事同様、単純なモデルで考えたお遊びなので、この記事の結果だけ見て安易に実践に活かそうとは思わないでいただきたいです。

今回は、ランクマッチにおいて$${N}$$個のデッキ($${N≥2}$$)があり、デッキ$${k}$$, $${(k=1, 2, ...,N)}$$がそれぞれ$${p_k (0≤p_k≤1, \sum_{k=1}^{N}p_k=1)}$$の割合で存在している場合に勝利する確率を最大にするためにはどのようなデッキを使えば良いかを考えてみよう。

自分の使用するデッキXは

デッキ$${k}$$に対して$${x_k (0≤x_k≤1)}$$の確率で勝利するとする。

このときランクマッチを一戦して勝利する確率$${P}$$は

$${P=\sum_{k=1}^{N}{p_k}{x_k}}$$と計算できます。

また前回の記事と同様に$${\sum_{k=1}^{N}x_k}$$の値は固定と言う制約をつける。問題を単純にするため、この一定値は$${\cfrac{N}{2}}$$とする。(全てのデッキに対して勝率$${\cfrac{1}{2}}$$のとき$${\sum_{k=1}^{N}x_k=\cfrac{N}{2}}$$なのでこれを基準にして考える。)この制約のもと$${P}$$を最大化する$${x_1, x_2, ...x_N}$$を求める。

制約$${0≤x_k≤1(k=1, 2, ...,N), \sum_{k=1}^{N}x_k=\cfrac{n}{2}}$$の元$${P=\sum_{k=1}^{N}{p_k}{x_k}}$$を最大化したいと言う問題に帰着したが、これは典型的な線型計画法の問題になっている。（人によっては計算せずとも一瞬で答えがわかると思うが、今回はちゃんと計算することにする

前回の記事で、多変数関数の制約付き最大値や最小値を求めるにはラグランジュの未定乗数法を使えば良いといったが今回は適用できない。ラグランジュの未定乗数法は大雑把にいえば極大値や極小値を見つけるための方法だが最大値の候補は極大値だけではなく、定義域の境界もある(今回の定義域は$${0≤x_k≤1(k=1, 2, ...,N), \sum_{k=1}^{N}x_k=\cfrac{N}{2}}$$)。定義域の境界で最大値をとるときにはラグランジュの未定乗数法によって最大値を求めることができず、今回もそうなっている。実際計算してみるとPの停留点を与える$${x_1, x_2, ...x_N}$$が存在しないことがすぐにわかります。（Pは一次関数なので計算せずとも極大値が存在しないことは明らかだが）

その代わり、Pがただの一次関数なので簡単に最大値を求めることができる。

線形計画法っぽくこの問題を考えても良いのだが、今回はできるだけ幅広い方々に楽しんでいただくため、なるべく高校までの数学の言葉のみを使って考えていこうと思う。

まず、準備として$${p_k (0≤p_k≤1, (k=1, 2, 3, ...)}$$に対して$${p_1≤p_2≤...≤p_N}$$と言う条件をつけておこう。これは$${p_k (k=1, 2, 3, ...)}$$を小さい順に整理しているだけで、一般性は失っていない。

次に、$${P}$$を最大化するには$${x_N}$$を最大に、つまり$${x_N=1}$$とするのが良い（$${N≥2}$$なので$${0≤x_N≤1}$$かつ$${\sum_{k=1}^{N}x_k=\cfrac{N}{2}}$$を満たす最大の$${x_N}$$は1)ことを示す。（一番多いデッキに絶対勝てるようにすれば良いと言うこと）

$${x_N=1}$$としたとき$${P=p_N+\sum_{k=1}^{N-1}{p_k}{x_k}}$$だがここから$${x_N}$$を$${∆(0≤∆≤1)}$$だけ減らしたとき、$${P}$$の変化分$${δP}$$を計算する。$${x_N}$$を$${∆(0≤∆≤1)}$$だけ減らした分$${x_1, x_2, ...x_{N-1}}$$を増やせる（もちろん$${0≤x_k≤1(k=1, 2, ...,N), \sum_{k=1}^{N}x_k=\cfrac{n}{2}}$$)を満たしたままだが）。この$${x_k(k=1,2, 3, ...N-1)}$$の増加分を$${∆_k}$$とおく。当然$${\sum_{k=1}^{N-1}∆_k=∆}$$となっている。また今回は$${∆_k≥0(k=1,2, 3, ...N-1)}$$としておく。$${{∆_k}<0}$$となる$${k}$$が存在するときも問題なく示せるが、少々面倒なので今回は省略する。（例えば残りの$${x_1, x_2, ...x_{N-1}}$$を$${\sum_{k=1}^{N-1}{p_k}{x_k}}$$が最大となるよう取ることをにあらかじめ約束しておくと良い）

このとき

$${δP=(p_N(1-∆)+\sum_{k=1}^{N-1}{p_k}({x_k+∆_k}))-(p_{N}+\sum_{k=1}^{N-1}{p_k}{x_k})}$$

$${=-{p_N}∆+\sum_{k=1}^{N-1}{p_k}∆_k}$$

 $${≤-{p_N}∆+\sum_{k=1}^{N-1}{p_{N-1}∆_k}}$$ ($${p_1≤p_2≤...≤p_{N-1}}$$なので)

$${=-{p_N}∆+p_{N-1}\sum_{k=1}^{N-1}∆_k}$$

$${=-{p_N}∆+{p_{N-1}}∆}$$

$${=-({p_N}-{p_{N-1}})∆}$$

$${≤0}$$ ($${p_{N-1}≤p_{N}, 0≤∆}$$なので)

より$${P}$$はかならず小さくなる（または変化しない）。

これにより$${x_N=1}$$とするのが良いとわかった。

次に残りの$${x_1, x_2, ...x_{N-1}}$$を決めていきたいが、この段階で$${P=p_{N}+\sum_{k=1}^{N-1}{p_k}{x_k}}$$となっており$${x_1, x_2, ...x_{N-1}}$$の制約は$${0≤x_k≤1(k=1, 2, ...,N-1), \sum_{k=1}^{N}x_k=\cfrac{N}{2}-1}$$となる。$${p_N}$$は定数なので、制約$${0≤x_k≤1(k=1, 2, ...,N-1), \sum_{k=1}^{N-1}x_k=\cfrac{N}{2}-1}$$のもと$${\sum_{k=1}^{N-1}{p_k}{x_k}}$$を最大化する問題になっていて、これは最初考えていた問題

「$${0≤x_k≤1(k=1, 2, ...,N), \sum_{k=1}^{N}x_k=\cfrac{N}{2}}$$の元$${P=\sum_{k=1}^{N}{p_k}{x_k}}$$を最大化」

で$${N}$$を$${N-1}$$に置き換えて、制約条件が少しだけ変わったものとなっている。なので先ほどと同じ議論で$${x_{N-1}=1}$$, $${x_{N-2}=1}$$,....としていくのが良いことが言えます。

しかしこれはずっと続くわけではない。

先の議論をを$${m}$$回繰り返すと、つまり$${x_{N}=x_{N-1}=...=x_{N-m+1}=1}$$とすると、その次は$${P={\sum_{k=1}^{N-m}{p_k}{x_k}}+{\sum_{k=N-m+1}^{N}{p_k}}}$$を制約$${0≤x_k≤1(k=1, 2, ...,N-m), \sum_{k=1}^{N}{x_k}=\cfrac{N}{2}-m}$$のもとで最大化することとなる。ここで$${\cfrac{N}{2}-m≥1}$$となっていれば次も同様の議論を繰り返すことができるが$${\cfrac{N}{2}-m<1}$$となっていると$${0≤x_{N-m}≤1, \sum_{k=1}^{N}x_k=\cfrac{N}{2}-m}$$を満たす最大の$${x_{N-m}}$$が1でなくなってしまうので同様の議論を繰り返せない。では$${m=M}$$回目で初めて$${\cfrac{N}{2}-m<1}$$となったとしよう。$${N,M}$$は共に整数なので、このとき$${\cfrac{N}{2}-M}$$の値は$${N}$$が偶数なら$${0}$$、奇数なら$${\cfrac{1}{2}}$$となる。ちなみにこの$${M}$$の値は$${[\cfrac{N}{2}]}$$と表せる。ただし$${[・]}$$はガウス記号を表す

$${N}$$が偶数の時

$${0≤x_{N-M}≤1, \sum_{k=1}^{N}x_k=0}$$なので、残りの$${x_1, x_2, ...x_{N-M}}$$は全て0とするしかない。この時$${P=\sum_{k=N-M+1}^{N}p_k}$$

$${N}$$が奇数の時

$${0≤x_{N-M}≤1, \sum_{k=1}^{N}x_k=\cfrac{1}{2}}$$なので、$${x_{N-M}}$$を最大、つまり$${x_{N-M}=\cfrac{1}{2}}$$として残りの$${x_1, x_2, ...x_{N-M-1}}$$を全て0とすれば良い。

この時$${P=\cfrac{1}{2}p_{N-M}+\sum_{k=N-M+1}^{N}p_k}$$

まあ、考えてみればそれはそうだ、と言う結果だ。

これはできるだけ存在割合の多いデッキに絶対勝てるようにして少ないデッキは完全に諦めるのが良いと言うことを表していて、かなり直感的に納得しやすい。

ただし実際にこのようなデッキが作れるとは考えにくいし、仮にそのようなデッキがあったとしてもそのデッキによってデッキ分布が大きく変動してしまうだろう。