lib/othello.c

   1 /*
   2  * =====================================================================================
   3  *
   4  *       Filename:  othello.c
   5  *
   6  *    Description:  Handle the othello board content
   7  *
   8  *        Version:  1.0
   9  *        Created:  25/04/2017 15:16:08
  10  *       Revision:  none
  11  *       Compiler:  gcc
  12  *
  13  *         Author:  Jerome Benoit (fraggle), jerome.benoit@piment-noir.org
  14  *   Organization:  Piment Noir
  15  *
  16  * =====================================================================================
  17  */
  18
  19 #include <stdlib.h>
  20 #include <stdbool.h>
  21 #include <string.h>
  22
  23 #include "othello.h"
  24 #include "debug.h"
  25
  26 unsigned int current_player(unsigned int round_count) {
  27
  28     if (round_count % 2 != 0) {
  29         return player_two;
  30     } else {
  31         return player_one;
  32     }
  33 }
  34
  35 unsigned int current_opponent(unsigned int current_player) {
  36
  37     if (current_player == player_one) {
  38         return player_two;
  39     } else {
  40         return player_one;
  41     }
  42 }
  43
  44 /* for consistency with ncurses, the board coordinates are in the following order:
  45  * O--x-->
  46  * |
  47  * y
  48  * |
  49  * v
  50  * The origin O has (1, 1) coordinates */
  51
  52 unsigned int get_box_value(int y, int x, unsigned int pawn_array[board_size][board_size]) {
  53
  54     return pawn_array[y-1][x-1];
  55 }
  56
  57 bool is_box_type(int y, int x, unsigned int pawn_array[board_size][board_size], unsigned int type) {
  58
  59     if (type > 2) {
  60         return NULL;
  61     }
  62     if (get_box_value(y, x, pawn_array) == type) {
  63         return true;
  64     } else {
  65         return false;
  66     }
  67 }
  68
  69 static bool is_valid_coordinates(int y, int x) {
  70
  71     if ((y > 0 && y < board_size + 1) && \
  72             (x > 0 && x < board_size + 1)) {
  73         return true;
  74     } else {
  75         return false;
  76     }
  77 }
  78
  79 /* helper function to set a correct value at the (y, x) coordinates in the pawns array */
  80 void set_pawn(int y, int x, unsigned int type, unsigned int pawn_array[board_size][board_size]) {
  81
  82     if (type > 0 && type < 3 && \
  83             is_valid_coordinates(y, x)) {
  84         pawn_array[y-1][x-1] = type;
  85     } //FIXME: else case should set invalid values to permit to catch errors
  86 }
  87
  88 /* reverse the pawn at (y, x) coordinates if it exists */
  89 static void reverse_pawn(int y, int x, unsigned int pawn_array[board_size][board_size]) {
  90
  91     if (is_box_type(y, x, pawn_array, black)) {
  92         set_pawn(y, x, white, pawn_array);
  93     } else if (is_box_type(y, x, pawn_array, white)) {
  94         set_pawn(y, x, black, pawn_array);
  95     }
  96 }
  97
  98 void zero_pawns(unsigned int pawn_array[board_size][board_size]) {
  99
 100     for (int i = 1; i <= board_size; i++) {
 101         for (int j = 1; j <= board_size; j++) {
 102             set_pawn(i, j, empty, pawn_array);
 103          }
 104     }
 105 }
 106
 107 /* set the pawns in the start position */
 108 void init_pawns(unsigned int pawn_array[board_size][board_size]) {
 109
 110     /* the 2D array zeroing is not necessary if it is properly initialized to zero */
 111     zero_pawns(pawn_array);
 112     set_pawn(5, 4, black, pawn_array);
 113     set_pawn(4, 5, black, pawn_array);
 114     set_pawn(4, 4, white, pawn_array);
 115     set_pawn(5, 5, white, pawn_array);
 116 }
 117
 118 unsigned int count_pawns_type(unsigned int pawn_array[board_size][board_size], unsigned int type) {
 119     unsigned int count = 0;
 120
 121     if (type > 2) {
 122         return 0;
 123     }
 124     for (int i = 1; i <= board_size; i++) {
 125         for (int j = 1; j <= board_size; j++) {
 126             if (is_box_type(i, j, pawn_array, type)) {
 127                 count++;
 128             }
 129         }
 130     }
 131     return count;
 132 }
 133
 134 static void direction_to_coordinates(unsigned int direction, int* start_y, int* start_x) {
 135
 136     if (direction == north) {
 137         *start_y = *start_y - 1;
 138     } else if (direction == north_east) {
 139         *start_y = *start_y - 1;
 140         *start_x = *start_x + 1;
 141     } else if (direction == east) {
 142         *start_x = *start_x + 1;
 143     } else if (direction == south_east) {
 144         *start_y = *start_y + 1;
 145         *start_x = *start_x + 1;
 146     } else if (direction == south) {
 147         *start_y = *start_y + 1;
 148     } else if (direction == south_west) {
 149         *start_y = *start_y + 1;
 150         *start_x = *start_x - 1;
 151     } else if (direction == west) {
 152         *start_x = *start_x - 1;
 153     } else if (direction == north_west) {
 154         *start_y = *start_y - 1;
 155         *start_x = *start_x - 1;
 156     }
 157 }
 158
 159 bool is_board_full(unsigned int pawn_array[board_size][board_size]) {
 160
 161     /* an alternate method is to test the round count vs. 60 */
 162     for (int i = 1; i <= board_size; i++) {
 163         for (int j = 1; j <= board_size; j++) {
 164             if (is_box_type(i, j, pawn_array , empty)) {
 165                 return false;
 166             }
 167         }
 168     }
 169     return true;
 170 }
 171
 172 unsigned int eval_winner(unsigned int nb_white, unsigned int nb_black) {
 173
 174     if (nb_white > nb_black) {
 175         return player_two;
 176     } else if (nb_white < nb_black) {
 177         return player_one;
 178     } else {
 179         return 0;
 180     }
 181 }
 182
 183 static unsigned int count_pawn_to_reverse_one_direction(int y, int x, int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 184     unsigned int nb_pawns_reversed = 0;
 185     int moving_y = y, moving_x = x;
 186
 187     /* count the pawns to reverse in the chosen direction */
 188     direction_to_coordinates(direction, &moving_y, &moving_x);
 189     while (true) {
 190         if (!is_valid_coordinates(moving_y, moving_x) || is_box_type(moving_y, moving_x, pawn_array, empty)) {
 191             return 0;
 192         }
 193         if (is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 194             break;
 195         }
 196         nb_pawns_reversed++;
 197         direction_to_coordinates(direction, &moving_y, &moving_x);
 198     }
 199     return nb_pawns_reversed;
 200 }
 201
 202 /* revert the pawns if needed in one direction */
 203 static unsigned int reverse_one_direction(int y, int x, int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size], bool dry_run) {
 204     unsigned int nb_pawns_reversed = 0;
 205     int moving_y = y, moving_x = x;
 206
 207     nb_pawns_reversed = count_pawn_to_reverse_one_direction(moving_y, moving_x, direction, current_player, pawn_array);
 208
 209     /* now reverse the needed pawns */
 210     if (nb_pawns_reversed > 0 && !dry_run) {
 211         moving_y = y, moving_x = x;
 212         direction_to_coordinates(direction, &moving_y, &moving_x);
 213         while (!is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 214             reverse_pawn(moving_y, moving_x, pawn_array);
 215             direction_to_coordinates(direction, &moving_y, &moving_x);
 216         }
 217     }
 218     return nb_pawns_reversed;
 219 }
 220
 221 /* loop optimized version of valid_shot changing nothing to the pawns 2D array */
 222 static bool is_legal_shot(int y, int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 223     unsigned int nb_pawns_reversed = 0;
 224
 225     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 226         return false;
 227     }
 228
 229     for (unsigned int direction = north; direction <= north_west; direction++) {
 230         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, true);
 231         if (nb_pawns_reversed > 0) {
 232             return true;
 233         }
 234     }
 235     return false;
 236 }
 237
 238 /* play the shot if legal and flip or reverse the necessary pawns */
 239 unsigned int valid_shot(int y, int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 240     unsigned int nb_pawns_reversed = 0;
 241
 242     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 243         return 0;
 244     }
 245
 246     for (unsigned int direction = north; direction <= north_west; direction++) {
 247         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, false);
 248     }
 249
 250     if (nb_pawns_reversed == 0) {
 251         return nb_pawns_reversed;
 252     }
 253
 254     set_pawn(y, x, current_player, pawn_array);
 255     return nb_pawns_reversed;
 256 }
 257
 258 static void add_shots_list_cell(int y, int x, unsigned int type, struct shots_list_s* shots_list) {
 259     struct shots_list_s* list_cell = malloc(sizeof(struct shots_list_s));
 260     if (!list_cell) {
 261         exit(EXIT_FAILURE);
 262     }
 263
 264     if (type > 0 && type < 5 && is_valid_coordinates(y, x)) {
 265         list_cell->y = y;
 266         list_cell->x = x;
 267         list_cell->type = type;
 268         list_add_tail(&(list_cell->list), &(shots_list->list));
 269     }
 270 }
 271
 272 void free_shots_list(struct shots_list_s* shots_list) {
 273     struct shots_list_s* list_counter;
 274
 275     while (!list_empty(&shots_list->list)) {
 276         list_counter = list_entry(shots_list->list.next, struct shots_list_s, list);
 277         list_del(&list_counter->list);
 278         free(list_counter);
 279     }
 280
 281 }
 282
 283 void build_playable_shots_list(unsigned int current_player, struct shots_list_s* shots_list, unsigned int pawn_array[board_size][board_size]) {
 284
 285     for (unsigned int i = 0; i <= board_size; i++) {
 286         for (unsigned int j = 0; j <= board_size; j++) {
 287             if (is_legal_shot(i, j, current_player, pawn_array)) {
 288                 add_shots_list_cell(i, j, hint_allowed, shots_list);
 289             /* FIXME: a neighbourhood detection is needed
 290             } else if (is_box_type(i, j, pawn_array, empty)){
 291                 add_shots_list_cell(i, j, hint_forbidden, shots_list);
 292             */
 293             }
 294         }
 295     }
 296 }