c# - C# でチェスのようなゲームを作成するには?

Question

質問があります。次のようなルールを適用するチェスのようなプログラムを書きたいと思います。

• 片側にキングとクイーン、反対側にはキングだけが必要です。
• 最初の面は、可能な限り少ない移動数で 2 番目の面を合致させる必要があります。

このプロジェクトの作り方について、あなたの考えを知りたいです。たとえば、どちらのコードの書き方が簡単か (オブジェクト指向か構造化か...) を知りたいのですが (オブジェクト指向については少し知っています)、そのアルゴリズムの書き方について教えてもらえますか? たとえば、どこからコードを書き始める必要がありますか?

Answer 1

ここでの朗報は、対処する部分が 3 つしかないため、問題の範囲がかなり制限されていることです。ここでは、論理的なパズルを解くほど、実際にはゲームを実装していません。私は次のようにアプローチします：

1. 3 つの部分を簡単な方法で表す方法を考え出します。パズルを解こうとしているだけなので、ここでは (テスト以外では) UI は必要ありません。最も単純な方法は、おそらく 3 つの部分のそれぞれに単純な行、列の位置を設定することです。

2. 以前にオブジェクト指向プログラムを作成したことがない場合は、おそらく手続き型モデルに固執し、表現する必要があるデータの変数を定義するだけで済みます。問題の範囲は小さいので、これで解決できます。OOP の経験があれば、問題を適切に分割できますが、おそらく継承関係は必要ありません。

3. 可能な動きを生成するためのコードを記述し、特定の動きがまったく意味があるかどうかを判断します。正当なキングの動きは、キングをチェックしない動きです。ほとんどのクイーンの移動は許可されますが、敵のキングがクイーンを奪う可能性がある移動も除外する必要があります。

4. 次に、パズルを解くための一連の動きをどのように組み立てるかについての戦略を決定する必要があります。真の最適解 (単に良い解ではなく) を見つける必要がある場合は、力ずくの検索が必要になる場合があります。これは、この問題に対して実行可能である可能性があります。おそらく、深さ優先検索を実行することをお勧めします (これが何を意味するのかわからない場合は、それが最初に調査するトピックです)。考慮。

5. ブルート フォースを機能させることができ、物事を高速化する必要がある場合は、メリットがないことを証明できる動きがあるかどうかを検討してください。その場合は、これらの動きを検索からすぐに除外して、考慮する必要があるブランチの数を節約できます。また、評価関数を最適化するために作業することもできます。何十億もの関数を実行する場合、より高速な評価は非常に有益です。最後に、どのブランチを最初に試すかを評価するためのヒューリスティックを思いつくかもしれません。「良い」解に早く収束できるほど、最適な解を見つけるために考慮する必要があるケースが少なくなります。

---

私が気付いた 1 つの注意点は、敵のキングがチェックメイトを回避しようとしていると仮定すると、問題は大きく異なるということです。単純な深さ優先の刈り込みは、敵のキングをチェックメイトするのに最適な方法で移動できる場合にのみ機能します。敵のキングがチェックメイトを回避しようとしている場合、最適化の目標が矛盾しているため、問題が複雑になります (できるだけ少ない手数で発生させたいのですが、敵のキングはできるだけ長く延期したいと考えています)。可能性の範囲を特徴付けることに限定されます (たとえば、キングが完全に協力的である場合は 3 つの動きが最善のケースであり、キングが完全に回避的である場合は最悪のケースで 8 つの動きが最善です)。

Answer 2

これは、エンドゲーム データベースの最も単純な例です。64^3 = 262144 ポジション未満なので、各ポジションのスコアを簡単に保存できます。この場合、スコアをチェックメイトまでの手数として定義し、勝ちポジションを得ることができます。または描画位置の場合は 255。概要は次のとおりです。

1. すべてのスコアを 255 に設定します。
2. すべてのチェックメイト ポジションを探し、それらを 0 としてスコア付けします。
3. 深さ = 1 に設定します。
4. 描画された位置 (スコア = 255) ごとに、勝った位置への移動が存在するかどうかを確認します (より正確には、対戦相手のすべての移動が負けている位置への移動が存在するかどうかを確認します)。そうであれば、そのスコアを深さに設定します。 .
5. ステップ 4 で新しい位置が見つからない場合は、完了です。
6. 深さを増やして、手順 4 に進みます。

これで、ディスクに保存できる 250k テーブルができました (ゼロから生成するのに何秒もかかる必要はありません)。スペースが重要な場合は、さまざまな方法でスペースを大幅に削減できます。ウィキペディアには、これらすべてに関する素晴らしい記事があります-「Endgame tablebase」を検索してください。

Answer 3

この SO の質問 (チェス AI のプログラミング) を見てください。

その質問に対する答えから、このC# Chess Game Starter Kitは良い出発点になると思いますが、興味深い歴史/情報については、参照されている他の記事も参照してください。

Answer 4

ここのポスターは、Stockfish が良い出発点になることを示唆していますが、C# を求めているのに対し、これは C++ プロジェクトです。

ソリューションは要件によって異なります。「ただ動かすだけ」に興味がある場合は、200 行以上のコードを書かなくてもプロジェクトを完了することができます。オープン ソースの C# プロジェクトを埋め込み、一致するまでの移動回数をエンジンに報告するように依頼することができます。オープン ソース プロジェクトが UCI でサポートされている場合は、次のコマンドで問題が解決します。

go mate x

ここで、x は交尾までの移動回数です。

ただし、自分で考える必要がある場合。効率的なビットボード表現かオブジェクト指向表現かを選択する必要があります。Bitboard は非常に優れた表現であり、非常に高速ですが、プログラミングが困難です。すべてのチェス エンジンはビットボードを使用します。あなたのプロジェクトでは、表現効率はあまり重要ではないので、OO 表現を選択できます。