2012年2月28日火曜日

『確率』は如何に作られている・・・?

戦闘シミュ作っていて、改めて

コンピュータで再現される『確率』というのは油断ならないものなんだな・・・

というのを学んだ中途半端イクサー。
今回は・・・どのように『確率』がコンピュータの内部で決まっているのか、
みたいなのをかなり具体的に紹介(?)してみたいな、と。
まぁ、紹介といってもそれ自体がIXAで確率を決めている方法そのものだ、という
事では決してありません。完璧に分かる人はIXAを作った人だけですし、

“一般にこういう風に確率は作られているんだ”

みたいな一般論を。

合成で勝てない人。くじで泣いてばかりの人。
確率詐欺だと思う前に、コンピュータ上での『確率』がどのようにして作られているのかを
知ってみるのは少し慰みになるのではないかなと思います(苦笑)
オリジナルIXA合成&くじ攻略法を考える手助けになればと^^;

◆    ◇    ◆

サイコロを振って出た目、のような完全にランダムな数の事を乱数というのですが、
コンピュータでは完全ランダムはどう頑張っても再現出来ない、みたいな話を前に書きました。
で、コンピュータで作る乱数を疑似乱数と言うのです。
以下で乱数、と言うのは全て疑似乱数を指しています。

疑似乱数には、乱数と比べて決定的に違う特徴があるのです。
それは。

初期状態が同じならば、発生する乱数も全く同じになる

・・・これだけではピンと来ないかもしれないですね。
コンピュータは、「入力が何も無い所から出力を作る」というのが出来ないのです。
何をするにも指示待ちなのがコンピュータ。

①何か、入力にとある数字をいれる。
②すると、その数字をあらかじめ内部で決めているルールに従って変換
③その変換した数字を、『ランダムな数字ですよぉ』と出してくる訳です。

したがって、入力が同じならば、変換するルールは変えようがないんだから
出力も必ず同じなんですね。

代表的な変換ルールの例を1つ簡単に。線形合同法、というやつです。
代表的というか、かなり単純なので軽くて、便利。なのでよく使われているルールです。
他にも沢山の変換ルールが作られ、知られていますが・・・
私も偉そうに言ってはいますがシロウトなので分かりません(笑)

まず、3つのキーとなる数字を決めます。
A, B, Cとしましょう。
これはシステムの内部で定めておくものなので、変更はできません。

これを使って・・・

まず、入力の値をXとすると、得られる出力Yは

Y = ( AX + B ) mod C

と表現されます。

modって何?
平たく言えば、割り算の余り、です。

例えば・・・

A = 5, B = 2, C = 13とすると。

入力Xを3とすると、Yは、

Y = ( 5*3 + 2 ) mod 13 = 17 mod 13 = 4

17÷13 = 1余り4。modは、この余り4を求める演算です^^

で、この4をまたXに入れて、

Y' = ( 5*4 + 2 ) mod 13 = 22 mod 13 = 9

同じように繰り返して、

Y'' = ( 5*9 + 2 ) mod 13 = 47 mod 13 = 8

Y''' = ( 5*8 + 2 ) mod 13 = 42 mod 13 = 3

ここで、3が出てきたという事はX=3となって、最初に戻ってぐるり一周。
つまり、これだと

4 → 9 → 8 → 3 → 4 → 9 → 8 → 3 → 4 ・・・

という出力が得られる。

補足を入れると、1つの数字を入力して、1つの数字だけが出力されるとは
決まっていませんし、一般には“数列”、複数個の数字が出力されることになりますね。
上の例の場合も複数この数字を連鎖的に出力してくれます。
ただし、周期は4。5つ目からは2周目になります。
ちなみに、線形合同法ではどれだけA, B, Cの数字を厳選しても周期は最大でもCまで
しか確保できない事が知られています。誰得な補足w

こうして得られた出力を使って、確率を作る訳ですね^^

例えば。
先頭から10個の数字を取って来てその和を取る

4 + 9 + 8 + 3 + 4 + 9 + 8 + 3 + 4 + 9  =  61

で、この数字よりも合成成功確率が高ければ成功する、みたいな?

適当ですよ? 喩え話です(笑)
こんな感じで確率は作られているとイメージして下さい。
と言う事は・・・

入力に入れる数字は常に変化し続けないといけない

のですな。
じゃないと、出力される結果は常に同じになってしまうから。
いつもX = 3では、いつも出力結果は

4 → 9 → 8 → 3 → 4 → 9 → 8 → 3 → 4 ・・・

で、いつも先頭10個の数字の和は61。
61%よりも低い合成ならば絶対に常に成功しない(笑)
全然ランダムじゃないじゃないか。

入力(後述するが用語でseedという)が一緒なら常に結果は一緒なのだ。
※結果は一緒、と言ってもどう一緒になるのかは乱数列が内部のシステムで実際どう使われているかに依る。

じゃあ、入力に入れる数字をランダムにするために、更にその入力の入力を作って。
乱数のための乱数を作ればいいじゃない。
で、その入力を常に変化させるための入力をまた作って・・・乱数のための乱数、その元になる乱数(ry
以下無限ループですよね??w
ならば、どうやって『常に変化し続ける入力』を用意しているんだ?

良くあるのは、入力に時刻を使うんですね。

現在時刻の秒数を入力に使う

とか決めておけば、1秒毎に入力は変化してくれます。
時間、という常に変化し続ける量そのものをXにしておけば良いではないか。

こうすれば、上の例では、1秒毎にX = 3, 4, 5, 6, ・・・と勝手にXが変化していってくれます。
これで、1秒毎に違う出力が得られる。

この入力の事を、専門用語でシード(seed)と言います。
線形合同法では、最初に決めた『X = 3』がシードに当たりますね。
文字通り、乱数を発生させるための種(seed)です。

と言う事は・・・

秒数が同じ時に作られるランダムな数は一緒なの?

・・・そうなりますね。

疑似乱数では、得られるランダム(に見える)数にはよく見れば周期性がある

のです。この例だと、60で1周してしまう訳ですよねー

秒数ではなく、ミリ秒にすればどうだ。
1000で1周しますね。根本的には同じですw

ちょうど一周するタイミングで全く同じトライをすると・・・
生成されるランダム(に見える)数も全く同じはず。という事は、結果も全く同じになったり・・・
原理的にはあり得る話です。
勿論、もっと複雑な乱数を生成する方法は沢山ありますが。
ゲームだとこういう比較的簡単な方法で『確率』を再現しているのも多いと聞きます。
実際のプログラムでもそんなに厳密な確率を決めなくて良いものならば、線形合同法でかなり実用に足るとは思われます。
勿論、A, B, Cの数はもっとぐちゃぐちゃでしょう。
単純そうに見えても工夫すれば、十分“実用に足るルール”なのです。

IXAは・・・どうなのでしょうねぇ・・・?
ブラウザゲームは、ユーザーのPCに何もインストールする事無く、ブラウザだけで遊べる
のが売りな訳ですよね。
で、ただでも鯖が良く固まったりして負荷対策には色々と苦労していそうなIXA。
複雑な変換ルールであればあるほど、常識的に考えて負荷は大きいでしょう。
ならば・・・こういう線形合同法みたいな、計算量が少なくて軽いもの、それに近いアルゴリズムを使っている可能性は十分にある。。
合戦の報告書で、完全に連撃をピッタリ同着させると稀に着弾順と報告書記載順がおかしくなっている時ありますよね?
と言う事は・・・IXAは1秒単位で大体動いているのかな・・・?
(1秒以下は無視されているような節は他にも多々見受けられる・・・)
と言う事は、seedにもし時刻が設定されている線形合同法ならば、
秒、分、時間、日数あたり、もしくはそれの組み合わせ、演算でseedを作っているのかな・・・
ミリ秒とかなら無理だろうけど、秒以上の粗さならば、
目に見える形でそういう“周期”があってもまぁ分からなくもない・・・

スキル追加合成で、ある特定の位置の候補ばっかり成功する時とかあるもんな・・・
合戦で、スキルが発動調子良い時はとことん発動するし、そうじゃない時はホントに発動しない。
周期的かどうかは知らないけど、その時々でかなり“ゾーン”的なものは感じるよな・・・

※はい、全て私の妄想です。一切客観的事実はありません(笑)

“こういうタイミング、周期でどうにも合成やくじの結果が似ているぞ?”

みたいなルールを掴めたとしたら・・・

世の中に色々と出回っている噂、

くじはどうすれば良いのが引けるか、とか
ランクアップ合成で失敗しにくい方法、とか
追加合成で成功しやすい時、しにくい時とか

こういうのが何かしらの“周期”に関連付けて説明できればそれなりに面白いのかもしれないかな、
とか個人的には思いますね。

最後に。重ね重ね、あくまでシロウトの妄想ですゆえ ( ̄^ ̄)

5 件のコメント:

  1. よく(?)乱数調整ってのがゲームで使われてますよね。
    もし、乱数の周期がわかってしまえばその乱数を調整することによって狙った通りの結果(例えば何時何分何秒に籤引けば必ず天とか必ず合成成功とか)を出すことも可能になるのでしょうかね?
    まぁ実質そこまでやることは不可能なのでしょうができたらって話ですw
    要するに単なる妄想にすぎませんが…
    第一できてしまったら皆がそれをし始めてむちゃめちゃになってしまいそうなww
    運は運として、外れても泣かない覚悟でやるべきですよね、やっぱり。
    だからこそ楽しいってところもあるようなw
    悲しみのほうが多いけど…

    返信削除
    返信
    1. ですね^^
      乱数調整は上の説明で言えばseedを如何に特定するのかという作業ですね。
      seedを特定すれば、そこから発生している出力列は特定できる。
      なので、その出力列によって得られる結果がはっきりと解析できてしまっているならば、今現在のseed状態が分かれば、何をどうやればどんな結果が出るのかは全て予知できてしまう、という・・・
      普通は、そう簡単に周期なんて特定できないようになっているのですが。
      IXAではどうにも・・・確率詐欺だ、なんて言われるほど結構偏りが激しいですよね?
      それに、スキル追加合成で同じ位置の合成候補ばかり成功する事がある、みたいなのは実は私前期に実験して確かめているのです。
      『同一カード合成やったら成功すれば常にS2が付く時間』
      らしきものが存在しているのも確認しちゃってたり^^
      晴信を10枚ちょい集めて、ガンガン同一合成したら剛撃晴信が4,5枚量産出来ちゃったりとかww
      その間、剛撃以外が付いた晴信はいませんでしたよ。
      ・・・どう見ても不自然ですよね、これ。
      内部状態が『もし成功したらS2しかつかない状態』になるようなseedにその時はセットされていた、そのseedの時にはいつもこうなる、
      とか説明が付けられればかなり説得力あるかもな、とか。。
      これの周期が分かってしまえば・・・大変ですよ(笑)

      ・・・という具合に、かなり極端な偏りがある場合はseedがどういう時に成功する、みたいなのは特徴として出てきやすいかも、とか。。
      勿論、運営の方々が確率をある程度いじれるようにしてあるだろうというのも考えられるので
      →くじの説明に、
      『くじの仕様については、ゲームシステムの変更、ゲームバランス、ユーザー数の増減、新たな武将の追加のアップデート内容等を考慮して、ユーザーに告知することなく変更される可能性があるので、予めご了承ください。』とある
      “絞っているかどうか?”みたいな、システムの周期だけでなく外部からの制御もあるかも、と。。
      なのでなかなかそうは単純ではないだろうなぁとは思うのですw

      ……確かに、出来てしまったらゲームシステム崩壊しちゃいますよね(笑)
      必勝法を探そう、というのは裏返して言えば『何と無粋な事をしているんだ』という事ですからね^^;
      あくまでも、一般に“そういう傾向がある”という雑学読み物として見て頂ければ一番いいと思うのです。
      これまで散々数字で考察してきた私が言うのもおかしい話ですけどww

      削除
  2. PC?だけの話としてね、サイコロは1/6『らしい』ということを考え、
    0と1がそれぞれ1兆個ずつ配列aに入っており、シャッフルして交互に2兆回(無限に近い数)取り出したときに、確率が『均等になる』とかでもいいんじゃないかなぁと

    javaのrandomもc++のrandもどういう作りなのかは知らないですが

    返信削除
    返信
    1. 仰る配列のシャッフル、だと・・・
      その1回ごとの取り出し方をどう規定するのかと言う部分がピンポイントで抜き出せば『乱数操作』になるのでしょうか?
      確かに数えきれない程の回数混ぜ合わせればもはやそのビット列はきっちりぐちゃぐちゃになっているように見えると思います。
      ただ・・・それだとかなり負荷はかかるのではないでしょうか?
      1回乱数を作るためにとてつもない計算量が必要となると、なかなか実装するハードルは高いように思われます。
      計算量を無限大に近づけていけば、全てのモノはランダム性を帯びて来る。
      かなり誤解を招きそうな言い方ですが(笑)
      サイコロでもコインの裏表でも、無限回試行を繰り返せばやがてはそれぞれ1/6、1/2に収束する、というのは確率の前提ですしね。。
      上で述べた、入力の入力、それのための入力を・・・というお話に近いものがあります。

      javaのrandomや、c/c++のrand、VBのRandom、VBAのRndは全て線形合同法で実現されているらしいです。
      ググってみれば、例えばc++だと、
      A=214013, B=2531011, C=4294967296
      での線形合同法によりrand関数は作られている、との事です。

      削除
  3. お久しぶりです。

    なにやら、すんごいソフトをつくってしまわれたそうで!!

    それはさておき、今回の記事ですが、たしかに、合成が成功しやすかったり、金で特が乱発されたり、そんな時間帯が存在しますね。同盟員の間でも、私はこの時間帯、とかいうのがあるようです^^

    くじのところの注意書き、もしかしたら、一定のタイミング(メンテナンス)で、基礎数値をかえているのかもしれませんね!!
    過去に、くじからやたら極がでるようになって、メンテでもとにもどされたという例もあるようですし、その可能性が大きいんじゃないかなぁと思ってみたりしました。

    返信削除