読者です 読者をやめる 読者になる 読者になる

simplestarの技術ブログ

目的を書いて、思想と試行、結果と考察、そして具体的な手段を記録します。

3目ならべで強化学習すると、どうなる?→こうなる

AI

前回の記事ははじめての強化学習ということで、Bellman方程式を使ってきわめて単純な経路分岐問題を解いてみました。
今回はもう少し複雑な経路問題を解いてみたいと思います。

お題は「3目ならべ」です。

先攻後攻が決まったら、まずは 3x3 のマス目の 9つのうち、いずれかに先行が〇を描き
その後は互いに余ったマスに×と〇を描いていき、3つ先に並べた方が勝利するゲームです。

理論的な話はもう理解できているので
さっそく、全パターンを走査するプログラムを書いてみましょう。

ということで、書きました。

    bool?[] _masume = new bool?[9];

    int[][] _finish = new int[8][];

	void Start ()
    {
        for (int i = 0; i < _masume.Length; i++)
        {
            _masume[i] = null;
        }
        _finish[0] = new int[3] { 0, 1, 2 };
        _finish[1] = new int[3] { 3, 4, 5 };
        _finish[2] = new int[3] { 6, 7, 8 };

        _finish[3] = new int[3] { 0, 3, 6 };
        _finish[4] = new int[3] { 1, 4, 7 };
        _finish[5] = new int[3] { 2, 5, 8 };

        _finish[6] = new int[3] { 0, 4, 8 };
        _finish[7] = new int[3] { 2, 4, 6 };

        PutTrue();
    }

    private bool IsFinish(int[] finish, bool ex)
    {
        return (ex == _masume[finish[0]] && ex == _masume[finish[1]] && ex == _masume[finish[2]]);
    }

    private void PutTrue()
    {
        for (int i = 0; i < _masume.Length; i++)
        {
            if (null == _masume[i])
            {
                bool ex = true;
                _masume[i] = ex;
                bool win = false;
                for (int k = 0; k < _finish.Length; k++)
                {
                    if (IsFinish(_finish[k], ex))
                    {
                        win = true;
                        break;
                    }
                }
                if (!win)
                    PutFalse();
                _masume[i] = null;
            }
        }
    }

    private void PutFalse()
    {
        for (int j = 0; j < _masume.Length; j++)
        {
            if (null == _masume[j])
            {
                bool ex = false;
                _masume[j] = ex;
                bool win = false;
                for (int k = 0; k < _finish.Length; k++)
                {
                    if (IsFinish(_finish[k], ex))
                    {
                        win = true;
                        break;
                    }
                }
                if (!win)
                    PutTrue();
                _masume[j] = null;
            }
        }
    }

勝利判定付きです。

では、強化学習するための、State と Action の樹形図をこの再帰処理に構築してもらいましょう。
そんなコードを書いてみます。

はい、ということで書きました。
ちゃんと樹形図を作ってくれています。

f:id:simplestar_tech:20170122173848j:plain

    class Action
    {
        public int i = -1;
        public float reward = 0;
        public State state = null;
    }

    class State
    {
        public float reward = 0;
        public List<Action> actions = new List<Action>();
    }

    bool?[] _masume = new bool?[9];

    int[][] _finish = new int[8][];

    int _gameover = 0;

	void Start ()
    {
        for (int i = 0; i < _masume.Length; i++)
        {
            _masume[i] = null;
        }
        _finish[0] = new int[3] { 0, 1, 2 };
        _finish[1] = new int[3] { 3, 4, 5 };
        _finish[2] = new int[3] { 6, 7, 8 };

        _finish[3] = new int[3] { 0, 3, 6 };
        _finish[4] = new int[3] { 1, 4, 7 };
        _finish[5] = new int[3] { 2, 5, 8 };

        _finish[6] = new int[3] { 0, 4, 8 };
        _finish[7] = new int[3] { 2, 4, 6 };

        State state0 = new State() { reward = 0 };
        PutTrue(state0);
    }

    private bool IsFinish(int[] finish, bool ex)
    {
        bool isGameOver = (ex == _masume[finish[0]] && ex == _masume[finish[1]] && ex == _masume[finish[2]]);
        if (isGameOver)
            _gameover++;
        return isGameOver;
    }

    private void PutTrue(State state)
    {
        for (int i = 0; i < _masume.Length; i++)
        {
            if (null == _masume[i])
            {
                State newState = new State();
                state.actions.Add(new Action() { i = i, reward = 0, state = newState });
                bool ex = true;
                _masume[i] = ex;
                bool win = false;
                for (int k = 0; k < _finish.Length; k++)
                {
                    if (IsFinish(_finish[k], ex))
                    {
                        newState.reward = 1;
                        win = true;
                        break;
                    }
                }
                if (!win)
                    PutFalse(newState);
                _masume[i] = null;
            }
        }
    }

    private void PutFalse(State state)
    {
        for (int j = 0; j < _masume.Length; j++)
        {
            if (null == _masume[j])
            {
                State newState = new State();
                state.actions.Add(new Action() { i = j, reward = 0, state = newState });
                bool ex = false;
                _masume[j] = ex;
                bool win = false;
                for (int k = 0; k < _finish.Length; k++)
                {
                    if (IsFinish(_finish[k], ex))
                    {
                        newState.reward = -1;
                        win = true;
                        break;
                    }
                }
                if (!win)
                    PutTrue(newState);
                _masume[j] = null;
            }
        }
    }

ゲームオーバー数をざっと数えてみたところ21万回だったので21万の枝葉ができる樹形図となっている模様。
一応先攻だったときの報酬として、〇で勝てば+1、×で勝てば-1という形で State の reward を決めさせてもらいました。

あとは、この樹形図を使って学習するコードを書く必要がありますね。
書いてみます。

書きました。

    private void LearnState(State state)
    {
        for (int i = 0; i < state.actions.Count; i++)
        {
            Action action = state.actions[i];
            LearnAction(action);
        } 
    }

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

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

学習結果を表示すると次の通りです。

f:id:simplestar_tech:20170129112556j:plain

期待どおりでしたか?

そう、実は相手の着手も自分が打てるという条件と等しい学習方法ですので
相手が最弱手を打つことを想定して行動の報酬を決定しています。
つまり何処に打つにしても、必ず5手で勝利するため、報酬は同じとなってしまいました。

ということで
3目ならべで強化学習すると、どうなる?→こうなる
を示しました。

ちゃんとしたAIにするには、いつか勉強した MinMax法 を使うのがよさそうです。
記事は次に続きます。