0

アルファベータ法のアルゴリズムは次のとおりです。

function ALPHA-BETA-SEARCH(state) returns an action
      v <- MAX-VALUE(state, -∞, +∞)
      return the action in ACTIONS(state) with value v

function MAX-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then 
        return UTILITY(state)
    v <- -∞
    for each a in ACTIONS(state) do
        v <- MAX(v, MIN-VALUE(RESULT(state, a), α, β))
        if v ≥ β then
            return v
        α <- MAX(α, v)
    return v

function MIN-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then 
        return UTILITY(state)
    v <- +∞
    for each a in ACTIONS(state) do
        v <- MIN(v, MAX-VALUE(RESULT(state, a), α, β))
        if v ≤ α then 
            return v
        β <- MIN(β, v)
    return v

アルゴリズムは、ACTIONS関数が特定ので使用可能なすべてのアクションのリストを提供することを示していますstate。

たとえば、チェッカーのゲームを見てみましょう。あるチェッカー、たとえばA、が別のチェッカー、たとえば、と対角線上にあるとしますB。Aを実行できる場合B、それは（可能であれば、他のチェッカーを実行する必要があるため、避けられない）アクションです。または、複数のテイクがある場合、これらはすべてアクションです。この状況は、実際には鉛筆と紙を使用して描くことができます。より具体的には、状況はツリーを使用して表すことができます。各ノードは状態を表し、その子ノードへのエッジはその状態からの可能なアクションを表します。

ツリーデータ構造を明示的に格納する必要はないと思います。ただし、上記のアルゴリズムには次のステートメントが含まれていますreturn the action in ACTIONS(state) with value v。これで、ACTIONS(state)は特定の状態から可能なアクションを返します（たとえば、どこでAプレイする必要があるか）。

すべてのアルゴリズムを実行すると、値が取得され、ターミナルノードから渡されvた値でノードを追跡します。v

ここで、すべての状態からのすべての可能な移動またはアクションの完全なツリーを保存しないと仮定します。がreturn the action ACTIONS(state) with the value v実行されると、次の状態につながるアクションのみが取得され、アクションの1つが可能な限り最良のパスにつながることがわかります。しかし、ツリー全体など、追加の簿記がない場合、アクションを値と一致させることができますvか？

4

2 に答える 2

4
于 2012-04-17T09:56:23.747 に答える
1

私があなたに答えることが重要だと思う2つの問題：

  1. ツリーはとにかく構築されます-暗黙的に、各ACTIONS(vertex)操作は単にvertex彼の息子のそれぞれに接続できます-したがって、とにかく追加のツリー構築の実際の必要はありません。もちろん、vそのツリーの各ノードなどにプロパティを追加することもできます。

  2. それでも、実際のツリーを必要とせず、気にしない場合、考えられる解決策の1つは(v, state)、単なる。ではなく[タプル]を返すことvです。戻り値のすべての操作vは、現在と同じように実行されます。実際に使用するstateのはトップレベルだけALPHA-BETA-SEARCH()です。もちろん、値だけでなく、この値を与えている頂点も見つける必要があるため、それほど洗練されていない機能が必要になりMINます。MAXv

于 2012-04-17T09:39:29.603 に答える