2

If I have a 64 length java array i[], is there a quick way to find out if every position in that array is "full", other than looping through the entire array? I'm writing a Reversi AI and I need to know whether the entire array is full or not.

Sam P
  • 453
  • 6
  • 19
  • 1
    I doubt that any of the offered methods will be faster at run-time than iterating the array. Or perhaps more importantly, that iterating a 64 element array will be anything like a 'performance bottle-neck'. – Andrew Thompson Apr 19 '12 at 09:41
  • Take note that the Othello variant of Reversi can end even if the board is not completely filled. This means that having some way to tell *only* if the board is full or not (even a very fast one), is not very helpful, you still need to check if (n)either player has any moves left before declaring the game as finished (i.e. placing it in a leaf of a Minimax tree/graph). (*This means the game may end before the grid is completely filled.* from : .wikipedia.org/wiki/Reversi#Rules) – Shivan Dragon Sep 10 '14 at 19:42

4 Answers4

10

Keep a flags variable of type long (which is 64 bits) and use it to track which array entries are 'full' by setting or clearing the relevant bit as appropriate. (You need to keep this in sync with your array entries.)

If you use a 1 value for each bit to mean the relevant cell is full, the you can tell very quickly if the whole array is full by comparing the flag variable to -1L.

Example implementation

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

You can be even more cunning, and use a flags variable to track the colour of each cell too, so you can avoid using arrays altogether. One variable tracks whether the given cell is occupied or not, and the other tracks the colour (0 for white, 1 for black, say). 

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
Graham Borland
  • 60,055
  • 21
  • 138
  • 179
2

You can keep separately a number of "empty" cells, and update it after each move.

However I don't see a need for this optimization: loop of length 64 must be very fast. Please try to see if this is a real bottleneck and if the optimization is worth your effort.

Vlad
  • 35,022
  • 6
  • 77
  • 199
  • if I am using an alpha-beta pruning method, I must see if the grid is full every time I open a node. therefore, there are 64^64 possible loopings. Can you see why now? – Sam P Apr 19 '12 at 09:43
  • @Sam: in this case, using just an increment/decrement to maintain the number of empty cells must be faster than the bit operations (which involve index calculations). – Vlad Apr 19 '12 at 11:04
0

You can use two BitSets for black-and-white (or free-and-iswhite).

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
0

Arrays.asList(i).contains(EMPTY) (possibly you are interpreting null to mean empty).

Tom Hawtin - tackline
  • 145,806
  • 30
  • 211
  • 305
  • 1
    Doesn't contains method in turn loops? – sgowd Apr 19 '12 at 09:38
  • This is less efficient than the obvious approach of iterating over the array. – Marko Topolnik Apr 19 '12 at 09:39
  • It's quicker to write and read. I mean, if we were talking about performance we wouldn't be using an array element for each position -two `long`s would do, and the comparison would probably take a single simple operation (on a sufficiently modern processor architecture). – Tom Hawtin - tackline Apr 19 '12 at 10:14