問題タブ [chess]

コンピュータのチェス プログラムでチェス盤を表すには、どのようなデータ構造を使用しますか?

私はチェス サーバーとチェス用の 1 つまたは複数のクライアントを作成するつもりであり、プログラミング言語に依存しない方法で、チェスのルール (たとえば、ゲームの状態に基づいて許容される動き、ゲームが完了したときのルール) を記述したいと考えています。一部のチェス ルール (キング キャスリング、アンパッサン、3 回以上の繰り返しの動きに基づく引き分けなど) はボード レイアウトだけでなく、動きの履歴にも基づいているため、これは少し注意が必要です。

形式は次のようにすることをお勧めします。

• 原文
• 人間が読める
• 標準に基づく (YAML、XML など)
• さまざまな言語で簡単に解析可能

しかし、適切な解決策を得るために、これらのいずれかを喜んで犠牲にします。

私の主な質問は次のとおりです。データ形式からこのような複雑な状態で動作するような複雑なアルゴリズムを構築するにはどうすればよいですか?

フォローアップの質問は次のとおりです。出発点として機能する同様の方法で解決された同様の問題の例を提供できますか?

編集：明確にするためのリクエストに応えて、Pythonで記述されたサーバー、C＃で記述された1つのクライアント、およびJavaで記述された別のクライアントがあると考えてください。場所ごとにルール（駒の移動の許容範囲、チェックの状況など）を明記するのは避けたいと思います。これらのルールは、言語に依存しない方法で一度指定することをお勧めします。

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

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

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

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

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

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

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

私はJavaを使用しており、チェスエンジンをコーディングしています。

バイト内の最初の1ビットのインデックスと最後の1ビットのインデックスを見つけようとしています。

私は現在JavaでLong.numberOfTrailingZeros（）（またはそのようなもの）を使用しており、バイトを除いてその機能をエミュレートしたいと思います。

それは次のようなものでしょうか：

もしそうなら、bitCountを比較的効率的に実装するにはどうすればよいでしょうか。私は良い説明を気にしません、ただ私にコードを与えないでください。

ターンベースのゲーム サーバーを RESTful API としてどのようにモデル化しますか? たとえば、チェス サーバーでは、同じ API の別のクライアントに対してチェスのゲームをプレイできます。他のクライアントとゲームを要求して交渉する何らかの方法と、ゲームの個々の動きをプレイする何らかの方法が必要になります。

これは REST (RESTful) API の良い候補ですか? それとも、これを別の方法でモデル化する必要がありますか?

私は自分のスキルを磨くための演習として、またそれが楽しいという理由から、C# で Windows アプリのチェス ゲームをコーディングしています。プレーヤーがオプションを選択して、クリックされたときにピースが合法的に移動できる正方形を強調表示できるようにする機能を含めました。CustomControl はチェス盤のレンダリングを処理し、正方形も強調表示します。

プレーヤーがピースを新しい正方形にドラッグし始めるまで、すべてが計画どおりに機能します。マウスを動かした瞬間、ハイライトが消えます。Paint イベントが発生し、ボード自体が再描画されると思われます。また、ハイライトは最初のボード レイアウトの一部ではないため、描画されません。

私がやりたいことは、ピースが目的の正方形にドロップされるまで、正方形が強調表示されたままになることです。これを達成することは可能ですか？任意の提案をいただければ幸いです。

疑似コード:

速度の数パーセントを与える小さな最適化には興味がありません。私は、アルファベータ検索の最も重要なヒューリスティックに興味があります。そして、評価関数の最も重要なコンポーネント。

私は、(改善/コードサイズ) 比率が最大のアルゴリズムに特に興味があります。（ない（改善/複雑さ））。

ありがとう。

PS Killer ムーブ ヒューリスティックは完璧な例です。実装が簡単で強力です。ヒューリスティックのデータベースは複雑すぎます。

良い動きをして他のプレイヤーに勝つことを学習するチェス エンジンをプログラムしたいと考えています。チェス盤の表現と、すべての可能な動きを出力する関数を既にコーディングしました。したがって、ボードの特定の状況がどれほど良いかを示す評価関数だけが必要です。したがって、与えられた位置を評価する人工ニューラル ネットワークを使用したいと思います。出力は数値でなければなりません。値が高いほど、白人プレーヤーの位置が高くなります。

私のアプローチは、385 個のニューロンのネットワークを構築することです。ボードには 6 つのユニークなチェスの駒と 64 のフィールドがあります。したがって、すべてのフィールドに対して 6 つのニューロン (すべてのピースに 1 つ) を使用します。白い駒がある場合、入力値は 1 です。黒い駒がある場合、値は -1 です。そのフィールドにそのようなピースがない場合、値は 0 になります。さらに、プレイヤーが移動するためのニューロンが 1 つ必要です。白のターンの場合、入力値は 1 であり、黒のターンの場合、値は -1 です。

ニューラルネットワークの構成はなかなか良いと思います。しかし、主要な部分が欠けています: このニューラル ネットワークをコーディング言語 (Delphi など) に実装するにはどうすればよいでしょうか? 各ニューロンの重みは最初は同じであるべきだと思います。試合の結果に応じて、重みを調整する必要があります。しかし、どのように？2 人のコンピューター プレイヤー (両方とも私のエンジンを使用) を対戦させるべきだと思います。白が勝った場合、黒は重みが良くないというフィードバックを受け取ります。

したがって、ニューラル ネットワークをコーディング言語に実装するのを手伝っていただければ幸いです (Delphi が最適ですが、それ以外の場合は疑似コードです)。前もって感謝します！

まともな .Net チェス エンジンを探しています。既存の優れたチェスがある場合、.Net に移植するのに適した候補に関する推奨事項はありますか?