著者

草野 一彦 成澤 和志 篠原 歩

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.108-113, 2010-11-12

---

立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す.

著者

小松 智希 成澤 和志 篠原 歩

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2012, no.8, pp.1-8, 2012-07-06

---

探索空間が非常に広く,評価関数が作りにくいゲームにおいて行動決定を行う手法にモンテカルロ法があり,囲碁や大貧民などのゲームに対して有効な手法であることがわかってきた.しかし,麻雀のように探索空間全体に対して得点が得られる組み合わせが少ないゲームでは,モンテカルロ法は報酬を得ることができるプレイアウトの回数が少ないため,十分な効果を発揮することができない.本論文では,麻雀におけるモンテカルロ法の非効率性を実験的に検証する.また,プレイアウトにおいて効率的に報酬を得ることができる手法を提案し,モンテカルロ法と比較することで実験的に有効性を示す.Monte Carlo methods have been successfully applied for playing games, and have outperformed previous algorithm in such games as Go and Daihinmin. However, as we will experimentally show, it is not very effective for some games like Mahjong, where random simulation can rarely get rewards. Without positive rewards, players have little reason to choose better actions. In this paper, we propose a new algorithm to overcome this difficulty. It virtually simulates many play-outs in each trial simultaneously, so that many of play-outs can get positive rewards, even for this kind of games. We show some preliminary experiments that convinced us that the approach is promising.

著者

小松 智希 成澤 和志 篠原 歩

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2012-GI-28, no.8, pp.1-8, 2012-07-06

---

探索空間が非常に広く,評価関数が作りにくいゲームにおいて行動決定を行う手法にモンテカルロ法があり,囲碁や大貧民などのゲームに対して有効な手法であることがわかってきた.しかし,麻雀のように探索空間全体に対して得点が得られる組み合わせが少ないゲームでは,モンテカルロ法は報酬を得ることができるプレイアウトの回数が少ないため,十分な効果を発揮することができない.本論文では,麻雀におけるモンテカルロ法の非効率性を実験的に検証する.また,プレイアウトにおいて効率的に報酬を得ることができる手法を提案し,モンテカルロ法と比較することで実験的に有効性を示す.

著者

海津 純平 吉仲 亮 篠原 歩

雑誌

ゲームプログラミングワークショップ2016論文集

巻号頁・発行日

no.2016, pp.154-157, 2016-10-28

著者

海津 純平 成澤 和志 篠原 歩

雑誌

ゲームプログラミングワークショップ2015論文集

巻号頁・発行日

vol.2015, pp.172-178, 2015-10-30

---

多人数不完全情報ゲームの一つである麻雀は,他プレイヤとの状況に応じて戦略を変更することが重要である.例えば,自分が大きく点差をつけられ順位が低いときは得点の高い役を狙う戦略が,自分がトップのときはゲームを早く終了させるための戦略が有効な戦略とされる.本論文では,プレイヤの戦略として捨てる牌の選択だけに着目するため,他プレイヤを排除した一人麻雀を考え,一人麻雀に対して一つのパラメータを変更することで打ち方を変えることができる手法を提案する.提案する手法は,小松らが提案したモンテカルロ法を改良した手法を基にしており,プレイアウトにおける報酬として,上がり点を高くするための評価指標と早上がりをするための評価指標の二つを組合せたものを用いている.また,計算機実験によって,計算時間および,上がり率,平均点数,上がった時の平均点数,平均上がり巡目に対する評価を行う.

著者

大川 貴聖 吉仲 亮 篠原 歩

雑誌

ゲームプログラミングワークショップ2017論文集

巻号頁・発行日

vol.2017, pp.50-55, 2017-11-03

---

人狼ゲームで勝利するためには,各プレイヤの役職を推定することが重要である.先行研究では,サポートベクターマシンを用いて人狼を推定する手法が提案された.本論文では,先行研究を基に,深層学習を用いて役職を推定するエージェントを提案する.学習で使用する特徴を増やし,学習モデルをサポートベクターマシンから多層パーセプトロンに変更した.また,計算機実験において,過去の人狼知能大会のエージェントと対戦し,その勝率と推定精度に対する評価を行った.その結果,提案手法が有効であることを確認した.

著者

海津 純平 成澤 和志 篠原 歩

雑誌

ゲームプログラミングワークショップ2015論文集

巻号頁・発行日

no.2015, pp.172-178, 2015-10-30

著者

竹田 正幸 篠原 歩

雑誌

情報処理

巻号頁・発行日

vol.43, no.7, pp.763-769, 2002-07-15

---

テキストデータを圧縮したままパターン照合を行う「圧縮テキスト上でのパターン照合」が新しい研究課題として脚光を浴びるようになった.本稿では,この課題に関する最新の研究成果について,理論と実用の両面から解説する.

著者

篠原 歩 宮野 悟

出版者

一般社団法人情報処理学会

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.32, no.3, pp.p257-263, 1991-03-15

被引用文献数

4

著者

ディプタラマ 石黒 裕也 成澤 和志 篠原 歩 ジョーダン チャールズ

雑誌

ゲームプログラミングワークショップ2015論文集

巻号頁・発行日

vol.2015, pp.154-161, 2015-10-30

---

一般化三並べはFrank Hararyによって提案された2人完全情報ゲームであり,碁盤面上に先手後手が交互に石を1つずつ置き,あらかじめ定められた動物を先に作ったプレイヤが勝ちというゲームである.2人完全情報ゲームの勝敗判定問題は与えられたゲームに対して,先手必勝,後手必勝または引き分けとなるかを判定する問題である.オセロや五目並べなど,多くの2 人完全情報ゲームの勝敗判定問題はPSPACE完全であることが知られている.それに対して,代表的なPSPACE 完全問題としてQuantified Boolean Formula (QBF) に対する充足可能性問題(TQBF)が存在し,TQBFを高速に解くプログラム,QBFソルバが開発されてきた.本研究では一般化三並べの拡張であるGTTT(p,q)およびTorusGTTT(m,n)の勝敗判定問題をTQBFに帰着し,QBFソルバを用いてゲーム勝敗判定問題を解く.ゲームのパラメータによっては既存のゲームの探索手法より,QBFソルバの方がより速く勝敗判定問題を解けることが見られた.

著者

小林 直樹 篠原 歩 佐藤 亮介 五十嵐 淳 海野 広志

出版者

東京大学

雑誌

基盤研究(S)

巻号頁・発行日

2015-05-29

---

本課題では、高階モデル検査の(1)理論的基盤の強化とそれに基づく高階モデル検査アルゴリズムの改良、(2)プログラム検証への応用、(3)高階モデル検査の拡張とそのプログラム検証への応用、(4)データ圧縮への応用、の4つを柱に研究を進めている。以下、それぞれの項目について、平成28年度(およびその繰越として遂行した平成29年度の一部の結果)について述べる。(1)理論的基盤の強化:HORSモデル検査とHFLモデル検査という2種類の高階モデル検査の間に相互変換が存在することを示すとともに、HFLモデル検査問題を型推論問題に帰着できることを示した。後者の結果に基づき、HFLモデル検査器のプロトタイプを作成した。また、高階文法の性質について調べ、語を生成するオーダーnの文法と木文法を生成するオーダーn-1の文法と間の対応関係を示した。さらに、高階モデル検査アルゴリズムの改良を行い、値呼びプログラムに対して直接的に高階モデル検査を適用する手法を考案、実装した。(2)プログラム検証への応用:プログラム検証で扱える対象プログラムや性質の拡充を行い、関数型プログラムの公平非停止性の検証、コード生成プログラムの検証、動的なスレッド生成を伴う高階並列プログラムの検証、などを可能にした。(3)拡張高階モデル検査:HORSに再帰型を加えて拡張したμHORSに対するモデル検査アルゴリズムの改良を行い、その有効性をJavaプログラムの検証を通して示した。(4)データ圧縮への応用:データをそれを生成する関数型プログラムの形に圧縮する方式(高階圧縮)について、圧縮後のプログラムをビット列に変換する部分の改良を行った。また、高階圧縮のための様々な要素技術について研究を進めた。

著者

八鍬 友貴 本田 耕一 篠原 歩

雑誌

ゲームプログラミングワークショップ2009論文集

巻号頁・発行日

vol.2009, no.12, pp.35-42, 2009-11-06

著者

松原 渉 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.12, pp.39-45, 2010-04-15

---

移調を許したマッチングとは,与えられたテキストとパタンに対して,任意のオフセットを許した移調パタンの出現を発見する問題であり,例として音楽検索が挙げられる.本研究では,移調を一般に文字の置き換え関数としてとらえ,任意の置換が与えられたとき,すべてのパタンを検出する問題について取り組む.入力のテキストとパタンは,文法圧縮の一種である直線的プログラム(SLP)で与えられるものとし,文字列を陽に展開することなく処理を完了する効率の良いアルゴリズムを与える.

著者

松原 渉 稲永 俊介 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.108, no.443, pp.9-16, 2009-02-23

---

平衡直線的プログラム(Balanced Straight line program,BSLP)は単元集合を生成する文脈自由文法とみなすことができ,そこで生成される文字列の長さNは,変数の個数nに対して指数的に長くなりうる.そのため,BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,BSLPとして表現された文字列の非反復性判定をO(max(n^2,nlog^2N))時間,O(n^2)領域で解くアルゴリズムを示す.

著者

津田 英隆 白井 英大 寺邊 正大 橋本 和夫 篠原 歩

出版者

一般社団法人 電気学会

雑誌

電気学会論文誌D(産業応用部門誌) (ISSN:09136339)

巻号頁・発行日

vol.129, no.12, pp.1201-1211, 2009-12-01 (Released:2009-12-01)

参考文献数

11

被引用文献数

4 5

---

The conventional semiconductor yield analysis is a hypothesis verification process, which heavily depends on engineers' knowledge. Data mining methodology, on the other hand, is a hypothesis discovery process that is free from this constraint. This paper proposes a data mining method for semiconductor yield analysis, which consists of the following two phases: discovering hypothetical failure causes by regression tree analysis and verifying the hypotheses by visualizing the measured data based on engineers' knowledge. It is shown, through experiment under the real environment, that the proposed method detects hypothetical failure causes, which were considered practically impossible to detect, and that yield improvement is achieved by taking preventive actions based on the detected failure causes.

著者

竹田 正幸 篠原 歩 坂内 英夫 瀧本 英二 坂本 比呂志 畑埜 晃平 稲永 俊介

出版者

九州大学

雑誌

基盤研究(B)

巻号頁・発行日

2010

---

本研究では,圧縮データ処理に基づいて軽量XMLデータベース管理システム(DBMS)のための基盤技術を確立することを目標とし,主として以下の成果を得た.(1) 高速で軽量なオンライン文法圧縮アルゴリズムの開発. (2) 圧縮データ上で動作するq-グラム頻度計算アルゴリズムの開発. (3) 高速XMLデータストリームフィルタリング技術の開発. この他,DBMSの備えるべき知的データ処理機能として,パターンの効率的な枚挙,分類,オンライン予測等に関する研究を行い,多くの成果を得ている.

著者

稲永 俊介 船本 崇 竹田 正幸 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.622, pp.29-36, 2004-01-22

---

文字列の文法に基づく圧縮とは,与えられたテキストを生成する文法を構築することによってデータのサイズを縮小する圧縮法である.この中で長さ優先置換法とは,テキスト中の部分文字列のうち,重複なく複数回現れている最長のものを生成規則として別の一文字に置換していくものである.本論文では,文字列に対する索引構造の一つである接尾辞木に対して極めて技巧的な構造の更新を行うことにより,この長さ優先置換を線形時間で行うアルゴリズムを提案する.