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     dst->rb = src->rb;
  35     dst->rb->memcpy(dst->history,src->history,
  36                     (BOARD_SIZE*BOARD_SIZE - INIT_STONES)*sizeof(move_t));
  37     for(i=0;i<BOARD_SIZE;i++) {
  38         dst->rb->memcpy(dst->board[i],src->board[i],BOARD_SIZE*sizeof(int));
  39     }
  40 }
  41
  42 static int reversi_sim_move(const reversi_board_t *game, const int row,
  43         const int col, const int player) {
  44     reversi_board_t game_clone;
  45     reversi_copy_board(&game_clone,game);
  46     return reversi_make_move(&game_clone,row,col,player);
  47 }
  48
  49 static int reversi_get_max_moves(const reversi_board_t *game, int player) {
  50     int max = -BOARD_SIZE*BOARD_SIZE;
  51     int row, col;
  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         }
  58     }
  59     return max;
  60 }
  61
  62 static int reversi_sim_move2(const reversi_board_t *game, const int row,
  63         const int col, const int player) {
  64     /* Takes the other player's next best move into account */
  65     int score;
  66     reversi_board_t game_clone;
  67     reversi_copy_board(&game_clone,game);
  68     score = reversi_make_move(&game_clone,row,col,player);
  69     return score - reversi_get_max_moves(&game_clone,
  70                                          reversi_flipped_color(player));
  71 }
  72
  73
  74 static move_t simple_move_func(const reversi_board_t *game, int player) {
  75     int max = -BOARD_SIZE*BOARD_SIZE;
  76     int count = 0;
  77     int row, col;
  78     int r;
  79     for(row=0; row<BOARD_SIZE; row++) {
  80         for(col=0; col<BOARD_SIZE; col++) {
  81             int v = reversi_sim_move2(game,row,col,player);
  82             if(v>max) {
  83                 max = v;
  84                 count = 1;
  85             }
  86             else if(v==max) {
  87                 count ++;
  88             }
  89         }
  90     }
  91
  92     if(!count) return MOVE_INVALID;
  93
  94     /* chose one of the moves which scores highest */
  95     r = game->rb->rand()%count;
  96     row = 0;
  97     col = 0;
  98     while(true) {
  99         if(reversi_sim_move2(game, row, col, player)==max) {
 100             r--;
 101             if(r<0) {
 102                 return MAKE_MOVE(row,col,player);
 103             }
 104         }
 105         col ++;
 106         if(col==BOARD_SIZE) {
 107             col = 0;
 108             row ++;
 109             if(row==BOARD_SIZE) {
 110                 row = 0;
 111             }
 112         }
 113     }
 114 }
 115
 116 const game_strategy_t strategy_simple = {
 117     true,
 118     NULL,
 119     simple_move_func
 120 };