著者

草野 一彦 成澤 和志 篠原 歩

雑誌

ゲームプログラミングワークショップ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

---

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

著者

海津 純平 成澤 和志 篠原 歩

雑誌

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

巻号頁・発行日

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

---

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

著者

成澤和志 山田 泰寛 池田 大輔

出版者

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

雑誌

情報処理学会研究報告情報学基礎(FI) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.59, pp.45-52, 2006-05-30

---

プログの増加が著しい近年、プログスパムが大きな問題であり、スパム検出の技術の発達が求められている。スパム検出に関する研究は内容解析やリンク解析によるものが多く、複雑な処理やアルゴリズムを使用する。我々はプログスパムの内容ではなく、コピーされ大凰に生成される性質に着目した手法を提案する。テキストの部分文字列を数え上げた時、出現頻度と異なり数にはジップの法則が成り立つことを利用して、自然言語の知識を必要としない、高速なスパム検出の技術を得ることができる。また、我々は人エ的なデータによる本手法の正当性を調ぺ、実際のプログデータから本手法によりプログスパムを検出することに成功した。Blog spam detection is a key for the blog spam problems as the number of blog sites is extermery in creasing.Existing methods for blog spam detection are based on contexts o rlinkstructures analysis,and does not work well completely.We suggest a method utilizing thefact that spamsaremassproducedatalowcostinsteadoftheircontext・Ourmethoddoesnot need backgroundknowledge of blog entries,such as naturallanguages,because of usingZipf's law for the frequency and the vocabulary size of substrings.We present the validity of our method by artificial data set,and succeed to detect blog spamsftomactualblogentries.

著者

海津 純平 成澤 和志 篠原 歩

雑誌

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

巻号頁・発行日

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

著者

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

雑誌

ゲームプログラミングワークショップ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ソルバの方がより速く勝敗判定問題を解けることが見られた.

著者

成澤 和志

出版者

情報処理学会 ; 1960-

雑誌

情報処理 : 情報処理学会誌 : IPSJ magazine (ISSN:04478053)

巻号頁・発行日

vol.57, no.5, pp.470-476, 2016-05

著者

竹田 正幸 定兼 邦彦 坂本 比呂志 瀧本 英二 坂内 英夫 稲永 俊介 喜田 拓也 畑埜 晃平 井 智弘 中島 祐人 成澤 和志

出版者

九州大学

雑誌

基盤研究(A)

巻号頁・発行日

2013-04-01

---

爆縮とは工学用語で,爆発の圧力が;外側ではなく内側へ集中する現象をいい,通常では得難い物理現象を発生させるために利用される.本研究では,膨れ上がるデータを爆発的に凝縮することにより,(i) データ量削減, (ii) データ処理の高速化,(iii) 知識獲得の三つを達成する基盤技術の確立を目指し,これを情報爆縮 (information implosion) と名付けた.情報爆縮基盤技術の確立のために,(A)高速データストリーム圧縮アルゴリズム,(B)圧縮データ上の高速データ処理アルゴリズム,(C)大規模データ解析アルゴリズムという3つの研究項目をおいて研究開発を行い多くの成果を得た.

著者

成澤 和志 稲永 俊介 坂内 英夫 竹田 正幸

出版者

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

雑誌

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

巻号頁・発行日

vol.107, no.24, pp.63-70, 2007-04-19

被引用文献数

1

---

本論文では,Blumerらによって提案された同値関係による同値類を計算する問題を考える.Blumerらはコンパクト有向無閉路文字列グラフ(CDAWG)と呼ばれる索引構造を定義するために同値類を利用した.同値類は本質的に等しく出現する冗長な部分文字列を集めた集合であるため,テキスト解析において有用である.本論文では,接尾辞配列を用いて同値類を計算するアルゴリズムを提案する.提案アルゴリズムでは,接尾辞木および接尾辞リンク木の巡回を模倣するため接尾辞配列の他に2つの補助配列を使用するが,これら以外のデータ構造を必要としない.このアルゴリズムは入力文字列に対して,線形時間および線形領域で動作する.本論文では,提案アルゴリズムと接尾辞木およびコンパクト有向無閉路文字列を用いたアルゴリズムとの計算時間・計算領域を計算機実験によって比較する.