diff options
author | Antoine Cellerier <dionoea@videolan.org> | 2007-07-01 20:48:51 +0000 |
---|---|---|
committer | Antoine Cellerier <dionoea@videolan.org> | 2007-07-01 20:48:51 +0000 |
commit | cd82964e5d42b0252b8f14f15fc80709def37984 (patch) | |
tree | c9ef436d40b69f70b3d8d4c9967d8fdc812f3277 /apps | |
parent | 58f97f517a2d5918b8a18617130c2fce09af7683 (diff) | |
download | rockbox-cd82964e5d42b0252b8f14f15fc80709def37984.tar.gz rockbox-cd82964e5d42b0252b8f14f15fc80709def37984.zip |
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
Diffstat (limited to 'apps')
-rw-r--r-- | apps/plugins/reversi/reversi-game.c | 33 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-game.h | 14 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-gui.c | 22 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy-naive.c | 5 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy-simple.c | 3 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy.c | 1 | ||||
-rw-r--r-- | 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) { | |||
120 | * can make a move. Note that the implementation is not correct | 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 | 121 | * as a game may be finished even if there are free cells |
122 | */ | 122 | */ |
123 | bool reversi_game_is_finished(const reversi_board_t *game) { | 123 | bool reversi_game_is_finished(const reversi_board_t *game, int player) { |
124 | return (reversi_count_free_cells(game) == 0); | 124 | return (reversi_count_free_cells(game) == 0) |
125 | } | 125 | || (reversi_count_passes(game,player) == 2); |
126 | |||
127 | |||
128 | /* Finds out who should place the next stone. It's the partner | ||
129 | * of the last move or WHITE if the game is just started. | ||
130 | * | ||
131 | * Returns WHITE or BLACK. | ||
132 | */ | ||
133 | int reversi_get_turn(const reversi_board_t *game) { | ||
134 | int moves; | ||
135 | moves = reversi_count_moves(game); | ||
136 | if (moves == 0) { | ||
137 | return WHITE; | ||
138 | } else { | ||
139 | return reversi_flipped_color(MOVE_PLAYER(game->history[moves-1])); | ||
140 | } | ||
141 | } | 126 | } |
142 | 127 | ||
143 | 128 | ||
@@ -165,6 +150,7 @@ static int reversi_count_player_moves(const reversi_board_t *game, | |||
165 | return cnt; | 150 | return cnt; |
166 | } | 151 | } |
167 | 152 | ||
153 | /* Returns the number of moves available for the specified player */ | ||
168 | int reversi_count_player_available_moves(const reversi_board_t *game, | 154 | int reversi_count_player_available_moves(const reversi_board_t *game, |
169 | const int player) { | 155 | const int player) { |
170 | int cnt = 0, row, col; | 156 | int cnt = 0, row, col; |
@@ -176,6 +162,17 @@ int reversi_count_player_available_moves(const reversi_board_t *game, | |||
176 | return cnt; | 162 | return cnt; |
177 | } | 163 | } |
178 | 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 | } | ||
179 | 176 | ||
180 | /* Returns the number of moves made by WHITE so far */ | 177 | /* Returns the number of moves made by WHITE so far */ |
181 | int reversi_count_white_moves(const reversi_board_t *game) { | 178 | 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 @@ | |||
23 | #include <stdbool.h> | 23 | #include <stdbool.h> |
24 | #include "plugin.h" | 24 | #include "plugin.h" |
25 | 25 | ||
26 | #define WHITE 1 /* WHITE constant, it always plays first (as in chess) */ | 26 | #define WHITE 1 /* WHITE constant, it always plays first (as in chess) */ |
27 | #define BLACK 2 /* BLACK constant */ | 27 | #define BLACK -1 /* BLACK constant */ |
28 | #define FREE 0 /* Free place constant */ | 28 | #define FREE 0 /* Free place constant */ |
29 | 29 | ||
30 | #define BOARD_SIZE 8 | 30 | #define BOARD_SIZE 8 |
31 | #define INIT_STONES 4 | 31 | #define INIT_STONES 4 |
32 | 32 | ||
33 | /* Description of a move. A move is stored as a byte in the following format: | 33 | /* Description of a move. A move is stored as a byte in the following format: |
@@ -50,7 +50,7 @@ typedef unsigned char move_t; | |||
50 | /* State of a board */ | 50 | /* State of a board */ |
51 | typedef struct _reversi_board_t { | 51 | typedef struct _reversi_board_t { |
52 | /* The current state of the game (BLACK/WHITE/FREE) */ | 52 | /* The current state of the game (BLACK/WHITE/FREE) */ |
53 | char board[BOARD_SIZE][BOARD_SIZE]; | 53 | int board[BOARD_SIZE][BOARD_SIZE]; |
54 | 54 | ||
55 | /* Game history. First move (mostly, but not necessarily, black) is stored | 55 | /* Game history. First move (mostly, but not necessarily, black) is stored |
56 | * in history[0], second move (mostly, but not necessarily, white) is | 56 | * in history[0], second move (mostly, but not necessarily, white) is |
@@ -64,8 +64,7 @@ typedef struct _reversi_board_t { | |||
64 | 64 | ||
65 | void reversi_init_game(reversi_board_t *game); | 65 | void reversi_init_game(reversi_board_t *game); |
66 | int reversi_flipped_color(const int color); | 66 | int reversi_flipped_color(const int color); |
67 | bool reversi_game_is_finished(const reversi_board_t *game); | 67 | bool reversi_game_is_finished(const reversi_board_t *game, int cur_player); |
68 | int reversi_get_turn(const reversi_board_t *game); | ||
69 | int reversi_count_occupied_cells(const reversi_board_t *game, | 68 | int reversi_count_occupied_cells(const reversi_board_t *game, |
70 | int *white_count, int *black_count); | 69 | int *white_count, int *black_count); |
71 | int reversi_count_moves(const reversi_board_t *game); | 70 | int reversi_count_moves(const reversi_board_t *game); |
@@ -77,6 +76,7 @@ int reversi_is_valid_move(const reversi_board_t *game, | |||
77 | const int row, const int col, const int player); | 76 | const int row, const int col, const int player); |
78 | int reversi_count_player_available_moves(const reversi_board_t *game, | 77 | int reversi_count_player_available_moves(const reversi_board_t *game, |
79 | const int player); | 78 | const int player); |
79 | int reversi_count_passes(const reversi_board_t *game, const int player); | ||
80 | 80 | ||
81 | 81 | ||
82 | #endif | 82 | #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; | |||
190 | static cursor_wrap_mode_t cursor_wrap_mode; | 190 | static cursor_wrap_mode_t cursor_wrap_mode; |
191 | 191 | ||
192 | static bool quit_plugin; | 192 | static bool quit_plugin; |
193 | static bool game_finished; | ||
193 | 194 | ||
194 | 195 | ||
195 | /* Initialises the state of the game (starts a new game) */ | 196 | /* Initialises the state of the game (starts a new game) */ |
196 | static void reversi_gui_init(void) { | 197 | static void reversi_gui_init(void) { |
197 | reversi_init_game(&game); | 198 | reversi_init_game(&game); |
198 | white_strategy = &strategy_human; | 199 | game_finished = false; |
199 | black_strategy = &strategy_human; | ||
200 | cur_player = BLACK; | 200 | cur_player = BLACK; |
201 | 201 | ||
202 | /* Place the cursor so that WHITE can make a move */ | 202 | /* Place the cursor so that WHITE can make a move */ |
@@ -330,9 +330,10 @@ static struct opt_items strategy_settings[] = { | |||
330 | { "Human", NULL }, | 330 | { "Human", NULL }, |
331 | { "Naive robot", NULL }, | 331 | { "Naive robot", NULL }, |
332 | { "Simple robot", NULL }, | 332 | { "Simple robot", NULL }, |
333 | //{ "AB robot", NULL }, | ||
333 | }; | 334 | }; |
334 | static const game_strategy_t * const strategy_values[] = { | 335 | static const game_strategy_t * const strategy_values[] = { |
335 | &strategy_human, &strategy_naive, &strategy_simple }; | 336 | &strategy_human, &strategy_naive, &strategy_simple, /*&strategy_ab*/ }; |
336 | 337 | ||
337 | 338 | ||
338 | /* Sets the strategy for the specified player. 'player' is the | 339 | /* Sets the strategy for the specified player. 'player' is the |
@@ -354,6 +355,9 @@ static bool reversi_gui_choose_strategy( | |||
354 | result = rb->set_option(prompt, &index, INT, strategy_settings, num_items, NULL); | 355 | result = rb->set_option(prompt, &index, INT, strategy_settings, num_items, NULL); |
355 | (*player) = strategy_values[index]; | 356 | (*player) = strategy_values[index]; |
356 | 357 | ||
358 | if((*player)->init_func) | ||
359 | (*player)->init_func(&game); | ||
360 | |||
357 | return result; | 361 | return result; |
358 | } | 362 | } |
359 | 363 | ||
@@ -557,6 +561,8 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { | |||
557 | 561 | ||
558 | game.rb = rb; | 562 | game.rb = rb; |
559 | rb->srand(*rb->current_tick); /* Some AIs use rand() */ | 563 | rb->srand(*rb->current_tick); /* Some AIs use rand() */ |
564 | white_strategy = &strategy_human; | ||
565 | black_strategy = &strategy_human; | ||
560 | 566 | ||
561 | reversi_gui_init(); | 567 | reversi_gui_init(); |
562 | cursor_wrap_mode = WRAP_FLAT; | 568 | cursor_wrap_mode = WRAP_FLAT; |
@@ -580,21 +586,21 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { | |||
580 | break; | 586 | break; |
581 | } | 587 | } |
582 | 588 | ||
583 | if(cur_strategy->is_robot) { | 589 | if(cur_strategy->is_robot && !game_finished) { |
584 | /* TODO: Check move validity */ | ||
585 | move_t m = cur_strategy->move_func(&game, cur_player); | 590 | move_t m = cur_strategy->move_func(&game, cur_player); |
586 | reversi_make_move(&game, MOVE_ROW(m), MOVE_COL(m), cur_player); | 591 | reversi_make_move(&game, MOVE_ROW(m), MOVE_COL(m), cur_player); |
587 | cur_player = reversi_flipped_color(cur_player); | 592 | cur_player = reversi_flipped_color(cur_player); |
588 | draw_screen = true; | 593 | draw_screen = true; |
589 | /* TODO: Add some delay to prevent it from being too fast ? */ | 594 | /* TODO: Add some delay to prevent it from being too fast ? */ |
590 | /* TODO: Don't duplicate end of game check */ | 595 | /* TODO: Don't duplicate end of game check */ |
591 | if (reversi_game_is_finished(&game)) { | 596 | if (reversi_game_is_finished(&game, cur_player)) { |
592 | reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); | 597 | reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); |
593 | rb->snprintf(msg_buf, sizeof(msg_buf), | 598 | rb->snprintf(msg_buf, sizeof(msg_buf), |
594 | "Game over. %s have won.", | 599 | "Game over. %s have won.", |
595 | (w_cnt>b_cnt?"WHITE":"BLACK")); | 600 | (w_cnt>b_cnt?"WHITE":"BLACK")); |
596 | rb->splash(HZ*2, msg_buf); | 601 | rb->splash(HZ*2, msg_buf); |
597 | draw_screen = true; /* Must update screen after splash */ | 602 | draw_screen = true; /* Must update screen after splash */ |
603 | game_finished = true; | ||
598 | } | 604 | } |
599 | continue; | 605 | continue; |
600 | } | 606 | } |
@@ -618,17 +624,19 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { | |||
618 | && (lastbutton != REVERSI_BUTTON_MAKE_MOVE_PRE)) | 624 | && (lastbutton != REVERSI_BUTTON_MAKE_MOVE_PRE)) |
619 | break; | 625 | break; |
620 | #endif | 626 | #endif |
627 | if (game_finished) break; | ||
621 | if (reversi_make_move(&game, cur_row, cur_col, cur_player) > 0) { | 628 | if (reversi_make_move(&game, cur_row, cur_col, cur_player) > 0) { |
622 | /* Move was made. Global changes on the board are possible */ | 629 | /* Move was made. Global changes on the board are possible */ |
623 | draw_screen = true; /* Redraw the screen next time */ | 630 | draw_screen = true; /* Redraw the screen next time */ |
624 | cur_player = reversi_flipped_color(cur_player); | 631 | cur_player = reversi_flipped_color(cur_player); |
625 | if (reversi_game_is_finished(&game)) { | 632 | if (reversi_game_is_finished(&game, cur_player)) { |
626 | reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); | 633 | reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); |
627 | rb->snprintf(msg_buf, sizeof(msg_buf), | 634 | rb->snprintf(msg_buf, sizeof(msg_buf), |
628 | "Game over. %s have won.", | 635 | "Game over. %s have won.", |
629 | (w_cnt>b_cnt?"WHITE":"BLACK")); | 636 | (w_cnt>b_cnt?"WHITE":"BLACK")); |
630 | rb->splash(HZ*2, msg_buf); | 637 | rb->splash(HZ*2, msg_buf); |
631 | draw_screen = true; /* Must update screen after splash */ | 638 | draw_screen = true; /* Must update screen after splash */ |
639 | game_finished = true; | ||
632 | } | 640 | } |
633 | } else { | 641 | } else { |
634 | /* An attempt to make an invalid move */ | 642 | /* 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 @@ | |||
26 | 26 | ||
27 | static move_t naive_move_func(const reversi_board_t *game, int player) { | 27 | static move_t naive_move_func(const reversi_board_t *game, int player) { |
28 | int num_moves = reversi_count_player_available_moves(game, player); | 28 | int num_moves = reversi_count_player_available_moves(game, player); |
29 | int r = game->rb->rand()%num_moves; | 29 | int r; |
30 | int row = 0; | 30 | int row = 0; |
31 | int col = 0; | 31 | int col = 0; |
32 | if(!num_moves) return MOVE_INVALID; | ||
33 | r = game->rb->rand()%num_moves; | ||
32 | while(true) { | 34 | while(true) { |
33 | if(reversi_is_valid_move(game, row, col, player)) { | 35 | if(reversi_is_valid_move(game, row, col, player)) { |
34 | r--; | 36 | r--; |
@@ -49,5 +51,6 @@ static move_t naive_move_func(const reversi_board_t *game, int player) { | |||
49 | 51 | ||
50 | const game_strategy_t strategy_naive = { | 52 | const game_strategy_t strategy_naive = { |
51 | true, | 53 | true, |
54 | NULL, | ||
52 | naive_move_func | 55 | naive_move_func |
53 | }; | 56 | }; |
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, | |||
33 | dst->rb->memcpy(dst->history,src->history, | 33 | dst->rb->memcpy(dst->history,src->history, |
34 | (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t)); | 34 | (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t)); |
35 | for(i=0;i<BOARD_SIZE;i++) { | 35 | for(i=0;i<BOARD_SIZE;i++) { |
36 | dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE); | 36 | dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE*sizeof(int)); |
37 | } | 37 | } |
38 | } | 38 | } |
39 | 39 | ||
@@ -113,5 +113,6 @@ static move_t simple_move_func(const reversi_board_t *game, int player) { | |||
113 | 113 | ||
114 | const game_strategy_t strategy_simple = { | 114 | const game_strategy_t strategy_simple = { |
115 | true, | 115 | true, |
116 | NULL, | ||
116 | simple_move_func | 117 | simple_move_func |
117 | }; | 118 | }; |
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 @@ | |||
23 | /* Strategy that requires interaction with the user */ | 23 | /* Strategy that requires interaction with the user */ |
24 | const game_strategy_t strategy_human = { | 24 | const game_strategy_t strategy_human = { |
25 | false, | 25 | false, |
26 | NULL, | ||
26 | NULL | 27 | NULL |
27 | }; | 28 | }; |
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 @@ | |||
28 | a move has been considered or HISTORY_INVALID_ENTRY if no move | 28 | a move has been considered or HISTORY_INVALID_ENTRY if no move |
29 | has been considered. The board should not be modified. */ | 29 | has been considered. The board should not be modified. */ |
30 | typedef move_t (*move_func_t)(const reversi_board_t *game, int color); | 30 | typedef move_t (*move_func_t)(const reversi_board_t *game, int color); |
31 | typedef void (*init_func_t)(const reversi_board_t *game); | ||
31 | 32 | ||
32 | /* A playing party/strategy */ | 33 | /* A playing party/strategy */ |
33 | typedef struct _game_strategy_t { | 34 | typedef struct _game_strategy_t { |
34 | const bool is_robot; /* Is the player a robot or does it require user input? */ | 35 | const bool is_robot; /* Is the player a robot or does it require user input? */ |
35 | move_func_t move_func; /* Function for advicing a move */ | 36 | init_func_t init_func; /* Initialise strategy */ |
37 | move_func_t move_func; /* Make a move */ | ||
36 | } game_strategy_t; | 38 | } game_strategy_t; |
37 | 39 | ||
38 | 40 | ||
@@ -40,5 +42,9 @@ typedef struct _game_strategy_t { | |||
40 | extern const game_strategy_t strategy_human; | 42 | extern const game_strategy_t strategy_human; |
41 | extern const game_strategy_t strategy_naive; | 43 | extern const game_strategy_t strategy_naive; |
42 | extern const game_strategy_t strategy_simple; | 44 | extern const game_strategy_t strategy_simple; |
45 | //extern const game_strategy_t strategy_ab; | ||
46 | |||
47 | #define CHAOSNOISE 0.05 /**< Changerate of heuristic-value */ | ||
48 | #define CHAOSPROB 0.1 /**< Probability of change of the heuristic-value */ | ||
43 | 49 | ||
44 | #endif | 50 | #endif |