スクフェスのスコア計算方法の予想をしていたら、浮動小数の深みを見た話 - 「float32では合うのに、float64では合わない計算」
概要
スクフェスのスコア計算方法の予想を多くの方としていた所*1、float32では合うのに、float64では合わない計算に直面しました。
一言で言えば浮動小数誤差なのですが、
ceil(x * 1.1)
という計算において、float64において、特定の10の倍数のみ計算が合わない- float64では計算が合わない場合があるのに、float32では常に計算が合う
- 上記の現象が、スクフェスのスコア計算シミュレーションという実用的な場面で発生している
という面白い側面があります。
この現象の技術的な詳細は、別のブログ記事にて非常に細かく紹介しています。この現象は、計算結果の末尾たった1ビットがずれることで発生していることがわかりました。この1ビットがずれる場合とずれない場合が存在するのですが、その詳細について上記の記事で詳しく説明しています。
この記事では、この現象に辿り着くまでの議論の経緯を、スクフェス的な側面にスポットライトを当てて説明します。
背景
2019年2月20日のスクフェスのアップデートにおいて様々な変更が行われました。その大きなものの一つに、回復特技と判定特技によってタップ時のスコアが増加するようになった、というものがあります。
@magu_maki さんが、下記のtwitterのスレッドにおいて非常に詳細なデータと共に、回復特技のタップスコア計算方法の詳細なデータと共に、スコア計算方法の予想を載せています。
回復の新機能について検証しました。
— まぐお@フライングバード=エリコヌスⅡ世 (@magu_maki) 2019年2月20日
体力が41,43,44の3つのユニット(属性一致、グループ不一致、回復特技のみ)で試したところ、それぞれ2.04%,2.18%,2.25%×ゲージがMAXになった回数分ユニットの属性値が増えるとして計算すると、実測値と全て一致しました。
⇒上昇率は0.5+(体力-19)×0.07と予想! pic.twitter.com/j7xTUzBOdb
このデータと予想は非常に精密で、
- データの数が非常に多い。
- それぞれ体力ゲージのMAX回数やユニット属性値、Perfect/Great判定など様々な状況での観測である。
- それにも関わらず、それらの数多くの実測値を全て言い当て続けている。
という特徴を持っていました。
しかし、この驚くべき精度で次々と実測値が的中される中、たった一つだけ実測値と予想値が合わない観測が発生していました。
応援タップSCOREアップの計算方法はまだ解が見つかっていないけど、とりあえず回復のパラメータアップの方の検証を進め、体力41~54まで判明。なお、応援タップSCOREアップは、SCOREの繰り下げ前の小数にアップ率を掛けて繰り上げると良さそうだけど、1つだけ合わない実測値ががががが… pic.twitter.com/9bsTnL18Nm
— まぐお@フライングバード=エリコヌスⅡ世 (@magu_maki) 2019年2月22日
上記のツイートの3枚目の画像の下側にある、赤枠で囲まれた「-1」のデータがその観測値です。
このデータでは、以前のデータとは違う点が一つありました。それは、タップスコア計算において、「タップスコアアップ」というメドレーフェスティバルのイベント中に発生する「応援」の効果を受けて、通常よりタップスコアが上昇するというものでした。
タップスコアアップは、タップスコアが1.1倍になるという効果を持っているということが広く知られています。@magu_maki さんの計算によると、
- 通常のタップスコア計算後、つまり切り捨て処理などを行った後に、得られたスコアを1.1倍して、その後切り上げをする
という計算を行うと、実測値とほぼ一致することがわかりました。しかし、1つのデータのみこの計算では説明ができていませんでした。
試みられた計算: 10の倍数が関係している?
この現象を説明するために、様々な計算が試みられました。
下記のツイートでは、@magu_makiさんによって、切り上げや切り捨てをするタイミングや、行う対象の数を変更する事が試みられました。
+1とは?
— まぐお@フライングバード=エリコヌスⅡ世 (@magu_maki) 2019年2月22日
他に2通りの計算方法を試したのですがどちらも合わずでした。誤差が出ている箇所のGreatの切捨後のSCOREが820(赤の部分)で1桁目が0なので、その0.1倍が82と整数になり繰り上がらないため902になり、実測値の903と合わないので、その辺り何かヒントにならないですかね? pic.twitter.com/sfMIc2sCiQ
この時点で、
- 「誤差が出ている箇所のGreatの切捨後のSCOREが820(赤の部分)で1桁目が0」で、
- 「その0.1倍が82と整数になり繰り上がらないため902に」なるために「実測値の903と合わない」のではないか?
という事が@magu_makiさんによって予想されます。
深まる謎: 丸め込み誤差のはずなのに、10の倍数でも正しく丸め込まれる場合がある?
また、@siratama_zさんによって、丸め込み誤差を考慮したような下記の方法が試みられました。
すみません、説明が足らなかった上に言ってることが間違っていました。
— siratama (@siratama_z) 2019年2月22日
「タップSCOREアップ×1.1」から「繰上」の計算を、ROUNDUP(x,0)ではなくROUNDDOWN(x+1,0)でやるとうまくいくかなと思ったのですが、ゲージ2の101-200の「97」は実測値とずれていないことを見落としていました。 pic.twitter.com/duvsx9VePe
このような計算を行うことで、10の倍数の時のみ通常の切り上げよりも1だけ大きい出力を得ることができ、820*1.1 → 903という計算が説明できるようになりました。
しかしここで、重要な事が指摘されます。それは、同じ10の倍数であるはずの他のデータでは、元々切り上げが正しく計算できているため、この計算方法ではそちらのデータについては説明ができなくなってしまうことが指摘されます。具体的には、実測値は
- 820*1.1 は820+82+1 = 903と計算されている
- 970*1.1 は970+97 = 1067と計算されている
という不可解な事が起きているのです。
この点は、@magu_makiさんによっても問題として明確に挙げられています。
まさにこの970があることが厄介で、820と同じように1の位が0なのにこちらは合ってるんですよね。何か変えるとこっちが違ってきちゃって…うーむ…🤔
— まぐお@フライングバード=エリコヌスⅡ世 (@magu_maki) 2019年2月22日
この時点で、
- 1.1倍という計算は小数を含む計算なので、入力が10の倍数の時、切り上げ前の結果がちょうど整数になる関係で誤差が発生するのではないか
- 820では切り上げが正しく行われないが、970では正しく行われるようなメカニズムは何か?
という事が明確に意識されていました。つまりこの問題の最も難しい点は、10の倍数の中でも、正しく切り上げが計算される場合がある事を説明するという点でした。
打開策: 「float32では計算が合うのに、float64で計算すると計算が合わない」事がある
ここで@snowharinchan*3によって、下記の事が指摘されます。
わかったかもしれません!実はスクフェスは内部的にfloat64を使っていて、10の倍数であるはずの820を1.1倍した後にもfloat誤差が乗っていて、それを切り上げて誤差が発生するのではないでしょうか?
— レン@凛ちゃん推し (@SnowhaRinchan) 2019年2月23日
このように仮定して、float32の場合とfloat64の場合、そしてまぐおさんの表にある、1.1倍適用前のスコアが820、970の場合で計算すると、なんとfloat64で計算する場合、820だとceilがずれるが970だとずれない、という驚くべき結果が得られましたw pic.twitter.com/Jfkpc4ybrU
— レン@凛ちゃん推し (@SnowhaRinchan) 2019年2月23日
実際、1.1倍適用前のスコアが0から1999までの場合で、float32とfloat64でのceilの結果がずれる場合を全て列挙するとこのようになり、基本的に10の倍数なのですが、940から1280の間に空白があったり、他にも470-640、60-80などにも空白があります。 pic.twitter.com/4QNFvdfTKU
— レン@凛ちゃん推し (@SnowhaRinchan) 2019年2月23日
なので、1.1倍適用前のスコア実測値がここに列挙されているスコアになり、かつ、1.1倍応援が適用された場合、float誤差によってceil関数の計算がずれる、と予測することができます。
— レン@凛ちゃん推し (@SnowhaRinchan) 2019年2月23日
この指摘には二つの大きなポイントがあります。
1つ目は、float64で計算すると、同じ10の倍数でも、820では切り上げの計算が合わないのに、970では合う現象を再現できる事を指摘した点です。つまり、当初予想されていた通りこの現象は浮動小数計算由来の切り上げ誤差だったが、詳しく計算すると、中には計算が合う場合も存在する事を指摘した点です。
しかし、@magu_makiさんのExcelによる検証でも、1.1倍の処理に浮動小数が使われています。にも関わらず、なぜExcelのシートでは現象が再現されなかったのでしょうか?
その答えとなる2つ目のポイントは、float64ではこの現象は発生するのに、float32ではこの現象は発生せず常に切り上げが正しく計算されるという事を指摘した点です。同じ計算をfloat32で行うと同じ不動小数の仲間でも、常に正しく計算が行われました。そして、どうやらExcelではfloat32が使われているらしく(ExcelのVBA環境にて WorkSheetFunction.Ceiling
を用いると、float32における計算結果が再現されることなどから推定)、float32を用いているExcelでは現象が再現できなかったという事がわかりました。
調べてみると、VBAではDouble型を用いてfloat64による計算が可能であることがわかります。VBAで作った関数はExcelから呼べるため、これを使ってfloat64で1.1倍した後に切り上げを行う関数を作成した所、820、970のデータを含め、他のデータも説明が可能になりました。*4
発生する理由:末尾1ビットのみがずれる場合がある
この現象が発生する理由を詳しく追っていくと、float64で計算した場合、末尾の1ビットのみ1になり、切り上げ時に誤差が発生する場合があることが発生原因であることがわかります。
末尾のビットがずれるだけなら、小数計算を厳密に扱えない計算機では普通の事の様に思えますが、面白いのは10の倍数の中でも末尾のビットがずれない場合があるということと、float64ではこれが発生するのに、float32では発生しないということです。
この詳しい原理については、冒頭でも紹介した別の記事にて詳しく説明しています。
ゲーム的なコメント
float64によって切り上げの計算が合わない場合は、全て最終的なスコアの値が本来の値よりも1だけ大きく計算されます。スクフェス的には、ボーナスがタップスコア「アップ」とのみ謳っており、「1.1倍される」とは言っていません。この現象が発生している時も発生していない時も、いずれもボーナスが適用される前よりもスコアが上がっているという事実は変わらないことから、「タップスコアアップ」というボーナスの名称には反していない、と個人的に考えています。
結論、感想
- スクフェスのスコア計算において、「1.1倍した後に切り上げ」という計算において切り上げ誤差が発生していた。誤差が発生した数は常に10の倍数であったが、10の倍数の中でも、誤差が発生しない数が存在し、謎を呼んだ。
- 計算をfloat64で行うことで現象が再現できることがわかった。
- 同時に、float32で行うと再現できないことがわかった。
- float64で計算を行うことで、唯一説明できなかったデータが説明可能になった。
技術的な詳細は、冒頭でも紹介した下記の記事にて記していますが、この切り上げの問題は末尾のたった1ビットの誤差によって発生しています。21世紀である2019年の現在、このようなビットレベルの現象が、実際にiOSやAndroidで配布されているスクフェスというゲームのスコア予想という実用的な場面で発生している事にワクワクを覚えました。
*1:スクフェスの2019年2月のアップデートで変更された新たなスコア計算方法の解析を @magu_maki さんが行っていた所、一つだけ説明できないデータ点が浮上しました。様々な計算方法が試みられましたが、これに対して、私が計算がずれる原因は、浮動小数点由来の誤差ではないかと予想しました。その結果、浮動小数の誤差まで考慮すると、実際に観測されたデータが全て説明できるようになりました。
*2:https://twitter.com/magu_maki/status/1099710995600072704
*3:この記事の著者です