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