migrando/MinimaxEnemy.cpp

   1 #include "MinimaxEnemy.h"
   2 #include "Board.h"
   3
   4 #include <cstdio>
   5 #include <climits>
   6
   7 void MinimaxEnemy::move(Board *board, int& fromX, int& fromY, int& toX, int& toY)
   8 {
   9   Board::MoveList moveList;
  10         board->all_moves(_player, moveList);
  11
  12         int choice;
  13         alphabeta(*board, _minimax_depth, -INT_MAX, INT_MAX, _player, &choice);
  14
  15         /*
  16         printf("choice: %i\n", choice);
  17   reps(i, moveList) {
  18                 printf("%i: (%i, %i) -> (%i, %i)\n", i, INDEX_X(moveList[i].first), INDEX_Y(moveList[i].first)
  19                                                            , INDEX_X(moveList[i].second), INDEX_Y(moveList[i].second));
  20                 fflush(stdout);
  21   } //*/
  22
  23         fromX = INDEX_X(moveList[choice].first);
  24         fromY = INDEX_Y(moveList[choice].first);
  25         toX = INDEX_X(moveList[choice].second);
  26         toY = INDEX_Y(moveList[choice].second);
  27 }
  28
  29 #define SQU(x) ((x) * (x))
  30 #define MAX_ALPHABETA 2 * SQU(0 - 3.5) * 12
  31
  32 // negamax com poda alphabeta
  33 int MinimaxEnemy::alphabeta(Board board, int depth, int alpha, int beta, int player, int *index)
  34 {
  35         //printf("alphabeta(%i, %i, %i, %i)\n", depth, alpha, beta, player);
  36
  37         int fakeIndex;
  38         if(board.is_end()) {
  39                 //printf("board is end %i %i\n", board.win(0), board.win(1));
  40                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
  41                 mul *= 2 * _player - 1;
  42                 if(board.win(_player)) return mul * MAX_ALPHABETA;
  43                 return -mul * MAX_ALPHABETA;
  44         }
  45         if(depth == 0) {
  46                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
  47                 mul *= 2 * _player - 1;
  48                 return mul * heuristica(board, _player);
  49         }
  50
  51         Board::MoveList moveList;
  52         moveList.reserve(board.count() * 2); // reserva o dobro do número de peças vivas
  53         board.all_moves(player, moveList);
  54
  55         int size = (int) moveList.size();
  56         rep(i, size) {
  57                 int rec = -alphabeta(board.move_result(player, moveList[i]), depth - 1, -beta, -alpha, !player, &fakeIndex);
  58                 if(alpha < rec) {
  59                         alpha = rec;
  60                         *index = i;
  61                 }
  62                 if(alpha >= beta)
  63                         return alpha;
  64         }
  65         return alpha;
  66 }
  67
  68 // heurística: minimizar a soma das distâncias das nossas peças para o centro do tabuleiro
  69 int MinimaxEnemy::heuristica(Board board, bool player)
  70 {
  71         int res = 0;
  72         rep(i, 8)
  73                 rep(j, 8)
  74                         if(board.get(player, i, j))
  75                                 res += SQU(i - 3.5) + SQU(j - 3.5); // distância para o centro
  76         return MAX_ALPHABETA - res;
  77 }