4

私は三目並べゲームを開発していますが、ゲームがいつ終了するか（そして誰が勝つか）をチェックするアルゴリズムが必要です。3x3ゲームでは、それぞれの可能な勝利状況をチェックします（8つの機能があります）。しかし、7x7（4つのサインが連続しているか、列に並んでいるか、斜めになっている必要があります）には、多くの可能な勝利パターンがあります。

4

4 に答える 4

38

各プレーヤーにビットボードを使用している場合は、ビットシフト操作を使用してボードの勝利をテストできます。

ビットボードの構造は次のとおりです。

6 14 22 30 38 46 54
5 13 21 29 37 45 53
4 12 20 28 36 44 52
3 11 19 27 35 43 51
2 10 18 26 34 42 50
1  9 17 25 33 41 49
0  8 16 24 32 40 48

プレーヤーがゲームボード内の位置を占める場合、関連するビットは1そうではありません0（ビット7、15、23、...がそうであることに注意して0ください）。プレーヤーが勝ちボードを持っているかどうかを確認するには、次の機能を使用できます。

bool haswon(int64_t board)
{
    int64_t y = board & (board >> 7);
    if (y & (y >> 2 * 7)) // check \ diagonal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8)) // check horizontal -
        return true;
    y = board & (board >> 9);
    if (y & (y >> 2 * 9)) // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

例の助けを借りて、私は説明しようとします：1人のプレーヤーの次のビットボードは、最初の行の勝利の組み合わせの垂直と斜めの勝利の横に含まれています。

0101010
1110111
0111011
1101110
0001000
1010101
0011110 ... four occupied positions --> winning board

水平チェックの手順は次のとおりです。

  1. y = board & (board >> 8)

    0101010   0010101   0000000
1110111   0111011   0110011
0111011   0011101   0011001
1101110 & 0110111 = 0100110
0001000   0000100   0000000
1010101   0101010   0000000
0011110   0001111   0001110

  2. y & (y >> 2 * 8)

    0000000   0000000   0000000
0110011   0001100   0000000
0011001   0000110   0000000
0100110 & 0001001 = 0000000
0000000   0000000   0000000
0000000   0000000   0000000
0001110   0000011   0000010

水平チェックの結果、1ビットが設定されたボードになります。これは、ボードに勝利が含まれ、関数がを返すことを意味しますtrue。

同様の機能を使用して、コネクト4ゲームの勝利を確認しました。JohnTrompのTheFhourstonesBenchmarkのソースで、この魅力的な機能を見ました。

于 2011-08-12T21:15:44.297 に答える
4

非常に基本的なアプローチは、すべての単一セルからのすべての方向の実行を確認することですが、ここでは、単一の「行」のセルを1回だけチェックするアプローチを示します。「ライン」は、ベガスのスロットマシンのように、勝つ可能性のある行、列、または対角線です:)

  1. 「行」ごとに、その「行」の先頭に移動します。
  2. カウンターを0に設定します。
  3. 「行」の各セルについて（行を順番にトラバースする）：
    • セルがP1で、カウンターが> = 0の場合、カウンターに1を追加します
      • カウンター=4の場合、P1が勝ちます。
    • セルがP1で、カウンタが負の場合、カウンタを0に設定します
    • セルがP2で、カウンターが<= 0の場合、カウンターから1を引きます
      • カウンター=-4の場合、P2が勝ちます
    • セルがP2で、カウンタが正の場合、カウンタを0に設定します

重要な編集：セルにP1もP2も含まれていない場合は、カウンターを0にリセットします（doh！）。この些細なことですが、必要な手順を省略しました。それ以外の場合、「11-11」は勝利としてカウントされます。

「線」は、反復ごとに開始点と行/列のオフセットを指定してトラバースできます（たとえば、北西から南東への最長の対角線の場合は、（0,0）から開始して（1,1）進みます）。もちろん、長さが4未満の対角線は、完全にチェックされることを回避できます。

ハッピーコーディング。

于 2011-08-12T18:55:42.683 に答える
2

すべての位置をループします。各位置について、対角線下、右下、右下の4つのフィールドを確認します（常にフィールド自体を含みます）。存在しないフィールドをチェックしているときにアプリが爆破されないように、適切なチェックを入れてください。

于 2011-08-12T18:32:29.600 に答える
0

単純。forすべての行、列、対角線の増加、対角線の減少に対して4つのループを作成します。それぞれに、4つの連続したピースがあるかどうかをテストします。

于 2011-08-12T21:14:03.983 に答える