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