/*
 * ai.c
 *
 * An implementation of computer intelligence (you wot?) for 3Dc.
 */
/*

    3Dc, a game of 3-Dimensional Chess
    Copyright (C) 1995,1996  Paul Hicks

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    E-Mail: paulh@euristix.ie
*/
#ifdef DEBUG
#include <stdio.h>
#endif /* DEBUG */

#include <stdlib.h>
#include <limits.h>
#include <sys/time.h>

#include "machine.h"
#include "3Dc.h"

#ifndef MAX
#define MAX(a,b) ((a) < (b) ? (b) : (a))
#define MIN(a,b) ((a) > (b) ? (b) : (a))
#endif /* MAX */

#define BEST_STACKS 5
Local struct stackList
{
  stack *stacks[BEST_STACKS];
  int   ratings[BEST_STACKS];
} bestMoves = {
{ NULL, NULL, NULL, NULL, NULL },
{ INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN }
};

Local int values[ TITLES ] = 
{
  26, 42, 22, 10, 25, /* Royalty */
  45, 21, 12, 24, 15, /* Nobility */
  6 /* Pawn */
};


Local void
PushMove(Move *move, int value)
{
  int i;

  if ( value == INT_MIN )
    return;

  for ( i = 0; (bestMoves.stacks [i] != NULL) &&
               (bestMoves.ratings[i] > value) &&
               (i < BEST_STACKS);
       ++i )
    nop();

  if ( i == BEST_STACKS )
    {
      free( move );
      return;
    }

  if ( bestMoves.ratings[i] == value )
    {
      StackPush( bestMoves.stacks[i], move );
      free( move );
    }
  else
    {
      int j;

      j = BEST_STACKS-1;

      /* Get rid of the lowest level (if it falls off the end) */
      if (bestMoves.stacks[j] != NULL)
        StackDelete( bestMoves.stacks[j] );

      /* Move all the lower levels down */
      for (; j > i; --j)
        {
          bestMoves.stacks [j] = bestMoves.stacks [j-1];
          bestMoves.ratings[j] = bestMoves.ratings[j-1];
        }

      /* Create the new stack */
      bestMoves.stacks[i] = StackNew();
      StackPush( bestMoves.stacks[i], move );
      bestMoves.ratings[i] = value;
    }

  return;
}

/* This function circumvents the problem of negative ratings
 * by adding to all ratings enough to make the smallest rating == 0 */
Local void
FixMoves( void )
{
  int i, add;

  for ( i = (BEST_STACKS -1); (bestMoves.stacks[i] == NULL) && (i >= 0); --i )
    nop();

  if ((i < 0) || (bestMoves.ratings[i] >= 0))
    return;

  add = -(bestMoves.ratings[i]);

  for (; i >= 0; --i)
    bestMoves.ratings[i] += add;
     
}

Local Move *
PopMove( void )
{
  Move *ret;
  int stacks, randStack, randMove, randBase, randNum;

  if ( bestMoves.stacks[0] == NULL )
    return NULL;

  /*
   * This algorithm works by generating a number randBase on which to base a
   * call to random(): think of it as a die with randBase sides.  randBase
   * it dependant on the rating of the moves at the current level and
   * on the level itself.  It may be that the number of moves at the current
   * level will also be a factor in later version.  (A "level" is all moves
   * with equal rating.  Only the top BEST_STACKS levels are remembered).
   * Then the generated random number is reverse engineered into a level.
   * Finally a purely random choice of move within that level is made.
   */
  if ( bestMoves.ratings[0] == INT_MAX )
    {
      /* If this move wins the game then do it unconditionally */
      randMove = 0;
      randStack = 0;
    }
  else
    {
      for ( stacks = 0, randBase = 0;
           ( bestMoves.stacks[stacks] != NULL ) &&
           ( stacks < BEST_STACKS ) ;
           ++stacks )
        randBase += ((BEST_STACKS-stacks) * bestMoves.ratings[stacks]);

      randNum = random()%randBase;

      for ( randStack = stacks-1;
           (randStack > 0) && (randNum > 0); --randStack )
        {
          randNum -= (( BEST_STACKS - randStack ) *
                      bestMoves.ratings[randStack] );
        }

      randMove = random()%bestMoves.stacks[randStack]->nSize;
      D( printf( "Choosing move %i from a stack of size %i\n",
                randMove+1, bestMoves.stacks[randStack]->nSize ) );
    }

  ret = StackPeek( bestMoves.stacks[randStack], randMove );
  CHECK((ret->xyzBefore.zLevel != 3) && (ret->xyzAfter.zLevel != 3));

  /* This defeats the opaqueness of stack.c but it's easy */
  /* It just clears the one move we've just made from the move stack */

  /* If the chosen move was the top of the stack.. */
  if (randMove == 0)
    {
      /* Don't free the move: it's "ret" and still in use! */
      StackPop( bestMoves.stacks[randStack] );

      /* If there is only the one move then we remove the stack */
      if ( bestMoves.stacks[randStack]->nSize == 0 )
        {
          StackDelete( bestMoves.stacks[randStack] );

          while ( ((randStack+1) < BEST_STACKS) &&
                  (bestMoves.stacks[randStack+1] != NULL) )
            {
              bestMoves.stacks [randStack] = bestMoves.stacks [randStack+1];
              bestMoves.ratings[randStack] = bestMoves.ratings[randStack+1];
              ++randStack;
            }

          bestMoves.stacks[randStack] = NULL;
          bestMoves.ratings[randStack] = INT_MIN;
        }
    }
  /* We used a second or later move */
  else
    {
      int i;
      struct stack_el *el, *temp;

      el = bestMoves.stacks[randStack]->top;

      for (i = 1; (i < randMove) && (el->below != NULL); ++i)
        {
          el = el->below;
        }

      if (!CHECK((el->below != NULL) && (el->below->mvt == ret)))
        {
          /* Hopefully this can never happen */
        }
      else
        {
          temp = el->below;
          el->below = temp->below;
          bestMoves.stacks[randStack]->nSize--;
          free( temp );
        }
    }
  
  return ret;
}

Local int
RateMove( Move *move, Colour bwSide )
{
  int rating = 0;
  Colour bwEnemy;
  Coord xyzPos;
  Piece *moving, *storing;
  bwEnemy = ( bwSide == WHITE ) ? BLACK : WHITE;

  /* Rate taking king */
  if (move->pVictim == Muster[ bwEnemy ][ MusterIdx( king, 0 )])
    return INT_MAX;

  /* Fake the move for simple lookahead */
  moving  = Board[ move->xyzBefore.zLevel ]
                 [ move->xyzBefore.yRank ]
                 [ move->xyzBefore.xFile ];
  storing = Board[ move->xyzAfter.zLevel ]
                 [ move->xyzAfter.yRank ]
                 [ move->xyzAfter.xFile ];

  if (!CHECK( moving != NULL ))
    return INT_MIN;

  /* Rate saving king */
  /* It might be more efficient to put the IsKingChecked() call
   * inside the move faked below but that would mean nasty code
   * duplication re: finding king coords and so on.  This code
   * is easier to maintain. */
  if ( FakeMoveAndIsKingChecked( Muster[ bwSide ][ MusterIdx( king, 0 )],
                                 move->xyzAfter.xFile,
                                 move->xyzAfter.yRank,
                                 move->xyzAfter.zLevel ))
    return INT_MIN;

  /* Fake the move */
  Board[ move->xyzBefore.zLevel ]
       [ move->xyzBefore.yRank ]
       [ move->xyzBefore.xFile ] = NULL;
  Board[ move->xyzAfter.zLevel ]
       [ move->xyzAfter.yRank ]
       [ move->xyzAfter.xFile ] = moving;
  if ( storing != NULL )
    storing->bVisible = FALSE;

  /* Rate check */
  xyzPos = (Muster[ bwEnemy ][ MusterIdx( king, 0 )])->xyzPos;
  if ( SquareThreatened( bwSide,
            xyzPos.xFile, xyzPos.yRank, xyzPos.zLevel) != NULL )
    rating += values[ king ];

  /* Rate danger: if there's a chance of being captured in the new pos. */
  xyzPos = move->xyzAfter;
  if ( SquareThreatened( bwEnemy,
            xyzPos.xFile, xyzPos.yRank, xyzPos.zLevel) != NULL )
    rating -= (values[ moving->nName ] /2);

  /* Undo the fake */
  Board[ move->xyzBefore.zLevel ]
       [ move->xyzBefore.yRank ]
       [ move->xyzBefore.xFile ] = moving;
  Board[ move->xyzAfter.zLevel ]
       [ move->xyzAfter.yRank ]
       [ move->xyzAfter.xFile ] = storing;
  if ( storing != NULL )
    storing->bVisible = TRUE;

  /* Rate capture */
  if (( move->pVictim != NULL ) &&
      ( move->pVictim->bwSide == bwEnemy ))
    {
      int i;

      rating += values[ move->pVictim->nName ];

      /* Rate evasion: if there's a chance of any friendly piece
       * being captured in the old pos but not in the new (this isn't
       * an authorative check and needs to be enhanced). */
      for ( i = 0; i < PIECES; ++i )
        {
          if ( Muster[ bwSide ][ i ]->bVisible &&
               SquareThreatened( bwEnemy,
                                 Muster[ bwSide ][ i ]->xyzPos.xFile,
                                 Muster[ bwSide ][ i ]->xyzPos.yRank,
                                 Muster[ bwSide ][ i ]->xyzPos.zLevel ) ==
              move->pVictim )
            rating += (values[ Muster[ bwSide ][ i ]->nName ] /2);
        }
    }

  /* Rate special moves */
  /* En passant and castling not yet possible for computer */
  if (( move->pVictim != NULL ) &&
      ( move->pVictim->bwSide == bwSide))
    rating += 10; /* Castling */
  if (( move->xyzAfter.yRank == (bwSide == WHITE ? RANKS-1 : 0) ) &&
      ( moving->nName == pawn ))
    rating += values[queen]; /* Promotion */
  /* Note the horrible magic numbers below */
  if ( (ABS( move->xyzAfter.yRank - move->xyzBefore.yRank ) == 2) &&
      ( moving->nName == pawn ))
    rating += 1; /* Two-forward by pawn: the computer doesn't
                  * usually like opening its attack routes otherwise */

  /* Rate position; distance forward (should be proximity to
   * enemy king except for pawns */
  if ( bwSide == WHITE )
    rating += move->xyzAfter.yRank - move->xyzBefore.yRank;
  else
    rating += 7 - move->xyzAfter.yRank + move->xyzBefore.yRank;

  return rating;
}

Global Boolean
GenMove(const Colour bwSide, Move **ret)
{
  Local int pieceIdx = 0;
  stack *moves;
  Move *thisMove;

  /* First clear out any old moves */
  if (pieceIdx == 0)
    {
      int i;
      
      for ( i = 0; (bestMoves.stacks[i] != NULL) && (i < BEST_STACKS); ++i)
        {
          StackDelete(bestMoves.stacks[i]);
          bestMoves.stacks[i] = NULL;
          bestMoves.ratings[i] = INT_MIN;
        }
    }

  if ( Muster[bwSide][pieceIdx]->bVisible )
    {
      moves = FindAllMoves( Muster[bwSide][pieceIdx] );
      if (moves != NULL)
        {
#         ifdef NOTDEF
          StackDump( moves );
#         endif /* DEBUG */

          while ( (thisMove = StackPop( moves )) != NULL )
            {
              PushMove( thisMove, RateMove( thisMove, bwSide ) );
            }

          StackDelete( moves );
        }
    }

  if (++pieceIdx == PIECES)
    {
      FixMoves();
      *ret = PopMove();
      pieceIdx = 0;
      return TRUE;
    }

  *ret = NULL;
  return FALSE;
}

/* This tries again for a move in case the last one failed for some reason */
Global Boolean
GenAltMove(const Colour bwSide, Move **ret)
{
  *ret = PopMove();
  return TRUE;
}

/* Creates a stack of legal moves that this piece can take in this go */
stack *
FindAllMoves(Piece *piece)
{
  stack *moves;
  Move move;
  Colour bwEnemy;
  int x, y, z;

#define CURX (piece->xyzPos.xFile)
#define CURY (piece->xyzPos.yRank)
#define CURZ (piece->xyzPos.zLevel)

  moves = StackNew();
  if (moves == NULL)
    return NULL;

  bwEnemy = ((piece->bwSide == WHITE) ? BLACK : WHITE);
  move.xyzBefore = piece->xyzPos;

  if (piece->nName == knight)
    {
      for (y = MAX(0, CURY -2); y < MIN(RANKS, CURY +3); y++)
        {
          if (y == CURY)
            continue;
          for (x = MAX(0, CURX -2); x < MIN(FILES, CURX +3); x++)
            {
              if (x == CURX)
                continue;

              if (ABS(CURX-x) == ABS(CURY-y))
                continue;

              if ((Board[CURZ][y][x] == NULL) ||
                  (Board[CURZ][y][x]->bwSide == bwEnemy))
                {
                  move.xyzAfter.xFile = x;
                  move.xyzAfter.yRank = y;
                  move.xyzAfter.zLevel = CURZ;
                  move.pVictim = Board[CURZ][y][x];
                  move.nHadMoved = piece->bHasMoved;

                  if (!FakeMoveAndIsKingChecked( piece, x, y, CURZ ))
                    StackPush(moves, &move);
                } /* End valid move */
            } /* End x loop */
        } /* End y loop */
    } /* End knight */
  else if (piece->nName == cannon)
    {
      for (z = 0; z < LEVELS; z++)
        {
          if (z == CURZ)
            continue;

          for (y = MAX( 0, CURY -3 ); y < MIN( RANKS, CURY +4 ); y++)
            {
              if (y == CURY)
                continue;

              for (x = MAX( 0, CURX -3 ); x < MIN( FILES, CURX +4 ); x++)
                {
                  if (x == CURX)
                    continue;

                  if ((ABS(CURX-x) == ABS(CURY-y)) ||
                      (ABS(CURX-x) == ABS(CURZ-z)) ||
                      (ABS(CURY-y) == ABS(CURZ-z)))
                    continue;

                  if ((Board[z][y][x] == NULL) ||
                      (Board[z][y][x]->bwSide == bwEnemy))
                    {
                      move.xyzAfter.xFile = x;
                      move.xyzAfter.yRank = y;
                      move.xyzAfter.zLevel = z;
                      move.pVictim = Board[z][y][x];
                      move.nHadMoved = piece->bHasMoved;

                      if (!FakeMoveAndIsKingChecked( piece, x, y, z ))
                        StackPush(moves, &move);
                    } /* End valid move */
                } /* End x loop */
            } /* End y loop */
        } /* End z loop */
    } /* End cannon */
  else if (piece->nName == pawn) /* Don't bother searching for en passant */
    {
      y = ((piece->bwSide == WHITE) ? 1 : -1);

      for (x = MAX(0, CURX-1); x < MIN(FILES, CURX+2); ++x)
        {
          /* Due to the complexity of the conditional this time,
           * I've opted for aborting when illegal instead of
           * proceeding when legal. */
          if ((x == CURX) && (Board[CURZ][CURY+y][CURX] != NULL))
            continue;

          if ( (x != CURX) &&
              ((Board[CURZ][CURY + y][x] == NULL) ||
               ((Board[CURZ][CURY + y][x])->bwSide != bwEnemy)) )
            continue;

          move.xyzAfter.xFile = x;
          move.xyzAfter.yRank = CURY + y;
          move.xyzAfter.zLevel = CURZ;
          move.pVictim = Board[CURZ][CURY + y][x];
          move.nHadMoved = piece->bHasMoved;

          if (!FakeMoveAndIsKingChecked(piece, x, CURY+y, CURZ))
            StackPush(moves, &move);

          /* This next conditional is for the two-forward move:
           * it only happens when the previous attempt was the one-forward
           * move and makes assumptions based on that fact. */
          if ( (x==CURX) && (piece->bHasMoved == FALSE) &&
              (Board[CURZ][CURY + y+y][CURX] == NULL) )
            {
              move.xyzAfter.yRank += y;
              if (!FakeMoveAndIsKingChecked(piece, CURX, CURY+y+y, CURZ))
                StackPush(moves, &move);
            }
        } /* End x loop */
    } /* End pawn */
  else
    {
      int d, dist;
      Piece *pEncountered;

      /*
       * The king and prince can only move one square;
       * all others can move MAX(FILES,RANKS)-1.
       * For a regular board, this is 7.  (Not 8: If you moved 8
       * in any direction you would be off the edge of the board)
       */
      if ((piece->nName == king) ||
          (piece->nName == prince))
        dist = 1;
      else
        dist = MAX(FILES, RANKS) -1;

      for (z = -1; z <= 1; ++z)
      {
       /*
        * Cater for pieces that can't change level.
        */
       if (((piece->nName == prince) ||
            (piece->nName == princess) ||
            (piece->nName == abbey) ||
            (piece->nName == galley)) &&
           (z != 0))
         continue;

       for (y = -1; y <= 1; ++y)
       {
         for (x = -1; x <= 1; ++x)
         {
           if ((x==0) && (y==0) && (z==0))
             continue;

           /*
            * Cater for the pieces that can only move
            * horizontally/vertically.
            */
           if (((piece->nName == rook) ||
                (piece->nName == galley)) &&
               !HORZ(x, y))
             continue;
           /*
            * Cater for the pieces that can only move
            * diagonally.
            */
           else if (((piece->nName == bishop) ||
                     (piece->nName == abbey)) &&
                    !DIAG(x, y))
             continue;

           for (d = 1; d <= dist; ++d)
           {
             pEncountered = TraverseDir(piece, x, y, z, d);
             if (IsMoveLegal(piece, pEncountered))
               {
                 move.xyzAfter = pEncountered->xyzPos;
                 move.pVictim = pEncountered;
                 move.nHadMoved = piece->bHasMoved;

                 /* Check for putting own king in check */
                 if (!FakeMoveAndIsKingChecked(piece,
                                               pEncountered->xyzPos.xFile,
                                               pEncountered->xyzPos.yRank,
                                               pEncountered->xyzPos.zLevel))
                   StackPush(moves, &move);
               }

             if (pEncountered != SQUARE_EMPTY)
               break; /* No point on continuing in this direction if
                       * we've hit a piece or the edge of the board.. */
           } /* End d loop */
         } /* End x loop */
       } /* End y loop */
     } /* End z loop */
    }

  return moves;

#undef CURX
#undef CURY
#undef CURZ
}