13

私はゲームの意思決定 AI を書いていて、次のコードを思いつきました。

if(pushedLeft && leftFree && leftExists)
    GoLeft();
else if(pushedRight && rightFree && rightExists)
    GoRight();
else if(leftFree && leftExists)
    GoLeft();
else if(rightFree && rightExists)
    GoRight();
else if(pushedLeft && leftExists)
    GoLeft();
else if(pushedRight && rightExists)
    GoRight();
else if(leftExists)
    GoLeft();
else if(rightExists)
    GoRight();
// else do nothing...

ifこれは、同様の条件付きのステートメントのかなり長いストリームです!

この素敵なパターンになることに注意してください。

L1 L2 L3  -> L
R1 R2 R3  -> R
   L2 L3  -> L
   R2 R3  -> R
L1    L3  -> L
R1    R3  -> R
      L3  -> L
      R3  -> R
(nothing) -> 0

このコードの目的は、入ってくる状態情報に基づいて、オブジェクトが左または右に移動するか (またはまったく移動しないか) を決定することです。各情報には、異なる優先順位があります。次のように順序付けられたリストに記述できます。

Highest Priority
----------------
Don't ever move into an invalid space
Prefer to move into an unoccupied space
Prefer to move in the push direction
Prefer to move left
----------------
Lowest Priority

この決定を行うための情報入力を追加すると、条件の数が 2 倍になることは明らかです。また、これらの入力の可能な値の数を 2 倍にする (例: 上/下/左/右を許可する) と、条件の数も 2 倍になります。(つまり、これは n×m 2の条件ですよね?)

だから私の質問は：

これをコーディングするための、満足のいく、エレガントな方法はありますか?

私はそれを行うための素敵な「n×m」の方法があるに違いないと考えています（編集：最初はここに「n + m」がありましたが、n×mの入力条件があるため、それは不可能に思えます）。ここの私のコードと一般的な問題の両方に当てはまるものはありますか?

上記の条件付きバージョンと同じかそれ以上のパフォーマンスを発揮するものが望ましいです。理想的には、ヒープ割り当てを回避するもの - ゲーム開発シナリオで使用するために重要です (ただし、これらは必要に応じてキャッシュなどでいつでも最適化できます)。

また、この問題に対して「Google で使用できる用語」はありますか? これは珍しい問題ではないと思いますが、名前がわかりません。

更新: Superpig の回答のおかげで、さまざまなオプションのスコアを計算するというアイデアがあります。このようなもの：

int nothingScore = 1 << 4;
int leftScore = (1 << 1) + (pushedLeft ? 1 << 2 : 0) + (leftFree ? 1 << 3 : 0) + (leftExists ? 1 << 5 : 0);
int rightScore = (pushedRight ? 1 << 2 : 0) + (rightFree ? 1 << 3 : 0) + (rightExists ? 1 << 5 : 0);

確かに、スコアリング コードを記述するより適切な方法があります (スコアリングする別の方法もあります)。そして、スコアが計算されたら何をするかを選択するという問題がまだあります。そしてもちろん、採点をまったく含まない、より良い方法があるかもしれません。

更新 2:ここに自分の回答を投稿して受け入れました(Superpig は完全なソリューションではなく、これまでのところ他の回答はリモートで正しい軌道に乗っていないため)。さまざまな出力をスコアリングするのではなく、ビットフィールドを使用してオプションを除外するアプローチを選択しました。これにより、メモリに単一の整数のみを使用して決定を下すことができます。

4

8 に答える 8

7

これは基本的に分類の問題です。意思決定ツリー (または動作ツリー) のようなものが必要です。状況 (有効性、フリーネス、プッシュ方向など) に対して一連の個別の入力を取得し、結果を「上、下、左、または右」に分類しようとしています。

if ステートメントの長いチェーンよりも優れた、または同等のパフォーマンスが必要な場合、少なくとも命令数/実行された比較の数に関しては、そこで行っている方法で比較を行う必要があると思います。すべての方向のスコアを計算してから最大値をチェックする、または動きのリストを優先と非優先に再帰的に分割するなどのアプローチはすべて、純粋な比較シーケンスよりも多くの作業を行うことになります。

ルックアップ テーブルを作成するだけでよいと思います。方向が有効かどうかを示す 4 ビット、方向が占有されているかどうかを示す 4 ビット、およびプッシュ方向を示す 2 ビットの合計 10 ビットがあるため、1024 の異なる状況があり、それぞれの動作は次のようになります。わずか 2 ビット (つまり 1 バイト) で記述されるため、テーブルの合計サイズは 1024 バイトになります。

単一のエントリは次のような構造になります。

union DecisionSituation
{
    unsigned short Index;
    struct
    {       
        bool ValidLeft : 1;
        bool ValidRight : 1;
        bool ValidUp : 1;
        bool ValidDown : 1;
        bool OccupiedLeft : 1;
        bool OccupiedRight : 1;
        bool OccupiedUp : 1;
        bool OccupiedDown : 1;
        Direction PushDirection : 2; 
    } Flags;
}

その構造体にフラグを入力して状況を説明し、'Index' 値を読み取ってルックアップ テーブル インデックスを取得します。

編集:また、スコアリング関数に関しては、厳密なビットパターンを実行しているため、すべての三項演算子をスキップできると思います:

int leftScore = (leftExists << 4) | (leftFree << 3) | (pushedLeft << 2) | 1;
int rightScore = (rightExists << 4) | (rightFree << 3) | (pushedRight << 2) | 0;

// Find the highest scoring direction here

// If none of the scores are at least (1 << 4) it means none of them existed
if(highest score < (1 << 4)) return nothing;

// otherwise just return the highest scoring direction
于 2012-06-10T12:34:53.337 に答える
4

最も重要なことは、入力が何であるかを宣言するコードと、それらの相対的な優先順位をシンプル、短く、エレガントにすることです。そのコードを記述する 1 つの方法を次に示します。

PreferencedDecisionMaker pdm = new PreferencedDecisionMaker();
pdm.Push(false, leftExists, rightExists, upExists, downExists);
pdm.Push(0);
pdm.Push(false, leftFree,   rightFree,   upFree,   downFree  );
pdm.Push(false, pushedLeft, pushedRight, pushedUp, pushedDown);
pdm.Push(1);
switch(pdm.Decision)
{
    case 1: GoLeft();  break;
    case 2: GoRight(); break;
    case 3: GoUp();    break;
    case 4: GoDown();  break;
}

ここでは、入力は基本的に表形式で宣言されています。各入力の優先順位は、行の順序によって定義されます。各列は可能な出力に対応します。

このコードの「複雑さ」は n×m です。

(これをテーブルのように見せるためにインデントを使用しましたが、より複雑な入力条件では、各行が 1 行にきちんと存在することはできません。これは問題ではありません。重要なのは、n×m しかないということです。宣言. 条件が短いときにテーブルのように見えるようにできるのは、ちょうどいいボーナスです.

決定を行うための実際の舞台裏のコード (PreferencedDecisionMaker型) はそれほど重要ではありません。優先順位に基づいて最適な出力決定を計算するには、いくつかの方法があります。Superpig はスコアリングを提案しましたが、これは優れています。しかし、私はビットフィールドを使用したオプション除去アプローチに行き着きました。このためのコードを以下に掲載しました。

ビットフィールドを使用すると、配列にヒープメモリを割り当てる必要がないという大きな利点があります。唯一の欠点は、オプションが 32 個に制限されていることです。

次のコードは完全にはテストされていません。Pushそして、メソッドの 32 のバージョンすべてに記入したわけではありません。それは「いたずら」である可変構造体を使用します-それを不変構造体に変換することは簡単なはずです。または、クラスにすることもできますが、ヒープ割り当てを回避する利点が失われます。

struct PreferencedDecisionMaker
{
    private uint availableOptionsBits;

    private static readonly int[] MultiplyDeBruijnBitPosition = {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    public int Decision
    {
        get
        {
            uint v = availableOptionsBits;

            // Find position of lowest set bit in constant time
            // http://stackoverflow.com/a/757266/165500
            return MultiplyDeBruijnBitPosition[((uint)((v & -v) * 0x077CB531U)) >> 27];
        }
    }

    private void InternalPush(uint preference)
    {
        if(availableOptionsBits == 0)
            availableOptionsBits = preference;
        else
        {
            uint combinedBits = availableOptionsBits & preference;
            if(combinedBits != 0)
                availableOptionsBits = combinedBits;
        }
    }

    public void Push(int option)
    {
        if(option < 0 || option >= 32) throw new ArgumentOutOfRangeException("Option must be between 0 and 31");
        InternalPush(1u << option);
    }

    // ... etc ...
    public void Push(bool p0, bool p1, bool p2, bool p3, bool p4) { InternalPush((p0?1u:0u) | ((p1?1u:0u)<<1) | ((p2?1u:0u)<<2) | ((p3?1u:0u)<<3) | ((p4?1u:0u)<<4)); }
    // ... etc ...
}
于 2012-06-11T03:51:19.060 に答える
3

一連のステートメントがある場合、通常は状態パターンifと組み合わせたポリモーフィズムを使用してリファクタリングできます。

紹介として、Misko Hevery の次のビデオをご覧ください (きっと気に入るはずです)。

http://www.youtube.com/watch?v=4F72VULWFvc&feature=player_embedded# !

これはプレゼンテーションの要約です。

ほとんどの if はポリモーフィズム (サブクラス化) で置き換えることができます

これが望ましい理由は次のとおりです。

  • if を使用しない関数は、if を使用するよりも読みやすい
  • ifs のない関数はテストしやすい
  • ifs の関連する分岐は、同じサブクラスになります。

ポリモーフィズム (サブクラス) を使用する

  • チェックしている場合、オブジェクトはその状態に基づいて異なる動作をする必要があります
  • 複数の場所で同じ if 条件をチェックする必要がある場合

次の場合に使用

  • 境界チェック プリミティブ オブジェクト (>、<、==、!=)
  • ...他の用途ですが、今日は回避することに焦点を当てています

多くの場合、ポリモーフィック ソリューションの方が優れています。

  • 元のソースコードがなくても新しい動作を追加できる
  • 各操作/懸念は別のファイルに分かれています
  • テスト/理解を容易にする

編集

ポリモーフィズムで状態パターンを使用すると、以前よりも多くのクラスが必要になることを意味するため、ソリューションはより複雑に見えますが、この種のコードのテストを書き始める限り、トレードオフははるかに優れています。その方がテストしやすく、読みやすく、理解しやすく、したがって、保守と拡張が容易であることがわかります (今は右または左への移動について投稿しましたが、後で上下に移動する必要がある場合を想像してください。今すぐコードをリファクタリングしないでください。新しい機能を追加すると、本当の PITA になります)

次のようなものがあります。

// represents the current position
class MyClass
{
  public int X;
  public int Y;
}
abstract class NodeMoving
{
   abstract void Move();
   abstract bool IsValid(MyClass myclass);
}
abstract class NodeMovingLeft : NodeMoving
{
   override void Move()
   {
      // add code to move left
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
abstract class NodeMovingRight : NodeMoving
{
   override void Move()
   {
      // add code to move right
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
// and then start modeling the different states
class RightFree : NodeMovingRight
{
   override bool IsValid(MyClass myclass)
   {
      // add condition to validate if the right is free
   }
}
// combining conditions
class PushedLeft : NodeMovingLeft
{
   override bool IsValid(MyClass myclass)
   {
      // code to determine if it has been pushed to the left
   }
}
class LeftFree : PushedLeft
{
   override bool IsValid(MyClass myclass)
   {
      // get condition to indicate if the left is free
      var currentCondition = GetCondition();
      // combining the conditions
      return currentCondition && base.IsValid(myClass);
   }
}

条件を計算して移動を実行するために必要なプロパティを追加する必要があります

メソッドがどれだけ小さいかに注意する価値があります (はい、以前よりも多くのメソッドがあります) が、分離してテストするのは非常に簡単です。

編集 2 -- 優先度の追加

単純なステート マシンができたので、優先順位を評価する必要があります。それを行う 1 つの方法 (改善方法を聞きたいのですが) は、優先順位キューを使用することです。

http://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

次のようになります。

    // you could place the priorities in a service to reuse it
    var priorities = new HashSet<NodeMoving>();

    priorities.Add(new RightExists());
    priorities.Add(new PushedLeft());

    var currentPosition = new MyClass { X = 1, Y = 2 };

    foreach (var priority in priorities)
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: RightExists

    // now changing the priority order
    foreach (var priority in priorities.Reverse())
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: PushedLeft
于 2012-06-10T11:30:49.790 に答える
2

状態パターンを使用します。すべての異なる状態と、それらの間で許可される遷移を含む状態図を描きます。コーディングすると、ノードごとに状態サブクラスがあります。各状態ノード/クラスは、入力を決定し、次の許可された状態への適切な遷移を駆動します。あなたが言及した状態の多様性を避けることはできないと思います。

于 2012-06-10T11:44:34.147 に答える
1

これは機能しませんか：

if(!leftExists) {
    if(rightExists) {
        GoRight();
    } else {
        // Panic!
    }
} else if(!rightExists) {
    GoLeft();
} else if(rightFree || leftFree && !(rightFree && leftFree)) {
    if(rightFree) {
        GoRight();   
    } else {
        GoLeft();
    }
} else if(pushedRight) {
    // Assumption: pushedLeft and pushedRight cannot both be true?
    GoRight();
} else {
    // PushedLeft == true, or we just prefer to move left by default
    GoLeft();
}

今のところ、これは同じ量のコードですが、共通の条件を削除したため、条件を追加しても各ブランチに影響を与えることはありません。目的の優先度で挿入するだけです。

于 2012-06-10T12:06:29.697 に答える
1

私はあなたのソリューションの変更に固執します。

GoLeft を left が存在するかどうかも返す関数にすることを考えましたか? それが複雑な関数であり、これをLOTと呼んでいて、テストで最適化が必要であることが示されない限り、それが私がすることです.

すると、以下のようになります。それは基本的にあなたがやっていることですが、読みやすいです。

オブジェクト指向ではなく、コマンドパターンを使用していないため、これには反対票が投じられると確信していますが、質問に答えており、読みやすいです;）より複雑な問題については、次のように考えますこれらの答えを使用しますが、この特定の問題については、単純な答えに固執します.

if(pushedLeft && leftFree && GoLeft())    ;
else if(pushedRight && rightFree && GoRight())    ;
else if(leftFree && GoLeft())    ;
else if(rightFree && GoRight())    ;
else if(pushedLeft && GoLeft())    ;
else if(pushedRight && GoRight())    ;
else if(GoLeft())    ;
else if(GoRight())    ;
// else do nothing...
于 2012-06-10T16:29:10.950 に答える
0

これを把握するには、次の対策をお勧めします。

  1. if ステートメントでどのステートメントを組み合わせるかを決定する

  2. if ステートメントのもつれを解くと、次のようなネストされた if ステートメントが生成されます

    if (moveRight) 
{
    if (pushedleft)
    {
        /// ...
    }
}

  3. これができたら、すべての条件付きロジックをメソッドにパックし始めます。たとえば、HandleMoveRight

  4. これを行うと、クラスの抽出を開始し、最終的にコマンド パターンを作成できます。

これで、追加の機能を追加する際の問題はなくなり、複雑さもなくなりました。

于 2012-06-10T11:57:29.387 に答える
0

@john2lob が推奨する状態パターンは正しいアプローチだと思います。また、イベント 'push' / 'free' / 'exists' のアクションの次の遷移を決定するために、ある種の決定木アプローチが必要です。ところで: 「無料」と「存在する」の違いは何ですか?

于 2012-06-10T12:08:03.910 に答える