apps/plugins/reversi/reversi-game.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (c) 2006 Alexander Levin
  11  *
  12  * All files in this archive are subject to the GNU General Public License.
  13  * See the file COPYING in the source tree root for full license agreement.
  14  *
  15  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  16  * KIND, either express or implied.
  17  *
  18  ****************************************************************************/
  19
  20 /*
  21  * Reversi. Code is heavily based on othello code by Claudio Clemens which is
  22  * copyright (c) 2003-2006 Claudio Clemens <asturio at gmx dot net> and is
  23  * released under the GNU General Public License as published by the Free
  24  * Software Foundation; either version 2, or (at your option) any later version.
  25  */
  26
  27 #include <stddef.h>
  28 #include "reversi-game.h"
  29
  30 /*
  31  * Constants for directions. The values are chosen so that
  32  * they can be bit combined.
  33  */
  34 #define DIR_UP 1        /* UP         */
  35 #define DIR_DO 2        /* DOWN       */
  36 #define DIR_LE 4        /* LEFT       */
  37 #define DIR_RI 8        /* RIGHT      */
  38 #define DIR_UL 16       /* UP LEFT    */
  39 #define DIR_UR 32       /* UP RIGHT   */
  40 #define DIR_DL 64       /* DOWN LEFT  */
  41 #define DIR_DR 128      /* DOWN RIGHT */
  42
  43 /* Array of directions for easy iteration through all of them */
  44 static int DIRECTIONS[] =
  45     {DIR_UP, DIR_DO, DIR_LE, DIR_RI, DIR_UL, DIR_UR, DIR_DL, DIR_DR};
  46 #define NUM_OF_DIRECTIONS 8
  47
  48
  49 /* Initializes a reversi game */
  50 void reversi_init_game(reversi_board_t *game) {
  51     int r, c;
  52     for (r = 0; r < BOARD_SIZE; r++) {
  53         for (c = 0; c < BOARD_SIZE; c++) {
  54             game->board[r][c] = FREE;
  55         }
  56     }
  57     game->board[3][3] = WHITE;
  58     game->board[4][4] = WHITE;
  59     game->board[3][4] = BLACK;
  60     game->board[4][3] = BLACK;
  61
  62     /* Invalidate the history */
  63     c = sizeof(game->history) / sizeof(game->history[0]);
  64     for (r = 0; r < c; r++) {
  65         game->history[r] = MOVE_INVALID;
  66     }
  67 }
  68
  69
  70 /* Returns the 'flipped' color, e.g. WHITE for BLACK and vice versa */
  71 int reversi_flipped_color(const int color) {
  72     switch (color) {
  73         case WHITE:
  74             return BLACK;
  75
  76         case BLACK:
  77             return WHITE;
  78
  79         default:
  80             return FREE;
  81     }
  82 }
  83
  84
  85 /* Counts and returns the number of occupied cells on the board.
  86  * If white_count and/or black_count is not null, the number of
  87  * white/black stones is placed there. */
  88 int reversi_count_occupied_cells(const reversi_board_t *game,
  89         int *white_count, int *black_count) {
  90     int w_cnt, b_cnt, r, c;
  91     w_cnt = b_cnt = 0;
  92     for (r = 0; r < BOARD_SIZE; r++) {
  93         for (c = 0; c < BOARD_SIZE; c++) {
  94             if (game->board[r][c] == WHITE) {
  95                 w_cnt++;
  96             } else if (game->board[r][c] == BLACK) {
  97                 b_cnt++;
  98             }
  99         }
 100     }
 101     if (white_count != NULL) {
 102         *white_count = w_cnt;
 103     }
 104     if (black_count != NULL) {
 105         *black_count = b_cnt;
 106     }
 107     return w_cnt + b_cnt;
 108 }
 109
 110
 111 /* Returns the number of free cells on the board */
 112 static int reversi_count_free_cells(const reversi_board_t *game) {
 113     int cnt;
 114     cnt = reversi_count_occupied_cells(game, NULL, NULL);
 115     return BOARD_SIZE*BOARD_SIZE - cnt;
 116 }
 117
 118
 119 /* Checks whether the game is finished. That means that nobody
 120  * can make a move. Note that the implementation is not correct
 121  * as a game may be finished even if there are free cells
 122  */
 123 bool reversi_game_is_finished(const reversi_board_t *game, int player) {
 124     return (reversi_count_free_cells(game) == 0)
 125            || (reversi_count_passes(game,player) == 2);
 126 }
 127
 128
 129 /* Returns the total number of moves made so far */
 130 int reversi_count_moves(const reversi_board_t *game) {
 131     int cnt;
 132     cnt = reversi_count_occupied_cells(game, NULL, NULL);
 133     return cnt - INIT_STONES;
 134 }
 135
 136
 137 /* Returns the number of moves made by the specified
 138  * player (WHITE or BLACK) so far
 139  */
 140 static int reversi_count_player_moves(const reversi_board_t *game,
 141         const int player) {
 142     int moves, cnt, i;
 143     moves = reversi_count_moves(game);
 144     cnt = 0;
 145     for (i = 0; i < moves; i++) {
 146         if (MOVE_PLAYER(game->history[i]) == player) {
 147             cnt++;
 148         }
 149     }
 150     return cnt;
 151 }
 152
 153 /* Returns the number of moves available for the specified player */
 154 int reversi_count_player_available_moves(const reversi_board_t *game,
 155         const int player) {
 156     int cnt = 0, row, col;
 157     for(row=0;row<BOARD_SIZE;row++) {
 158         for(col=0;col<BOARD_SIZE;col++) {
 159             if(reversi_is_valid_move(game, row, col, player)) cnt++;
 160         }
 161     }
 162     return cnt;
 163 }
 164
 165 /* Returns the number of players who HAVE to pass (2 == game is stuck) */
 166 int reversi_count_passes(const reversi_board_t *game, const int player) {
 167     if(reversi_count_player_available_moves(game,player)==0) {
 168         if(reversi_count_player_available_moves(game,
 169                     reversi_flipped_color(player))==0) {
 170             return 2;
 171         }
 172         return 1;
 173     }
 174     return 0;
 175 }
 176
 177 /* Returns the number of moves made by WHITE so far */
 178 int reversi_count_white_moves(const reversi_board_t *game) {
 179     return reversi_count_player_moves(game, WHITE);
 180 }
 181
 182
 183 /* Returns the number of moves made by BLACK so far */
 184 int reversi_count_black_moves(const reversi_board_t *game) {
 185     return reversi_count_player_moves(game, BLACK);
 186 }
 187
 188
 189 /* Checks whether the specified position is on the board
 190  * (and not beyond)
 191  */
 192 static bool reversi_is_position_on_board(const int row, const int col) {
 193     return (row >= 0) && (row < BOARD_SIZE) &&
 194            (col >= 0) && (col < BOARD_SIZE);
 195 }
 196
 197
 198 /* Returns the delta for row to move in the specified direction */
 199 static int reversi_row_delta(const int direction) {
 200     switch (direction) {
 201         case DIR_UP:
 202         case DIR_UL:
 203         case DIR_UR:
 204             return -1;
 205
 206         case DIR_DO:
 207         case DIR_DL:
 208         case DIR_DR:
 209             return 1;
 210
 211         default:
 212             return 0;
 213     }
 214 }
 215
 216
 217 /* Returns the delta for column to move in the specified direction */
 218 static int reversi_column_delta(const int direction) {
 219     switch (direction) {
 220         case DIR_LE:
 221         case DIR_UL:
 222         case DIR_DL:
 223             return -1;
 224
 225         case DIR_RI:
 226         case DIR_UR:
 227         case DIR_DR:
 228             return 1;
 229
 230         default:
 231             return 0;
 232     }
 233 }
 234
 235
 236 /* Checks if some stones would be captured in the specified direction
 237  * if a stone were placed in the specified cell by the specified player.
 238  *
 239  * Returns 0 if no stones would be captured or 'direction' otherwise
 240  */
 241 static int reversi_is_valid_direction(const reversi_board_t *game,
 242         const int row, const int col, const int player, const int direction) {
 243     int row_delta, col_delta, r, c;
 244     int other_color;
 245     int flip_cnt; /* Number of stones that would be flipped */
 246
 247     row_delta = reversi_row_delta(direction);
 248     col_delta = reversi_column_delta(direction);
 249     other_color = reversi_flipped_color(player);
 250
 251     r = row + row_delta;
 252     c = col + col_delta;
 253
 254     flip_cnt = 0;
 255     while (reversi_is_position_on_board(r, c) &&
 256             (game->board[r][c] == other_color)) {
 257         r += row_delta;
 258         c += col_delta;
 259         flip_cnt++;
 260     }
 261
 262     if ((flip_cnt > 0) && reversi_is_position_on_board(r, c) &&
 263             (game->board[r][c] == player)) {
 264         return direction;
 265     } else {
 266         return 0;
 267     }
 268 }
 269
 270
 271 /* Checks whether the move at the specified position would be valid.
 272  * Params:
 273  *   - game: current state of the game
 274  *   - row: 0-based row number of the move in question
 275  *   - col: 0-based column number of the move in question
 276  *   - player: who is about to make the move (WHITE/BLACK)
 277  *
 278  * Checks if the place is empty, the coordinates are legal,
 279  * and some stones can be captured.
 280  *
 281  * Returns 0 if the move is not valid or, otherwise, the or'd
 282  * directions in which stones would be captured.
 283  */
 284 int reversi_is_valid_move(const reversi_board_t *game,
 285         const int row, const int col, const int player) {
 286     int dirs, i;
 287     dirs = 0;
 288
 289     /* Check if coordinates are legal */
 290     if (!reversi_is_position_on_board(row, col)) {
 291         return dirs;
 292     }
 293
 294     /* Check if the place is free */
 295     if (game->board[row][col] != FREE) {
 296         return dirs;
 297     }
 298
 299     /* Check the directions of capture */
 300     for (i = 0; i < NUM_OF_DIRECTIONS; i++) {
 301         dirs |= reversi_is_valid_direction(game, row, col, player, DIRECTIONS[i]);
 302     }
 303
 304     return dirs;
 305 }
 306
 307
 308 /* Flips the stones in the specified direction after the specified
 309  * player has placed a stone in the specified cell. The move is
 310  * assumed to be valid.
 311  *
 312  * Returns the number of flipped stones in that direction
 313  */
 314 static int reversi_flip_stones(reversi_board_t *game,
 315         const int row, const int col, const int player, const int direction) {
 316     int row_delta, col_delta, r, c;
 317     int other_color;
 318     int flip_cnt; /* Number of stones flipped */
 319
 320     row_delta = reversi_row_delta(direction);
 321     col_delta = reversi_column_delta(direction);
 322     other_color = reversi_flipped_color(player);
 323
 324     r = row + row_delta;
 325     c = col + col_delta;
 326
 327     flip_cnt = 0;
 328     while (reversi_is_position_on_board(r, c) &&
 329             (game->board[r][c] == other_color)) {
 330         game->board[r][c] = player;
 331         r += row_delta;
 332         c += col_delta;
 333         flip_cnt++;
 334     }
 335
 336     return flip_cnt;
 337 }
 338
 339
 340 /* Tries to make a move (place a stone) at the specified position.
 341  * If the move is valid the board is changed. Otherwise nothing happens.
 342  *
 343  * Params:
 344  *   - game: current state of the game
 345  *   - row: 0-based row number of the move to make
 346  *   - col: 0-based column number of the move to make
 347  *   - player: who makes the move (WHITE/BLACK)
 348  *
 349  * Returns the number of flipped (captured) stones (>0) iff the move
 350  * was valid or 0 if the move was not valid. Note that in the case of
 351  * a valid move, the stone itself is not counted.
 352  */
 353 int reversi_make_move(reversi_board_t *game,
 354         const int row, const int col, const int player) {
 355     int dirs, cnt, i;
 356
 357     dirs = reversi_is_valid_move(game, row, col, player);
 358     if (dirs == 0) {
 359         return 0;
 360     }
 361
 362     /* Place the stone into the cell */
 363     game->board[row][col] = player;
 364
 365     /* Capture stones in all possible directions */
 366     cnt = 0;
 367     for (i = 0; i < NUM_OF_DIRECTIONS; i++) {
 368         if (dirs & DIRECTIONS[i]) {
 369             cnt += reversi_flip_stones(game, row, col, player, DIRECTIONS[i]);
 370         }
 371     }
 372
 373     /* Remember the move */
 374     i = reversi_count_moves(game);
 375     game->history[i-1] = MAKE_MOVE(row, col, player);
 376
 377     return cnt;
 378 }