棒消しゲームは先手必勝か後手必勝かどうかについて微考ペガサス

棒消しゲームについて
45mix.net

---

段数によって先手必勝・後手必勝が分かれるんじゃないかと思って確かめてみたらそうだったという話。
ちなみにこのゲームは引き分けの無い二人零和有限確定完全情報ゲームなので、先手必勝・後手必勝のどちらかになることは間違いない。
こういうゲームの場合、以下のアルゴリズムで良い想定。引き分けも、手番パスも無いのでシンプルに考えられる。

function 勝者の判定 ( $ゲームの局面 ) : 勝者
{
	if ( $ゲームの局面　は勝敗が決している ) // この局面において何方かのプレイヤの勝利条件が達成されているか
	{
		return $ゲームの局面　における勝者 ;
	}

	for ( $指し手 : 手番のプレイヤにできる全ての指し手 )
	{
		if ( 勝者の判定 ( $ゲームの局面 + $指し手 ) == 手番のプレイヤ ) // この局面において手番のプレイヤがこの手で指し進め、勝利するなら ...
		{
			return 手番のプレイヤ ; // ... 手番のプレイヤの勝ちは確定していることになる。
		}
	}

	return 相手側のプレイヤ ; // この局面において手番のプレイヤが何を指しても負けるのなら、相手側のプレイヤの勝ちは確定していることになる。
}

Print "お互い最善手を指せば " + 勝者の判定 ( ゲームの初期状態 ) + " が常に勝利する。" ;

　
実際にやってみた。
コード：

public void Main()
{
	for (int n = 1; ; n++)
	{
		Console.WriteLine(n + " 段の場合 " + (GetWinner(Enumerable.Range(1, n).ToArray()) == Player_e.Me ? "先手必勝" : "後手必勝") + " です。");
	}
}

private enum Player_e
{
	Me,
	Another,
}

private Player_e GetWinner(IList<int> rows) // rows: 各行の(連続する)棒の本数 , ret: 自分(Player_e.Me)を手番とした場合のこの局面における勝者
{
	if (rows.Count == 0) // 直前に相手が消した棒が最後なら、相手の負け。
	{
		return Player_e.Me; // つまり勝者は自分
	}

	for (int i = 0; i < rows.Count; i++) // 全ての行について
	{
		int row = rows[i];

		for (int s = 0; s < row; s++) // 消し始めの位置
		{
			for (int c = 1; s + c <= row; c++) // 消す本数
			{
				int l = s; // 分断された行の左側
				int r = row - (s + c); // 分断された行の右側

				List<int> next = new List<int>(); // 次の局面を作る。

				next.AddRange(rows.Take(i)); // 消した行の前側
				next.AddRange(rows.Skip(i + 1)); // 消した行の後側

				// 分断された部分を独立した行と見なして追加する。
				if (l != 0) next.Add(l);
				if (r != 0) next.Add(r);

				if (GetWinner(next) == Player_e.Another) // 次の局面以降において自分の勝ちが確定するなら ...
				{
					return Player_e.Me; // ... 勝者は自分
				}
			}
		}
	}

	return Player_e.Another; // 勝ち目が無ければ、勝者は相手側
}

で、
これを実行したらやたら重かったので、勝者をキャッシュして同じ局面については再探索しないように修正したのが以下。
コード：

public void Main()
{
	for (int n = 1; ; n++)
	{
		Console.WriteLine(n + " 段の場合 " + (GetWinner(Enumerable.Range(1, n).ToArray()) == Player_e.Me ? "先手必勝" : "後手必勝") + " です。");
	}
}

private enum Player_e
{
	Me,
	Another,
}

private Player_e GetWinner(IList<int> rows) // rows: 各行の(連続する)棒の本数_昇順であること , ret: 自分(Player_e.Me)を手番とした場合のこの局面における勝者
{
	if (rows.Count == 0) // 直前に相手が消した棒が最後なら、相手の負け。
	{
		return Player_e.Me; // つまり勝者は自分
	}

	string strRows = RowsToString(rows);

	if (WinnerCache.ContainsKey(strRows)) // 既知の局面なら、既知の勝者を返す。
	{
		return WinnerCache[strRows];
	}

	for (int i = 0; i < rows.Count; i++) // 全ての行について
	{
		int row = rows[i];

		for (int s = 0; s < row; s++) // 消し始めの位置
		{
			for (int c = 1; s + c <= row; c++) // 消す本数
			{
				int l = s; // 分断された行の左側
				int r = row - (s + c); // 分断された行の右側

				List<int> next = new List<int>(); // 次の局面を作る。

				next.AddRange(rows.Take(i)); // 消した行の前側
				next.AddRange(rows.Skip(i + 1)); // 消した行の後側

				// 分断された部分を独立した行と見なして追加する。
				if (l != 0) next.Add(l);
				if (r != 0) next.Add(r);

				next.Sort((a, b) => a - b); // 昇順にソートする。

				if (GetWinner(next) == Player_e.Another) // 次の局面以降において自分の勝ちが確定するなら ...
				{
					WinnerCache.Add(strRows, Player_e.Me); // この局面における勝者を記憶

					return Player_e.Me; // ... 勝者は自分
				}
			}
		}
	}

	WinnerCache.Add(strRows, Player_e.Another); // この局面における勝者を記憶

	return Player_e.Another; // 勝ち目が無ければ、勝者は相手側
}

private Dictionary<string, Player_e> WinnerCache = new Dictionary<string, Player_e>();

private string RowsToString(IList<int> rows)
{
	return string.Join("_", rows);
}

出力：

1 段の場合 後手必勝 です。
2 段の場合 先手必勝 です。
3 段の場合 後手必勝 です。
4 段の場合 先手必勝 です。
5 段の場合 先手必勝 です。
6 段の場合 先手必勝 です。
7 段の場合 後手必勝 です。
8 段の場合 先手必勝 です。
9 段の場合 先手必勝 です。
10 段の場合 先手必勝 です。
^C

　
まだ重い気がするけど、10 段以下で先手必勝・後手必勝が分かれるのが見れたので満足。
微考終了。