using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static JyoutaiDef[] mGameTreeArr;
static void Main()
{
//ゲーム木の作成
CreateGameTreeArr();
//全ノードのスコアをMinMax法で求める
DeriveAllSyouhai();
//根ノードからの経路を表示
PrintMinMaxKeiro();
}
struct JyoutaiDef
{
internal int Level;
internal int NodeID;
internal List<int> KoNodeIDList;
internal Dictionary<int, char> BanDict;
internal HashSet<int> VisitedSet;
internal int Score;
}
//ゲーム木の作成
static void CreateGameTreeArr()
{
var NodeInfoList = new List<JyoutaiDef>();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.NodeID = GetNodeID();
WillPush.KoNodeIDList = new List<int>();
WillPush.BanDict = InitBanDict();
WillPush.VisitedSet = new HashSet<int>();
WillPush.VisitedSet.Add(GetHash(2, WillPush.BanDict));
WillPush.Score = 0;
NodeInfoList.Add(WillPush);
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
var JyoutaiList = new List<JyoutaiDef>();
//勝ちになる手があるか？
bool HasKatite = false;
//遷移可能な盤面を列挙
int wkTeban = DeriveTebanFromLevel(Popped.Level + 1);
Dictionary<int, char>[] CanSeniBanDictList =
DeriveCanSeniBanDictList(Popped.BanDict, wkTeban == 1);
foreach (Dictionary<int, char> EachBanDict in CanSeniBanDictList) {
WillPush.Level = Popped.Level + 1;
WillPush.NodeID = GetNodeID();
WillPush.KoNodeIDList = new List<int>();
WillPush.BanDict = EachBanDict;
WillPush.VisitedSet = new HashSet<int>(Popped.VisitedSet);
WillPush.VisitedSet.Add(GetHash(wkTeban, WillPush.BanDict));
int wkSyouhai = DeriveSyouhai(wkTeban, WillPush.BanDict, Popped.VisitedSet);
if (wkSyouhai == 0) WillPush.Score = 0;
if (wkSyouhai == 1) WillPush.Score = WillPush.Level;
if (wkSyouhai == 2) WillPush.Score = 9999;
//勝ちになる手があったら、その手で確定
if (wkSyouhai == wkTeban) {
HasKatite = true;
Popped.KoNodeIDList.Add(WillPush.NodeID);
NodeInfoList.Add(WillPush);
break;
}
JyoutaiList.Add(WillPush);
}
if (HasKatite) continue;
JyoutaiList.ForEach(X =>
{
Popped.KoNodeIDList.Add(X.NodeID);
NodeInfoList.Add(X);
if (X.Score == 0) Stk.Push(X);
});
}
//レベルの降順でソートしておく
mGameTreeArr = NodeInfoList.OrderByDescending(X => X.Level).ToArray();
}
//遷移可能な盤面を列挙
static Dictionary<int, char>[] DeriveCanSeniBanDictList(Dictionary<int, char> pBanDict, bool pIsKeibu)
{
var WillReturn = new List<Dictionary<int, char>>();
int wkKey = -1;
if (pIsKeibu) wkKey = pBanDict.First(X => X.Value == '警').Key;
else wkKey = pBanDict.First(X => X.Value == '泥').Key;
List<int> CanMovePosList = DeriveCanMovePosList(wkKey);
CanMovePosList.RemoveAll(X => pBanDict[X] != '○');
foreach (int EachMovePos in CanMovePosList) {
var wkBanDict = new Dictionary<int, char>(pBanDict);
wkBanDict[wkKey] = '○';
wkBanDict[EachMovePos] = (pIsKeibu ? '警' : '泥');
WillReturn.Add(wkBanDict);
}
return WillReturn.ToArray();
}
//座標を引数として、移動可能な座標を返す
static List<int> DeriveCanMovePosList(int pFromPos)
{
var WillReturn = new List<int>();
if (pFromPos == 0) WillReturn.AddRange(new int[] { 1, 2, 3 });
if (pFromPos == 1) WillReturn.AddRange(new int[] { 0, 4 });
if (pFromPos == 2) WillReturn.AddRange(new int[] { 0, 5 });
if (pFromPos == 3) WillReturn.AddRange(new int[] { 0, 4, 5 });
if (pFromPos == 4) WillReturn.AddRange(new int[] { 1, 3, 5 });
if (pFromPos == 5) WillReturn.AddRange(new int[] { 2, 3, 4 });
return WillReturn;
}
//勝敗(未決定は0、先手勝は1、後手勝は2)を求める
static int DeriveSyouhai(int pTeban, Dictionary<int, char> pBanDict, HashSet<int> pVisitedSet)
{
//同一盤面になったら、泥棒の勝ち
int wkHash = GetHash(pTeban, pBanDict);
if (pVisitedSet.Contains(wkHash)) {
return 2;
}
if (pTeban == 2) {
//警部が泥棒に隣接してたら警部の勝ち
int wkKey = pBanDict.First(X => X.Value == '警').Key;
List<int> wkCanMovePosList = DeriveCanMovePosList(wkKey);
if (wkCanMovePosList.Exists(X => pBanDict[X] == '泥'))
return 1;
}
return 0;
}
//引数のレベルに対する手番(先手は1、後手は2)を返す
static int DeriveTebanFromLevel(int pLevel)
{
return (pLevel % 2 == 1) ? 1 : 2;
}
//NodeID(自動採番)
static int mNodeID = 0;
static int GetNodeID()
{
return ++mNodeID;
}
//初期状態のDictを返す
static Dictionary<int, char> InitBanDict()
{
var WillReturn = new Dictionary<int, char>();
WillReturn[0] = '○';
WillReturn[1] = '○';
WillReturn[2] = '泥';
WillReturn[3] = '警';
WillReturn[4] = '○';
WillReturn[5] = '○';
return WillReturn;
}
//全ノードのスコアをMinMax法で求める
static void DeriveAllSyouhai()
{
for (int I = 0; I <= mGameTreeArr.GetUpperBound(0); I++) {
if (mGameTreeArr[I].Score != 0) continue;
int Teban = DeriveTebanFromLevel(mGameTreeArr[I].Level);
//先手の場合は、後手が最善手で応じても先手が最小のScoreとなる手を選ぶ
if (Teban == 1) {
int wkMax = int.MinValue;
foreach (int EachKoNodeID in mGameTreeArr[I].KoNodeIDList) {
int wkScore = mGameTreeArr.First(X => X.NodeID == EachKoNodeID).Score;
if (wkMax < wkScore)
wkMax = wkScore;
}
mGameTreeArr[I].Score = wkMax;
}
//後手の場合は、先手が最善手で応じても後手が最大のScoreとなる手を選ぶ
else {
int wkMin = int.MaxValue;
foreach (int EachKoNodeID in mGameTreeArr[I].KoNodeIDList) {
int wkScore = mGameTreeArr.First(X => X.NodeID == EachKoNodeID).Score;
if (wkMin > wkScore)
wkMin = wkScore;
}
mGameTreeArr[I].Score = wkMin;
}
}
}
//根ノードからの経路を表示
static void PrintMinMaxKeiro()
{
int CurrInd = mGameTreeArr.GetUpperBound(0);
Console.WriteLine("解は{0}手", mGameTreeArr[CurrInd].Score + 1);
Console.WriteLine();
while (true) {
Console.WriteLine("{0}手目", mGameTreeArr[CurrInd].Level);
PrintBan(mGameTreeArr[CurrInd].BanDict);
List<int> wkKoNodeIDList = mGameTreeArr[CurrInd].KoNodeIDList;
int wkScore = mGameTreeArr[CurrInd].Score;
CurrInd = Array.FindIndex(mGameTreeArr, X => wkKoNodeIDList.Contains(X.NodeID)
&& X.Score == wkScore);
if (CurrInd == -1) break;
}
}
//手番と盤面をハッシュ値に変換
static int GetHash(int pTeban, Dictionary<int, char> pBanDict)
{
var NumList = new List<int>();
//手番もハッシュ値に含める
NumList.Add(pTeban);
foreach (var EachPair in pBanDict.OrderBy(X => X.Key)) {
if (EachPair.Value == '○') NumList.Add(0);
if (EachPair.Value == '警') NumList.Add(1);
if (EachPair.Value == '泥') NumList.Add(2);
}
//3の7乗=2187なので3進数ならオーバーフローしない
int WillReturn = 0;
foreach (int EachInt in NumList) {
WillReturn *= 3;
WillReturn += EachInt;
}
return WillReturn;
}
//盤面を表示
static void PrintBan(Dictionary<int, char> pBanDict)
{
var sb = new System.Text.StringBuilder();
sb.AppendFormat(" {0}", pBanDict[0]);
sb.AppendLine();
sb.Append(" ／│＼");
sb.AppendLine();
sb.AppendFormat("{0} {1} {2}", pBanDict[1], pBanDict[3], pBanDict[2]);
sb.AppendLine();
sb.Append(" ＼／＼／");
sb.AppendLine();
sb.AppendFormat(" {0}─{1}", pBanDict[4], pBanDict[5]);
sb.AppendLine();
Console.WriteLine(sb.ToString());
}
}
