added .gitignore for all to enjoy
[chess] / 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 }