//---------------------------------------------------------------------------
// POTM ENTRY: Carnac
//       [this name is a reference to the old prehistorical stone alignements
//        of Carnac in Brittany, France. I visited them last summer...]
// BY: Frederic van der Plancke
// AT: fvdp@decis.be
// COMPILE INSTRUCTIONS: ensure macro POTM_ENTRY is defined
//   and keep fingers crossed when compiling for the first time.
//---------------------------------------------------------------------------
// Note:
// *  This code was slightly tidied up, but is equivalent to my POTM entry,
//   up to one difference: search for 'if (_isExhaustiveSoFar)' below.
// *  All code included in #ifdef VERBOSE or #ifdef PROFILING blocks is for
//   debugging and can be safely removed. Idem for ASSERT(..) statements.
//   I wondered if I should remove these lines, but they may be useful for
//   someone who wants to see how my code executes. To read my code, though,
//   you better remove them.
// *  I hope there is no bug, but I'm not totally sure. If you see one, please
//   tell me !
//---------------------------------------------------------------------------
#define POTM_ENTRY
//---------------------------------------------------------------------------
#ifdef __BORLANDC__
// meaning: C++ Builder 1.0.
#pragma hdrstop
#include <condefs.h>
#endif
//---------------------------------------------------------------------------
#ifdef POTM_ENTRY
#include <stdlib.h>
#include <algo.h> // for std::sort, std::merge
#include <iostream.h>
#include <sys/times.h>
#define POTM_MAIN main
#define POTM_IO
#define POTM_PLAYER        // : public ::Player
#define POTM_NAMESPACE(n)  // namespace n {
#define POTM_NAMESPACE_END // } // end namespace
#define ASSERT(p) ((void)0)
#else
#error you forgot to define POTM_ENTRY ;-)
#include "entry.h" // definitions for my own use. You don't need this.
#include <time.h>
#endif
//---------------------------------------------------------------------------

#include <setjmp.h>

//---------------------------------------------------------------------------

//#define CHECK_BOARD { if (checking_board) check_board(); }
#define CHECK_BOARD {}

//#define VERBOSE

#undef CERR
#define CERR cerr
//---------------------------------------------------------------------------
POTM_NAMESPACE(carnac)        // you may safely ignore this line
//---------------------------------------------------------------------------
// profiling
#ifdef PROFILING
   #define DECLARE_PROFILE(tag) int profile_##tag = 0
   #define RESET_PROFILE(tag) profile_##tag = 0
   #define PRINT_PROFILE(tag) os << "| " #tag " " << profile_##tag << ::endl

   DECLARE_PROFILE(visited_nodes);
   DECLARE_PROFILE(search_terminal_nodes);
   DECLARE_PROFILE(game_terminal_nodes);
   DECLARE_PROFILE(hash_alpha_cutoff);
   DECLARE_PROFILE(hash_beta_cutoff);
   DECLARE_PROFILE(hash_hits);
   DECLARE_PROFILE(hash_exact_hits);
   DECLARE_PROFILE(hash_written_entries);
   DECLARE_PROFILE(exhausted_nodes);
   //   DECLARE_PROFILE(apriori_refutations);
   //   DECLARE_PROFILE(apriori_prunings);
   DECLARE_PROFILE(line_evaluations);

   void resetProfiles()
   {
   RESET_PROFILE(visited_nodes);
   RESET_PROFILE(search_terminal_nodes);
   RESET_PROFILE(game_terminal_nodes);
   RESET_PROFILE(hash_alpha_cutoff);
   RESET_PROFILE(hash_beta_cutoff);
   RESET_PROFILE(hash_hits);
   RESET_PROFILE(hash_exact_hits);
   RESET_PROFILE(hash_written_entries);
   RESET_PROFILE(exhausted_nodes);
   //   RESET_PROFILE(apriori_refutations);
   //   RESET_PROFILE(apriori_prunings);
   RESET_PROFILE(line_evaluations);
   }
   void printProfiles(ostream & os)
   {
   os << "Profiles:" << ::endl;
   PRINT_PROFILE(visited_nodes);
   PRINT_PROFILE(search_terminal_nodes);
   PRINT_PROFILE(game_terminal_nodes);
   PRINT_PROFILE(hash_alpha_cutoff);
   PRINT_PROFILE(hash_beta_cutoff);
   PRINT_PROFILE(hash_hits);
   PRINT_PROFILE(hash_exact_hits);
   PRINT_PROFILE(hash_written_entries);
   PRINT_PROFILE(exhausted_nodes);
   //   RESET_PROFILE(apriori_refutations);
   //   RESET_PROFILE(apriori_prunings);
   PRINT_PROFILE(line_evaluations);
   }
#else
#define PROFILE(what) ((void)0)
#endif

//---------------------------------------------------------------------------

const int unit = 10;
const int infinity = 14*119*unit + 1;

//---------------------------------------------------------------------------
// lineval.h/cpp
//---------------------------------------------------------------------------

typedef int (*ValuationTable)[128];

class Valuation_base {
public:
   Valuation_base(ValuationTable masterTableX,
                  ValuationTable masterTableO = 0);

//private:
   short _cache[1 << 14]; // 16384 integers ! 32K or 64K table.

protected:
   short compute(int i);

   ValuationTable _masterXTable;
   ValuationTable _masterOTable;
};

class DirectValuation : public Valuation_base {
public:
   DirectValuation(ValuationTable masterTableX,
                   ValuationTable masterTableO = 0);

   int at(int i) { return _cache[i]; }
};


Valuation_base::
Valuation_base(ValuationTable masterTableX, ValuationTable masterTableO)
{
    _masterXTable = masterTableX;
    _masterOTable = masterTableO ?  masterTableO :  masterTableX;
}
short Valuation_base::compute(int i)
{
   const int cell_X = 0x01;
   const int cell_O = 0x02;

   int x_sequ = 0;
   int x_sequ_size = 0;
   int o_sequ = 0;
   int o_sequ_size = 0;
   int score = 0;

   for(;;)
   {
       int c = i & 0x03; // next cell in line
       i = i >> 2;

       if (c & cell_X) // c is X or empty:
       {
          ++ x_sequ_size;
          x_sequ = x_sequ + x_sequ;
          if (c == cell_X)
             ++ x_sequ;
       }
       else
       {
          score += _masterXTable[x_sequ_size][x_sequ];
          x_sequ_size = x_sequ = 0;
       }

       if (c & cell_O) // c is O or empty:
       {
          ++ o_sequ_size;
          o_sequ = o_sequ + o_sequ;
          if (c == cell_O)
             ++ o_sequ;
       }
       else
       {
          score -= _masterOTable[o_sequ_size][o_sequ];
          o_sequ_size = o_sequ = 0;
       }

       if (i==0 && c==0) break;
   }//end while i

   return score;
}

DirectValuation::
DirectValuation(ValuationTable masterXTable, ValuationTable masterOTable)
: Valuation_base(masterXTable, masterOTable)
{
    for (int i = 0; i < (1 << 14); ++ i)
        _cache[i] = compute(i);
}



//---------------------------------------------------------------------------

int weights_table[8][128] = { // mean of "half" and "gauss"
  {0},
  {0,0},
  {0,0,0,0},
  {2,4,4,13,4,13,13,30},
  {5,8,13,23,13,24,32,58,8,13,24,44,23,44,58,100},
  {9,14,17,31,23,35,56,82,17,29,50,68,56,77,105,161,14,23,29,44,35,51,77,
      124,31,44,68,108,82,124,161,250},
  {15,21,31,44,33,47,71,101,33,45,67,90,80,103,158,207,31,37,46,65,67,87,
      130,172,71,87,130,163,158,193,264,370,21,28,37,52,45,69,87,122,47,69,
      87,115,103,139,193,285,44,52,65,87,90,115,163,246,101,122,172,246,207,
      285,370,560},
  {22,29,40,55,47,59,87,121,45,56,81,107,101,123,182,242,47,53,65,89,92,114,
      157,209,101,119,162,204,200,243,357,455,40,47,56,78,65,97,114,159,81,
      96,119,156,162,201,286,371,87,97,114,142,157,186,266,339,182,206,286,
      350,357,418,576,767,29,41,47,63,53,73,97,133,56,70,96,124,119,162,206,
      278,59,73,97,120,114,158,186,249,123,162,201,254,243,317,418,587,55,63,
      78,109,89,120,142,194,107,124,156,200,204,254,350,500,121,133,159,194,
      209,249,339,478,242,278,371,500,455,587,767,1190},
};

//---------------------------------------------------------------------------

DirectValuation valuation(weights_table);
//#define VALUE_OF_LINE(i) valuation.at(i)
#define VALUE_OF_LINE(i) valuation._cache[i]

//---------------------------------------------------------------------------
// hash.h  (hash.cpp follows)
//---------------------------------------------------------------------------

class PtHashedPosition {
public:
    short board[7];
};

class PtHashEntry {
public:
    PtHashedPosition position;
    short depth; // depth of next evaluation

    short minValue; // min value of position
    short maxValue; // max value of position

    char  bestMove;
};

class PtHash {
public:
    PtHash(int maxSize = 131072);  // size must be a power of two.
    ~PtHash();

    typedef int Index;
    enum { invalidIndex = -1 };

    // reading:

    Index findExisting(const int position[7]) const;
    // returns invalidIndex if [position] not stored in [this]

    // advanced reading methods:

    Index getHash(const int position[7]) const;
    // returns index where [position] is or would be stored in [this]
    bool  isPresent(Index, const int position[7]) const;
    // returns true iff [position] is stored at given Index.

    // values are always w.r.t. the player to play.

    short getMinValue(Index i) const { return _entries[i].minValue; }
    short getMaxValue(Index i) const { return _entries[i].maxValue; }

    short getDepth(Index i) const { return _entries[i].depth; }
    int   getMove(Index i) const { return _entries[i].bestMove; }

    // writing:

    void eraseAll(); // invalidates all entries

    // overwriting any previous entry:
    void  write(const int position[7],
                int depth, int minValue, int maxValue,
                int move,
                Index i = invalidIndex);

private://forbidden:
    PtHash(const PtHash &);
    void operator = (const PtHash &);

private:
    PtHashEntry* _entries;

    // parameters:
    int _size;      // size of _entries; a power of two.
    int _hashMask;  // _size - 1...
};

//---------------------------------------------------------------------------
//  hash.cpp
//---------------------------------------------------------------------------

PtHash::Index PtHash::findExisting(const int position[7]) const
{
    Index would_be = getHash(position);
    if (isPresent(would_be, position))
        return would_be;
    else
        return invalidIndex;
}

bool  PtHash::isPresent(PtHash::Index i, const int position[7]) const
{
    ASSERT(0 <= i && i < _size);

    const short* storedPos = _entries[i].position.board;
    const int* wantedPos = position;
    return true //_entries[i].valueKind != vkInvalid
        && *storedPos++ == *wantedPos++
        && *storedPos++ == *wantedPos++
        && *storedPos++ == *wantedPos++
        && *storedPos++ == *wantedPos++
        && *storedPos++ == *wantedPos++
        && *storedPos++ == *wantedPos++
        && *storedPos   == *wantedPos
        ;
}

PtHash::Index PtHash::getHash(const int position[7]) const
{
    const unsigned prime = 997;
    const int* pos = position;

    unsigned hash = *pos++;
    hash = hash * prime + *pos++;
    hash = hash * prime + *pos++;
    hash = hash * prime + *pos++;
    hash = hash * prime + *pos++;
    hash = hash * prime + *pos++;
    hash = hash * prime + *pos;

    return hash & _hashMask;
}

// overwriting any previous entry:
void PtHash::
write(const int position[7],
      int depth, int minValue, int maxValue,
      int move,
      Index i)
{
    if (i == invalidIndex)
        i = getHash(position);
    ASSERT(0 <= i && i < _size);

    PtHashEntry* entry = & _entries[i];
    for (int i = 0; i < 7; ++ i)
        entry->position.board[i] = position[i];
    entry->minValue = minValue;
    entry->maxValue = maxValue;
    entry->depth = depth;
    entry->bestMove = move;
}

PtHash::PtHash(int size)
: _size(0), _hashMask(0), _entries(0)
{
    // size must be a positive power of two:
    ASSERT(size > 0 && (size & (size - 1)) == 0);
    ASSERT(size * sizeof(PtHashEntry) < 10000000); // max 10 megs !!!

    _entries = new PtHashEntry[size];
    ASSERT(_entries);
    if (! _entries) {
        CERR << "Hashtable allocation failure" << ::endl;
        throw "Ouch!";
    }

    _size = size;
    _hashMask = _size - 1;

    eraseAll();
}
//---------------------------------------------------------------------------
PtHash::~PtHash()
{
    if (_entries) delete[] _entries;
}
//---------------------------------------------------------------------------
void PtHash::eraseAll()
{
    memset(_entries, 0, sizeof(_entries));
	// may Bjarne Stroustrup never see this ;-)
}

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

struct ValuedMove {
   int x; int y;
   int score; // DIFFERENCE between scores after and before move.
};
inline bool operator < (const ValuedMove & v, const ValuedMove & w)
{
   return v.score > w.score;
}

//---------------------------------------------------------------------------

class Player;

class Position {
public:
    Position(Player* p, const char* board);

    int get_player() const // returns player to play
        { return board_remainder % 2; }

    int get_board_score_for_X() const { return board_score; }
    const int* get_board() const { return board_rows; }

    int is_free(int x, int y) const;
    int move_value_X(int x, int y) const; // evaluate move for X

    // returns moves in board_moves and count as return value :
    int init_moves(ValuedMove* board_moves);
    int update_moves(
        //-- in:
        int x,
        int y,
        // previous move list:
        const ValuedMove* board_moves,
        int board_nummoves,
        //-- out:
        ValuedMove* new_board_moves
        // returned value: new_board_nummoves
    );

    void move(int p, int x, int y);
    void unmove(int p, int x, int y);

    int find_any_move(int & x, int & y) const;

    void display(::ostream & os) const;

    // general / debug configuration:
    static bool checking_board;

private:// methods
    void init_board(const char*);

    int computed_board_score() const; // DEBUG - need not be fast
    void check_board() const; // DEBUG

private:// members

    int board_rows[7];
    int board_cols[7];
    int board_score; // heuristic score
    int board_remainder; // # of EMPTY CELLS

    //@@@ to add:
    //int board_min_score;
    //int board_max_score;

    Player* player; // static data that do not really belong to Position
};

inline ostream & operator << (ostream & os, const Position & pos)
{
    pos.display(os);
    return os;
}

//---------------------------------------------------------------------------

class Player {
public:
    Player(const char* board);

    int evaluate(
        int depth, int min_value, int max_value,
        ValuedMove moves[], int num_moves       // moves at level to play
    );

    void iterative_deepening(int startDepth = 4, int incrDepth = 2);

    void init_time_check(double allowed_time_in_seconds);
    //init_time_check sets limit but not jmpbuf
    void time_check(); // makes setjmp in case time limit exceeded.

    //bool checked_play();
    bool checked_play(char* char_board); // writes move into char_board

private:
    // forbidden copy & assignment:
    Player(const Player &);
    void operator = (const Player &);

private:
    time_t  time_limit;
    jmp_buf _jmpBuffer;

    Position _currentPosition;
    // implicit temporaries for iterative deepening:
    int _currentMaxFullDepth;
    int _xBest;
    int _yBest;
    bool _isExhaustiveSoFar;

    PtHash _hashTable;
};

Player::Player(const char* board)
: time_limit(0),
  //_jmpBuffer(),   // this line works OK with my compiler, not with Fred's !
  _currentPosition(this, board),
  _currentMaxFullDepth(0), _xBest(-1), _yBest(-1),
  _isExhaustiveSoFar(true),
  _hashTable()
{}

// final score eval

int sign_of_player[2] = { 1, -1 };

//---------------------------------------------------------------------------


bool Position::checking_board = true;

//---------------------------------------------------------------------------

// returns moves in board_moves and count as return value :
int Position::init_moves(ValuedMove* board_moves)
{
    ValuedMove* pWrite = board_moves;
    for (int x = 0; x < 7; ++ x)
        for (int y = 0; y < 7; ++ y)
            if (is_free(x,y))
            {
                int score = move_value_X(x,y);
                ASSERT(score >= 0);
                if (score > 0)
                {
                    pWrite->x = x;
                    pWrite->y = y;
                    pWrite->score = score;
                    ++ pWrite;
                }
            }
    std::sort(board_moves, pWrite);
    return pWrite - board_moves;
}

//---------------------------------------------------------------------------

int Position::update_moves(
    //-- in:
    int x,
    int y,
    // previous move list:
    const ValuedMove* board_moves,
    int board_nummoves,
    //-- out:
    ValuedMove* new_board_moves
    // returned value: new_board_nummoves
    )
{
    const ValuedMove* pRead = board_moves;
    const ValuedMove* pReadEnd = board_moves + board_nummoves;

    ValuedMove oldMoves[49-12];
    ValuedMove* pWriteOld = oldMoves;
    ValuedMove newMoves[12];
    ValuedMove* pWriteNew = newMoves;

    int newRow = board_rows[x];
    int newCol = board_cols[y];

    for ( ; pRead < pReadEnd; ++ pRead)
    {
        int xRead = pRead->x;
        int yRead = pRead->y;
        if (xRead == x) // same row
        {
            if (yRead != y)
            {
                int score = move_value_X(xRead, yRead);
                ASSERT(score >= 0);
                if (score > 0) // elimination of dead move
                {
                    pWriteNew->x = xRead;
                    pWriteNew->y = yRead;
                    pWriteNew->score = score;
                    ++ pWriteNew;
                }
            }
        }
        else if (yRead == y)
        {
            ASSERT(xRead != x);

            int score = move_value_X(xRead, yRead);
            if (score > 0) // elimination of dead move
            {
                    pWriteNew->x = xRead;
                    pWriteNew->y = yRead;
                    pWriteNew->score = score;
                    ++ pWriteNew;
            }
        }
        else {
            pWriteOld->x = xRead;
            pWriteOld->y = yRead;
            pWriteOld->score = pRead->score;
            ++ pWriteOld;
        }
    }//end for pRead

    std::sort(newMoves, pWriteNew);
    const ValuedMove* newEnd =
       std::merge(newMoves, pWriteNew, oldMoves, pWriteOld, new_board_moves);

    return newEnd - new_board_moves;
}


//---------------------------------------------------------------------------

int Position::computed_board_score() const // need not be fast
{
    int score = 0;
    for (int i = 0; i < 7; ++ i)
    {
        score += VALUE_OF_LINE(board_rows[i]);
        score += VALUE_OF_LINE(board_cols[i]);
    }
    return score;
}

//---------------------------------------------------------------------------

// for debug only:
void Position::check_board() const
{
    int empty = 0;
    int numX = 0;
    int numO = 0;
    for (int y = 0; y < 7; ++ y)
    {
        int yy = 2*y;
        for (int x = 0; x < 7; ++ x)
        {
            int xx = 2*x;

            bool hX = ((board_rows[y] >> xx) & 0x03) == 0x01;
            bool hO = ((board_cols[x] >> yy) & 0x03) == 0x02;

            bool vX = ((board_rows[y] >> xx) & 0x03) == 0x01;
            bool vO = ((board_cols[x] >> yy) & 0x03) == 0x02;

            bool forbidden  = ((board_rows[y] >> xx) & 0x03) == 0x00;
            bool forbidden2 = ((board_cols[x] >> yy) & 0x03) == 0x00;

            if (   hX != vX
                || hO != vO
                || forbidden != forbidden2
                || (hX && hO)
               )
            {
               CERR << "Bad board at " << x << ":" << y << " !" << ::endl;
               return;
            }

            if (! forbidden && ! hX && ! hO) ++ empty;
            if (hX) ++ numX;
            if (hO) ++ numO;
        }
    }
    if (empty != board_remainder)
    {
        CERR << "Bad empty count: is " << board_remainder
             << " but there are " << empty << " empty cells."
             << ::endl;
        return;
    }
    if (! (numO <= numX && numX <= numO + 1))
    {
        CERR << "Bad O/X count"
             << ::endl;
        return;
    }

    /*//TEMP
    CERR << "Scores:\n\trows: ";
    for (int i = 0; i < 7; ++ i)
        CERR << int(VALUE_OF_LINE(board_rows[i])) << " ";
    CERR << "\tcols: ";
    for (int i = 0; i < 7; ++ i)
        CERR << int(VALUE_OF_LINE(board_cols[i])) << " ";
    /**/

    if (board_score != computed_board_score())
    {
        CERR << "Bad score " << board_score << " instead of actual "
             << computed_board_score()
             << ::endl;
    }
}

//---------------------------------------------------------------------------

int Position::is_free(int x, int y) const
{
    CHECK_BOARD
    return ((board_cols[x] >> (y+y)) & 0x03) == 0x03;
}

int Position::move_value_X(int x, int y) const // evaluate move for X
{
    CHECK_BOARD

// score pour X: (X-score avec X) - (X-score)
// score pour O: (O-score avec O) - (O-score) = (X score) - (X-score avec O)
// somme: (X-score avec X) - (X-score avec O) !

    int row = board_rows[y];
    int rowbit = 1 << (x+x);
    int score = VALUE_OF_LINE(row &~ (rowbit+rowbit))  // X-score with X
              - VALUE_OF_LINE(row &~ rowbit); // X-score with O

    int col = board_cols[x];
    int colbit = 1 << (y+y);
    score += VALUE_OF_LINE(col &~ (colbit+colbit))
           - VALUE_OF_LINE(col &~ colbit);

    ASSERT(score >= 0);
    return score;
}

//---------------------------------------------------------------------------

void Position::move(int p, int x, int y)
{
    CHECK_BOARD

    int row = board_rows[y];
    int score = - VALUE_OF_LINE(row);
    row &=~ (1 << (1-p+x+x));
    score += VALUE_OF_LINE(row);
    board_rows[y] = row;

    int col = board_cols[x];
    score -= VALUE_OF_LINE(col);
    col &=~ (1 << (1-p+y+y));
    score += VALUE_OF_LINE(col);
    board_cols[x] = col;

    board_score += score;

    -- board_remainder;
    CHECK_BOARD
}
void Position::unmove(int p, int x, int y)
{
    CHECK_BOARD

    int row = board_rows[y];
    int score = - VALUE_OF_LINE(row);
    row |= (3 << (x+x));
    score += VALUE_OF_LINE(row);
    board_rows[y] = row;

    int col = board_cols[x];
    score -= VALUE_OF_LINE(col);
    col |= (3 << (y+y));
    score += VALUE_OF_LINE(col);
    board_cols[x] = col;

    board_score += score;

    ++ board_remainder;
    CHECK_BOARD
}

//---------------------------------------------------------------------------

Position::Position(Player* pl, const char* board)
: player(pl)
{
    init_board(board);
}

void Position::init_board(const char* board)
{
    checking_board = false;
    // because board invariant will not hold during initialization,
    // and computed_board_score() below will want to check it.

    board_remainder = 49;
    for (int i = 0; i < 7; ++ i)
    {
        board_rows[i] = board_cols[i] = 0;
    }

    int delta_X = 0;

    for (int y = 0; y < 7; ++ y, ++ board)
    {
        for (int x = 0; x < 7; ++ x, ++ board)
        {
            int cell = 0;
            if (*board == 'X')
            {
               cell = 0x01;
               ++ delta_X;
               -- board_remainder;
            }
            else if (*board == 'O')
            {
               cell = 0x02;
               -- delta_X;
               -- board_remainder;
            }
            else if (*board == '-')
            {
               cell = 0x03;
               //++ board_remainder;
            }
            else if (*board == '+')
            {
               cell = 0x00;
               -- board_remainder;
            }
            else
                throw 666;

            board_rows[y] |= (cell << (x+x));
            board_cols[x] |= (cell << (y+y));
        }
    }

    board_score = computed_board_score();
    checking_board = true;
    CHECK_BOARD
}

void Position::display(::ostream & os) const
{
    for (int iRow = 0; iRow < 7; ++ iRow)
    {
       for (int iCol = 0; iCol < 7; ++ iCol)
          os << "+XO-"[(board_rows[iRow] >> (2*iCol)) & 0x03];
       os << ::endl;
    }
}


//---------------------------------------------------------------------------

int num_visited_nodes = 0;
int num_terminal_nodes = 0;

int Position::find_any_move(int & xFinal, int & yFinal) const
{
  for (int x = 0; x < 7; ++ x)
    for (int y = 0; y < 7; ++ y)
      if (is_free(x,y))
      {
        xFinal = x;
        yFinal = y;
        return true;
      }
  return false;
}

//---------------------------------------------------------------------------


#ifdef POTM_ENTRY
// this code supposes CLK_TCK==100
int mytime100() // returns time in 1/100 of second.
{
	int seconds;
	static struct tms TMS;
	times(&TMS);

	return TMS.tms_stime + TMS.tms_utime;
}
// POTM contestants, mind this:
//    clock() goes with CLOCKS_PER_SEC
//    times() goes with CLK_TCK
// these two timing functions have precision ~1/100 sec. on Fred's machine
// but CLOCKS_PER_SEC == 100000 or so.
#else
int mytime100() { return clock() / (CLOCKS_PER_SEC / 100); }
#endif

void Player::init_time_check(double delay)
{
    time_limit = mytime100() + 100 * delay;
}

void Player::time_check()
{
    int t = mytime100();
    if (t >= time_limit)
        longjmp(_jmpBuffer, 1);
}

//---------------------------------------------------------------------------

#define MOVE_OF_XY(x,y) ((x)+8*(y))
#define WRITE_XY_OF_MOVE(m,x,y) { x=(m)%8; y=(m)/8; }

int Player::evaluate(
    int depth, int min_value /*alpha*/, int max_value /*beta*/,
    // moves AT PREVIOUS LEVEL:
    ValuedMove moves[], int num_moves
    )
    //--- implicit arguments (members of Player or globals):
    //  int  _currentPosition;
    //  int  _xFinal, _yFinal;   // best move at first level
    //  bool _isExhaustiveSoFar;       // was search exhaustive so far ?
    //+++ all stats: num_visited_nodes etc.
{
    PROFILE(visited_nodes);

    #ifdef VERBOSE
    {{{
    CERR << "enter [evaluate] depth=" << depth
         << " window=[" << min_value << ".." << max_value << "]"
         << " player=" << "XO"[_currentPosition.get_player()] << ::endl
         << "position=\n" << _currentPosition
         << "current X value= " << _currentPosition.get_board_score_for_X()
         << ::endl
         << "moves=";
    for (int i = 0; i < num_moves; ++ i)
        CERR << " " << moves[i].x << ":" << moves[i].y;
    CERR << ::endl << ::endl;
    }}}
    #endif

    int player = _currentPosition.get_player();

    //---- TIME CHECK ----
    if (depth <= _currentMaxFullDepth - 2) // not too often...
        time_check();

    //---- TERMINAL NODES: ---- (these are not currently hashed)

    if (depth == _currentMaxFullDepth || num_moves == 0)
    {
        #ifdef PROFILING
        PROFILE(search_terminal_nodes);
        if (num_moves == 0)
            PROFILE(game_terminal_nodes);
        #endif

        if (num_moves != 0)
            _isExhaustiveSoFar = false;

        int value = sign_of_player[player] *
                      _currentPosition.get_board_score_for_X();

        #ifdef VERBOSE
        CERR << "terminal node, value = " << value << ::endl << ::endl;
        #endif

        return value;
    }

    //---- NON-TERMINAL NODES: ----

    // known bounds on the value of the position (from the hash table):
    // (for current depth !!!)
    int knownMinBound = - infinity;
    int knownMaxBound = infinity;

    // best move so far - maybe the hash move -
    //     move that guarantees knownMinBound:
    int bestMove = -1;

    // hash move:
    int hashMove = -1;

    PtHash::Index iHash = _hashTable.getHash(_currentPosition.get_board());
    if (_hashTable.isPresent(iHash, _currentPosition.get_board()))
    {
        PROFILE(hash_hits);

        #ifdef VERBOSE
        CERR << "found in hash as #" << iHash << ":" << ::endl;
        CERR << "  hash-depth=" << _hashTable.getDepth(iHash) << ::endl;
        CERR << "  hash-value " << _hashTable.getMinValue(iHash)
             << ".." << _hashTable.getMaxValue(iHash)
             << ::endl;
        {{{
            int dbgMove, dbgX, dbgY;
            dbgMove = _hashTable.getMove(iHash);
            WRITE_XY_OF_MOVE(dbgMove, dbgX, dbgY);
            if (dbgMove < 0)
                CERR << "  no hash-move" << ::endl;
            else
                CERR << "  hash-move " << dbgX << ":" << dbgY << ::endl;
        }}}
        CERR << ::endl;
        #endif

        int hashDepth = _hashTable.getDepth(iHash);
        if (hashDepth >= _currentMaxFullDepth - depth)
        {
            PROFILE(hash_exact_hits);

            // hash contains information at higher (hence equal) depth...
            // ...so we consider its minValue and maxValue as valid,
            //    and we merge this info with our current [alpha..beta]
            //    window.

            knownMinBound = _hashTable.getMinValue(iHash);
            if (knownMinBound >= max_value)
            {
                ASSERT(depth > 0);
                // otherwise we should return final move

                PROFILE(hash_beta_cutoff);
                return knownMinBound;
            }
            else if (knownMinBound > min_value)
            {
                min_value = knownMinBound;
                //ASSERT(); // must give a move that yields this value
            }

            knownMaxBound = _hashTable.getMaxValue(iHash);
            if (knownMaxBound <= min_value)
            {
                PROFILE(hash_alpha_cutoff);
                return knownMaxBound;
            }
            else if (knownMaxBound < max_value)
                max_value = knownMaxBound;

            // check 'a la Cavalerie d'Offenbach:
            ASSERT(knownMaxBound <= knownMaxBound);
        }

        ASSERT(min_value < max_value);
        // otherwise, we would have returned by now.

        // anyway, first move in hash is first move to try:

        hashMove = _hashTable.getMove(iHash);
        bestMove = hashMove; // in case no better move is found...
    }

    for (int iMove = -1; // [-1] means [hashMove].
         min_value < max_value && iMove < num_moves;
         ++ iMove)
    {
        int x, y, move; // choice of move:
        if (iMove == -1) // first of all, hashMove, if defined:
        {
            if (hashMove == -1)
                continue;
            //else:
            move = hashMove;
            WRITE_XY_OF_MOVE(move,x,y);
        }
        else // then non-hash moves:
        {
            x = moves[iMove].x;
            y = moves[iMove].y;
            move = MOVE_OF_XY(x,y);
            if (move == hashMove)
                continue;
        }

        _currentPosition.move(player, x, y);
        //
        ValuedMove next_moves[49];
        int num_next_moves =
            _currentPosition.update_moves(x, y, moves,num_moves, next_moves);
        //
        int value = - evaluate(depth + 1, - max_value, - min_value,
                               next_moves, num_next_moves);
        if (value > min_value)
        {
            bestMove = move;
            knownMinBound = value;
            min_value = value;
        }
        //
        _currentPosition.unmove(player, x, y);
    }

    if (min_value < max_value) // no beta cutoff ?
        knownMaxBound = min_value;
    PROFILE(hash_written_entries);
    _hashTable.write(_currentPosition.get_board(),
                     _currentMaxFullDepth - depth, // depth of examination
                     knownMinBound, knownMaxBound,
                     bestMove,
                     iHash);

    #ifdef VERBOSE
    CERR << "Written in hash #" << iHash << ":\ndepth=" << depth
         << ", player=" << "XO"[_currentPosition.get_player()]
         << ", position:\n"
         << _currentPosition
         << "value: " << knownMinBound << ".." << knownMaxBound << ::endl;
        {{{
            int dbgX, dbgY;
            WRITE_XY_OF_MOVE(bestMove, dbgX, dbgY);
            if (bestMove < 0)
                CERR << "no move" << ::endl;
            else
                CERR << "move: " << dbgX << ":" << dbgY << ::endl;
        }}}
    CERR << "end new hash entry.\n" << ::endl
         << ::endl;
    #endif

    if (depth == 0)
    {
        WRITE_XY_OF_MOVE(bestMove, _xBest, _yBest);
    }

    return min_value;
}


void Player::
iterative_deepening(
    int startDepth, int incrDepth // defaults 4, 2.
    )
{
    #ifdef PROFILING
    resetProfiles();
    int id_start100 = mytime100();
    #endif

    // current move choice:
    _xBest = -1;
    _yBest = -1;

    init_time_check(9.5);
    if (setjmp(_jmpBuffer) == 0)
    {
        for (_currentMaxFullDepth = startDepth;
             true; // non-stop !!! (unless timeout or exhaustive level)
             _currentMaxFullDepth += incrDepth)
        {
            #ifdef PROFILING
            resetProfiles();
            int start100 = mytime100();
            #endif

            ValuedMove moves[49];
            int num_moves =
                _currentPosition.init_moves(moves);

            _isExhaustiveSoFar = true;

            int value =
                this->evaluate(0, - infinity, infinity, moves, num_moves);

            #if defined(VERBOSE) || defined(PROFILING)
            CERR << "IDAB Depth " << _currentMaxFullDepth << " finds:\n"
                 << "  move " << char('A'+_xBest) << char('1'+_yBest) << "\n"
                 << "  value " << value << POTM_IO endl;
            #endif
            #ifdef PROFILING
            CERR << "IDAB Depth " << _currentMaxFullDepth << " profiles:"
                 << POTM_IO endl;
            CERR << "| spent time " << ((mytime100() - start100) * 0.01)
                 << POTM_IO endl;
            printProfiles(CERR);
            #endif

			// in my actual POTM entry, next test was mistakenly included in
			// the above #ifdef PROFILING block. This resulted in my program
			// always spending 9.6 seconds to think - even where there was
			// only one possible move left ;-)
            if (_isExhaustiveSoFar)
            {
                #ifdef PROFILING
                    CERR << "IDAB performed a full search !" << ::endl;
                #endif
                break;
            }
        }//end for
    }
    else
    {
        // return of longjmp, nothing to do !
            #if defined(VERBOSE) || defined(PROFILING)
            CERR << "Aborted IDAB Depth " << _currentMaxFullDepth
                 << "  best move so far: "
                 << char('A'+_xBest) << char('1'+_yBest)
                 << POTM_IO endl;
            #endif
            #ifdef PROFILING
            CERR << "Aborted IDAB Depth " << _currentMaxFullDepth
                 << " profiles:"
                 << POTM_IO endl;
            printProfiles(CERR);
            #endif
    }

    if (_xBest < 0)
    {
        _currentPosition.find_any_move(_xBest, _yBest);
    }

    #ifdef PROFILING
            CERR << "Total spent time in iterative_deepening: "
                 << ((mytime100() - id_start100) * 0.01) << ::endl;
    #endif
}

bool Player::checked_play(char* board)
// returns true if played; false if game is full or internal error
{
    int player = _currentPosition.get_player();
    // _currentPosition is indeterminate after iterative_deepening().

    iterative_deepening();

    if (_xBest >= 0 && _yBest >= 0 && board[_xBest + _yBest * 8] == '-')
    {
        board[_xBest + _yBest * 8] = "XO"[player];
        return true;
    }
    else
        return false;
}
void play(char* board) { Player(board).checked_play(board); }

#ifdef POTM_ENTRY
int main(int argc, char** argv)
{
    #define BOARD_DATA_SIZE (8*7)
    char board[BOARD_DATA_SIZE + 1];
    board[BOARD_DATA_SIZE] = 0;
    cin.read(board, BOARD_DATA_SIZE);

    play(board);

    cout.write(board, BOARD_DATA_SIZE);
    return 0;
}
#endif

//---------------------------------------------------------------------------
POTM_NAMESPACE_END   // you may safely ignore this line
//---------------------------------------------------------------------------