algorithm - チェスに最適なアルゴリズムはありますか?

Question

私は最近、チェスコンピューターの可能性について、プログラマーではない人と話し合っていました。私は理論に精通していませんが、十分に知っていると思います。

私は、チェスで常に勝つか膠着状態になる決定論的チューリングマシンは存在し得ないと主張しました。player1/2 の手のすべての組み合わせの空間全体を検索したとしても、コンピューターが各ステップで決定する 1 つの手はヒューリスティックに基づいていると思います。ヒューリスティックに基づいているため、対戦相手が実行できるすべての動きに必ずしも勝つとは限りません。

それどころか、私の友人は、「間違い」の動きをしなければ、コンピューターは常に勝つか引き分けになると考えていました (ただし、それを定義しますか?)。しかし、CS を経験したプログラマーとして、賢明な対戦相手が与えられた場合、あなたの良い選択でさえ、最終的には「間違い」を犯す可能性があることを知っています。すべてを知っていても、次の一手はヒューリスティックに一致する貪欲です。

ほとんどのチェスコンピューターは、可能なエンドゲームを進行中のゲームと一致させようとします。これは、基本的に動的プログラミングのトレースバックです。繰り返しますが、問題のエンドゲームは回避できます。

編集:うーん...ここでいくつかの羽を波立たせたように見えます. それは良い。

もう一度考えてみると、チェスのような有限のゲームを解くのに理論上の問題はないように思えます。チェスはチェッカーよりも少し複雑で、必ずしも駒を数的に使い果たすのではなく、メイトによって勝利が決まると私は主張します。私の最初の主張はおそらく間違っていますが、まだ十分に (正式に) 証明されていないことを指摘したと思います。

私の思考実験は、ツリー内のブランチが取られるたびに、アルゴリズム (または記憶されたパス) が、対戦相手の移動の可能性のあるブランチに対して (交尾することなく) メイトへのパスを見つけなければならないということだったと思います。議論の後、私たちが夢見ることができるよりも多くのメモリがあれば、これらすべてのパスを見つけることができるので、それを購入します。

score 107 · Accepted Answer

「私は、チェスで常に勝ったり行き詰まったりする決定論的チューリングマシンは存在し得ないと主張しました。」

あなたは完全に正しくありません。そんな機械もあるだろう。問題は、検索しなければならない状態空間の巨大さです。それは有限であり、ただ本当に大きいだけです。

これが、チェスがヒューリスティックに頼る理由です。状態空間が大きすぎます (ただし有限です)。列挙するだけでも、ましてや可能なすべてのゲームのすべてのコースに沿ったすべての完璧な動きを検索することは、非常に大きな検索問題になります。

オープニングは、「強い」ポジションを与えるゲーム中盤に到達するようにスクリプト化されています。既知の結果ではありません。ピースが少ないエンドゲームでさえ、最善の次の動きを決定するために列挙するのは困難です. 技術的には有限です。しかし、選択肢の数は膨大です。2ルーク+キングでさえ、22の可能な次の動きのようなものがあります. そして、交尾するのに 6 回の移動が必要な場合、12,855,002,631,049,216 回の移動を見ていることになります。

オープニングの動きで計算を行います。最初の動きは 20 程度しかありませんが、2 番目の動きは 30 ほどあります。つまり、3 番目の動きまでに、360,000 の代替ゲームステートを見ていることになります。

しかし、チェスのゲームは (技術的に) 有限です。巨大だが有限。完璧な情報があります。定義された開始状態と終了状態があり、コイントスやサイコロのロールはありません。

score 73 · Accepted Answer

チェスについて実際に発見されたことについて、私はほとんど何も知りません。しかし、数学者としての私の推論は次のとおりです。

まず、白が先に行くことを覚えておかなければなりません。黒にアドバンテージを与えるかもしれません。

ここで、黒が常に勝つ/膠着状態になる完璧な戦略が存在しないと仮定します。これは、黒が何をしようとも、白が勝つために従うことができる戦略があることを意味します。ちょっと待ってください - これは、白の完璧な戦略があることを意味します!

これは、2 人のプレイヤーのうち少なくとも 1 人が、そのプレイヤーが常に勝ったり引き分けたりできる完璧な戦略を持っていることを示しています。

次の 3 つの可能性しかありません。

白は完璧にプレーすれば常に勝つことができる
黒は完璧にプレーすれば常に勝つことができる
1 人のプレイヤーが完璧にプレイすれば、勝つか引き分けます (両方のプレイヤーが完璧にプレイすると、常に膠着状態になります)。

しかし、これらのうちどれが実際に正しいかは、決してわかりません。

質問への答えはイエスです。チェスには、少なくとも 2 人のプレーヤーのうちの 1 人にとって完璧なアルゴリズムがなければなりません。

score 29 · Accepted Answer

チェッカーゲームでは、プログラムが常にゲームに勝ったり引き分けたりできることが証明されています。つまり、一方のプレイヤーが他方のプレイヤーに負けを強いる動きの選択肢はありません。

研究者たちは、5000億の可能なチェッカーの位置を調べるのにほぼ20年を費やしました.ちなみに、これはまだチェスの位置の数の非常に小さな割合です. チェッカーの取り組みには、研究チームがチェッカーの経験則をソフトウェアにプログラムし、動きを成功または失敗として分類するのを支援したトッププレーヤーが含まれていました。その後、研究者は、毎日平均 50 台のコンピューターでプログラムを実行させました。ある日、プログラムは 200 台のマシンで実行されました。研究者は進行状況を監視し、それに応じてプログラムを微調整しました。実際、チヌークは 1994 年にチェッカーの世界選手権で人間を破って優勝しました。

はい、あなたはチェスを解くことができます。いいえ、すぐには解けません。

score 15 · Accepted Answer

これはコンピューターに関する質問ではなく、チェスのゲームに関する質問です。

問題は、ゲームに決して負けないためのフェイルセーフ戦略が存在するかということです。そのような戦略が存在する場合、すべてを知っているコンピューターは常にそれを使用でき、もはやヒューリスティックではありません。

たとえば、ゲームの三目並べは通常、ヒューリスティックに基づいてプレイされます。しかし、フェイルセーフ戦略が存在します。対戦相手が何を動かしても、最初から正しく行えば、常にゲームに負けないようにする方法を見つけることができます。

したがって、チェスにもそのような戦略が存在するかどうかを証明する必要があります。基本的には同じですが、可能な動きのスペースが大幅に大きくなっています。

score 13 · Accepted Answer

私は非常に遅くこのスレッドに来ましたが、あなたはすでにいくつかの問題に気付いています。しかし、元マスターで元プロのチェスプログラマーとして、私はいくつかの有用な事実と数字を追加できると考えました。チェスの複雑さを測定する方法はいくつかあります。

チェスの総ゲーム数は約 10^(10^50) です。その数は想像を絶するほど多い。
40 手以下のチェスゲームの数は、約 10^40 です。それは今でも信じられないほどの数です。
可能なチェスの位置の数は約 10^46 です。
完全なチェスの探索木 (シャノン数) は、平均分岐係数 35、平均ゲーム時間 80 に基づいて、約 10^123 です。
比較のために、観測可能な宇宙の原子の数は、一般的に約 10^80 と推定されています。
6ピース以下のエンドゲームはすべて照合・解決済みです。

私の結論: チェスは理論的には解決可能ですが、それを行うための資金、動機、計算能力、または記憶域はありません。

score 9 · Accepted Answer

実際、いくつかのゲームは解決されています。Tic-Tac-Toe は、常に勝ったり引き分けたりする AI を構築するための非常に簡単なものです。最近、Connect 4 も解決されました (そして、2 番目のプレイヤーにとって不公平であることが示されました。完璧なプレイは彼を失う原因となるからです)。

しかし、チェスは解決されておらず、公正なゲームであるという証拠 (つまり、完璧なプレーが引き分けになるかどうか) も証明されていないと思います。ただし、理論的な観点から厳密に言えば、チェスには有限数の可能な駒の配置があります。したがって、検索スペースは有限です (ただし、信じられないほど大きい)。したがって、完全に機能する決定論的チューリングマシンは存在します。しかし、それが構築できるかどうかは別の問題です。

score 7 · Accepted Answer

実際、両方のプレイヤーが順序付けのない無限のゲームで勝利戦略を持つことは可能です。ただし、チェスは整然としています。実際、50手ルールのため、ゲームが持つことができる手の数には上限があり、したがって、チェスの可能なゲームは有限数しかありません(正確に解決するために列挙することができます..理論的には、少なくとも：）

score 7 · Accepted Answer

平均的な 1000 ドルのデスクトップは、2040 年までにわずか 5 秒でチェッカーを解けるようになります (5x10^20 計算)。

この速度でも、これらのコンピューター 100 台でチェスを解くのに約 6.34 x 10^19年かかります。まだ実現不可能です。程遠い。

2080 年頃には、平均的なデスクトップで 1 秒あたり約 10^45 の計算が行われるようになります。1 台のコンピューターは、約 27.7 時間でチェスを解く計算能力を備えています。過去 30 年間のようにコンピューティング能力が成長し続ける限り、2080 年までには確実に実現します。

2090 年までに、1000 ドルのデスクトップでチェスを約 1 秒で解くのに十分な計算能力が存在するようになるでしょう...その日までには、チェスは完全に些細なものになるでしょう。

チェッカーが 2007 年に解かれ、1 秒で解ける計算能力が約 33 ～ 35 年遅れるとすれば、チェスは 2055 ～ 2057 年のどこかで解けるようになると概算できます。おそらく、より多くの計算能力が利用できるようになってから (45 年後にはそうなるでしょう)、このようなプロジェクトにより多くの時間を割けるようになるでしょう。ただ、早くて2050年、遅くて2060年と思います。

2060 年には、100 台の平均的なデスクトップでチェスを解くのに 3.17 x 10^10 年かかります。私はベンチマークとして 1000 ドルのコンピューターを使用していますが、価格/性能比も向上しているため、より大規模なシステムやスーパーコンピューターもおそらく利用可能になるでしょう。また、それらの計算能力は桁違いに速いペースで増加します。現在、スーパーコンピューターが 1 秒あたり 2.33 x 10^15 の計算を実行でき、1000 ドルのコンピューターが約 2 x 10^9 の計算を実行できるとします。比較すると、10 年前の差は 10^6 ではなく 10^5 でした。2060 年までに、桁違いの差はおそらく 10^12 になり、これでさえ予想よりも速く拡大する可能性があります。

これの多くは、私たち人間がチェスを解決する意欲を持っているかどうかに依存しますが、計算能力により、この時期にチェスを実行できるようになります (私たちのペースが続く限り)。

別の注意点として、Tic-Tac-Toe のゲームははるかに単純ですが、2,653,002 の計算が可能です (オープンボードを使用)。Tic-Tac-Toe を約 2.5 (毎秒 100 万回の計算) 秒で解く計算能力は、1990 年に達成されました。

さかのぼって、1955 年には、コンピューターは三目並べを約 1 か月 (1 秒あたり 1 回の計算) で解く能力を持っていました。繰り返しますが、これは 1000 ドルでコンピュータにパッケージ化できた場合に得られるものに基づいており (1000 ドルのデスクトップは明らかに 1955 年には存在しませんでした)、このコンピュータは Tic-Tac-Toe の解決に専念していたはずです.... Tic-Tac-Toe がコンピューターによって「解決された」と見なされた日付はないと思いますが、計算には費用がかかり、この目的には使用されませんでした。実際の計算能力よりも遅れていることを確認してください。

また、45 年間で 1000 ドルの価値が現在の約 4 分の 1 になることを考慮に入れると、このようなプロジェクトにより多くの資金を投じることができますが、計算能力は引き続き安くなります。

score 6 · Accepted Answer

あなたの議論の結末は、現代のチェスプログラムが現在動作している方法によってサポートされています。そのように動作するのは、決定論的に動作するチェスプログラムをコーディングするにはリソースが多すぎるためです。必ずしもそのように機能するとは限りません。チェスがいつか解ける可能性はありますし、そうなった場合、コンピューターによって解かれる可能性があります。

score 5 · Accepted Answer

この質問の内容であるゲーム理論から、答えは「はい」です。チェスは完璧にプレイできます。ゲームスペースは既知/予測可能であり、そうです、孫の量子コンピューターがあれば、おそらくすべてのヒューリスティックを排除できます。

今日では、完璧な三目並べマシンを任意のスクリプト言語で作成でき、リアルタイムで完全に再生できます。

Othelloは、現在のコンピューターで簡単に完璧にプレイできるもう1つのゲームですが、マシンのメモリとCPUには少し助けが必要です。

チェスは理論的には可能ですが、実際には不可能です（2008年）

i-Goはトリッキーで、可能性の空間は宇宙の原子の量を超えているため、完璧なi-Goマシンを作成するには時間がかかる場合があります。

score 5 · Accepted Answer

チェスはマトリックスゲームの例であり、定義上、最適な結果が得られます（ナッシュ均衡を考えてください）。プレーヤー1と2がそれぞれ最適な動きをした場合、常に特定の結果に到達します（それが勝ち負けであるかどうかはまだ不明です）。

score 5 · Accepted Answer

記録のために、チェッカーで勝ったり引き分けたりできるコンピューターがあります。チェスでも同じことができるかどうかはわかりません。移動回数はかなり多いです。また、ピースは前後だけでなく、どの方向にも移動できるため、状況が変わります。確かではありませんが、チェスは決定論的ですが、コンピューターが現在妥当な時間内にすべての動きを決定するには、可能な動きが多すぎると思います。

score 5 · Accepted Answer

私はあなたが死んでいると思います。Deep Blue や Deep Thought などのマシンは、多数の事前定義されたゲームと、それらのゲームの終わりにツリーを解析する巧妙なアルゴリズムでプログラムされています。もちろん、これは極端な単純化です。ゲームの過程で、コンピューターに「勝つ」チャンスは常にあります。これは、コンピューターに最適ではない動きを強制するような動きをすることを意味します (それが何であれ)。コンピューターが移動の制限時間までに最適なパスを見つけられない場合、望ましくないパスの 1 つを選択することで間違いを犯す可能性があります。

実際の機械学習、または遺伝的プログラミング/進化的アルゴリズムを使用する別のクラスのチェスプログラムがあります。一部のプログラムは進化しており、ニューラルネットワークなどを使用して意思決定を行っています。このような場合、コンピュータは「ミス」を犯すかもしれないが、それでも勝利に終わるのではないかと想像します。

このタイプの GP については、Blondie24という魅力的な本があります。チェッカーの話ですが、チェスにも当てはまります。

score 5 · Accepted Answer

1970 年代のチェスプログラマーとして、私はこれについてはっきりと意見を持っています。私が約10年前に書いたことは、今日でも基本的に真実です。

「未完の作業とチェスプログラマーへの挑戦」

当時、私はチェスを適切に行えば、伝統的に解決できると思っていました。

Checkers は最近解決されましたが (Yay, University of Alberta, Canada!!!)、それは事実上総当たりで行われました。伝統的にチェスをするためには、より賢くなければなりません。

もちろん、量子コンピューティングが現実のものにならない限り。もしそうなら、チェスは三目並べと同じくらい簡単に解けるでしょう。

1970 年代初頭、Scientific American に短いパロディがあり、私の注意を引きました。それはチェスのゲームがロシアのチェスコンピューターによって解決されたという発表でした。双方の完璧なプレイで勝利を確実にする白の完璧な手が 1 つあると判断されました。その手は次のとおりです。1. a4!

score 3 · Accepted Answer

それは完全に解決可能です。

10^50 の奇数の位置があります。私の推測では、各位置には、格納するために最低 64 ラウンドバイトが必要です (各正方形には、2 つの所属ビット、3 つのピースビットがあります)。それらが照合されると、チェックメイトである位置を識別でき、位置を比較して関係を形成し、どの位置が大きな結果ツリーの他の位置につながるかを示します。

次に、そのようなものが存在する場合、プログラムは最下位の片側のみのチェックメイトルートを見つけるだけで済みます。いずれにせよ、チェスは最初の段落の終わりでかなり単純に解決されました。

score 3 · Accepted Answer

ここでの多くの回答は、重要なゲーム理論のポイントを示しています。

チェスは、ゲームの状態に関する完全な情報を備えた有限で決定論的なゲームです。
有限のゲームを解決し、完璧な戦略を特定することができます
しかし、チェスは十分に大きいので、力ずくの方法で完全に解決することはできません。

しかし、これらの観察は重要な実用的なポイントを見逃しています:無敵のマシンを作成するために完全なゲームを完全に解決する必要はありません.

実際、可能な状態空間のごく一部を検索することなく、無敵のチェスマシン (つまり、決して負けず、常に勝ちまたは引き分けを強制する) を作成できる可能性が非常に高くなります。

たとえば、次の手法はすべて、必要な検索スペースを大幅に削減します。

Alpha/Beta やMTD-fなどのツリーの剪定手法は、すでに検索スペースを大幅に削減しています
証明可能な勝利位置。多くのエンディングがこのカテゴリに分類されます。たとえば、KR 対 K を検索する必要はありません。これは実績のある勝利です。いくつかの作業を行うことで、より多くの保証された勝利を証明することができます。
ほぼ確実な勝利 - ばかげたミスのない「十分な」プレー (たとえば ELO 2200+ について?) の場合、多くのチェスのポジションはほぼ確実な勝利です。あなたのプログラムがそのようなポジションを強制でき、ポジションのアドバンテージを検出するのに十分なヒューリスティックを備えている場合、100% の確率で勝つか、少なくとも引き分けになると安全に想定できます。
ツリー検索ヒューリスティック - 十分なパターン認識があれば、関連する「興味深い」動きのサブセットにすばやく集中できます。これは人間のグランドマスターのプレイ方法なので、明らかに悪い戦略ではありません.....そして、パターン認識アルゴリズムは常に改善されています。
リスク評価 - ポジションの「リスク」のより良い概念は、結果がより不確実な状況に計算能力を集中させることにより、はるかに効果的な検索を可能にします (これは静止検索の自然な拡張です) 。

上記の手法を適切に組み合わせれば、「無敵」のチェスマシンを作成できると断言できます。私たちはおそらく、現在のテクノロジーとそう遠く離れていません。

このマシンに勝てないことを証明するのはほぼ確実に難しいことに注意してください。それはおそらくライマン仮説のようなものになるでしょう - 私たちはそれが完全に機能し、決して負けたことがないことを示す経験的結果 (それ自体に対する数十億回の引き分けを含む) を示すことをかなり確信していますが、実際にはそれを行う能力はありません。証明する。

「完璧」に関する追加の注意事項:

ゲーム理論的な意味でマシンを「完璧」と表現しないように気をつけています。

勝利の組み合わせがどれほど複雑であっても、勝利を強制できるあらゆる状況で常に勝利します。これを完全に計算するのが非常に難しい場合、勝敗の境界に状況があります。
対戦相手のプレイの潜在的な不完全性に関する入手可能なすべての情報を活用する。たとえば、対戦相手が貪欲すぎる可能性があると推測し、対戦相手にミスを犯させる可能性が高いという理由で、通常よりもわずかに弱いラインを故意にプレイする。不完全な対戦相手に対しては、対戦相手が強制的な勝利をおそらく見つけられず、自分自身が勝つ可能性が高くなると推定した場合、実際に負けるのが最適な場合があります。

完璧であること (特に、不完全で未知の対戦相手が与えられた場合) は、単に無敵であることよりもはるかに難しい問題です。

score 2 · Accepted Answer

player1 / 2の動きのすべての組み合わせの空間全体を検索する場合、コンピューターが各ステップで決定する1つの動きは、ヒューリスティックに基づいています。

そこには2つの競合するアイデアがあります。1つは、考えられるすべての動きを検索することであり、もう1つは、ヒューリスティックに基づいて決定することです。ヒューリスティックは、適切な推測を行うためのシステムです。あなたがすべての可能な動きを探しているなら、あなたはもはや推測していません。

score 2 · Accepted Answer

あなたの思考実験には 2 つの誤りがあります。

チューリングマシンが「制限」されていない場合 (メモリ、速度など)、ヒューリスティックを使用する必要はありませんが、最終的な状態 (勝ち、負け、引き分け) を評価することはできます。完璧なゲームを見つけるには、Minimax アルゴリズム ( http://en.wikipedia.org/wiki/Minimaxを参照) を使用して各プレイヤーの最適な動きを計算するだけでよく、これにより 1 つまたは複数の最適なゲームが導き出されます。
また、使用されるヒューリスティックの複雑さに制限はありません。完全なゲームを計算できれば、そこから完全なヒューリスティックを計算する方法もあります。必要に応じて、チェスの位置を「私がこの状況にある場合、S の場合、私の最善の動きは M です」というようにマップする関数にすぎません。

他の人がすでに指摘したように、これは 3 つの可能な結果で終わります: 白は強制的に勝つことができ、黒は強制的に勝つことができ、そのうちの 1 つは引き分けを強制することができます。

完全なチェッカーゲームの結果は、既に「計算」されています。人類が以前に自滅することがなければ、コンピューターが十分なメモリと速度を備えた進化を遂げたときに、チェスの計算も行われるようになるでしょう。または、量子コンピューターがいくつかあります... または、誰か (研究者、チェスの専門家、天才) が、ゲームの複雑さを大幅に軽減するいくつかのアルゴリズムを見つけるまで. 例を挙げると、1 から 1000 までのすべての数の合計は? 1+2+3+4+5...+999+1000 を計算するか、単純に次のように計算できます。N*(N+1)/2 with N = 1000; 結果 = 500500. 想像してみてください。その式について知らない、数学的帰納法について知らない、数値の掛け算や足し算の方法さえ知らない、と想像してみてください。このゲームの複雑さを最終的に軽減する現在未知のアルゴリズムが存在する可能性があり、現在のコンピューターで最適な動きを計算するのに 5 分しかかかりません。もう少し時間があれば、ペンと紙を使って、あるいはあなたの心の中でさえ、それを人間として推定することさえ可能かもしれません.

ですから、簡単な答えは次のとおりです。人類が十分に長く生き残るなら、それは時間の問題です!

score 2 · Accepted Answer

「ゲーム理論の父」エルンスト・フリードリッヒ・フェルディナンド・ツェルメロの研究を参照しているジョン・マッカリーのこの記事を見つけました。それは次の結論を引き出します。

チェスでは、白が強制的に勝利するか、黒が強制的に勝利するか、または双方が少なくとも引き分けを強制することができます。

論理は私には聞こえます。

score 2 · Accepted Answer

「チェスに完璧なアルゴリズムはありますか?」

はいあります。常に勝つのは白のためかもしれません。たぶん、黒が常に勝つためです。たぶん、少なくとも両方が常に結ぶことです。どちらかはわかりませんし、今後もわかりませんが、確かに存在します。

こちらもご覧ください

神のアルゴリズム

score 1 · Accepted Answer

これは少し難しいのは承知していますが、ここに 5 セント相当のお金を入れなければなりません。コンピューター、または人間が参加しているすべてのチェスゲームを、勝利または膠着状態で終了させることは可能です。

ただし、これを達成するには、考えられるすべての動きや反応などを、考えられるすべてのゲームの結果まで正確に把握し、これを視覚化する、またはこの情報を分析する簡単な方法を考えなければなりません。それは常に枝分かれするマインドマップです。

中央のノードがゲームの開始点になります。各ノードからの各枝は動きを象徴し、それぞれが兄弟の動きとは異なります。この邸宅でそれを提示するには、特に紙でこれを行っている場合は、多くのリソースが必要になります. コンピューターでは、ブランチを元に戻さない限り、非常に多くの繰り返しの動きがあるため、これには数百テラバイトのデータが必要になる可能性があります。

ただし、そのようなデータを記憶することは、不可能ではないにしても、信じがたいことです。コンピュータに、(最大で) 8 つの瞬時に可能な手から取り出す最適な手を認識させることは可能ですが、もっともらしくはありません...そのコンピュータは、その手を超えたすべての分岐を処理できる必要があるため、結論に至るまで、勝利または膠着状態に至るすべての結論を数えてから、負けた結論に対してその数の勝利した結論に基づいて行動します。これには、Terrabytes またはそれ以上のデータを処理できる RAM が必要です! そして、今日の技術では、そのようなコンピューターは、世界で最も裕福な 5 人の男性および/または女性の銀行残高よりも多くを必要とするでしょう!

ですから、いろいろ考えた結果、できるかもしれませんが、一人ではできませんでした。そのようなタスクには、チェスだけでなく、科学とコンピューター技術の分野で、今日生きている最も優秀な頭脳の 30 人が必要です。超大型コンピューター...少なくとも1世紀は存在できなかった. それは行われます！この生涯ではありません。

score 1 · Accepted Answer

状態空間のサイズが原因で解を期待できないという主張には、私は 99.9% しか納得していません。

確かに、10^50 はありえないほど大きな数です。状態空間のサイズを n としましょう。

可能な限り長いゲームでの手数の限界は? すべてのゲームは有限回の移動で終了するため、そのような境界が存在し、それを m と呼びます。

初期状態から、O(m) 空間で n 回の動きをすべて列挙することはできませんか? 確かに、O(n) 時間はかかりますが、宇宙のサイズからの議論は、それを直接解決するものではありません。O(m) スペースはそれほど多くないかもしれません。O(m) 空間の場合、このトラバーサル中に、トラバースしているパスに沿った状態の継続が、EitherMayWin、EitherMayForceDraw、WhiteMayWin、WhiteMayWinOrForceDraw、BlackMayWin、または BlackMayWinOrForceDraw につながるかどうかも追跡できませんか? (誰のターンであるかに応じてラティスがあり、ラティスミートを使用してトラバーサルの履歴の各状態に注釈を付けます。)

私が何かを見逃していない限り、それはチェスがどのカテゴリに分類されるかを判断するための O(n) 時間 / O(m) 空間アルゴリズムです。ウィキペディアでは、宇宙の年齢は約 10^60 プランク倍と推定されています。宇宙論の議論に入ることなく、熱/寒さ/宇宙の死の前にそれくらいの時間が残っていると推測しましょう. つまり、プランクの 10^10 倍ごと、つまり 10^-34 秒ごとに 1 つの移動を評価する必要があります。これは信じられないほど短い時間です (これまでに観測された最短時間よりも約 16 桁も短くなっています)。楽観的に言えば、現在または予見されている非量子 P は、NP 技術の適切なサブセットであり、評価したいと期待できる最先端技術で実行されている、非常に優れた実装です (一歩前進、結果の状態を中間状態または 3 つの最終状態の 1 つとして分類します) は、100 MHz のレートで (10^-8 秒ごとに 1 回) 状態になります。このアルゴリズムは非常に並列化可能であるため、結果を収集する機能と合わせて、10 の 26 乗のコンピューター、または私の体のすべての原子に対して約 1 台のコンピューターが必要になります。

力ずくの解決策には、常にわずかな希望があると思います。運が良ければ、白の可能性のある最初の動きの 1 つだけを調査する際に、平均よりもはるかに低いファンアウトを持つものと、白が常に勝つか、または勝つか引き分けるものを選択します。

また、チェスの定義をいくらか縮小し、道徳的に同じゲームであることを皆に納得させることも期待できます. 引き分けの前にポジションを 3 回繰り返す必要が本当にあるのでしょうか? 逃げる側に50手で逃げる能力を発揮させる必要があるのか？アンパッサンルールの一体何が起こっているのか、誰かが理解していますか? ;) もっと深刻なことに、プレーヤーがチェックを逃れるためだけに移動したり、膠着状態がアンパッサンキャプチャである場合に、(引き分けや負けではなく) 強制的に移動させる必要があるでしょうか? 希望する非クイーンの昇格が即時のチェックまたはチェックメイトにつながらない場合、ポーンが昇格できるピースの選択を制限できますか?

また、ゲーム後半の状態とその可能性のある結果の大規模なデータベースへの各コンピューターのハッシュベースのアクセスをどの程度許可するか (既存のハードウェアと既存のエンドゲームデータベースでは比較的実現可能である可能性があります) が、早期の検索を削減するのにどの程度役立つかについても確信が持てません。明らかに、O(n) ストレージなしで関数全体をメモすることはできませんが、大きな整数を選択して、考えられる (または簡単に証明できないと思いますが) 終了状態のそれぞれから逆方向に列挙する多くのエンドゲームをメモすることができます。

score 0 · Accepted Answer

解決できるかもしれませんが、気になることがあります。ツリー全体をトラバースできたとしても、対戦相手の次の動きを予測する方法はまだありません。常に相手の状態に基づいて次の手を動かし、「最善の」動きを可能にする必要があります。次に、次の状態に基づいて、もう一度実行します。したがって、対戦相手が特定の方法で動く場合、最適な動きが最適である可能性があります。対戦相手の一部の動きについては、最後の動きが最適ではなかった可能性があります。

すべてのステップで「完璧な」動きがどのようにあり得るのか、私にはわかりません。

そのためには、対戦相手の次の動き（三目並べのように）に関係なく、[現在のゲームの]すべての状態に勝利につながるツリー内のパスが必要です。それを理解する時間。

score -2 · Accepted Answer

もちろん、ボード上のピースの組み合わせは 10 の 50 乗しかありません。それを念頭に置いて、すべてのコンピベーションでプレイするには、10 を 50 乗する必要があります (繰り返しを含むと、その数に 3 を掛けます)。つまり、チェスでは、10 の 100 乗未満の手数があります。チェックメイトにつながるものを選ぶだけで、準備完了です

score -3 · Accepted Answer

64 ビットの数学 (= チェス盤) とビット単位の演算子 (= 次の可能な手) だけが必要です。とても簡単です。ブルートフォースは通常、最適な方法を見つけます。もちろん、すべての位置に対応する普遍的なアルゴリズムはありません。実際には、計算も時間制限があり、タイムアウトすると停止します。優れたチェスプログラムとは、重いコード (パス、2 倍のポーンなど) を意味します。小さなコードはそれほど強力ではありません。データベースを開いて終了させると、処理時間が節約されます。これは、ある種の前処理されたデータです。デバイス、つまり、OS、スレッドの可能性、環境、ハードウェアが要件を定義します。プログラミング言語は重要です。とにかく開発過程が面白い。

algorithm - チェスに最適なアルゴリズムはありますか?

27 に答える 27

こちらもご覧ください

Related

Reference