２行＋αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄 発表構成 • • • • チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値 発表構成 • • • • チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 先手 チョンプとは • 長方形の板チョコを、２人が交互に食べていくゲーム。 • 左上のブロックが毒チョコ • 各手番でプレイヤーは１つのブロックを選び、その右や下に あるブロックを全て食べる。 • 毒チョコを食べざるを得なくなったプレイヤーの負け。 後手が毒チョコを食べざるを得ない 先手の勝ち！ 先手必勝の証明 • 盤面の大きさに関わらず、チョンプは先手必勝。 – 証明：先手と後手のどちらかが必勝。後手が必勝と仮定する と・・・ 先手必勝の証明 • 盤面の大きさに関わらず、チョンプは先手必勝。 – 証明：先手と後手のどちらかが必勝。後手が必勝と仮定する と・・・ 先手必勝の証明 • 盤面の大きさに関わらず、チョンプは先手必勝。 – 証明：先手と後手のどちらかが必勝。後手が必勝と仮定する と・・・ 先手必勝の証明 • 盤面の大きさに関わらず、チョンプは先手必勝。 – 証明：先手と後手のどちらかが必勝。後手が必勝と仮定する と・・・ 先手必勝の証明 • 盤面の大きさに関わらず、チョンプは先手必勝。 – • 証明：先手と後手のどちらかが必勝。後手が必勝と仮定する と・・・ シンプルな証明が存在するが、具体的な必勝手順が分 かっていない。 チョンプの簡単な負け型（１） • 2×n、n×nの盤面に対して、必勝手順が発見されている。 • 用語の説明 – 勝ち型：必勝手順が存在する （次に動くプレイヤーが勝ち） – 負け型：そうでない場合 （次に動くプレイヤーが負け） • 2×n – 先手は最初に、右下の１つのブロックだけを食べる。 – １行目が２行目より１つだけ多い形が負け型。 チョンプの簡単な負け型（２） • n×n – 先手は最初に、左から２番目、上から２番目のチョコを選ぶ。 – 縦と横のブロック数が同じものが負け型。 • 3×n – 一般には知られていない。 発表構成 • • • • チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値 ３行チョンプ（１） • ３行チョンプについて、負け型を列挙する。 – ２行目の数が少ないものから順に並べる。 • ２行チョンプの場合（３行目が０個） • ３行目が１個の場合 • ３行目が２個の場合 ３行チョンプ（１） • ３行チョンプについて、負け型を列挙する。 – ２行目の数が少ないものから順に並べる。 • ２行チョンプの場合（３行目が０個） • ３行目が１個の場合 2,0 • ３行目が２個の場合 2,2,2,・・・ 1,1,1,・・・ ３行チョンプ（１） • ３行チョンプについて、負け型を列挙する。 – ２行目の数が少ないものから順に並べる。 • ２行チョンプの場合（３行目が０個） • ３行目が１個の場合 1,1,1,・・・ 2,0 負け型の列 • ３行目が２個の場合 2,2,2,・・・ ３行チョンプ（２） • • • • • • • • さらに増やしたときの、負け型の列 ３行目が３個 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,・・・ • ０で終わるか、同じ数が無限に続くものが出てくる。 • しかし、３行目が１２０個のとき・・・ ３行チョンプ（３） • ３行目が１２０個の場合 – 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が交互に出てくる。 • 必ず周期的なものになるのでは？ • 半順序集合ゲーム周期性定理により、肯定的に証明された。 半順序集合ゲーム周期性定理[S.B. 2003] • ３行目以下の形を固定 – • ４行目、５行目、・・・があっても良い 負け型の列は、次の２つのいずれかになる。 1. 0で終わる有限個の列 2. ある正整数pが存在して、 ２行目の個数bがある数より大きい場合 はすべて、負け型の列のb番目とb+p番目は同じ数になる。 • • このpを周期と呼ぶ。 0で終わらない場合は、必ず周期をもつことになる。 ３行チョンプの周期性[A.E.Brouwer] • ３行目が10000個のものまで、周期が計算 されている。 – – – – – – 右図は周期２以上のものの例。 ３行目が120個で最初に周期２． ３行目が402個で最初に周期４． ３行目が2027個で最初に周期３． ３行目が6541個で最初に周期９． ３行目が10000個以下のものの中で、最大の周 期は９． • 周期は、３行目の個数に対してかなり小さく なる。 • 今回の研究：３行とは異なる形のチョンプに も言えるか？ 発表構成 • • • • チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値 ２行＋１列チョンプの周期性 • ２行＋１列チョンプの負け型の公式[E.R.B. et al 1980] • a+bが偶数のとき • a+bが奇数のとき • 周期が存在する場合、必ず周期１となる。 • 以下では、それ以外の形について、計算機を用いて周期を 計算した結果を示す。 ２行＋２列チョンプの周期性 • ２行＋２列チョンプで、周期が２以上になるもの ４行チョンプの周期性 • ４行チョンプで、周期が２以上になるもの • ３行目以下の個数が比較的少ない 場合でも、周期が大きくなる。 • 前に現れた周期の倍数となるよう な周期が出てくる。 発表構成 • • • • チョンプとは ３行チョンプと周期性 ３行以上のチョンプの周期性 ２行チョンプのグランディ値 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 グランディ値について • • ゲームの途中の各盤面に 対して定義される非負整数。 求め方 1. 2. • • • • 動けない盤面：0 そうでない盤面：１手動いた後 の盤面すべてのグランディ値 のmex mex：集合に含まれない最小の非負整数 0ならば、負け型 正の数ならば、勝ち型 複数のゲームを並行して行うゲームのグランディ値は、個々 のグランディ値から容易に計算できる。 ２行チョンプのグランディ値 • a+bが偶数のとき a 2a b g 1 2 • a+bが奇数のとき 2a b 3(a b 1) g min 1 , 2 2 （証明は省略） • 右図のようなゲームでも、 必勝手順を求めることが できる。 b まとめ • 様々な形のチョンプについて、周期を計算した。その結果、３ 行のチョンプのものに比べて周期が非常に大きくなることが 分かった。 • ２行チョンプのグランディ値を求める公式を発見した。 今後の課題 • ３行目以下のブロックの数を固定した場合に、周期がどのよ うになるかを検証する。 • ２行より大きいチョンプのグランディ値についての研究。
© Copyright 2024 ExpyDoc
