【JavaScript】AI プログラミングのスゝメ 「ミニマックス法 三目並べ」
こんにちは。あるいはこんばんは皆さん。ご覧頂きありがとうございます。
いきなりで何ですが、皆さんには AI プログラミング（探索アルゴリズム）のキホンのキ ミニマックス法 を三目並べをベースに実装（コピペ）して頂きます。ハイ、そこ 「三目並べかよ、つまんね」 とか言わない。何事も基本が大事です。
実際のところ三目並べはゲーム性に乏しく、引き分けになることも知られていて、筆者も喰いつきのよい題材だとは思っていないのですが、ミニマックス法の解説ではよく扱われ資料は豊富です。伝える側、受け手にも適した扱いやすい題材てことなのでしょう。強いオセロとか、身の丈に合わない難しいプログラムに喰いつきがちですが、比較的やさしい小さなプログラムを一行一行丁寧に辿り プログラム全体 をしっかりと理解して、自分のものにしてしまうことに時間を使った方が近道だったりする。自身の経験から筆者はそう考えています。
この記事は JavaScript（プログラミング）初学者を意識して書いています。記載したコードは都度都度できるだけ丁寧に解説していますので、コード中のコメントと併せて読んでみてください。「面白そう」「もっと知りたい」てことになれば筆者的に思うツボなのですが、退屈そうと感じた方も「ツッコミどころでも探したろか」な感じでよろしくお願いします。
必要なものは使い慣れたテキストエディタとブラウザだけです。
テキストエディタを開いたら、さっそく始めましょう。
.html .js .png ファイルの命名とディレクトリ構成
以下のディレクトリ構成で各ファイルを配置していきます。
.
├─ index.html
├─ scripts
│ └─ ox-minimax.js
└─ images
└─ ox.png
HTML
index.html で保存するソースコードです。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8" />
<title>三目並べ(Minimax)</title>
<style>
.ox-container {
text-align: center;
}
#ox-board {
width: 234px;
height: 234px;
border: 1px solid;
margin: 0 auto;
}
#ox-board div {
width: 76px;
height: 76px;
float: left;
border: 1px solid;
cursor: pointer;
}
.maru {
background-image: url("./images/ox.png");
}
.peke {
background-image: url("./images/ox.png");
background-position: -76px;
}
</style>
</head>
<body>
<div class="ox-container">
<div id="ox-board"></div>
<p>
<button id="ai-button">- Minimax AI -</button>
</p>
</div>
<script src="./scripts/ox-minimax.js"></script>
</body>
</html>
背景画像
 |
|---|
| ox.png (152 x 76) |
ox.png で images ディレクトリ配下に置きます。
index.html ox.png ox-minimax.js（白紙）を所定の場所に配置できたら、続けて JavaScript コードを ox-minimax.js ファイルに貼り付けていきましょう。
定数（みたく扱う変数群）
var SIDE_SIZE = 3; // 辺の長さ
var BOARD_SIZE = SIDE_SIZE * SIDE_SIZE; // マスの数
var MARU_VALUE = 1; // マルを示す値
var PEKE_VALUE = -1; // ペケを示す値
var BLANK_VALUE = 0; // 空きを示す値
var MAX_VALUE = Number.POSITIVE_INFINITY; // 十分大きな数
var MIN_VALUE = Number.NEGATIVE_INFINITY; // 十分小さな数
「constで宣言しろよ」というツッコミが聞こえてきそうですが、このプログラムではvar宣言で統一。アロー関数式なんかも使いません。もしツッコミや質問なんかを頂いた場合、的確に回答するためには筆者的に ECMA-262 3rd edition 準規で書くしかないかなあ、ていうのがその理由です。初学者の方は、今どきのコードでないことを頭の隅っこにでも置いてください。（決して悪い書き方と言っているわけではないです）
コード解説に戻って、代入している値の意味についてはコメントの通り。次、行きます。
ルートオブジェクト
// ルートオブジェクト
var Marupeke = {
board: [0, 0, 0, 0, 0, 0, 0, 0, 0], // 盤面の状態（配列）
squareElements: [], // マス（DOM 要素）にアクセスするための参照を保持（配列）
turn: MARU_VALUE // 手番を示す値（先手マル）
};
これから順次、プロパティ（関数）を追加していくわけですが、ここでは特に難しいことしているわけではないので、サクッとコピペして次、行きます。
盤面（DOM）作成とイベント関数を設定する関数
前半はマスにあたる要素を生成して、親となる要素（DOMツリー）に追加挿入。後半はclickイベントで呼出される関数を設定しています。ここでのポイントは、発火したclickイベントをdocumentノードで一括して捕捉しているところになるでしょうか。設定した関数の第一引数で受け取れるEventオブジェクトを使えば、大抵の場合documentノードでの監視で事足ります。
// 盤面（DOM）作成とイベント関数を設定
Marupeke.createDOMBoard = function (id) {
var board = document.getElementById(id); // 親要素にアクセスするための参照
var elements = this.squareElements; // マス要素参照を保持する配列
var cell;
// 配列要素数がBOARD_SIZEになるまで繰り返し
while (elements.length < BOARD_SIZE) {
cell = document.createElement('div'); // div（マス）要素生成
board.appendChild(cell); // 生成した要素を親要素に追加挿入
elements.push(cell); // 生成要素の参照をelementsにpush
}
// ここからclickイベントで呼出される関数設定
this.handleEvent = function (event) { // handleEventメソッド定義
var target = event.target; // clickイベントが発火した要素参照
if (target.id === 'ai-button') { // id属性が'ai-button'なら
return tryAI(); // コンピュータに着手させる関数呼出し
}
var board = this.board;
var elements = this.squareElements;
for (var i = 0; i < elements.length; i++) {
// ユーザ選択位置を見つけ
if (target === elements[i]) {
return this.update(i, this.turn); // update関数呼出し
}
}
return false;
};
// addEventListenerにhandleEventメソッドを持つオブジェクト参照(this)を渡す
document.addEventListener('click', this, false);
// clickイベントで呼出される関数設定ここまで
return elements; // マス要素の参照が並ぶ配列を返す
};
// 盤面（DOM）作成関数呼出し
Marupeke.createDOMBoard('ox-board');
コピペ、保存が終わったら、ここで動作確認（デバッグ）してみましょう。実際に動かして視覚的に文脈の流れを確認した方が、コード読むよりも確実。面倒ですが、スキルアップには必須です。
Chrome デベロッパー ツール
index.htmlをブラウザで開いたら [F12] キーをポチっと [開発者ツール] が開きます。 [ソース] タブ [ox-minimax.js] を選択してwhile文頭に [ブレークポイント] 設定まで進めましょう。あとは [F5] キー（再読み込み） [F8] キー押下で、生成されたマス要素が親要素（DOMツリー）へ挿入（描画）される様子を確認できます。[範囲] （ローカルスコープ）欄で、変数elements（squareElementsプロパティ）に蓄積されていくマス要素への参照を確認してみるのもよいです。
num 並びラインがあれば true を返す関数
勝敗判定です。横、縦、斜めの各ラインを順に走査。勝敗成立ラインが見つかれば true を返して終了。見つからなければ、文末のreturn文まで処理を行いfalseを返します。ミニマックス探索でも頻繁に呼ばれ、AI の振る舞いにも関わる関数です。
// num並びラインがあればtrueを返す
Marupeke.lineChecker = function (turn, num) {
var lineIndex = [
0, 1, 2, // 探索位置（ライン）
3, 4, 5,
6, 7, 8,
0, 3, 6,
1, 4, 7,
2, 5, 8,
0, 4, 8,
2, 4, 6
];
var work = 0; // 初期値
for (var i = 0; i < lineIndex.length; i++) {
work += this.board[lineIndex[i]]; // 各マスの値をworkに加算
if (i % SIDE_SIZE === SIDE_SIZE - 1) { // ライン終端
if (work * turn === num) return true; // num並びラインが見つかる
work = 0; // 初期値に戻す
}
}
return false; // num並びラインなし
};
Marupeke.lineChecker(1, 3)で呼出せば |O|O|O| マルの三つ並びでヒットします。
Marupeke.lineChecker(-1, 2)なら |X| |X| とか、いわゆるリーチラインの有無を調べることができます。
着手位置と手番を受け取り盤面データとDOMを更新する関数
マル、ペケの描画にはいろんなアプローチがありますが、ここではマス要素のclassNameプロパティでスタイル変更（CSS 背景画像適用）しています。
// 着手位置と手番を受け取り内部データとDOM更新
Marupeke.update = function (move, turn) {
if (this.board[move] !== BLANK_VALUE) return false;
this.board[move] = turn; // 内部盤面更新
// DOM盤面更新（クラス名代入）
this.squareElements[move].className = turn === MARU_VALUE ? 'maru' : 'peke';
if (this.lineChecker(turn, SIDE_SIZE)) { // turn三つ並びライン完成
console.log(turn === MARU_VALUE ? 'マル' : 'ペケ', '勝ち'); // ゲーム終了処理
}
this.turn = -turn; // 手番を渡す（符号反転）
return true;
};
動作確認の様子
update関数の定義でマス目をクリックできるようになりました。マルとぺケが交互に描画され、ライン完成でコンソール欄にメッセージが表示されれば成功です。次に進みましょう。
すべての合法着手を返す関数
三目並べやオセロのようなゲームに限らず、迷路やパズルなどの最短経路探索でも必要になるのが、未来局面の網羅。扱うものによっては面倒なのですが、三目並べは空き位置を数え上げるだけなので楽です。
// すべての合法着手を返す
Marupeke.possibleMoves = function (turn) {
var arr = [];
for (var i = 0; i < BOARD_SIZE; i++) {
if (this.board[i] === BLANK_VALUE) arr.push(i);
}
return arr;
};
局面評価関数
単に勝ち負け引き分けだけを評価する必勝読みなら、返す値はこれで十分です。あえて勝ち負けの評価値を一定にすることで、アルファ・ベータ法などの探索アルゴリズムでは、計算コスト（時間）を抑えることができます。
// 局面評価関数
Marupeke.evaluate = function (line, max) {
if (line) { // ライン完成
if (max) return 1; // max勝ち
else return -1; // mini勝ち
}
return 0; // 引き分け
};
ミニマックス法
この記事のタイトルにもなっている心臓部です。Wikipedia のミニマックス法擬似コードを、ほぼそのまんまトレースしています。
// Minimax
function minimax (board, depth, turn, maxTurn) {
var line = Marupeke.lineChecker(turn, SIDE_SIZE); // turnのライン監視
if (line || depth === 0) { // ライン完成か深さ限度
return Marupeke.evaluate(line, turn === maxTurn); // 終局
}
turn = -turn; // 手番を渡す（符号反転）
var moves = Marupeke.possibleMoves(); // すべての着手
var score, max, min, i = 0;
if (turn === maxTurn) { // max番
max = MIN_VALUE; // 十分小さな数
for ( ; i < moves.length; i++) { // 展開
board[moves[i]] = turn; // 局面を進める
score = minimax(board, depth - 1, turn, maxTurn); // 潜る（再帰呼出し）
board[moves[i]] = BLANK_VALUE; // 局面を戻す
if (score > max) max = score;
}
return max;
} else { // mini番
min = MAX_VALUE; // 十分大きな数
for ( ; i < moves.length; i++) { // 展開
board[moves[i]] = turn; // 局面を進める
score = minimax(board, depth - 1, turn, maxTurn); // 潜る（再帰呼出し）
board[moves[i]] = BLANK_VALUE; // 局面を戻す
if (score < min) min = score;
}
return min;
}
}
簡単な流れは
- 受け取った局面が終局かを調べ、終局なら評価値を返す
- 手番を変更し、すべての着手を数え上げ展開
- 生成した局面を
minimax関数（自身）に渡して呼出す - 局面を戻して
minimax関数が返した評価値を手番（大小）に応じて更新 - 局面を生成できなくなるまで繰り返し、最終的（ベスト）な評価値を返す
これを再帰的に繰り返します。さっぱり意味不明ですか？今はそれでいいんです。
すべての着手を評価して局面を更新する関数（動作確認用）
button 要素クリックで呼出される関数です。コピペ、保存すればプログラム完成です。
// すべての着手評価と局面更新
function tryAI () {
var best = null; // 初期値
var board = Marupeke.board; // 盤面の状態（配列）
var turn = Marupeke.turn; // 現在の番手（max番）
var moves = Marupeke.possibleMoves(); // すべての着手
console.log('着手数（深さ制限）', moves.length); // ログ出力
var score;
for (var i = 0; i < moves.length; i++) { // 展開
board[moves[i]] = turn; // 局面を進める
score = minimax(board, moves.length - 1, turn, turn); // 着手（moves[i]）を評価
board[moves[i]] = BLANK_VALUE; // 局面を戻す
console.log('move:', moves[i], 'score:', score); // ログ出力
// scoreがbest.scoreを超えていればbest更新
if (!best || best.score < score) best = {move: moves[i], score: score};
}
if (best) { // 最善手が見つかる
Marupeke.update(best.move, turn); // 着手とturnを渡してDOMと内部データ更新
console.log('Best', 'move:', best.move, 'score:', best.score); // ログ出力
return true;
}
return false;
}
「人間らしい AI」とは？
「人間らしい」次の一手は？
- 勝てる局面では必ず勝つ局面にする
- ほぼほぼ負け局面でも可能なら相手のミスで勝てる局面にする
「人間らしい」「最善を尽くす」は、こんな感じに定義できるのではないかと。で、こんな話をするのは、完成したプログラムがこの定義から外れ「人間らしくなくない」「最善を尽くそうとしない」からなのですが。（意図的です）
筆者は将棋対局のネット中継をよく観ます。将棋は幼い頃遊びでやった程度の、いわゆる「観る将」です。億単位の局面を読む AI とほとんど同じ手を指し進めるのですから、プロ棋士は凄いですね。それでも、たまに大盤解説を担当する棋士が AI の挙げる候補手に「人間はまず指さない、指せない」マイナスの手にしか見えないようで、解説に困る場面があります。AI 世代に代わる過渡期だからなのかもですけど、解説の先生も大変だなあと。対局中継 AI は精度を犠牲にしてでも、人間らしい古典的思考が通用する仕様でもよいのではないかと思ったりします。
ここまで読んでくれたということは、それなりに興味を持ってくれたのではないかと期待して筆者から課題をひとつ。
「このプログラムが人間らしく最善を尽くした手を選ぶようにしなさい」
時機を見て、皆さんといっしょに答え合わせできればいいかなと考えています。ヒントになる資料は豊富ですから、余力があればチャレンジしてみてください。
なんだか雑談気味の締めになりましたけど、最後までお付き合いありがとうございました。ではまた。お疲れした。
Discussion