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

前回の記事ははじめての強化学習ということで、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;
    }