stellar

Stellar - Chess engine written in C
Log | Files | Refs

perft.c (3577B)

      1 #include <pthread.h>
      2 #include <semaphore.h>
      3 #include <stdio.h>
      4 
      5 #include "moves.h"
      6 #include "perft.h"
      7 
      8 struct MoveList_T moveList[10];
      9 long nodes;
     10 
     11 void perft_driver(CBoard_T board, struct MoveList_T *moveList, int depth,
     12                   unsigned long long *nodes) {
     13     if (depth == 0) {
     14         (*nodes)++;
     15         return;
     16     }
     17 
     18     MoveList_T list = MoveList_generate(&moveList[depth], board);
     19     CBoard_T copy = CBoard_new();
     20 
     21     for (int i = 0; i < MoveList_size(list); i++) {
     22         CBoard_copy(board, copy);
     23         if (!Move_make(MoveList_move(list, i), copy, 0)) continue;
     24         perft_driver(copy, moveList, depth - 1, nodes);
     25     }
     26 
     27     MoveList_reset(list);
     28     CBoard_free(&copy);
     29 }
     30 
     31 void perft_test(CBoard_T board, int depth) {
     32     MoveList_T list = MoveList_generate(&moveList[depth], board);
     33     CBoard_T copy = CBoard_new();
     34     long start = get_time_ms();
     35 
     36     printf("\n     Performance test\n\n");
     37 
     38     nodes = 0;
     39     for (int i = 0; i < MoveList_size(list); i++) {
     40         CBoard_copy(board, copy);
     41         Move move = MoveList_move(list, i);
     42         if (!Move_make(MoveList_move(list, i), copy, 0)) continue;
     43         unsigned long long node = 0;
     44         perft_driver(copy, moveList, depth - 1, &node);
     45         printf("%s%s: %llu\n", square_to_coordinates[Move_source(move)],
     46                square_to_coordinates[Move_target(move)], node);
     47         nodes += node;
     48     }
     49     MoveList_reset(list);
     50     CBoard_free(&copy);
     51 
     52     printf("\nNodes searched: %ld\n\n", nodes);
     53     printf("\n    Depth: %d\n", depth);
     54     printf("    Nodes: %ld\n", nodes);
     55     printf("     Time: %ld\n\n", get_time_ms() - start);
     56 }
     57 
     58 typedef struct perf_shared perf_shared;
     59 struct perf_shared {
     60     CBoard_T board;
     61     MoveList_T list;
     62     int depth;
     63     sem_t *mutex;
     64     int *index;
     65     sem_t *finish;
     66     unsigned long long *total;
     67 };
     68 
     69 void *perft_thread(void *arg) {
     70     perf_shared *shared = (perf_shared *)arg;
     71     CBoard_T board = CBoard_new();
     72     unsigned long long node_count = 0;
     73 
     74     struct MoveList_T moveList[10];
     75 
     76     while (1) {
     77         sem_wait(shared->mutex);
     78         *shared->total += node_count;
     79         if (*shared->index >= MoveList_size(shared->list)) {
     80             sem_post(shared->mutex);
     81             break;
     82         }
     83         Move move = MoveList_move(shared->list, (*shared->index)++);
     84         sem_post(shared->mutex);
     85 
     86         CBoard_copy(shared->board, board);
     87         if (!Move_make(move, board, 0)) continue;
     88 
     89         node_count = 0;
     90         perft_driver(board, moveList, shared->depth, &node_count);
     91         printf("%s%s: %llu\n", square_to_coordinates[Move_source(move)],
     92                square_to_coordinates[Move_target(move)], node_count);
     93     }
     94     CBoard_free(&board);
     95     sem_post(shared->finish);
     96     return NULL;
     97 }
     98 
     99 void perft_test_threaded(CBoard_T board, int depth) {
    100     MoveList_T list = MoveList_generate(NULL, board);
    101     int size = 8;
    102 
    103     unsigned long long total = 0;
    104     perf_shared shared[size];
    105     pthread_t threads[size];
    106     sem_t mutex, finish;
    107 
    108     int index = 0;
    109     sem_init(&mutex, 0, 1);
    110     sem_init(&finish, 0, 0);
    111     for (int i = 0; i < size; i++) {
    112         shared[i].board = board;
    113         shared[i].list = list;
    114         shared[i].depth = depth - 1;
    115         shared[i].mutex = &mutex;
    116         shared[i].index = &index;
    117         shared[i].finish = &finish;
    118         shared[i].total = &total;
    119         pthread_create(threads + i, NULL, perft_thread, (void *)(shared + i));
    120     }
    121 
    122     for (int i = 0; i < size; i++)
    123         sem_wait(&finish);
    124     MoveList_free(&list);
    125 
    126     printf("Nodes processed: %llu\n", total);
    127 }