オセロをMinMax法を導入する方法（JavaScript編）

JavaScriptでオセロを作っていて、そのオセロのCOMにMinMax法を導入したので方法を紹介。

ただし、コードは結構汚いです。

MinMax法とは？

MinMax法とは、オセロや将棋等のゲームで、コンピュータがどのように考えて手を指すかと言う思考方法（アルゴリズム）の１つ。

画像：リバーシプログラムの作り方

上記の画像から分かるように、オセロには様々な手順の可能性が考えられるが、それぞれの局面に評価を付けていき、どの手順が最善かを調べるのがMinMax法となる。

具体的には、「自分（COM）の手を考えるときは最も評価が高い手を選び、相手の手を考えるときは最も評価が低い、つまりCOM側が指されて一番イヤな手を選ぶ」と言うのがMinMax法だと言える。

実際に書いたコード

実際に書いたコードは、以下の通り。

function minMaxCom(comColor, comBoard, putPos, thinkDepth, isPass, isComTurn, isRootFunc) {
  let comCurrentBoard = [];
      comCurrentBoard = comBoard.slice().map( function(row){ return row.slice(); });
    if(putPos) {
      putStone(-comColor, comCurrentBoard, putPos[0], putPos[1]);
    }

  let value,
      max      = -64,
      min      = 64,
      can_move = false,
      select_pos = [];

  if( thinkDepth === 0 ) {
    return countComStone(comCurrentBoard);
  }

  for(let x = 1; x <= BOARD_WIDTH; x++) {
    for(let y = 1; y <= BOARD_WIDTH; y++) {
      if( isValidPutStone(comColor, comCurrentBoard, x, y) ) {
        can_move = true;
        value = minMaxCom(-comColor, comCurrentBoard, [x, y], thinkDepth - 1, false, !isComTurn, false);
        if(isComTurn) {

          if( value > max ) {
            max = value;
            select_pos = [x, y];
          }
        } else {
          if( value < min ) {
            min = value;
            select_pos = [x, y];
          }
        }
      }
    }
  }
  if(!can_move) {
    if(isPass) {
      return countComStone(comCurrentBoard);
    } else {
      if(isComTurn) {
        max = minMaxCom(-comColor, comCurrentBoard, false, thinkDepth - 1, true, !isComTurn, false);
      }else {
        min = minMaxCom(-comColor, comCurrentBoard, false, thinkDepth - 1, true, !isComTurn, false);
      }
    }
  }

  if(isRootFunc) {
    return select_pos;
  }

  if(isComTurn) {
    return max;
  } else {
    return min;
  }
}

凄く汚いコードだが、要は「再帰関数を使ってどんどん手を深く読んでいき、最終的に石の多さを評価として返している」ようにしている。

ちなみに、リバーシプログラムの作り方のページでは、以下のコードがC言語で書かれていた。

static int Com_EndSearch(Com *self, int in_depth, int in_color, int in_opponent, int in_pass, int *out_move)
{
    int x, y;
    int value, max = -MAX_VALUE;
    int can_move = 0;
    int move;

    if (in_depth == 0) {
        self->Node++;
        return Board_CountDisks(self->Board, in_color) - Board_CountDisks(self->Board, in_opponent);
    }
    *out_move = NOMOVE;
    for (x = 0; x < BOARD_SIZE; x++) {
        for (y = 0; y < BOARD_SIZE; y++) {
            if (Board_Flip(self->Board, in_color, Board_Pos(x, y))) {
                if (!can_move) {
                    *out_move = Board_Pos(x, y);
                    can_move = 1;
                }
                value = -Com_MidSearch(self, in_depth - 1, in_opponent, in_color, 0, &move);
                Board_Unflip(self->Board);
                if (value > max) {
                    max = value;
                    *out_move = Board_Pos(x, y);
                }
            }
        }
    }
    if (!can_move) {
        if (in_pass) {
            *out_move = NOMOVE;
            self->Node++;
            max = Board_CountDisks(self->Board, in_color) - Board_CountDisks(self->Board, in_opponent);
        } else {
            *out_move = PASS;
            max = -Com_MidSearch(self, in_depth, in_opponent, in_color, 1, &move);
        }
    }
    return max;
}

上記のコードは厳密にはNegaMax法と言うMinMax法の兄弟のような方法で書いているが、JavaScriptで書く場合もこれぐらいシンプルに持っていきたい。