碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学)
パターン生成ゲーム 伊藤さんの数理解析研究所でのセミナー 黒(先手)と白(後手)が碁盤上に互いに石を置く(スライドでは、黒は青く、白は赤い) 先手が指定されたパターンを作れば勝ち 後手は邪魔をして守りきれば勝ち 後手がパターンを作っても勝ち(反撃あり) 後手のパターン生成は無視(反撃なし) 伊藤さんの数理解析研究所でのセミナー
五目並べ 縦横、対角線、逆対角線に5連を作れば勝ち 反撃あり 、15x15の盤 (交差点に石を置く) 反撃あり 、15x15の盤 (交差点に石を置く) パターンが出来なければ、満局(通常白勝ち) 三十数手程度で先手勝ちが示されている。 1993年にコンピュータプログラム化 連珠: 複雑(五珠2箇所打ちルールなど) 満局を引き分けにすることもある 6目並べ:後手の勝ち(つまり満局)? 7目並べならたぶん証明できるが。。。
浦月定石の典型例 15 16 19 11 6 13 5 2 17 10 9 7 1 18 12 8 14 3 4
花月定石の典型例 6 2 3 4 8 14 1 11 12 9 5 13 16 15 23 7 24 18 10 17 22 19 21 20 25
(斜めなし)4目並べ 縦横に4連を作れば勝ち 先手必勝 先手が6手(反撃なし)または7手(反撃あり)で勝てる
4 4 1 2 1 2 7 3 8 3 7 5 6 5 6 後手の反撃が無ければ4手(あと2手)で2-2が出来る 後手の反撃含みの防ぎ
5 6 1 2 7 3 4 後手の反撃が無ければ4手で2-2が出来る
4 4 1 2 1 2 3 5 6 3 5 6 7 7 後手の反撃があっても5手で2-3が出来る 後手の反撃があっても5手で2-3が出来る
7 7 1 2 1 2 3 5 6 3 5 6 4 4 後手の反撃があっても5手で2-3が出来る 後手の反撃があっても5手で2-3が出来る(連珠の花月定石と似ている)
斜めなし5目ならべは? 後手の反撃が無くても後手が勝ち 数学的にエレガントな証明 (伊藤さんの講演) 局部戦略でOK 白は直前黒の着手の 数学的にエレガントな証明 (伊藤さんの講演) 局部戦略でOK 白は直前黒の着手の 隣接点に打つ どの隣接点かは タイリングで指定
斜めなし5目ならべは? 後手の反撃が無くても後手が勝ち 数学的にエレガントな証明 ドミノタイリング を用いる
ドミノ以外のタイリング 斜めなし5目並べ後手勝ち 別証明 3x3タイリングを 用いる
疑問: 横4または縦5だと? 定理?? 後手の反撃が無いと先手が勝ち 予想 後手の反撃があれば後手が勝ち 疑問: 横4または縦5だと? 定理?? 後手の反撃が無いと先手が勝ち 予想 後手の反撃があれば後手が勝ち 横4または縦7: 反撃なしでも後手勝ち 証明:ドミノタイリングを用いる 横4または縦6: たぶん反撃なしでも後手勝ちだが、証明は不明。 巨大タイリングを用いて計算機をぶん回せば多分。。。
横4または縦5 (反撃なし版) 定理 後手の反撃が無いと先手が勝ち いくつかの捕題を用いて、最後は各個撃破での証明(??)
基本事項 基本事項2: 横に二連または縦に三連ができたら、後手はどちらかの端を止める必要がある。 飛び二、飛び三は真ん中もしくは端を止める 基本事項1: ゲームは単調 ある局面が先手勝ちなら、黒石追加、もしくは白石削除を行った局面も先手勝ち(囲碁や将棋では成立しない条件) 基本事項2: 横に二連または縦に三連ができたら、後手はどちらかの端を止める必要がある。 飛び二、飛び三は真ん中もしくは端を止める
補題1: ある黒石の左半平面および右隣列に白石が無く、同列の上下にそれぞれ3枡と4枡空白があるとき、続けて黒が打てば黒勝ち 補題1: ある黒石の左半平面および右隣列に白石が無く、同列の上下にそれぞれ3枡と4枡空白があるとき、続けて黒が打てば黒勝ち 4 3 1 2
4 6 5 3 8 7 9 1 2
5 x △ 4 3 1 2
1 補題2.これでも勝ち
3 1 2 補題2の「証明」
補題の系 黒が離れたところに着手したときには、白はその近傍(隣接8近傍、△の位置、もしくは上下に距離2以下)に応手しないといけない x x 1 x x 1 x x x x x x x △ x △ △ x △ x x
最も基本の手筋(基本手筋1) 補題: 黒石が縦に2つ並んだ場合、次の2種類の図面は黒から打てば勝ち。
妙手あり
5 1 2 3 4 補題の系より勝ち
5 4 3 1 2
1
基本手筋2。 横に止まらない石が縦に2つ並ぶ下図は勝ち x 補題の系から勝ち 2 1 3
基本手筋2。 横に止まらない石が縦に2つ並ぶ下図は勝ち 基本手筋2。 横に止まらない石が縦に2つ並ぶ下図は勝ち 7 6 5 2 4 1 3
基本手筋2に対する最強の受け 2 1 3 4
2 1 x 6 3 x 4 14 13 5 9 10 12 11 7 15 16 18 8 17 19
2 1 6 3 4 x △ 5 9 10 11 7 12 8 基本手筋1に帰着 13
基本手筋2に対する次善の受け (解答略) 2 1 3 4
弱い受け(その1) 2 2 1 1 詳細略
5 2 1 3 手筋2で解決 4
2 1 4 3 5 手筋1で解決
弱い受け(その2) 解説不要? 2 2 1 1 3 3
2 1 3 4 5 手筋2で解決
2 1 4 3 5 手筋1で解決
中級の受け 3 1 2 4 2と4を入れ替えたものも同様
7 5 6 3 1 2 4 基本手筋1で解決
7 5 3 1 2 6 4 基本手筋1で解決
6 5 3 1 2 8 4 7 9 基本手筋2で解決
7 5 3 1 2 6 4
6 x 5 x 3 1 2 4 7 △
最強の受け 4 2 3 1
応手 4 2 1 3 A 5 C D B
最難関の変化 12 4 2 1 3 9 x 5 10 11 6 7 8 基本手筋2に帰着 13
最難関の変化その2 15 4 2 1 3 14 13 10 9 12 5 11 6 7 8 基本手筋1に帰着
4 2 1 3 6 5 8 12 10 7 9 11 13 14 15
4 2 1 3 6 5 8 12 7 9 10 11 13 14 15
以下はEasy Cases 13 4 2 1 3 10 9 x 6 5 11 8 7 12 基本手筋1に帰着
4 2 1 3 7 8 5 6 9 基本手筋1(変形)に帰着
その他の受け(難しくない) 4 4 3 1 2 3 1 2 Easy
8 2 1 3 4 5 6 7 9
9手目が少し難しい 15 10 2 1 3 4 11 12 9 5 6 13 7 14 8
10 2 1 3 4 14 11 9 12 5 6 13 7 8 15
10 2 1 3 4 11 9 12 5 6 13 14 7 8 15
11 2 1 3 4 9 5 6 10 7 8
8 7 9 10 2 1 3 4 6 5 11
6 2 1 3 4 5 7
15 9 13 10 11 7 12 8 14 2 1 3 4 5 6
15 9 10 13 7 8 12 11 14 2 1 3 4 5 6
問題点 証明になっているか?(誰か詳細を詰めて!) 計算理論の論文にはならない??? 後手反撃ありの場合は後手勝ちか? 考え方自体は計算理論の論文でも似たようなもの 後手反撃ありの場合は後手勝ちか? 必勝手順の盤面サイズはかなり大きい 横4、縦6はどうなんだろうか? ほかの組み合わせはどうだろうか? または は白勝ち など 縦五、横五、斜めkで後手必勝になるkは?
7目並べ 縦、横、斜めに7つ並べる 後手は反撃しない 後手勝ちか? アイデア: 4x4のタイリング 縦、横、斜めに7つ並べる 後手は反撃しない 後手勝ちか? アイデア: 4x4のタイリング 4x4の中で、縦横の4連、対角線4連、副対角線3連、さらに 「副副対角線の2連のうちの指定した2通り」がどれも出来ないことを示せばよい 計算機でチェックすればよいのだが。。。
4x4での攻防 防ぐ必要のある2連はAa と Bb 黒の1手目に対する白の応手は AaBbのどれか(他は負けそう)。 A B a b a a 黒の1手目の位置に対する白の応手のテーブル 3手目は、もう一つの2連候補をつぶす ちょっと怪しい。。。 A B B A B b a A a b a b