1

cの問題の多くの異なる「レベル」で使用されるプロセスがあり、「慣用的な」方法が望ましい問題を処理する方法を知りたい.私はこれを十分に説明していないことを知っている.例を挙げる：

最良の次の動きを出力することになっているゲームソルバーを作成する一般的な問題を考えてみてください.forループ内のすべての可能な動きをチェックし、それが（このラウンドで）勝利の動きであるかどうかを確認する必要があると思います.それ以外の場合は、対戦相手があなたの動きに対してプレイできる可能性のあるすべての動きをチェックし (for ループ)、関数を呼び出して最適な動きを再度見つけます。

ただし、関数は呼び出し元と通信する方法を見つける必要があるため、このアプローチにはパフォーマンス (関数などを呼び出すために必要な定型コードの実行に時間がかかる) や柔軟性の制限など、いくつかの制限があることがわかりました。良い手が見つかりました。

bestmove()
{
  for (;i<maxmove;i++)
   {
    if(checkifwinning(moves[i])) return;
    for (;n<maxopponentmove;n++)
     {
      bestmove();
     }
   }

私はしばらくの間 haskell をいじっていたので、再帰的な解決策を探すことに頭を悩ませているのではないでしょうか。この関数を「C ネイティブ」な方法で書く方法を教えていただければ幸いです。

4

3 に答える 3

3

C 言語では、再帰関数を使用できます。ただし、末尾再帰呼び出しの概念はありません (ただし、最近の GCC コンパイラは、末尾再帰呼び出しを純粋に反復的なマシン コードに最適化できる場合があります)。

再帰関数をコーディングするときは、再帰が深すぎたり、ローカル呼び出しフレームが大きすぎたりしないようにする必要があります (したがって、ヒープ メモリを使用します)。

于 2012-04-25T11:16:25.993 に答える
0

あなたが本当に必要としているのは、分岐限定のようなアルゴリズムだと思います。「オープン」な動き (つまり、まだ考慮されていない) のリストと「閉じられた」動き (つまり、すでに考慮されている) のリストを保持します。C では、これは 2 つのキュー (オープンとクローズ) を使用して実装するのが最適です。次に、次のようなアルゴリズムがあります。

while (open is not empty)
{
   pop gameState from open
   if (gameState in closed)
      continue;
   push gameState to closed
   for (eachMove)
   {
       computeNewState();
       addStateToOpen();
   }
}

再帰的アプローチと比較して、これにはいくつかの利点があります。

  • すべてのゲームの状態が一度だけ考慮されることを確信している
  • スタックを「圧倒」しない
于 2012-04-25T11:23:29.433 に答える
0

あなたは、ゲーム ツリーを検索して最適な動きを見つけることについて話している。minimaxのような標準アルゴリズムを使用できます。あなたのアプローチは、見つかった最初の勝利の動きで終了するツリーの深さ優先検索のようです。これは、勝利への最短経路を見つけたり、対戦相手の勝利を防いだりしないことに注意してください。

alpha-beta pruningなど、ゲーム ツリーの検索を高速化する方法があります。このような標準アルゴリズムは、C などで関数を呼び出すオーバーヘッドを心配するよりもはるかに優れた方法です。C 関数呼び出しは高価ではありません。C コードを書くときは、このような「最適化」に注意してください。いずれにせよ、オプティマイザの方が優れている可能性があります。少なくとも、最初に最も簡単な方法でバージョンを作成して、ベンチマークするものを用意してください。あなたの仕事は、良いアルゴリズムを見つけることです。

于 2012-04-25T12:48:25.113 に答える