/* Alternative implementation of the sample code for assignment 2 question 3 */
/* The sample code has everything for the game rules, but nothing for AI     */

/* Note: This is *heavily* optimized, and is *very* difficult to read!!  */
/* This tries to optimize the finding of playable positions by having a  */
/* board representing the positions of the bits.  Computations are done  */
/* not bit-by-bit, but instead as a whole 64-bit word.  This exploit     */
/* instruction-level parallelism provided by current 32 or 64-bit        */
/* computers, and also save a lot of space in memory (rather than 66     */
/* bytes per config, this uses 16 bytes), in the expense of making code  */
/* that is very difficult to read and understand.                 -Isaac */

#include <iostream>
#include <string>
using namespace std;

static const char MIN_PLAYER = -1, EMPTY_CELL = 0, MAX_PLAYER = 1;
static const char MIN_PLAYER_CHAR = 'X',
  EMPTY_CELL_CHAR = '.', MAX_PLAYER_CHAR = 'O';

// 64-bit integer, giving 1 bit per board location
// for a 32-bit architecture this actually involve a little more time
// to deal with the state, but it will make the obfuscated program a bit
// more readable
typedef unsigned long long bitboard_t;

// Count the number of 1-bits in a 64-bit word within 60 instructions
// (when compiled with -funroll-loops on g++ 3.2)
static int num_bit_set(bitboard_t inbits) {
  int total = 0;
  for (int i = 0; i < 2; ++i) { // for each 32-bit word
    // extract the lower 32-bits
    unsigned int bits = inbits & 0xffffffff;
    unsigned int evenbits = (bits & 0x55555555);
    // extract bit 1, 3, 5, ..., 31, put them in bit 0, 2, 4, ..., 30.
    unsigned int oddbits = ((bits>>1) & 0x55555555);
    // Add them up, so bit 0&1 stores number of bits set in bit 0 & bit 1,
    // bit 2&3 stores number of bits set in bit 2 & bit 3, etc.
    bits = evenbits + oddbits;
    // extract bit 0-1, 4-5, ..., 60-61
    evenbits = (bits & 0x33333333);
    // extract bit 2-3, 6-7, ..., 62-63
    oddbits = ((bits >> 2) & 0x33333333);
    // Add them up, so bits 0-3 stores number of bits set in bit 0--bit 3, etc
    bits = evenbits + oddbits;
    // This is repeated until we get the number of bits in all the 64-bits
    // merge bit 0-3, etc with 4-7, etc
    evenbits = (bits & 0x0f0f0f0f);
    oddbits = ((bits >> 4) & 0x0f0f0f0f);
    bits = evenbits + oddbits;
    // merge bit 0-7, etc with 8-15, etc
    evenbits = (bits & 0x00ff00ff);
    oddbits = ((bits >> 8) & 0x00ff00ff);
    bits = evenbits + oddbits;
    // merge bit 0-15, etc with 16-31, etc
    evenbits = (bits & 0x0000ffff);
    oddbits = ((bits >> 16) & 0x0000ffff);
    total += evenbits + oddbits;
    inbits >>= 32;
  }
  return total;
}

struct game_config_t {
  // It won't store who is the next to move, so minimax must keep it.  This
  // make the whole structure align better to memory locations
  // It won't store whether the last move is pass (it is not needed, as
  // it is now feasible to know quickly whether a game already terminated)
  bitboard_t min_board, max_board;
  // This is not made a constructor, since we might need temporary board
  void make_init_state() {
    max_board = bit_of(3,3)|bit_of(4,4);
    min_board = bit_of(3,4)|bit_of(4,3);
  }
  // Can side make any move?
  bool must_pass(char side) {
    // Get the bit positions that are playable
    bitboard_t playable = (side == MIN_PLAYER) ?
      get_playable(min_board, max_board):
      get_playable(max_board, min_board);
    // must pass if playable has no bit is set
    return playable == 0;
  }
  // Can side play at (y, x) now?
  bool can_play(char side, int y, int x) {
    bitboard_t playable = (side == MIN_PLAYER) ?
      get_playable(min_board, max_board):
      get_playable(max_board, min_board);
    // if the specified bit is on, then can play there
    return (playable & bit_of(y, x)) != 0;
  }
  // Number of pieces for each side
  int count(char side) {
    if (side == MIN_PLAYER)
      return num_bit_set(min_board);
    else
      return num_bit_set(max_board);
  }
  // Make a move for side, at position (y, x)
  void make_move(char side, int y, int x) {
    if (side == MIN_PLAYER) {
      bitboard_t flipped = get_flipped(min_board, max_board, bit_of(y, x));
      // set those bits flipped for myself
      min_board |= flipped;
      // clear those bits flipped for the opponent
      max_board &= ~flipped;
    } else {
      bitboard_t flipped = get_flipped(max_board, min_board, bit_of(y, x));
      max_board |= flipped;
      min_board &= ~flipped;
    }
  }
  // Make a move for side, at position (y, x), and store the result elsewhere
  void make_move(char side, int y, int x, game_config_t &result) {
    result = *this;
    if (side == MIN_PLAYER) {
      bitboard_t flipped = get_flipped(min_board, max_board, bit_of(y, x));
      // set those bits flipped for myself
      result.min_board |= flipped;
      // clear those bits flipped for the opponent
      result.max_board &= ~flipped;
    } else {
      bitboard_t flipped = get_flipped(max_board, min_board, bit_of(y, x));
      result.max_board |= flipped;
      result.min_board &= ~flipped;
    }
  }
  /* Print the current board */
  void print() {
    cout << "  1 2 3 4 5 6 7 8\n";
    for (int y = 0; y < 8; ++y) {
      cout << char('A'+y);
      for (int x = 0; x < 8; ++x) {
	cout << ' ';
	bitboard_t bit = bit_of(y, x);
	if (max_board & bit)
	  cout << MAX_PLAYER_CHAR;
	else if (min_board & bit)
	  cout << MIN_PLAYER_CHAR;
	else
	  cout << EMPTY_CELL_CHAR;
      }
      cout << endl;
    }
  }
  /* Get an input.  Return false if failed. */
  bool get_move(char side, int &y, int &x) {
    string s;
    getline(cin, s);
    if (s.length() != 2)
      return false;
    if (s[0] >= 'a' && s[0] <= 'h')
      y = s[0] - 'a';
    else if (s[0] >= 'A' && s[0] <= 'H')
      y = s[0] - 'A';
    else
      return false;
    if (s[1] >= '1' && s[1] <= '8')
      x = s[1] - '1';
    else
      return false;
    return can_play(side, y, x);
  }
  // Convert row and column numbers to bit mask
  static bitboard_t bit_of(int y, int x) {
    return 1ULL << (y * 8 + x);
  }
  // Print the playable positions
  void print_playable(char side) {
    bitboard_t playable = (side == MIN_PLAYER) ?
      get_playable(min_board, max_board):
      get_playable(max_board, min_board);
    cout << "Playable:";
    for (int i = 0; i < 8; ++i)
      for (int j = 0; j < 8; ++j)
	if (playable & bit_of(i, j))
	  cout << ' ' << char('A' + i) << char('1' + j);
    cout << endl;
  }
  // Before shift left 1 bit, clear the left-most bit to avoid overflow
  static const bitboard_t LSHIFT_MASK = 0x7f7f7f7f7f7f7f7fULL;
  // Before shift right 1 bit, clear the right-most bit to avoid overflow
  static const bitboard_t RSHIFT_MASK = 0xfefefefefefefefeULL;

  // This is around 700 instructions.  In my computer (600MHz PIII) this
  // takes 1.6 microsecs (i.e., 960 CPU cycles).  This still takes 3 times
  // as much time as the "world record", but then it is completely in C,
  // and don't need an MMX computer to run.
  static bitboard_t get_playable(bitboard_t myboard, bitboard_t yourboard) {
    // extremely obfuscated code part 1
    // This is very performance critical: this is done in each decision,
    // a slow one will directly translate to a slow program
    bitboard_t result = 0;
    bitboard_t curr_bits, found_bits;
    int curr_shift;

    // For all directions, the strategy is the same.
    // 1. from the opponent's board, shift once towards left or top, and find
    //    which are not the opponent's pieces.  This gives the top or left
    //    boundary of the opponent's pieces.
    // 2. shift once in the reverse direction.  Set j = 1.  (Actually, store
    //    the amount of shift rather than j.)
    // 3. shift once in the reverse direction.  If it is occupied by
    //    the opponent, leave the bit there.  Otherwise extract the bit.
    // 4. The bits extracted in step 3 is the other (bottom or right) boundary
    //    of a group of bits, all having j piece wide.  If myboard contains a
    //    piece at that position (back-support), mark the other side as
    //    potentially playable.  If the other side has my piece, mark this
    //    side as potentially playable (front-support).
    // 5. increment i, repeat steps 3--5 for 5 more times.

    // N-S direction (shift by 8 bits)
    curr_bits = (yourboard >> 8) & ~yourboard; // step 1
    curr_bits <<= 8;		// step 2
    curr_shift = 8;
    for (int i = 0; i < 6; ++i) {
      curr_shift += 8;
      curr_bits <<= 8;		// step 3: shift and extract
      found_bits = curr_bits & ~yourboard;
      curr_bits &= yourboard;
      result |= ((found_bits & myboard) >> curr_shift); // step 4: back-support
      result |= ((found_bits >> curr_shift) & myboard)
			     << curr_shift; // step 4: front-support
    }
    // W-E direction (shift by 1 bit)
    // The RSHIFT_MASK (and LSHIFT_MASK below) guard against overflow
    // to next column.
    curr_bits = ((yourboard & RSHIFT_MASK) >> 1) & ~yourboard;
    curr_bits <<= 1;
    curr_shift = 1;
    for (int i = 0; i < 6; ++i) {
      curr_shift += 1;
      curr_bits &= LSHIFT_MASK;
      curr_bits <<= 1;
      found_bits = curr_bits & ~yourboard;
      curr_bits &= yourboard;
      result |= ((found_bits & myboard) >> curr_shift);
      result |= ((found_bits >> curr_shift) & myboard)
			     << curr_shift;
    }
    // NW-SE direction (shift by 9 bits)
    curr_bits = ((yourboard & RSHIFT_MASK) >> 9) & ~yourboard;
    curr_bits <<= 9;
    curr_shift = 9;
    for (int i = 0; i < 6; ++i) {
      curr_shift += 9;
      curr_bits &= LSHIFT_MASK;
      curr_bits <<= 9;
      found_bits = curr_bits & ~yourboard;
      curr_bits &= yourboard;
      result |= ((found_bits & myboard) >> curr_shift);
      result |= ((found_bits >> curr_shift) & myboard)
			     << curr_shift;
    }
    // NE-SW direction (shift by 7 bits) (overflow in the opposite direction!)
    curr_bits = ((yourboard & LSHIFT_MASK) >> 7) & ~yourboard;
    curr_bits <<= 7;
    curr_shift = 7;
    for (int i = 0; i < 6; ++i) {
      curr_shift += 7;
      curr_bits &= RSHIFT_MASK;
      curr_bits <<= 7;
      found_bits = curr_bits & ~yourboard;
      curr_bits &= yourboard;
      result |= ((found_bits & myboard) >> curr_shift);
      result |= ((found_bits >> curr_shift) & myboard)
			     << curr_shift;
    }

    // Remove those bits that I've already got, and return
    return result & ~myboard;
  }
  static bitboard_t get_flipped(bitboard_t myboard, bitboard_t yourboard,
				bitboard_t play_pos) {
    // extremely obfuscated code part 2
    // Much less optimization possible here, but yet we want to avoid doing
    // any multiplication
    bitboard_t curr, potential, result = play_pos;
    // North
    curr = play_pos >> 8;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr >>= 8)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // South
    curr = play_pos << 8;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr <<= 8)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // East
    curr = (play_pos & LSHIFT_MASK) << 1;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & LSHIFT_MASK) << 1)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // West
    curr = (play_pos & RSHIFT_MASK) >> 1;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & RSHIFT_MASK) >> 1)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // South-West
    curr = (play_pos & RSHIFT_MASK) << 7;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & RSHIFT_MASK) << 7)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // North-East
    curr = (play_pos & LSHIFT_MASK) >> 7;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & LSHIFT_MASK) >> 7)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // South-East
    curr = (play_pos & LSHIFT_MASK) << 9;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & LSHIFT_MASK) << 9)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    // North-West
    curr = (play_pos & RSHIFT_MASK) >> 9;
    potential = 0;
    if (curr && (curr & yourboard)) {
      potential |= curr;
      while ((curr = (curr & RSHIFT_MASK) >> 9)) {
	if (curr & ~yourboard) {
	  if (curr & myboard)
	    result |= potential;
	  break;
	}
	potential |= curr;
      }
    }
    return result;
  }
};

/* speed testing code
int main() {
  game_config_t state;
  state.make_init_state();
  for (int i = 0; i < 10000000; ++i)
    bitboard_t x = state.get_playable(state.min_board, state.max_board);
}
*/

/* Main program with no AI at all */
int
main()
{
  game_config_t state;
  state.make_init_state();
  char side = MAX_PLAYER;
  for (;;) {
    state.print();
    // Terminate check at beginning
    if (state.must_pass(side) && state.must_pass(-side))
      break;
    if (side == MAX_PLAYER)
      cout << "MAX(" << MAX_PLAYER_CHAR << ")";
    else
      cout << "MIN(" << MIN_PLAYER_CHAR << ")";
    cout << "'s move: ";
    if (state.must_pass(side)) {
      cout << "pass" << endl;
    } else {
      int y, x;
      // state.print_playable(side);
      while (!state.get_move(side, y, x)) {
	cout << "Invalid move, please try again.\n";
	if (side == MAX_PLAYER)
	  cout << "MAX(" << MAX_PLAYER_CHAR << ")";
	else
	  cout << "MIN(" << MIN_PLAYER_CHAR << ")";
	cout << "'s move: ";
      }
      state.make_move(side, y, x);
    }
    side = -side;
  }
  cout << "Game ended with MAX " << state.count(MAX_PLAYER)
       << ", MIN " << state.count(MIN_PLAYER) << endl;
}