3目ならべ（〇×ゲーム）で最強のAIを作る

表題の通り、今回は3目ならべで最強のAIを作りました。
最も勝利確率の高いマスを赤く示してくれるツールとなっています。

具体的にどうしたかというと
前回作った強化学習のコードの一部を次の通り、変更してみました。
変更の意図としてはBellman方程式のModelの部分にて、着手可能なすべての手に対して均等に着手する確率を割り振ってみたらどうなるか、というものです。

    private void LearnAction(Action action)
    {
        LearnState(action.state);
        action.reward = action.state.reward + 0.999f * GetSumReward(action.state);
    }

    private float GetSumReward(State state)
    {
        if (0 == state.actions.Count)
        {
            return 0;
        }
        float sumReward = 0;
        for (int i = 0; i < state.actions.Count; i++)
        {
            sumReward += state.actions[i].reward / state.actions.Count;
        }
        return sumReward;
    }

何故最強と言えるのか、それを確かめる作業をしてみましょう。
今回作った行動の報酬の通りに打つ先手をAIとして、すべての着手を調べてみます。
ここでAIは常に同じ状況で同じ手を返すため、すべての着手を調べることができます。

作った行動と状態の樹形図をたどるようにして、先手をAIにした場合の後手の人間があらゆる手を打ったとしてその後の勝敗を調べました。
その時の全数検査のコードがこちら

結果は、後手の人間が勝利した回数 = 0 引き分けた回数 = 4 負けた回数 = 72 となりました。
対局パターン数は76ということでした。

つまり、先手において最強のAI（少なくとも負けることがないAI）ができていることを確認できました。
今度は後手用のAIも作ってみましょう。
次回へ続きます。

    int _humanWinCount = 0;
    int _humanDrawCount = 0;
    int _humanLoseCount = 0;
    int _gamePatternCount = 0;

    void Start ()
    {
        _globalState = new State() { reward = 0 };
        _currentState = _globalState;
        PutTrue(_globalState);
        LearnState(_globalState);
        AIPut(_globalState);

        Debug.Log("Human win = " + _humanWinCount + " draw = " + _humanDrawCount + " lose = " + _humanLoseCount);
        Debug.Log("Pattern Count = " + _gamePatternCount);
    }

    private void AIPut(State state)
    {
        float minmax = 0;
        int actionOffset = -1;
        if (_mark)
        {
            minmax = float.MinValue;
            for (int i = 0; i < state.actions.Count; i++)
            {
                if (minmax < state.actions[i].reward)
                {
                    minmax = state.actions[i].reward;
                    actionOffset = i;
                }
            }
        }
        else
        {
            minmax = float.MaxValue;
            for (int i = 0; i < state.actions.Count; i++)
            {
                if (minmax > state.actions[i].reward)
                {
                    minmax = state.actions[i].reward;
                    actionOffset = i;
                }
            }
        }
        if (-1 != actionOffset)
        {
            State nextState = state.actions[actionOffset].state;
            _mark = !_mark;
            PutTest(nextState);
        }
    }

    private void PutTest(State state)
    {
        if (0 == state.actions.Count)
        {
            bool win = state.reward > 0;

            if (win)
                ++_humanLoseCount;
            else
                ++_humanDrawCount;
            ++_gamePatternCount;
        }
        for (int i = 0; i < state.actions.Count; i++)
        {
            State nextState = state.actions[i].state;
            _mark = !_mark;

            if(nextState.reward < 0)
            {
                ++_humanWinCount;
                ++_gamePatternCount;
            }
            else
                AIPut(nextState);
        }
    }