解決したゲーム

解決されたゲームとは、両方のプレイヤーが完璧にプレイすると仮定して、どの位置からでも結果（勝ち、負け、または引き分け）を正しく予測できるゲームのことです。この概念は通常、抽象戦略ゲーム、特に完全な情報があり偶然の要素がないゲームに適用されます。このようなゲームを解くには、組み合わせゲーム理論やコンピューターの支援が必要になる場合があります。

概要

2人用ゲームはいくつかのレベルで解くことができる: ^[1]^[2]

超弱溶液

両側で完璧なプレイが行われた場合に、最初のプレイヤーが最初の位置から勝つか、負けるか、引き分けになるかを証明します ()。これは、完璧なプレイの詳細を実際に決定する必要がない非構成的証明(戦略を盗む議論を含む可能性あり) になる場合があります。

弱い解決策

ゲームの開始時から、対戦相手のあらゆるプレイに対して、一方のプレイヤーの勝利、またはどちらかのプレイヤーの引き分けを確実にするアルゴリズムを提供します。

強力なソリューション

一方または両方の側で不完全なプレイがすでに発生している場合でも、どの位置からでも両方のプレーヤーに完璧なプレイを生成できるアルゴリズムを提供します。

その名前にもかかわらず、多くのゲーム理論家は「超弱い」証明が最も奥深く、最も興味深く、最も価値があると考えています。「超弱い」証明では、学者はゲームの抽象的な特性について推論し、完璧なプレイが実現された場合にこれらの特性が特定の結果につながることを示す必要があります。^{[引用が必要]}

対照的に、「強力な」証明は、多くの場合、力ずくで進められます。つまり、コンピューターを使用してゲームツリーを徹底的に検索し、完璧なプレイが実現された場合に何が起こるかを調べます。その結果得られる証明は、盤上のあらゆる可能な位置に対する最適な戦略を提供します。ただし、これらの証明は、一部のゲームが引き分けで解決でき、他の一見非常に似ているゲームが勝ちで解決できる理由をより深く理解するのにはあまり役立ちません。

有限の数のポジションを持つ 2 人ゲームのルールが与えられれば、ゲームツリーを徹底的にトラバースするミニマックスアルゴリズムをいつでも簡単に構築できます。ただし、多くの非自明なゲームでは、このようなアルゴリズムは特定のポジションでの動きを生成するために実行不可能な時間を必要とするため、既存のハードウェアでアルゴリズムを妥当な時間内に実行できない限り、ゲームは弱くまたは強く解決されたとは見なされません。多くのアルゴリズムは、事前に生成された巨大なデータベースに依存しており、実質的にそれ以上のものではありません。

強力な解法の簡単な例として、三目並べのゲームは、完璧なプレイをすれば両方のプレイヤーが引き分けになる（手動で結果を決定できる）ため、簡単に解くことができます。また、ニムのようなゲームも、組み合わせゲーム理論を使用した厳密な分析が可能です。

ゲームが解けるかどうかは、必ずしも人間がプレイして面白いかどうかと同じではありません。強く解かれたゲームであっても、その解法が複雑すぎて記憶できない場合は、依然として面白いことがあります。逆に、弱く解かれたゲームは、勝利戦略が覚えられるほど単純であれば魅力を失う可能性があります (例: Maharajah and the Sepoys )。非常に弱い解法 (例:十分に大きなボードでの ChompまたはHex ) は、一般にプレイアビリティに影響を与えません。

完璧なプレー

ゲーム理論において、完璧なプレイとは、対戦相手の反応にかかわらず、そのプレイヤーにとって最良の結果につながるプレイヤーの行動または戦略のことである。ゲームにおける完璧なプレイは、ゲームが解かれたときにわかる。^[1]ゲームのルールに基づいて、すべての可能な最終局面を評価できる（勝ち、負け、引き分けとして）。後ろ向き推論によって、最終局面ではない局面を、1手離れた局面と同一であり、その手を持つプレイヤーにとって最も価値がある局面として再帰的に評価することができる。したがって、局面間の遷移は、動いているプレイヤーにとってより良い評価をもたらすことは決してなく、ある局面における完璧な手は、同様に評価される局面間の遷移となる。例えば、引き分けの局面にいる完璧なプレイヤーは、常に引き分けまたは勝ちとなり、負けることはない。同じ結果になる選択肢が複数ある場合、完璧なプレイは、良い結果につながる最速の方法、または悪い結果につながる最遅の方法と見なされることがある。

完璧なプレイは、対戦相手の戦略に関係なく、最高の最小期待結果を保証する戦略として、非完全情報ゲームに一般化できます。たとえば、じゃんけんの完璧な戦略は、各オプションを均等 (1/3) の確率でランダムに選択することです。この例の欠点は、この戦略では対戦相手の最適でない戦略を決して利用しないため、この戦略の期待結果がどの戦略に対しても常に最小期待結果に等しくなることです。

ゲームの最適な戦略は（まだ）わかっていないかもしれませんが、ゲームをプレイするコンピュータは、特定の終盤の位置からのゲームの解（終盤テーブルベースの形式）から恩恵を受ける可能性があり、これにより、ゲームのある時点以降は完璧にプレイできるようになります。コンピュータチェスプログラムは、これを実行することでよく知られています。