著者

小松 秀平 小野 廣隆

巻号頁・発行日

2015-04-10 (Released:2015-04-10)

---

日本のジャンケンは,グー(石),チョキ(鋏),パー(紙)の3つの手によるものが一般的であるが,世界には4手以上からなるジャンケンが数多く存在する.しかしその中には明らかに他の手と比べ弱く,使うべきでない手(無駄な手)が含まれるものも多々ある.伊藤らは無駄な手のない4手以上のジャンケン(一般化ジャンケン)について有向グラフとしての特徴づけを行った.本研究では,一般化ジャンケンを2人ゼロ和ゲームとして定式化し,最適混合戦略の観点から一般化ジャンケンについて考察を行う.伊藤らの定めた無駄な手のないジャンケンであっても, 戦略的には無駄な手が存在し得ること, 戦略的に無駄な手が存在しないジャンケンは必ず奇数手からなることを示す.

著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

vol.2021, pp.130-137, 2021-11-06

---

本研究では一般化ぷよぷよの計算複雑度について考える.対象とするのは盤面サイズ,色数に関して一般化した,オフライン型パズルとしてのぷよぷよである.本研究ではこの一般化ぷよぷよにおける 2つの問題を取り上げる.1 つは全消し判定であり,もう一つは連鎖数最大化である.前者に関してはぷよ 2色(おじゃまぷよあり)の設定であっても NP 完全であることが,後者に関してはぷよ 4 色(おじゃまぷよあり)の設定でも NP 困難であることが示されている.特に後者に関しては,詳細な証明は公開されていないがぷよ 3 色(おじゃまぷよあり)の設定で,あるいはぷよ 5 色(おじゃまぷよなし)でも NP 困難であることが指摘されている.本研究ではこれらの結果をいくつかの側面から強化する.我々の結果は以下のとおりである: (1) 連鎖数最大化はぷよ 3 色(おじゃまぷよなし)でも NP 困難,(2) P≠NP の仮定の下で, ぷよ 4 色(おじゃまぷよあり)の連鎖数最大化に対しては近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズムは存在しない, (3) 全消し判定はぷよ 4 色(おじゃまぷよなし)でも NP 完全である.

著者

木谷 裕紀 大渡 勝己 小野 廣隆

雑誌

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

巻号頁・発行日

vol.2019, pp.258-265, 2019-11-01

---

単貧民とは,不完全情報多人数ゲームである大貧民を完全情報ゲームとして簡易化したものである.これまでの研究により,二人単貧民に関しては配られた手札からどちらが必勝プレイヤであるかどうかを線形時間で判定できることがわかっている.本研究では手札非公開で行う不完全情報単貧民において如何に「必勝戦略」を得るかについて考える.手札に関する情報が全くない場合,確定的な意味で「必勝戦略」を得ることは難しい.このため,本研究では相手の手札に関する部分的な情報を提供するオラクルの存在を許したモデルを定義し,そのオラクル存在下で必勝戦略が得られるかどうかについて考察する.相手がどの札を持っているかなどの情報がない状況でも,マッチング数と呼ばれるゲームの構造パラメータを得るオラクルさえあれば完全情報単貧民と同様の必勝戦略をとることができるなど,オラクルの強さと必勝戦略発見可能性に関する様々な結果が得られることを示す.

著者

佐久間 俊慎 小野 廣隆 山下 雅史 朝廣 雄一 牧野 和久 堀山 貴史

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1325, pp.8-14, 2003-05

著者

横尾 真 神取 道宏 田村 明久 船木 由喜彦 関口 格 坂井 豊貴 平山 勝敏 尾山 大輔 安田 洋祐 岡本 吉央 岩崎 敦 川崎 雄二郎 小野 廣隆 櫻井 祐子 東藤 大樹 上田 俊 伊藤 孝行 小島 武仁 小原 一郎

出版者

九州大学

雑誌

基盤研究(S)

巻号頁・発行日

2012-05-31

---

本研究プロジェクトでは、我が国の持続可能な発展のために、計算機科学とミクロ経済学の技術を統合/発展させ、経済的、社会的、環境的な観点からの要求をバランスした、希少な資源の望ましい配分を実現するメカニズムの設計理論を構築することを目的としている。具体的には、資源配分メカニズムの設計、解析、表現技術に関して研究を推進し、特に、制約付き両方向マッチングにおけるメカニズム設計、ノイズのある繰り返しゲームの均衡解析、協力ゲームに関する表現技術に関して顕著な成果が得られている(査読付き国際会議87件、国際論文誌74件、国内論文誌11件、著書8件、教科書の執筆4件、招待講演40件)。

著者

都 勇志 木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

vol.2022-GI-47, no.14, pp.1-7, 2022-03-11

---

ゲームの難易比較や AI ベンチマークの妥当性評価などのため,二人零和有限確定完全情報ゲームの「複雑さ」の計量が様々な形で研究されている.代表的な「複雑さ」の尺度の一つが状態空間数であり,これは初期局面から到達可能な局面数として定義されている.本研究では将棋の状態空間数の見積もりを行う.禁則ルールの多さなどから将棋の厳密な状態空間数を測ることは容易ではないが,2008 年の篠田の研究により 4.65×1062 と 9.14×1069 の間の値を取ることがわかっている.本研究では将棋の状態空間数のより正確な評価を行い,2.45×1064 と 6.78×1069 の間の値を取ることを示す.上界値の評価については持ち駒が少ないほど局面のパターンが増えることに注目した計量方法を提案する.下界については,篠田により提案された駒配置のテンプレートを改良し,これに基づく解析を行う.また将棋から派生したゲームである 5 五将棋についても状態空間数が 13 桁から 20 桁の間であることを示す.

著者

木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

vol.2018, pp.199-203, 2018-11-09

---

全国的に認知度, 人気が高いトランプカードゲームの一つであるババ抜きは不完全情報ゲームであり, 心理的な駆け引きを除けば戦略性よりも偶然性が支配するゲームである. 本研究では手札公開で行う完全情報の「ババ抜き」ゲームを定義し, その最適戦略について考察する. プレイヤーが3 人の場合における必勝戦略の有無に関する必要十分条件を与える. さらに, プレイヤー4 人以上のときすべてのプレイヤーが最善をつくすと「千日手」が発生して引き分けとなる局面が存在することを示す.

著者

木谷 裕紀 小野 廣隆

雑誌

第81回全国大会講演論文集

巻号頁・発行日

vol.2019, no.1, pp.99-100, 2019-02-28

---

全国的に認知度, 人気が高いトランプカードゲームの一つである「ババ抜き」は不完全情報ゲームであり, 心理的な駆け引きを除けば戦略性よりも偶然性が支配するゲームである. 本研究では手札公開で行う完全情報の「ババ抜き」ゲームを定義し,その最適戦略の有無について考察する. まず, プレイヤーが3人以下の場合における必勝戦略の有無に関する必要十分条件を与える. さらに, プレイヤー 4 人以上のときすべてのプレイヤーが最善をつくすと「千日手」が発生して引き分けとなる局面が存在することを示す.

著者

馬場 雅大 小野 廣隆 定兼 邦彦 山下 雅史

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-129, no.1, pp.1-8, 2010-02-26

---

大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた.本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる.提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり,右の子へ巡回するといった操作を定数時間で行うことができる.また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す.

著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

no.2021, pp.130-137, 2021-11-06

著者

木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

no.2018, pp.199-203, 2018-11-09

著者

後藤 隆元 小野 廣隆 定兼 邦彦 山下 雅史

出版者

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

雑誌

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

巻号頁・発行日

vol.105, no.72, pp.1-8, 2005-05-13

---

計算機の性能の向上や, インターネットの普及により, 我々が扱うデータの量は急速に増加している.そしてそれに伴い, 大きなデータの中から必要なデータを探し出す機会も多くなっている.しかし, 扱うデータの量が増えるにつれて検索に必要な時間計算量や空間計算量も増加するため, より効率の良い検索アルゴリズムが求められている.一般に, 文字列検索を行う際にはあらかじめ対象となるファイルに対して索引付けを行って検索しやすくしている.そこで, 本研究では複数のファイルを格納した文書データベースに対して, 圧縮接尾辞配列を用いた索引付けを行うことにより, 時間的にも空間的にも効率が良く, 検索漏れが生じない文字列検索アルゴリズムを提案する.

著者

泉 朋子 泉 泰介 小野 廣隆 和田 幸一

出版者

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

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.18, pp.49-56, 2009-02-26

---

証明書分散問題(Minimum Certificate Dispersal Problem, MCD)とは,グラフGと要求集合Rが与えられたときに,Rに含まれるすべての要求を満たすよう各ノードにGの辺を割り当て,各ノードに割り当てられる辺の総数を最小化する問題である.要求とはグラフG上の異なる2つのノードの順序対で表され,要求(u, v)を満たすにはノードu, vに割り当てる辺の和集合にGにおけるuからvへの経路が含まれる必要がある.MCDは与えられるグラフが強連結の場合においてもNP-困難であることが既に示されている.本研究では,MCDの近似可能性について議論する.まず,強連結グラフにおいてMCDの近似率の下界がOmega(log n)(nはGのノード数)であることを示し,さらに任意のグラフにおけるMCDに対する多項式時間O(log n)-近似アルゴリズムが構成可能であることを示す.また,既存研究において多項式時間2-近似アルゴリズムであると評価されていたアルゴリズムが,無向グラフを入力とするMCDに対しては多項式時間3/2-近似アルゴリズムであることを示す.Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability / inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Omega (log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.