絵画的迷路生成のある拡張 2010 3/1 組合せゲーム・パズルミニ研究集会池田心（北陸先端大）本題に入る前に・・・ 1 去年は・・・人間の対戦相手としてのゲームアルゴリズム，話題提供 2009 3/3 組合せゲーム・パズルミニ研究集会池田心（京都大学） 2 自己紹介 • • • • 学部は数学科大学院は知能システム科学専攻現在は京大学術情報メディアセンター助教昔からゲーム好き，パズル好き，プログラム好き．囲碁五段． →当然，最強の囲碁プログラムを目指すことに． 3 ということで・・・絵画的迷路生成のある拡張 2010 3/1 組合せゲーム・パズルミニ研究集会池田心北陸先端大情報科学研究科ゲーム情報学分野囲碁やるぞ～～！！ 4 今回の話：絵画的迷路生成 • 解いた結果が好みの絵となる迷路の生成法（岡本先生の前回の発表）に感銘を受けて • いくつかの課題 – 入り口出口が隣になる – 左手法で解けてしまう – 迷路の難しさの指標？ 5 2ｘ2 から 3ｘ3 へ • 2ｘ2の解像度だと「すれ違い」ができない • じゃあ 3x3 にしよう 6 作成手順 1. 2. 3. 4. 入り口と出口を一本の3x3タイルで結ぶ絵の部分を作る絵じゃない部分を作る変換をかけて綺麗な迷路にする 7 １．入り口と出口を一本に結ぶ • 絵の部分の全域木を作り，指定の入り口・出口を結ぶルートを発見 • その部分だけを3x3タイルで埋めていく 8 ２．絵の部分を作る • Step1で作った木を使う．幹に枝が生えている形になるので，枝を迂回させて幹に戻るループを作る歯っ欠けは最後まで残る 9 ３．絵じゃない部分を作る • Step2と同様，葉をはやしていく • 正解ルートには１穴で，不正解ルートには１穴または２穴で接続する • 作り方を似せることで正解・不正解が遠目にわかりやすくなることを防ぎたい 10 簡単すぎない迷路のために • 不正解部を作る際にはバイアスをかける • 長すぎる木，短すぎる木，大きすぎる木は，迷路を簡単にする 11 ４．変換をかけて綺麗な迷路に • このままでは 3x3 のタイルが目立つ • 正解部分が変わらない変換をかける 12 ４．変換をかけて綺麗な迷路に • 不正解部分は前回も指摘があったのでこれを拡張 • 変化の多様性が向上，行き止まりまでの長さも「短すぎず長すぎず」に調整する 13