3

私は (例えばhttp://radagast.se/othello/Help/order.html ) を読みましたが、最初に各レベルで最良の動きを検索すると (反復的な深化を使用して見つけることができます)、検索がはるかに高速になります。

追加のメモリと CPU 時間をあまり使用せずに、可能な限り最良の動きを検索するにはどうすればよいでしょうか?

4

2 に答える 2

2

基本的に2つの戦略があります：

  1. 静的移動の順序
  2. 動的移動順序

動的移動順序付けでは、以前の検索からの情報が使用されます。これは、同じ位置に再度転置するか、以前のあまり徹底していない検索でその位置にすでに到達しているためです。それはあなたが言及した反復深化のアイデアであり、それは継続的に探索距離を増加させます。

動的な移動順序は非常に強力です。それを行うには多くの方法がありますが、最も一般的な2つの方法は、転置テーブルとキラームーブです。

  • 転置テーブルは、以前の検索に関する情報、特に見つかった最良の移動に関する情報をキャッシュします。再び同じ位置に到達すると、前の検索からすぐに最良の動きを検索できます。非常に多くの場合、それはより深い検索によって最良の動きとして確認されます。

  • キラームーブは同様のアプローチを使用し、類似しているが同一ではない位置からの知識を使用できるという追加の利点があります。ただし、移動順序のキラー移動の品質は、一般に、転置テーブルからの移動よりも劣ります。そのため、通常、転置移動後に検索されます。

しかし、以前の検索からの情報がない場合はどうすればよいでしょうか。多くの場合、静的な移動順序付けに使用できるドメイン固有の知識があります。たとえば、チェスには多くの経験則があります。1つは、キャプチャムーブは、非キャプチャムーブよりも最良のムーブである可能性が高いということです。より洗練された戦略（静的再キャプチャ分析など）がありますが、より複雑な計算も検索の速度を低下させるため、注意が必要です。

静的な移動順序と動的な移動順序の両方を組み合わせることにより、チェスエンジンは、ヒット率が90％を超える位置での最良の移動を推測できることがよくあります。

于 2012-12-28T23:14:48.117 に答える
0

アプリオリに、最良の動きを検索する方法を知っていれば、そもそも検索を行う必要はありません。多くの場合、解決しようとしているゲームの専門知識が必要です。たとえば、チェッカーでは、そうでない手の前に、キングになるすべての動きを評価してみてください。

于 2012-01-18T15:13:05.813 に答える