unsigned long a;
unsigned char max_depth;
int global_deadend_score = DEADEND_SCORE;
int deadend_limit = DEADEND_DEPTH_LIMIT;

int check_stale(struct board *brd, struct coord king_pos, unsigned char depth, unsigned char *reps);

long int sub_score(long int *score, unsigned add)
{
  long int retval = *score - add;
  if(retval > *score)
    retval = LONG_MIN;

  return retval;
}

unsigned ascend_value(unsigned char piece)
{
  if(piece == PC_QUEEN) return QUEEN_VALUE/2;
  else if(piece == PC_BISHOP) return BISHOP_VALUE/2;
  else if(piece == PC_ROOK) return ROOK_VALUE/2;
  else return KNIGHT_VALUE/2;
}

// return larger number if the opponent has more royal pieces
signed char rate_move(struct move *move, struct board *brd, unsigned char turn)
{
  struct board temp;
  static unsigned char depth = 0;
  struct move lmove;
  struct move opmax;
  struct coord moves[MAX_MOVES];
  struct coord pc_coords;
  struct coord king_pos;
  unsigned char move_count;

  struct piece_count cur_op_pc_count;
  struct piece_count mov_op_pc_count;
  struct piece_count cur_my_pc_count;

  unsigned char ascend_required;
  unsigned char ascend;
  int32_t ascend_max_score;
  int32_t noascend_score;
  unsigned char stale;
  unsigned char piece;
  unsigned char capture;
  unsigned legal_move_count;
  unsigned char non_aggressiveness;
  signed char s, r, q;
  short int check_score = CHECK_SCORE;
  short int deadend_score = global_deadend_score;
  unsigned short pawn_move_score = PAWN_MOVE_SCORE;
  unsigned pawn_value = PAWN_VALUE;
  unsigned char reps = 1;

#define OPP_MOVE (!(depth & 1))


  move->staledraw = move->ascend = move->score = 0;
  move->checkmate_found = UCHAR_MAX;

  if(depth >= max_depth)
    goto end;

//  fprintf(stderr, "%c%c-%c%c ", 'a' + move->src.col, 7-move->src.row+'1',
//                                'a' + move->dst.col, 7-move->dst.row+'1');

  temp = *brd;

  depth++;

  piece_count(brd, !turn, &cur_op_pc_count);

  piece_count(brd, turn, &cur_my_pc_count);

  // be very aggressive at beginning and endgame
  s = cur_op_pc_count.queen_count * 2 + cur_op_pc_count.rook_count + ((cur_op_pc_count.bishop_count + cur_op_pc_count.knight_count) >> 1);
  r = cur_my_pc_count.queen_count * 2 + cur_my_pc_count.rook_count + ((cur_my_pc_count.bishop_count + cur_my_pc_count.knight_count) >> 1);
  piece = piece_in_tile(brd, move->coords.src.row, move->coords.src.col);
  if(s <= 1)
  {
    non_aggressiveness = 1;
    if(s <= 2)
    {
      capture = piece_in_tile(brd, move->coords.src.row, move->coords.src.col);
      if(capture && (capture & 0x7) < PC_ROOK)
        pawn_value <<= 2;
    }
    if(r <= 2)
    {
      pawn_value <<= 2;
      pawn_move_score <<= 4;
      pawn_move_score *= (piece & PC_BLACK) ? move->coords.src.row : 7 - move->coords.src.row;
    }
    if(!s)
    {
      check_score = 50;
      deadend_score -= deadend_limit;
    }
  }
  else
  {
    non_aggressiveness = 1;
    if((q = cur_op_pc_count.queen_count - cur_my_pc_count.queen_count) > 0)
      non_aggressiveness += q;
    if((q = cur_op_pc_count.rook_count - cur_my_pc_count.rook_count) > 0)
      non_aggressiveness += q>>1;
    s = s - r;
  }

  a++;

  piece &= 0x7;
  if(piece == PC_KING)
  {
    if(abs(move->coords.dst.col - move->coords.src.col) == 2)
      move->score += CASTLE_SCORE;
  }

  else if(piece < PC_ROOK)
    move->score += pawn_move_score;

  ascend_required = move_piece(&temp, move->coords.src, move->coords.dst);

  king_pos = find_king(&temp, !turn);

  piece_count(&temp, !turn, &mov_op_pc_count);

  move->score += ((signed)cur_op_pc_count.queen_count - mov_op_pc_count.queen_count) * QUEEN_VALUE;
  move->score += ((signed)cur_op_pc_count.rook_count - mov_op_pc_count.rook_count) * ROOK_VALUE;
  move->score += ((signed)cur_op_pc_count.knight_count - mov_op_pc_count.knight_count) * KNIGHT_VALUE;
  move->score += ((signed)cur_op_pc_count.bishop_count - mov_op_pc_count.bishop_count) * BISHOP_VALUE;
  move->score += ((signed)cur_op_pc_count.pawn_count - mov_op_pc_count.pawn_count) * pawn_value;

  stale = check_stale(&temp, king_pos, depth, &reps);

  if(turn_count > 3 && stale >= 4)
  {
    if(OPP_MOVE)
      move->score += REPETITION_SCORE;
    else
      move->score -= REPETITION_SCORE;
    move->staledraw = 1;
  }
  else if(stale == 2)
  {
    if(OPP_MOVE)
      move->score += STALEMATE_SCORE;
    else
      move->score -= STALEMATE_SCORE;
    if(depth <= 2)
      move->staledraw = 1;
  }
  else if(stale == 3)
  {
    if(!OPP_MOVE)
      move->score += CHECKMATE_SCORE - depth;
    else
      move->score += CHECKMATE_SCORE / depth;
    move->checkmate_found = depth;
  }
  else
  {
    if(stale == 1 && !reps)
    {
      move->score += check_score;
    }

    if(ascend_required)
    {
      noascend_score = move->score;
      ascend_max_score = INT32_MIN;
      ascend = PC_ROOK;
    }

    do
    {
      if(ascend_required)
      {
        ascend_piece(&temp, move->coords.dst, ascend);
        stale = check_stale(&temp, king_pos, -1, 0);
        if(stale <= 1)
          move->score = noascend_score + ascend_value(ascend) + (stale ? CHECK_SCORE : 0);
        else if(stale <= 3)
        {
          if(stale == 2)
            move->score = noascend_score + (OPP_MOVE ? STALEMATE_SCORE : -STALEMATE_SCORE);
          else// if(stale == 3)
            move->score = noascend_score + ascend_value(ascend) + OPP_MOVE ? CHECKMATE_SCORE / depth : CHECKMATE_SCORE;
          goto ascend;
        }
      }

      if(!OPP_MOVE ? (move->score > deadend_score + depth * deadend_limit)
                       : (move->score < -deadend_score - depth * deadend_limit))
      {
//        fprintf(stderr, "Calculating %s move, score: %i\n", OPP_MOVE ? "opponent's" : "my", move->score);
        opmax.score = INT32_MIN;
        for(legal_move_count=0,pc_coords.row=0;pc_coords.row<8;pc_coords.row++)
          for(pc_coords.col=0;pc_coords.col<8;pc_coords.col++)
          {
            if((piece = tile_occupied(&temp, pc_coords.row, pc_coords.col))
               && !((piece & PC_BLACK) ^ ((!turn) << 3)))
            {
              move_count = legal_moves(&temp, pc_coords, &king_pos, moves);
              if(move_count)
              {
                legal_move_count += move_count;
                lmove.coords.src = pc_coords;
                while(move_count--)
                {
                  lmove.coords.dst = moves[move_count];
                  rate_move(&lmove, &temp, !turn);
                  if(opmax.score < lmove.score)
                    opmax = lmove;
                  if(lmove.staledraw)
                  {
                    if(depth < 2) move->staledraw = 1;
                  }
                  else
                  {
                    if(lmove.checkmate_found < move->checkmate_found)
                      move->checkmate_found = lmove.checkmate_found;
                    if(opmax.score >= CHECKMATE_SCORE)
                      break;
                  }
                }
              }
            }
          }
        if(turn_count > 5)
          move->score -= LEGAL_MOVE_VALUE*(legal_move_count>>depth);
        move->score -= OPP_MOVE ? opmax.score << 1 : opmax.score / (depth * non_aggressiveness);
      }
/*      else
      {
        fprintf(stderr, "Stopping to %s move, score: %i\n", OPP_MOVE ? "opponent's" : "my", move->score);
      }*/
      if(ascend_required)
      {
        ascend:
        if(ascend_max_score <= move->score)
        {
          ascend_max_score = move->score;
          move->ascend = ascend;
        }
        ascend++;
      }
      else break;
    }
    while(ascend < PC_KING);
  }

  depth--;
  end:
  return s;
}

signed char rate_move_to_depth(struct board *brd, struct move *move, unsigned char depth, unsigned char turn)
{
  signed char ret;

  max_depth = depth;
  ret = rate_move(move, brd, turn);

  if(move->checkmate_found != UCHAR_MAX)
    if(!graphics)
      printf("Found %s checkmate at depth %u\n", (move->checkmate_found & 1) ? "my" : "opponent's", move->checkmate_found);

  return ret;
}

struct piece_all_moves *all_moves;

unsigned moves_above_score(int32_t score)
{
//  unsigned char row, col;
  unsigned char n;
  unsigned char count;
  unsigned retval = 0;
  struct move *ptr;

/*  for(row=0;row<8;row++)
    for(col=0;col<8;col++)
    {
      count = all_moves[(row<<3)+col].move_count;
      while(count--)
        if(all_moves[(row<<3)+col].moves[count].score >= score)
          retval++;
    }*/

  for(n=0;n<64;n++)
  {
    count = all_moves[n].move_count;
    ptr = all_moves[n].moves;
    while(count--)
    {
      if(ptr->score >= score)
        retval++;
      ptr++;
    }
  }

  return retval;
}

int ask_resign(void)
{
  int chr;

  game_status->resign_asked = 1;

  while(1)
  {
    chr = show_dialog("Looks like I need more practice. Will you accept my resignation? (y/n)");
    if(chr == 'y' || chr == 'Y')
      return 1;
    else if(chr == 'n' || chr == 'N')
      return 0;
  }
}


unsigned calc_legal_moves(struct coord *king_pos, struct board *brd)
{
  struct coord pc_coords;
  struct piece_all_moves *piece_moves;
  unsigned retval = 0;
  unsigned char side = piece_in_tile(brd, king_pos->row, king_pos->col) & PC_BLACK;
  unsigned char piece;

  for(pc_coords.row=0;pc_coords.row<8;pc_coords.row++)
    for(pc_coords.col=0;pc_coords.col<8;pc_coords.col++)
    {
      piece = piece_in_tile(brd, pc_coords.row, pc_coords.col);
      if(!piece || (piece & PC_BLACK) != side) continue;
      piece_moves = &all_moves[(pc_coords.row<<3)+pc_coords.col];
      piece_moves->move_count = legal_moves(brd, pc_coords, king_pos, piece_moves->legal_moves);
      if(piece_moves->move_count)
      {
        memset(piece_moves->moves, 0, sizeof(piece_moves->moves));
        retval += piece_moves->move_count;
      }
    }
  return retval;
}

#define BESTVAL_LIMIT 1000

/*struct aimvstruct
{
  unsigned total_moves;
  struct move max;
  struct move max_nostale;
  struct coord pc_coords;
};*/

void reset_aimv(struct coord king_pos, struct aimvstruct *state)
{
  memset(all_moves, 0, 64*sizeof(struct piece_all_moves));
  memset(&state->max_nostale, 0, sizeof(struct move));
  state->max_nostale.score = INT32_MIN;

  memset(&state->max, 0, sizeof(struct move));
  state->max.score = INT32_MIN;

  state->total_moves = calc_legal_moves(&king_pos, &board);
  state->board = &board;
}

struct move do_ai_move(struct board *brd, struct coord king_pos, signed char *dontcommit, struct aimvstruct *state)
{
//  struct move *move;
//  struct coord *moves;
//  unsigned char move_count;
  unsigned char piece;
  char *ascends[] = { "rook", "knight", "bishop", "queen" };
  unsigned char d;
  unsigned char i;
  int32_t bestval = -CHECKMATE_SCORE + BESTVAL_LIMIT;
  struct piece_all_moves *piece_moves;
//  int32_t bestval_limit2;
  signed char s;
  long t;
  unsigned char m;
  unsigned char turn = (game_status->turn^state->phase) & 1;

  if(!dontcommit)
    if(ai_opening(&board, &state->max, -1, dontcommit))
      return state->max;

  if(!state->total_moves)
  {
//    if(ai_opening(&board, &state->max, -1, dontcommit))
//      return state->max;
    reset_aimv(king_pos, state);
    state->bestval_limit2 = 0;
  }

  if(setup.timecontrol == TIMECTRL_TIMEPERMOVE)
    d = 1;
  else if(setup.deep_thinking && state->gsmov)
  {
    d = setup.depth2;
    state->pc_coords.row = state->pc_coords.col = 0;
  }
  else
    d = setup.depth1;

//  state->bestval_limit2 = 0;
  for(a=0, i=0; d<=setup.depth2; (setup.timecontrol == TIMECTRL_TIMEPERMOVE) ? d++ : (d += setup.depth2 - setup.depth1), state->max.score = bestval = state->bestval_limit2, i++, a=0,
                                 state->pc_coords.row=0,state->pc_coords.col=0)
  {
    if(setup.timecontrol == TIMECTRL_TIMEPERMOVE)
    {
      t = time(0);
      m = 0;
      state->bestval_limit2 = 0;
    }


    for(/*state->pc_coords.row=0*/;state->pc_coords.row<8;state->pc_coords.row++,state->pc_coords.col=0)
      for(/*state->pc_coords.col=0*/;state->pc_coords.col<8;state->pc_coords.col++)
      {
        if((piece = piece_in_tile(brd, state->pc_coords.row, state->pc_coords.col))
           && !((piece & PC_BLACK) ^ (turn << 3)))
        {
          piece_moves = &all_moves[(state->pc_coords.row<<3)+state->pc_coords.col];

//          if(state->move == piece_moves->moves+(piece_moves->move_count - state->move_count-1)) //
          if(state->onemv && state->move_count > 0)
              goto onemv;

          state->move_count = piece_moves->move_count;

          if(state->move_count)
          {
            state->moves = piece_moves->legal_moves;
            state->move = piece_moves->moves;
            if(state->onemv) goto onemv;

            for(;state->move_count--;state->moves++,state->move++)
            {
//printf("%u ", state->pcmvs_rated);
              if(state->onemv)
              {
                goto make_move;
              }
              onemv:
#if defined(SDLFUNCS) || defined(DOS)
              if(graphics && !state->onemv)
              {
                print_timectrl(1);
                if(setup.timecontrol != TIMECTRL_TIMEPERMOVE)
                {
                  if(playeroutoftime())
                    goto make_move;
                }
                else
                {
                  m++;
                  if(i && ((long)time(0) - t) / m + 1 >= (long)setup.timelimit - get_move_time())
                    goto make_move;
                }
              }
#endif

              if(state->move->score < bestval)
              {
                if(!state->onemv)
                  continue;
              }

              state->move->coords.src = state->pc_coords;
              state->move->coords.dst = *state->moves;
              s = rate_move_to_depth(brd, state->move, d, turn);

              state->bestval_limit2 += state->move->score;

              if((state->move->score > state->max.score) || (state->move->score == state->max.score && !(rand() & 7)))
              {
                state->max = *state->move;
                if(state->max.staledraw)
                {
                  if(state->max_nostale.score > (-QUEEN_VALUE/2) || s < 2)
                  {
                    if(!graphics) puts("Trying to avoid draw...");
                  }
                  else goto select_stale;
                }
                else select_stale:state->max_nostale = state->max;
              }
              else if(!state->onemv && setup.blunders && !(rand() % setup.blunders) && state->move->score < state->max.score)
              {
                state->max = *state->move;
                goto make_move;
              }

              if(!state->onemv && state->max.score >= CHECKMATE_SCORE) goto make_move;
            }
          }
        }
      }

//    if(state->onemv) goto make_move;
#ifndef DEBUG
    if(!graphics)
#endif
      printf("depth %u: Analyzed %lu possible situations.\n", d, a);

    if(turn_count <= 3) break;

    if(setup.timecontrol != TIMECTRL_TIMEPERMOVE && setup.depth2 == setup.depth1) break;

    if(d != setup.depth2 || setup.timecontrol == TIMECTRL_TIMEPERMOVE)
    {
      state->bestval_limit2 /= state->total_moves;
#ifndef DEBUG
      if(!graphics)
#endif
      {
        printf("Total moves: %u, average score: %li\n", state->total_moves, (long)state->bestval_limit2);
        printf("Best move: %c%c-%c%c\n", 'a' + state->max.coords.src.col, 7-state->max.coords.src.row+'1',
                                'a' + state->max.coords.dst.col, 7-state->max.coords.dst.row+'1');
      }
      state->bestval_limit2 += (state->max.score - state->bestval_limit2) / 2;
      if(state->max.score < CHECKMATE_SCORE && (moves_above_score(state->bestval_limit2) <= 1 || state->max.score < 0))
      {
        state->bestval_limit2 = -CHECKMATE_SCORE + BESTVAL_LIMIT;
#ifndef DEBUG
        if(!graphics)
#endif
          puts("Trying to find better moves...");
      }
#ifndef DEBUG
      if(!graphics)
#endif
        printf("Recalculating moves with score >= %li using depth %u.\n", (long int)state->bestval_limit2, setup.depth2);
    }

  }

  make_move:
  state->moves_rated++;

  if(state->max.staledraw && state->max_nostale.score != INT32_MIN)
    state->max = state->max_nostale;

  if(dontcommit)
  {
    *dontcommit = s;
    return state->max;
  }

#if defined(SDLFUNCS) || defined(DOS)
  if((!setup.white_ai || !setup.black_ai) && setup.enable_clippy && s > 2 && state->max.score < QUEEN_VALUE)
    if(!game_status->resign_asked && (state->max.resign = ask_resign()))
      return state->max;
#endif

  if(!graphics)
    printf("%u: Moving %c%c to %c%c (score: %li)\n", turn_count, 'a' + state->max.coords.src.col, 7-state->max.coords.src.row+'1',
                                'a' + state->max.coords.dst.col, 7-state->max.coords.dst.row+'1', (long int)state->max.score);

  if(move_piece(&board, state->max.coords.src, state->max.coords.dst))
  {
    if(!state->max.ascend) state->max.ascend = PC_QUEEN;
    ascend_piece(&board, state->max.coords.dst, state->max.ascend);
    if(!graphics)
      printf("Ascended to %s\n", ascends[state->max.ascend - PC_ROOK]);
  }

  return state->max;
}
