オセロをMinMax法を導入する方法(JavaScript編)
JavaScriptでオセロを作っていて、そのオセロのCOMにMinMax法を導入したので方法を紹介。
ただし、コードは結構汚いです。
MinMax法とは?
MinMax法とは、オセロや将棋等のゲームで、コンピュータがどのように考えて手を指すかと言う思考方法(アルゴリズム)の1つ。
上記の画像から分かるように、オセロには様々な手順の可能性が考えられるが、それぞれの局面に評価を付けていき、どの手順が最善かを調べるのが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で書く場合もこれぐらいシンプルに持っていきたい。