MinimaxEnemy.cpp

   1 #include "MinimaxEnemy.h"
   2 #include "Board.h"
   3
   4 #include <cstdio>
   5 #include <climits>
   6 //#include <iostream>
   7 //using namespace std;
   8 typedef MinimaxEnemy::HeuType HeuType;
   9
  10 HeuType maxhNull = -1
  11                                 , maxhCentro = -1
  12                                 , maxhConcentration = -1
  13                                 , maxhCentralisation = -1
  14                                 , maxhMasscenter = -1
  15                                 , maxhQuads = -1
  16                                 , maxhConnectedness = -1
  17                                 , maxhUniformity = -1
  18                                 ;
  19 typedef struct sHeu {
  20         int i;
  21         HeuType h;
  22 } Heu;
  23
  24 static Board::MoveListOt g_MoveList[10];
  25 //static Board::Set _think_boards[2] = {Board::Set(board_compare), Board::Set(board_compare)};
  26 //#include <map>
  27 //static std::map<Board::Comp, int> _board_value[2];
  28 static Heu g_Heu[10][8 * 12];
  29 static Board g_Boards[10][8 * 12];
  30
  31 int lessHeu(const void *l, const void *r) {
  32         return ((Heu *)l)->h - ((Heu *)r)->h;
  33 }
  34
  35 int moreHeu(const void *l, const void *r) {
  36         return ((Heu *)r)->h - ((Heu *)l)->h;
  37 }
  38
  39 void MinimaxEnemy::move(Board *board, int& fromX, int& fromY, int& toX, int& toY)
  40 {
  41         //_game_boards.insert(board->to_comp());
  42         //_think_boards[0].clear();
  43         //_think_boards[1].clear();
  44         //_board_value[0].clear();
  45         //_board_value[1].clear();
  46
  47         /*
  48         for(Board::Set::iterator i = _game_boards.begin(); i != _game_boards.end(); ++i) {
  49                 cout << i->first << ' ' << i->second << endl;
  50         }
  51         cout << endl;//*/
  52
  53   Board::MoveListOt moveList;
  54         board->all_moves(_player, moveList);
  55
  56         alphabeta(*board, _minimax_depth, -HeuTypeMax, HeuTypeMax, _player);
  57         //_game_boards.insert(board->move_result(_player, moveList[_choice]).to_comp());
  58
  59         //printf("_choice: %i\n", _choice); fflush(stdout);
  60         /*
  61   reps(i, moveList) {
  62                 printf("%i: (%i, %i) -> (%i, %i)\n", i, INDEX_X(moveList[i].first), INDEX_Y(moveList[i].first)
  63                                                            , INDEX_X(moveList[i].second), INDEX_Y(moveList[i].second));
  64                 fflush(stdout);
  65   } //*/
  66
  67         fromX = INDEX_X(INDEX_FROM(moveList[_choice]));
  68         fromY = INDEX_Y(INDEX_FROM(moveList[_choice]));
  69         toX = INDEX_X(INDEX_TO(moveList[_choice]));
  70         toY = INDEX_Y(INDEX_TO(moveList[_choice]));
  71 }
  72
  73 #define SQU(x) ((x) * (x))
  74 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  75 #define MAX_ALPHABETA HeuTypeMax / 10000
  76
  77 // negamax com poda alphabeta
  78 HeuType MinimaxEnemy::alphabeta(Board board, int depth, HeuType alpha, HeuType beta, int player)
  79 {
  80         //printf("alphabeta(%i, %i, %i, %i)\n", depth, alpha, beta, player);
  81
  82         if(board.is_end()) {
  83                 //printf("board is end %i %i\n", board.win(0), board.win(1));
  84                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
  85                 mul *= 2 * _player - 1;
  86                 if(board.win(_player)) return mul * MAX_ALPHABETA * (1 - 2 * board.win(!_player)) * (depth + 1); /* considerando vitoria simultanea */
  87                 return -mul * MAX_ALPHABETA * (depth + 1); /* dando prioridade para o caminho mais curto */
  88         }
  89         if(depth == 0) {
  90                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
  91                 mul *= 2 * _player - 1;
  92                 return mul * heuristica(board, _player);
  93         }
  94
  95         /*
  96         if(_game_boards.count(board.to_comp())) { // empate
  97                 return 0; // nao funciona, acaba sendo sempre a melhor escolha para ambos
  98         }*/
  99
 100         //Board::MoveOt *moveList = g_MoveList[depth];
 101         int size = board.all_moves(player, g_MoveList[depth]);
 102
 103 /* sort */
 104         rep(i, size) {
 105                 g_Heu[depth][i].h = heuristica(g_Boards[depth][i] = board.move_result(player, g_MoveList[depth][i]), _player);
 106                 g_Heu[depth][i].i = i;
 107         }
 108
 109         if(player != _player) {
 110                 qsort(&g_Heu[depth], size, sizeof(Heu), lessHeu);
 111         } else {
 112                 qsort(&g_Heu[depth], size, sizeof(Heu), moreHeu);
 113         }
 114         //Heu *perm = g_Heu[depth];
 115         //Board *boards = g_Boards[depth];
 116
 117         /*
 118         if(depth == _minimax_depth) {
 119                 rep(i, size)
 120                         printf("%i(%i) ", g_Heu[depth][i].i, g_Heu[depth][i].h);
 121                 printf("\n");
 122         }//*/
 123 /* end sort */
 124
 125         rep(i, size) {
 126                 /*
 127                 if(i / (float) size > 0.75) { // ignora os piores
 128                         break;
 129                 }//*/
 130                 //Board b = board.move_result(player, moveList[perm[i].i]);
 131                 //if(_game_boards.count(b.to_comp())) { /* empate */
 132                         //continue; // ignora posições que já foram atingidas antes
 133                 //}
 134                 //HeuType rec;
 135                 //if(_think_boards[!player].count(b.to_comp())) { /* transposição */
 136                 //      rec = -_board_value[!player][b.to_comp()];
 137                 //} else {
 138                 HeuType rec = -alphabeta(g_Boards[depth][g_Heu[depth][i].i], depth - 1, -beta, -alpha, !player);
 139                 //}
 140                 if(alpha < rec) {
 141                         alpha = rec;
 142                         if(depth == _minimax_depth) {
 143                                 _choice = g_Heu[depth][i].i;
 144                         }
 145                 }
 146                 if(alpha >= beta) {
 147                         //_board_value[player][board.to_comp()] = alpha; _think_boards[player].insert(board.to_comp());
 148                         return alpha;
 149                 }
 150         }
 151         //_board_value[player][board.to_comp()] = alpha; _think_boards[player].insert(board.to_comp());
 152         return alpha;
 153 }
 154
 155 #define FINDMAX(x) \
 156         if(x > MAX(1, max##x)) { \
 157                 max##x = x; \
 158                 printf(#x ": %f\n", x); \
 159         }
 160
 161 HeuType MinimaxEnemy::heuristica(Board board, bool player)
 162 {
 163         HeuType hNull = rand() / (double) RAND_MAX
 164                                         , hCentro = centro(board, player)
 165                                         , hConcentration = concentration(board, player)
 166                                         , hCentralisation = centralisation(board, player)
 167                                         , hMasscenter = masscenter(board, player)
 168                                         , hQuads = quads(board, player)
 169                                         , hConnectedness = connectedness(board, player)
 170                                         , hUniformity = uniformity(board, player)
 171                                         ;
 172         //FINDMAX(hCentro);
 173         //FINDMAX(hCentro);
 174         //FINDMAX(hConcentration);
 175         //FINDMAX(hCentralisation);
 176         //FINDMAX(hMasscenter);
 177         //FINDMAX(hQuads);
 178         //FINDMAX(hConnectedness);
 179         //FINDMAX(hUniformity);
 180         return hNull * _heu[0]
 181                 + hCentro * _heu[1]
 182                 + hConcentration * _heu[2]
 183                 + hCentralisation * _heu[3]
 184                 + hMasscenter * _heu[4]
 185                 + hQuads * _heu[5]
 186                 + hConnectedness * _heu[6]
 187                 + hUniformity * _heu[7]
 188                 //+ centro(board, player)
 189                 //+ concentration(board, player)
 190                 //+ centralisation(board, player)
 191                 //+ masscenter(board, player)
 192                 //+ quads(board, player)
 193                 //+ connectedness(board, player)
 194                 //+ uniformity(board, player)
 195                 ;
 196 }
 197
 198 // centro: diferença entra as médias das distâncias para o centro
 199 HeuType MinimaxEnemy::centro(Board board, bool player)
 200 {
 201         HeuType res = 0;
 202         rep(i, 8)
 203                 rep(j, 8)
 204                         if(board.get(player, i, j))
 205                                 res += SQU(i - 3.5) + SQU(j - 3.5); // distância para o centro
 206         res /= (double) board.t[player].count();
 207         HeuType resb = 0;
 208         rep(i, 8)
 209                 rep(j, 8)
 210                         if(board.get(!player, i, j))
 211                                 resb += SQU(i - 3.5) + SQU(j - 3.5); // distância para o centro
 212         resb /= (double) board.t[!player].count();
 213         //return MAX_ALPHABETA - res;
 214         return (resb - res) / 14.8;
 215 }
 216
 217 HeuType MinimaxEnemy::concentration(Board board, bool player)
 218 {
 219         static HeuType minsum[] = {0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22};
 220         HeuType cmx = 0, cmy = 0;
 221         int n = board.t[player].count();
 222         rep(i, 8)
 223                 rep(j, 8)
 224                         if(board.get(player, i, j)) {
 225                                 cmx += i;
 226                                 cmy += j;
 227                         }
 228         cmx /= (double) n;
 229         cmy /= (double) n;
 230
 231         HeuType sum = -minsum[n];
 232         rep(i, 8)
 233                 rep(j, 8)
 234                         if(board.get(player, i, j)) {
 235                                 HeuType dx = abs(cmx - i);
 236                                 HeuType dy = abs(cmy - j);
 237                                 sum += MAX(dx, dy);
 238                         }
 239         HeuType res = sum;
 240
 241         cmx = 0, cmy = 0;
 242         n = board.t[!player].count();
 243         rep(i, 8)
 244                 rep(j, 8)
 245                         if(board.get(!player, i, j)) {
 246                                 cmx += i;
 247                                 cmy += j;
 248                         }
 249         cmx /= (double) n;
 250         cmy /= (double) n;
 251
 252         sum = -minsum[n];
 253         rep(i, 8)
 254                 rep(j, 8)
 255                         if(board.get(!player, i, j)) {
 256                                 HeuType dx = abs(cmx - i);
 257                                 HeuType dy = abs(cmy - j);
 258                                 sum += MAX(dx, dy);
 259                         }
 260         HeuType resb = sum;
 261         return (resb - res) / 24;
 262 }
 263
 264 HeuType MinimaxEnemy::centralisation(Board board, bool player)
 265 {
 266         static
 267         int squval[8][8] = {{-80, -25, -20, -20, -20, -20, -25, -80},
 268                                         {-25,  10,  10,  10,  10,  10,  10, -25},
 269                                                                                         {-20,  10,  25,  25,  25,  25,  10, -20},
 270                                                                                         {-20,  10,  25,  50,  50,  25,  10, -20},
 271                                                                                         {-20,  10,  25,  50,  50,  25,  10, -20},
 272                                                                                         {-20,  10,  25,  25,  25,  25,  10, -20},
 273                                         {-25,  10,  10,  10,  10,  10,  10, -25},
 274                                                                                         {-80, -25, -20, -20, -20, -20, -25, -80}};
 275         HeuType res = 0.0;
 276         rep(i, 8)
 277                 rep(j, 8)
 278                         if(board.get(player, i, j)) {
 279                                 res += squval[i][j];
 280                         }
 281         res /= board.t[player].count();
 282
 283         HeuType resb = 0.0;
 284         rep(i, 8)
 285                 rep(j, 8)
 286                         if(board.get(!player, i, j)) {
 287                                 resb += squval[i][j];
 288                         }
 289         resb /= board.t[!player].count();
 290
 291         return (res - resb) / 63.1;
 292 }
 293
 294 HeuType MinimaxEnemy::masscenter(Board board, bool player)
 295 {
 296         HeuType cmx = 0, cmy = 0;
 297         int n = board.t[player].count();
 298         rep(i, 8)
 299                 rep(j, 8)
 300                         if(board.get(player, i, j)) {
 301                                 cmx += i;
 302                                 cmy += j;
 303                         }
 304         cmx /= (double) n;
 305         cmy /= (double) n;
 306         HeuType res = SQU(cmx) + SQU(cmy);
 307
 308         cmx = 0, cmy = 0;
 309         n = board.t[!player].count();
 310         rep(i, 8)
 311                 rep(j, 8)
 312                         if(board.get(!player, i, j)) {
 313                                 cmx += i;
 314                                 cmy += j;
 315                         }
 316         cmx /= (double) n;
 317         cmy /= (double) n;
 318         HeuType resb = SQU(cmx) + SQU(cmy);
 319
 320         return (res - resb) / 52.5;
 321 }
 322
 323 HeuType MinimaxEnemy::quads(Board board, bool player)
 324 {
 325         HeuType cmx = 0, cmy = 0;
 326         int n = board.t[player].count();
 327         rep(i, 8)
 328                 rep(j, 8)
 329                         if(board.get(player, i, j)) {
 330                                 cmx += i;
 331                                 cmy += j;
 332                         }
 333         cmx /= (double) n;
 334         cmy /= (double) n;
 335         HeuType res = 0;
 336         repbe(i, MAX(0, cmx - 2), MIN(6, cmx + 3)) {
 337                 repbe(j, MAX(0, cmy - 2), MIN(6, cmy + 3)) {
 338                         if(board.get(player, i, j) +
 339                                  board.get(player, i + 1, j) +
 340                                  board.get(player, i, j + 1) +
 341                                  board.get(player, i + 1, j + 1) >= 3) {
 342                                 res++;
 343                         }
 344                 }
 345         }
 346
 347         cmx = 0, cmy = 0;
 348         n = board.t[!player].count();
 349         rep(i, 8)
 350                 rep(j, 8)
 351                         if(board.get(!player, i, j)) {
 352                                 cmx += i;
 353                                 cmy += j;
 354                         }
 355         cmx /= (double) n;
 356         cmy /= (double) n;
 357         HeuType resb = 0;
 358         repbe(i, MAX(0, cmx - 2), MIN(6, cmx + 3)) {
 359                 repbe(j, MAX(0, cmy - 2), MIN(6, cmy + 3)) {
 360                         if(board.get(!player, i, j) +
 361                                  board.get(!player, i + 1, j) +
 362                                  board.get(!player, i, j + 1) +
 363                                  board.get(!player, i + 1, j + 1) >= 3) {
 364                                 resb++;
 365                         }
 366                 }
 367         }
 368
 369         return (res - resb) / 7.0;
 370 }
 371
 372 HeuType MinimaxEnemy::connectedness(Board board, bool player)
 373 {
 374         static int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1},
 375                                                  dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 376
 377         int res = 0;
 378         rep(i, 8)
 379                 rep(j, 8)
 380                         if(board.get(player, i, j)) {
 381                                 rep(d, 8) {
 382                                         int x = i + dx[d],
 383                                                         y = j + dy[d];
 384                                         if(x < 0 || x > 7 ||
 385                                                  y < 0 || y > 7) {
 386                                                 continue;
 387                                         }
 388                                         if(board.get(player, x, y)) {
 389                                                 res++;
 390                                         }
 391                                 }
 392                         }
 393         res /= (double) board.t[player].count();
 394
 395         int resb = 0;
 396         rep(i, 8)
 397                 rep(j, 8)
 398                         if(board.get(!player, i, j)) {
 399                                 rep(d, 8) {
 400                                         int x = i + dx[d],
 401                                                         y = j + dy[d];
 402                                         if(x < 0 || x > 7 ||
 403                                                  y < 0 || y > 7) {
 404                                                 continue;
 405                                         }
 406                                         if(board.get(!player, x, y)) {
 407                                                 resb++;
 408                                         }
 409                                 }
 410                         }
 411         resb /= (double) board.t[!player].count();
 412
 413         return (res - resb) / 4.0;
 414 }
 415
 416 HeuType MinimaxEnemy::uniformity(Board board, bool player)
 417 {
 418         int res;
 419         int minx, miny, maxx, maxy;
 420         minx = miny = 8;
 421         maxx = maxy = -1;
 422         rep(i, 8)
 423                 rep(j, 8)
 424                         if(board.get(player, i, j)) {
 425                                 if(i < minx) minx = i;
 426                                 if(i > maxx) maxx = i;
 427                                 if(j < miny) miny = j;
 428                                 if(j > maxy) maxy = j;
 429                         }
 430         res = (maxx - minx) * (maxy - miny);
 431         int resb;
 432         minx = miny = 8;
 433         maxx = maxy = -1;
 434         rep(i, 8)
 435                 rep(j, 8)
 436                         if(board.get(!player, i, j)) {
 437                                 if(i < minx) minx = i;
 438                                 if(i > maxx) maxx = i;
 439                                 if(j < miny) miny = j;
 440                                 if(j > maxy) maxy = j;
 441                         }
 442         resb = (maxx - minx) * (maxy - miny);
 443         return (resb - res) / 48.84;
 444 }
 445
 446 void MinimaxEnemy::set_weights(HeuType heu[NUM_HEU])
 447 {
 448         rep(i, NUM_HEU)
 449                 _heu[i] = heu[i];
 450 }
 451