最近、「絶対に勝てない三目並べ」のゲームを作ったのですが、非常にささやかながらも楽しいプロジェクトで、いろいろ学ぶこともできました。ゲームの全体像に興味がある方は、 こちらでゲームを試してみてください 。

無敵のゲームにするには、コンピュータ側が全ての手を計算し、何らかの基準を用いて最善の手を決められるようなアルゴリズムを作る必要があります。多岐にわたって調べた結果、このプロジェクトにはどうやら ミニマックス アルゴリズムが適当そうだということが分かりました。

このアルゴリズムを根本的な意味で真に理解し、自分のゲームに実装できるようになるまでにはある程度の時間が必要でした。多くのコードサンプルと説明に目を通しましたが、私が能なしだからか、どれを見てもプロセスの内実を十分に理解することはできなかったのです。この投稿が、ミニマックスアルゴリズムに関する皆さんの理解に少しでもお役に立てたらと思います。

三目並べにおける完璧なゲームの説明

最初に、三目並べで完璧なゲームをすることの定義から始めましょう。

完璧な試合運びをすれば、結果は勝つか引き分けになります。ここでもし相手も完璧なら、そのゲームは引き分けです。

このような状態をどうやって定量的に記述できるでしょうか。まずは”終局時の条件”に点数を割り当ててみます。

• 勝てば10ポイント獲得
• 負ければ10ポイント喪失（相手が10ポイント獲得）
• 引き分けなら0ポイントで、ポイント獲得者なし

これで、どのゲームの結果に対しても点数を決められる基盤のようなものができました。

簡単な例で確認

ゲーム終盤の例を使って、これを適用してみましょう。私は×で、次は私の番です。最終的な目標は、もちろん点数を最大限に稼ぐことですよね。

一番上の図の状態の時に自分の番であれば、いくつかの選択肢があることになります。打つことができる場所は3マスで、そのうちの1マスに打てば勝ちが決まり10ポイント獲得です。ただ、その他のマスに打ってしまうと、逆に○が勝利となります。もちろん○には勝たせたくないですから、ここでの私の目標は、先手として最大点数を稼げる一手を打つことです。

○の視点

○の立場から見るとどうでしょうか。○も勝つためにゲームをしていますよね。しかし先手のこちら側とは攻め方が逆で、こちらの結果が最悪に終わるような選択肢を取ることになると思います。つまり○は、こちら側の最終的な点数を最小限に抑えたいというわけです。では、上の図で勝ちが決まらずにゲームが継続した場合について、○の視点から見てみましょう。

明らかに、○は－10ポイントに結びつくような手を選ぶでしょう。

ミニマックスの説明

ミニマックスアルゴリズムでは、2人のプレーヤー間の交互の動きが鍵で、”順番が来た”プレーヤーは最大点数となる一手を選択しようとします。選択肢の点数は、どの一手が相手にとって最小であるかによって決まります。そして、相手プレーヤーの手の点数は、最大点数を取ろうとする次の順番のプレーヤーによって決まり、このようにツリーを移動しながら終局へと至ります。

×が”次の順番のプレーヤー”と仮定すると、アルゴリズムは次のように説明できます。

• ゲームが終わる場合、×側から見たスコアを結果として返す
• そうでない場合、選択可能なそれぞれの手における新たなゲーム状態のリストを取得する
• 点数のリストを作成する
• 各状態について、その状態のミニマックスの結果を点数リストに追加する
• ×の番であれば、点数リストから最大点数を返す
• ○の番であれば、点数リストから最小点数を返す

このアルゴリズムは再帰的ですよね。最後の点数が確定するまで、プレーヤーの間を行ったり来たりしています。

アルゴリズムの実行をツリー全体と共に見てみましょう。そしてアルゴリズム的に、どうしてすぐに勝ちに結びつくような手が選択されるかを示したいと思います。

• 1の状態で次は×の番。×は状態2、3、4を生成し、これらの状態についてミニマックスを呼び出す。
• 状態2では、ゲームが終了するため、状態1の点数リストに＋10をプッシュする。
• 状態3、4では終局を迎えないため、3は状態5と6を生成し、それらについてミニマックスを呼び出す。同じく状態4は状態7と8を生成し、それらについてミニマックスを呼び出す。
• 状態5は状態3の点数リストに－10をプッシュする。同様に状態7が状態4の点数リストに－10をプッシュする。
• 状態6と8が、終局となる唯一の選択肢を生成し、それぞれ状態3と4の手リストに＋10を追加する。
• 状態3と4では○の番のため、○は最小点数を探す。－10と＋10を比べて、両方の状態ともに－10を選択する。
• 最後に状態2、3、4の点数リストに＋10、－10、－10が並べられ、その中から状態1は最大点数である＋10を得て勝つことができる状態2を選ぶ。

やることがかなりたくさんありますね。こういうアルゴリズムはコンピュータに任せるのが吉です。

ミニマックス法をコード化する

これまでの説明で、ミニマックスアルゴリズムがどうやって最善の手を弾きだすのかなんとなく分かったでしょうか？　理解をさらに深めるために私が行ったミニマックスアルゴリズムの実装を見てみましょう。

以下がゲームの得点の関数です。

# @player is the turn taking player
def score(game)
    if game.win?(@player)
        return 10
    elsif game.win?(@opponent)
        return -10
    else
        return 0
    end
end

シンプルですよね。次の手を打つプレーヤーがゲームに勝つなら、return +10。対戦相手が勝つなら-10。そうでなければ0です。気を付けなければいけないのは、問題なのはプレーヤーが誰かということではありません。×か○かというのではなく、次は誰の番かということが重要です。

では、続いて実際のミニマックスアルゴリズムです。この実装では、 choice または move は単にボードの上の行と列です。例えば、3×3のボードでは、[0,2]は上の右のマスになります。

def minimax(game)
    return score(game) if game.over?
    scores = [] # an array of scores
    moves = []  # an array of moves

    # Populate the scores array, recursing as needed
    game.get_available_moves.each do |move|
        possible_game = game.get_new_state(move)
        scores.push minimax(possible_game)
        moves.push move
    end

    # Do the min or the max calculation
    if game.active_turn == @player
        # This is the max calculation
        max_score_index = scores.each_with_index.max[1]
        @choice = moves[max_score_index]
        return scores[max_score_index]
    else
        # This is the min calculation
        min_score_index = scores.each_with_index.min[1]
        @choice = moves[min_score_index]
        return scores[min_score_index]
    end
end

PerfectPlayer のクラスの中でこのアルゴリズムを動かすと、最善の手の究極の選択肢は @choice の変数の中に保存されます。そしてそれは、今のプレーヤーが手を打った後のゲームの新しい状態を返すのに使われます。

完璧だけど運命論者的なプレーヤー

上記のアルゴリズムを実装すると、三目並べのゲームでは誰も勝てないことが分かります。テスト中に私が発見した興味深いニュアンスは、完璧なプレーヤーは常に完璧だということです。言い換えるなら、完璧なプレーヤーが結果的に負けや引き分けに陥りそうな場合は、次の一手のための決断はどちらかというと運命論的になってしまいうということです。このアルゴリズムが言いたいのは基本的に”ヘイ、どうせ負けるぞ。だから、次やこの先6手で負けたって関係ない”ということです。

これを発見したのは、明らかに操作されたボード、もしくは”間違い”があるボードをアルゴリズムに渡して、次の最善の手を見つけ出そうとした時のことです。「完璧なプレーヤー」は私がすぐに勝つのを防ぐために少なくとも戦って抵抗するだろう、と私は予想していました。でも違いました。

注釈:Expected: Smart　予想していた賢い手
Actual: Dumb　実際のバカな手

ここで何が起きているか以下の手の状態をツリーにしたものを見て確認しましょう（分かりやすいように、いくつかの状態は排除しています）。

注釈: X wins. ×の勝利
X Ultimately Wins. （完璧なプレーヤーが抵抗した上で）結局×の勝利

• 1の状態ではどちらのプレーヤーも完璧です。○はコンピュータプレーヤーです。○が状態5を選べば、状態9で×が即座に勝ちます。
• しかし、状態3のように×が勝つのを○が阻止したとすると、×は状態7で○の勝利の可能性を潰します。
• こうなると、状態10、11のように、×の勝ち方には2つの可能性が出ます。ということで、状態7で○がどのような手にを選んだとしても関係なく×が結局は勝つのです。

これらのシナリオの結果と、結局は負けると分かっている中で空白のマスをどの手にも優劣がなく平等な形で左右上下に繰り返し埋めていくという事実から、最後の手として選ばれるのは5の状態です。完璧なプレーヤーにとって、1の状態に陥った時には5の状態が最後の一手となるのです。手の配置は[上の左、上の右、真ん中の左、真ん中の中央]です。

では、三目並べのすごい達人はどうしてるのでしょうか？

いい試合をする：深さ

ボードの中の並べ方に関わらず完璧なプレーヤーは完璧にプレーをして自分の負けに向かうので、このアルゴリズムを改善する鍵はゲームが終わるまでの回ってくる順番の数、つまりは”深さ”です。基本的に、完璧なプレーヤーは完璧にプレーをし、可能な限り試合を長引かせるようにします。

これをやるために、最後のゲームスコアから、深さ、つまり順番の数、反復を減算します。順番が多ければスコアが低く、順番が少なければスコアは高くなります。上述のコードを改訂するなら、以下のようにします。

def score(game, depth)
    if game.win?(@player)
        return 10 - depth
    elsif game.win?(@opponent)
        return depth - 10
    else
        return 0
    end
end

def minimax(game, depth)
    return score(game) if game.over?
    depth += 1
    scores = [] # an array of scores
    moves = []  # an array of moves

    # Populate the scores array, recursing as needed
    game.get_available_moves.each do |move|
        possible_game = game.get_new_state(move)
        scores.push minimax(possible_game, depth)
        moves.push move
    end

    # Do the min or the max calculation
    if game.active_turn == @player
        # This is the max calculation
        max_score_index = scores.each_with_index.max[1]
        @choice = moves[max_score_index]
        return scores[max_score_index]
    else
        # This is the min calculation
        min_score_index = scores.each_with_index.min[1]
        @choice = moves[min_score_index]
        return scores[min_score_index]
    end
end

ミニマックスを呼び出すたびに深さは1ずつインクリメントされ、最後のゲームの状態が最終的に計算されるとスコアは深さによって調整されます。ではこれがどういうことか以下のツリーで見てみましょう。

これを見ると、深さ（左に表記した黒色の数字）よって勝負が決まる最後の選択肢のスコアが変化します。ミニマックスの0の段階では、可能である最大のスコアを出そうと試み（○がプレーする番なので）、スコアが-8の他のものよりスコアのいい-6のものを選びます。そして、負けが分かっていても、わたしたちの信頼できる友、完璧なプレーヤーはここでは、潔く負けることよりも、動きを阻止することを選びます。

結論

今までの議論で、ミニマックスアルゴリズムの理解を深めることでき、三目並べで試合を優勢に持っていく方法が分かっていただけてたらうれしいです。もし、質問したいことや混乱したことがあれば、コメントを残してください。いただいたコメントを参考に、この記事を改善していきたいと思います。ここに出てきた 私の三目並べゲーム のコードは githubで見る ことができます。