２行＋αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.

Presentation on theme: "２行＋αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄."— Presentation transcript:

1 ２行＋αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄

2 発表構成 チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値

3 発表構成 チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値

4 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。

5 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手

6 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。

7 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手

8 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。

9 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手

10 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。

11 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手

12 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。

13 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手

14 チョンプとは 長方形の板チョコを、２人が交互に食べていくゲーム。 左上のブロックが毒チョコ
各手番でプレイヤーは１つのブロックを選び、その右や下にあるブロックを全て食べる。 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手が毒チョコを食べざるを得ない 先手の勝ち！

15 先手必勝の証明 盤面の大きさに関わらず、チョンプは先手必勝。 証明：先手と後手のどちらかが必勝。後手が必勝と仮定すると・・・

16 先手必勝の証明 盤面の大きさに関わらず、チョンプは先手必勝。 証明：先手と後手のどちらかが必勝。後手が必勝と仮定すると・・・

17 先手必勝の証明 盤面の大きさに関わらず、チョンプは先手必勝。 証明：先手と後手のどちらかが必勝。後手が必勝と仮定すると・・・

18 先手必勝の証明 盤面の大きさに関わらず、チョンプは先手必勝。 証明：先手と後手のどちらかが必勝。後手が必勝と仮定すると・・・

19 先手必勝の証明 盤面の大きさに関わらず、チョンプは先手必勝。 シンプルな証明が存在するが、具体的な必勝手順が分かっていない。
証明：先手と後手のどちらかが必勝。後手が必勝と仮定すると・・・ シンプルな証明が存在するが、具体的な必勝手順が分かっていない。

20 チョンプの簡単な負け型（１） 2×n、n×nの盤面に対して、必勝手順が発見されている。 2×n 用語の説明
勝ち型：必勝手順が存在する　（次に動くプレイヤーが勝ち） 負け型：そうでない場合　（次に動くプレイヤーが負け） 2×n 先手は最初に、右下の１つのブロックだけを食べる。 １行目が２行目より１つだけ多い形が負け型。 具体例を書き、負け型の説明をする。

21 チョンプの簡単な負け型（２） n×n 3×n 先手は最初に、左から２番目、上から２番目のチョコを選ぶ。
縦と横のブロック数が同じものが負け型。 3×n 一般には知られていない。

22 発表構成 チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値

23 ３行チョンプ（１） ３行チョンプについて、負け型を列挙する。 ２行チョンプの場合（３行目が０個） ３行目が１個の場合 ３行目が２個の場合
２行目の数が少ないものから順に並べる。 ２行チョンプの場合（３行目が０個） ３行目が１個の場合 ３行目が２個の場合

24 ３行チョンプ（１） ３行チョンプについて、負け型を列挙する。 ２行チョンプの場合（３行目が０個） ３行目が１個の場合 ３行目が２個の場合
２行目の数が少ないものから順に並べる。 ２行チョンプの場合（３行目が０個） 1,1,1,・・・ ３行目が１個の場合 2,0 ３行目が２個の場合 2,2,2,・・・

25 ３行チョンプ（１） ３行チョンプについて、負け型を列挙する。 ２行チョンプの場合（３行目が０個） ３行目が１個の場合 ３行目が２個の場合
２行目の数が少ないものから順に並べる。 ２行チョンプの場合（３行目が０個） 1,1,1,・・・ ３行目が１個の場合 2,0 負け型の列 ３行目が２個の場合 2,2,2,・・・

26 ３行チョンプ（２） さらに増やしたときの、負け型の列 ３行目が３個 3,3,0 ３行目が４個 4,4,4,0
３行目が３個 3,3,0 ３行目が４個　4,4,4,0 ３行目が５個　5,3,4,4,4,・・・ ３行目が６個　5,5,5,0 ３行目が７個　6,6,3,5,5,5,・・・ ３行目が８個　7,5,6,6,0 ３行目が９個　7,7,3,6,6,6,・・・ ０で終わるか、同じ数が無限に続くものが出てくる。 しかし、３行目が１２０個のとき・・・

27 ３行チョンプ（３） ３行目が１２０個の場合 70と72が交互に出てくる。 必ず周期的なものになるのでは？
86,84,85,85,79,84,84,72,83,83,83,67,82,82,　61,82,80,57,81,81,81,81,48,45,74,78,78,78,　38,78,76,77,77,77,26,76,28,76,74,75,18,75,　73,74,10,10,72,73,71,3,　72,70,72,70,72,70,72,70,・・・ 70と72が交互に出てくる。 必ず周期的なものになるのでは？ 半順序集合ゲーム周期性定理により、肯定的に証明された。

28 半順序集合ゲーム周期性定理[S.B. 2003] ３行目以下の形を固定 負け型の列は、次の２つのいずれかになる。 このpを周期と呼ぶ。
４行目、５行目、・・・があっても良い 負け型の列は、次の２つのいずれかになる。 0で終わる有限個の列 ある正整数pが存在して、 ２行目の個数bがある数より大きい場合はすべて、負け型の列のb番目とb+p番目は同じ数になる。 このpを周期と呼ぶ。 0で終わらない場合は、必ず周期をもつことになる。

29 ３行チョンプの周期性[A.E.Brouwer]
３行目が10000個のものまで、周期が計算されている。 右図は周期２以上のものの例。 ３行目が120個で最初に周期２． ３行目が402個で最初に周期４． ３行目が2027個で最初に周期３． ３行目が6541個で最初に周期９． ３行目が10000個以下のものの中で、最大の周期は９． 周期は、３行目の個数に対してかなり小さくなる。 今回の研究：３行とは異なる形のチョンプにも言えるか？

30 発表構成 チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値

31 ２行＋１列チョンプの周期性 ２行＋１列チョンプの負け型の公式[E.R.B. et al 1980] 周期が存在する場合、必ず周期１となる。
a+bが偶数のとき a+bが奇数のとき 周期が存在する場合、必ず周期１となる。 以下では、それ以外の形について、計算機を用いて周期を計算した結果を示す。

32 ２行＋２列チョンプの周期性 ２行＋２列チョンプで、周期が２以上になるもの

33 ４行チョンプの周期性 ４行チョンプで、周期が２以上になるもの ３行目以下の個数が比較的少ない場合でも、周期が大きくなる。
前に現れた周期の倍数となるような周期が出てくる。

34 発表構成 チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値

35 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

36 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

37 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

38 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

39 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

40 グランディ値について ゲームの途中の各盤面に対して定義される非負整数。 求め方 mex：集合に含まれない最小の非負整数 0ならば、負け型
動けない盤面：0 そうでない盤面：１手動いた後の盤面すべてのグランディ値のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々のグランディ値から容易に計算できる。

41 ２行チョンプのグランディ値 a+bが偶数のとき a+bが奇数のとき （証明は省略） 右図のようなゲームでも、必勝手順を求めることができる。
　　　　　　　　　　　　　　　（証明は省略） a b 右図のようなゲームでも、必勝手順を求めることができる。

42 まとめ 今後の課題 様々な形のチョンプについて、周期を計算した。その結果、３行のチョンプのものに比べて周期が非常に大きくなることが分かった。
２行チョンプのグランディ値を求める公式を発見した。 今後の課題 ３行目以下のブロックの数を固定した場合に、周期がどのようになるかを検証する。 ２行より大きいチョンプのグランディ値についての研究。