探索アルゴリズムを小さなモデルで動かして確認してみた
オセロで探索アルゴリズムを使おうとしてうまく使えなかったので、小さなモデルで動作を確認しながら理解しようと思い、試してみた。
どうやって動作を確認しようかと思ったが、最近JavaScriptがわかってきたので、JSONを探索ツリーとしてブラウザの検証でconsole.logの出力を確認する方法で試した。
試してわかったが、結構サンプルコード間違っていると思う。
末端のリーフノードを評価値とした都合でdepthは使わなかった。通常は評価関数から取得するものだ。
オセロゲーム開発 ～ミニマックス探索法～
https://uguisu.skr.jp/othello/minimax.htmlちょうどオセロの探索法を紹介しているページがあったのでこの例の動作を確認してみた。図で説明してあるのがありがたい。プログラム例は結果が異なったので、Wikipediaのコードも参考にしながら試した。
https://ja.wikipedia.org/wiki/ミニマックス法このサイトでは以下の3つの検索アルゴリズムの図解があった。
- Minimax（ミニマックス）探索法
- Negamax 探索法
- アルファベータ法（alpha-beta search）～
その他にもいろいろ紹介されてあったが、残念ながら図がなかったので、以上の3つを試してみた。
Minimax(ミニマックス)探索法
<!DOCTYPE html>
<html>
<head>
<title>Minimax(ミニマックス)探索法</title>
</head>
<body>
<script>
let tree = {
"S": {
"A": {
"C": [2,4,5],
"D": [7,3,5],
},
"B": {
"E": [6,4,1],
"F": [3,4,2],
},
},
};
let Minimax = function(key, value, turn) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
let best = turn ? -100 : 100;
for (let i = 0; i < values.length; ++i) {
let val = Minimax(keys[i], values[i], !turn);
if (turn && best < val) {
console.log("if (turn && best(", best, ") < val(", val, ") ) best = val", val);
best = val;
}
if (!turn && best > val) {
console.log("if (!turn && best(", best, ") < val(", val, ") ) best = val", val);
best = val;
}
}
console.log(key, value, turn, "return best", best);
return best;
};
console.log("result", Minimax(Object.keys(tree), Object.values(tree), false));
</script>
</body>
</html>上のhtmlをブラウザで表示するとブラウザの表示は真っ白だが、Chromeの検証(右クリックメニューの検証あるいは[F12]等で表示)のConsoleで確認したのが下の画像。実行している順番等がわかる。最終結果も図の通りだ。turnでコードが分かれているので符号を反転する必要はないはずだ。はじめ負の数が出て結果も違ったので悩んだ。
Negamax 探索法
<!DOCTYPE html>
<html>
<head>
<title>Negamax 探索法</title>
</head>
<body>
<script>
let tree = {
"S": {
"A": {
"C": [2,5,7],
"D": [4,3,5],
},
"B": {
"E": [6,4,1],
"F": [3,4,2],
},
},
};
let NegaMax = function(key, value) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return -value;
}
let best = -100;
for (let i = 0; i < values.length; ++i) {
let val = -NegaMax(keys[i], values[i]);
if (best < val) {
console.log("best(", best, ") = val(", val, ")");
best = val;
}
}
console.log(key, value, "return best", best);
return best;
};
console.log("result", NegaMax(Object.keys(tree), Object.values(tree)));
</script>
</body>
</html>
図の通りに動いた。呼ぶたびに符号を反転することでコードを共通化している。試したコードではturnは使わなかったので削除した。NegaMaxはシンプルなコードになるのだが、符号を反転させるので頭が混乱する。
αβ(アルファベータ)法ゲーム木探索
https://uguisu.skr.jp/othello/alpha-beta.html<!DOCTYPE html>
<html>
<head>
<title>αβ(アルファベータ)法ゲーム木探索</title>
</head>
<body>
<script>
let tree = {
"S": {
"A": {
"C": [2,4,5],
"D": [7,3,5],
},
"B": {
"E": [4,3,2],
"F": [6,4,1],
},
},
};
let alphabeta = function(key, value, turn, alpha, beta) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
for (let i = 0; i < values.length; ++i) {
let val = alphabeta(keys[i], values[i], !turn, alpha, beta);
if (turn) {
if( val > alpha) {
console.log("if (turn && val(", val, ") > alpha(", alpha, ")");
alpha = val;
}
if (alpha >= beta) {
console.log("if (alpha(", alpha, ") >= beta(", beta, ")) break; // βカット");
break;
}
}
if (!turn) {
if (val < beta) {
console.log("if (!turn && val(", val, ") < beta(", beta, ")");
beta = val;
}
if (alpha >= beta) {
console.log("if (alpha(", alpha, ") >= beta(", beta, ")) break; // αカット");
break;
}
}
}
if (turn) {
console.log(key, value, turn, alpha, beta, "return alpha", alpha);
return alpha;
} else {
console.log(key, value, turn, alpha, beta, "return beta", beta);
return beta;
}
};
console.log("result", alphabeta(Object.keys(tree), Object.values(tree), false, -100, 100));
</script>
</body>
</html>
結果にβカットとαカットが登場する。Eは登場するが、Fはカットされていて登場しない。
3つとも図の通りに動かすことができた。
5分で覚えるAI Minimax（ミニマックス）法とalpha-beta法
せっかくなので、もう少し試そうと思い、探したらまたオセロのページがあったので試した。同じツリーでMinimax法とalpha-beta法を説明してくれている。
Minimaxアルゴリズム
<!DOCTYPE html>
<html>
<head>
<title>Minimax(ミニマックス)アルゴリズム</title>
</head>
<body>
<script>
let tree = {
"N0": {
"N1": {
"N1-1": 7,
"N2-2": 12,
},
"N2": {
"N2-1": -5,
"N2-2": -10,
},
"N3": {
"N3-1": 20,
"N3-2": -2,
},
},
};
let maxlevel = function(key, value) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
let score_max = -100;
for (let i = 0; i < values.length; ++i) {
let score = minlevel(keys[i], values[i]);
if (score > score_max) {
console.log("if (score(", score, ") > score_max(", score_max, ")) { score_max = score; }");
score_max = score;
}
}
console.log(key, value, "return score_max", score_max);
return score_max;
};
let minlevel = function(key, value) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
let score_min = 100;
for (let i = 0; i < values.length; ++i) {
let score = maxlevel(keys[i], values[i]);
if (score < score_min) {
console.log("if (score(", score, ") < score_min(", score_min, ")) { score_min = score; }");
score_min = score;
}
}
console.log(key, value, "return score_min", score_min);
return score_min;
};
console.log("result", minlevel(Object.keys(tree), Object.values(tree)));
</script>
</body>
</html>関数が二つに分かれている。サンプルではminlevelからminlevelを呼んでいるが、交互に呼ぶのでminlevelからはmaxlevelを呼ぶ。
alpha-beta法
<!DOCTYPE html>
<html>
<head>
<title>alpha-beta法</title>
</head>
<body>
<script>
let tree = {
"N0": {
"N1": {
"N1-1": 7,
"N2-2": 12,
},
"N2": {
"N2-1": -5,
"N2-2": -10,
},
"N3": {
"N3-1": 20,
"N3-2": -2,
},
},
};
let maxlevel = function(key, value, alpha, beta) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
let score_max = -100;
for (let i = 0; i < values.length; ++i) {
let score = minlevel(keys[i], values[i], alpha, beta);
if (score >= beta) {
console.log("if (score(", score,") >= beta(", beta, ")) { return score; } // βカット");
return score;
}
if (score > score_max) {
console.log("if (score(", score, ") > score_max(", score_max, ")) { score_max = score; }");
score_max = score;
console.log("alpha = Max.max(alpha(", alpha, "), score_max(", score_max, ");");
alpha = Math.max(alpha, score_max);
}
}
console.log(key, value, "return score_max", score_max);
return score_max;
};
let minlevel = function(key, value, alpha, beta) {
let keys = Object.keys(value);
let values = Object.values(value);
if (values.length == 0) {
return value;
}
let score_min = 100;
for (let i = 0; i < values.length; ++i) {
let score = maxlevel(keys[i], values[i], alpha, beta);
if (score <= alpha) {
console.log("if (score(", score,") <= alpha(", alpha, ")) { return score; } // αカット");
return score;
}
if (score < score_min) {
console.log("if (score(", score, ") < score_min(", score_min, ")) { score_min = score; }");
score_min = score;
console.log("beta = Max.min(beta(", beta, "), score_min(", score_min, ");");
beta = Math.min(beta, score_min);
}
}
console.log(key, value, "return score_min", score_min);
return score_min;
};
console.log("result", minlevel(Object.keys(tree), Object.values(tree), -100, 100));
</script>
</body>
</html>
αカットが2回起きている。
今度探索アルゴリズムを使うときは小さなモデルで試してから使おうと思う。