11

私はチェスのゲームを作っていますが、1 つのことを除いて事実上すべてを手に入れました。この問題にどう対処したらよいか困っています。

有効な動きを生成するために私が現在疑似コードで持っているものは次のとおりです: クラス getMoveLocations (チェスのそれらの正方形の1つである場所を定義しました): この場所が境界内にあり、この場所の駒が敵の駒である場合、およびシミュレートされた移動によってボードがチェックされない場合は、この場所を駒が移動できる可能性のある場所に追加します。

これに関する問題は、チェス盤が「チェックされている」かどうかを確認する方法です。私のコードでは、すべての敵の移動位置を収集し、それらの敵の移動位置のいずれかが王の位置と重なるかどうかを確認することにより、チェス盤が「チェック」されていると見なします。

残念ながら、ここから無限ループが始まります。すべての敵の映画の場所を収集するために、各敵の可能な移動場所は、その移動によってチェックされないことを確認する必要があります。敵の位置がどれもチェックされていないことを確認するために、味方の潜在的な移動位置などをすべて収集する必要があります.

機能するアルゴリズムを取得する方法に困惑しています。私のコードは「理論的には」論理的に意味がありますが、実装することはできません。A) すべての正当な動きをチェックする方法を実装するより効率的な方法、または B) この無限ループを修正する方法に興味があります。

4

5 に答える 5

9

サイドがチェックされているかどうかを判断するためのより効率的な方法があります。キングから外側にスキャンして、それを攻撃できるピースを見つけるかどうかを確認します。例えば、キングの位置から、敵のビショップが対角線に沿っているかどうかなどを確認します。移動リストを生成する必要はまったくないので、再帰は必要ありません。ここにいくつかの擬似コードがあります:

function leftInCheck(board, sideToCheck) {

   // one of the four rays for bishop/queen attacks
   d := 0
   while (king rank + d, king file + d) is on the board
      piece := board[king rank + d][king file + d]
      if piece is an enemy bishop or queen
         return true
      if piece is not an empty square   // a piece blocks any potential
         break                          // attack behind it so we can stop
      d := d + 1

   // do this for all the other forms of attack
   ...

   return false
}

ご覧のとおり、コードの繰り返しがありますが、短くすることができます。わかりやすいのでそのままにしておきました。今行っているように疑似合法的な動きを生成し、それぞれを作成し、上記のサブルーチンでチェックを残すものを省略することにより、正当な動きを生成できます。これには、当然のことながら、追加の利点があります。ここにいくつかの擬似コードがあります:

function legalMoves(board, sideToMove) {
   moveList := empty
   for each move in pseudoLegalMoves()
      make(move)
      if not leftInCheck(board, sideToMove)
         moveList.add(move)
      unmake(move) // you may not need this
   return moveList
}

キャスリングでは、キングとルークの間のマスに攻撃があるかどうかを確認する必要があります。幸いなことに、上記のサブルーチンを拡張して、キング以外の正方形でも機能するようにすることができるので、これは簡単です。

ビットボードや 0x88 を使用しておらず、代わりに単純な配列表現を使用していると思います。これにより、固定されたピースを決定するために攻撃マップを非常に高速に生成する必要があるため、合法的な動きの生成を実装することが少し難しくなります (中間の疑似合法的な動きはありません)。あなたが野心的であれば、これは可能性です。

追加の注意として、ここでの他の回答には少しがっかりしています。また、優れたムーブジェネレーターを作成したい人には、私自身の回答をお勧めしません (チェスのプログラミングに不慣れな人のみを対象としています)。これは、徹底的に検討され、よく知られた解決策があるトピックですが、独創的なアイデアを引き出しています。もちろん、これには何も問題はありませんが、なぜ車輪を再発明する必要があるのでしょうか。ムーブ生成の確立された方法を調べてください。

于 2013-05-29T01:24:10.543 に答える
2

getMoveLocationsチェックへの移行を心配するかどうかを示すフラグを受け入れるようにプロシージャを変更します。たとえば、ピースが固定されている場合でも、移動して相手のキングを捕まえることができます。フラグがチェック リスクを無視するように設定されている場合、チェック テストをスキップすると再帰が中断されます。

代わりに (そして同等に) チェックに移動する問題を無視する移動を生成するための別のメソッドを記述します。その手順を「ボードをチェック状態にする」テストの一部として使用します。

于 2013-05-29T01:10:33.947 に答える
2

移動によって敵の駒がキングに攻撃を加えることができる場合、その移動はあなたの側をチェックします (したがって、許可されません)。

自分自身をチェックすることは、対戦相手をチェックすることとは異なることに注意してください。対戦相手をチェックすると、相手は応答する順番があります。自分を抑えることができれば、応答する機会はゼロになります。彼らはあなたの王を捕まえることができ、たとえ彼らがどんなに悪い立場に置かれたとしても、あるいは彼らが「チェックされている」としても、それは常に正しい動きです - 彼らは勝ったのです! その後は何も残らない。

したがって、移動を行うことで自分自身がチェックされるかどうかを確認するには、敵の駒がキングに攻撃を移動できるかどうかを確認します. それでおしまい。将来のチェックなどを再帰的に解決しているわけではありません-彼らが今すぐ王を攻撃できる場合、それは無効です.

于 2013-05-29T01:19:57.980 に答える
1

一部の投稿者はチェス エンジンを十分に理解していないようです。議論を試みる前に、よく読んで調べてください。

そこに移動できるかどうかではなく、そこに攻撃できるかどうかを確認します。とにかく、後で評価関数にそれが必要になるでしょう...

これを実行するエンジンがいくつあるかはわかりませんが、Stockfish が実行していることは知っているので (src フォルダーの evaluate.cpp を参照)、GOOD エンジンの中ではかなり標準的だと思います。とにかく評価のために行う必要がある場合は、動きの生成で使用することもできます。

于 2013-05-29T02:38:38.287 に答える