MTGの簡単なデッキでのゲームの全探索を行うコードを書いてみた - プレイヤー２人は全知全能の完全情報ゲームとしても常識的な時間で探索が終わらなかった -

　C#でMTGのゲームプレイの木探索を行うコードを書いてみたが意外と難しく、完成とは程遠いが意見等を頂けるとありがたいので途中経過を公開しようと思う。
　複雑なスペルや特殊なデッキを考えるとキリがなく、できるだけ単純なゲームから考えていきたいし、ソフトの雛形作りの意味もあるので簡単にしたいので、まずはその基本であるお互いバニラクリーチャーと土地だけのデッキの場合のシミュレーションを行うことにする。さらに面倒を省くために、プレイヤーはお互いのデッキの内容を知っていて除去とかバットリとかは飛んでこないことを知っているとする。するとプレイヤーはマナ効率だけを考えて漫然とクリーチャーをプレイすることになる。
　まずはお互いのプレイヤーがハンド・お互いの未来のドローを知っている状態（完全情報ゲーム）としてMin-Max法で全探索を行うコードを書いてみた。デッキはクリーチャーと土地のみでプレイヤーの選択肢はアタックとブロックのみで、カードのプレイは手なりに行うものとした。デッキ枚数は40枚とした。デッキのバランスをいじることで、適切なマナカーブや土地配分がわかるかと考えていたが、計算にかなり時間がかかるようで、３時間ほど動かしてみても１ゲームが終わらなかった。計算時間の見積もりもできてないし、無駄な探索が多いのも明らかである。
　次は無駄な探索を削ること、計算の進捗状況を知ることをやっていこうと思う。プログラムに詳しい人からこうしたらコードが読みやすくなるよとか、早くなるよとか教えて頂けるとありがたいです。

動作の概要

　**メイン関数

using System;
using GameSimulator.探索;

namespace GameSimulator {
    static class Program {
        [STAThread]
        static void Main() {         
            Player player1 = new Player(6); //先手ハンド６で初期化
            Player player2 = new Player(7);//後手ハンド7で初期化

            SecondMainPhaseNode node = new SecondMainPhaseNode();
            node.MyPlayer = player1;
            node.OppPlayer = player2;
            node.IsMaxPlayer = true;    //先手をmaxプレイヤーと指定
            var result = node.Eval();   //探索開始
           Console.WriteLine(result.WinningRate);
        
           var x =  Console.ReadLine();
        }
    }
}

評価

将来的には状況からの評価を行いたいが、今回は全探索を行うので、勝つ負けるの２値で扱っていて、WinningRagteにはMin()の値かMax()の値か0(引き分け）が入る

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GameSimulator {
    class Evaluation {
        #region プロパティ

        public int WinningRate { get; set; }
        #endregion

        #region コンストラクタ
        public Evaluation() {

        }
        public Evaluation(Evaluation ev) {

        }
        #endregion

        #region Static
        public static Evaluation Min() {
            var val = new Evaluation();
            val.WinningRate = int.MinValue;
            return val;
        }
        public static Evaluation Max() {
            var val = new Evaluation();
            val.WinningRate = int.MaxValue;
            return val;
        }
        #endregion
    }
}

カードをクラス化したもの

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.ObjectModel;
using System.Collections.Specialized;

namespace GameSimulator {
    public enum CardType { None, Creature, Land };
    public class Creature : Card {
        public Creature()
            : base(CardType.Creature) {
        }
        public Creature(int P, int T)
            : base(CardType.Creature) {
            Power = P;
            Toughness = T;
        }
        public Creature(int P, int T, int cost)
            : base(CardType.Creature, cost) {
            Power = P;
            Toughness = T;
        }

        private int _Power;
        private int _Toughness;


        public int Power {
            get { return _Power; }
            set { _Power = value; }
        }

        public int Toughness {
            get { return _Toughness; }
            set { _Toughness = value; }
        }
        public bool Taped {
            get;
            set;
        }

        public override string ToString() {
            return Power + "/" + Toughness;
        }
    }

    public class Land : Card {

        public Land()
            : base(CardType.Land) {
        }
    }

    public class Card {
        #region フィールド
        private CardType _Type;
        private int _Cost;
        #endregion

        #region プロパティ
        public int Cost {
            get { return _Cost; }
            private set { _Cost = value; }
        }
        public CardType Type {
            get { return _Type; }
            private set { _Type = value; }
        }
        #endregion
        #region コンストラクタ
        public Card() {
            Type = CardType.None;
            Cost = 0;
        }
        public Card(CardType type) {
            Type = type;
        }
        public Card(CardType type, int cost) {
            Type = type;
            Cost = cost;
        }
        #endregion

        public override string ToString() {
            return "Land";
        }

    }
}

　**場・ハンド・ライフの情報保持
場のクリーチャーやハンドを管理する。カードのプレイはPlay(card)を通して行う。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.ObjectModel;

namespace GameSimulator {
    public class Player {
        #region フィールド

        private Dictionary<Creature, bool> _CreatureIsTaped = new Dictionary<Creature, bool>();
        private List<Land> _Lands = new List<Land>();
        private List<Card> _Deck = new List<Card>();
        private List<Card> _Hand = new List<Card>();
        private int _Life = 20;
        private Player _Opponent;
        #endregion
        #region プロパティ
        public int Life {
            get { return _Life; }
            set { _Life = value; }
        }

        public List<Card> Hand {
            get { return _Hand; }
            set { _Hand = value; }
        }

        public List<Card> Deck {
            get { return _Deck; }
            set { _Deck = value; }
        }

        public List<Land> Lands {
            get { return _Lands; }
            set { _Lands = value; }
        }

        public Dictionary<Creature, bool> CreatureIsTaped {
            get { return _CreatureIsTaped; }
            set { _CreatureIsTaped = value; }
        }
        public ReadOnlyCollection<Creature> GetCreatures() {
            return new ReadOnlyCollection<Creature>(_CreatureIsTaped.Select(x => x.Key).ToList());
        }
        public IEnumerable<Creature> GetCreaturesIE() {
            return CreatureIsTaped.Select(x => x.Key);
        }
        public Player Opponent {
            get { return _Opponent; }
            set { _Opponent = value; }
        }

        #endregion

        #region コンストラクタ
        public Player() {
            Init();
        }
        public Player(List<Creature> creatures, List<Card> deck, List<Card> hand, List<Land> land) {
            Init();
            Deck = deck.ToList();
            Hand = hand.ToList();
            Lands = land.ToList();
        }
        public void Init() {
            Init(7);
        }
        public void Init(int handNum) {
            for (int i = 0; i < 17; i++) {
                Deck.Add(new Land());
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(2, 2, 2));
            }
            for (int i = 0; i < 6; i++) {
                Deck.Add(new Creature(3, 3, 3));
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(4, 4, 4));
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(5, 5, 5));
            }
            for (int i = 0; i < 2; i++) {
                Deck.Add(new Creature(6, 6, 6));
            }

            Deck = Deck.OrderBy(x => Guid.NewGuid()).ToList();  //シャッフル
            Hand = new List<Card>();
            for (int i = 0; i < handNum; i++) {
                DrawACard();
            }
        }
        public Player(Player pl) {
            this.CreatureIsTaped = new Dictionary<Creature, bool>(pl.CreatureIsTaped);
            this.Lands = new List<Land>(pl.Lands);
            this.Deck = new List<Card>(pl.Deck);
            this.Hand = new List<Card>(pl.Hand);

        }
        public Player(int handNum) {
            Init(handNum);
        }
        #endregion

       

        //カードを引く
        public void DrawACard() {
            if (Deck.Count != 0) {

                Hand.Add(Deck[0]);
                Deck.RemoveAt(0);
            }
            else {
                throw new Exception();
            }
        }

        //カードをハンドから場に出す
        void Play(Card card) {
            if (card.Type == CardType.Creature) {
                PlayCreature((Creature)card);
            }
            else if (card.Type == CardType.Land) {
                PlayLand((Land)card);
            }

        }
        void PlayCreature(Creature card) {
            Hand.Remove(card);
            CreatureIsTaped.Add(card, false);
        }
        void PlayLand(Land land) {
            Hand.Remove(land);
            this.Lands.Add(land);
        }
        //出せる場合ランドをプレイする
        void PlayLandAuto() {
            var land = Hand.FirstOrDefault(x => x.Type == CardType.Land);
            if (land != null) {
                this.Play(land);
            }
        }
        //スペルプレイのアルゴリズム
        void PlaySpellAuto() {
            //プレイ可能なマナ数で初期化
            int mana = Lands.Count;
            //プレイ可能なカードで最大コストのカードからプレイ
            var query = from x in Hand where (x.Cost <= mana) && (x.Type != CardType.Land) orderby -x.Cost select x;
            foreach (var x in query) {
                if (x.Cost <= mana) {
                    Play(x);
                    mana -= x.Cost;
                }
            }
        }
        public void SecondMainPlay() {
            UntapAll();
            PlayLandAuto();
            PlaySpellAuto();
        }
        public void UntapAll() {
            var list = CreatureIsTaped.Select(x => x.Key).ToList();
            foreach (var x in list) {
                CreatureIsTaped[x] = false;
            }
        }
        public void TapCreatures(List<Creature> cre) {
            foreach (var x in cre) {
                CreatureIsTaped[x] = true;
            }
        }
        #region プライベート
        int Pow(int x, int y) {
            int val = 1;
            for (int i = 0; i < y; i++) {
                val *= x;
            }
            return val;
        }
        #endregion

    }
}

探索

　Nodeクラスがが枝分かれして探索する。NodeクラスはメンバとしてListクラスのNextListを保持し、Eval()関数でこれらのノードから最大あるいは最小の評価結果を返す。最大を返すか最小の結果を返すかはプレイヤーがMaxプレイヤーかMinプレイヤーかによって決め、IsMaxPlayerの値によってきまる。
NodeはAttakerNode, BlockerNode, MainPhaseNodeに継承され、AttakerNodeのNextListにはBlockerNodeが入り、BlockerNodeのNextListにはMainPhaseNodeが入り、MainPhaseNodeのNextListにはAttakerNodeが入り、これら３つを順にめぐる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GameSimulator.探索 {

    class Node {
        #region フィールド

        Evaluation _Evaluation = null;
        private Player _MyPlayer;
        private Player _OppPlayer;
        private List<Node> _NextList = null;
        private Node _Previous = null;
        #endregion
        #region プロパティ

        public Evaluation CurrentEvaluation {
            get { return _Evaluation; }
            set { _Evaluation = value; }
        }
        public Player MaxPlayer {
            get {
                if (IsMaxPlayer) {
                    return _MyPlayer;
                }
                else {
                    return _OppPlayer;
                }
            }
        }
        public Player MinPlayer {
            get {
                if (IsMaxPlayer) {
                    return _OppPlayer;
                }
                else {
                    return _MyPlayer;
                }
            }
        }
        public Player MyPlayer {
            get { return _MyPlayer; }
            set { _MyPlayer = value; }
        }
        public Player OppPlayer {
            get { return _OppPlayer; }
            set { _OppPlayer = value; }
        }
        public bool IsMaxPlayer { get; set; }
        public List<Node> NextList {
            get { return _NextList; }
            set { _NextList = value; }
        }
        public Node SelectedNode { get; set; }


        public Node Privious {
            get { return _Previous; }
            set { _Previous = value; }
        }
        
        #endregion

        #region コンストラクタ
        public Node() { }
        public Node(Node node) {
            this.CurrentEvaluation = new Evaluation(node.CurrentEvaluation);
            this.MyPlayer = new Player(node.MyPlayer);
            this.OppPlayer = new Player(node.OppPlayer);
            this.IsMaxPlayer = node.IsMaxPlayer;
        }
        #endregion

        #region 公開関数
        public virtual Evaluation Eval() {
            if (NextList == null) {
                CreateNextNodeList();
            }
            if (CurrentEvaluation == null) {
                if (NextList.Count == 0) {
                    return CurrentEvaluation;
                }
                CurrentEvaluation = SelectNode().Eval();
            }
            return CurrentEvaluation;
        }

        public virtual Node SelectNode() {
            if (NextList.Count == 0) {
                return null;
            }
            Node node = null;
            if (IsMaxPlayer) {
                int evl = int.MinValue;
                foreach (var x in NextList) {
                    if (evl <= x.Eval().WinningRate) {
                        evl = x.Eval().WinningRate;
                        node = x;
                    }
                }
            }
            else {
                int evl = int.MaxValue;
                foreach (var x in NextList) {
                    if (evl >= x.Eval().WinningRate) {
                        evl = x.Eval().WinningRate;
                        node = x;
                    }
                }
            }
            return node;
        }
        public virtual void CreateNextNodeList() {

        }
        #endregion
    }
    class SecondMainPhaseNode : Node {
        #region コンストラクタ

        public SecondMainPhaseNode() {

        }
        public SecondMainPhaseNode(Node node)
            : base(node) {

        }
        #endregion
        public override void CreateNextNodeList() {
            this.NextList = new List<Node>();
            Player my = new Player(MyPlayer);
            Player opp = new Player(OppPlayer);
            my.DrawACard();
            my.SecondMainPlay();
            if(8 <my.CreatureIsTaped.Count
                && 8 < opp.CreatureIsTaped.Count) {
                    CurrentEvaluation = new Evaluation();
                    CurrentEvaluation.WinningRate = 0;
                    return; //クリーチャーの数がどちらも８超えたら引き分け
            }
            else if (my.Deck.Count < 10) {
                CurrentEvaluation = new Evaluation();
                CurrentEvaluation.WinningRate = 0;  // デッキ枚数が10きったら引き分け
            }
            AttakerNode node = new AttakerNode();
            node.MyPlayer = opp;
            node.OppPlayer = my;
            node.IsMaxPlayer = !this.IsMaxPlayer;
            node.Privious = this;
            this.NextList.Add(node);
        }
    }
    class BlockerNode : Node {
        #region プロパティ
        public List<Creature> Attackers { get; set; }
        Dictionary<Node, Dictionary<Creature, Creature>> Blockers { get; set; }  //keyブロッカー　val アタッカーor null
        #endregion
        #region コンストラクタ
        public BlockerNode()
            : base() {
        }
        public BlockerNode(List<Creature> attackers) {
            Attackers = attackers;
        }

        #endregion

        public override void CreateNextNodeList() {
            var cre = MyPlayer.GetCreatures().Where(x => !x.Taped).ToList();
            Dictionary<Creature, Creature> noBlock = new Dictionary<Creature, Creature>();
            foreach (var x in cre) {
                noBlock.Add(x, null);
            }
            List<Dictionary<Creature, Creature>> blkList = new List<Dictionary<Creature, Creature>>();
            blkList.Add(noBlock);
            foreach (var x in cre) {
                var add = new List<Dictionary<Creature, Creature>>();
                foreach (var y in blkList) {
                    foreach (var sel in Attackers) {
                        var blk = new Dictionary<Creature, Creature>(y);
                        blk[x] = sel;
                        add.Add(blk);
                    }
                }
                blkList.AddRange(add);
            }
            NextList = new List<Node>();
            foreach (var x in blkList) {
                var val = SolveCombat(x);
                if (val != null) {
                    NextList.Add(val);
                }
                else {
                    if (IsMaxPlayer) {
                        CurrentEvaluation = Evaluation.Min();
                    }
                    else {
                        CurrentEvaluation = Evaluation.Max();
                    }
                }

            }
        }

        //ダメージ割り振り解決
        private SecondMainPhaseNode SolveCombat(Dictionary<Creature, Creature> block) {
            SecondMainPhaseNode newNode = new SecondMainPhaseNode();
            newNode.MyPlayer = new Player(this.OppPlayer);
            newNode.OppPlayer = new Player(this.MyPlayer);
            newNode.IsMaxPlayer = !this.IsMaxPlayer;
            newNode.Privious = this;
            foreach (var atk in Attackers) {
                var blks = block.Where(x => x.Value == atk).Select(x => x.Key);
                if (blks == null) {
                    newNode.OppPlayer.Life -= atk.Power; //ブロックされていなければダメージが入る
                    if (newNode.OppPlayer.Life <= 0) {   //死判定
                        return null;
                    }
                }
                else {
                    int rest = atk.Power;
                    var b = blks.OrderBy(x => -x.Power);
                    foreach (var blk in b) {    //パワーの大きいブロッカーからダメージを割り振る
                        if (blk.Power <= rest) {
                            rest -= blk.Power;
                            newNode.OppPlayer.CreatureIsTaped.Remove(blk);
                        }
                    }
                    if (atk.Power <= blks.Sum(x => x.Power)) {
                        OppPlayer.CreatureIsTaped.Remove(atk);  // アタッカーの死判定
                    }
                }
            }
            return newNode;
        }
    }

    class AttakerNode : Node {
        public override void CreateNextNodeList() {
            var creatures = MyPlayer.GetCreatures();
            //0
            //1
            //01
            //11
            //001
            //101
            //011
            //111とふえていく
            List<List<Creature>> attacker = new List<List<Creature>>();
            attacker.Add(new List<Creature>());
            foreach (var x in creatures) {
                List<List<Creature>> add = new List<List<Creature>>();
                foreach (var y in attacker) {
                    var atk = y.ToList();
                    atk.Add(x);
                    add.Add(atk);
                }
                attacker.AddRange(add);
            }

            NextList = new List<Node>();
            foreach (var x in attacker) {
                BlockerNode node = new BlockerNode(x);
                node.MyPlayer = new Player( this.OppPlayer);
                node.OppPlayer = new Player(this.MyPlayer);
                node.OppPlayer.TapCreatures(x);
                node.IsMaxPlayer = !this.IsMaxPlayer;
                node.Privious = this;
                NextList.Add(node);
            }
        }
    }
}