2017-03-08

MMORPGに見る順序数(Ordinal)と基数(Cardinal)

数学

突然ですが英語を書いてみます。

「このMMORPGには3つのステージがあります」
「There are three stages in this MMORPG」

「私はこのMMORPGで3番目に強いプレイヤーです」
「I am the third strongest player in this MMORPG」

おなじ3でも、英語だと「three」と「third」に分かれます。

自然数のもつ意味

1,2,3…という自然数そのものには意味はありませんが、数に持たせる意味によって、呼び名が変わってきます。

「three」のように、物を数える数を 基数(Cardinal Number) と呼びます。

「third」のように、物の位置を特定する数を 順序数(Ordinal Number) と呼びます。

自然数が持つ、この2つの意味について考えてみます。

基数(Cardinal Number)

濃度 (数学) - Wikipediaより引用

それぞれの集合 A には A の濃度（|A|、card(A)、#A などで表される）と呼ばれるものが一つ割り当てられており、次の性質をみたす:

1.集合 A から集合 B への全単射が存在するとき、またそのときに限り |A| = |B|。

2.A が有限集合のとき、|A| は A の要素の個数に等しい。

ある集合の濃度であるものを基数と呼ぶ。

たとえば、あるMMORPGにおけるステージの集合をA、そのMMORPGがサービス終了したあと別のMMORPG内に移された新生ステージの集合Bとおくと、このときAからBへの全単射が存在するためcard(A)=card(B)となります。

ちなみに、自然数はすべて基数です。

順序数(Ordinal Number)

順序数 - Wikipediaより引用

整列集合 (A, <) に対して、A を定義域とする関数 G を超限再帰によって G(a) = { G(x) | x < a } と定義したとき、G の値域 ran(G) を (A, <) の順序数といい、これを ord(A, <) で表す。ある整列集合の順序数であるような集合を順序数と呼ぶ。

あるMMORPGのプレイヤー同士に強弱<が存在し、<の順番で並んだプレイヤーの集合Bにおいて「自分よりも強いプレイヤーの集合」の集合がord(B, <)となります。

誰もログインしていないMMORPGにおいては順序数は空集合∅、つまりord(B, <) = ∅です。コレが「最小の順序数」ということで、ゼロと定義します。0 = ∅

1位までのプレイヤーからなる集合ならば、「自分よりも強いプレイヤー」は空集合∅なので、ord(B, <) = {∅} となります。コレは「最小の次の順序数」ということで、イチとします。1 = {∅}

2位までのプレイヤーからなる集合ならば、「空集合∅」と、「空集合の集合{∅}」なので、2 = {∅,{∅}} となります。ちょっと無理矢理ですね。

ちなみに、自然数はすべて順序数です。

基数と順序数の違い

ここで基数と順序数の違いを見ていきます。

基数card(A)は、Aの要素の個数になります。
順序数ord(A,<)は、Aの要素の個数になります。

同じです。おわり。

しかし、この議論は重要な前提条件をひとつ見落としています。それは Aが有限集合である ということです。

Aが有限集合とは限らない、つまり 無限集合 だった場合は、どうなるでしょうか。

無限集合における基数と順序数

濃度 (数学) - Wikipediaの「基数と順序数」より引用

すべての自然数を 0, 1, 2, 3, … と並べた場合の濃度は $\aleph_{0}$ 、順序数は ω である。これを並べ替えて 2, 3, …, 1 とした場合、濃度は変わらないが、順序数は ω + 1 になり、ω より大きくなる。

まず基数について見てみます。

あるMMORPGの全ステージの集合をAとします。このMMORPGは仮に75面までしか確認されていないとすると、そのステージ数card(a)は有限であるとは断言できません。仮にステージ数が無限だったとして、 card(A) = $\aleph_{0}$ です。

そして、ステージ数は無限ですが75面以降無限にあるステージを全部すっ飛ばして最終面100面に到達したとします。このときもcard(A) = $\aleph_{0}$ です。

基数は変わりませんでした。一方で、順序数を見てみます。

あるMMORPGの全プレイヤーが強い順に並んでいる集合を(B,<)とします。もしかしたらNPCとか幽霊も参加していたりするかもしれないので無限のプレイヤーがいるとします。このときord(B,<)=ωです。

ここで、最弱だったプレイヤーが無限人を追い抜いて最強になったとします。このときord(B,<)=ω+1となります。

当然、ω < ω+1 です。基数と順序数によって、振る舞いが異なります。

結論

基数(Cardinal Number)によって支配されているMMORPGは順番を無視しても難易度が変わるような事態は起こりません。

しかし順序数(Ordinal Number)によって支配されているMMORPGは順序をひっくり返すことで想像を超える強さを手にしたことになるかもしれないので、なんか結果的に想定外の事態とかが起きる危険性があるので悪の計画とかに利用するなら十分気をつけたほうが良いと思います。たぶん。

参考文献

2017-01-04

【レイティング・ランキングの数理】スプラトゥーンとポケモンのレート計算式を読み解く

ゲーム数学

レイティング・ランキングの数理 ―No.1は誰か？―という本を読んでいます。

f:id:s2terminal:20170104190530j:plain:w240

数年前に買った『Google PageRankの数理』の続編のような立ち位置で、本書はPageRankに限らずより一般的な順位付けの手法を数多く語った本です。

例:Splatoonのウデマエ

まず本題に入る前に、例として『Splatoon』のガチマッチのウデマエについて軽く触れておきます。

計算方法はガチマッチ指南 - スプラトゥーン(Splatoon) for 2ch Wiki*に記載されています。以下にウデマエによる獲得基準ポイントを引用します。

ウデマエ	－	±	＋
Ｃ	+20	+15	+12
Ｂ	+10	+10	+10
Ａ	+10	+10	+10
Ｓ	-	+4	+3

これらにいくつかの要素が加わって実際のポイントが前後するのですが、基本的には 自分の所属ランク帯にウデマエの変動値が依存する ようになっています。

さて、このSplatoonのウデマエ計算式は、他のゲームと比べても結構特殊な物だったようです。では一般的なレーティングとはどのような物なのでしょうか。

『レイティング・ランキングの数理』に紹介のあった手法のひとつ、チェス等の順位付けに使われている 「イロのレーティング(Elo Rating)」 について見てみます。

イロのレーティング

イロレーティング - Wikipedia

プレイヤーi,jのレートをそれぞれ $r_i$ , $r_j$ とおきます。 iとjとの勝負を考えます。

このとき「iがjに勝つ確率 $E_{ij}$ 」を下記で表します。

${ \displaystyle E_{ij} = \frac{1}{1+10^{ -{d_{ij}/400}}} }$ ・・・(1)

ここで $d_{ij} = r_i - r_j$ 、つまりレート差で、高いほどiの方が強いということです。

そしてiとjが対戦した後、下記の計算式でiの新しいレーティングを算出します。

${ \displaystyle r_{new} = r_{old} + K(S - E_{ij}) }$ ・・・(2)

Kは定数で、高ければ高いほどレートの変動が大きくなります。Sはiがjに勝ったら1、負けたらゼロ、引き分けなら1/2とします。つまり勝った回数です。

詳細な仕組みは『レイティング・ランキングの数理』を読むか、Web上の文献だと下記が詳しいと思います。

lfics81.techblog.jp

イロのレーティングは以下の特徴を持ちます。

レートの平均値(初期値)は1,500
レートの差が200ある場合、約76%の確率でレートの高いほうが勝利する

ポケモンのレーティング計算式

最近ポケモンのレーティングバトルをしていたので、このレート計算式を題材として読み解いてみます。

ポケモンXY ORAS データまとめ wiki - 基礎知識より引用

勝利時に加算される値＝ 16 ＋（相手のレート－自分のレート）× 0.04
敗北時に減算される値＝ 16 ＋（自分のレート－相手のレート）× 0.04

つまりレートが同じなら16変動し、レート差25ごとに1増減する。

※小数点以下、切り捨て

※レート差が400以上差がある場合、勝利時に加算される値はゼロ

つまり下記の式となるようです。

勝利時: $r_{new} = r_{old} + 16 + \frac{1}{25}(r_j - r_i)$

敗北時: $r_{new} = r_{old} - 16 - \frac{1}{25}(r_i - r_j)$

これを先程の $S$ と $d_{ij}$ を使うと、下記に書き換えることができます。

${ \displaystyle r_{new} = r_{old} + 32(S - (\frac{1}{800}d_{ij} + \frac{1}{2})) }$

イロレーティングの式のような形に変形することができました。

これを実際に先程のイロレーティングの式(2)にあてはめると、

$K=32$

$E_{ij} = \frac{1}{800}d_{ij} + \frac{1}{2}$ ・・・(3)

となっています。

勝率 $E_{ij}$ の部分が、(1)と(3)とで大きく異なっている事が分かります。

これはイロのレーティングを修正したレート変動を計算しやすくした近似系のようで、Wikipediaによると棋力などのレーティングにも用いられている計算式のようです。

実際、イロのレーティングでレート変動を計算するには対数計算を使う必要があり、とても暗算では求められません。ですが(3)の式でしたら、その場でかんたんに計算することができます。

ここまでをまとめると、下記のようになります。

イロレーティングにおける勝率の計算式

${ \displaystyle E_{ij} = \frac{1}{1+10^{ -{d_{ij}/400}}} }$ ・・・(1)

ポケモンなどで使われている勝率の近似式

${ \displaystyle E_{ij} = \frac{1}{800}d_{ij} + \frac{1}{2} }$ ・・・(3)

イロのレーティングとその近似の比較

さて、この近似はどれくらいイロのレーティングに近いのでしょうか。

カシオ計算機のサイトで f(x)=(1/800)x+1/2、g(x)=1/(1+10^-x/400) として算出しました。

keisan.casio.jp

d	近似	イロ
0	50%	50%
100	62.5%	64.00649998%
200	75%	75.97469266%
300	87.5%	84.90204428%
400	100%	90.90909091%
500	112.5%	94.67597848%

レート差300あたりまでは近い値が出ていますが、400で勝率100%を超えてしまい、非現実的な値となっている事が分かります。

実際のグラフは、下記のサイトだともう少し見やすくなります。

http://ja.numberempire.com/graphingcalculator.php?functions=1%2F(1%2B10%5E(-x%2F400))%2C%20x%2F800%2B1%2F2&xmin=-451&xmax=549&ymin=-0.1&ymax=1.1&var=x

f:id:s2terminal:20170104175128p:plain:w640

x≧400で1.0を突き抜けていることが分かります。

実際に、ポケモンでもレート差400以上ある時には例外措置が取られています。

ゲームにおけるレーティング

このイロのレーティングがどれくらい優れているかはレイティング・ランキングの数理に書かれている通りなので省略します。

ここで、冒頭に挙げたSplatoonのウデマエに話を戻します。

Splatoonのウデマエについて解説された記事がありますので、これらに目を通してみます。

Evaluating Splatoon's Ranking System より引用

nearly 75% of Splatoon players will end up with the rank of A−, A, or A+, with over 36% of players having a rank of A+

※上記はランクS,S+が追加されるアップデートよりも以前のものであり、A+が最高ランクの頃の話です

スプラトゥーンのウデマエ分布に関して - でこすけの日記より引用

勝敗が完全にランダムだと半分以上のプレイヤーがクラスSになります

説明は省きますが、Splatoonのウデマエは特定ランク帯にプレイヤーが偏るようになっているようです。

さて冒頭にて、Splatoonのウデマエ変動の計算方法は他のゲームとは異なる独自のロジックに基づいている事を示しました。実際にイロのレーティングの計算式を見た後であれば、その異質さは一目瞭然だと思います。

つまり「イロのレーティング」は勝率に基づいた客観性のある算出方法であるのに対して、「Splatoonのウデマエ」はどうやら 特定ランク帯に偏るよう意図して作られているらしい 事が見えてきます。

これはどういう事かというと、ある程度は プレイヤースキルに依存せずともランク上昇を味わうことができる 仕組みになっています。乱暴に例えると、プレイヤースキルよりもRPGのレベルのようにプレイ時間の影響を受けやすい指標だということです。また、良くも悪くもウデマエがプレイヤースキルをあまり反映しておらず 実力差の大きいプレイヤーとも結構マッチしやすい仕組みだった ということです。そのようにデザインされたゲームらしい事が分かりました。

おそらくプレイヤースキルを定量化して過度な競争を煽ることを嫌って、このような平和的な仕組みを取り入れているのだと考えます。競技性よりもパーティゲームを重視する、実に任天堂らしい設計だと思います。

まとめ

「イロのレーティング」という手法があり、ポケモンなど多くのゲームや競技のレートはこの方法をもとに算出されている事が分かりました。

一方Splatoonのウデマエは、プレイヤースキルを定量化するという目的よりも、ある意図を持ってゲームデザインのひとつとして設計されたらしい事が分かりました。

参考文献

www.kyoritsu-pub.co.jp

本記事は、本書の第5章「Eloのシステム」のうちほんの数ページを参考にして書かれました。

本書には他にも数々のレイティング・ランキングの手法が紹介され、また前提知識となる数学的な要素が結構省かれているので、見た目以上にボリュームがあります。まるで大学の教科書を思い出します。 (実際、教科書としても使えるよ！と冒頭に書いてありました)

ランキングを作るという、ただそれだけでここまで奥深い内容になるのだと思いました。良い本です。

2015-10-12

Google PageRankベクトルをRubyで求めてみた

数学 IT

『Google PageRankの数理』という本を読んでいます。 www.kyoritsu-pub.co.jp

内容は古いものの、GoogleのSEO順位を定量的に算出するロジックについて解説している貴重な一冊です。楽しいのですが線形代数学の知識を要求されるので、読むのが結構しんどい本でもあります。

PageRankをベクトルで表す

まだ最初の数十ページしか読んでいないのですが、GoogleのPageRankの求め方はこの本の50ページに、下記のように書かれていました。

Google行列GのPageRankベクトルはGの定常ベクトルで、次のものになる。
π = [0.03721, 0.05396, 0.04151, 0.3751, 0.206, 0.2862]
※ Gは既知の6次元正方行列(省略)

「次のものになる」とか言って突然に答えを出しているのですが、この算出方法がよく分かりませんでした。 (そもそも 定常ベクトル なんて単語は記憶に無い)

この定常ベクトルπが実際のPageRankを表しております。 6次元正方行列Gで表される6つのページに対して、最大値「0.3751」を持つ4番目のページが最もPageRankが高く、逆に最低値「0.03721」の1番目が最もPageRankが低いという事になります。

つまりこの 定常ベクトルとやらが肝 なので、求めないと話になりません。

なので実際に求めてみました。

定常ベクトルを求める

まず書籍にある定常ベクトルの定義から、1次方程式の形に変形します。

x を求めたい定常ベクトル、 G をGoogle行列(各ページのリンクとかを表す行列)とすると

$x=xG , xe=1$

$\Leftrightarrow$

$\begin{bmatrix}E-G \end{bmatrix}^{\mathrm{T}}x=0, ex=1$

$\Leftrightarrow$

$\begin{bmatrix} \begin{bmatrix}E-G \end{bmatrix}^{\mathrm{T}} \\ e \end{bmatrix}x= \begin{bmatrix}0 \\ 1 \end{bmatrix}$ ・・・(1)

(TeXとか久しぶりすぎて何も覚えてない…)

(1)の1次方程式を解くメソッドを、Rubyのmatrixライブラリを使うことで以下のように記述します。

require 'matrix'

# 引数google: Google行列
def page_rank(google)
  dimension = google.row_size

  ans = (Matrix.identity(dimension) - google).transpose
  ans = Matrix.rows(ans.to_a.push([].fill(1,0,dimension)))
  ans = ans.lup.solve([].fill(0,0,dimension).push(1))
  ans.covector.minor(0,1,0,dimension).round(5)
end

# 書籍に記載されている実際のGoogle行列G
g = Matrix[
[1,28,28,1,1,1],
[10,10,10,10,10,10],
[19,19,1,1,19,1],
[1,1,1,1,28,28],
[1,1,1,28,1,28],
[1,1,1,55,1,1]
].map{|i| i.to_f / 60 } 

p page_rank(g)
#=> Matrix[[0.03721, 0.05396, 0.04151, 0.37508, 0.206, 0.28625]]

数学的にもプログラム的にももう少しやりようがあるような気がしますが、目的の出力は得られました。これで無事にPageRankが求められたようです。

backstage

合唱音源の新着情報の舞台裏

MMORPGに見る順序数(Ordinal)と基数(Cardinal)

自然数のもつ意味

基数(Cardinal Number)

順序数(Ordinal Number)

基数と順序数の違い

無限集合における基数と順序数

結論

参考文献

【レイティング・ランキングの数理】スプラトゥーンとポケモンのレート計算式を読み解く

例:Splatoonのウデマエ

イロのレーティング

ポケモンのレーティング計算式

イロレーティングにおける勝率の計算式

ポケモンなどで使われている勝率の近似式

イロのレーティングとその近似の比較

ゲームにおけるレーティング

まとめ

参考文献

Google PageRankベクトルをRubyで求めてみた

PageRankをベクトルで表す

定常ベクトルを求める