// This is obviously a perpetual work in progress, but it's good
// enough to generate moves to test the ruby script.  Actually it
// almost always gets higher scores and chains than me playing
// manually, despite using mostly the same strategy.  I think this
// says a lot about being able to apply a strategy consistently.
//
// Stats from solving 5000 games (see {solutions,stats}_{1,2,3}.txt):
//
//        Scores                                       Chains
// depth  min  25%     median  75%     max     mean    min median max mean
// 1      32   35800   47850   68760   350360  58746   1   2      12  2.596
// 2      34   90270   133330  193610  573210  150325  1   2      14  3.530
// 3      276  223260  297180  381570  770440  306058  1   2      14  4.122
//
// Premature deaths (reflected in the minimum scores above):
// depth = 1 -> 30
// depth = 2 -> 6
// depth = 3 -> 3
//
// Personal favorite game:
/*
   ruby arle.rb 4591 llljllljlljllljlllkkjljlljhkjkkjhkkkjhkkkjkjllljljhjhkjllljhkkjjkjllljkjhhkjllkjkjllkjhhjllkjhhkjllkkkljhhjlljlkjhhkjhhjhhkjhhjhhkjkjljhkjhkkkjhhkjljlkkkjhkjkjhhkjllljllkkkljllljhhjllkkkljlllkkjhhkjlljllkkkjhhjlkkjhjjkjllljkjllkjlljhkjjhkkkjjhkjjljhjjlljhkjhkkjlkkjhhkkjlljllljllljllkkkljllkkkjljhhjjljhjhhkkjhhjllkjhhkkjhkkkjhkjhkkjhhkjkkkjhkj
*/

#include"ai.h"
#include<thread>
#include<vector>

namespace {

// Number of moves to look ahead when planning a move.
//
// Increasing this value causes the solver to take exponentially more time
// and space, but score does not necessarily increase with greater depth.
// This is because this solver actually relies a fair bit on luck, as
// opposed to deliberately building chains.  Over-thinking a position
// sometimes actually causes the score to decrease.  Current setting is a
// good trade off between time and quality.
//
// For comparison, solving seed=42:
//  depth = 1 -> time = 0:00.14, score = 29070
//  depth = 2 -> time = 0:00.55, score = 165600
//  depth = 3 -> time = 0:08.99, score = 441320
//  depth = 4 -> time = 2:42.63, score = 307790
//  depth = 5 -> time = 40:54.82, score = 622270
static constexpr int kSearchDepth = 3;

// If true, enable multi-threaded search.
//
// Note that with g++ 7.4.0-1 on Cygwin 3.0.7-1, enabling multi-thread
// mode actually make things significantly slower.  MingW appears to
// work just fine.
static constexpr bool kUseMultiThreadedSearch = true;

struct Move
{
   // Series of keystrokes to apply, always end in "j".
   std::string move = "j";

   // Points obtained by applying this move, higher is better.
   //
   // This is either score value or some estimate of scoring potential,
   // depending on the metric we are maximizing.
   int points = 0;
};

enum class OptimizationMetric
{
   // Maximize score that can be earned in a single move.
   kMaximizeScore,

   // Maximize non-scoring clusters that can be built in a single move.
   kMaximizePotential
};
static constexpr const char *kMetricLabel[2] = {"score", "potential"};

// Positions to test.
static constexpr int kAsymmetricPositions = 22;
static constexpr int kSymmetricPositions = 11;
static constexpr const char *kPositions[kAsymmetricPositions] =
{
   // Orientations 0 + 1
   "lllj",
   "llj",  "llkj",
   "lj",   "lkj",
   "hhj",  "hhkj",
   "hj",   "hkj",
   "j",    "kj",

   // Orientations 2 + 3
   "lllkkj",
   "llkkj",  "llkkklj",
   "lkkj",   "llkkkj",
   "hhkkj",  "hkkkj",
   "hkkj",   "kkkj",
   "kkj",    "lkkkj",
};

// Returns true if grid is considered nearly full.
//
// Grid is considered nearly full if we have anything near the top, or if we
// have too few spots remaining.
//
// Note that even if this function always returns false, i.e. if the grid is
// never considered nearly full, there is still some instant death detection
// logic to prevent the grid from being completely full.  Intuitively then,
// we should just make this function return false all the time to maximize
// potential chains.  But if we did that, we would never "cash out" of the
// chains we have built, and end up clearing short chains near the top of
// the grid.  Current heuristic appears to work well for most seeds.
//
// It's also the case that instant death detection doesn't always work if
// the fate was sealed several blocks ago, so it helps to try to start
// clearing the grid when we are nearly full.
static bool NearlyFull(const Grid &grid)
{
   int empty_spot_count = kWidth * kHeight;
   for(int x = 0; x < kWidth; x++)
   {
      const int height = static_cast<int>(grid[x].size());
      if( x > 0 && x < kWidth - 1 && height >= kHeight - 1 )
         return true;
      empty_spot_count -= height;
   }
   return empty_spot_count <= kWidth * 2;
}

// Give a rating to current grid in terms of number of potential
// chains that can be built.
//
// Intuitively, we want lots of near-complete clusters such that when
// we do decide to clear them, there is a chance that they will form
// long chains.  The weights here are set to encourage that behavior.
//
// As to the actual chains that do result from this heuristic, that is
// mostly based on luck, since we make no deliberate attempt to
// construct chains.
static int GetPotentialPoints(const Grid &grid)
{
   const ClusterList cluster_list = MarkClusters(grid);
   int points = kWidth * (kHeight + 2) + 1;
   for(const Cluster &c : cluster_list)
   {
      if( static_cast<int>(c.size()) >= 3 )
      {
         // Higher weight for clusters that are near complete.  Note
         // that if there is more than enough to complete a chain in a
         // cluster, those clusters will still get the same number of
         // points.  This is so that more small clusters are preferred
         // over fewer large clusters.
         points += 8;
      }
      else if( static_cast<int>(c.size()) == 2 )
      {
         // Half-complete clusters get half points.
         points += 4;
      }
      else if( static_cast<int>(c.size()) == 1 )
      {
         // Single-tile clusters are penalized to avoid fragmentation.
         points--;
      }
   }
   return points;
}

// Forward declaration.
static Move Search(OptimizationMetric metric,
                   const Grid &grid,
                   const BlockList &block_list,
                   int block_index,
                   int depth);

// Compute score for a single position.
static void TestMove(OptimizationMetric metric,
                     const Grid &grid,
                     const BlockList &block_list,
                     int block_index,
                     int depth,
                     int position_index,
                     Move *output_move)
{
   Grid test_grid = grid;
   PendingBlock block(block_list[block_index]);

   output_move->move = kPositions[position_index];
   ApplyMoves(test_grid, output_move->move, &block);
   output_move->points = DropBlock(block, &test_grid);

   // Avoid instant death.
   if( test_grid[(kWidth - 1) / 2].size() >= kHeight - 1 )
   {
      output_move->points = 0;
      return;
   }

   if( metric == OptimizationMetric::kMaximizePotential )
      output_move->points = GetPotentialPoints(test_grid);

   // If dropping this block will not cause us to reach the nearly
   // full condition, give some bonus points to prefer this move
   // over others.
   if( !NearlyFull(test_grid) )
      output_move->points += 4;

   // If we haven't reached maximum depth yet, add points from
   // recursive search result.
   if( depth > 0 )
   {
      output_move->points += Search(metric,
                                    test_grid,
                                    block_list,
                                    block_index + 1,
                                    depth - 1).points;
   }
}

// Given a grid config, return best move.
static Move Search(OptimizationMetric metric,
                   const Grid &grid,
                   const BlockList &block_list,
                   int block_index,
                   int depth)
{
   Move move;
   if( block_index >= static_cast<int>(block_list.size()) )
      return move;

   const int position_count =
      block_list[block_index][0] == block_list[block_index][1]
      ? kSymmetricPositions : kAsymmetricPositions;
   for(int i = 0; i < position_count; i++)
   {
      Move test_move;
      TestMove(metric, grid, block_list, block_index, depth, i, &test_move);

      // Update best move.
      if( move.points < test_move.points )
      {
         move.move.swap(test_move.move);
         move.points = test_move.points;
      }
   }
   return move;
}

// Given a grid configuration, return best move.
//
// This differs from Search in that it's multi-threaded, but note that
// everything below the toplevel expansion proceeds in single-threaded
// mode.  This avoids exponential increase in number of threads.
//
// We could use a thread pool with fixed number of workers instead,
// but it seemed tricky to get right, and I couldn't tell if it was my
// fault or cygwin's fault.  Current implementation is more
// straightforward and easier to debug.
static Move MultiThreadedSearch(OptimizationMetric metric,
                                const Grid &grid,
                                const BlockList &block_list,
                                int block_index,
                                int depth)
{
   Move move;
   if( block_index >= static_cast<int>(block_list.size()) )
      return move;

   // Allocate output buffers.
   const int position_count =
      block_list[block_index][0] == block_list[block_index][1]
      ? kSymmetricPositions : kAsymmetricPositions;
   std::vector<Move> move_candidates(position_count);

   std::vector<std::thread> search_threads;
   search_threads.reserve(position_count);
   for(int i = 0; i < position_count; i++)
   {
      // Capture everything by reference except the loop variable "i".
      search_threads.emplace_back(
         [&, i]() {
            TestMove(metric,
                     grid,
                     block_list,
                     block_index,
                     depth,
                     i,
                     &move_candidates[i]);
         });
   }

   // Wait for child threads to complete.
   for(auto &t : search_threads)
      t.join();

   // Update best move.
   for(int i = 0; i < position_count; i++)
   {
      if( move.points < move_candidates[i].points )
      {
         move.move.swap(move_candidates[i].move);
         move.points = move_candidates[i].points;
      }
   }
   return move;
}

}  // namespace

// Generate move to drop a single block.
std::string GenerateMove(const Grid &grid,
                         const BlockList &block_list,
                         int block_index)
{
   // If the game is about to end either due to lack of blocks
   // remaining or because the grid is mostly full, we want to
   // optimize for as many points as we can get.  Otherwise, we want
   // to optimize for increasing number of near-complete clusters that
   // can be used for scoring later.
   const OptimizationMetric metric =
      static_cast<int>(block_list.size()) - block_index < 16 ||
      NearlyFull(grid)
      ? OptimizationMetric::kMaximizeScore
      : OptimizationMetric::kMaximizePotential;
   printf("%s: ", kMetricLabel[static_cast<int>(metric)]);
   fflush(stdout);

   const Move move =
      kUseMultiThreadedSearch
      ? MultiThreadedSearch(metric, grid, block_list, block_index, kSearchDepth)
      : Search(metric, grid, block_list, block_index, kSearchDepth);
   printf("%s -> %d\n", move.move.c_str(), move.points);
   return move.move;
}