testing qsearchHEADmaster

3 files changed, 243 insertions, 49 deletions

diff --git a/Makefile b/Makefile
index 053890b..8570b99 100644
--- a/Makefile
+++ b/Makefile
@@ -30,10 +30,10 @@ $(PROGRAM_NAME)-old: Makefile $(HEADERS) $(SRC)
 	$(CC) $(SRC) -o $@ $(CFLAGS) $(LIBS)
 
 test: all
-	$(CUTECHESS) -engine name=xenon-new proto=uci dir=`pwd` cmd=./xenonchess -engine proto=uci dir=`pwd` cmd=./xenonchess-old name=xenon-old -each tc=1+.01 -rounds 200 -ratinginterval 1
+	$(CUTECHESS) -engine name=xenon-new proto=uci dir=`pwd` cmd=./xenonchess -engine proto=uci dir=`pwd` cmd=./xenonchess-old name=xenon-old -each tc=1+.01 -rounds 1000 -ratinginterval 1
 
 test-tscp: $(PROGRAM_NAME)
-	$(CUTECHESS) -engine name=xenon-new proto=uci dir=`pwd` cmd=./xenonchess -engine proto=xboard dir=/ cmd=$(TSCP) name=tscp -each tc=1+.01 -rounds 1000
+	$(CUTECHESS) -engine name=xenon-new proto=uci dir=`pwd` cmd=./xenonchess tc=1+.01 -engine proto=xboard dir=/ cmd=$(TSCP) name=tscp tc=.2+.001 -rounds 1000 -ratinginterval 1
 
 %.o: %.c Makefile $(HEADERS)
 	@echo "CC $<"
diff --git a/chess.c b/chess.c
index 743e709..2d860d8 100644
--- a/chess.c
+++ b/chess.c
@@ -1,13 +1,13 @@
 #include "chess.h"
 
-#define DEFAULT_DEPTH 3
-#define MAX_DEPTH 5
+#define DEFAULT_DEPTH 4
+#define MAX_DEPTH 6
 
 //#define AUTOMATCH
 #define UCI
-#ifdef TEST_FEATURE
-#define CHECK_EXTENSIONS
-#endif
+//#ifdef TEST_FEATURE
+//#define CHECK_EXTENSIONS
+//#endif
 
 #if defined(AUTOMATCH) && defined(UCI)
 #error stupid
@@ -18,7 +18,7 @@ static const int piece_values[] = { 0,
                                     500, /* rook */
                                     320, /* knight */
                                     330, /* bishop */
-                                    10000,
+                                    900,
                                     0  /* king, value doesn't matter */
 };
 
@@ -590,8 +590,112 @@ inline bool gen_and_call(const struct chess_ctx *ctx,
     }
 }
 
-void for_each_move(const struct chess_ctx *ctx,
-                   int y, int x,
+/* exactly that, and promotions too */
+void for_each_capture(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)
+{
+    assert(valid_coords(y, x));
+
+    const struct piece_t *piece = &ctx->board[y][x];
+
+    switch(piece->type)
+    {
+    case EMPTY:
+        return;
+    case PAWN:
+    {
+        /* special case */
+        int dy = (piece->color == WHITE ? 1 : -1);
+
+        if(!valid_coords(y + dy, x))
+            break;
+
+        /* en passant */
+        if((piece->color == WHITE && y == 4) ||
+           (piece->color == BLACK && y == 3))
+        {
+            /* piece to right */
+            int opp = piece->color == WHITE ? 1 : 0;
+            if(valid_coords(y + dy, x + 1) && ctx->en_passant[opp][x + 1])
+            {
+                if(!gen_and_call(ctx, y, x, dy, 1, cb, data, enforce_check))
+                    return;
+            }
+            if(valid_coords(y + dy, x - 1) && ctx->en_passant[opp][x - 1])
+            {
+                if(!gen_and_call(ctx, y, x, dy, -1, cb, data, enforce_check))
+                    return;
+            }
+        }
+
+        for(int dx = -1; dx <= 1; dx += 2)
+        {
+            if(enemy_occupied(ctx, y + dy, x + dx, piece->color))
+            {
+                if(!gen_and_call(ctx, y, x, dy, dx, cb, data, enforce_check))
+                    return;
+            }
+        }
+
+        /* promotions only */
+        if((y == 7 || y == 0) && !occupied(ctx, y + dy, x))
+            if(!gen_and_call(ctx, y, x, dy, 0, cb, data, enforce_check))
+                return;
+        break;
+    }
+    case ROOK:
+    case BISHOP:
+    case QUEEN:
+    {
+        const struct coordinates *dir = line_moves[piece->type];
+        while(dir->x != COORD_END)
+        {
+            bool clear = true;
+            for(int i = 1; i < 8 && clear; ++i)
+            {
+                struct coordinates d = { i * dir->y, i * dir->x };
+                clear = valid_coords(y + d.y, x + d.x);
+                if(!clear)
+                    break;
+                if(occupied(ctx, y + d.y, x + d.x))
+                {
+                    /* occupied square */
+                    if(enemy_occupied(ctx, y + d.y, x + d.x, piece->color))
+                        if(!gen_and_call(ctx, y, x, d.y, d.x, cb, data, enforce_check))
+                            return;
+                    clear = false;
+                }
+            }
+            ++dir;
+        }
+        break;
+    }
+    case KNIGHT:
+    case KING:
+    {
+        const struct coordinates *moves = jump_moves[piece->type];
+
+        while(moves->x != COORD_END)
+        {
+            struct coordinates d = *moves;
+            if(valid_coords(y + d.y, x + d.x))
+            {
+                    /* occupied square */
+                if(enemy_occupied(ctx, y + d.y, x + d.x, piece->color))
+                    if(!gen_and_call(ctx, y, x, d.y, d.x, cb, data, enforce_check))
+                        return;
+            }
+            ++moves;
+        }
+        break;
+    }
+    default:
+        assert(false);
+    }
+}
+
+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 consider_castle)
 {
@@ -1207,6 +1311,8 @@ struct chess_ctx ctx_from_fen(const char *fen, int *len)
         }
     }
     char *tok = strtok_r(NULL, " ", &save);
+    if(!tok)
+        goto invalid;
     switch(tolower(tok[0]))
     {
     case 'w':
@@ -1397,14 +1503,28 @@ struct chess_ctx get_uci_ctx(int *wtime, int *btime, int *movetime)
             int depth;
             if(sscanf(line, "perft %d\n", &depth) != 1)
                 depth = 4;
-            printf("info depth %d nodes %lu\n", depth, perft(&ctx, depth - 1));
+
+            clock_t start = clock();
+
+            uint64_t count = perft(&ctx, depth - 1);
+
+            clock_t end = clock();
+            float time = (float)(end - start) / CLOCKS_PER_SEC;
+
+            printf("info depth %d nodes %lu in %.2f seconds (%.1f/sec)\n", depth, count, time, count / time);
             fflush(stdout);
         }
         else if(!strncasecmp(line, "eval", 4))
         {
-            printf("info value WHITE: %d, BLACK: %d\n", eval_position(&ctx, WHITE), eval_position(&ctx, BLACK));
+            printf("info string value WHITE: %d, BLACK: %d\n", eval_position(&ctx, WHITE), eval_position(&ctx, BLACK));
             fflush(stdout);
         }
+        else if(!strncasecmp(line, "quit", 4))
+        {
+            free(ptr);
+            exit(0);
+        }
+
         free(ptr);
     }
 }
@@ -1507,7 +1627,15 @@ again:
         int depth;
         if(sscanf(line, "perft %d\n", &depth) != 1)
             depth = 4;
-        printf("info depth %d nodes %lu\n", depth, perft(ctx, depth - 1));
+
+        clock_t start = clock();
+
+        uint64_t count = perft(ctx, depth - 1);
+
+        clock_t end = clock();
+        float time = (float)(end - start) / CLOCKS_PER_SEC;
+
+        printf("info depth %d nodes %lu in %.2f seconds (%.1f/sec)\n", depth, count, time, count / time);
         fflush(stdout);
         goto again;
     }
@@ -1545,6 +1673,9 @@ 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->stop_time > 0 && info->stop_time < ms_time())
+        return false;
+
     ++pondered;
 
     int king_penalty = 0;
@@ -1563,7 +1694,8 @@ bool negamax_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
     }
 
     execute_move(&local, move);
-    int v = -(best_move_negamax(&local, info->depth - 1, -info->b, -info->a, local.to_move, NULL, info->full_depth, info->stop_time) + king_penalty);
+    int v = -(best_move_negamax(&local, info->depth - 1, -info->b, -info->a, local.to_move,
+                                NULL, info->full_depth, info->stop_time) + king_penalty);
     if(v > info->best || (v == info->best && rand() % 8 == 2))
     {
         info->best = v;
@@ -1573,12 +1705,10 @@ bool negamax_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
 
     if(info->depth == info->full_depth)
     {
-#if defined(UCI) || DEFAULT_DEPTH > 3
-        printf("info currmove ");
-        print_move(ctx, move);
-        printf("info currmovenumber %d\n", ++moveno);
-        fflush(stdout);
-#endif
+        //printf("info currmove ");
+        //print_move(ctx, move);
+        //printf("info currmovenumber %d\n", ++moveno);
+        //fflush(stdout);
         //printf("current best: %d, ", info->best);
         //print_move(ctx, info->move);
         //printf("movescore: %d\n", v);
@@ -1604,6 +1734,62 @@ int ms_time(void)
     return t.tv_sec * 1000 + t.tv_nsec / 1e6;
 }
 
+struct quiesce_info {
+    int a, b;
+    int result;
+    bool finished;
+};
+
+bool quiesce_cb(void *data, const struct chess_ctx *ctx, struct move_t move)
+{
+    struct quiesce_info *info = data;
+    struct chess_ctx local = *ctx;
+    execute_move(&local, move);
+
+    int v = -quiesce(&local, -info->b, -info->a);
+    print_ctx(ctx);
+    printf("value %d for move ", v);
+    print_move(ctx, move);
+    if(v >= info->b)
+    {
+        info->result = info->b;
+        info->finished = true;
+        return false;
+    }
+    if(v > info->a)
+        info->a = v;
+    return true;
+}
+
+int quiesce(const struct chess_ctx *ctx, int a, int b)
+{
+    int stand = eval_position(ctx, ctx->to_move);
+    if(stand >= b)
+        return b;
+    if(a < stand)
+        a = stand;
+
+    struct quiesce_info info;
+    info.a = a;
+    info.b = b;
+    info.finished = false;
+
+    for(int y = 0; y < 8; ++y)
+    {
+        for(int x = 0; x < 8; ++x)
+        {
+            if(ctx->board[y][x].color == ctx->to_move)
+            {
+                /* recurse */
+                for_each_capture(ctx, y, x, quiesce_cb, &info, true);
+                if(info.finished)
+                    return info.result;
+            }
+        }
+    }
+    return info.a;
+}
+
 int best_move_negamax(const struct chess_ctx *ctx, int depth,
                       int a, int b, int color,
                       struct move_t *best, int full_depth, int stop_time)
@@ -1628,7 +1814,7 @@ int best_move_negamax(const struct chess_ctx *ctx, int depth,
                     /* abort! */
                     if(best)
                         best->type = NOMOVE;
-                    printf("aborting depth %d search due to time\n", info.full_depth);
+                    printf("info string aborting depth %d search due to time\n", info.full_depth);
                     return -99999999;
                 }
                 if(ctx->board[y][x].color == ctx->to_move)
@@ -1642,22 +1828,30 @@ int best_move_negamax(const struct chess_ctx *ctx, int depth,
             *best = info.move;
     }
     if(!depth || info.move.type == NOMOVE) /* terminal node */
+    {
+#ifdef TEST_FEATURE
+        return quiesce(ctx, a, b);
+#else
         return eval_position(ctx, color);
+#endif
+    }
 
     return info.best;
 }
 
 struct move_t best_move(const struct chess_ctx *ctx, int stop_time)
 {
+    printf("stop time is %d\n", stop_time);
     struct move_t best;
     best.type = NOMOVE;
     if(stop_time < 0)
     {
+        printf("ignoring time, doing default depth search\n");
         /* no time limit, default depth */
         best_move_negamax(ctx, DEFAULT_DEPTH, -9999999, 9999999, ctx->to_move, &best, DEFAULT_DEPTH, stop_time);
         return best;
     }
-    for(int i = 1; i < MAX_DEPTH; ++i)
+    for(int i = 1; i <= MAX_DEPTH; ++i)
     {
         struct move_t old = best;
         best_move_negamax(ctx, i, -9999999, 9999999, ctx->to_move, &best, i, old.type == NOMOVE ? -1 : stop_time);
@@ -1669,12 +1863,7 @@ struct move_t best_move(const struct chess_ctx *ctx, int stop_time)
                 return old;
             }
             else
-            {
-                printf("finishing search...\n");
-                /* finish the search, ignoring the time */
-                best_move_negamax(ctx, i, -9999999, 9999999, ctx->to_move, &best, i, -1);
                 return best;
-            }
         }
         printf("after depth %d search, best move: ", i);
         print_move(ctx, best);
@@ -1684,23 +1873,20 @@ struct move_t best_move(const struct chess_ctx *ctx, int stop_time)
 
 float calculate_phase(const struct chess_ctx *ctx)
 {
-    int mat = count_material(ctx, WHITE) + count_material(ctx, BLACK);
-    static int start_material = -1;
-    if(start_material < 0)
-    {
-        struct chess_ctx new = new_game();
-        start_material = count_material(&new, WHITE) * 2;
-    }
-    int end_material = piece_values[KING] * 2;
-    return (float)(mat - start_material) / (float)(end_material - start_material);
+    int npieces = 0;
+    for(int y = 0; y < 8; ++y)
+        for(int x = 0; x < 8; ++x)
+            if(ctx->board[y][x].type != EMPTY)
+                ++npieces;
+
+    return (float)(32 - npieces) / (float)(32 - 2);
 }
 
 #define INTERPOLATE(a, b, x) ((a) + ((b) - (a)) * (x))
 
-void init_pst(const struct chess_ctx *ctx)
+void init_pst(float phase)
 {
     memset(location_bonuses, 0, sizeof(location_bonuses));
-    float phase = calculate_phase(ctx);
     printf("game phase is %f\n", phase);
     for(int i = 0; i < 6; ++i)
         for(int y = 0; y < 8; ++y)
@@ -1738,7 +1924,7 @@ int main()
     unsigned int seed;
     int fd = open("/dev/urandom", O_RDONLY);
     read(fd, &seed, sizeof seed);
-    srand(seed);
+    srand(seed + time(0));
 
 #ifndef UCI
     struct chess_ctx ctx = new_game();
@@ -1747,6 +1933,7 @@ int main()
 
     for(;;)
     {
+        int wtime = -1, btime = -1, movetime = -1;
 #ifndef AUTOMATCH
 #ifndef UCI
         struct move_t player = get_move(&ctx, ctx.to_move);
@@ -1767,29 +1954,34 @@ int main()
         print_ctx(&ctx);
         print_status(&ctx);
 #else
-        int wtime = -1, btime = -1, movetime = -1;
         struct chess_ctx ctx = get_uci_ctx(&wtime, &btime, &movetime);
 #endif
 #endif
+
+        float phase = calculate_phase(&ctx);
+
         int stop_time;
-        int think_time = movetime > 0 ? movetime : (ctx.to_move == WHITE ? wtime : btime) / 40;
-        if(think_time <= 0)
+        int think_time = movetime > 0 ? movetime : (ctx.to_move == WHITE ? wtime : btime) / (phase < .5 ? 40 : 20);
+        if(think_time < 0 || (movetime < 0 && ((ctx.to_move == WHITE ? wtime : btime) < 0)))
             stop_time = -1;
         else
+        {
+            printf("info string allocated %d ms to think\n", think_time);
             stop_time = ms_time() + think_time;
+        }
 
-        printf("info Thinking...\n");
+        printf("info string Thinking...\n");
         struct move_t best;
         pondered = 0;
         moveno = 0;
         clock_t start = clock();
 
-        init_pst(&ctx);
+        init_pst(phase);
 
         best = best_move(&ctx, stop_time);
         //best_move_negamax(&ctx, DEFAULT_DEPTH, -9999999, 9999999, ctx.to_move, &best, DEFAULT_DEPTH, stop_time);
         clock_t end = clock();
-        float time = (float)(end - start) / CLOCKS_PER_SEC;
+        float t = (float)(end - start) / CLOCKS_PER_SEC;
         printf("bestmove ");
         print_move(&ctx, best);
         fflush(stdout);
@@ -1800,15 +1992,15 @@ int main()
         print_status(&ctx);
 #endif
 
-        if(time)
+        if(t)
         {
-            printf("info pondered %"PRIu64" moves in %.2f seconds (%.1f/sec)\n", pondered,
-                   time, pondered / time);
+            printf("info string pondered %"PRIu64" moves in %.3f seconds (%.1f/sec)\n", pondered,
+                   t, pondered / t);
         }
 
         if(best.type == NOMOVE)
         {
-            printf("info Stalemate\n");
+            printf("info string Stalemate\n");
             return 0;
         }
     }
diff --git a/chess.h b/chess.h
index 36cf5a7..efef2b2 100644
--- a/chess.h
+++ b/chess.h
@@ -73,3 +73,5 @@ bool can_castle(const struct chess_ctx *ctx, int color, int style);
 uint64_t perft(const struct chess_ctx *ctx, int depth);
 struct chess_ctx ctx_from_fen(const char *fen, int *len);
 extern int location_bonuses[6][8][8];
+int ms_time(void);
+int quiesce(const struct chess_ctx *ctx, int a, int b);