研究集会「組合せゲーム・パズル」,豊橋技術科学大学

Slides:



Advertisements
Similar presentations
画像処理・実習 第十四回:パターン認識 東海大学 情報理工学部 情報メディア学科 濱本和彦. 今回の内容 5. パターン認識 5.1 マッチングの原理 5.2 テンプレートマッチング 実習 相互相関とテンプレートマッチング.
Advertisements

オブジェクト指向 言語 論 第八回 知能情報学部 新田直也. 多相性(最も単純な例) class A { void m() { System.out.println( “ this is class A ” ); } } class A1 extends A { void m() { System.out.println(
ハニカム構造 ~六角形の秘密~ 1902 岡本 紗也加. 1 動機、目的 ・ 蜂は、なぜ六角形の形をした巣を作るのか。 他の図形にはない六角形の特徴や利点を深く知る!
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
Problem H: Queen’s case
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
折り紙幾何学 ~折り紙で数学を楽しもう~ 2903 木村 麻里.
曲面上のグラフの彩色 ~種数の増加,面の制限及び局所平面性~
半順序集合ゲーム周期性定理の拡張 京都大学情報学研究科 ○後藤順一 伊藤大雄.
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
円周率 98E13036  平川 芳昭.
プログラミング入門 手順を作る マイクロワールドEX講義用資料(ICT活用教育ICT活用教育研究所)
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
C09 ネットワーク問題のモデル化と アルゴリズムの研究
Problem D: King Slime ~キングスライム~
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
「六角大王」によるCG作成と Webページ制作
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
2.2.1 ブラベー格子 単位格子:原子が配列している周期的な配列の中で最も     単純で最小な単位    
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
拡張タングラムとラッキーパズルの凸配置について
第四回 ゲーム                 05A1054         前田嵩公.
~オセロゲーム~ アルゴリズムとそのプログラム
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
三角形や四角形ではない図形の 角の大きさの和を求めよう。.
Bridge It と Connections の 必勝法について
情報論理工学 研究室 第10回 完全解析されたゲーム.
米山研究室紹介 -システム制御工学研究室-
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
京都大学大学院情報学研究科 宮川博光 伊藤大雄
Bridge It と Connections の 必勝法について
中3数 三平方の定理の利用 内 容 2つの三角定規の3辺の比 平面図形への利用 座標平面上の2点間の距離を求める。
5 図形と合同 1章 三角形 §1 二等辺三角形         (4時間).
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
中学数学1年 5章 平面図形 §2 作図 (3時間).
正多角形の作図 プログラミングで多角形を描く方法を考えよう 1時間目.
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
学 正多角形のどんな性質を使えば,プログラミングで正多角形を描くことができるだろうか。
色塗りゲームとゲームカラーリング数 慶應義塾大学大学院 理工学研究科   関口 陽介.
モンテカルロ法を用いた 立体四目並べの対戦プログラム
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
円と正多角形 プログルをつかって学ぼう.
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
プログラミング入門 はじめてのタートルグラフィックス マイクロワールドEX講義用資料(ICT活用教育ICT活用教育研究所)
リバーシ 06a1056 藤田将義.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
分割制限ニム 山崎浩一*、五十嵐善英*、塚村善弘 *群馬大学理工学部.
ゲーム理論 ー 駆け引きの科学 - (2) 展開形のゲーム
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
岡圭吾(東京大学) 稲葉直貴(タイムインターメディア) 飯野玲(日本評論社)
C.岩崎雅哉 大須賀佑介 杉原雄太 中野武重 日名啓吾
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
ペンシルパズルの大道芸ステージショーへの応用
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

研究集会「組合せゲーム・パズル」,豊橋技術科学大学 正六角盤面上の一般化三並べ 東京電機大学 理工学部 入倉弘介  松浦昭洋   研究集会「組合せゲーム・パズル」,豊橋技術科学大学

ハラリイの一般化三並べ 三目並べを一般化した二人ゲーム m×m正方盤面で,n個のマスから成る図形 (n細胞生物)の完成を競う。 ○ × ○ × × ○ 斜めは認めない 先手必勝手順が存在する生物 = 勝ち型 先手必勝手順が存在しない生物 = 負け型

正六角盤面上の一般化三並べ ゲームに用いる盤面を正六角形に変更 move(α, m) : m×m×m盤面におけるn細胞生物α 3×3 正方盤面 2×2×2 正六角盤面 move(α, m) : m×m×m盤面におけるn細胞生物α                         の先手必勝手順の最小手数 負け型のとき、move(α, m) = ∞

3細胞以下の生物に対する結果 1細胞生物 one 3細胞生物 3I Rock Bow 1 2 b a 2細胞生物 two a b 2 1 move(one, 1) = 1 move(two, 1) = 2 move(Rock, 2) = move(Bow, 2) = 3 move(3I, m) = ∞ (m = 2) 3 (m > 3)

4細胞生物に対する結果 全て先手必勝 4細胞生物は以下の7通り move(α, m) = ∞ (m < 3) 6 (m > 4)

               の必勝法 3手で両端の空いた“Bow”を作ればよい。

    の必勝法 3手でRockを作れば、複数の完成形が可能 3 2 1

    の必勝法 3手でRockを作れば、2方向で完成形が可能 3 2 1

の6手での必勝法 3手め以降、環状にBowを作り続ける 5手勝利の不可能性 そのためには、4手で次の いずれかを作る必要あり。      の6手での必勝法 3手め以降、環状にBowを作り続ける  5手勝利の不可能性 そのためには、4手で次の いずれかを作る必要あり。 2面待ちにするのが不可能。 2 5 4 3 3 4

    の必勝法  a b c

    の必勝法(続)   i d,f c e k

5細胞生物に対する結果 5細胞生物は、以下の22通り B C D F G I J K L M N P Q R S T U V W X Y Z

5細胞生物に対する結果 5細胞生物は、以下の22通り 勝ち型 負け型 未解決

必勝法の分類 P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L どの3生物、4生物から“進化”させるか 生物 Rock P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L Bow 3I

     生物 P の必勝法 move(P, m) < 7 (m = 3) move(P, m) = 5 (m > 4)

     生物 B の必勝法 move(B, m) = 6 (m > 4) move(M, m) = 6 (m > 4)

     生物 J の必勝法 move(J, m) = 5 (m > 4) 生物G, Nも類似の方法。

     生物 Q の必勝法 move(Q, m) < 6 (m > 4) 生物Fも類似の方法。

生物 S の必勝法 move(S, m) < 7 (m > 4) move(T, m) = 6 (m > 4) move(U, m) < 7 (m > 4)

     生物 Y の必勝法 最長手数の手順 b move(Y, m) < 10 (m > 5)

     生物 V の必勝法 a

     生物 V の必勝法 b (b-m) (b-n) move(V, m) < 8 (m > 4)

     生物 L の必勝法 最長手数の手順 move(L, m) < 12 (m > 4)

5Xに対する後手の引き分け戦略 無限に広がる盤面を、隣り合う2つのマスをペアとし、階段状に並べる。 後手の戦略 ○ × × ○ どの方向の5マスも、ペアのマスを必ず1つ含む → 完成不可能

5Dに対する後手の引き分け戦略 × 〇 ○

5細胞生物に対するまとめ (1) m = 3 のとき、move(P, m) < 7 (2) m > 4 のとき、 move(α, m) = 5 (α = P, B, J, G, N, K) 6 (α = M, T) 6 (α = Q, F) 7 (α = S, U) 8 (α = V, W) 12 (α = L) < (3) m > 5のとき、move(Y, m) < 10 (4) move(α, m) = ∞ (α= D, X, m > 1)

まとめ 正六角盤面上で、5細胞以下の生物について 先手必勝法と後手の引き分け戦略を考察した。 課題  ・必勝か否か未解決の5細胞生物(R,C,Z,I)  ・上下限の改良 (注記) 本発表後、以下の文献で同じ問題に対する解析が行われ   ていることが判明した。同論文では、 R, C, Z, I, Y以外の生物に   ついて、先手必勝法と後手の引き分け戦略が示されている。   (盤面サイズに関する議論はない) J.-P. Bode, H. Harborth, “Hexagonal polyomino achievement”, Discrete Math., vol. 212 (1-2), pp. 5-18, 2000