オセロを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;
    }
}

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

ちなみに、 リバーシプログラムの作り方](http://www.es-cube.net/es-cube/reversi/sample/html/2_4.html)のページでは、以下のコードが[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で書く場合もこれぐらいシンプルに持っていきたい。