tic tac toe

tictactoe.cpp

#include <iostream>
#include <iomanip>

#define BINARY(x) 0b##x 

const short UPPER_LEFT = BINARY(100000000);

const short FULL_BOARD = BINARY(111111111);

const short HORIZ_0 = BINARY(111000000);
const short HORIZ_1 = BINARY(000111000);
const short HORIZ_2 = BINARY(000000111);

const short VERT_0 = BINARY(100100100);
const short VERT_1 = BINARY(010010010);
const short VERT_2 = BINARY(001001001);

const short DIAG_0 = BINARY(100010001);
const short DIAG_1 = BINARY(001010100);

using namespace std;

// Check if we have a winner!
bool didPlayerWin(short moves) {
  if (((moves & HORIZ_0) == HORIZ_0) ||
      ((moves & HORIZ_1) == HORIZ_1) ||
      ((moves & HORIZ_2) == HORIZ_2) ||
      ((moves & VERT_0)  == VERT_0)  ||
      ((moves & VERT_1)  == VERT_1)  ||
      ((moves & VERT_2)  == VERT_2)  ||
      ((moves & DIAG_0)  == DIAG_0)  ||
      ((moves & DIAG_1)  == DIAG_1))
    return true;
  return false;
}

// Where are we allowed to move?
short validMoves(short xMoves, short oMoves) {
  return ~(xMoves | oMoves) & FULL_BOARD;
}

// Board visualizer
void printBoard(string description, short xMoves, short oMoves) {
  cout << description << endl;
  for (int row=0; row<3; row++) {
    for (int col=0; col<3; col++) {
      short currentPosition = UPPER_LEFT >> (col + row*3);
      if ((xMoves & currentPosition) != 0)
        cout << "x";
      else if ((oMoves & currentPosition) != 0)
        cout << "o";
      else
        cout << "-";
    }
    cout << endl;
  }
}

// Is it over yet?
bool gameOver(short xMoves, short oMoves) {
  if ((validMoves(xMoves, oMoves) & FULL_BOARD) == 0)
    return true;
  return didPlayerWin(xMoves) || didPlayerWin(oMoves);
}

// if we move here, we'll win immediately!
short winningMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short winning = 0;
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      // check if moving here makes us win
      if (didPlayerWin(thinkingPlayer | sel))
        winning |= sel;
    }
  }
  return winning;
}

// if we move here, we'll lose next turn!
short losingMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short trapping = 0;
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      // check if moving here gives the opponent a winning move
      if (winningMoves(idlePlayer, thinkingPlayer | sel))
        trapping |= sel;
    }
  }
  return trapping;
}

// if we move here, we'll win right now or on our next turn
short planWinningMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short winning = 0 | winningMoves(thinkingPlayer, idlePlayer);
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      short opponentMoves =
          validMoves(idlePlayer, thinkingPlayer | sel);
      if (losingMoves(idlePlayer, thinkingPlayer | sel) ==
          opponentMoves) {
        // moving here forces the opponent to make a bad move
        winning |= sel;
      }
    }
  }
  return winning;
}

// if we move here, our opponent can plan a winning move
short planLosingMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short trapping = 0 | losingMoves(thinkingPlayer, idlePlayer);
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      // check if moving here guarantees a win for them
      if (planWinningMoves(idlePlayer, thinkingPlayer | sel))
        trapping |= sel;
    }
  }
  return trapping;
}

// now we want perfect moves
// aka moves that start a chain where we win for sure
short perfWinningMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short winning = 0 | winningMoves(thinkingPlayer, idlePlayer);
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      // check if moving here forces them to make a bad move
      if (planLosingMoves(idlePlayer, thinkingPlayer | sel) ==
         validMoves(idlePlayer, thinkingPlayer | sel)) {
        winning |= sel;
      }
    }
  }
  return winning;
}}

// we also want perfectly bad moves
// aka moves that start a chain where we lose for sure
short perfLosingMoves(short thinkingPlayer, short idlePlayer) {
  if (gameOver(thinkingPlayer, idlePlayer))
    return 0;
  short moves = validMoves(thinkingPlayer, idlePlayer);
  short trapping = 0 | losingMoves(thinkingPlayer, idlePlayer);
  // for all valid moves..
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel) {
      // check if moving here lets them make a winning move
      if (perfWinningMoves(idlePlayer, thinkingPlayer | sel))
        trapping |= sel;
    }
  }
  return trapping;
}

void printLosingMovesExample() {
  // short xMoves = 0b000010000;
  // short oMoves = 0b000000000;
  short xMoves = 0b000100100;
  short oMoves = 0b000000010;
  printBoard("O's turn", xMoves, oMoves);
  short moves = perfLosingMoves(oMoves, xMoves);
  printBoard("If O moves here, he will lose", moves, moves);

  cout << endl;

  xMoves = 0b100000000;
  oMoves = 0b000000000;
  printBoard("O's turn", xMoves, oMoves);
  moves = perfLosingMoves(oMoves, xMoves);
  printBoard("If O moves here, he will lose", moves, moves);
}

int countMoves(short moves) {
  int result = 0;
  for (short sel = 1 << 8; sel != 0; sel = sel >> 1) {
    if (moves & sel)
      result++;
  }
  return result;
}

void printFirstMoveTable() {
  for (int row=0; row<3; row++) {
    for (int col=0; col<3; col++) {
      short move = UPPER_LEFT >> (col + row*3);

      short availableMoves = validMoves(0, move);
      short badMoves = perfLosingMoves(0, move);

      cout << setiosflags(ios::fixed) << setprecision(3);
      cout << countMoves(badMoves)/
        (double)countMoves(availableMoves);
      if (col != 2)
        cout << " | ";
    }
    cout << endl;
    if (row != 2)
      cout << "---------------------" << endl;
  }
}

int main() {
  short xMoves = 1;
  short oMoves = 0;

  printLosingMovesExample();
  printFirstMoveTable();
}