京都大学大学院情報学研究科 宮川博光 伊藤大雄

Presentation on theme: "京都大学大学院情報学研究科 宮川博光 伊藤大雄"— Presentation transcript:

1 京都大学大学院情報学研究科 宮川博光 伊藤大雄
スネーキーの置き石1の必勝法 京都大学大学院情報学研究科 宮川博光　　伊藤大雄　

2 今日の流れ 一般化三目並べの概要 スネーキーの詰み 勝ち型1~3の紹介 先手の初期(1~4手)の配置 初期の配置から勝ち型までの流れ(概要)
まとめと今後の課題

3 一般化三目並べの概要 ルール 碁盤状の盤面 盤面の大きさは無限大 先手と後手が交互に石を打つ 予め定められたある形を作る
4 5 1A 1B 1C 1D 1E 1 4 7 1 2 3 4 5 1F 1G 1H 1I 1J 2 5 8 3 6 9 2A 2B 2C 2D 2E 一般化三目並べの概要 ルール 碁盤状の盤面 盤面の大きさは無限大 先手と後手が交互に石を打つ 予め定められたある形を作る 回転と反転はOK(斜めは×) 先にその形を作れば勝ち 黒石が先手、白石が後手

4 一般化三目並べの概要 勝ち型 負け型 両者が最善の手を尽くしたとき先手必勝である形 例： 無限に続けても決着が着かない形 負け型を含む形 4
5 1A 1B 1C 1D 1E 1 4 7 1 2 3 4 5 1F 1G 1H 1I 1J 2 5 8 3 6 9 2A 2B 2C 2D 2E 一般化三目並べの概要 勝ち型 両者が最善の手を尽くしたとき先手必勝である形 例： 負け型 無限に続けても決着が着かない形 負け型を含む形

5 一般化三目並べの概要 負け型の証明 負け型の証明には畳敷き戦略を利用 未解決 スネーキー

6 一般化三目並べの概要 置石 ハンディキャップ数 互いに打ち始める前に、先手が盤面上に置く黒石 勝ち型になる必要最小限の置き石数 例：
ハンディキャップ数２ ハンディキャップ数２以下

7 一般化三目並べの概要 置石 ハンディキャップ数 互いに打ち始める前に、先手が盤面上に置く黒石 勝ち型になる必要最小限の置き石数 例：
ハンディキャップ数２ ハンディキャップ数１

8 今日の流れ 一般化三目並べの概要 スネーキーの詰み 勝ち型1~3の紹介 先手の初期(1~4手)の配置 初期の配置から勝ち型までの流れ(概要)
まとめと今後の課題

9 スネーキーの詰み リーチ(先手)：後手が抑えないと負けが決まる

10 スネーキーの詰み ダブルリーチ：リーチが２箇所。後手の負けが決まる

11 今日の流れ 一般化三目並べの概要 スネーキーの詰み 勝ち型1~3の紹介 先手の初期(1~4手)の配置 初期の配置から勝ち型までの流れ(概要)
まとめと今後の課題

12 勝ち型1,2,3の紹介 超重要！ 後手が打ち終わったあと、以下の５つの盤面になったときに
4 5 1A 1B 1C 1D 1E 4 7 4 5 1F 1G 1H 1I 1J 5 8 3 6 9 2A 2B 2C 2D 2E 勝ち型1,2,3の紹介 後手が打ち終わったあと、以下の５つの盤面になったときに 先手の勝ちが決まる。これを勝ち型1,2,3と呼ぶことにする 超重要！ 1 1 3 2 2 勝ち型１ 勝ち型２

13 勝ち型1,2,3の紹介 勝ち型３ 先手が６手、後手が５手打った後に以下の条件を満たすときを考えている 斜線には後手の白石が１つ以上ある
赤線上に後手の白石が１つある 先手の黒石は一直線上に５つ並んでいる 斜線には後手の白石が２つ以上ある 赤線上には後手の白石が１つもない 先手の黒石は一直線上に５つ並んでいる

14 勝ち型１の証明 1A 1G 1B 1 2 1 2 3 2 1A 1B 1C 1D 1E 1F 1G 1 2B 2 2B 1C 1 2A

15 2 1C 2 2B 1C 3 1 2A 1 3 1 1D 2 2 2 2 3 3 2 1 1D 4 3 2 1 1D 4 3 1 1D 3

16 2 1 3 2 1 1 2 1E 1E 1E 3 2 2 1 4 3 1 1 2 1F 1F 1F

17 勝ち型１の補足 両者は勝ち型1である。左側の図は必ず右図にすることが可能。 1 3 4 5 1A 1B 1C 1D 1E 4 7 1 2 3
1F 1G 1H 1I 1J 5 8 3 6 9 勝ち型１の補足 両者は勝ち型1である。左側の図は必ず右図にすることが可能。 2 1 2 1

18 今日の流れ 一般化三目並べの概要 スネーキーの詰み 勝ち型1~3の紹介 先手の初期(1~4手)の配置 初期の配置から勝ち型までの流れ(概要)
まとめと今後の課題

19 先手の初期(1~4手)の配置 1A 1B 1 1C 1A 1C 1B 2G 1A 2A 2F 1B 2G 2F 1 2B 2E 1 2A
2D 2 2B 2E 2 2A 2D 2C 2D 2C 2B

20 先手の初期(1～4手)の配置 1A 1A 1 1 1 1C 2 2C 2E 2 2 2C 2G 1A 2A 2F 1B 2G 2F 1 2B
2D 2 2B 2E 2 2A 2D 2C 2D 2C 2B

21 先手の初期(1～4手)の配置 後手 白石が指定の場所に１つ A~Eの枠のどこかに１つ D A A B E B D E C C A

22 先手の初期(1～4手)の配置 反転させれば同じ 1A 1A 1 1 1 1C 2 2C 2E 2 2 2C 1A 1A 3 1 3 1 3

23 先手の初期(1～4手)の配置 1A 1A 1 1 1 1C 2 2C 2E 2 2 2C 3I 3J 1A 3A 3I 3J 1A 3A
3H 3 1 3B 3H 3 1 3B 3G 2 2C 2E 2 3C 3F 3E 3D 3C 3G 3F 3E 3D

24 先手の初期(1～4手)の配置 後手 黄色の枠： 　枠２つで白石２つ 赤色の枠： 　枠２つで白石１つ 透明の枠： 　枠１つで白石１つ

25 今日の流れ 一般化三目並べの概要 スネーキーの詰み 勝ち型1~3の紹介 先手の初期(1~4手)の配置 初期の配置から勝ち型までの流れ(概要)
まとめと今後の課題

26 初期の配置から勝ち型まで 基本的方針（E以外） 一直線上に２つ隣り合わせで並ぶ黒石の両端に 白石がない(赤線)ケースが必ずある。
黒石を一直線上に４つ以上並べることが可能 D A A B E B D E C C A

27 勝ち型１ 勝ち型３ 勝ち型２ 1C 2B 1A 1 1B 1A 1 2 2A 1A 1 2 2A 1Cは1A,1B以外 2Bは2A以外 2B
3 3 勝ち型３ 勝ち型２

28 2 3 2 1 1B 勝ち型３ 2B 1C 2B 1C 2A 2 1 3 2 1 2Bは2A以外

29 初期の配置から勝ち型まで 基本的方針 赤線上には白石がな いため、黒石を４つ以 上並べることが可能。 別の方法

30 1Cは1A,1B以外 2Bは2A以外 勝ち型１ 勝ち型２ 1B 2B 1C 1 1A 2A 2 1 1A 2B 2A 2 1 1A 2A 2
3 2 1 1A 3 3 勝ち型１ 勝ち型２

31 4 5 1A 1B 1C 1D 1E 1 4 7 1 2 5 1F 1G 1H 1I 1J 5 8 6 9 2A 2B 2C 2D 2E 1B 1B 1B 1 4 3 1 2 2 1 2 2 3 勝ち型１ 1C 1 2

32 まとめ 今後の課題 スネーキーの置き石１の必勝法の概要を示した スネーキーのハンディキャップは１以下であることを 示した
　スネーキーのハンディキャップ０は勝ち型？負け型？