apps/plugins/reversi/reversi-strategy-simple.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (c) 2007 Antoine Cellerier
  11  *
  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.
  16  *
  17  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  18  * KIND, either express or implied.
  19  *
  20  ****************************************************************************/
  21
  22 #include "reversi-strategy.h"
  23
  24 /**
  25  * Simple strategy:
  26  *   A very simple strategy. Makes the highest scoring move taking the other
  27  *   player's next best move into account.
  28  *   From Algorithm by Claudio Clemens in hinversi, simpleClient.c
  29  */
  30
  31 static void reversi_copy_board(reversi_board_t *dst,
  32         const reversi_board_t *src) {
  33     int i;
  34     rb->memcpy(dst->history,src->history,
  35                     (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t));
  36     for(i=0;i<BOARD_SIZE;i++) {
  37         rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE*sizeof(int));
  38     }
  39 }
  40
  41 static int reversi_sim_move(const reversi_board_t *game, const int row,
  42         const int col, const int player) {
  43     reversi_board_t game_clone;
  44     reversi_copy_board(&game_clone,game);
  45     return reversi_make_move(&game_clone,row,col,player);
  46 }
  47
  48 static int reversi_get_max_moves(const reversi_board_t *game, int player) {
  49     int max = -BOARD_SIZE*BOARD_SIZE;
  50     int row, col;
  51     for(row=0; row<BOARD_SIZE; row++) {
  52         for(col=0; col<BOARD_SIZE; col++) {
  53             int v = reversi_sim_move(game,row,col,player);
  54             if(v>max)
  55                 max = v;
  56         }
  57     }
  58     return max;
  59 }
  60
  61 static int reversi_sim_move2(const reversi_board_t *game, const int row,
  62         const int col, const int player) {
  63     /* Takes the other player's next best move into account */
  64     int score;
  65     reversi_board_t game_clone;
  66     reversi_copy_board(&game_clone,game);
  67     score = reversi_make_move(&game_clone,row,col,player);
  68     return score - reversi_get_max_moves(&game_clone,
  69                                          reversi_flipped_color(player));
  70 }
  71
  72
  73 static move_t simple_move_func(const reversi_board_t *game, int player) {
  74     int max = -BOARD_SIZE*BOARD_SIZE;
  75     int count = 0;
  76     int row, col;
  77     int r;
  78     for(row=0; row<BOARD_SIZE; row++) {
  79         for(col=0; col<BOARD_SIZE; col++) {
  80             int v = reversi_sim_move2(game,row,col,player);
  81             if(v>max) {
  82                 max = v;
  83                 count = 1;
  84             }
  85             else if(v==max) {
  86                 count ++;
  87             }
  88         }
  89     }
  90
  91     if(!count) return MOVE_INVALID;
  92
  93     /* chose one of the moves which scores highest */
  94     r = rb->rand()%count;
  95     row = 0;
  96     col = 0;
  97     while(true) {
  98         if(reversi_sim_move2(game, row, col, player)==max) {
  99             r--;
 100             if(r<0) {
 101                 return MAKE_MOVE(row,col,player);
 102             }
 103         }
 104         col ++;
 105         if(col==BOARD_SIZE) {
 106             col = 0;
 107             row ++;
 108             if(row==BOARD_SIZE) {
 109                 row = 0;
 110             }
 111         }
 112     }
 113 }
 114
 115 const game_strategy_t strategy_simple = {
 116     true,
 117     NULL,
 118     simple_move_func
 119 };