Minmax算法选择一些深度的最差移动

2018-06-02 16:18:05

我必须为FloodWars（Android上的游戏）编写代码。到目前为止，我成功地编写了一个minmax和一个材料评估器，这很简单。

我的问题是，在一个特定的桌子上，奇数以上的深度超过9，这是最糟糕的举动。这里是表格：

@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##
@@**..**@@.#@@.##

颜色被替换为： '@', '#', '+', '.', '*' 。以下是指定深度的输出：

++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##
++**..**@@.#@@.##

在所有小于11的深度上，它会给出预期的输出：

****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##
****..**@@.#@@.##

以下是一些重要的代码片断：

int minmaxMin(int lvl, board *b)
{
    if(lvl == 0)
    {
        return evalM(b, g_me, g_he);
    }
    board cpB;
    moves M = getMoves(b, g_me, g_he);
    int score = 1000000;
    int i;

    for(i = 0; i < 3; i++)  
    {
        copyBoard(b, &cpB);
        memset(was, 0, MAX_L * MAX_C);
        floodfill_ch(&cpB, g_he.l, g_he.c, b->d[g_he.l][g_he.c], M.m[i]);

        score = min(score, minmaxMax(lvl - 1, &cpB)); 
    }

    return score;
}

int minmaxMax(int lvl, board *b)
{
    if(lvl == 0)
    {
        return evalM(b, g_me, g_he);
    }
    board cpB;
    moves M = getMoves(b, g_me, g_he);
    int score = -1000000;

    for(int i = 0; i < 3; i++)  
    {
        copyBoard(b, &cpB);
        memset(was, 0, MAX_L * MAX_C);
        floodfill_ch(&cpB, g_me.l, g_me.c, b->d[g_me.l][g_me.c], M.m[i]);

        score = max(score, minmaxMin(lvl - 1, &cpB)); 
    }

    return score;
}

lvl是深度，board是以[MAX_L] [MAX_C] - data和l（行数），c（列数）存储的电路板 - 板的实际大小。

函数floodfill_ch（...）在棋盘上将一组颜色变成另一种颜色，getMoves（...）获得合法移动（所有移动 - 拐角）并且evalM（...）获得董事会（由'我'主导的广场 - 广场由'他'主导）。

g_me和g_he是玩家的位置（行和列）。

我交换了evalM的观点， evalM是如何建议的，但没有发生任何事情。我在stdout上打印了根的孩子的结果，结果（分数）不同，但程序选择了最差的一个。
这里是交换参数的程序的调试屏幕：

scr: 0:
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##

scr: 0:
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##

scr: -26:
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##

这是没有参数交换的输出：

scr: 39:
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##
    ++**..**@@.#@@.##

scr: 26:
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##
    ..**..**@@.#@@.##

scr: 39:
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##
    ****..**@@.#@@.##

得分是在根的孩子上标记的分数。

这是整个代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define DEBUG

#ifndef DEBUG
  #define fin stdin
  #define fout stdout
#else
  FILE *fin, *fout, *tty;
#endif

#define MAX_L 50
#define MAX_C 50

typedef struct
{
  char d[MAX_L][MAX_C];
  int l, c;
}board;

typedef struct
{
  int l, c;
}player;

typedef struct
{
  char m[3];
}moves;

int max(int a, int b)
{
  return a > b ? a : b;
}

int min(int a, int b)
{
  return a < b ? a : b;
}


//utilities
void readBoard(FILE *fin, board *b, player* me, player* he);
void printBoard(FILE *fout, board *b);

//eval
int evalM(board* b, player me, player he);

//search
int minmaxMin(int lvl, board *b);
int minmaxMax(int lvl, board *b);
int negamax(int lvl, board *b, char col);


int alphabetaMin(int lvl, board *bo, int a, int b);
int alphabetaMax(int lvl, board *bo, int a, int b);

void floodfill_ch(board *b, int l, int c, char from, char to);


player g_me, g_he;
char was[MAX_L][MAX_C];

//moves
moves getMoves(board *b, player me, player he)
{
  char pM [] = {'@', '#', '+', '.', '*'};
  moves M;
  int i, j = 0;

  //printf("inside getMoves (%c, %c): ", b->d[me.l][me.c], b->d[he.l][he.c]);
  for(i = 0; i < 5; i++)
    if(pM[i] != b->d[me.l][me.c] && pM[i] != b->d[he.l][he.c])
      M.m[j++] = pM[i]/*, printf("'%c' ", pM[i])*/;
  //printf("n");
  return M;
}

void copyBoard(board *src, board *dst)
{
  dst -> l = src -> l;
  dst -> c = src -> c;
  memcpy(dst -> d, src -> d, MAX_C * MAX_L);
}

int main()
{
  #ifdef DEBUG
  fin = fopen("in", "r");
  fout = fopen("out", "w");
  tty = fopen("debugyline", "w");
  #endif
  board currentState;
  board cpB;
  board winner;
  player me, he;
  int score;

  readBoard(fin, &currentState, &me, &he);
  g_me = me, g_he = he;
  printf("reported: (%d %d) (%d %d)n", me.l, me.c, he.l, he.c);
  printf("reported score: %dn", evalM(&currentState, me, he));
  printBoard(stdout, &currentState);

  moves M = getMoves(&currentState, g_me, g_he);
  printf("possible moves: '%c' '%c' '%c';n", M.m[0], M.m[1], M.m[2]);
  score = -1000000;
  for(int i = 0; i < 3; i++)
  {
    copyBoard(&currentState, &cpB);
    memset(was, 0, MAX_L * MAX_C);
    floodfill_ch(&cpB, g_me.l, g_me.c, cpB.d[g_me.l][g_me.c], M.m[i]);

    int x = minmaxMin(10, &cpB);
    #ifdef DEBUG
    fprintf(stdout, "    scr: %d:n", x, evalM(&cpB, g_he, g_me));
    printBoard(stdout, &cpB);
    fprintf(stdout, "nnnnn");
    #endif

    if(x > score)
    {
      score = x;
      copyBoard(&cpB, &winner);
    }
  }

  printf("nn");
  printf("minimax scored at: %dn", score);
  printBoard(stdout, &winner);


  #ifdef DEBUG
  fclose(fin);
  fclose(fout);
  fclose(tty);
  #endif
  return 0;
}
//search

//--
void floodfill_ch(board *b, int l, int c, char from, char to)
{
  if(l >= 0 && l < b->l && c >= 0 && c < b->c && !was[l][c] && b->d[l][c] == from)
  {
    b->d[l][c] = to;
    was[l][c] = 1;
    char ldir[] = {0,  0, -1, 1},
       cdir[] = {1, -1,  0, 0};

    for(int i = 0; i < 4; i++)
      floodfill_ch(b, l + ldir[i], c + cdir[i], from, to);
  }
}
//--

//minmax (mm123)
int minmaxMin(int lvl, board *b)
{
  if(lvl == 0)
  {
    #ifdef DEBUG
    fprintf(tty, "scr = %d: n", evalM(b, g_he, g_me));
    //printBoard(tty, b);
    //fprintf(tty, "nnnnn");
    #endif
    return evalM(b, g_he, g_me);
  }
  board cpB;
  moves M = getMoves(b, g_me, g_he);
  int score = 1000000;
  int i;

  for(i = 0; i < 3; i++)
  {
    copyBoard(b, &cpB);
    memset(was, 0, MAX_L * MAX_C);
    floodfill_ch(&cpB, g_he.l, g_he.c, b->d[g_he.l][g_he.c], M.m[i]);

    score = min(score, minmaxMax(lvl - 1, &cpB));
  }

  return score;
}

int minmaxMax(int lvl, board *b)
{
  if(lvl == 0)
  {
    #ifdef DEBUG
    fprintf(tty, "scr = %d: n", evalM(b, g_he, g_me));
    printBoard(tty, b);
    fprintf(tty, "nnnnn");
    #endif
    return evalM(b, g_me, g_he);
  }
  board cpB;
  moves M = getMoves(b, g_me, g_he);
  int score = -1000000;

  for(int i = 0; i < 3; i++)
  {
    copyBoard(b, &cpB);
    memset(was, 0, MAX_L * MAX_C);
    floodfill_ch(&cpB, g_me.l, g_me.c, b->d[g_me.l][g_me.c], M.m[i]);
    /*
    #ifdef DEBUG
    fprintf(tty, "%d:n", lvl - 1);
    printBoard(tty, &cpB);
    fprintf(tty, "nnnnn");
    #endif
    */
    score = max(score, minmaxMin(lvl - 1, &cpB));
  }

  return score;
}



// eval (ev456)
int sum;

void floodfill(board *b, int l, int c, char src)
{
  if(l >= 0 && l < b->l && c >= 0 && c < b->c && !was[l][c] && b->d[l][c] == src)
  {
    sum ++;
    was[l][c] = 1;
    char ldir[] = {0,  0, -1, 1},
       cdir[] = {1, -1,  0, 0};

    for(int i = 0; i < 4; i++)
      floodfill(b, l + ldir[i], c + cdir[i], src);
  }
}

int evalM(board* b, player me, player he)
{
  int s_me, s_he;

  sum = 0;
  memset(was, 0, MAX_L * MAX_C);
  floodfill(b, me.l, me.c, b->d[me.l][me.c]);
  s_me = sum;

  sum = 0;
  memset(was, 0, MAX_L * MAX_C);
  floodfill(b, he.l, he.c, b->d[he.l][he.c]);
  s_he = sum;

  return s_me - s_he;
}

// I/O => board (iob1234)
void readBoard(FILE *fin, board *b, player* me, player* he)
{
    int l, c;
    char ch, t;
  player pJ, pS;
    t = fgetc(fin);
    fscanf(fin," ");

    ch = fgetc(fin);
    l = 0;
    while(ch != EOF && ch != 'n')
    {
        c = 0;
        while(ch != 'n' && ch != ' ' && ch != EOF)
        {
            b->d[l][c] = ch;
            ch = fgetc(fin);
            c++;
        }
        ch = fgetc(fin);
        l++;
    }

  b->l = l;
  b->c = c;

  pJ.l = l-1, pJ.c = 0;
  pS.l = 0, pS.c = c-1;

  if(t == 'J')
    *me = pJ, *he = pS;
  else if(t == 'S')
    *me = pS, *he = pJ;
  #ifdef DEBUG
  else printf("debug: (error) type of player broken; exiting...n"), exit(-1);
  #endif
}

void printBoard(FILE *fout, board *b)
{
  int l, c;
  for(l = 0; l < b->l; l++)
  {
    fprintf(fout, "        ");
    for(c = 0; c < b->c; c++)
      fprintf(fout, "%c", b->d[l][c]);
    fprintf(fout, "n");
  }
}

minmax算法的调用是minmaxMin(10, &cpB);

链接地址: http://www.djcxy.com/p/9639.html

上一篇: Minmax algorithm chooses the worst move for some depths

下一篇: Implementing and using MinMax with four in row (connect4) game