C#で強化学習 その1 -Q-learning(Q学習)で簡単なゲームAIを作ってみる-

こんにちはLInk-Uの町屋敷です。

今回は強化学習をやっていきたいと思います。

主にQ-learningの具体的な実装の方法を書いて、Q-learning自体の証明とかには触れません。

強化学習は今までやってきたニューラルネットやSVMなどの学習方法と毛色が異なります。

何をやるかをざっくりいうと
ある問題を解きたいときにある状況になったときにこういうことをしたらこうなったという経験を蓄積して、
その経験を元に次に同じ状況になったとき最適な行動を選択するようにAIを訓練します。

Q-learningを行う準備

強化学習を行うアルゴリズムはたくさんあるのですが、今回はQ-learningという手法をC#で一から実装していきます。
いつものPythonだと一から実装すると重くてやってられなくなるかもしれないから回避。
C#には今回使わなかったけどUnityもあるしね。

早速実装して行きましょう。
今回のタスクはRPGでよくある1対1の戦闘で相手モンスターを倒すことです。
プレイヤーは状況に応じて攻撃や回復を行います。

強化学習ではプレイヤーに何回も戦闘を行ってその結果によってAIを賢くしていきます。
なので、Q-learningどうこうのまえに自動で戦闘を行うプログラムを先に書く必要があります。

まずプレイヤーや相手モンスターを扱う親クラスCharacterを作りましょう。

public abstract class Character
    {
        private string name;
        private int id;
        private int maxHp;
        private int maxMp;
        private int hp;
        private int mp;
        private Dictionary<int, Action> actions;
        private Dictionary<string, double> weeknesses;

        public Character()
        {
            this.Init();
        }

        private void Init()
        {
            this.name = this.SetName();
            this.id = this.SetId();
            this.maxHp = this.SetMaxHp();
            this.maxMp = this.SetMaxMp();
            this.hp = this.maxHp;
            this.mp = this.maxMp;
            this.actions = this.SetActions();
            this.weeknesses = this.SetWeekness();
        }

        private string SetName()
        {
            return this.GetType().Name;
        }

        public abstract int SetId();
        public abstract int SetMaxHp();
        public abstract int SetMaxMp();

        public void SetHp(int hp)
        {
            this.hp = hp;
        }

        public void SetMp(int mp)
        {
            this.mp = mp;
        }

        public abstract Dictionary<int, Action> SetActions();
        public abstract Dictionary<string, double> SetWeekness();

        public string GetName()
        {
            return this.name;
        }

        public int GetId()
        {
            return this.id;
        }

        public int GetHp()
        {
            return this.hp;
        }

        public int GetMp()
        {
            return this.mp;
        }


        public int GetMaxHp()
        {
            return this.maxHp;
        }

        public int GetMaxMp()
        {
            return this.maxMp;
        }

        public Dictionary<int, Action> GetActions()
        {
            return this.actions;
        }

        public Dictionary<string, double> GetWeekness()
        {
            return this.weeknesses;
        }

        public void RestoreHp()
        {
            this.hp = this.maxHp;
        }

        public void RestoreMp()
        {
            this.mp = this.maxMp;
        }

    }

攻撃力とか防御力とかはなくて、HPとMPだけです、ダメージ量とかは技で固定で、攻撃の属性に対する相性をweeknessesで設定するモデルです。

カードゲームによくある仕組み。

次に、キャラクターごとにデータを作っていきます。

public class Player : Character
    {
        public Player() : base()
        {

        }

        public override int SetId()
        {
            return 0;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 100;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

SetWeeknessはさっき書いた属性に対する耐性です。今回属性は「物理」と「魔法」があります。

SetActions関数でそのキャラクターが選択できる行動を定義します。

CharacterクラスとPlayerクラスのように親クラスとしてActionクラスを作り、

行動の内容はActionTableクラスに定義されています。

    public class Action
    {
        public int id;
        public int hpDamage;
        public int hpHeal;
        public int mpCost;
        public string attribute;

        public Action(int id, int hpDamage, int hpHeal, int mpCost, string attribute, ref int count)
        {
            this.id = id;
            this.hpDamage = hpDamage;
            this.hpHeal = hpHeal;
            this.mpCost = mpCost;
            this.attribute = attribute;
            ++count;
        }
    }

    static class ActionTable
    {
        public static int count;
        public static Action normalAttack;
        public static Action magicAttack;
        public static Action heal;
        public static Action strongAttack;

        static ActionTable()
        {
            count = 0;
            normalAttack = new Action(count, 10, 0, 0, "physical", ref count);
            magicAttack = new Action(count, 15, 0, 10, "magic", ref count);
            heal = new Action(count, 0, 40, 10, "magic", ref count);
            strongAttack = new Action(count, 30, 0, 0, "physical", ref count);
        }
    }

Playerクラスでプレイヤーの情報を設定しました。

同じことを敵モンスターでも行います。今回はゴブリン、ウィッチ、グリズリーの3種類の敵を作りました。

それぞれの特徴は後で書きます。

さて、これでデータは揃ったのであとは戦闘部分を書けばいいのですが、Q-learningの説明を先にしてから説明します。

Q-learningを実装する

強化学習は、ある状況になったときにこういうことをしたらこうなったという経験を蓄積して、
その経験を元に次に同じ状況になったとき最適な行動を選択するようにAIを訓練するものでした。

よってまずどんな状況を考慮するかを決めてあげなくてはなりません。

RPGの一対一の戦闘で考えられうる状況のうち今回は以下の4つを考えます。

  1. 何と戦っているか
  2. 自分の残りHPはどのくらいか
  3. 自分の残りMPはどのくらいか
  4. 戦闘に勝利、敗北した

1は今回ゴブリン、ウィッチ、グリズリーの3パターンです。

残りHPや残りMPは単なる数字なのでその値一つ一つを異なる状況と考えてしまうと

連続値を扱えないQ-learningだと状況の数がかなり増えて計算に時間がかかってしまうので、ざっくり離散化します。

HPでは、残りHPが半分以上、残りHPが1/4以上、残りHPが1/4未満の3パターン。

MPでは、残りMPが半分以上ある、残りMPが半分未満だが0ではない、残りMP0の3パターンです。

1,2,3が戦闘中に考えられる状況です。

1,2,3それぞれ3パターンずつあって4が2パターンあるので今回考えられる状況は3*3*3+2=29通り存在します。

それぞれの状況でプレイヤーは選択できる行動を行います。つまりMPが切れていない状況では、

Playerクラスの関数SetActionsで追加した、通常攻撃、魔法攻撃、HP回復のうちどれかを実行することになります。

通常攻撃は相手に10ダメージ、魔法攻撃はMP10を使って相手に15ダメージ、回復はMP10を使って自分のHPを40回復します。

回復だけやけに数値が大きいのは、はじめ10でやってたんですけどQ-learningの結果全く使われない産廃と化していたので上げました。

次に報酬について説明します。

強化学習では、行った行動がいい行動だったのか悪い行動だったのかを判別する基準として報酬を用います。

つまり、行動の結果に点数を付けてあげます。

今回はRPGの戦闘なので、敵を倒したら1000点、負けたら-1000点といった超単純なものです。

HP,Mpがたくさんあって敵がゴブリンのときに通常攻撃して敵を倒せたらその組み合わせにプラスの評価がされるというわけです。

しかし、毎回行動を行った直後に効果が現れるとは限らないので、ある行動の評価を行うときはある程度未来までみてその間に得た報酬を参考にします。

つまり、HP,Mpがたくさんあって敵がゴブリンのときに通常攻撃を2回行ってから魔法攻撃をして敵を倒した場合、最後の魔法攻撃だけにいい評価を与えるのではなく、最初の通常攻撃にも意味があるだろうという考えです。

ある程度未来までみてその間に得た報酬のことを収益と言ってその期待値を行動価値Qといいます。

このへんは本や他のサイトのほうが詳しいので、それを見ることをあ勧めします。

Qは収益の期待値を表すので、ある状況、行動を行ったときのQの値がわかっていれば、選択できる行動の中でQの一番大きい行動を選んでおけば良いということがわかります。

そしてこのQを経験から計算するのがQ-learningです。

C#ではこんな感じ。

        public void updateQ(int situationNo, int nextSituation, int actionNo, double reward, List<int> unselectableActions = null, List<int> nextUnselectableActions = null)
        {
            int maxIndex = -1;
            double maxQ = -10000000;

            this.qValues[situationNo, actionNo] = (1 - this.alpha) * this.qValues[situationNo, actionNo]
                + this.alpha * (reward + this.gamma * serachMaxAndArgmax(nextSituation, ref maxIndex, ref maxQ, nextUnselectableActions));
        }

Qの値は状況、行動ごとに変わるので1度に更新するのは配列 this.qValues[situationNo, actionNo]の値1つです。

1回の戦闘で報酬が得られるタイミングは1回だけなので何回も何回も戦闘を行います。

1回の戦闘のことを1エピソードと呼びます。

        public override int MainProcess(int nEpisodes)
        {
            this.player = new Player();
            this.SetEneyList();

            var q = new QLearning(
                this.GetSituationSize(),
                this.GetActionSize(),
                0
            );
            int situationNo;
            int nextSituationNo;
            int e = 0;
            while (e < nEpisodes)
            {
                //this.enemy = this.SelectRandomEnemy();
                this.enemy = this.enemyList[e % 3];
                player.RestoreHp();
                player.RestoreMp();
                enemy.RestoreHp();
                enemy.RestoreMp();
                do
                {
                    situationNo = this.GetSituationNo();
                    nextSituationNo = -1;
                    var unselectable = this.GetUnselectableActions(situationNo);
                    int actionNo = q.SelectActionByEGreedy(0.05, situationNo, unselectable);

                    double reward = this.CalcActionResult(situationNo, ref nextSituationNo, actionNo);
                    var nextUnselectable = this.GetUnselectableActions(nextSituationNo);
                    q.updateQ(situationNo, nextSituationNo, actionNo, reward, unselectable, nextUnselectable);

                } while (nextSituationNo != ENEMY_DEATH && nextSituationNo != PLAYER_DEATH);

				if (e % 1000 == 0)
				{
					Console.WriteLine();
                    Console.Write(String.Format("Progress {0:f4}%", (double) 100 * e / nEpisodes));
					Console.WriteLine();
					this.PrintQValuesWithParams(q);
				}
				e++;
            }

            Console.WriteLine();
            this.PrintQValuesWithParams(q);

            return 0;
        }

while (e < nEpisodes)の中が1回の戦闘で、do-while文の中がプレイヤーと敵の攻撃の1ターンになります。

this.GetSituationNo()で現在の状況を確認し、q.SelectActionByEGreedyで状況とQをもとに行動を選択しています。

ここで、常に一番大きなQをもつ行動を選択するようにしてしまうと、たまたま良い結果が出たものを集中的に行って本当に良い行動を見落としてしまう可能性があるため小さい確率で一番大きなQをもつ行動以外を選択するようにします。

CalcActionResultで戦闘の処理と報酬の付与を行っています。

        public override double CalcActionResult(int situationNo, ref int nextSituation, int actionNo)
        {

            if (situationNo == PLAYER_DEATH)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            if (situationNo == ENEMY_DEATH)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }

            int playerHp = this.player.GetHp();
            int playerMp = this.player.GetMp();
			int playerMpOrg = playerMp;
            int enemyHp = this.enemy.GetHp();
            int enemyMp = this.enemy.GetMp();

            Action playerAction = this.player.GetActions()[actionNo];
            string playerAttackAttribute = playerAction.attribute;
            enemyHp -= (int)(playerAction.hpDamage * this.enemy.GetWeekness()[playerAttackAttribute]);
            playerHp += this.player.GetActions()[actionNo].hpHeal;
            if (playerHp > this.player.GetMaxHp())
                playerHp = this.player.GetMaxHp();
            playerMp -= this.player.GetActions()[actionNo].mpCost;
            if (enemyHp <= 0)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }
            Action enemyAction = this.SelectRandomAction(enemy);
            string enemyAttackAttribute = enemyAction.attribute;
            playerHp -= (int)(enemyAction.hpDamage * this.player.GetWeekness()[enemyAttackAttribute]);
            enemyHp += enemyAction.hpHeal;
            if (enemyHp > this.enemy.GetMaxHp())
                enemyHp = this.enemy.GetMaxHp();
            enemyMp -= enemyAction.mpCost;
            if (playerHp <= 0)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            this.player.SetHp(playerHp);
            this.player.SetMp(playerMp);
            this.enemy.SetHp(enemyHp);
            this.enemy.SetMp(enemyMp);


            nextSituation = this.GetSituationNo();

			return (playerMp - playerMpOrg) * MP_CONSUMPTION_REWARD_RATE;
        }

プレイヤーとモンスターのHP,MPを足したり引いたりしてHPが0になったら死亡判定してるだけです。

どちらかが死亡するとエピソードが終了します。

エピソードを行う数は予め決まっていてそれをすべて実行し終えると終了です。

Q-learningの実行結果

各モンスターに対して100万回戦闘しました。

普通にやったら何ヶ月かかるのかわからない処理ですがPCさんなら6分17秒でやってくれます。

対戦相手がゴブリンのときの結果がこれ。

ゴブリンは通常攻撃、魔法攻撃ともに等倍のダメージを受け、毎ターン通常攻撃しか行わないただの雑魚です。

少し見にくいが2行で1つのデータで、1行目は左から「対戦相手」、「HP状態」、[MP状態]を表す。、「HP状態」は0のとき半分以上1のとき1/4以上、2のときが1/4以下を表し、「MP状態」は0のとき半分以上1のとき0以上、2のときが0です。2行目は各行動の行動価値を表していて左から通常攻撃、魔法攻撃、回復です。

だから、上から2行目までは対戦相手がゴブリンのときでHP,MPが十分ある時は3つの行動のうち一番値の大きい魔法攻撃をするのが良いことになります。

BlogRainForest.Gobrin 2 0の行をみるとHPがかなり少なくてMPが十分ある時は回復するのが良いということがわかります。

次にウイッチの場合、ウイッチは裏で通常攻撃を効きやすく(2倍)、魔法攻撃を効きにくく(半分)しています。

結果では通常攻撃の行動価値が魔法攻撃の行動価値よりも常に大きくなっているのでウィッチ相手には通常攻撃と回復しか選択しないようなAIを作ることが出来ました。

まとめ

Q-learningを用いることで、簡単なゲームAIを作ることが出来ました。

Q-learningでは状態は離散値でしたが状況や行動を連続した値で表して計算を行う方法も存在するので、機会があったら解説しようと思います。

使用したプログラム

using System;
using System.Collections.Generic;


namespace BlogRainForest
{
    class Program
    {
        static void Main(string[] args)
		{
			var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            //var ql = new QLearning();
            var rb = new RpgBattle();
            rb.MainProcess(3000000);
			sw.Stop();
			TimeSpan ts = sw.Elapsed;
            Console.WriteLine($" {sw.ElapsedMilliseconds}ms");
            Console.Write("nEndn");
            Console.Read();
        }
    }


    public class QLearning
    {
        public double[,] qValues;
        public double alpha;
        public double gamma;

        public QLearning(int sSize, int aSize, int fillValue, double alpha = 0.01, double gamma = 0.8)
        {
            this.alpha = alpha;
            this.gamma = gamma;
            this.qValues = new double[sSize, aSize];
            for (int i = 0; i < sSize; i++)
            {
                for (int j = 0; j < aSize; j++)
                {
                    this.qValues[i, j] = fillValue;
                }
            }
        }

        public void updateQ(int situationNo, int nextSituation, int actionNo, double reward, List<int> unselectableActions = null, List<int> nextUnselectableActions = null)
        {
            int maxIndex = -1;
            double maxQ = -10000000;

            this.qValues[situationNo, actionNo] = (1 - this.alpha) * this.qValues[situationNo, actionNo]
                + this.alpha * (reward + this.gamma * serachMaxAndArgmax(nextSituation, ref maxIndex, ref maxQ, nextUnselectableActions));
        }

        public int SelectActionByGreedy(int situationNo, List<int> unselectableActions = null)
        {
            unselectableActions = unselectableActions ?? new List<int>();
            int maxIndex = -1;
            double maxQ = -10000000;
            this.serachMaxAndArgmax(situationNo, ref maxIndex, ref maxQ, unselectableActions);
            return maxIndex;
        }

        public int SelectActionByEGreedy(double epsilon, int situationNo, List<int> unselectableActions = null)
        {
            Random r = new Random();
            if (r.NextDouble() < epsilon)
            {
				int action = -1;
				do
				{
					action = r.Next(this.qValues.GetLength(1));
				} while (unselectableActions.Contains(action));
				return action;
            }
            else
            {
                return this.SelectActionByGreedy(situationNo, unselectableActions);
            }
        }

        private double serachMaxAndArgmax(int situationNo, ref int maxIndex, ref double maxQ, List<int> unselectableActions = null)
		{
            unselectableActions = unselectableActions ?? new List<int>();
            for (int j = 0; j < this.qValues.GetLength(1); j++)
            {
				
				if (unselectableActions.Contains(j))
				{
					continue;
				}
                if (this.qValues[situationNo, j] > maxQ)
                {
                    maxIndex = j;
                    maxQ = this.qValues[situationNo, j];
                }
            }
            
            return maxQ;
        }

        public void PrintQValues()
        {
            var rowCount = this.qValues.GetLength(0);
            var colCount = this.qValues.GetLength(1);
            for (int row = 0; row < rowCount; row++)
            {
                for (int col = 0; col < colCount; col++)
                    Console.Write(String.Format("{0}t", this.qValues[row, col]));
                Console.WriteLine();
            }
        }
    }


    public abstract class Task
    {
        public abstract int MainProcess(int nEpisodes);
        public abstract int GetSituationSize();
        public abstract int GetActionSize();
        public abstract List<int> GetUnselectableActions(int situation);
        public abstract double CalcActionResult(int situationNo, ref int nextSituation, int actionNo);
    }

    public class RpgBattle : Task
    {
        public const int PLAYER_DEATH = 27;
        public const int ENEMY_DEATH = 28;

        public const double PLAYER_DEATH_REWARD = -1000;
        public const double ENEMY_DEATH_REWARD = 1000;
		public const double MP_CONSUMPTION_REWARD_RATE = 0;

        public Character player;
        public Character enemy;
        public List<Character> enemyList;


        public override int MainProcess(int nEpisodes)
        {
            this.player = new Player();
            this.SetEneyList();

            var q = new QLearning(
                this.GetSituationSize(),
                this.GetActionSize(),
                0
            );
            int situationNo;
            int nextSituationNo;
            int e = 0;
            while (e < nEpisodes)
            {
                //this.enemy = this.SelectRandomEnemy();
                this.enemy = this.enemyList[e % 3];
                player.RestoreHp();
                player.RestoreMp();
                enemy.RestoreHp();
                enemy.RestoreMp();
                do
                {
                    situationNo = this.GetSituationNo();
                    nextSituationNo = -1;
                    var unselectable = this.GetUnselectableActions(situationNo);
                    int actionNo = q.SelectActionByEGreedy(0.05, situationNo, unselectable);

                    double reward = this.CalcActionResult(situationNo, ref nextSituationNo, actionNo);
                    var nextUnselectable = this.GetUnselectableActions(nextSituationNo);
                    q.updateQ(situationNo, nextSituationNo, actionNo, reward, unselectable, nextUnselectable);

                } while (nextSituationNo != ENEMY_DEATH && nextSituationNo != PLAYER_DEATH);

				if (e % 1000 == 0)
				{
					Console.WriteLine();
                    Console.Write(String.Format("Progress {0:f4}%", (double) 100 * e / nEpisodes));
					Console.WriteLine();
					this.PrintQValuesWithParams(q);
				}
				e++;
            }

            Console.WriteLine();
            this.PrintQValuesWithParams(q);

            return 0;
        }

        public void PrintQValuesWithParams(QLearning q)
        {
            var rowCount = q.qValues.GetLength(0);
            var colCount = q.qValues.GetLength(1);

            int charaId = -1;
            int hpSituation = -1;
            int mpSituation = -1;

            for (int row = 0; row < rowCount; row++)
            {
                if (row >= PLAYER_DEATH)
                    continue;
                this.GetParamsBySituationIndex(row, ref charaId, ref hpSituation, ref mpSituation);
                Console.Write(String.Format("{0}t{1}t{2}", this.enemyList[charaId - 1], hpSituation, mpSituation));
                Console.WriteLine();
                for (int col = 0; col < colCount; col++)
                    Console.Write(String.Format("{0}t", q.qValues[row, col]));
                Console.WriteLine();
            }
        }

        public override int GetSituationSize()
        {
            int enemyKindCount = 3;
            int hpSituationCount = 3;
            int mpSituationCount = 3;
            //自分死亡(PLAYER_DEATH)と相手死亡(ENEMY_DEATH)状態も足す
            return enemyKindCount * hpSituationCount * mpSituationCount + 2;
        }

        public int GetSituationNo()
        {
            return 9 * (this.enemy.GetId() - 1) + 3 * this.GetHpSituation() + this.GetMpSituation();
        }

        private int GetSituationIndexByParams(int charactterId, int hpSituation, int mpSituation)
        {
            return 9 * (charactterId - 1) + 3 * hpSituation + mpSituation;
        }

        private void GetParamsBySituationIndex(int situationId, ref int characterId, ref int hpSituation, ref int mpSituation)
        {
            characterId = situationId / 9;
            hpSituation = (situationId - 9 * characterId) / 3;
            mpSituation = situationId - 9 * characterId - 3 * hpSituation;
            ++characterId;
        }

        public override int GetActionSize()
        {
            return this.player.GetActions().Count;
        }

        public override List<int> GetUnselectableActions(int situation)
        {
            if (situation == PLAYER_DEATH)
				return new List<int>();
            if (situation == ENEMY_DEATH)
				return new List<int>();
            List<int> unselectableActions = new List<int>();

            foreach (KeyValuePair<int, Action> a in this.player.GetActions())
            {
                if (a.Value.mpCost > this.player.GetMp())
                    unselectableActions.Add(a.Value.id);
            }

            return unselectableActions;
        }

        public override double CalcActionResult(int situationNo, ref int nextSituation, int actionNo)
        {

            if (situationNo == PLAYER_DEATH)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            if (situationNo == ENEMY_DEATH)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }

            int playerHp = this.player.GetHp();
            int playerMp = this.player.GetMp();
			int playerMpOrg = playerMp;
            int enemyHp = this.enemy.GetHp();
            int enemyMp = this.enemy.GetMp();

            Action playerAction = this.player.GetActions()[actionNo];
            string playerAttackAttribute = playerAction.attribute;
            enemyHp -= (int)(playerAction.hpDamage * this.enemy.GetWeekness()[playerAttackAttribute]);
            playerHp += this.player.GetActions()[actionNo].hpHeal;
            if (playerHp > this.player.GetMaxHp())
                playerHp = this.player.GetMaxHp();
            playerMp -= this.player.GetActions()[actionNo].mpCost;
            if (enemyHp <= 0)
            {
                nextSituation = ENEMY_DEATH;
                return ENEMY_DEATH_REWARD;
            }
            Action enemyAction = this.SelectRandomAction(enemy);
            string enemyAttackAttribute = enemyAction.attribute;
            playerHp -= (int)(enemyAction.hpDamage * this.player.GetWeekness()[enemyAttackAttribute]);
            enemyHp += enemyAction.hpHeal;
            if (enemyHp > this.enemy.GetMaxHp())
                enemyHp = this.enemy.GetMaxHp();
            enemyMp -= enemyAction.mpCost;
            if (playerHp <= 0)
            {
                nextSituation = PLAYER_DEATH;
                return PLAYER_DEATH_REWARD;
            }
            this.player.SetHp(playerHp);
            this.player.SetMp(playerMp);
            this.enemy.SetHp(enemyHp);
            this.enemy.SetMp(enemyMp);


            nextSituation = this.GetSituationNo();

			return (playerMp - playerMpOrg) * MP_CONSUMPTION_REWARD_RATE;
        }

        public void SetEneyList()
        {
            this.enemyList = new List<Character>();
            this.enemyList.Add(new Goblin());
            this.enemyList.Add(new Witch());
            this.enemyList.Add(new Grizzly());
        }

        private Character SelectRandomEnemy()
        {
            Random rnd = new Random();
            int ri = rnd.Next(this.enemyList.Count);
            return this.enemyList[ri];
        }

        private Action SelectRandomAction(Character character)
        {
            Random rnd = new Random();
            List<int> KeyList = new List<int>(character.GetActions().Keys);
            int ri = rnd.Next(KeyList.Count);
            return character.GetActions()[KeyList[ri]];
        }

        private int GetHpSituation()
        {
            if (this.player.GetMaxHp() / 2 < this.player.GetHp())
            {
                return 0;
            }
            else if (this.player.GetMaxHp() / 4 < this.player.GetHp())
            {
                return 1;
            }
            else
            {
                return 2;
            }
        }

        private int GetMpSituation()
        {
            if (this.player.GetMaxMp() / 2 < this.player.GetMp())
            {
                return 0;
            }
            else if (10 <= this.player.GetMp())
            //else if (this.player.GetMaxMp() / 4 < this.player.GetMp())
            {
                return 1;
            }
            else
            {
                return 2;
            }
        }
    }


    public abstract class Character
    {
        private string name;
        private int id;
        private int maxHp;
        private int maxMp;
        private int hp;
        private int mp;
        private Dictionary<int, Action> actions;
        private Dictionary<string, double> weeknesses;

        public Character()
        {
            this.Init();
        }

        private void Init()
        {
            this.name = this.SetName();
            this.id = this.SetId();
            this.maxHp = this.SetMaxHp();
            this.maxMp = this.SetMaxMp();
            this.hp = this.maxHp;
            this.mp = this.maxMp;
            this.actions = this.SetActions();
            this.weeknesses = this.SetWeekness();
        }

        private string SetName()
        {
            return this.GetType().Name;
        }

        public abstract int SetId();
        public abstract int SetMaxHp();
        public abstract int SetMaxMp();

        public void SetHp(int hp)
        {
            this.hp = hp;
        }

        public void SetMp(int mp)
        {
            this.mp = mp;
        }

        public abstract Dictionary<int, Action> SetActions();
        public abstract Dictionary<string, double> SetWeekness();

        public string GetName()
        {
            return this.name;
        }

        public int GetId()
        {
            return this.id;
        }

        public int GetHp()
        {
            return this.hp;
        }

        public int GetMp()
        {
            return this.mp;
        }


        public int GetMaxHp()
        {
            return this.maxHp;
        }

        public int GetMaxMp()
        {
            return this.maxMp;
        }

        public Dictionary<int, Action> GetActions()
        {
            return this.actions;
        }

        public Dictionary<string, double> GetWeekness()
        {
            return this.weeknesses;
        }

        public void RestoreHp()
        {
            this.hp = this.maxHp;
        }

        public void RestoreMp()
        {
            this.mp = this.maxMp;
        }

    }

    public class Player : Character
    {
        public Player() : base()
        {

        }

        public override int SetId()
        {
            return 0;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 100;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

    public class Goblin : Character
    {
        public Goblin() : base()
        {

        }

        public override int SetId()
        {
            return 1;
        }

        public override int SetMaxHp()
        {
            return 140;
        }

        public override int SetMaxMp()
        {
            return 0;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 1.0);
            return weeknesses;
        }
    }

    public class Witch : Character
    {
        public Witch() : base()
        {

        }

        public override int SetId()
        {
            return 2;
        }

        public override int SetMaxHp()
        {
            return 100;
        }

        public override int SetMaxMp()
        {
            return 200;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.magicAttack.id, ActionTable.magicAttack);
            actions.Add(ActionTable.heal.id, ActionTable.heal);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 2.0);
            weeknesses.Add("magic", 0.5);
            return weeknesses;
        }
    }

    public class Grizzly : Character
    {
        public Grizzly() : base()
        {

        }

        public override int SetId()
        {
            return 3;
        }

        public override int SetMaxHp()
        {
            return 240;
        }

        public override int SetMaxMp()
        {
            return 0;
        }

        public override Dictionary<int, Action> SetActions()
        {
            var actions = new Dictionary<int, Action>();
            actions.Add(ActionTable.normalAttack.id, ActionTable.normalAttack);
            actions.Add(ActionTable.strongAttack.id, ActionTable.strongAttack);
            return actions;
        }

        public override Dictionary<string, double> SetWeekness()
        {
            var weeknesses = new Dictionary<string, double>();
            weeknesses.Add("physical", 1.0);
            weeknesses.Add("magic", 2.0);
            return weeknesses;
        }
    }

    public class Action
    {
        public int id;
        public int hpDamage;
        public int hpHeal;
        public int mpCost;
        public string attribute;

        public Action(int id, int hpDamage, int hpHeal, int mpCost, string attribute, ref int count)
        {
            this.id = id;
            this.hpDamage = hpDamage;
            this.hpHeal = hpHeal;
            this.mpCost = mpCost;
            this.attribute = attribute;
            ++count;
        }
    }

    static class ActionTable
    {
        public static int count;
        public static Action normalAttack;
        public static Action magicAttack;
        public static Action heal;
        public static Action strongAttack;

        static ActionTable()
        {
            count = 0;
            normalAttack = new Action(count, 10, 0, 0, "physical", ref count);
            magicAttack = new Action(count, 15, 0, 10, "magic", ref count);
            heal = new Action(count, 0, 40, 10, "magic", ref count);
            strongAttack = new Action(count, 30, 0, 0, "physical", ref count);
        }
    }
}