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