1990 年代のゲーム開発者にとって、それは簡単なことではありませんでした。彼らのコンピューティング能力は非常に限られていたため、可能な限り効率的にコードを作成する必要がありました。たとえば、一般に Quake 3 として知られる一人称シューティング ゲームの Quake III Arena を考えてみましょう。プレイヤーは 3 次元の世界をナビゲートするため、プログラマーは 3D グラフィックスと関連する計算を処理する最も賢い方法を見つける必要がありました。

Quake 3 は 1999 年にリリースされ、当時最高のコンピューター ゲームの 1 つと考えられています。これは業界に永続的な影響を与えました。この功績はストーリーのせいではなく、Quake 3 が最初のマルチプレイヤー一人称シューティング ゲームの 1 つだったからです。プレーヤーはネットワーク ケーブルまたはインターネット経由でコンピューターに接続し、リアルタイムで対戦できます。

ゲームのコードも印象に残りました。これには、専門家を驚かせ、科学者の好奇心を呼び起こす非常に効率的なアルゴリズムが含まれています。

科学ジャーナリズムの支援について

この記事を気に入っていただけた場合は、受賞歴のあるジャーナリズムをサポートすることを検討してください。 購読 購読を購入することで、今日の世界を形作る発見やアイデアに関するインパクトのあるストーリーを未来に確実に届けることができます。

奇妙なコード

3 次元空間内のオブジェクト、キャラクター、または他のプレイヤーの方向を数学的に検出するには、基本的に方向を示す矢印であるベクトルを作成します。ベクトルを比較するには、同じ長さに正規化する必要があるため、それに応じてベクトルをスケーリングする必要があります。ここで、数値の平方根で割る逆平方根という難しい計算が必要になります。

電卓を使わずに 26 の逆平方根を計算するように頼んだら、おそらくしばらくの間行き詰まるでしょう。正直に言って、私もそうでしょう。1990 年代には、コンピューターも同じ課題に直面する必要がありました。数値を処理することはできますが、このプロセスには多くの処理能力が必要であり、計算に時間がかかる可能性があります。 1 つの問題は平方根そのものでした。 2つ目はパーティションでした。そのため、Quake 3 のプログラマーは、この逆平方根を見つけるためのより良い方法を探しました。そして実際、彼らのソースコードは簡単な解決策を明らかにしました。

興味深いことに、開発者はそのトリックを決して宣伝しませんでした。 Quake 3 のソースコードがオープンソースになっていなかったら、その手法は永久に隠されたままになっていたでしょう。しかし、発売されると、好奇心旺盛な愛好家たちが注目しました。逆平方根を計算するためのコード スニペットを発見したとき、彼らは当惑しました。理解するのが難しく、開発者のコ​​メントは特に役に立ちませんでした。しかし、徐々に人々はコードがどのように機能するかを知るようになりました。

現在、プログラム コードを段階的に説明するチュートリアルが数多くあります。これらのウォークスルーでは、C プログラミング言語の特別な機能を利用します。たとえば、数値はメモリ アドレスと呼ばれるコンピュータの場所に保存され、その後操作されます。これは、除算などの計算量の多い演算を回避する賢い方法です。トロント大学のコンピューター科学者、ダニエル・ハリントン氏はプレゼンテーションで、「店舗で何かに誤ったラベルを貼り付けて従業員を説得するようなものだと考えてほしい。だがここで愚かなのは履歴書だ」と述べた。

数学的な観点から見ると、コードは簡単に説明できます。逆平方根を求めるには、まず解を推測し (これは通常は間違っています)、次に所定の手順に従ってその推測を改良します。このようにして、徐々により良い解決策に到達します。

これらはどれも前例のないものでも、新しいものでもありません。ただし、印象的なのは、結果が実際のソリューションに十分に近づくまでに、通常、プロセスを 4 ～ 5 回繰り返す必要があることです。このプロセスには大量の計算能力が必要です。 Quake 3 では、初期値、つまりプロセスの最初のステップで使用される推定数値が非常に巧妙に選択されているため、必要な最適化ステップは 1 つだけです。

魔法の数字を探しています

最適化ステップは、いわゆるニュートン・ラフソン法に対応しており、関数が複数の反復にわたって出力 0 または関数のルートを生成する値を推定します。ゼロだけではなく逆平方根を計算したいので、これは最初は直観に反しているように思えるかもしれません。しかし、プログラマはトリックを使用します。つまり、推定される関数を、初期推定値と実際の結果の差として定義します。ニュートン・ラフソン法により、誤差は徐々に小さくなり、正確な解に近づきます。

これを考慮するために、2.5 の逆平方根を計算したいと想像してください。アルゴリズムは固定推定値から開始します。3.1 を仮定します。実際の解との差を判断するには、開始値を 2 乗し、1 を結果で割ります。 3.1 が実際には 2.5 の逆平方根である場合、1 を 3.1 の 2 乗で割ると 2.5 が得られます。実際の結果は 0.1 です。したがって、その差は 2.4 になります。

ニュートン・ラフソン法では、反復ごとにこの差が減少するため、徐々に正確な値に近づいていきます。信頼できる結果を得るには、通常、このようなステップが 4 ～ 5 回必要です。それでも、Quake 3 ではイテレーションが大幅に削減されました。

重要なのは、ニュートン ステップの開始値がどのように計算されるかです。このメソッドのアルゴリズムは基本的に 3 つのステップで動作します。

1. 逆平方根を計算する指定された数値を、対応するメモリ アドレス (コンピューターに保存されているデータ内の場所) に変換します。

2. この値は半分になり、16 進値 0x5f3759df から減算されます。これはニュートン法の初期値です。

3. 次に、ニュートンステップを実行します。

秘密の文字列 0x5f3759df は特に謎に満ちており、それ以来、コンピューター サイエンスの歴史に「魔法の数字」として名を残しています。これが、逆平方根の近似解を得るのに 1 回の反復だけで済み、最大誤差が 0.175 パーセントになるのはこのためです。

プログラム コードがオープン ソースとして利用可能になるとすぐに、専門家はその魔法の数字の起源について困惑しました。 2003 年に発行された技術論文の中で、コンピューター科学者のクリス ローモントは次のように書いています。「この値はどこから来て、なぜコードは機能するのでしょうか?」

16 進数 0x5f3759df は、10 進表記の 1,597,463,007 に相当します。プログラム コードを個々のステップに分解することで、ローモントは、いくつかの計算で 1,597,463,007 を達成できることに気付きました。この計算を簡素化するために、関連する計算を表す方法を次に示します。

価値 ³⁄₂2²³ 127 は数値表現を C に変換したものです。しかし、0.0450465 の起源はそれほど明確ではありません。

ローモントは、さまざまな入力に対してどの値が最適な結果をもたらすかを数学的に調査しました。言い換えれば、どの初期値が逆平方根に最もよく近似し、したがって誤差が最小になるでしょうか?彼は 1,597,465,647 という値に到達しました。これはおよそ次のとおりです。

これは、Quake 3 ソース コードにある値と一致します。結果は、そこで見つかった値に非常に近いです。

ローモント氏が自分の結果を元の結果と比較したとき、彼は驚きました。ニュートン・ラフソン法の 2 段階では、計算された定数が実際にうまく機能し、考えられる最大誤差は元のコードの値よりも小さくなりました。 Lomont 氏は、「しかし驚くべきことに、1 回のニュートン反復の後、最大の相対誤差が生じます。」と書いています。 「ここでもまた疑問が生じます。元のコード定数はどのようにして取得されたのでしょうか?」

彼の計算では、コンピューター科学者は、ニュートン ステップ数を無視して、理論的に可能な限り最良の値が得られる数値のみを考慮しました。より良い定数を求めて、ラモントは計算を繰り返し、単一のニュートン位相に対して可能な限り最良の解を得るために計算を最適化しました。彼は 1,597,463,174 という値に到達しました。これはおよそ次のとおりです。

この結果を実際のテストに適用したところ、実際には、Quake 3 コードのマジック ナンバーよりわずかに良い結果が得られました。

Lomont は論文の中で、どちらの定数も近似値であるため、実際にはどちらを選択してもよいと述べています。さらに彼は、定数の原作者に会って、どのようにして魔法の数字に辿り着いたのかを知りたいと述べた。

オンライン コミュニティは、この謎の人物の継続的な捜索を開始しました。この取り組みに特に熱心に取り組んだのは、最初に Quake 3 の主任開発者 John Carmack に連絡を取ったコンピューター科学者の Rhys Somefelt です。しかし、カーマック氏はこの断片を誰がコード化したのか確信が持てず、推測しかできませんでした。

ソンムフェルトは 1990 年代の最も著名な開発者数名に連絡を取り、それぞれが自分の著者であることを主張することなく、他の著者候補を提案しました。 1980 年代後半にコンピューター メーカーのアーデント コンピューターに勤務していたグレッグ ウォルシュ氏が、逆平方根アルゴリズムにマジック ナンバーを導入したようです。その後、他の数名を通じて Quake 3 アルゴリズムに侵入しました。しかし、マジックナンバーがどのように正確に決定されたのかは、今日に至るまで不明のままです。

これは特に満足のいく結論ではありません。それでも、Quake 3 コードのストーリー、または少なくとも逆平方根を中心に展開する部分は非常に興味深いものです。当時、効率的なソフトウェア プログラミングにどれだけの労力と知力が費やされていたかは驚くべきことですが、今日のコンピューティング能力のせいでこの傾向はしばしば見落とされています。

この記事は最初に掲載されました ウィッセンシャフトのスペクトル そして許可を得て転載しました。