ITPW 2007

/* Autor: Remigiusz Modrzejewski
* <lrem at maxnet org pl>
* Part of http://lrem.net/pages/view/itpw
* Distributed under the terms of GNU GPL version 2, as found on:  
* http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <list>
#include <vector>
#include <cassert>

using namespace std;

#define MAX_PLAYERS 4
#define MAX_CARD 13
#define MAX_SAME 8
#define MAX_POOL 104
#define POOL_LEVELS 4
#define WAR_POOL_LEVELS 3
#define SURE_THRESHOLD 15
#define HISTORY_FACTOR 0.531142595416039
#undef assert

#define max(a,b)(a<b?b:a)
#define min(a,b)(a<b?a:b)

struct _known_group
{
   int top, bottom;
   list<int> cards;
};

struct _log
{
   int high,
      low,
      sum,
      observations;

   _log(void) :
      high(0),
      low(13),
      sum(0),
      observations(0)
   {}

   int mean(void)
   {
      return sum/observations;
   }
};

struct player
{
   int cards_in_hand,
      top_card,
      pending_decisions[MAX_POOL],
      pd_bidders[MAX_POOL],
      pd_pool[MAX_POOL],
      pending_count,
      cards_in_pool;
   bool bidding,
      its_me;
   _log log[2][MAX_PLAYERS+1][WAR_POOL_LEVELS][POOL_LEVELS];
   list<_known_group> known;

   player() : its_me(false) {}

   void play (void);
   void move (void);
   int after_war_decision(double);
   int defend_decision(double);
   int heads_up_decision(double);
   void reveal (void);
   void record (int);
   void observe (void);
   void draw (void);
   void mark_winner (void);
   void dispatch_war (void);
   void win (void);
   pair<double, double> probabilities (int); // higher, equal
   pair<double, double> educated_guess (int); // guess, sureness
} players[MAX_PLAYERS];

struct game_status
{
   int pool,
      war_pool,
      bidders,
      bid,
      players,
      my_number,
      unknowns[MAX_CARD+1],
      known_pool[MAX_POOL],
      known_count,
      best_top;
   bool know_top,
      in_game,
      winner_survives_war,
      war;
   player *winner;

   void set_state (void);
} table;

void set_deck (void);

#ifdef DEBUG
#define debug(...)\
   char deb_buf[BUFSIZ];\
sprintf(deb_buf, "%d.debug", table.my_number);\
FILE *deb_f=fopen(deb_buf, "a");\
fprintf(deb_f, __VA_ARGS__);\
fclose(deb_f);

void init_files (void)
{
   char deb_buf[BUFSIZ];
   sprintf(deb_buf, "%d.stderr", table.my_number);
   stderr = fopen(deb_buf, "w");
   sprintf(deb_buf, "%d.debug", table.my_number);
   unlink(deb_buf);
}

void check_totals (void)
{
   int total_hand = 0,
      total_pool = 0;

   for(int i = 0; i < table.players; i++)
   {
      assert(0 <= players[i].cards_in_hand);
      total_hand += players[i].cards_in_hand;
      assert(0 <= players[i].cards_in_pool);
      total_pool += players[i].cards_in_pool;
   }

   assert(table.pool == total_pool + table.war_pool);
   assert(total_hand + total_pool + table.war_pool == 104);
}

void check_types (void)
{
   int of_type[MAX_CARD+1];

   for(int i = 1; i <= MAX_CARD; i++)
      of_type[i] = table.unknowns[i];
   for(int i = 0; i < table.known_count; i++)
      of_type[table.known_pool[i]]++;
   for(int i = 0; i < table.players; i++)
   {
      int previous_top = -12345,
         previous_bottom = -12345;
      for(list<_known_group>::iterator it = players[i].known.begin();
            it != players[i].known.end(); it++)
      {
         assert(previous_top < it->top);
         assert(previous_bottom < it->top);
         previous_top = it->top;
         previous_bottom = it->bottom;
         for(list<int>::iterator jt = it->cards.begin();
               jt != it->cards.end(); jt++)
            of_type[*jt]++;
      }
   }
   for(int i = 1; i <= MAX_CARD; i++)
      assert(of_type[i] == MAX_SAME);
}

void check_sanity (void)
{
   check_totals();
   check_types();
}

#else
#define debug(...)
#define assert(...)
#define init_files()
#define check_sanity()
#endif

int main(void)
{
   srand(time(NULL));

   while(true)
   {
      char command[BUFSIZ];
      scanf("%s", command);

      if(strcmp(command, "topcard") == 0)
      {
         int player;
         scanf("%d", &player);
         players[--player].reveal();
      }
      else if(strcmp(command,"your_number") == 0)
      {
         scanf("%d", &table.my_number);
         table.my_number--;
         players[table.my_number].its_me = true;
         init_files();
         printf("=OK\n\n");
      }
      else if(strcmp(command,"setdeck") == 0)
      {
         set_deck();
      }
      else if(strcmp(command,"setstate") == 0)
      {
         table.set_state();
      }
      else if (strcmp(command, "play") == 0)
      {
         int player;
         scanf("%d", &player);
         players[--player].play();
      }
      else if (strcmp(command, "genmove") == 0)
      {
         scanf("%*d");
         players[table.my_number].move();
      }
      else
         printf("?FTW\n\n");
#define MAX_SAME 8
      scanf("%*[^\n]");
      fflush(stdout);
   }
}

void set_deck (void)
{
   debug("set_deck\n");
   int n, x;
   scanf("%d", &n);
   for(int i = 0; i <= MAX_CARD; i++)
      table.unknowns[i] = 0;
   for(int i =0; i < n; i++)
   {
      scanf("%d", &x);
      table.unknowns[x]++;
   }
   for(int i = 0; i < table.players; i++)
      players[i].known.clear();
   table.know_top = table.war = table.in_game = false;
   table.known_count = table.war_pool = 0;
   table.winner = NULL;
   printf("=OK\n\n");
}

void game_status::set_state (void)
{
   debug("game_status::set_state war:%d\n", war);
   if(!war && winner)
      winner->win();
   scanf("%d %d", &pool, &players);
   bidders = 0;
   bid = war ? 2 : 1;
   for(int i = 0; i < players; i++)
   {
      player *current = &::players[i];
      current->pending_count = 0;
      int new_cih;
      scanf("%d", &new_cih);
      debug("\tplayer:%d cards_in_hand:%d new_cih:%d\n",
            i, current->cards_in_hand, new_cih);
      if(in_game)
         war_pool += current->cards_in_pool;
      current->cards_in_pool = in_game ?
         current->cards_in_hand - new_cih : 1;
      assert(!current->cards_in_pool
            || current->cards_in_pool == bid
            || !new_cih);
      current->cards_in_hand = new_cih;
      if(current->bidding = 0 < current->cards_in_pool)
      {
         bidders++;
      }
   }
   know_top = !::players[my_number].bidding;
   war = false;
   in_game = true;
   best_top = -1;
   printf("=OK\n\n");
   check_sanity();
}

void player::win (void)
{
   _known_group tmp;

   tmp.top = cards_in_hand + 1;
   tmp.bottom = cards_in_hand + table.known_count;

   for(int i = 0; i < table.known_count; i++)
      tmp.cards.push_front(table.known_pool[i]);
   table.known_count = 0;

   known.push_back(tmp);

   debug("player::win\n\tcards_in_hand:%d\n\ttable.pool:%d\n",
         cards_in_hand, table.pool);

   cards_in_hand += table.pool;
   for(int i = 0; i < table.players; i++)
      players[i].cards_in_pool = 0;
   table.war_pool = table.pool = 0;
   check_sanity();
}

void player::record (int decision)
{
   pd_pool[pending_count] = cards_in_pool;
   pd_bidders[pending_count] = table.bidders;
   pending_decisions[pending_count++] = decision;
}

int bidders_level (int bidders)
{
   if(bidders == 2)
      return 0;
   return 1;
}

int war_pool_level (int war_pool)
{
   if(table.war_pool == 0)
      return 0;
   /*if(table.war_pool < 6)
   return 1;*/
   return 2;
}

int pool_level (int pool)
{
   if(pool < 2)
      return 0;
   /*if(pool < 5)
   return 1;*/
   if(pool < 9 )
      return 2;
   return 3;
}

void player::observe (void)
{
   if(!pending_count)
      return;
   while(pending_count--)
   {
      int i = pending_count;
      _log *current = &log[pending_decisions[i]]
         [bidders_level(pd_bidders[i])]
         [war_pool_level(table.war_pool)]
         [pool_level(pd_pool[i])];

      current->high = max(current->high, top_card);
      current->low  = min(current->low, top_card);
      current->sum += top_card;
      current->observations++;
   }
}

void player::play (void)
{
   char move[BUFSIZ];

   scanf("%s", move);
   if(strcmp(move, "pass") == 0)
   {
      pending_count = 0;
      bidding = false;
      table.bidders--;
      draw();
   }
   else if(strcmp(move, "raise") == 0)
   {
      int count;
      scanf("%d", &count);
      table.bid += count;
      record(1);
   }
   else
   {
      record(0);
   }
   if(bidding)
   {
      int change = min(table.bid - cards_in_pool, cards_in_hand);
      table.pool += change;
      cards_in_hand -= change;
      cards_in_pool += change;
   }
   printf("=OK\n\n");
   check_sanity();
}

void player::mark_winner (void)
{
   table.war = false;
   table.best_top = top_card;
   table.winner = this;
   table.winner_survives_war = 0 < cards_in_hand;
}

void player::dispatch_war (void)
{
   if(table.winner_survives_war)
      table.war = table.war || 0 < cards_in_hand;
   else
      if(cards_in_hand)
         mark_winner();
      else
         table.winner = NULL;
}

void player::reveal (void)
{
   scanf("%d", &top_card);
   debug("player::reveal top_card:%d table.best_top:%d\n",
         top_card, table.best_top);
   observe();
   if(table.know_top)
   {
      draw();
      if(!its_me)
      {
         table.unknowns[top_card]--;
         assert(0 <= table.unknowns[top_card]);
         table.known_pool[table.known_count++] = top_card;
      }
      if(top_card > table.best_top)
      {
         mark_winner();
      }
      else if(top_card == table.best_top)
      {
         dispatch_war();
      }
   }
   else
   {
      table.unknowns[top_card]--;
      table.known_pool[table.known_count++] = top_card;
      table.know_top = true;
   }

   printf("=OK\n\n");
   check_sanity();
}

void player::draw()
{
   debug("player::draw\n\tknown.front().top:%d\n\tcards_in_pool:%d\n",
         known.front().top, cards_in_pool);
   for(list<_known_group>::iterator it = known.begin();
         it != known.end(); it++)
   {
      it->top -= cards_in_pool;
      it->bottom -= cards_in_pool;
   }
   while(!known.empty() && known.front().top <= 0)
   {
      for(list<int>::iterator it = known.front().cards.begin();
            it != known.front().cards.end(); it++)
      {
         table.unknowns[*it]++;
         assert(table.unknowns[*it] <= MAX_SAME);
      }
      known.pop_front();
   }
   check_sanity();
}

pair<double, double> player::probabilities (int opposed_to) // higher, equal
{
   int higher_unknowns = 0,
      equal_unknowns = 0,
      lower_unknowns = 0,
      total_unknowns;

   for(int i = 0; i < opposed_to; i++)
      lower_unknowns += table.unknowns[i];
   equal_unknowns = table.unknowns[opposed_to];
   for(int i = opposed_to + 1; i <= MAX_CARD; i++)
      higher_unknowns += table.unknowns[i];
   total_unknowns = higher_unknowns + equal_unknowns + lower_unknowns;

   debug("player::probabilities\n\topposed_to:%2d\n\thigher_unknowns:%3d"
         "\n\tequal_unknowns:%3d\n\tlower_unknowns:%3d\n",
         opposed_to, higher_unknowns, equal_unknowns,
         lower_unknowns);
   return make_pair(((double)higher_unknowns)/total_unknowns,
         ((double)equal_unknowns)/total_unknowns);
}

pair <double, double> player::educated_guess (int opposed_to) // guess, sureness
{
   int observations = 0;
   double sureness,
         probability = 0;

   for(int i = 0; i < pending_count; i++)
   {
      _log *current = &log[pending_decisions[i]]
         [bidders_level(pd_bidders[i])]
         [war_pool_level(table.war_pool)]
         [pool_level(pd_pool[i])];

      if(opposed_to < current->low)
         probability += 1.0;
      else
         if(opposed_to <= current->high)
            probability += (current->mean() - opposed_to)
               / MAX_CARD * 0.5 + 0.5;

      observations += current->observations;
   }

   if(pending_count)
      probability /= pending_count;
   sureness = (double)observations / SURE_THRESHOLD;
   if(sureness > 1.0)
      sureness = 1.0;

   debug("player::educated_guess probability:%f sureness:%f\n",
         probability, sureness);

   return make_pair(probability, sureness);
}

int player::after_war_decision (double not_lose_probability)
{
   return 0 + (not_lose_probability > 0.376839497753451   && cards_in_pool < 3)
      - (not_lose_probability < 0.573746084050261 && cards_in_pool > 2);
}

int player::defend_decision (double not_lose_probability)
{
   return -1 + (not_lose_probability > 0.925840075024843
         && cards_in_hand > 19)
      + (not_lose_probability > 0.72379728518924
            && cards_in_hand > 25
            && !(rand()%1) );
}

int player::heads_up_decision (double not_lose_probability)
{
   return -1 + (not_lose_probability > 0.915249272223223
         && cards_in_hand > 25)
      + (not_lose_probability > 0.749845951323045
            && cards_in_hand > 31
            && !(rand()%6) );
}

void player::move (void)
{
   int decision = -1;
   double win_probability,
         historical_probability;

   historical_probability = win_probability = 1;
   for(int i = 0; i < table.players; i++)
      if(players[i].bidding && !players[i].its_me)
      {
         double       current_not_win;
         pair<double, double> current_historical,
            current_statistical;

         current_statistical =
            players[i].probabilities(top_card);
         current_not_win = current_statistical.first
            + current_statistical.second;
         win_probability -= current_not_win;

         current_historical= players[i].educated_guess(top_card);
         historical_probability -= (current_historical.first
               * current_historical.second) +
            (current_not_win
            * (1.0 - current_historical.second));
      }

   win_probability = historical_probability * HISTORY_FACTOR
      + win_probability * (1 - HISTORY_FACTOR);

   if(win_probability > 0.917373993954353 || top_card == 13)
      decision = cards_in_hand < 14 ? 0 :
         (3 - !(rand()%1) - !(rand()%3));
   else if(top_card > 7 && table.bid == 1 && rand()%3)
   {
      decision = 1;
   }
   else
      if(table.war_pool)
      {
         decision = after_war_decision(win_probability);
      }
      else if (table.bidders == 2)
      {
         decision = heads_up_decision(win_probability);
      }
      else
      {
         decision = defend_decision (win_probability);
      }
   debug("player::move\n\ttop_card:%2d\n\twin_probability:%f\n\t"
         "decision:%d\n",
         top_card, win_probability, decision);

   if(cards_in_pool == table.bid)
      decision = max(decision, 0);
   decision = min(decision, max(0,(
               (cards_in_hand + cards_in_pool - table.bid))));

   if(cards_in_hand == 0)
      decision = 0;

   if(decision > 0)
      printf("=raise %d\n\n", decision);
   else if(decision < 0)
      printf("=pass\n\n");
   else
      printf("=check\n\n");
}