Cマガ電脳クラブ(第118回) ウサギと犬

問題

Figのような盤と十円玉3個，百円玉1個を使ってふたりで遊ぶゲームを紹介する。
遊び方は以下の通り。

 (1)図のH，K，Jに十円玉を1個ずつ置き，猟犬とする
 (2)百円玉はウサギで，猟犬のいないところならどこに置いてもよい
 (3)先手は猟犬
 (4)線に沿って隣が空いていればその○に，猟犬のうちの1匹が移動する。
    ただし、バックはできない(たとえば図のFからB，C，D，E，Gには行けるが，H，I，Jには行けない)
 (5)ウサギも隣が空いていれば線に沿って移動する。方向は自由
 (6)以下(4)と(5)を交互に続ける

最終的にウサギを動けなくしたら猟犬の勝ち，
猟犬の包囲網を通り抜けたら(犬はバックができないのだからウサギが犬のうしろに回り込めば)ウサギの勝ちである。
なお，千日手(同じ場面の繰り返し)になった場合は猟犬側にその解消義務がある。

さてこのゲーム，実は猟犬側に必勝法がある。猟犬をコンピュータが担当し，
人と対戦する必勝プログラムを作ってほしい。対戦の表示方法はご自由にどうぞ。

    Fig. ウサギと犬
    　　Ａ
    　／│＼
    Ｂ─Ｃ─Ｄ
    │＼│／│
    Ｅ─Ｆ─Ｇ
    │／│＼│
    Ｈ─Ｉ─Ｊ
    　＼│／
    　　Ｋ

ソース

using System;
using System.Collections.Generic;
using System.Linq;

//UI部分
partial class Program
{
    static char[,] mBanArr;
    static int mLevel;
    static bool mHasSyouhai;
    static Dictionary<int, int> mVisitedInuHashCntDict = new Dictionary<int, int>();

    //1ゲームを行う
    static void ExecGame()
    {
        mBanArr = InitBanArr('X');
        mLevel = 0;
        mHasSyouhai = false;
        mVisitedInuHashCntDict.Clear();

        while (true) {
            InputHitoItte(false);
            if (mHasSyouhai) break;
            mLevel++;

            bool HasBug;
            ExecComItte(out HasBug);
            if (HasBug) return;
            if (mHasSyouhai) break;
            mLevel++;
        }
        Console.WriteLine("ウサギの負けです");
        Console.WriteLine("□□□□□□□□□□□□□□□□□□□□□□□□□");
    }

    //人の1手を入力
    static void InputHitoItte(bool pIsRetry)
    {
        if (pIsRetry == false) {
            if (mLevel == 0) {
                PrintBan(mBanArr);
                Console.Write("ウサギの配置場所を入力して下さい ");
            }
            else Console.Write("ウサギの移動先を入力して下さい ");
        }
        string wkStr = Console.ReadLine().ToUpper();
        if (wkStr.Length != 1) {
            Console.Write("入力エラーです。再入力して下さい ");
            InputHitoItte(true); return;
        }
        char wkChar = wkStr[0];
        if (wkChar < 'A' || 'J' < wkChar) {
            Console.Write("入力エラーです。再入力して下さい ");
            InputHitoItte(true); return;
        }
        if (mLevel >= 2 && CanMoveUsagi(wkChar) == false) {
            Console.Write("移動不可です。再入力して下さい ");
            InputHitoItte(true); return;
        }
        ExecHitoItte(wkChar);
    }

    //指定した座標にウサギが移動可能かを返す
    static bool CanMoveUsagi(char pNewPos)
    {
        char CurrUsagiPos = DeriveCurrUsagiPos();

        if (pNewPos == 'A') {
            if (mBanArr[1, 0] != ' ') return false;
            return "BCD".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'B') {
            if (mBanArr[0, 1] != ' ') return false;
            return "ACEF".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'C') {
            if (mBanArr[1, 1] != ' ') return false;
            return "ABDF".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'D') {
            if (mBanArr[2, 1] != ' ') return false;
            return "ACFG".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'E') {
            if (mBanArr[0, 2] != ' ') return false;
            return "BFH".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'F') {
            if (mBanArr[1, 2] != ' ') return false;
            return "BCDEGHIJ".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'G') {
            if (mBanArr[2, 2] != ' ') return false;
            return "DFJ".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'H') {
            if (mBanArr[0, 3] != ' ') return false;
            return "EFIK".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'I') {
            if (mBanArr[1, 3] != ' ') return false;
            return "FHJK".Contains(CurrUsagiPos);
        }
        if (pNewPos == 'J') {
            if (mBanArr[2, 3] != ' ') return false;
            return "FGIK".Contains(CurrUsagiPos);
        }
        return false;
    }

    //現在のウサギの座標をCharで返す
    static char DeriveCurrUsagiPos()
    {
        if (mBanArr[1, 0] == 'ウ') return 'A';
        if (mBanArr[0, 1] == 'ウ') return 'B';
        if (mBanArr[1, 1] == 'ウ') return 'C';
        if (mBanArr[2, 1] == 'ウ') return 'D';
        if (mBanArr[0, 2] == 'ウ') return 'E';
        if (mBanArr[1, 2] == 'ウ') return 'F';
        if (mBanArr[2, 2] == 'ウ') return 'G';
        if (mBanArr[0, 3] == 'ウ') return 'H';
        if (mBanArr[1, 3] == 'ウ') return 'I';
        if (mBanArr[2, 3] == 'ウ') return 'J';
        return 'K';
    }

    //人の1手を指して、メッセージ表示
    static void ExecHitoItte(char pChar)
    {
        if (mLevel == 0) {
            mBanArr = InitBanArr(pChar);
        }
        else {
            for (int X = 0; X <= UB_X; X++) {
                for (int Y = 0; Y <= UB_Y; Y++) {
                    if (mBanArr[X, Y] == 'ウ')
                        mBanArr[X, Y] = ' ';
                }
            }
            if (pChar == 'A') mBanArr[1, 0] = 'ウ';
            if (pChar == 'B') mBanArr[0, 1] = 'ウ';
            if (pChar == 'C') mBanArr[1, 1] = 'ウ';
            if (pChar == 'D') mBanArr[2, 1] = 'ウ';
            if (pChar == 'E') mBanArr[0, 2] = 'ウ';
            if (pChar == 'F') mBanArr[1, 2] = 'ウ';
            if (pChar == 'G') mBanArr[2, 2] = 'ウ';
            if (pChar == 'H') mBanArr[0, 3] = 'ウ';
            if (pChar == 'I') mBanArr[1, 3] = 'ウ';
            if (pChar == 'J') mBanArr[2, 3] = 'ウ';
        }

        SyouhaiHantei();
        JyoukyouHyouji();
    }

    //COMが手を指す
    static void ExecComItte(out bool pHasBug)
    {
        pHasBug = false;

        //遷移可能な盤面を列挙
        List<char[,]> CanSeniBanArrList = DeriveCanSeniBanArrList(mBanArr, false);

        //犬勝ちのHash値(179742,198558,323676)が最優先で、
        //次に、訪問回数の少ないノードを優先する。
        IEnumerable<char[,]> CanSeniBanArrEnum = CanSeniBanArrList
            .OrderByDescending(A => GetHash(1, A) == 179742)
            .ThenByDescending(A => GetHash(1, A) == 198558)
            .ThenByDescending(A => GetHash(1, A) == 323676)
            .ThenBy(A => mVisitedInuHashCntDict.ContainsKey(GetHash(1, A)) ?
                         mVisitedInuHashCntDict[GetHash(1, A)] : 0);

        bool FoundNode = false;
        foreach (char[,] EachCanSeniBanArr in CanSeniBanArrEnum) {
            int wkHash = GetHash(1, EachCanSeniBanArr);

            int wkInd = mHashIndDict[wkHash];
            if (mNodeInfoArr[wkInd].Syouhai == 1) {
                if (mVisitedInuHashCntDict.ContainsKey(wkHash)) {
                    mVisitedInuHashCntDict[wkHash]++;
                }
                else mVisitedInuHashCntDict[wkHash] = 1;
                mBanArr = EachCanSeniBanArr;
                FoundNode = true;
                break;
            }
        }
        if (FoundNode == false) {
            Console.WriteLine("バグってます！！！");
            Console.WriteLine("犬勝の手が存在しません");
            pHasBug = true;
            return;
        }
        SyouhaiHantei();
        JyoukyouHyouji();
    }

    //状況を表示
    static void JyoukyouHyouji()
    {
        var sb = new System.Text.StringBuilder();
        if (mLevel % 2 == 0) {
            sb.AppendLine("□□□□□□□□□□□□□□□□□□□□□□□□□");
        }
        else {
            sb.AppendLine("■■■■■■■■■■■■■■■■■■■■■■■■■");
        }

        int Teban = ((mLevel % 2 == 1) ? 1 : 2);
        sb.AppendFormat("現在の手数={0}。Hash={1}。", mLevel, GetHash(Teban, mBanArr));
        sb.Append((mLevel % 2 == 0) ? "犬の手番。" : "ウサギの手番。");
        sb.AppendLine();
        Console.WriteLine(sb.ToString());
        PrintBan(mBanArr);
    }

    //勝敗が決定しているかを判定
    static void SyouhaiHantei()
    {
        mHasSyouhai = (DeriveSyouhai(mBanArr) == 1);
    }
}

//ロジック部分
partial class Program
{
    const int UB_X = 3 - 1;
    const int UB_Y = 5 - 1;

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static void Main()
    {
        //初期処理
        InitSyori();

        while (true) {
            ExecGame();
        }
    }

    //初期処理
    static void InitSyori()
    {
        Console.WriteLine("遷移可能な盤面を列挙します。");
        ExecUnionFind();
        Console.WriteLine("遷移可能な盤面は{0}通り。", mNodeInfoArr.Length);

        //mNodeInfoArrの添字[Hash値]のDictを作成
        CreateHashIndDict();

        //全ノードの勝敗を求める
        DeriveAllSyouhai();
    }

    struct NodeInfoDef
    {
        internal int Teban;
        internal char[,] BanArr;
        internal int Hash; //手番と盤面のハッシュ値
        internal List<int> KoHashList; //子ノードのハッシュ値のリスト
        internal int Syouhai; //勝敗 (未決定は0、先手勝は1、後手勝は2)
    }
    static NodeInfoDef[] mNodeInfoArr;

    //遷移可能な手番と盤面の組み合わせをUnionFindで列挙
    static void ExecUnionFind()
    {
        var NodeInfoList = new List<NodeInfoDef>();

        var Stk = new Stack<NodeInfoDef>();
        NodeInfoDef WillPush;

        foreach (char EachUsagiPos in "ABCDEFGI") {
            WillPush.Teban = 2;
            WillPush.BanArr = InitBanArr(EachUsagiPos);
            WillPush.Hash = GetHash(WillPush.Teban, WillPush.BanArr);
            WillPush.KoHashList = new List<int>();
            WillPush.Syouhai = 0;
            NodeInfoList.Add(WillPush);
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            NodeInfoDef Popped = Stk.Pop();
            WillPush.Teban = (Popped.Teban == 1 ? 2 : 1);

            var JyoutaiList = new List<NodeInfoDef>();

            //勝ちになる手があるか？
            bool HasKatite = false;

            //遷移可能な盤面を列挙
            List<char[,]> CanSeniBanArrList;
            if (WillPush.Teban == 1)  //犬の手番の場合
                CanSeniBanArrList = DeriveCanSeniBanArrList(Popped.BanArr, false);
            else //ウサギの手番の場合
                CanSeniBanArrList = DeriveCanSeniBanArrList(Popped.BanArr, true);

            foreach (char[,] EachBanArr in CanSeniBanArrList) {
                WillPush.BanArr = EachBanArr;
                WillPush.Hash = GetHash(WillPush.Teban, WillPush.BanArr);
                WillPush.KoHashList = new List<int>();
                WillPush.Syouhai = 0;
                WillPush.Syouhai = DeriveSyouhai(WillPush.BanArr);

                //勝ちになる手があったら、その手で確定
                if (WillPush.Syouhai == WillPush.Teban) {
                    HasKatite = true;
                    Popped.KoHashList.Add(WillPush.Hash);

                    //訪問済ノードならAddしない
                    if (NodeInfoList.Exists(A => A.Hash == WillPush.Hash) == false)
                        NodeInfoList.Add(WillPush);

                    break;
                }
                JyoutaiList.Add(WillPush);
            }

            if (HasKatite) continue;

            foreach (NodeInfoDef EachJyoutai in JyoutaiList) {
                Popped.KoHashList.Add(EachJyoutai.Hash);

                //訪問済ノードなら再訪しない
                if (NodeInfoList.Exists(A => A.Hash == EachJyoutai.Hash))
                    continue;
                NodeInfoList.Add(EachJyoutai);

                if (EachJyoutai.Syouhai == 0) Stk.Push(EachJyoutai);
            }
        }
        //Hash値でソートしておく
        mNodeInfoArr = NodeInfoList.OrderBy(A => A.Hash).ToArray();
    }

    //mNodeInfoArrの添字[Hash値]のDictを作成
    static Dictionary<int, int> mHashIndDict = new Dictionary<int, int>();
    static void CreateHashIndDict()
    {
        for (int I = 0; I <= mNodeInfoArr.GetUpperBound(0); I++) {
            mHashIndDict.Add(mNodeInfoArr[I].Hash, I);
        }
    }

    //全ノードの勝敗を求める
    static void DeriveAllSyouhai()
    {
        int LimitNodeCnt = 10, PrevNodeCnt = 0;
        while (true) {
            int CurrNodeCnt = mNodeInfoArr.Count(A => A.Syouhai == 0);
            if (CurrNodeCnt == 0) break;

            if (CurrNodeCnt == PrevNodeCnt) LimitNodeCnt *= 2;
            else LimitNodeCnt = 10;

            for (int I = 0; I <= mNodeInfoArr.GetUpperBound(0); I++) {
                if (mNodeInfoArr[I].Syouhai != 0) continue;

                mNodeInfoArr[I].Syouhai =
                    DeriveRootNodeSyouhai(mNodeInfoArr[I].Hash, LimitNodeCnt);
            }
            PrevNodeCnt = CurrNodeCnt;
        }
    }

    struct JyoutaiDefDFS
    {
        internal int Level;
        internal int NodeID;
        internal List<int> KoNodeIDList;
        internal int Hash; //手番と盤面のハッシュ値
        internal int Syouhai; //勝敗 (未決定は0、先手勝は1、後手勝は2)
        internal HashSet<int> VisitedSetInu;
    }

    //根ノードのHash値と訪問ノード数上限を引数として、
    //完全ゲーム木を作り、根ノードの勝敗を求める
    static int DeriveRootNodeSyouhai(int pRootHash, int pLimitNodeCnt)
    {
        var GameTreeList = new List<JyoutaiDefDFS>();

        var Stk = new Stack<JyoutaiDefDFS>();
        JyoutaiDefDFS WillPush;
        WillPush.Level = 0;
        WillPush.NodeID = GetNodeID();
        WillPush.KoNodeIDList = new List<int>();
        WillPush.Hash = pRootHash;
        WillPush.Syouhai = 0;
        WillPush.VisitedSetInu = new HashSet<int>();

        int Ind1 = mHashIndDict[pRootHash];
        if (mNodeInfoArr[Ind1].Teban == 1) { //犬番の場合
            WillPush.VisitedSetInu.Add(pRootHash);
        }
        GameTreeList.Add(WillPush);
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDefDFS Popped = Stk.Pop();

            //ノード数上限を超えた場合
            if (GameTreeList.Count > pLimitNodeCnt) return 0;

            int Ind2 = mHashIndDict[Popped.Hash];

            var JyoutaiList = new List<JyoutaiDefDFS>();

            //勝ちになる手があるか？
            bool HasKatite = false;

            foreach (int EachHash in mNodeInfoArr[Ind2].KoHashList) {
                int Ind3 = mHashIndDict[EachHash];
                WillPush.Level = Popped.Level + 1;
                WillPush.NodeID = GetNodeID();
                WillPush.KoNodeIDList = new List<int>();
                WillPush.Hash = EachHash;
                WillPush.Syouhai = mNodeInfoArr[Ind3].Syouhai;

                if (mNodeInfoArr[Ind3].Teban == 1) { //犬番の場合
                    //犬番での千日手は不可
                    if (Popped.VisitedSetInu.Contains(EachHash)) continue;
                    WillPush.VisitedSetInu = new HashSet<int>(Popped.VisitedSetInu);
                    WillPush.VisitedSetInu.Add(EachHash);
                }
                else { //ウサギ番の場合
                    WillPush.VisitedSetInu = Popped.VisitedSetInu;
                }

                //勝ちになる手があったら、その手で確定
                if (mNodeInfoArr[Ind3].Teban == mNodeInfoArr[Ind3].Syouhai) {
                    Popped.KoNodeIDList.Add(WillPush.NodeID);
                    GameTreeList.Add(WillPush);
                    HasKatite = true;
                    break;
                }
                JyoutaiList.Add(WillPush);
            }

            if (HasKatite) continue;

            //勝敗不明な手があるなら、負けになる手をRemove
            if (JyoutaiList.Exists(A => A.Syouhai == 0))
                JyoutaiList.RemoveAll(A => A.Syouhai != 0);

            foreach (JyoutaiDefDFS EachJyoutai in JyoutaiList) {
                Popped.KoNodeIDList.Add(EachJyoutai.NodeID);
                GameTreeList.Add(EachJyoutai);
                if (EachJyoutai.Syouhai == 0) Stk.Push(EachJyoutai);
            }
        }

        //レベルの降順でソートしておく
        JyoutaiDefDFS[] GameTreeArr = GameTreeList.OrderByDescending(A => A.Level).ToArray();
        while (GameTreeArr.Length > 1) {
            int TreeHeight = GameTreeArr.Max(X => X.Level);

            //木の高さ-1のノードの勝敗を決定する
            for (int I = 0; I <= GameTreeArr.GetUpperBound(0); I++) {
                if (GameTreeArr[I].Level > TreeHeight - 1) continue;
                if (GameTreeArr[I].Level < TreeHeight - 1) break;
                if (GameTreeArr[I].Syouhai != 0) continue;

                int Ind4 = mHashIndDict[GameTreeArr[I].Hash];
                int Teban = mNodeInfoArr[Ind4].Teban;

                //犬番の場合は、ウサギが最善手で応じても犬勝なら、犬勝
                if (Teban == 1) {
                    bool IsHit = false;
                    foreach (int EachKoNodeID in GameTreeArr[I].KoNodeIDList) {
                        if (Array.Exists(GameTreeArr,
                            A => A.NodeID == EachKoNodeID && A.Syouhai == 2)) {
                            IsHit = true;
                            break;
                        }
                    }
                    GameTreeArr[I].Syouhai = (IsHit ? 2 : 1);
                }
                //ウサギ番の場合は、犬が最善手で応じてもウサギ勝なら、ウサギ勝
                else {
                    bool IsHit = false;
                    foreach (int EachKoNodeID in GameTreeArr[I].KoNodeIDList) {
                        if (Array.Exists(GameTreeArr,
                            A => A.NodeID == EachKoNodeID && A.Syouhai == 1)) {
                            IsHit = true;
                            break;
                        }
                    }
                    GameTreeArr[I].Syouhai = (IsHit ? 1 : 2);
                }
            }
            //不要なノードを削除
            GameTreeArr = Array.FindAll(GameTreeArr, A => A.Level <= TreeHeight - 1);
        }
        return GameTreeArr[0].Syouhai;
    }

    //NodeID(自動採番)
    static int mNodeID = 0;
    static int GetNodeID()
    {
        return ++mNodeID;
    }

    //ウサギの位置を指定して、初期状態の2次元配列を返す
    static char[,] InitBanArr(char pUsagiPos)
    {
        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                WillReturn[X, Y] = ' ';
            }
        }
        WillReturn[0, 3] = '犬';
        WillReturn[1, 4] = '犬';
        WillReturn[2, 3] = '犬';

        if (pUsagiPos == 'A') WillReturn[1, 0] = 'ウ';
        if (pUsagiPos == 'B') WillReturn[0, 1] = 'ウ';
        if (pUsagiPos == 'C') WillReturn[1, 1] = 'ウ';
        if (pUsagiPos == 'D') WillReturn[2, 1] = 'ウ';
        if (pUsagiPos == 'E') WillReturn[0, 2] = 'ウ';
        if (pUsagiPos == 'F') WillReturn[1, 2] = 'ウ';
        if (pUsagiPos == 'G') WillReturn[2, 2] = 'ウ';
        if (pUsagiPos == 'I') WillReturn[1, 3] = 'ウ';
        return WillReturn;
    }

    //手番と盤面をハッシュ値に変換
    static int GetHash(int pTeban, char[,] pBanArr)
    {
        var NumList = new List<int>();

        //手番もハッシュ値に含める
        NumList.Add(pTeban);

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                if (X == 0 && Y == 0) continue;
                if (X == UB_X && Y == 0) continue;
                if (X == 0 && Y == UB_Y) continue;
                if (X == UB_X && Y == UB_Y) continue;

                if (pBanArr[X, Y] == ' ') NumList.Add(0);
                if (pBanArr[X, Y] == '犬') NumList.Add(1);
                if (pBanArr[X, Y] == 'ウ') NumList.Add(2);
            }
        }
        //3の12乗=531441なので3進数ならオーバーフローしない
        int WillReturn = 0;
        foreach (int EachInt in NumList) {
            WillReturn *= 3;
            WillReturn += EachInt;
        }
        return WillReturn;
    }

    //遷移可能な盤面を列挙
    static List<char[,]> DeriveCanSeniBanArrList(char[,] pBanArr, bool pIsUsagi)
    {
        var WillReturnList = new List<char[,]>();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (pIsUsagi == false && pBanArr[LoopX, LoopY] != '犬') continue;
                if (pIsUsagi && pBanArr[LoopX, LoopY] != 'ウ') continue;

                List<PointDef> CanMovePosList =
                    (pIsUsagi ? DeriveCanMovePosListUsagi(LoopX, LoopY) :
                                DeriveCanMovePosListInu(LoopX, LoopY));
                CanMovePosList.RemoveAll(A => pBanArr[A.X, A.Y] != ' ');

                foreach (PointDef EachMovePos in CanMovePosList) {
                    char[,] wkArr = (char[,])pBanArr.Clone();
                    wkArr[LoopX, LoopY] = ' ';
                    wkArr[EachMovePos.X, EachMovePos.Y] = (pIsUsagi ? 'ウ' : '犬');
                    WillReturnList.Add(wkArr);
                }
            }
        }
        return WillReturnList;
    }

    //座標を引数として、移動可能な座標を返す(犬用)
    static List<PointDef> DeriveCanMovePosListInu(int pFromX, int pFromY)
    {
        var WillReturnList = new List<PointDef>();
        if (pFromX == 0 && pFromY == 1
         || pFromX == 2 && pFromY == 1) { //BまたはDの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 0 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 1 });
        }
        if (pFromX == 1 && pFromY == 1) { //Cの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 0 });
            WillReturnList.Add(new PointDef() { X = 0, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 1 });
        }
        if (pFromX == 0 && pFromY == 2) { //Eの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
        }
        if (pFromX == 1 && pFromY == 2) { //Fの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 0, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 2 });
        }
        if (pFromX == 2 && pFromY == 2) { //Gの場合
            WillReturnList.Add(new PointDef() { X = 2, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
        }
        if (pFromX == 0 && pFromY == 3) { //Hの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 3 });
        }
        if (pFromX == 1 && pFromY == 3) { //Iの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 0, Y = 3 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 3 });
        }
        if (pFromX == 2 && pFromY == 3) { //Jの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 3 });
        }
        if (pFromX == 1 && pFromY == 4) { //Kの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 3 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 3 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 3 });
        }
        return WillReturnList;
    }

    //座標を引数として、移動可能な座標を返す(ウサギ用)
    static List<PointDef> DeriveCanMovePosListUsagi(int pFromX, int pFromY)
    {
        var WillReturnList = new List<PointDef>();
        WillReturnList.AddRange(DeriveCanMovePosListInu(pFromX, pFromY));
        if (pFromX == 1 && pFromY == 0) { //Aの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 1 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 1 });
        }
        if (pFromX == 0 && pFromY == 1) { //Bの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
        }
        if (pFromX == 1 && pFromY == 1) { //Cの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
        }
        if (pFromX == 2 && pFromY == 1) { //Dの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 2 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 2 });
        }
        if (pFromX == 0 && pFromY == 2) { //Eの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 3 });
        }
        if (pFromX == 1 && pFromY == 2) { //Fの場合
            WillReturnList.Add(new PointDef() { X = 0, Y = 3 });
            WillReturnList.Add(new PointDef() { X = 1, Y = 3 });
            WillReturnList.Add(new PointDef() { X = 2, Y = 3 });
        }
        if (pFromX == 2 && pFromY == 2) { //Gの場合
            WillReturnList.Add(new PointDef() { X = 2, Y = 3 });
        }
        if (pFromX == 0 && pFromY == 3) { //Hの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 4 });
        }
        if (pFromX == 1 && pFromY == 3) { //Iの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 4 });
        }
        if (pFromX == 2 && pFromY == 3) { //Jの場合
            WillReturnList.Add(new PointDef() { X = 1, Y = 4 });
        }
        return WillReturnList;
    }

    //盤面から勝敗(未決定は0、先手勝は1、後手勝は2)を求める
    static int DeriveSyouhai(char[,] pBanArr)
    {
        //犬勝かを判定
        char[,] wkP = pBanArr;
        if (wkP[1, 0] == 'ウ'
         && wkP[0, 1] == '犬' && wkP[1, 1] == '犬' && wkP[2, 1] == '犬') {
            return 1;
        }
        if (wkP[0, 2] == 'ウ'
         && wkP[0, 1] == '犬' && wkP[1, 2] == '犬' && wkP[0, 3] == '犬') {
            return 1;
        }
        if (wkP[2, 2] == 'ウ'
         && wkP[2, 1] == '犬' && wkP[1, 2] == '犬' && wkP[2, 3] == '犬') {
            return 1;
        }

        //犬が[1,0]にいたらウサギ勝
        if (wkP[1, 0] == '犬') return 2;

        //ウサギ勝かを判定
        var InuYList = new List<int>();
        int UsagiY = -1;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (wkP[X, Y] == 'ウ') UsagiY = Y;
                if (wkP[X, Y] == '犬') InuYList.Add(Y);
            }
        }
        //ウサギのY座標 >= 最も下の犬のY座標 ならウサギ勝
        if (UsagiY >= InuYList.Max()) return 2;

        //Y座標がウサギ以上の犬が1匹以下 ならウサギ勝
        if (InuYList.Count(A => UsagiY <= A) <= 1) return 2;

        //ウサギがFHIJのいずれかにいて、犬がBCDのいずれかにいたら ウサギ勝
        if (wkP[1, 2] == 'ウ'
         || wkP[0, 3] == 'ウ' || wkP[1, 3] == 'ウ' || wkP[2, 3] == 'ウ') {
            if (wkP[0, 1] == '犬' || wkP[1, 1] == '犬' || wkP[2, 1] == '犬') {
                return 2;
            }
        }
        return 0;
    }

    static void DebugPrint(NodeInfoDef pNodeInfo)
    {
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("Teban={0},Hash={1},勝敗={2},",
            pNodeInfo.Teban, pNodeInfo.Hash, pNodeInfo.Syouhai);

        sb.Append("子ノードのHashは");
        if (pNodeInfo.KoHashList.Count > 0)
            pNodeInfo.KoHashList.ForEach(A => sb.AppendFormat("{0},", A));
        else sb.Append("なし");

        Console.WriteLine(sb.ToString());
        PrintBan(pNodeInfo.BanArr);
    }

    //盤面を表示
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        Func<int, int, char, char> wkFunc = (pX, pY, pPos) =>
            pBanArr[pX, pY] == ' ' ? pPos : pBanArr[pX, pY];

        sb.AppendFormat("　　{0}", wkFunc(1, 0, 'Ａ'));
        sb.AppendLine();
        sb.AppendLine("　／│＼");
        sb.AppendFormat("{0}─{1}─{2}",
            wkFunc(0, 1, 'Ｂ'), wkFunc(1, 1, 'Ｃ'), wkFunc(2, 1, 'Ｄ'));
        sb.AppendLine();
        sb.AppendLine("│＼│／│");
        sb.AppendFormat("{0}─{1}─{2}",
            wkFunc(0, 2, 'Ｅ'), wkFunc(1, 2, 'Ｆ'), wkFunc(2, 2, 'Ｇ'));
        sb.AppendLine();
        sb.AppendLine("│／│＼│");
        sb.AppendFormat("{0}─{1}─{2}",
            wkFunc(0, 3, 'Ｈ'), wkFunc(1, 3, 'Ｉ'), wkFunc(2, 3, 'Ｊ'));
        sb.AppendLine();
        sb.AppendLine("　＼│／");
        sb.AppendFormat("　　{0}", wkFunc(1, 4, 'Ｋ'));
        sb.AppendLine();
        Console.WriteLine(sb.ToString());
    }
}

実行結果

遷移可能な盤面を列挙します。
遷移可能な盤面は1237通り。
　　Ａ
　／│＼
Ｂ─Ｃ─Ｄ
│＼│／│
Ｅ─Ｆ─Ｇ
│／│＼│
犬─Ｉ─犬
　＼│／
　　犬

ウサギの配置場所を入力して下さい a
□□□□□□□□□□□□□□□□□□□□□□□□□
現在の手数=0。Hash=472423。犬の手番。

　　ウ
　／│＼
Ｂ─Ｃ─Ｄ
│＼│／│
Ｅ─Ｆ─Ｇ
│／│＼│
犬─Ｉ─犬
　＼│／
　　犬

省略

解説

完全ゲーム木を作って、全ノードの勝敗を求めてます。

第062回 クラム・ゲーム
パズルトピア - [魔物退治] 紹介