オセロを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で書く場合もこれぐらいシンプルに持っていきたい。