micro-optimizations and checkmate

2 files changed, 172 insertions, 69 deletions

diff --git a/chess.c b/chess.c
index bd695b6..9291dba 100644
--- a/chess.c
+++ b/chess.c
@@ -1,5 +1,9 @@
 #include "chess.h"
 
+#define DEPTH 5
+
+#define AUTOMATCH
+
 int count_material(const struct chess_ctx *ctx, int color)
 {
     int total = 0;
@@ -37,7 +41,9 @@ bool count_space_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
     if(move.type == NORMAL)
     {
         int x = move.data.normal.to.x, y = move.data.normal.to.y;
-        if(ctx->board[y][x].color != NONE) /* enemy */
+        if(ctx->board[y][x].color != NONE) /* threatens an enemy piece */
+            (*count)++;
+        if((x == 3 || x == 4) && (y == 3 || y == 4)) /* controls center */
             (*count)++;
     }
     return true;
@@ -60,31 +66,45 @@ int count_space(const struct chess_ctx *ctx, int color)
     return space;
 }
 
-enum player inv_player(enum player p)
+#define inv_player(p) ((p)==WHITE?BLACK:WHITE)
+
+bool king_in_checkmate(const struct chess_ctx *ctx, int color)
 {
-    return p == WHITE ? BLACK : WHITE;
+    struct coordinates king;
+    if(king_in_check(ctx, color, &king))
+    {
+        /* no legal moves */
+        return count_space(ctx, color) == 0;
+    }
+    return false;
 }
 
 int eval_position(const struct chess_ctx *ctx, int color)
 {
     int score = 0;
 
-    score += count_material(ctx, color) * 2;
-    score -= count_material(ctx, inv_player(color)) * 3;
+    score += count_material(ctx, color) * 3;
+    score -= count_material(ctx, inv_player(color)) * 2;
     score += count_space(ctx, color);
     score -= count_space(ctx, inv_player(color));
 
-    if(king_in_check(ctx, color))
+    if(king_in_check(ctx, color, NULL))
+    {
         score -= 10;
-    else if(king_in_check(ctx, inv_player(color)))
+        if(king_in_checkmate(ctx, color))
+            score -= 2000;
+    }
+    else if(king_in_check(ctx, inv_player(color), NULL))
+    {
         score += 10;
+        if(king_in_checkmate(ctx, inv_player(color)))
+            score += 2000;
+    }
+
     return score;
 }
 
-bool valid_coords(int y, int x)
-{
-    return ((0 <= y && y <= 7) && (0 <= x && x <= 7));
-}
+#define valid_coords(y, x) ((0 <= y && y <= 7) && (0 <= x && x <= 7))
 
 const struct coordinates king_moves[] = {
     { 0, 1 },
@@ -158,6 +178,9 @@ const struct coordinates *jump_moves[] = {
     king_moves,
 };
 
+#define friendly_occupied(ctx, y, x, c) ((ctx)->board[(y)][(x)].color == NONE ? false : ((ctx)->board[(y)][(x)].color == (c)))
+
+#if 0
 bool friendly_occupied(const struct chess_ctx *ctx, int y, int x, int color)
 {
     if(!valid_coords(y, x))
@@ -177,7 +200,11 @@ bool friendly_occupied(const struct chess_ctx *ctx, int y, int x, int color)
         assert(false);
     }
 }
+#endif
+
+#define enemy_occupied(ctx, y, x, c) ((ctx)->board[(y)][(x)].color == NONE ? false : ((ctx)->board[(y)][(x)].color == inv_player(c)))
 
+#if 0
 bool enemy_occupied(const struct chess_ctx *ctx, int y, int x, int color)
 {
     if(!valid_coords(y, x))
@@ -197,15 +224,14 @@ bool enemy_occupied(const struct chess_ctx *ctx, int y, int x, int color)
         assert(false);
     }
 }
+#endif
 
-bool occupied(const struct chess_ctx *ctx, int y, int x)
-{
-    return ctx->board[y][x].color != NONE;
-}
+#define occupied(ctx, y, x) ((ctx)->board[(y)][(x)].color != NONE)
 
 struct check_info {
     int color;
     bool checked;
+    struct coordinates king;
 };
 
 bool detect_check_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
@@ -217,6 +243,8 @@ bool detect_check_cb(void *data, const struct chess_ctx *ctx, struct move_t move
             y = move.data.normal.to.y;
         if(ctx->board[y][x].type == KING && ctx->board[y][x].color == info->color)
         {
+            info->king.y = y;
+            info->king.x = x;
             info->checked = true;
             return false;
         }
@@ -224,7 +252,7 @@ bool detect_check_cb(void *data, const struct chess_ctx *ctx, struct move_t move
     return true;
 }
 
-bool king_in_check(const struct chess_ctx *ctx, int color)
+bool king_in_check(const struct chess_ctx *ctx, int color, struct coordinates *king)
 {
     struct check_info info;
     info.color = color;
@@ -235,21 +263,23 @@ bool king_in_check(const struct chess_ctx *ctx, int color)
         {
             /* check enemy pieces */
             if(ctx->board[y][x].color == inv_player(color))
+            {
                 for_each_move(ctx, y, x, detect_check_cb, &info, false);
-            if(info.checked)
-                goto early;
+                if(info.checked)
+                    goto early;
+            }
         }
     }
 early:
     if(info.checked)
     {
-        //printf("IN CHECK!!!1\n");
-        //print_ctx(ctx);
+        if(king)
+            *king = info.king;
     }
     return info.checked;
 }
 
-struct move_t construct_move(int color, int y, int x, int dy, int dx)
+inline struct move_t construct_move(int color, int y, int x, int dy, int dx)
 {
     struct move_t ret;
     ret.color = color;
@@ -259,37 +289,52 @@ struct move_t construct_move(int color, int y, int x, int dy, int dx)
     return ret;
 }
 
-bool gen_and_call(const struct chess_ctx *ctx,
-                  int y, int x,
-                  int dy, int dx,
-                  bool (*cb)(void *data, const struct chess_ctx*, struct move_t),
-                  void *data, bool enforce_check)
+inline bool gen_and_call(const struct chess_ctx *ctx,
+                         int y, int x,
+                         int dy, int dx,
+                         bool (*cb)(void *data, const struct chess_ctx*, struct move_t),
+                         void *data, bool enforce_check)
 {
     struct move_t move = construct_move(ctx->board[y][x].color,
                                         y, x,
                                         dy, dx);
+    bool promotion = false;
     /* promotion! */
     if(ctx->board[y][x].type == PAWN &&
        (y + dy == 0 || y + dy == 7))
-    {
-        move.type = PROMOTION;
-        move.data.promotion.from = (struct coordinates) { y, x  };
-        move.data.promotion.to = (struct coordinates) { y + dy, x + dx };
-        move.data.promotion.type = QUEEN;
-    }
+        promotion = true;
 
     if(enforce_check)
     {
         struct chess_ctx local = *ctx;
         execute_move(&local, move);
-        bool check_after = king_in_check(&local, ctx->board[y][x].color);
+        bool check_after = king_in_check(&local, ctx->board[y][x].color, NULL);
 
         /* move puts player in check */
         if(check_after)
             return true;
     }
 
-    return cb(data, ctx, move);
+    if(promotion)
+    {
+        move.type = PROMOTION;
+        move.data.promotion.from = (struct coordinates) { y, x  };
+        move.data.promotion.to = (struct coordinates) { y + dy, x + dx };
+
+        /* try all possible pieces */
+        enum piece promote_pieces[] = { ROOK, KNIGHT, BISHOP, QUEEN };
+        for(int i = 0; i < ARRAYLEN(promote_pieces); ++i)
+        {
+            move.data.promotion.type = promote_pieces[i];
+            if(!cb(data, ctx, move))
+                return false;
+        }
+        return true;
+    }
+    else
+    {
+        return cb(data, ctx, move);
+    }
 }
 
 void for_each_move(const struct chess_ctx *ctx,
@@ -309,8 +354,17 @@ void for_each_move(const struct chess_ctx *ctx,
     {
         /* special case */
         int dy = (piece->color == WHITE ? 1 : -1);
+
         if(!valid_coords(y + dy, x))
             break;
+
+        /* 2 squares on first move */
+        if((ctx->board[y][x].color == WHITE && y == 1) ||
+           (ctx->board[y][x].color == BLACK && y == 6))
+            if(!occupied(ctx, y + 2 * dy, x) && !occupied(ctx, y + dy, x))
+                if(!gen_and_call(ctx, y, x, 2 * dy, 0, cb, data, enforce_check))
+                    return;
+
         for(int dx = -1; dx <= 1; dx += 2)
         {
             if(enemy_occupied(ctx, y + dy, x + dx, piece->color))
@@ -319,15 +373,10 @@ void for_each_move(const struct chess_ctx *ctx,
                     return;
             }
         }
+
         if(!occupied(ctx, y + dy, x))
             if(!gen_and_call(ctx, y, x, dy, 0, cb, data, enforce_check))
                 return;
-        /* 2 squares on first move */
-        if((ctx->board[y][x].color == WHITE && y == 1) ||
-           (ctx->board[y][x].color == BLACK && y == 6))
-            if(!occupied(ctx, y + 2 * dy, x) && !occupied(ctx, y + dy, x))
-                if(!gen_and_call(ctx, y, x, 2 * dy, 0, cb, data, enforce_check))
-                    return;
         break;
     }
     case ROOK:
@@ -387,6 +436,22 @@ void for_each_move(const struct chess_ctx *ctx,
             }
             ++moves;
         }
+
+        /* castling */
+#if 0
+        if(piece->type == KING)
+        {
+            /* white = 0, black = 1 */
+            int idx = piece->color == WHITE ? 0 : 1;
+
+            if(!ctx->king_moved[idx])
+            {
+                if(!king_in_check(ctx, piece->color, NULL))
+                {
+                }
+            }
+        }
+#endif
         break;
     }
     default:
@@ -458,14 +523,18 @@ void print_move(const struct chess_ctx *ctx, struct move_t move)
         const struct piece_t *to, *from;
         to = &ctx->board[move.data.normal.to.y][move.data.normal.to.x];
         from = &ctx->board[move.data.normal.from.y][move.data.normal.from.x];
+
+        char name[3];
+        name[0] = 'a' + move.data.normal.to.x;
+        name[1] = '1' + move.data.normal.to.y;
+        name[2] = '\0';
         if(to->type != EMPTY)
         {
-            printf("%s takes %s at %d, %d\n", piece_name(from->type), piece_name(to->type),
-                   move.data.normal.to.x, move.data.normal.to.y);
+            printf("%s takes %s at %s\n", piece_name(from->type), piece_name(to->type), name);
         }
         else
         {
-            printf("%s moves to %d, %d\n", piece_name(from->type), move.data.normal.to.x, move.data.normal.to.y);
+            printf("%s to %s\n", piece_name(from->type), name);
         }
         break;
     }
@@ -524,6 +593,7 @@ struct legal_data {
     bool legal;
 };
 
+#if 0
 bool legal_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
 {
     struct legal_data *info = data;
@@ -550,7 +620,9 @@ bool legal_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
     }
     return true;
 }
+#endif
 
+#if 0
 bool legal_move(const struct chess_ctx *ctx, struct move_t move)
 {
     if(move.type == NORMAL)
@@ -569,6 +641,7 @@ bool legal_move(const struct chess_ctx *ctx, struct move_t move)
     else
         return true;
 }
+#endif
 
 struct chess_ctx new_game(void)
 {
@@ -576,10 +649,10 @@ struct chess_ctx new_game(void)
     memset(&ret.board, 0, sizeof(ret.board));
     for(int i = 0; i < 8; ++i)
     {
-        ret.board[1][i].type = PAWN;
         ret.board[1][i].color = WHITE;
-        ret.board[6][i].type = PAWN;
+        ret.board[1][i].type = PAWN;
         ret.board[6][i].color = BLACK;
+        ret.board[6][i].type = PAWN;
     }
 
     int types[] = { ROOK, KNIGHT, BISHOP };
@@ -595,20 +668,21 @@ struct chess_ctx new_game(void)
         ret.board[7][7 - i].color = BLACK;
     }
 
+    ret.board[0][3].color = WHITE;
     ret.board[0][3].type = QUEEN;
-    ret.board[7][3].type = QUEEN;
+    ret.board[0][4].color = WHITE;
     ret.board[0][4].type = KING;
-    ret.board[7][4].type = KING;
-    ret.board[0][3].color = WHITE;
+
     ret.board[7][3].color = BLACK;
-    ret.board[0][4].color = WHITE;
+    ret.board[7][3].type = QUEEN;
     ret.board[7][4].color = BLACK;
+    ret.board[7][4].type = KING;
     ret.to_move = WHITE;
 
     return ret;
 }
 
-struct move_t get_move(enum player color)
+struct move_t get_move(const struct chess_ctx *ctx, enum player color)
 {
     struct move_t ret;
     ret.type = NOMOVE;
@@ -626,6 +700,15 @@ struct move_t get_move(enum player color)
     if(valid_coords(y, x) && valid_coords(y + dy, x + dx) && (dx || dy))
         ret = construct_move(color, y, x, dy, dx);
 
+    if(ctx->board[y][x].type == PAWN &&
+       (y + dy == 0 || y + dy == 7))
+    {
+        ret.type = PROMOTION;
+        ret.data.promotion.from = (struct coordinates) { y, x  };
+        ret.data.promotion.to = (struct coordinates) { y + dy, x + dx };
+        ret.data.promotion.type = QUEEN;
+    }
+
     free(line);
 
     return ret;
@@ -640,10 +723,20 @@ struct negamax_info {
 
 int negamax(const struct chess_ctx *ctx, int depth, int a, int b, int color, struct move_t *best);
 
+int pondered;
+
 bool negamax_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
 {
     struct negamax_info *info = data;
     struct chess_ctx local = *ctx;
+    if(info->depth == DEPTH)
+    {
+        printf("pondering top-level move: ");
+        print_move(ctx, move);
+        printf("best score so far: %d\n", info->best);
+        print_move(ctx, info->move);
+    }
+    ++pondered;
     execute_move(&local, move);
     int v = -best_move_negamax(&local, info->depth - 1, -info->b, -info->a, local.to_move, NULL);
     if(v > info->best)
@@ -685,19 +778,28 @@ int best_move_negamax(const struct chess_ctx *ctx, int depth, int a, int b, int
     return info.best;
 }
 
-#define DEPTH 3
-
-#define AUTOMATCH
+void print_status(const struct chess_ctx *ctx)
+{
+    if(king_in_checkmate(ctx, WHITE))
+        printf("White is in checkmate\n");
+    else if(king_in_check(ctx, WHITE, NULL))
+        printf("White is in check\n");
+
+    if(king_in_checkmate(ctx, BLACK))
+        printf("Black is in checkmate\n");
+    else if(king_in_check(ctx, BLACK, NULL))
+        printf("Black is in check\n");
+}
 
 int main()
 {
     srand(time(0));
     struct chess_ctx ctx = new_game();
     print_ctx(&ctx);
-    while(1)
+    for(int i = 0; i < 3; ++i)
     {
 #ifndef AUTOMATCH
-        struct move_t player = get_move(ctx.to_move);
+        struct move_t player = get_move(&ctx, ctx.to_move);
         if(player.type == NOMOVE)
         {
             printf("Illegal\n");
@@ -712,21 +814,21 @@ int main()
 
         execute_move(&ctx, player);
         print_ctx(&ctx);
-        if(king_in_check(&ctx, WHITE))
-            printf("White is in check\n");
-        if(king_in_check(&ctx, BLACK))
-            printf("Black is in check\n");
+        print_status(&ctx);
 #endif
 
         printf("Thinking...\n");
         struct move_t best;
+        pondered = 0;
+        clock_t start = clock();
         best_move_negamax(&ctx, DEPTH, -99999, 99999, ctx.to_move, &best);
+        clock_t end = clock();
+        float time = (float)(end - start) / CLOCKS_PER_SEC;
+        printf("pondered %d moves in %.2f seconds (%.1f/sec)\n", pondered,
+               time, pondered / time);
         print_move(&ctx, best);
         execute_move(&ctx, best);
         print_ctx(&ctx);
-        if(king_in_check(&ctx, WHITE))
-            printf("White is in check\n");
-        if(king_in_check(&ctx, BLACK))
-            printf("Black is in check\n");
+        print_status(&ctx);
     }
 }
diff --git a/chess.h b/chess.h
index b80cfd4..4bc0817 100644
--- a/chess.h
+++ b/chess.h
@@ -12,6 +12,7 @@
 #define ABS(x) ((x)<0:-(x):(x))
 #define MAX(a, b) ((a)>(b)?(a):(b))
 
+/* don't change any of these enum values */
 enum player { NONE = 0, WHITE = 1, BLACK = -1 };
 enum piece { EMPTY = 0, PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING };
 
@@ -48,16 +49,16 @@ struct chess_ctx {
 
 int eval_position(const struct chess_ctx *ctx, int color);
 void execute_move(struct chess_ctx *ctx, struct move_t move);
-bool gen_and_call(const struct chess_ctx *ctx,
-                  int y, int x,
-                  int dy, int dx,
-                  bool (*cb)(void *data, const struct chess_ctx*, struct move_t),
-                  void *data, bool enforce);
+inline bool gen_and_call(const struct chess_ctx *ctx,
+                         int y, int x,
+                         int dy, int dx,
+                         bool (*cb)(void *data, const struct chess_ctx*, struct move_t),
+                         void *data, bool enforce);
 void for_each_move(const struct chess_ctx *ctx,
                    int y, int x,
                    bool (*cb)(void *data, const struct chess_ctx*, struct move_t),
                    void *data, bool enforce_check);
-bool king_in_check(const struct chess_ctx *ctx, int color);
+bool king_in_check(const struct chess_ctx *ctx, int color, struct coordinates *king);
 void print_ctx(const struct chess_ctx *ctx);
 int best_move_negamax(const struct chess_ctx *ctx, int depth,
                       int a, int b,