【Unity】MiniMax法で〇✖ゲームのAIを実装する

今回も、前回までの続きです。
〇✖ゲームの実装自体は前回で終えたので、今回はMiniMax法でAIを実装します。

MiniMax法とは？

MiniMax法とは、簡単に言うと、

「プレイヤー（自分）は自分にとって最も有利な手を選び（最大化）、
相手は自分にとって最も不利な手を選ぶ（最小化）」と仮定した上で、
再帰的に最善の手を求めるアプローチのことです。

詳しくは、Wikipedia の内容をご覧ください。

MiniMax法による最善手の探索

MiniMax()メソッドがMiniMax法による最善手の探索を行っています。

MiniMax()メソッド自体が再帰的に処理を行っているため、
ChangeBestCellSprite()メソッド （命名テキトーすぎる） は最初の呼び出しのみ行います。

MiniMax()内で引数のフラグが逆のMiniMax()を呼び出しているのは、
自分（AI）と相手（Player）の手を交互に想定しているからです。

// 最善手のセルのスプライトを変更する
private void ChangeBestCellSprite()
{
    int bestScore = int.MinValue;
    int row = -1;
    int column = -1;

    for (int r = 0; r < Size; r++)
    {
        for (int c = 0; c < Size; c++)
        {
            if (cells[r, c].sprite == null)
            {
                cells[r, c].sprite = cross;
                int score = Minimax(0, false);
                cells[r, c].sprite = null;

                if (score > bestScore)
                {
                    bestScore = score;
                    row = r;
                    column = c;
                }
            }
        }
    }

    if (row != -1 && column != -1 && cells[row, column].sprite == null)
    {
        cells[row, column].sprite = cross;
    }
}

// 再帰的に現在の一手を評価する
int Minimax(int depth, bool isMaximizing)
{
    if (IsWin())
    {
        return isMaximizing ? -1 : 1;
    }
    if (IsDraw())
    {
        return 0;
    }

    if (isMaximizing)
    {
        int bestScore = int.MinValue;

        for (int r = 0; r < Size; r++)
        {
            for (int c = 0; c < Size; c++)
            {
                if (cells[r, c].sprite == null)
                {
                    cells[r, c].sprite = cross;

                    int score = Minimax(depth + 1, false);

                    cells[r, c].sprite = null;

                    bestScore = Mathf.Max(score, bestScore);
                }
            }
        }
        return bestScore;
    }

    // 相手が自分のスコアを最小化するように行動すると仮定
    else
    {
        int bestScore = int.MaxValue;

        for (int r = 0; r < Size; r++)
        {
            for (int c = 0; c < Size; c++)
            {
                if (cells[r, c].sprite == null)
                {
                    cells[r, c].sprite = circle;

                    int score = Minimax(depth + 1, true);

                    cells[r, c].sprite = null;

                    bestScore = Mathf.Min(score, bestScore);
                }
            }
        }
        return bestScore;
    }
}

このコードを実行すると、AIが確実に中央（1, 1）のセルを埋めに来るのが分かります。
また、プレイヤー（自分）がリーチになると、必ずゴールを阻止してきます。

おわりに

完璧とは程遠い実装ですが、MiniMax法としてのアプローチが出来ているはずです。
今後は、もっと高度なAIの動きにチャレンジしていきたいと思います。

最後までご覧いただきありがとうございました