1 /***************************************************************************
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
10 * Copyright (c) 2006 Alexander Levin
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.
15 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
16 * KIND, either express or implied.
18 ****************************************************************************/
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.
28 #include "reversi-game.h"
31 * Constants for directions. The values are chosen so that
32 * they can be bit combined.
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 */
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
49 /* Initializes a reversi game */
50 void reversi_init_game(reversi_board_t
*game
) {
52 for (r
= 0; r
< BOARD_SIZE
; r
++) {
53 for (c
= 0; c
< BOARD_SIZE
; c
++) {
54 game
->board
[r
][c
] = FREE
;
57 game
->board
[3][3] = WHITE
;
58 game
->board
[4][4] = WHITE
;
59 game
->board
[3][4] = BLACK
;
60 game
->board
[4][3] = BLACK
;
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
;
70 /* Returns the 'flipped' color, e.g. WHITE for BLACK and vice versa */
71 int reversi_flipped_color(const int color
) {
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
;
92 for (r
= 0; r
< BOARD_SIZE
; r
++) {
93 for (c
= 0; c
< BOARD_SIZE
; c
++) {
94 if (game
->board
[r
][c
] == WHITE
) {
96 } else if (game
->board
[r
][c
] == BLACK
) {
101 if (white_count
!= NULL
) {
102 *white_count
= w_cnt
;
104 if (black_count
!= NULL
) {
105 *black_count
= b_cnt
;
107 return w_cnt
+ b_cnt
;
111 /* Returns the number of free cells on the board */
112 static int reversi_count_free_cells(const reversi_board_t
*game
) {
114 cnt
= reversi_count_occupied_cells(game
, NULL
, NULL
);
115 return BOARD_SIZE
*BOARD_SIZE
- cnt
;
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
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);
129 /* Returns the total number of moves made so far */
130 int reversi_count_moves(const reversi_board_t
*game
) {
132 cnt
= reversi_count_occupied_cells(game
, NULL
, NULL
);
133 return cnt
- INIT_STONES
;
137 /* Returns the number of moves made by the specified
138 * player (WHITE or BLACK) so far
140 static int reversi_count_player_moves(const reversi_board_t
*game
,
143 moves
= reversi_count_moves(game
);
145 for (i
= 0; i
< moves
; i
++) {
146 if (MOVE_PLAYER(game
->history
[i
]) == player
) {
153 /* Returns the number of moves available for the specified player */
154 int reversi_count_player_available_moves(const reversi_board_t
*game
,
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
++;
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) {
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
);
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
);
189 /* Checks whether the specified position is on the board
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
);
198 /* Returns the delta for row to move in the specified direction */
199 static int reversi_row_delta(const int direction
) {
217 /* Returns the delta for column to move in the specified direction */
218 static int reversi_column_delta(const int direction
) {
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.
239 * Returns 0 if no stones would be captured or 'direction' otherwise
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
;
245 int flip_cnt
; /* Number of stones that would be flipped */
247 row_delta
= reversi_row_delta(direction
);
248 col_delta
= reversi_column_delta(direction
);
249 other_color
= reversi_flipped_color(player
);
255 while (reversi_is_position_on_board(r
, c
) &&
256 (game
->board
[r
][c
] == other_color
)) {
262 if ((flip_cnt
> 0) && reversi_is_position_on_board(r
, c
) &&
263 (game
->board
[r
][c
] == player
)) {
271 /* Checks whether the move at the specified position would be valid.
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)
278 * Checks if the place is empty, the coordinates are legal,
279 * and some stones can be captured.
281 * Returns 0 if the move is not valid or, otherwise, the or'd
282 * directions in which stones would be captured.
284 int reversi_is_valid_move(const reversi_board_t
*game
,
285 const int row
, const int col
, const int player
) {
289 /* Check if coordinates are legal */
290 if (!reversi_is_position_on_board(row
, col
)) {
294 /* Check if the place is free */
295 if (game
->board
[row
][col
] != FREE
) {
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
]);
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.
312 * Returns the number of flipped stones in that direction
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
;
318 int flip_cnt
; /* Number of stones flipped */
320 row_delta
= reversi_row_delta(direction
);
321 col_delta
= reversi_column_delta(direction
);
322 other_color
= reversi_flipped_color(player
);
328 while (reversi_is_position_on_board(r
, c
) &&
329 (game
->board
[r
][c
] == other_color
)) {
330 game
->board
[r
][c
] = player
;
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.
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)
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.
353 int reversi_make_move(reversi_board_t
*game
,
354 const int row
, const int col
, const int player
) {
357 dirs
= reversi_is_valid_move(game
, row
, col
, player
);
362 /* Place the stone into the cell */
363 game
->board
[row
][col
] = player
;
365 /* Capture stones in all possible directions */
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
]);
373 /* Remember the move */
374 i
= reversi_count_moves(game
);
375 game
->history
[i
-1] = MAKE_MOVE(row
, col
, player
);