碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .

Slides:



Advertisements
Similar presentations
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
Advertisements

 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
JMP version5(以上) 日本語版のScripting Languageによる プログラミング
初年次セミナー 第13回 2次元グラフィックス(1).
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
コンピュータ囲碁の仕組み ~ 将棋との違い ~
ブロック運びゲーム.
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
半順序集合ゲーム周期性定理の拡張 京都大学情報学研究科 ○後藤順一 伊藤大雄.
図形描画の基本図形(四角)を組み合わせて、家の形を作ります。
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
第8回  問題解決.
飛び越しゲーム 計算数理2演習 課題1 2011年度(阿原).
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
モンテカルロ法と囲碁・将棋ソフトの人知超え
模擬国内予選2014 Problem C 壊れた暗号生成器
A path to combinatorics 第6章前半(最初-Ex6.5)
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
情報論理工学 研究室 第6回: リバーシの合法手生成.
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
~オセロゲーム~ アルゴリズムとそのプログラム
思考力・表現力を高める 学習の流れ 本時のねらい 「数学的活動を通して思考力・表現力を高める」 ↓
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
Bridge It と Connections の 必勝法について
情報論理工学 研究室 第10回 完全解析されたゲーム.
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
千葉大学 理学部数学・情報数理学科 松井宏樹
フィルム ストリップ (中級)   このスライドの効果を再現するには、次の操作を行います。
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
強化学習を用いたバックギャモンプレイヤーの生成 TD-Gammon
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
京都大学大学院情報学研究科 宮川博光 伊藤大雄
Bridge It と Connections の 必勝法について
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
色塗りゲームとゲームカラーリング数 慶應義塾大学大学院 理工学研究科   関口 陽介.
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
SystemKOMACO Jw_cad 基本操作(3) Ver.1
A path to combinatorics 第3章後半(Ex3.8-最後)
Smart Graphic Layout トピック ステートメント 赤色の背景に画像を含む SmartArt グラフィック (中級)
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
指導手順 1 サッカーくじの説明をする。 2 実際に10口まで予想させる。 3 実際のくじ結果をみる。
博士たちの愛する円周率 徳山 豪 東北大学 “PI” that professors love
リバーシ 06a1056 藤田将義.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
or-8. ゲーム理論 (オペレーションズリサーチを Excel で実習するシリーズ)
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
分割制限ニム 山崎浩一*、五十嵐善英*、塚村善弘 *群馬大学理工学部.
ゲーム理論 ー 駆け引きの科学 - (2) 展開形のゲーム
Othello G班         山崎 木下 山本 上手      .
博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
情報論理工学 研究室 第8回: ミニマックス法.
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
岡圭吾(東京大学) 稲葉直貴(タイムインターメディア) 飯野玲(日本評論社)
アルゴリズム ~すべてのプログラムの基礎~.
プログラミング論 バイナリーサーチ 1.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
ペンシルパズルの大道芸ステージショーへの応用
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

碁石ゲームに関する考察 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

基本手筋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