//
// SCORE FOUR! GameBoard class implementation
//
// ECE 2036 
// Fall 2023   
// Prof. Yoder
//
// Goals:
// 1. Provide a fun application of C++ to solving a problem from Game Theory
// 2. Demonstrate implementation of the minimax algorithm, as presented in class.
// 3. Demonstrate parallelization using native C++ threads, as presented in class. 
//
// Notes:
// 1. While some member functions of the GameBoard class support arbitrary grid size,
//    others do not.  For this reason, the software presented here supports only 4x4x4 
//    game boards.
// 2. Several unused member functions of the GameBoard class have implementations which 
//    support gravity toggling, in anticipation of future development.  The present version
//    of the software supports only row/column input rather than row/column/height input.
#include <iostream>
#include <iomanip>
#include <future>
#include <vector>
#include <array>
#include <limits>
#include <cstdlib>
#include <ctime>
#include "GameBoard.h"

using namespace std;

constexpr int MAXSCORE = 1'000'000;

// DANGER!  While some member functions use this constant properly,
//          others ( like displayBoard() ) have the board size hard wired to 4.
constexpr int BOARD_SIZE = 4;

// GameBoard class implementation

GameBoard::GameBoard()
{
    board = {};

    // Create a list of all possible ways to win placing 4 tokens in a row.
    findWinningLines();

    // Seed the built-in RNG in case we have to make a random move. 
    srand(static_cast<unsigned>(time(nullptr)));
}

// Check a move's validity.

bool GameBoard::isValid(int r, int c) const
{
    if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE)
        return false;
    return board[r][c][BOARD_SIZE - 1] == 0;
}

// Gravity is turned on here.  
void GameBoard::updateBoard(int r, int c, int piece)
{
    for (int z = 0; z < BOARD_SIZE; ++z)
    {
        if (board[r][c][z] == 0)
        {
            board[r][c][z] = piece;
            return;
        }
    }
}

// Check a move's validity without gravity constraints.
bool GameBoard::isValid(int r, int c, int z) const
{
    if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE
        || z < 0 || z >= BOARD_SIZE )
        return false;
    return board[r][c][z] == 0;
}

// Move without the constraints of gravity..
void GameBoard::updateBoard(int r, int c, int z, int piece)
{
    if (board[r][c][z] == 0)
    {
       board[r][c][z] = piece;
       return;
    }
}


// Undo move with gravity turned on.
void GameBoard::undoMove(int r, int c)
{
    for (int z = BOARD_SIZE - 1; z >= 0; --z)
    {
        if (board[r][c][z] != 0)
        {
            board[r][c][z] = 0;
            return;
        }
    }
}

// Undo move with gravity turned off.
void GameBoard::undoMove(int r, int c, int z)
{
   board[r][c][z] = 0;
}

// Determine whether the game is over, assuming
// that gravity is turned on
bool GameBoard::movesLeft() const
{
    for (int r = 0; r < BOARD_SIZE; ++r)
        for (int c = 0; c < BOARD_SIZE; ++c)
            if (isValid(r, c))
                return true;
    return false;
}

// Win detection

int GameBoard::checkWinner() const
{
    for (const auto& line : winningLines)
    {
        int sum = 0;
        for (auto [x, y, z] : line)
            sum += board[x][y][z];
        if (sum == 4) return 1;
        if (sum == -4) return -1;
    }
    return 0;
}

// Minimalistic Static Board Evaluator (SBE)
// Since the minimax implementation (see next member function)
// features pruning, search depth is a less severe issue than 
// it otherwise would be, and we can get away with a simpler SBE.

int GameBoard::evaluateBoard() const
{
    int score = 0;
    for (const auto& line : winningLines)
    {
        int sum = 0;
        bool blocked = false;
        for (auto [x, y, z] : line)
            sum += board[x][y][z];

        if (sum == 4) return MAXSCORE;
        if (sum == -4) return -MAXSCORE;

        // Favor partial lines (e.g., three in a row)
        score += (sum * sum * (sum > 0 ? 1 : -1));

        // Next level of sophistication might be to 
        // reward partial filling of intersecting 
        // winningLines for which the intersection 
        // is not occupied by a token.  Reward forking.
    }
    return score;
}

// Minimax implementation with alpha-beta pruning
//    Goal:  Find the move which maximizes the specified player's 
//    score while minimizing the opponent's potential gains.
//
// depth:  current search depth in game tree
// player:  1 for human player, -1 for computer player
// alpha:  the minimum score that the maximizing player is guaranteed
// beta:  the maximum score that the minimizing player is guaranteed
// maxDepth:  maximum search depth in the game tree

int GameBoard::minimax(int depth, int player, int alpha, int beta, int maxDepth)
{
 
   // Check to see if we already have a winning configuration of tokens
   int winner = checkWinner();
   if (winner != 0)
       return winner * MAXSCORE / (depth + 1);

   // If max search depth reached, or no more moves left, score the game board
   if (depth >= maxDepth || !movesLeft())
       return evaluateBoard();

   int bestScore = (player == 1) ? -MAXSCORE : MAXSCORE;

   // Loop through all valid next moves for specified player
   for (int r = 0; r < BOARD_SIZE; ++r)
   {
      for (int c = 0; c < BOARD_SIZE; ++c)
      {
          if (!isValid(r, c)) continue;

          // Recursively call the minimax algorithm with each 
          // possible valid move at the current level
          updateBoard(r, c, player);
          int score = minimax(depth + 1, -player, alpha, beta, maxDepth);
          undoMove(r, c);

          if (player == 1)
          {
              bestScore = max(bestScore, score);
              alpha = max(alpha, bestScore);
          }
          else
          {
              bestScore = min(bestScore, score);
              beta = min(beta, bestScore);
          }

          // This next line is the magic!! Why? 
          // 1.  The minimizing player would never allow the maximizing player to  
          //     achieve a game state more advantageous to the maximizing player
          //     than the maximum score that the minimizing player can guarantee.
          //     So we can stop searching.
          // 2.  Similarly, the maximizing player would never pursue a branch of
          //     the game tree which is less advantageous than the minimum score
          //     that he can guarantee for himself.  So again, we can stop searching.
          // This saves us A LOT of unnecessary work, as we need only traverse a 
          // pruned game tree.
          if (beta <= alpha) break;
      }
  }
    return bestScore;
}

// Find the best move for a given player, given there exists at least one valid move.

// Implementation below spawns 4 threads at a time for demonstration purposes.
// Use of a thread pool and knowledge of available cores would enhance performance.

Move GameBoard::findBestMove(int depth, int player)
{
    
    GameBoard boardSplit[4]={*this,*this,*this,*this};
    future<int> thisThread[4];
    int score, thisScore[4];

    Move bestMove{-1, -1};
    int bestScore = (player == 1) ? -MAXSCORE : MAXSCORE;

    for (int r = 0; r < BOARD_SIZE; ++r)
    {
        // Spawn the 4 threads, one for each column in the current row.
        for (int c = 0; c < BOARD_SIZE; ++c)
        {
           if (!isValid(r, c)) continue; // skip over row/col combinations which are invalid.
           boardSplit[c].updateBoard(r,c,player);
           thisThread[c] = async(launch::async, [&, c]() 
                         { return boardSplit[c].minimax(1, -player, -MAXSCORE, MAXSCORE, depth) ;
                         });
        }
        // Wait for the threads to finish execution and record each thread's score.
        for (int c = 0; c < BOARD_SIZE; ++c)
        {
           if (!isValid(r, c)) {
              thisScore[c] = -player*MAXSCORE; 
           } else 
           {
              thisScore[c] = thisThread[c].get();
              boardSplit[c].undoMove(r,c);
           }
        }

        // Find the highest score from among the 4 threads, and update the current best move.
        for (int c = 0; c < BOARD_SIZE; ++c)
        {
           score = thisScore[c];

           if ((player == 1 && score > bestScore) || (player == -1 && score < bestScore))
           {
               bestScore = score;
               bestMove = {r, c};
           }
        }
              
    }
    if (bestMove.row == -1)  // fallback
    {
        cout << "I am having trouble thinking, so this is a random move." << endl;
        do {
            bestMove.row = rand() % 4;
            bestMove.col = rand() % 4;
        } while (!isValid(bestMove.row, bestMove.col));
    }
    return bestMove;
}

void GameBoard::computerMove(int depth)
{
    Move bestMove = findBestMove(depth, -1);
    cout << "Computer plays: row " << bestMove.row << ", col " << bestMove.col << endl;
    updateBoard(bestMove.row, bestMove.col, -1);
}

// simple helper function for ASCII visualization of tokens and pins.
static char convert(int v)
{
    if (v == 1) return 'O';
    if (v == -1) return 'X';
    return '|';
}
      
// Display the game board in 3D in a simple, but optically pleasing ASCII way.
// Work on this later for board sizes different than 4x4x4.

void GameBoard::displayBoard() const
{
  for (int c=0; c<4; c++)
  {
    for (int h=0; h<4; h++)
    {
      cout << setw((3-c)*5+7) << convert(board[0][3-c][3-h]) << setw(7) << convert(board[1][3-c][3-h]) <<
      setw(7)<< convert(board[2][3-c][3-h]) << setw(7) << convert(board[3][3-c][3-h]) << endl;

    }
    cout << endl;
  }
}


// Find all possible 4-in-a-row lines
// Work on this later for board sizes different than 4x4x4.

void GameBoard::findWinningLines()
{
   winningLines.clear();

   // simple inline helper function for readability.
   auto addLine = [&](vector<array<int,3>> line)
   {
       if (line.size() == 4)
          winningLines.push_back(line);
   };

   // Straight line wins along axes
   for (int x = 0; x < 4; ++x)
       for (int y = 0; y < 4; ++y)
       {
          // vertical
          vector<array<int,3>> line;
          for (int z = 0; z < 4; ++z) line.push_back({x,y,z});
          addLine(line);
       }

   for (int y = 0; y < 4; ++y)
      for (int z = 0; z < 4; ++z)
      {
         vector<array<int,3>> line;
         for (int x = 0; x < 4; ++x) line.push_back({x,y,z});
         addLine(line);
      }

   for (int x = 0; x < 4; ++x)
      for (int z = 0; z < 4; ++z)
      {
         vector<array<int,3>> line;
         for (int y = 0; y < 4; ++y) line.push_back({x,y,z});
         addLine(line);
      }

   // Diagonals within planes
   for (int z = 0; z < 4; ++z)
   {
      vector<array<int,3>> d1, d2;
      for (int i = 0; i < 4; ++i)
      {
         d1.push_back({i,i,z});
         d2.push_back({i,3-i,z});
      }
      addLine(d1); addLine(d2);
   }

   for (int y = 0; y < 4; ++y)
   {
      vector<array<int,3>> d1, d2;
      for (int i = 0; i < 4; ++i)
      {
          d1.push_back({i,y,i});
          d2.push_back({i,y,3-i});
      }
      addLine(d1); addLine(d2);
   }

   for (int x = 0; x < 4; ++x)
   {
      vector<array<int,3>> d1, d2;
      for (int i = 0; i < 4; ++i)
      {
         d1.push_back({x,i,i});
         d2.push_back({x,i,3-i});
      }
      addLine(d1); addLine(d2);
   }

   // Body diagonals
   vector<array<int,3>> bd1, bd2, bd3, bd4;
   for (int i = 0; i < 4; ++i)
   {
      bd1.push_back({i,i,i});
      bd2.push_back({i,i,3-i});
      bd3.push_back({i,3-i,i});
      bd4.push_back({i,3-i,3-i});
   }
   addLine(bd1); addLine(bd2); addLine(bd3); addLine(bd4);
}