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

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 @@
 reversi-game.c
-reversi-strategy.c
 reversi-gui.c
+reversi-strategy.c
+reversi-strategy-naive.c
+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,
     return cnt;
 }
 
+int reversi_count_player_available_moves(const reversi_board_t *game,
+        const int player) {
+    int cnt = 0, row, col;
+    for(row=0;row<BOARD_SIZE;row++) {
+        for(col=0;col<BOARD_SIZE;col++) {
+            if(reversi_is_valid_move(game, row, col, player)) cnt++;
+        }
+    }
+    return cnt;
+}
+
 
 /* Returns the number of moves made by WHITE so far */
 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,
  * Returns 0 if the move is not valid or, otherwise, the or'd
  * directions in which stones would be captured.
  */
-static int reversi_is_valid_move(const reversi_board_t *game,
+int reversi_is_valid_move(const reversi_board_t *game,
         const int row, const int col, const int player) {
     int dirs, i;
     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 @@
 #define _REVERSI_GAME_H
 
 #include <stdbool.h>
+#include "plugin.h"
 
 #define WHITE 1       /* WHITE constant, it always plays first (as in chess) */
 #define BLACK 2       /* BLACK constant */
@@ -56,6 +57,8 @@ typedef struct _reversi_board_t {
      * stored in history[1] etc.
      */
     move_t history[BOARD_SIZE*BOARD_SIZE - INIT_STONES];
+
+    struct plugin_api *rb;
 } reversi_board_t;
 
 
@@ -70,6 +73,10 @@ int reversi_count_white_moves(const reversi_board_t *game);
 int reversi_count_black_moves(const reversi_board_t *game);
 int reversi_make_move(reversi_board_t *game, const int row,
         const int col, const int player);
+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);
 
 
 #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] = {
 
 static struct opt_items strategy_settings[] = {
     { "Human", NULL },
-    { "Silly robot", NULL },
-    { "Smart robot", NULL },
+    { "Naive robot", NULL },
+    { "Simple robot", NULL },
 };
 static const game_strategy_t * const strategy_values[] = {
-    &strategy_human, &strategy_novice, &strategy_expert };
+    &strategy_human, &strategy_naive, &strategy_simple };
 
 
 /* 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) {
     /* Avoid compiler warnings */
     (void)parameter;
 
+    game.rb = rb;
+    rb->srand(*rb->current_tick); /* Some AIs use rand() */
+
     reversi_gui_init();
     cursor_wrap_mode = WRAP_FLAT;
 
@@ -563,10 +566,39 @@ enum plugin_status plugin_start(struct plugin_api *api, void *parameter) {
     quit_plugin = false;
     draw_screen = true;
     while (!exit && !quit_plugin) {
+        const game_strategy_t *cur_strategy = NULL;
         if (draw_screen) {
             reversi_gui_display_board();
             draw_screen = false;
         }
+        switch(cur_player) {
+            case BLACK:
+                cur_strategy = black_strategy;
+                break;
+            case WHITE:
+                cur_strategy = white_strategy;
+                break;
+        }
+
+        if(cur_strategy->is_robot) {
+            /* TODO: Check move validity */
+            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)) {
+                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 */
+            }
+            continue;
+        }
+
         button = rb->button_get(true);
 
         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 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (c) 2007 Antoine Cellerier
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#include "reversi-strategy.h"
+
+/**
+ * Naive/Stupid strategy:
+ *   Random moves
+ */
+
+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 row = 0;
+    int col = 0;
+    while(true) {
+        if(reversi_is_valid_move(game, row, col, player)) {
+            r--;
+            if(r<0) {
+                return MAKE_MOVE(row,col,player);
+            }
+        }
+        col ++;
+        if(col==BOARD_SIZE) {
+            col = 0;
+            row ++;
+            if(row==BOARD_SIZE) {
+                row = 0;
+            }
+        }
+    }
+}
+
+const game_strategy_t strategy_naive = {
+    true,
+    naive_move_func
+};
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 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (c) 2007 Antoine Cellerier
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#include "reversi-strategy.h"
+
+/**
+ * Simple strategy:
+ *   A very simple strategy. Makes the highest scoring move.
+ *   From Algorithm by Claudio Clemens in hinversi, simpleClient.c
+ */
+
+static void reversi_copy_board(reversi_board_t *dst,
+        const reversi_board_t *src) {
+    int i;
+    dst->rb = src->rb;
+    dst->rb->memcpy(dst->history,src->history,
+                    (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t));
+    for(i=0;i<BOARD_SIZE;i++) {
+        dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE);
+    }
+}
+
+static int reversi_sim_move(const reversi_board_t *game, const int row,
+        const int col, const int player) {
+    /* Gruik */
+    reversi_board_t game_clone;
+    reversi_copy_board(&game_clone,game);
+    return reversi_make_move(&game_clone,row,col,player);
+}
+
+static move_t simple_move_func(const reversi_board_t *game, int player) {
+    int max = 0;
+    int count = 0;
+    int row, col;
+    int r;
+    for(row=0; row<BOARD_SIZE; row++) {
+        for(col=0; col<BOARD_SIZE; col++) {
+            int v = reversi_sim_move(game,row,col,player);
+            if(v>max) {
+                max = v;
+                count = 1;
+            }
+            else if(v==max) {
+                count ++;
+            }
+        }
+    }
+
+    /* chose one of the moves which scores highest */
+    r = game->rb->rand()%count;
+    row = 0;
+    col = 0;
+    while(true) {
+        if(reversi_sim_move(game, row, col, player)==max) {
+            r--;
+            if(r<0) {
+                return MAKE_MOVE(row,col,player);
+            }
+        }
+        col ++;
+        if(col==BOARD_SIZE) {
+            col = 0;
+            row ++;
+            if(row==BOARD_SIZE) {
+                row = 0;
+            }
+        }
+    }
+}
+
+const game_strategy_t strategy_simple = {
+    true,
+    simple_move_func
+};
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 @@
 #include "reversi-strategy.h"
 #include <stddef.h>
 
-
-/* Implementation of a rather weak player strategy */
-static move_t novice_move_func(const reversi_board_t *game, int color) {
-    /* TODO: Implement novice_move_func */
-    (void)game;
-    (void)color;
-    return MOVE_INVALID;
-}
-
-
-/* Implementation of a good player strategy */
-static move_t expert_move_func(const reversi_board_t *game, int color) {
-    /* TODO: Implement expert_move_func */
-    (void)game;
-    (void)color;
-    return MOVE_INVALID;
-}
-
-
-
 /* Strategy that requires interaction with the user */
 const game_strategy_t strategy_human = {
     false,
     NULL
 };
-
-/* Robot that plays not very well (novice) */
-const game_strategy_t strategy_novice = {
-    true,
-    novice_move_func
-};
-
-/* Robot that is hard to beat (expert) */
-const game_strategy_t strategy_expert = {
-    true,
-    expert_move_func
-};
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 {
 
 /* --- Possible playing strategies --- */
 extern const game_strategy_t strategy_human;
-extern const game_strategy_t strategy_novice;
-extern const game_strategy_t strategy_expert;
+extern const game_strategy_t strategy_naive;
+extern const game_strategy_t strategy_simple;
 
 #endif