using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int UB;
struct JyoutaiDef
{
internal int Level;
internal int NodeID;
internal int OyaNodeID; //親のNodeID
internal int SameBanmenNodeID; //同一盤面のNodeID
internal bool[] BanArr;
//勝敗 (未決定は0、先手勝は1、後手勝は2、同一盤面の勝敗取得は3)
internal int Syouhai;
}
//先手必勝かのDict
static Dictionary<int, bool> IsSenteHissyouDict = new Dictionary<int, bool>();
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
for (int I = 2; I <= 28; I++) {
Console.Write("盤幅={0,2}。", I);
UB = I - 1;
//ゲーム木の作成
List<JyoutaiDef> GameTreeList = CreateGameTreeList();
//ゲーム木から、先手必勝かを調べる
if (IsSenteHissyou(GameTreeList)) {
Console.WriteLine("先手必勝。経過時間={0}", sw.Elapsed);
IsSenteHissyouDict[I] = true;
}
else {
Console.WriteLine("後手必勝。経過時間={0}", sw.Elapsed);
IsSenteHissyouDict[I] = false;
}
}
}
//ゲーム木の作成
static List<JyoutaiDef> CreateGameTreeList()
{
var WillReturnList = new List<JyoutaiDef>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.NodeID = GetNodeID();
WillPush.OyaNodeID = -1;
WillPush.SameBanmenNodeID = -1;
WillPush.BanArr = new bool[UB + 1];
WillPush.Syouhai = 0;
WillPush.Syouhai = DeriveSyouhai(WillPush);
WillReturnList.Add(WillPush);
if (WillPush.Syouhai == 0) stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
var JyoutaiList = new List<JyoutaiDef>();
//勝ちになる手があるか？
bool HasKatite = false;
for (int X = 0; X <= UB; X++) {
//1手目は対称な配置がない箇所のみ配置可能
if (Popped.Level == 0) {
//偶数の場合
if (UB % 2 == 1 && X > UB / 2) break;
//奇数の場合
if (UB % 2 == 0 && X >= UB / 2) break;
}
if (CanFillPiece(X, Popped.BanArr) == false) continue;
WillPush.BanArr = (bool[])Popped.BanArr.Clone();
//駒を配置する経路のPush処理
for (int wkX = 0; wkX <= 1; wkX++) {
WillPush.BanArr[X + wkX] = true;
}
WillPush.Level = Popped.Level + 1;
WillPush.NodeID = GetNodeID();
WillPush.OyaNodeID = Popped.NodeID;
//同一盤面のチェック
bool HasSameBanmen = false;
foreach (JyoutaiDef EachNode in WillReturnList) {
if (EachNode.Level != WillPush.Level) continue;
if (EachNode.Syouhai == 3) continue;
if (IsSameBanmen(EachNode.BanArr, WillPush.BanArr)) {
HasSameBanmen = true;
WillPush.Syouhai = 3;
WillPush.SameBanmenNodeID = EachNode.NodeID;
JyoutaiList.Add(WillPush);
break;
}
}
//同一盤面が既出の場合
if (HasSameBanmen) continue;
WillPush.Syouhai = DeriveSyouhai(WillPush);
WillPush.SameBanmenNodeID = -1;
//勝ちになる手があったら、その手で確定
if (WillPush.Syouhai == DeriveTebanFromLevel(WillPush.Level)) {
HasKatite = true;
WillReturnList.Add(WillPush);
break;
}
JyoutaiList.Add(WillPush);
}
if (HasKatite) continue;
JyoutaiList.ForEach(X =>
{
WillReturnList.Add(X);
if (X.Syouhai == 0) stk.Push(X);
});
}
Console.Write("ゲーム木のノード数={0,6}。", WillReturnList.Count);
return WillReturnList;
}
//盤面から勝敗(未決定は0、先手勝は1、後手勝は2)を求める
static int DeriveSyouhai(JyoutaiDef pJyoutaiDef)
{
//連続空白の固まりの数
var SpaceCntList = new List<int>();
int wkSpaceCnt = 0;
bool[] wkArr = pJyoutaiDef.BanArr;
for (int I = 0; I <= UB; I++) {
//連続空白の場合
if (wkArr[I] == false &&
(0 <= I - 1 && wkArr[I - 1] == false || I + 1 <= UB && wkArr[I + 1] == false)) {
wkSpaceCnt++;
}
else if (wkSpaceCnt > 0) { //連続空白でない場合
SpaceCntList.Add(wkSpaceCnt);
wkSpaceCnt = 0;
}
if (I == UB && wkSpaceCnt > 0) SpaceCntList.Add(wkSpaceCnt);
}
//連続空白の固まりが1つしかない場合
if (SpaceCntList.Count == 1) {
int SpaceCnt = SpaceCntList[0];
//偶数なら次の手番をもったほうの勝ち
if (SpaceCnt % 2 == 0)
return DeriveTebanFromLevel(pJyoutaiDef.Level + 1);
if (IsSenteHissyouDict.ContainsKey(SpaceCnt)) {
bool wkBool = IsSenteHissyouDict[SpaceCnt];
//次の手番を持ったほうの勝ちの場合
if (wkBool) return DeriveTebanFromLevel(pJyoutaiDef.Level + 1);
//次の手番を持ったほうの負けの場合
else return DeriveTebanFromLevel(pJyoutaiDef.Level);
}
}
if (SpaceCntList.Count > 1) {
//連続空白の固まりが2と3と5のみの場合
if (SpaceCntList.TrueForAll(X => X == 2 || X == 3 || X == 5)) {
int wkCnt = SpaceCntList.Count(X => X == 2 || X == 3);
//2と3の固まりの数が偶数なら、次の手番を持ったほうの負け
if (wkCnt % 2 == 0)
return DeriveTebanFromLevel(pJyoutaiDef.Level);
//2と3の固まりの数が奇数なら、次の手番を持ったほうの勝ち
if (wkCnt % 2 == 1)
return DeriveTebanFromLevel(pJyoutaiDef.Level + 1);
}
}
if (SpaceCntList.Count > 1) {
int wkCnt = SpaceCntList.Count(X => IsSenteHissyouDict[X]);
//先手勝ちの固まりが0なら、次の手番を持ったほうの負け
if (wkCnt == 0)
return DeriveTebanFromLevel(pJyoutaiDef.Level);
//先手勝ちの固まりが1つだけなら、次の手番を持ったほうの勝ち
if (wkCnt == 1)
return DeriveTebanFromLevel(pJyoutaiDef.Level + 1);
}
return 0;
}
//ゲーム木から、先手必勝かを調べる
static bool IsSenteHissyou(List<JyoutaiDef> pGameTreeList)
{
//レベルの降順でソートしておく
JyoutaiDef[] GameTreeArr = pGameTreeList.OrderByDescending(X => X.Level).ToArray();
while (GameTreeArr.Length > 1) {
int TreeHeight = GameTreeArr.Max(X => X.Level);
//Console.WriteLine("●●●●●●●●●●●●●●");
//Console.WriteLine("状態表示します");
//PrintGameTreeInfo(GameTreeArr);
//処理1
//レベル = 木の高さで、勝敗が0のノードは、最後に駒を置いたほうの勝ち
for (int I = 0; I <= GameTreeArr.Length - 1; I++) {
if (GameTreeArr[I].Level < TreeHeight) break;
if (GameTreeArr[I].Syouhai != 0) continue;
GameTreeArr[I].Syouhai = DeriveTebanFromLevel(GameTreeArr[I].Level);
}
//処理2
//同一盤面の勝敗取得ノードに勝敗をコピー
for (int I = 0; I <= GameTreeArr.Length - 1; I++) {
if (GameTreeArr[I].Level < TreeHeight) break;
if (GameTreeArr[I].Syouhai != 3) continue;
for (int J = 0; J <= GameTreeArr.Length - 1; J++) {
if (GameTreeArr[J].Level < TreeHeight) break;
if (GameTreeArr[J].NodeID != GameTreeArr[I].SameBanmenNodeID) continue;
GameTreeArr[I].Syouhai = GameTreeArr[J].Syouhai;
}
}
//処理3
//木の高さ-1のノードの勝敗を決定する
for (int I = 0; I <= GameTreeArr.Length - 1; I++) {
if (GameTreeArr[I].Level < TreeHeight - 1) break;
if (GameTreeArr[I].Level > TreeHeight - 1) continue;
if (GameTreeArr[I].Syouhai != 0) continue;
int Teban = DeriveTebanFromLevel(GameTreeArr[I].Level);
//レベルが奇数(先手)の場合は、後手が最善手で応じても先手勝ちなら、先手勝ち
if (Teban == 1) {
if (Array.Exists(GameTreeArr,
X => X.OyaNodeID == GameTreeArr[I].NodeID && X.Syouhai == 2))
GameTreeArr[I].Syouhai = 2;
else GameTreeArr[I].Syouhai = 1;
}
//レベルが偶数(後手)の場合は、先手が最善手で応じても後手勝ちなら、後手勝ち
if (Teban == 2) {
if (Array.Exists(GameTreeArr,
X => X.OyaNodeID == GameTreeArr[I].NodeID && X.Syouhai == 1))
GameTreeArr[I].Syouhai = 1;
else GameTreeArr[I].Syouhai = 2;
}
}
//処理4
//木の高さのノードをRemove
List<JyoutaiDef> wkGameTreeList = GameTreeArr.ToList();
wkGameTreeList.RemoveAll(X => X.Level == TreeHeight);
GameTreeArr = wkGameTreeList.OrderByDescending(X => X.Level).ToArray();
}
//Console.WriteLine("●●●●●●●●●●●●●●");
//Console.WriteLine("状態表示します");
//PrintGameTreeInfo(GameTreeArr);
return GameTreeArr[0].Syouhai == 1;
}
//引数のレベルに対する手番(先手は1、後手は2)を返す
static int DeriveTebanFromLevel(int pLevel)
{
return (pLevel % 2 == 1) ? 1 : 2;
}
//NodeID(自動採番)
static int mNodeID = 0;
static int GetNodeID()
{
return ++mNodeID;
}
//同一盤面かを返す
static bool IsSameBanmen(bool[] pBanArr1, bool[] pBanArr2)
{
bool IsDF1 = false, IsDF2 = false;
for (int X = 0; X <= UB; X++) {
bool CurrVal = pBanArr1[X];
if (pBanArr2[X] != CurrVal) IsDF1 = true;
if (pBanArr2[UB - X] != CurrVal) IsDF2 = true;
}
return IsDF1 == false || IsDF2 == false;
}
//マス目にピースを埋めれるか
static bool CanFillPiece(int pTargetX, bool[] pBanArr)
{
for (int X = 0; X <= 1; X++) {
if (pTargetX + X > UB) return false;
if (pBanArr[pTargetX + X]) return false;
}
return true;
}
//ゲーム木の状態を表示
static void PrintGameTreeInfo(JyoutaiDef[] pGameTreeArr)
{
var sb = new System.Text.StringBuilder();
foreach (JyoutaiDef EachNode in pGameTreeArr) {
sb.Length = 0;
sb.AppendFormat("Level={0},ID={1},OyaID={2},SameID={3}",
EachNode.Level, EachNode.NodeID, EachNode.OyaNodeID, EachNode.SameBanmenNodeID);
sb.AppendLine();
for (int X = 0; X <= UB; X++) {
bool wkBool = EachNode.BanArr[X];
if (wkBool) sb.Append('■');
else sb.Append('空');
}
sb.Append(" ");
string wkStr = "";
if (EachNode.Syouhai == 0) wkStr = "未決定";
if (EachNode.Syouhai == 1) wkStr = "先手勝";
if (EachNode.Syouhai == 2) wkStr = "後手勝";
if (EachNode.Syouhai == 3) wkStr = "同一盤面の勝敗取得";
sb.AppendFormat("勝敗={0}", wkStr);
sb.AppendLine();
Console.WriteLine(sb.ToString());
}
}
}