The Ecere SDK - chess/blob - src/ai.ec

   1 import "chess.ec"
   2
   3 struct MoveStack
   4 {
   5    ChessMove * moves;
   6    int size, count;
   7 };
   8
   9 define MAXDEPTH = 4;
  10 // define MAXDEPTH = 6;
  11 define MAXDEPTH_PASS2 = 50;
  12
  13 static MoveStack moveStack[MAXDEPTH_PASS2];
  14
  15 void AddMoveToList(MoveStack stack, ChessState state, PieceType type, Player player,
  16                    int x1, int y1, int x2, int y2)
  17 {
  18    if(IsMoveValid(x1,y1,x2,y2, state, null, true))
  19    {
  20       ChessMove * move;
  21
  22       if(stack.count + 1 > stack.size)
  23       {
  24          stack.size += 10000;
  25          stack.moves = renew stack.moves ChessMove[stack.size];
  26       }
  27
  28       move = &stack.moves[stack.count++];
  29
  30       move->player = player;
  31       move->type = type;
  32       move->x1 = x1;
  33       move->y1 = y1;
  34       move->x2 = x2;
  35       move->y2 = y2;
  36       // For now queen only...
  37       move->promotion = Queen;
  38    }
  39 }
  40
  41 void GeneratePieceMoveList(ChessState state, int x, int y, MoveStack stack)
  42 {
  43    Piece content = state.board[y][x];
  44    Player player = content.player;
  45    PieceType type = content.type;
  46    int x2,y2;
  47
  48    switch(type)
  49    {
  50       case Pawn:
  51       {
  52          int direction = (player == White) ? 1 : -1;
  53
  54          AddMoveToList(stack, state, type, player, x,y,x,y+direction);
  55
  56          if((player == White && y == 1) ||
  57             (player == Black && y == 6))
  58             AddMoveToList(stack, state, type, player, x,y,x,y+direction*2);
  59
  60          // Capturing Move (Including en passant)
  61          if(x > 0)
  62             AddMoveToList(stack, state, type, player, x,y,x-1,y+direction);
  63          if(x < 7)
  64             AddMoveToList(stack, state, type, player, x,y,x+1,y+direction);
  65          break;
  66       }
  67       case Knight:
  68          AddMoveToList(stack, state, type, player, x,y, x+1,y+2);
  69          AddMoveToList(stack, state, type, player, x,y, x+2,y+1);
  70          AddMoveToList(stack, state, type, player, x,y, x+2,y-1);
  71          AddMoveToList(stack, state, type, player, x,y, x+1,y-2);
  72          AddMoveToList(stack, state, type, player, x,y, x-1,y-2);
  73          AddMoveToList(stack, state, type, player, x,y, x-2,y-1);
  74          AddMoveToList(stack, state, type, player, x,y, x-2,y+1);
  75          AddMoveToList(stack, state, type, player, x,y, x-1,y+2);
  76          break;
  77       case Bishop:
  78       {
  79          for(x2 = 0; x2<8; x2++)
  80          {
  81             if(x2 != x)
  82             {
  83                y2 = y + Abs(x2 - x);
  84                if(y2 < 8)
  85                   AddMoveToList(stack, state, type, player, x,y,x2,y2);
  86                y2 = y - Abs(x2 - x);
  87                if(y2 >= 0)
  88                   AddMoveToList(stack, state, type, player, x,y,x2,y2);
  89             }
  90          }
  91          break;
  92       }
  93       case Rook:
  94          for(x2 = 0; x2<8; x2++)
  95          {
  96             if(x2 != x)
  97             {
  98                AddMoveToList(stack, state, type, player, x,y,x2,y);
  99             }
 100          }
 101          for(y2 = 0; y2<8; y2++)
 102          {
 103             if(y2 != y)
 104             {
 105                AddMoveToList(stack, state, type, player, x,y,x,y2);
 106             }
 107          }
 108          break;
 109       case Queen:
 110          for(x2 = 0; x2<8; x2++)
 111          {
 112             if(x2 != x)
 113             {
 114                y2 = y + Abs(x2 - x);
 115                if(y2 < 8)
 116                   AddMoveToList(stack, state, type, player, x,y,x2,y2);
 117                y2 = y - Abs(x2 - x);
 118                if(y2 >= 0)
 119                   AddMoveToList(stack, state, type, player, x,y,x2,y2);
 120             }
 121          }
 122          for(x2 = 0; x2<8; x2++)
 123          {
 124             if(x2 != x)
 125             {
 126                AddMoveToList(stack, state, type, player, x,y,x2,y);
 127             }
 128          }
 129          for(y2 = 0; y2<8; y2++)
 130          {
 131             if(y2 != y)
 132             {
 133                AddMoveToList(stack, state, type, player, x,y,x,y2);
 134             }
 135          }
 136          break;
 137       case King:
 138          AddMoveToList(stack, state, type, player, x,y, x,y+1);
 139          AddMoveToList(stack, state, type, player, x,y, x+1,y+1);
 140          AddMoveToList(stack, state, type, player, x,y, x+1,y);
 141          AddMoveToList(stack, state, type, player, x,y, x+1,y-1);
 142          AddMoveToList(stack, state, type, player, x,y, x,y-1);
 143          AddMoveToList(stack, state, type, player, x,y, x-1,y-1);
 144          AddMoveToList(stack, state, type, player, x,y, x-1,y);
 145          AddMoveToList(stack, state, type, player, x,y, x-1,y+1);
 146
 147          // Castle
 148          AddMoveToList(stack, state, type, player, x,y, x-2,y);
 149          AddMoveToList(stack, state, type, player, x,y, x+2,y);
 150          break;
 151    }
 152 }
 153
 154 void GenerateMoveList(ChessState state, MoveStack stack)
 155 {
 156    int x,y;
 157
 158    stack.count = 0;
 159    for(x = 0; x<8; x++)
 160       for(y = 0; y<8; y++)
 161       {
 162          Piece content = state.board[y][x];
 163          if(content && content.player == state.turn)
 164             GeneratePieceMoveList(state, x,y, stack);
 165       }
 166 }
 167
 168 int EvaluateMaterial(Piece board[8][8], Player turn)
 169 {
 170    int x,y;
 171    int materialMe = 0, materialOpp = 0;
 172
 173    for(y = 0; y<8; y++)
 174       for(x = 0; x<8; x++)
 175       {
 176          Piece content = board[y][x];
 177          if(content != Piece {})
 178          {
 179             Player player = content.player;
 180             PieceType piece = content.type;
 181
 182             if(player == turn)
 183                materialMe += materialValues[piece];
 184             else
 185                materialOpp += materialValues[piece];
 186          }
 187       }
 188    return materialMe - materialOpp;
 189 }
 190
 191 int EvaluatePosition(ChessState state, Player turn)
 192 {
 193    int position = 0;
 194
 195    // To help the mate...
 196    if(state.materialValue[White] < 7)
 197    {
 198       if((state.kings[White].x >= 3 && state.kings[White].x <= 4) &&
 199          (state.kings[White].y >= 3 && state.kings[White].y <= 4))
 200       {
 201          position -= 3;
 202       }
 203       else if((state.kings[White].x >= 2 && state.kings[White].x <= 5) &&
 204               (state.kings[White].y >= 2 && state.kings[White].y <= 5))
 205       {
 206          position -= 2;
 207       }
 208       else if((state.kings[White].x >= 1 && state.kings[White].x <= 6) &&
 209               (state.kings[White].y >= 1 && state.kings[White].y <= 6))
 210       {
 211          position -= 1;
 212       }
 213    }
 214
 215    // Castle
 216    if(state.castled[White]) position -= 15;
 217    if(state.castled[Black]) position += 15;
 218    return position;
 219 }
 220
 221 static int CompareGreater(const ChessMove a, const ChessMove b)
 222 {
 223    if(a.rating > b.rating) return 1;
 224    else if(a.rating < b.rating) return -1;
 225    else
 226    {
 227       if(a.count < b.count) return 1;
 228       else if(a.count > b.count) return -1;
 229       else
 230          return 0;
 231    }
 232 }
 233
 234 static int CompareSmaller(const ChessMove a, const ChessMove b)
 235 {
 236    if(a.rating < b.rating) return 1;
 237    else if(a.rating > b.rating) return -1;
 238    else
 239    {
 240       if(a.count > b.count) return 1;
 241       else if(a.count < b.count) return -1;
 242       else
 243          return 0;
 244    }
 245 }
 246
 247 bool FindMove(ChessState startState, int depth, int *maxDepth, ChessMove bestMove, int startRating, int * returnedRating,
 248               int startCount, int * returnedCount, bool * abort)
 249 {
 250    Player player = startState.turn;
 251    MoveStack * stack = &moveStack[depth];
 252    int bestRating = (player == Black) ? MININT : 200000;
 253    int c;
 254    int bestCount = MAXINT;
 255    int maxShots = stack->count;
 256
 257    // Stop AI
 258    if(*abort) return false;
 259
 260    GenerateMoveList(startState, stack);
 261    if(!stack->count && !Check(startState, player, startState.kings[player].x, startState.kings[player].y))
 262       bestRating = 0;
 263
 264    if(!stack->count)
 265       bestCount = startCount;
 266
 267    maxShots = stack->count;
 268    for(c = 0; c<maxShots; c++)
 269    {
 270       ChessMove * move = &stack->moves[c];
 271       int newRating, newCount = MAXINT;
 272       int delta = 0;
 273       ChessState state = startState;
 274
 275       StateMakeMove(&state, move->x1, move->y1, move->x2, move->y2, move->promotion, false, &delta);
 276       if(player == White)
 277          delta *= -1;
 278
 279       if(Abs(delta) < 1000 && (depth+1 < *maxDepth))
 280       {
 281          FindMove(&state, depth+1, maxDepth, null, startRating + delta, &newRating, startCount+1, &newCount, abort);
 282       }
 283       else
 284       {
 285          int position;
 286          position = EvaluatePosition(&state, player);
 287          newRating = startRating + delta + position;
 288
 289          if((player == Black) ? (newRating > bestRating) : (newRating < bestRating))
 290             newCount = startCount+1;
 291       }
 292
 293       move->rating = newRating;
 294       move->count = newCount;
 295
 296       if((player == Black) ? (newRating >= bestRating) : (newRating <= bestRating))
 297       {
 298          bestRating = newRating;
 299          if(move->count < bestCount)
 300             bestCount = move->count;
 301       }
 302    }
 303    stack->count = maxShots;
 304
 305    // Pass 2
 306    if(bestMove && stack->count)
 307    {
 308       int numGoodMoves;
 309       if(player == Black)
 310          qsort(stack->moves, stack->count, sizeof(ChessMove), CompareSmaller);
 311       else
 312          qsort(stack->moves, stack->count, sizeof(ChessMove), CompareGreater);
 313
 314       for(numGoodMoves = 0; numGoodMoves<stack->count; numGoodMoves++)
 315       {
 316          if(stack->moves[numGoodMoves].rating != bestRating)
 317             break;
 318          if(stack->moves[numGoodMoves].count != bestCount)
 319             break;
 320       }
 321
 322       c = GetRandom(0, numGoodMoves-1);
 323       bestMove = stack->moves[c];
 324    }
 325    if(returnedRating)
 326       *returnedRating = bestRating;
 327    if(returnedCount)
 328       *returnedCount = bestCount;
 329    Sleep(0);
 330
 331    return stack->count > 0;
 332 }
 333
 334 class AIThread : Thread
 335 {
 336    Chess chess;
 337    bool aiMoveResult;
 338    bool abortAI;
 339    ChessMove aiMove;
 340
 341    Timer aiTimer
 342    {
 343       this, 0.1;
 344
 345       bool DelayExpired()
 346       {
 347          if(aiMoveResult)
 348          {
 349             Wait();
 350             chess.MakeMove(aiMove.x1, aiMove.y1, aiMove.x2, aiMove.y2, aiMove.promotion);
 351             aiMoveResult = false;
 352             aiTimer.Stop();
 353          }
 354          return true;
 355       }
 356    };
 357
 358    void Play()
 359    {
 360       abortAI = false;
 361       app.UpdateDisplay();
 362       Create();
 363       aiTimer.Start();
 364    }
 365
 366    void Abort()
 367    {
 368       abortAI = true;
 369       Wait();
 370       aiTimer.Stop();
 371       aiMoveResult = false;
 372    }
 373
 374    ChessState * chessState;
 375
 376    uint Main()
 377    {
 378       ChessState * chessState = chess.chessState;
 379       int startRating = EvaluateMaterial(chessState->board, chessState->turn);
 380       int depth = MAXDEPTH;
 381
 382       RandomSeed((int)(GetTime() * 1000));
 383       aiMoveResult = FindMove(chessState, 0, &depth, &aiMove, startRating, null, 0, null, &abortAI);
 384
 385       return 0;
 386    }
 387
 388 public:
 389    property Chess chess { set { chess = value; } }
 390    property ChessState * chessState { set { chessState = value; } }
 391 }