// Tic-tac-toe simulator.
//
// Copyright 2009 Stephen Kelly <steveire@gmail.com>
//
// This is a proof of concept for using a struct of just two 8-bit chars to store a game of tic-tac-toe.
//
// In tic-tac-toe, the players take turns leaving one mark at a time in any of 9 positions, provided it is not already occupied.
//
// -----
// 1 2 3
// 4 5 6
// 7 8 9
// =====
//
// The winner is the first player to get 3 in a row of her own character. E.g, X wins here for its vertical line:
// -----
// O X O
// X X O
//   X
// =====
//
// If we bits represent the positions of marks for each player, then
//
// Player O could be represented as 101001000
// Player X could be represented as 010110010
//
// There are 8 possible win scenarios for a player - One of the three horizontal lines, one of the three vertical lines or
// one of the two diagonals.
//
// Representing these in the same binary notation with all non-winning placements omitted:
//
// 10001000 1
// 11100000 0
// 00011100 0
// 00000011 1
// 00101010 0
// 10010010 0
// 01001001 0
// 00100100 1
//
// The ninth bit is clear of the rest to show that it is the beginning of a new word. To determine if the positions of a players
// marks represent a win, it must have markers in each of the positions of one of the above bit strings. 5 of them can be represented
// in just 8 bits, and the other 3 require the 9th bit to determine if it is a win.
//
// By storing only the first 8 bits in the Game struct and ommitting the 9th we don't have to use an extra word to store the 9th bit
// and can store the state of play for both players in two unsigned chars. The state of the 9th bit can be inferred by examining the rest.
//
// The list above with the 9th bit omitted and converted to hexadecimal is in the {MAYBE_,}WINNER_* #defines. If a players placement matches
// one of the WINNER_* masks, that player has won. If a placement matches one of the MAYBE_WINNER_* defines, the 9th bit must be inferred
// and checked.
//
// The ninth bit can be inferred by counting the number of moves both players appear to have already made, and comparing to how many they
// should have made. If a player is missing a a place marker, it must be the unrepresented 9th bit. This information can only be known if
// we know which player made the most recent move.
//
// As there are only two players, which one is in play is represented with a boolean. If the boolean is true, it represents the home player,
// or the player using 'X'.


#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

#define WINNER_1 0x1c
#define WINNER_2 0x2a
#define WINNER_3 0x49
#define WINNER_4 0x92
#define WINNER_5 0xe0

#define MAYBE_WINNER_1 0x3
#define MAYBE_WINNER_2 0x24
#define MAYBE_WINNER_3 0x88

#define MAX_MOVES 9

struct Game
{
  Game() : home_player_positions(0), away_player_positions(0) {}

  unsigned char home_player_positions;
  unsigned char away_player_positions;
};

/**
  @returns The number of "1" bits in @p word.
*/
unsigned char population_count( unsigned char word )
{
  // This could be done with a lookup table instead.
  unsigned char pop = 0;
  while( word )
  {
    pop += ( word & 1 );
    word >>= 1;
  }
  return pop;
}

/**
  @returns Whether @p home_player (which moved most recently) has fewer moves represented that it should have in @p game.
*/
bool has_missing_move( Game *game, bool home_player )
{
  const unsigned char home_moves = population_count( game->home_player_positions );
  const unsigned char away_moves = population_count( game->away_player_positions );

  return home_player ? home_moves == away_moves : ( away_moves + 1 ) == home_moves;
}

/**
  @returns True if the player represented by @p home_player has won the @p game.
*/
bool is_winner( Game *game, bool home_player )
{
  const unsigned char player_positions = home_player ? game->home_player_positions : game->away_player_positions;
  if   ( ( ( player_positions & WINNER_1 ) == WINNER_1 )
      || ( ( player_positions & WINNER_2 ) == WINNER_2 )
      || ( ( player_positions & WINNER_3 ) == WINNER_3 )
      || ( ( player_positions & WINNER_4 ) == WINNER_4 )
      || ( ( player_positions & WINNER_5 ) == WINNER_5 ) )
    return true;

  return has_missing_move( game, home_player )
      && ( ( player_positions & MAYBE_WINNER_1 ) == MAYBE_WINNER_1
        || ( player_positions & MAYBE_WINNER_2 ) == MAYBE_WINNER_2
        || ( player_positions & MAYBE_WINNER_3 ) == MAYBE_WINNER_3 );
}

/**
  @returns True if the @p game is over. @p home_player represents the most recent player to play.
*/
bool is_over( Game *game, bool home_player )
{
  const unsigned char home_moves = population_count( game->home_player_positions );
  const unsigned char away_moves = population_count( game->away_player_positions );

  if ( is_winner( game, home_player ) )
    return true;

  const bool hidden_occupied = home_player ? ( home_moves == away_moves + 2 || home_moves == away_moves )
                                           : ( home_moves == away_moves - 1 || home_moves == away_moves + 1 );

  return ( away_moves + home_moves + ( hidden_occupied ? 1 : 0 ) ) == MAX_MOVES;
}

/**
  Randomly chooses an available slot for the player represented by @p home_player to place a mark.
*/
void make_move( Game *game, bool home_player )
{
  const unsigned char home_moves = population_count( game->home_player_positions );
  const unsigned char away_moves = population_count( game->away_player_positions );

  std::vector<unsigned char> available;

  const bool hidden_available = home_player ? ( away_moves + 1 != home_moves && away_moves - 1 != home_moves )
                                            : ( away_moves + 2 != home_moves && away_moves != home_moves );

  if ( hidden_available )
    available.push_back( 0 );

  unsigned char taken_positions = game->home_player_positions | game->away_player_positions;
  for (int i = 1; i < MAX_MOVES; ++i )
    if ( !( taken_positions & ( 1 << i - 1 ) ) )
      available.push_back( i );

  unsigned char selected = available.at( unsigned( rand() % available.size() ) );

  if ( selected != 0 )
    ( home_player ? game->home_player_positions : game->away_player_positions ) |= ( 1 << ( selected - 1 ) );
}

// Used to print the first 8 bits of the game board.
#define _11_MASK 0x80
#define _12_MASK 0x40
#define _13_MASK 0x20
#define _21_MASK 0x10
#define _22_MASK 0x08
#define _23_MASK 0x04
#define _31_MASK 0x02
#define _32_MASK 0x01

/**
  Prints the @p game board. @p home_player represents the player which made the most recent move.
*/
void print_game( Game *game, bool home_player )
{
  cout << endl;
  cout << "     " << "-----" << endl;
  cout << "     " << ( (_11_MASK & game->home_player_positions ) ? "X" : ( (_11_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << ( (_12_MASK & game->home_player_positions ) ? "X" : ( (_12_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << ( (_13_MASK & game->home_player_positions ) ? "X" : ( (_13_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << endl;
  cout << "     " << ( (_21_MASK & game->home_player_positions ) ? "X" : ( (_21_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << ( (_22_MASK & game->home_player_positions ) ? "X" : ( (_22_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << ( (_23_MASK & game->home_player_positions ) ? "X" : ( (_23_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << endl;
  cout << "     " << ( (_31_MASK & game->home_player_positions ) ? "X" : ( (_31_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";
  cout << ( (_32_MASK & game->home_player_positions ) ? "X" : ( (_32_MASK & game->away_player_positions ) ? "O" : " " ) ) << " ";

  const unsigned char home_moves = population_count( game->home_player_positions );
  const unsigned char away_moves = population_count( game->away_player_positions );

  if ( home_player )
  {
    if ( home_moves == away_moves )
      cout << "X";
    if ( home_moves == away_moves + 2 )
      cout << "O";
  } else {
    if ( home_moves == away_moves - 1 )
      cout << "X";
    if ( home_moves == away_moves + 1 )
      cout << "O";
  }
  cout << endl;
  cout << "     " << "=====" << endl;
}

/**
  Runs a game of two players randomly placing marks, and declares a winner.
*/
void run_game()
{
  Game game;
  bool home_player = false;
  do {
    home_player = !home_player;
    make_move( &game, home_player );
    print_game( &game, home_player );
  } while ( !is_over( &game, home_player ) );

  cout << endl;

  if ( is_winner( &game, home_player ) )
  {
    cout << ( home_player ? "X <- Winner" : "     Winner -> O" ) << endl;
    return;
  }

  cout << "   No Winner!" << endl;
}

int main()
{
  srand ( static_cast<unsigned int> ( time ( 0 ) ) );

//   for ( int i = 0; i < 1000000; ++i )
    run_game();

  return 0;
}