java - 配列内のすべての位置が「いっぱい」かどうかをすばやく見つける方法はありますか?

Question

長さ 64 の Java 配列 i[] がある場合、配列全体をループする以外に、その配列内のすべての位置が「いっぱい」であるかどうかを調べる簡単な方法はありますか? リバーシ AI を書いていますが、配列全体がいっぱいかどうかを知る必要があります。

Answer 1

タイプ (64 ビット) の flags 変数を保持しlong、関連するビットを適切に設定またはクリアすることによって、どの配列エントリが「いっぱい」であるかを追跡するために使用します。(これを配列エントリと同期させる必要があります。)

各ビットの値を使用して1、関連するセルがいっぱいであることを意味する場合、フラグ変数を と比較することで、配列全体がいっぱいかどうかをすぐに知ることができます-1L。

実装例

int[] grid = new int[64];
long  full = 0L;

// place a piece at a certain grid position
grid[17] = 1;   // pretend 1 is the code for black
full |= 1L << 17;   // set bit 17 in our "full" tracker

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't

---

さらに狡猾になり、フラグ変数を使用して各セルの色を追跡することもできるため、配列の使用を完全に避けることができます。1 つの変数は、指定されたセルが占有されているかどうかを追跡し、もう 1 つの変数は色を追跡します (白の場合は 0、黒の場合は 1 など)。

long colour = 0L;
long full   = 0L;

// set position 17 to white
colour &= ~(1L << 17);    // clear the bit (white)
full   |=  (1L << 17);    // set it to occupied

// set position 42 to black
colour |=  (1L << 42);    // set the bit (black)
full   |=  (1L << 42);    // set it to occupied

// is position 25 occupied?
if ((full & (1L<<25)) != 0) {
    // yes, but what colour?
    if ((colour & (1L<<25)) != 0)
        // black
    else
        // white
}

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't

Answer 2

いくつかの「空の」セルを個別に保持し、移動するたびに更新できます。

ただし、この最適化の必要性はわかりません。長さ 64 のループは非常に高速でなければなりません。これが実際のボトルネックであるかどうか、また最適化に努力する価値があるかどうかを確認してください。

Answer 3

白黒 (または自由白) には 2 つの BitSet を使用できます。

Answer 4

Arrays.asList(i).contains(EMPTY)（おそらく、null空を意味すると解釈しています）。