From cd82964e5d42b0252b8f14f15fc80709def37984 Mon Sep 17 00:00:00 2001 From: Antoine Cellerier Date: Sun, 1 Jul 2007 20:48:51 +0000 Subject: Make sure that reversi doesn't enter an infinite loop when using 1 or 2 AIs. + some changes that will be needed for more advanced AIs (which aren't ready to commit yet) git-svn-id: svn://svn.rockbox.org/rockbox/trunk@13758 a1c6a512-1295-4272-9138-f99709370657 --- apps/plugins/reversi/reversi-game.c | 33 ++++++++++++-------------- apps/plugins/reversi/reversi-game.h | 14 +++++------ apps/plugins/reversi/reversi-gui.c | 22 +++++++++++------ apps/plugins/reversi/reversi-strategy-naive.c | 5 +++- apps/plugins/reversi/reversi-strategy-simple.c | 3 ++- apps/plugins/reversi/reversi-strategy.c | 1 + apps/plugins/reversi/reversi-strategy.h | 8 ++++++- 7 files changed, 51 insertions(+), 35 deletions(-) diff --git a/apps/plugins/reversi/reversi-game.c b/apps/plugins/reversi/reversi-game.c index e3d11eaf53..4d4178bd0d 100644 --- a/apps/plugins/reversi/reversi-game.c +++ b/apps/plugins/reversi/reversi-game.c @@ -120,24 +120,9 @@ static int reversi_count_free_cells(const reversi_board_t *game) { * can make a move. Note that the implementation is not correct * as a game may be finished even if there are free cells */ -bool reversi_game_is_finished(const reversi_board_t *game) { - return (reversi_count_free_cells(game) == 0); -} - - -/* Finds out who should place the next stone. It's the partner - * of the last move or WHITE if the game is just started. - * - * Returns WHITE or BLACK. - */ -int reversi_get_turn(const reversi_board_t *game) { - int moves; - moves = reversi_count_moves(game); - if (moves == 0) { - return WHITE; - } else { - return reversi_flipped_color(MOVE_PLAYER(game->history[moves-1])); - } +bool reversi_game_is_finished(const reversi_board_t *game, int player) { + return (reversi_count_free_cells(game) == 0) + || (reversi_count_passes(game,player) == 2); } @@ -165,6 +150,7 @@ static int reversi_count_player_moves(const reversi_board_t *game, return cnt; } +/* Returns the number of moves available for the specified player */ int reversi_count_player_available_moves(const reversi_board_t *game, const int player) { int cnt = 0, row, col; @@ -176,6 +162,17 @@ int reversi_count_player_available_moves(const reversi_board_t *game, return cnt; } +/* Returns the number of players who HAVE to pass (2 == game is stuck) */ +int reversi_count_passes(const reversi_board_t *game, const int player) { + if(reversi_count_player_available_moves(game,player)==0) { + if(reversi_count_player_available_moves(game, + reversi_flipped_color(player))==0) { + return 2; + } + return 1; + } + return 0; +} /* Returns the number of moves made by WHITE so far */ int reversi_count_white_moves(const reversi_board_t *game) { diff --git a/apps/plugins/reversi/reversi-game.h b/apps/plugins/reversi/reversi-game.h index a13d336d45..de05df78f9 100644 --- a/apps/plugins/reversi/reversi-game.h +++ b/apps/plugins/reversi/reversi-game.h @@ -23,11 +23,11 @@ #include #include "plugin.h" -#define WHITE 1 /* WHITE constant, it always plays first (as in chess) */ -#define BLACK 2 /* BLACK constant */ -#define FREE 0 /* Free place constant */ +#define WHITE 1 /* WHITE constant, it always plays first (as in chess) */ +#define BLACK -1 /* BLACK constant */ +#define FREE 0 /* Free place constant */ -#define BOARD_SIZE 8 +#define BOARD_SIZE 8 #define INIT_STONES 4 /* Description of a move. A move is stored as a byte in the following format: @@ -50,7 +50,7 @@ typedef unsigned char move_t; /* State of a board */ typedef struct _reversi_board_t { /* The current state of the game (BLACK/WHITE/FREE) */ - char board[BOARD_SIZE][BOARD_SIZE]; + int board[BOARD_SIZE][BOARD_SIZE]; /* Game history. First move (mostly, but not necessarily, black) is stored * in history[0], second move (mostly, but not necessarily, white) is @@ -64,8 +64,7 @@ typedef struct _reversi_board_t { void reversi_init_game(reversi_board_t *game); int reversi_flipped_color(const int color); -bool reversi_game_is_finished(const reversi_board_t *game); -int reversi_get_turn(const reversi_board_t *game); +bool reversi_game_is_finished(const reversi_board_t *game, int cur_player); int reversi_count_occupied_cells(const reversi_board_t *game, int *white_count, int *black_count); int reversi_count_moves(const reversi_board_t *game); @@ -77,6 +76,7 @@ int reversi_is_valid_move(const reversi_board_t *game, const int row, const int col, const int player); int reversi_count_player_available_moves(const reversi_board_t *game, const int player); +int reversi_count_passes(const reversi_board_t *game, const int player); #endif diff --git a/apps/plugins/reversi/reversi-gui.c b/apps/plugins/reversi/reversi-gui.c index 5c759a02f1..dcf4dd8ccb 100644 --- a/apps/plugins/reversi/reversi-gui.c +++ b/apps/plugins/reversi/reversi-gui.c @@ -190,13 +190,13 @@ static int cur_player; static cursor_wrap_mode_t cursor_wrap_mode; static bool quit_plugin; +static bool game_finished; /* Initialises the state of the game (starts a new game) */ static void reversi_gui_init(void) { reversi_init_game(&game); - white_strategy = &strategy_human; - black_strategy = &strategy_human; + game_finished = false; cur_player = BLACK; /* Place the cursor so that WHITE can make a move */ @@ -330,9 +330,10 @@ static struct opt_items strategy_settings[] = { { "Human", NULL }, { "Naive robot", NULL }, { "Simple robot", NULL }, + //{ "AB robot", NULL }, }; static const game_strategy_t * const strategy_values[] = { - &strategy_human, &strategy_naive, &strategy_simple }; + &strategy_human, &strategy_naive, &strategy_simple, /*&strategy_ab*/ }; /* Sets the strategy for the specified player. 'player' is the @@ -354,6 +355,9 @@ static bool reversi_gui_choose_strategy( result = rb->set_option(prompt, &index, INT, strategy_settings, num_items, NULL); (*player) = strategy_values[index]; + if((*player)->init_func) + (*player)->init_func(&game); + return result; } @@ -557,6 +561,8 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { game.rb = rb; rb->srand(*rb->current_tick); /* Some AIs use rand() */ + white_strategy = &strategy_human; + black_strategy = &strategy_human; reversi_gui_init(); cursor_wrap_mode = WRAP_FLAT; @@ -580,21 +586,21 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { break; } - if(cur_strategy->is_robot) { - /* TODO: Check move validity */ + if(cur_strategy->is_robot && !game_finished) { move_t m = cur_strategy->move_func(&game, cur_player); reversi_make_move(&game, MOVE_ROW(m), MOVE_COL(m), cur_player); cur_player = reversi_flipped_color(cur_player); draw_screen = true; /* TODO: Add some delay to prevent it from being too fast ? */ /* TODO: Don't duplicate end of game check */ - if (reversi_game_is_finished(&game)) { + if (reversi_game_is_finished(&game, cur_player)) { reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); rb->snprintf(msg_buf, sizeof(msg_buf), "Game over. %s have won.", (w_cnt>b_cnt?"WHITE":"BLACK")); rb->splash(HZ*2, msg_buf); draw_screen = true; /* Must update screen after splash */ + game_finished = true; } continue; } @@ -618,17 +624,19 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { && (lastbutton != REVERSI_BUTTON_MAKE_MOVE_PRE)) break; #endif + if (game_finished) break; if (reversi_make_move(&game, cur_row, cur_col, cur_player) > 0) { /* Move was made. Global changes on the board are possible */ draw_screen = true; /* Redraw the screen next time */ cur_player = reversi_flipped_color(cur_player); - if (reversi_game_is_finished(&game)) { + if (reversi_game_is_finished(&game, cur_player)) { reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); rb->snprintf(msg_buf, sizeof(msg_buf), "Game over. %s have won.", (w_cnt>b_cnt?"WHITE":"BLACK")); rb->splash(HZ*2, msg_buf); draw_screen = true; /* Must update screen after splash */ + game_finished = true; } } else { /* An attempt to make an invalid move */ diff --git a/apps/plugins/reversi/reversi-strategy-naive.c b/apps/plugins/reversi/reversi-strategy-naive.c index 44a6dc9da0..ed01045951 100644 --- a/apps/plugins/reversi/reversi-strategy-naive.c +++ b/apps/plugins/reversi/reversi-strategy-naive.c @@ -26,9 +26,11 @@ static move_t naive_move_func(const reversi_board_t *game, int player) { int num_moves = reversi_count_player_available_moves(game, player); - int r = game->rb->rand()%num_moves; + int r; int row = 0; int col = 0; + if(!num_moves) return MOVE_INVALID; + r = game->rb->rand()%num_moves; while(true) { if(reversi_is_valid_move(game, row, col, player)) { r--; @@ -49,5 +51,6 @@ static move_t naive_move_func(const reversi_board_t *game, int player) { const game_strategy_t strategy_naive = { true, + NULL, naive_move_func }; diff --git a/apps/plugins/reversi/reversi-strategy-simple.c b/apps/plugins/reversi/reversi-strategy-simple.c index 9064922cba..0aca64c1ab 100644 --- a/apps/plugins/reversi/reversi-strategy-simple.c +++ b/apps/plugins/reversi/reversi-strategy-simple.c @@ -33,7 +33,7 @@ static void reversi_copy_board(reversi_board_t *dst, dst->rb->memcpy(dst->history,src->history, (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t)); for(i=0;irb->memcpy(dst->board[i],src->board[i],BOARD_SIZE); + dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE*sizeof(int)); } } @@ -113,5 +113,6 @@ static move_t simple_move_func(const reversi_board_t *game, int player) { const game_strategy_t strategy_simple = { true, + NULL, simple_move_func }; diff --git a/apps/plugins/reversi/reversi-strategy.c b/apps/plugins/reversi/reversi-strategy.c index 9adcbb661f..3f8ef45eaa 100644 --- a/apps/plugins/reversi/reversi-strategy.c +++ b/apps/plugins/reversi/reversi-strategy.c @@ -23,5 +23,6 @@ /* Strategy that requires interaction with the user */ const game_strategy_t strategy_human = { false, + NULL, NULL }; diff --git a/apps/plugins/reversi/reversi-strategy.h b/apps/plugins/reversi/reversi-strategy.h index 49e934ca1f..8328ea58db 100644 --- a/apps/plugins/reversi/reversi-strategy.h +++ b/apps/plugins/reversi/reversi-strategy.h @@ -28,11 +28,13 @@ a move has been considered or HISTORY_INVALID_ENTRY if no move has been considered. The board should not be modified. */ typedef move_t (*move_func_t)(const reversi_board_t *game, int color); +typedef void (*init_func_t)(const reversi_board_t *game); /* A playing party/strategy */ typedef struct _game_strategy_t { const bool is_robot; /* Is the player a robot or does it require user input? */ - move_func_t move_func; /* Function for advicing a move */ + init_func_t init_func; /* Initialise strategy */ + move_func_t move_func; /* Make a move */ } game_strategy_t; @@ -40,5 +42,9 @@ typedef struct _game_strategy_t { extern const game_strategy_t strategy_human; extern const game_strategy_t strategy_naive; extern const game_strategy_t strategy_simple; +//extern const game_strategy_t strategy_ab; + +#define CHAOSNOISE 0.05 /**< Changerate of heuristic-value */ +#define CHAOSPROB 0.1 /**< Probability of change of the heuristic-value */ #endif -- cgit v1.2.3