1

チェスのゲームの動きを教えて、誰が勝つかを宣言した場合、勝者が実際に勝つかどうかを多項式時間でチェックできないのはなぜですか? これは、私の理解ではNPの問題になります。

4

2 に答える 2

2

まず、8x8 のフィールドに 32 ピースで配置できるポジションの数は限られています。ポーンが他のピースに変換されることを考慮し、そのような利用可能なポジションも含める必要があります。もちろん、その中にはチェスのルールに従って到達できない位置もありますが、それは問題ではありません。重要なことは、限界があるということです。この制限を単純に MaxPositions と名付けましょう。

任意の位置について、次のようにツリーを作成しましょう。

  • 指定された位置がルートです。
  • 任意のポジション (チェスの正当なポジションかどうか) を子として追加します。
  • これらの子のいずれかについて、任意の位置を子として再度追加します。
  • ツリーが MaxPositions の深さに達するまで、この方法を続けます。

もう 1 レベルの深みが必要かどうか、アイデア (証明?) に必要かどうかを考えるのにうんざりしていますが、追加してみましょう。重要なことは、このように構築されたツリーには制限があるということです。

次のステップ: このツリーのうち、正当なチェスの手によってルートから到達できないサブツリーをすべて削除します。ツリー全体で到達できない位置がなくなるまで、残りの子、孫などについてこの手順を繰り返します。ツリーが制限されているため、ステップ数を制限する必要があります。

次に、幅優先検索を実行し、以前に見つかった場合は任意のノードを葉にします。そのようにマークする必要があります(!; 候補を描画しますか?)。どのメイトポジションでも同じです。

強制交尾があるかどうかを調べる方法は？どのサブ ツリーでも、自分の番になった場合、強制交配につながる子が少なくとも 1 人はいる必要があります。対戦相手の動きである場合、配偶者につながるすべての子には孫が必要です。もちろん、これは再帰的に適用されます。ただし、ツリーが限られているため、このアルゴリズム全体も限られています。

[感知]、このアルゴリズム全体は制限されています! 全体を制限する定数があります。つまり、制限は信じられないほど高い (そして最新のハードウェアが処理できる範囲をはるかに超えている) ものの、これは制限です (私に計算を依頼しないでください...)。つまり、私たちの問題は実際にはO(1) です!!!

チェッカーも同じです、行く、...

これまでのところ、これは強制合致に適用されます。最良の動きは何ですか？まず、強制交配を見つけることができるかどうかを確認します。もしそうなら、私たちは最善の手を見つけました。複数ある場合は、必要な移動数が最も少ないものを選択します (複数ある場合もあります...)。

そのような強制交配がない場合は、何らかの方法で「最良の」交配を測定する必要があります。おそらく、交配するために利用可能な継承の数を数えます。測定に関するその他の提案はありますか? このツリーを上から下に操作している限り、私たちはまだ限界があります。繰り返しますが、私たちはO(1)です。

今、私たちは何を逃しましたか？コメントのリンクをもう一度見てください。彼らは NxN チェッカーについて話しているのです! 作者はフィールドの大きさがバラバラ！

それでは、ツリーをどのように構築したかを振り返ってください。ツリーがフィールドのサイズに応じて指数関数的に成長することは明らかだと思います (自分で証明してみてください...)。

この答えは、問題が EXP(TIME) であることの証明ではないことをよく知っています。実際、それはまったく答えではないことを認めます。しかし、私が説明したことは、問題の複雑さの非常に良いイメージ/印象を与えると思います. そして、誰もより良い答えを提供しない限り、これは何もないよりはましだとあえて主張します...

あなたのコメントを考慮して、補遺：

ウィキペディアを参照させてください。実際には、リンクのように多項式ではなく、指数時間で他の問題を変換するだけで十分です。変換を適用して結果の問題を解決しても指数関数のままです。しかし、正確な定義についてはよくわかりません...

EXP 完全であることが既にわかっている問題については、これを示すだけで十分です (他の問題をこの問題に変換し、次にチェスの問題に変換しても、両方の変換が指数関数的である場合は、指数関数のままです)。

どうやら、JM Robson が NxN チェッカーでこれを行う方法を見つけたようです。おそらくロブソンのアルゴリズムを変更するだけで、一般化されたチェスでも可能であるに違いありません。古典的な 8x8 チェスでは不可能だと思いますが...

O(1) は、一般的なチェスではなく、古典的なチェスにのみ適用されます。しかし、NPにないと仮定するのは後者です！実際、この補遺に対する私の回答には、欠けている証明が 1 つあります。制限されたツリーのサイズ (N が修正されている場合) は、N の増加に伴って指数関数的に増加するよりも速くは増加しません (したがって、回答は実際には不完全です!)。

そして、一般化されたチェスが NP にないことを証明するには、非決定論的チューリング マシンで問題を解決するための多項式アルゴリズムが存在しないことを証明する必要があります。これはまた開いたままにしておきますが、私の答えはさらに完全ではありません...

于 2016-05-29T23:54:28.030 に答える