Problem H: Queen’s case

Slides:



Advertisements
Similar presentations
Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
Advertisements

G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
問題案 : 稲葉 解答:秋葉、稲葉.  「 + 」の辺を通ると所持金が 1 円増える  「 - 」の辺を通ると 1 円減る (文無しは通れ ない)  始点を0円で出て終点に0円で着く最短路 は?  |V| ≦ 250 =
原案 : 野田 解答 : 野田・山 口 問題文 : 野田 PROBLEM E: PSYCHIC ACCELERATOR ~ とある超能力の物体加速器~
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
Problem R: ツンデレチェッカー 問題作成・解説: 北村.
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
人工知能概論 第4回 探索(3) ゲームの理論.
ICPC夏合宿09 Day3 Problem D : Luigi‘s Tavern -ルイージの酒場-
連続系アルゴリズム演習 第2回 OpenMPによる課題.
Revenge of the Round Table
Day2 Problem I: Memory Match ~神経衰弱~
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
Alice in Foxland ~狐の国のアリス~
ICPC夏合宿09 Day2 Problem F Voronoi Island ~ボロノイ島戦記~
    有限幾何学        第8回.
Problem D: Double Sorting 原案: oxy, 解答作成: oxy, nya.
I: Tokyo Olympics Center
Intelligent Circular Perfect Cleaner(ICPC)
Princess, a Strategiest
Problem G : Entangled Tree
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
第8回  問題解決.
原案:阿部 担当:福澤, 笠原 英訳:寺島 解説:福澤
スーパー・シェイプ・ショット Super Shape Shot ゲームをつくろう <説明と進行>
JAG Regional Practice Contest 2012 問題C: Median Tree
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
原案: 矢藤(kohyatoh) 解答: 高原(rankalee, shimejitan), 矢藤 解説: 矢藤
政策決定のプロセス 政策過程論 公共選択 ゲームの理論.
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
Problem C: Princess' Japanese
2013年度模擬アジア地区予選 Problem E: Putter
Problem D: King Slime ~キングスライム~
Problem F Two-finger Programming
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
6.4 コード最適化 (1)コード最適化(code optimization)
原案・解説 : 野田 解答 : 野田・吉田 Problem D Futon ~布団~.
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
Bridge It と Connections の 必勝法について
情報論理工学 研究室 第10回 完全解析されたゲーム.
Problem I: Aaron と Bruce
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
Bridge It と Connections の 必勝法について
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
所属集団の変更できる社会的ジレンマ実験について2
モンテカルロ法を用いた 立体四目並べの対戦プログラム
問題作成、解説担当:中島 副担当:坪坂、松本
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
ORの手法ゲームの理論3 (Excelによるゲーム理論実習)
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
数値解析Ⅱ ~五目並べのプログラミング~ C班.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
7月13日の演習問題・解答例 について ネットワーク長が 18、22、26、28 の場合の
プログラミング 平成24年12月11日 森田 彦.
C問題 高所恐怖症 原案・ライタ : 伊藤 テスタ : 青木・西出.
人工知能概論 第4回 探索(3) ゲームの理論.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

Problem H: Queen’s case 原案:牟田 解答例:寺島・田村 英文:寺島 解説:寺島

Problem 女王が革命軍から逃げられるか判定する 王宮の地図と女王と革命軍の位置が与えられる 将棋のように交互に動く 女王が先手 1マス隣りに移動か待機 同じマスに重なると女王は捕まる 革命軍が動き終わった段階で,出口に女王が到達していると逃げられる 互いに最善手を取るとする

Sample1

Wrong Solution min-max探索 これだと経路に依存するので単純なキャッシュではアウト ループしたら引き分けと見なす FYI: GHI(Graph History Interaction) と呼ばれる問題で,いろいろ論文が存在する

Solution トポロジカルソート+min-max戦略 状態: (女王の位置, 革命軍の位置, 手番) 終端状態 捕縛: 女王と革命軍が同じ位置 逃走: 女王の手番に女王が出口にいて,革命軍が女王とは違う位置 確定できるところから順に結果を伝播させる

Solution (con’t) 捕縛条件 逃走条件: 確定しなかった場合,千日手となる 女王:次の手が全て捕縛 革命軍:次の手のいずれかが捕縛 逃走条件: 女王:次の手のいずれかが逃走 革命軍:次の手のすべてが逃走 確定しなかった場合,千日手となる

Result Submitted: 6 (2 teams) Solved: 1 First Accept: 278min (HITORI)

Edge case