-2

Big O表記のチェスでチェックメイトを決定するために、グラフ検索アルゴリズムがどのように複雑になるのか疑問に思いました。

4

4 に答える 4

2

両側に8個。最初の動きはポーンだけで16の可能性があり、騎士だけでさらに4つの可能性があり、2番目の映画は同じ量です。この後、可能性のリストは計算できないレベルに成長します。

世界で最高のチェスエンジンは、「最も可能性の高い」グラフ検索を使用します。

このウィキペディアの記事は非常に役立ちます：http：//en.wikipedia.org/wiki/Game_complexity

「Allisはまた、ゲームツリーの複雑さを少なくとも10123と推定しました。これは、平均分岐係数35と平均ゲーム長80に基づいています」。比較として、観測可能な宇宙の原子数は、よく比較されますが、4×1079から1081の間と推定されます。」

于 2012-09-20T03:33:06.510 に答える
1

答えは、アルゴリズムが残りのチェスの駒（N）によって可能なすべての動きを解決するということです。複雑さがO（N）（線形）になると、各ピースを通過するだけなので。

于 2012-09-22T07:33:42.487 に答える
0

王はせいぜい8つの動きを持っています。そして、それぞれの動きの後に王が脅かされているかどうかを確認するのに一定の時間がかかります。加えて、王が置かれたままでいる（そして別のピースが動く）場合。だから、それは一定の時間です。

于 2012-09-20T03:33:42.687 に答える
0

特定のボードにチェックメイトが含まれているかどうかを確認したいだけの場合は、次のようにすることができます。

  1. あなたの王が移動できる（王の）正方形のセットを決定します（すべての方向に8-あなた自身のピースが占めるフィールド-フィールドの境界）
  2. すべての敵の駒を繰り返し、攻撃する正方形を決定します。それらのマス目がキングセットにある場合は、それらを取り除きます。ブール値を維持して、王が攻撃を受けているかどうかを示します。
  3. キングセットが空になり、キングが攻撃を受けている場合はチェックメイト

ピースの数が影響するので、n個の任意のサイズのボードがある場合は問題になります。その場合、別のピースが攻撃をブロックする可能性があるため、ある位置を攻撃するかどうかをすべてのピースでチェックすることがボトルネックになります。単純な実装では、2次時間でそれを行うことができます。セット内のピースの位置を維持し、add（）とcontains（）用に最適化することで、これをnの線形に下げることができます（ただし、ボードのサイズもこれに影響します）。したがって、線形の複雑さは実現可能だと思います。

于 2012-09-20T09:24:52.620 に答える