diff options
author | Antoine Cellerier <dionoea@videolan.org> | 2007-07-01 17:51:38 +0000 |
---|---|---|
committer | Antoine Cellerier <dionoea@videolan.org> | 2007-07-01 17:51:38 +0000 |
commit | 9af42897706548a400a8444066b6ee4900c284f4 (patch) | |
tree | 4d8c63a2c267779cb3311e16e3a75843c4a8809a | |
parent | e76e138097ce8789821ce5be9ad9271ed46d8561 (diff) | |
download | rockbox-9af42897706548a400a8444066b6ee4900c284f4.tar.gz rockbox-9af42897706548a400a8444066b6ee4900c284f4.zip |
Implement 2 simple AIs for reversi:
* naive: plays random moves
* simple: plays highest score move (Even though it's named simple i can't beat it :/)
More AIs are yet to come (I'll be using those in hinversi).
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@13755 a1c6a512-1295-4272-9138-f99709370657
-rw-r--r-- | apps/plugins/reversi/SOURCES | 4 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-game.c | 13 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-game.h | 7 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-gui.c | 38 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy-naive.c | 53 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy-simple.c | 90 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy.c | 32 | ||||
-rw-r--r-- | apps/plugins/reversi/reversi-strategy.h | 4 |
8 files changed, 202 insertions, 39 deletions
diff --git a/apps/plugins/reversi/SOURCES b/apps/plugins/reversi/SOURCES index 342e4d0e26..575e9e079c 100644 --- a/apps/plugins/reversi/SOURCES +++ b/apps/plugins/reversi/SOURCES | |||
@@ -1,3 +1,5 @@ | |||
1 | reversi-game.c | 1 | reversi-game.c |
2 | reversi-strategy.c | ||
3 | reversi-gui.c | 2 | reversi-gui.c |
3 | reversi-strategy.c | ||
4 | reversi-strategy-naive.c | ||
5 | reversi-strategy-simple.c | ||
diff --git a/apps/plugins/reversi/reversi-game.c b/apps/plugins/reversi/reversi-game.c index 80893b7270..e3d11eaf53 100644 --- a/apps/plugins/reversi/reversi-game.c +++ b/apps/plugins/reversi/reversi-game.c | |||
@@ -165,6 +165,17 @@ static int reversi_count_player_moves(const reversi_board_t *game, | |||
165 | return cnt; | 165 | return cnt; |
166 | } | 166 | } |
167 | 167 | ||
168 | int reversi_count_player_available_moves(const reversi_board_t *game, | ||
169 | const int player) { | ||
170 | int cnt = 0, row, col; | ||
171 | for(row=0;row<BOARD_SIZE;row++) { | ||
172 | for(col=0;col<BOARD_SIZE;col++) { | ||
173 | if(reversi_is_valid_move(game, row, col, player)) cnt++; | ||
174 | } | ||
175 | } | ||
176 | return cnt; | ||
177 | } | ||
178 | |||
168 | 179 | ||
169 | /* Returns the number of moves made by WHITE so far */ | 180 | /* Returns the number of moves made by WHITE so far */ |
170 | int reversi_count_white_moves(const reversi_board_t *game) { | 181 | int reversi_count_white_moves(const reversi_board_t *game) { |
@@ -273,7 +284,7 @@ static int reversi_is_valid_direction(const reversi_board_t *game, | |||
273 | * Returns 0 if the move is not valid or, otherwise, the or'd | 284 | * Returns 0 if the move is not valid or, otherwise, the or'd |
274 | * directions in which stones would be captured. | 285 | * directions in which stones would be captured. |
275 | */ | 286 | */ |
276 | static int reversi_is_valid_move(const reversi_board_t *game, | 287 | int reversi_is_valid_move(const reversi_board_t *game, |
277 | const int row, const int col, const int player) { | 288 | const int row, const int col, const int player) { |
278 | int dirs, i; | 289 | int dirs, i; |
279 | dirs = 0; | 290 | dirs = 0; |
diff --git a/apps/plugins/reversi/reversi-game.h b/apps/plugins/reversi/reversi-game.h index a7d0329d1f..a13d336d45 100644 --- a/apps/plugins/reversi/reversi-game.h +++ b/apps/plugins/reversi/reversi-game.h | |||
@@ -21,6 +21,7 @@ | |||
21 | #define _REVERSI_GAME_H | 21 | #define _REVERSI_GAME_H |
22 | 22 | ||
23 | #include <stdbool.h> | 23 | #include <stdbool.h> |
24 | #include "plugin.h" | ||
24 | 25 | ||
25 | #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) */ |
26 | #define BLACK 2 /* BLACK constant */ | 27 | #define BLACK 2 /* BLACK constant */ |
@@ -56,6 +57,8 @@ typedef struct _reversi_board_t { | |||
56 | * stored in history[1] etc. | 57 | * stored in history[1] etc. |
57 | */ | 58 | */ |
58 | move_t history[BOARD_SIZE*BOARD_SIZE - INIT_STONES]; | 59 | move_t history[BOARD_SIZE*BOARD_SIZE - INIT_STONES]; |
60 | |||
61 | struct plugin_api *rb; | ||
59 | } reversi_board_t; | 62 | } reversi_board_t; |
60 | 63 | ||
61 | 64 | ||
@@ -70,6 +73,10 @@ int reversi_count_white_moves(const reversi_board_t *game); | |||
70 | int reversi_count_black_moves(const reversi_board_t *game); | 73 | int reversi_count_black_moves(const reversi_board_t *game); |
71 | int reversi_make_move(reversi_board_t *game, const int row, | 74 | int reversi_make_move(reversi_board_t *game, const int row, |
72 | const int col, const int player); | 75 | const int col, const int player); |
76 | int reversi_is_valid_move(const reversi_board_t *game, | ||
77 | const int row, const int col, const int player); | ||
78 | int reversi_count_player_available_moves(const reversi_board_t *game, | ||
79 | const int player); | ||
73 | 80 | ||
74 | 81 | ||
75 | #endif | 82 | #endif |
diff --git a/apps/plugins/reversi/reversi-gui.c b/apps/plugins/reversi/reversi-gui.c index e543563729..5c759a02f1 100644 --- a/apps/plugins/reversi/reversi-gui.c +++ b/apps/plugins/reversi/reversi-gui.c | |||
@@ -328,11 +328,11 @@ static const cursor_wrap_mode_t cursor_wrap_mode_values[3] = { | |||
328 | 328 | ||
329 | static struct opt_items strategy_settings[] = { | 329 | static struct opt_items strategy_settings[] = { |
330 | { "Human", NULL }, | 330 | { "Human", NULL }, |
331 | { "Silly robot", NULL }, | 331 | { "Naive robot", NULL }, |
332 | { "Smart robot", NULL }, | 332 | { "Simple robot", NULL }, |
333 | }; | 333 | }; |
334 | static const game_strategy_t * const strategy_values[] = { | 334 | static const game_strategy_t * const strategy_values[] = { |
335 | &strategy_human, &strategy_novice, &strategy_expert }; | 335 | &strategy_human, &strategy_naive, &strategy_simple }; |
336 | 336 | ||
337 | 337 | ||
338 | /* Sets the strategy for the specified player. 'player' is the | 338 | /* Sets the strategy for the specified player. 'player' is the |
@@ -555,6 +555,9 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { | |||
555 | /* Avoid compiler warnings */ | 555 | /* Avoid compiler warnings */ |
556 | (void)parameter; | 556 | (void)parameter; |
557 | 557 | ||
558 | game.rb = rb; | ||
559 | rb->srand(*rb->current_tick); /* Some AIs use rand() */ | ||
560 | |||
558 | reversi_gui_init(); | 561 | reversi_gui_init(); |
559 | cursor_wrap_mode = WRAP_FLAT; | 562 | cursor_wrap_mode = WRAP_FLAT; |
560 | 563 | ||
@@ -563,10 +566,39 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) { | |||
563 | quit_plugin = false; | 566 | quit_plugin = false; |
564 | draw_screen = true; | 567 | draw_screen = true; |
565 | while (!exit && !quit_plugin) { | 568 | while (!exit && !quit_plugin) { |
569 | const game_strategy_t *cur_strategy = NULL; | ||
566 | if (draw_screen) { | 570 | if (draw_screen) { |
567 | reversi_gui_display_board(); | 571 | reversi_gui_display_board(); |
568 | draw_screen = false; | 572 | draw_screen = false; |
569 | } | 573 | } |
574 | switch(cur_player) { | ||
575 | case BLACK: | ||
576 | cur_strategy = black_strategy; | ||
577 | break; | ||
578 | case WHITE: | ||
579 | cur_strategy = white_strategy; | ||
580 | break; | ||
581 | } | ||
582 | |||
583 | if(cur_strategy->is_robot) { | ||
584 | /* TODO: Check move validity */ | ||
585 | move_t m = cur_strategy->move_func(&game, cur_player); | ||
586 | reversi_make_move(&game, MOVE_ROW(m), MOVE_COL(m), cur_player); | ||
587 | cur_player = reversi_flipped_color(cur_player); | ||
588 | draw_screen = true; | ||
589 | /* TODO: Add some delay to prevent it from being too fast ? */ | ||
590 | /* TODO: Don't duplicate end of game check */ | ||
591 | if (reversi_game_is_finished(&game)) { | ||
592 | reversi_count_occupied_cells(&game, &w_cnt, &b_cnt); | ||
593 | rb->snprintf(msg_buf, sizeof(msg_buf), | ||
594 | "Game over. %s have won.", | ||
595 | (w_cnt>b_cnt?"WHITE":"BLACK")); | ||
596 | rb->splash(HZ*2, msg_buf); | ||
597 | draw_screen = true; /* Must update screen after splash */ | ||
598 | } | ||
599 | continue; | ||
600 | } | ||
601 | |||
570 | button = rb->button_get(true); | 602 | button = rb->button_get(true); |
571 | 603 | ||
572 | switch (button) { | 604 | switch (button) { |
diff --git a/apps/plugins/reversi/reversi-strategy-naive.c b/apps/plugins/reversi/reversi-strategy-naive.c new file mode 100644 index 0000000000..44a6dc9da0 --- /dev/null +++ b/apps/plugins/reversi/reversi-strategy-naive.c | |||
@@ -0,0 +1,53 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (c) 2007 Antoine Cellerier | ||
11 | * | ||
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. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | |||
20 | #include "reversi-strategy.h" | ||
21 | |||
22 | /** | ||
23 | * Naive/Stupid strategy: | ||
24 | * Random moves | ||
25 | */ | ||
26 | |||
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); | ||
29 | int r = game->rb->rand()%num_moves; | ||
30 | int row = 0; | ||
31 | int col = 0; | ||
32 | while(true) { | ||
33 | if(reversi_is_valid_move(game, row, col, player)) { | ||
34 | r--; | ||
35 | if(r<0) { | ||
36 | return MAKE_MOVE(row,col,player); | ||
37 | } | ||
38 | } | ||
39 | col ++; | ||
40 | if(col==BOARD_SIZE) { | ||
41 | col = 0; | ||
42 | row ++; | ||
43 | if(row==BOARD_SIZE) { | ||
44 | row = 0; | ||
45 | } | ||
46 | } | ||
47 | } | ||
48 | } | ||
49 | |||
50 | const game_strategy_t strategy_naive = { | ||
51 | true, | ||
52 | naive_move_func | ||
53 | }; | ||
diff --git a/apps/plugins/reversi/reversi-strategy-simple.c b/apps/plugins/reversi/reversi-strategy-simple.c new file mode 100644 index 0000000000..f1d2b83cc9 --- /dev/null +++ b/apps/plugins/reversi/reversi-strategy-simple.c | |||
@@ -0,0 +1,90 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (c) 2007 Antoine Cellerier | ||
11 | * | ||
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. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | |||
20 | #include "reversi-strategy.h" | ||
21 | |||
22 | /** | ||
23 | * Simple strategy: | ||
24 | * A very simple strategy. Makes the highest scoring move. | ||
25 | * From Algorithm by Claudio Clemens in hinversi, simpleClient.c | ||
26 | */ | ||
27 | |||
28 | static void reversi_copy_board(reversi_board_t *dst, | ||
29 | const reversi_board_t *src) { | ||
30 | int i; | ||
31 | dst->rb = src->rb; | ||
32 | dst->rb->memcpy(dst->history,src->history, | ||
33 | (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t)); | ||
34 | for(i=0;i<BOARD_SIZE;i++) { | ||
35 | dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE); | ||
36 | } | ||
37 | } | ||
38 | |||
39 | static int reversi_sim_move(const reversi_board_t *game, const int row, | ||
40 | const int col, const int player) { | ||
41 | /* Gruik */ | ||
42 | reversi_board_t game_clone; | ||
43 | reversi_copy_board(&game_clone,game); | ||
44 | return reversi_make_move(&game_clone,row,col,player); | ||
45 | } | ||
46 | |||
47 | static move_t simple_move_func(const reversi_board_t *game, int player) { | ||
48 | int max = 0; | ||
49 | int count = 0; | ||
50 | int row, col; | ||
51 | int r; | ||
52 | for(row=0; row<BOARD_SIZE; row++) { | ||
53 | for(col=0; col<BOARD_SIZE; col++) { | ||
54 | int v = reversi_sim_move(game,row,col,player); | ||
55 | if(v>max) { | ||
56 | max = v; | ||
57 | count = 1; | ||
58 | } | ||
59 | else if(v==max) { | ||
60 | count ++; | ||
61 | } | ||
62 | } | ||
63 | } | ||
64 | |||
65 | /* chose one of the moves which scores highest */ | ||
66 | r = game->rb->rand()%count; | ||
67 | row = 0; | ||
68 | col = 0; | ||
69 | while(true) { | ||
70 | if(reversi_sim_move(game, row, col, player)==max) { | ||
71 | r--; | ||
72 | if(r<0) { | ||
73 | return MAKE_MOVE(row,col,player); | ||
74 | } | ||
75 | } | ||
76 | col ++; | ||
77 | if(col==BOARD_SIZE) { | ||
78 | col = 0; | ||
79 | row ++; | ||
80 | if(row==BOARD_SIZE) { | ||
81 | row = 0; | ||
82 | } | ||
83 | } | ||
84 | } | ||
85 | } | ||
86 | |||
87 | const game_strategy_t strategy_simple = { | ||
88 | true, | ||
89 | simple_move_func | ||
90 | }; | ||
diff --git a/apps/plugins/reversi/reversi-strategy.c b/apps/plugins/reversi/reversi-strategy.c index 831c0cd92b..9adcbb661f 100644 --- a/apps/plugins/reversi/reversi-strategy.c +++ b/apps/plugins/reversi/reversi-strategy.c | |||
@@ -20,40 +20,8 @@ | |||
20 | #include "reversi-strategy.h" | 20 | #include "reversi-strategy.h" |
21 | #include <stddef.h> | 21 | #include <stddef.h> |
22 | 22 | ||
23 | |||
24 | /* Implementation of a rather weak player strategy */ | ||
25 | static move_t novice_move_func(const reversi_board_t *game, int color) { | ||
26 | /* TODO: Implement novice_move_func */ | ||
27 | (void)game; | ||
28 | (void)color; | ||
29 | return MOVE_INVALID; | ||
30 | } | ||
31 | |||
32 | |||
33 | /* Implementation of a good player strategy */ | ||
34 | static move_t expert_move_func(const reversi_board_t *game, int color) { | ||
35 | /* TODO: Implement expert_move_func */ | ||
36 | (void)game; | ||
37 | (void)color; | ||
38 | return MOVE_INVALID; | ||
39 | } | ||
40 | |||
41 | |||
42 | |||
43 | /* Strategy that requires interaction with the user */ | 23 | /* Strategy that requires interaction with the user */ |
44 | const game_strategy_t strategy_human = { | 24 | const game_strategy_t strategy_human = { |
45 | false, | 25 | false, |
46 | NULL | 26 | NULL |
47 | }; | 27 | }; |
48 | |||
49 | /* Robot that plays not very well (novice) */ | ||
50 | const game_strategy_t strategy_novice = { | ||
51 | true, | ||
52 | novice_move_func | ||
53 | }; | ||
54 | |||
55 | /* Robot that is hard to beat (expert) */ | ||
56 | const game_strategy_t strategy_expert = { | ||
57 | true, | ||
58 | expert_move_func | ||
59 | }; | ||
diff --git a/apps/plugins/reversi/reversi-strategy.h b/apps/plugins/reversi/reversi-strategy.h index 57bc3faf57..49e934ca1f 100644 --- a/apps/plugins/reversi/reversi-strategy.h +++ b/apps/plugins/reversi/reversi-strategy.h | |||
@@ -38,7 +38,7 @@ typedef struct _game_strategy_t { | |||
38 | 38 | ||
39 | /* --- Possible playing strategies --- */ | 39 | /* --- Possible playing strategies --- */ |
40 | extern const game_strategy_t strategy_human; | 40 | extern const game_strategy_t strategy_human; |
41 | extern const game_strategy_t strategy_novice; | 41 | extern const game_strategy_t strategy_naive; |
42 | extern const game_strategy_t strategy_expert; | 42 | extern const game_strategy_t strategy_simple; |
43 | 43 | ||
44 | #endif | 44 | #endif |