リサーチ

マジック:ザ・ギャザリングは、世界で最も難しいゲームとして正式に認められています。

マジック: ギャザリングは魔法使いが呪文を唱えたり、クリーチャーを召喚したり、魔法のオブジェクトを使って相手を倒したりするカードゲームです。ゲーム中、2人以上のプレイヤーが異なる力で60枚のカードのデッキを集める。デッキはゲームが進むにつれて作成される2万枚以上のカードのプールから集められます。 Magic:The GatheringはDungeonsやDragonsのようなロールプレイングファンタジーゲームに似ていますが、他のカードゲームよりもはるかに多くのカードとより複雑なルールがあります。

これは興味深い質問につながります。 MTGは、他の実際のゲーム(つまり、理論上のゲームではなく、実際にゲームが行われているゲーム)と比較すると、どれほど難しいのでしょうか。すぐに予約をする、ここでの複雑さはゲームプレイを理解することの複雑さではなく、ゲームの深さと多様性としての複雑さを意味します。

マジック:ザ・ギャザリングはどれほど複雑ですか?もっと難しい

答えはアレックスチャーチル、独立の仕事によって与えられました英国ケンブリッジのボードゲーム研究者兼デザイナー、ジョージア工科大学のSte​​lla Biederman、ペンシルバニア大学のAustin Herrick。

彼のチームは計算の複雑さを測定しましたゲーム、それはそれがコンピュータかチューリング機械で遊ぶことができるようにそれをコード化しました。 「この設計は、マジック:ザ・ギャザリングが文学で知られている最も計算上困難な現実世界のゲームであることを証明した」と科学者たちは述べた。

しかし、最初に、少し背景があります。 コンピュータサイエンスにおける非常に重要な仕事は、原則として問題を解決できるかどうかを判断することです。例えば、2つの数が比較的単純であるかどうか(言い換えれば、それらの最大公約数は1より大きくなければならない)かどうかを決めることは、有限数の明確に定義されたステップで完了でき、したがって計算できるタスクです。

チェスの通常のゲームでは、あなたもすることができますコンピューティングは、白人が勝利戦略を持っているかどうかに対する解決策を見つけます。プロセスは、ホワイトが勝つことができるかどうか見るために可能な限りの動きのシーケンスをすべてチェックすることを含みます。

しかし、これらの問題はどちらも計算可能ですが、それらを解決するために必要なリソースは大きく異なります。

これが計算量の概念が現れるところです。これは問題解決に必要なリソースに基づいたランキングです。

この場合、2つの判断数は比較的単純で、入力数の多項式関数に比例するいくつかのステップで見つけることができます。入力値がxの場合、多項式関数の最も重要なメンバーはCx ^ nの形式になります。ここで、Cとnは定数です。これはクラスPで、多項式時間を意味します。

それどころか、チェスの問題は解決されなければならない力ずくで、必要なステップ数は入力データの指数関数に比例して増加します。入力がxの場合、指数関数の最も重要な要素はCn ^ xです。ここで、Cとnは定数です。ここで我々はより複雑なEXP、または指数関数的時間のカテゴリーを扱っています。

さらに、アルゴリズムがないタスクと同様に、複雑さの異なる他のさまざまなカテゴリがあります。それらは計算不可能と呼ばれます。

どのカテゴリの難しさを調べますゲームは簡単ではありません。現実世界のほとんどのゲームでは、競技場の大きさなど、難易度に制限があります。そしてこれはそれらの多くを複雑さの点で自明にします。 「実際のゲームのアルゴリズム理論の分野における研究の大部分は、実際のバージョンではなく、主に人気のあるゲームの一般化に関するものでした」とChurchillは述べました。

したがって、ほんのわずかな実際のゲームだけが自明ではない複雑さを持っています。これらは「棒」(または「点と正方形」)、ジェンガとテトリスを含みます。

科学者の仕事は、マジックが次のように示していることを示しています。 集まりはこれら3つよりもはるかに複雑です。計数方法は、原則として簡単です。 Churchillと彼の会社は、各カードの長所と特性をエンコード可能な一連のステップに変換することから始めました。

彼らはそれから2人のプレーヤーの間でゲームをしました。チューリングマシンによる。そして最後に、彼らはどのプレイヤーが勝利戦略を持っているかを決定することがコンピュータサイエンスで知られている「ストップ問題」と同等であることを示しました。

これは次のことを決定する問題です。特定の入力ジョブを持つコンピュータプログラムまたは永遠に動作します。 1936年、Alan Turingはどのアルゴリズムも答えを決定できないことを証明しました。言い換えれば、このタスクは計算できません。

したがって、Churchillの結果は次のことを示しています。マジック:ギャザリングゲームの結果は計り知れません。 「これが、勝利戦略の定義を計算できない実際のゲームがあることを示す最初の結果です」と科学者たちは言います。これはゲーム理論の重要な基本的問題を提起する興味深い論文です。例えば、Churchillと共著者は、主要な形式的ゲーム理論はあらゆるゲームが計算可能であるべきであることを示唆していると言います。マジック:ザ・ギャザリングは、ゲームをモデル化するときにコンピュータ科学者が通常行う仮定を満たしていません。

あなたはこのゲームをプレイしましたか? Telegramでのチャットで教えてください。

EU向けのFacebook通知! FBコメントを表示および投稿するには、ログインする必要があります。