Check for two adjacent bits in 2D array (Java)

Question

I am writing a tic-tac-toe game in Java.

I have a 2D array representing a 3-by-3 grid, and need a method to check if there are 2 bits set in such a way that a row of 3 can be formed by adding a third bit.

The only way I could think of doing this is to iterate along the rows, checking for a blank space, then checking the bits around it, but this is potentially messy and confusing piece of code.

Any hints and advice are appreciated!

Answer 1

The strategy is ok - test all empty spaces on the board and calculate a score, while three-in-a-row is a maximum score and you can stop looking for better solutions.

Whether its messy or confusing or not is in your on hands. I'm pretty sure one can provide a readable implementation for this strategy. Think about self-speaking method names:

public Move bestMove(Board board) {
  Score actualMax = new Score(Score.MINIMUM);
  Move[] moves = findAllEmptyFields(board);
  for (Move move:moves) {
    Score actualScore = evaluateMoveForBoard(board, move);
    if (actualScore.equals(Score.MAXIMUM) {
      return move;
    } else if (actualScore.higherThan(actualMax)) {
      actualMax = actualScore;
    }
  }
  return actualMax.getMove();
}

My fictious Board class represents the actual tic-tac-toe board, my Score class holds the score for that move and the move for this score.

Confusing or readable?

Answer 2

I'd say that the inconvenient iterating still is the most straightforward way of doing this. If you still don't want that, I'd suggest you have a look at theory around bitboard. It's a way of representing chess, checkers and similar boards, maybe you can find something there.

Robert Hyatt has written several good articles on bitboard and published them freely on the intertubes.

Answer 3

For a TTT board that you know is always 3x3 just brute force it - there aren't that many comparisons.

pseudo:

foreach row
  if (col1 and col2 and not col3 OR col1 and not col2 and col3 OR not col1 and col2 and col3)
foreach col
  if (row1 and row2 and not row3 OR row1 and not row2 and row3 OR not row1 and row2 and row3)

Don't forget to add the two checks for the diags.

Answer 4

You can always just assign one of 2 bits per grid position 0 = empty 1 = player 1 2 = player 2. Fill it in each time a player makes a move

    1,    2              4,     8             16,     32

   64,  128            256,   512           1024,   2048

 4096, 8192          16384, 32768          65536, 131072

You can then use a quick simple bitwise check to see who has won.

To check the top line you would check bits 1 3 and 5. This can be done by taking the whole bitwise value and &'ing with 1 | 4 | 16 or 21. If the values is non zero then player 1 has a line. To check player 2 on the top line you would and with 2 | 8 | 32 or 42. A player 1 diagonal would be 1 | 256 | 65536 or 65281 and so on.