誰でも勝てる三目並べAIで遊ぼう

#はじめに

先に，Canvas を用いた三目並べの作成について報告した¹。このとき，cpu が選択する一手は，乱数を用いる方法であった。これは簡単な方法であるだけに，試行してみると，非常に弱いことが分かる。三目並べ AI を強くする方法として，ミニマックス法が知られている^{2 3 4}。参考記事² を参照しながら，Python をJavaScript に書き直すことによって，Canvas を用いた三目並べのプログラムに組み込んだ⁵。

ゲームの面白さは，勝ったときに，より強く感じられる。そこで，初心者でも勝てるような三目並べ AI の開発を考えた。その結果，誰でも勝てる三目並べAIが完成した⁶。やってみると判るように，誰でも勝てるだけでなく，負けようとしても勝ってしまう。引き分けに持ち込もうとしても，勝ってしまう。なぜ，そうなるのか，考えてみるのも面白いだろう。プログラム（最弱ミニマックス法）も置いてあるので，見ていただきたい⁷。

#ミニマックス法の実装

JavaScript に書き直したミニマックス法の実装部分を，下記に示す。

function minimax(depth) {
    // ミニマックス法で探索して，着手を返す
    if (state != GAME) { return evaluate(depth);}

    var best_value = 0;
    var value = 0;
    if (my_turn) { value = 10000;}
    else         { value = -10000;}

    for (var i = 0; i < 9; i++) {
        if (board[i] == 0) {
            put_value(i);
            var child_value = minimax(depth+1);
            if (my_turn) {
                if (child_value > value) {
                    value = child_value;
                    best_value = i;
                }
            }
            else {
                if (child_value < value) {
                    value = child_value;
                    best_value = i;
                }
            }
            undo_value(i);
        }
    }
    if (depth == 0) { return best_value;}
    else            { return value;}
}

#最弱ミニマックス法の実装

誰でも勝てる三目並べAI（最弱ミニマックス法）の実装部分を，下記に示す。

function minimaxmin(depth) {
    // ミニマックスミニ法で探索して，着手を返す
    if (state != GAME) { return evaluate(depth);}

    var best_value = 0;
    var value = 0;
    if (my_turn) { value = -10000;}
    else         { value = 10000;}

    for (var i = 0; i < 9; i++) {
        if (board[i] == 0) {
            put_value(i);
            var child_value = minimaxmin(depth+1);
            if (my_turn) {
                if (child_value < value) {
                    value = child_value;
                    best_value = i;
                }
            }
            else {
                if (child_value > value) {
                    value = child_value;
                    best_value = i;
                }
            }
            undo_value(i);
        }
    }
    if (depth == 0) { return best_value;}
    else            { return value;}
}

#おわりに

Canvas を用いた三目並べのプログラムに，ミニマックス法を組み込んだ。また，この最強ミニマックス法のアルゴリズムを逆にすることによって，誰でも勝てる三目並べAI（最弱ミニマックス法）のプログラムを作成した。ゲームの初心者に，興味を持ってもらうのに役立つと思われる。

1. 三目並べをCanvasとjQueryで作る ↩

2. ミニマックス法で最強の3目並べAIを実装する話 ↩ ↩²

3. 三目並べで学ぶミニマックス法 ↩

4. ミニマックス法を使ってマルバツゲームを実装した [Rust] ↩

5. 三目並べ（対局レベル２） ↩

6. 三目並べ（対局レベル－２） ↩

7. 三目並べ プログラム HTML JavaScript ↩