1 /***************************************************************************
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
10 * Copyright (c) 2006 Alexander Levin
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.
17 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
18 * KIND, either express or implied.
20 ****************************************************************************/
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.
30 #include "reversi-game.h"
33 * Constants for directions. The values are chosen so that
34 * they can be bit combined.
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 */
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
51 /* Initializes a reversi game */
52 void reversi_init_game(reversi_board_t
*game
) {
54 for (r
= 0; r
< BOARD_SIZE
; r
++) {
55 for (c
= 0; c
< BOARD_SIZE
; c
++) {
56 game
->board
[r
][c
] = FREE
;
59 game
->board
[3][3] = WHITE
;
60 game
->board
[4][4] = WHITE
;
61 game
->board
[3][4] = BLACK
;
62 game
->board
[4][3] = BLACK
;
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
;
72 /* Returns the 'flipped' color, e.g. WHITE for BLACK and vice versa */
73 int reversi_flipped_color(const int color
) {
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
;
94 for (r
= 0; r
< BOARD_SIZE
; r
++) {
95 for (c
= 0; c
< BOARD_SIZE
; c
++) {
96 if (game
->board
[r
][c
] == WHITE
) {
98 } else if (game
->board
[r
][c
] == BLACK
) {
103 if (white_count
!= NULL
) {
104 *white_count
= w_cnt
;
106 if (black_count
!= NULL
) {
107 *black_count
= b_cnt
;
109 return w_cnt
+ b_cnt
;
113 /* Returns the number of free cells on the board */
114 static int reversi_count_free_cells(const reversi_board_t
*game
) {
116 cnt
= reversi_count_occupied_cells(game
, NULL
, NULL
);
117 return BOARD_SIZE
*BOARD_SIZE
- cnt
;
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
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);
131 /* Returns the total number of moves made so far */
132 int reversi_count_moves(const reversi_board_t
*game
) {
134 cnt
= reversi_count_occupied_cells(game
, NULL
, NULL
);
135 return cnt
- INIT_STONES
;
139 /* Returns the number of moves made by the specified
140 * player (WHITE or BLACK) so far
142 static int reversi_count_player_moves(const reversi_board_t
*game
,
145 moves
= reversi_count_moves(game
);
147 for (i
= 0; i
< moves
; i
++) {
148 if (MOVE_PLAYER(game
->history
[i
]) == player
) {
155 /* Returns the number of moves available for the specified player */
156 int reversi_count_player_available_moves(const reversi_board_t
*game
,
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
++;
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) {
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
);
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
);
191 /* Checks whether the specified position is on the board
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
);
200 /* Returns the delta for row to move in the specified direction */
201 static int reversi_row_delta(const int direction
) {
219 /* Returns the delta for column to move in the specified direction */
220 static int reversi_column_delta(const int direction
) {
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.
241 * Returns 0 if no stones would be captured or 'direction' otherwise
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
;
247 int flip_cnt
; /* Number of stones that would be flipped */
249 row_delta
= reversi_row_delta(direction
);
250 col_delta
= reversi_column_delta(direction
);
251 other_color
= reversi_flipped_color(player
);
257 while (reversi_is_position_on_board(r
, c
) &&
258 (game
->board
[r
][c
] == other_color
)) {
264 if ((flip_cnt
> 0) && reversi_is_position_on_board(r
, c
) &&
265 (game
->board
[r
][c
] == player
)) {
273 /* Checks whether the move at the specified position would be valid.
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)
280 * Checks if the place is empty, the coordinates are legal,
281 * and some stones can be captured.
283 * Returns 0 if the move is not valid or, otherwise, the or'd
284 * directions in which stones would be captured.
286 int reversi_is_valid_move(const reversi_board_t
*game
,
287 const int row
, const int col
, const int player
) {
291 /* Check if coordinates are legal */
292 if (!reversi_is_position_on_board(row
, col
)) {
296 /* Check if the place is free */
297 if (game
->board
[row
][col
] != FREE
) {
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
]);
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.
314 * Returns the number of flipped stones in that direction
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
;
320 int flip_cnt
; /* Number of stones flipped */
322 row_delta
= reversi_row_delta(direction
);
323 col_delta
= reversi_column_delta(direction
);
324 other_color
= reversi_flipped_color(player
);
330 while (reversi_is_position_on_board(r
, c
) &&
331 (game
->board
[r
][c
] == other_color
)) {
332 game
->board
[r
][c
] = player
;
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.
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)
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.
355 int reversi_make_move(reversi_board_t
*game
,
356 const int row
, const int col
, const int player
) {
359 dirs
= reversi_is_valid_move(game
, row
, col
, player
);
364 /* Place the stone into the cell */
365 game
->board
[row
][col
] = player
;
367 /* Capture stones in all possible directions */
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
]);
375 /* Remember the move */
376 i
= reversi_count_moves(game
);
377 game
->history
[i
-1] = MAKE_MOVE(row
, col
, player
);