4

私は C でクライアント/サーバーの首謀者ゲームに取り組んでおり、これまでのところ終了しています。私のプログラムは機能しており、平均 6 ～ 7 回の推測で秘密を解きます。それから私はインターネットを調べていて、ドナルズ・クヌースのアプローチを見つけました：

  1. 残りの可能性のセット S を作成します (この時点で 1296 あります)。最初の推測は aabb です。
  2. 色付きのペグと白のペグが答えである場合に同じスコアを与えない S からすべての可能性を削除します。
  3. 可能な推測ごとに (必ずしも S である必要はありません)、可能な色付き/白のスコアごとに S から除外される可能性の数を計算します。推測のスコアは、そのような値の最小値です。最高得点 (ミニマックス) で推測をプレイします。
  4. 正しく理解できるまでステップ 2 に戻ります。

ここで私が言わなければならないのは、5 つの位置と 8 つの色を使用しているということです。

私は自分のプログラムを最適化しようとしているので、ステップ 3 がどのように見えるか、特にどのような推測が最も可能性を排除するかの計算がどのようになるかを理解するのに苦労しています。

私が知っていることは、すべての要素を調べて他の要素と比較する必要があるということですが、白/黒の値がないため、比較する方法がわかりません。そして、特定の条件を満たすエントリが最大の可能性を排除するものをどのように判断できるのだろうか.

4

1 に答える 1

3

私のブログで、アルゴリズムについて説明し、(C ではなく、Scheme で) 実装を提供します。注意が必要な部分は、ミニマックス関数の次の述語です。

(or (< size min-size)
    (and (= size min-size)
         (member (car ps) pool)
         (not (member min-probe pool))))

詳細を理解するにはブログ投稿全体を読む必要がありますが、基本的にこれは Knuth の「対象」要件を実装しています: プローブが新しい​​最小値である場合、または現在の最小値に等しい場合は、プールであり、現在の最小値がプールのメンバーでない場合は、それを新しい最小値として保持します。それ以外の場合は、次のプローブにループします。

于 2013-03-22T14:05:26.123 に答える