著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

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

---

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

著者

都 勇志 木谷 裕紀 小野 廣隆

雑誌

研究報告ゲーム情報学(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 人以上のときすべてのプレイヤーが最善をつくすと「千日手」が発生して引き分けとなる局面が存在することを示す.

著者

大渡 勝己 木谷 裕紀

雑誌

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

巻号頁・発行日

vol.2021-GI-46, no.15, pp.1-7, 2021-06-12

---

二人単貧民はトランプゲーム大富豪を簡略化した二人零和完全情報ゲームであり,この勝者は両プレイヤの手札枚数に対して線形時間で決定できる.本研究では,二人単貧民において,勝者の最後の提出札に着目し,この札の上に相手が札を提出可能か,またはパスしかできないかを考慮して試合結果を細かく分ける.このとき,互いのプレイヤの最強札の強さが異なる条件下においては,この試合結果についても手札枚数に対して線形時間で求められることを示す.さらに,最強札が同じ強さの場合についても,計算機実験の結果から予想しているゲームの性質について議論する.

著者

大渡 勝己 木谷 裕紀

雑誌

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

巻号頁・発行日

vol.2020, pp.30-37, 2020-11-06

---

二人単貧民はトランプゲームの大富豪(大貧民)を簡略化した二人零和確定完全情報ゲームである.通常,単貧民は手札をすべて出し切ったプレイヤの勝ちである.それに対して本研究では勝利条件を一般化し,予め定めた枚数の手札を出した方が勝ち,言い換えると,それぞれ指定された残り手札枚数に先に到達した方が勝ち,というルールについて検証を行った.結果として,通常の単貧民の場合と同じく,必勝プレイヤの判定を手札の総数N に対してO(N) 時間で計算でき,二人単貧民の性質の多くはこの一般化した勝利条件においても成り立つことを示した.さらに,このゲームにおける最適戦略についても,最適な提出札の必要十分な範囲をO(N) 時間で計算できることなどの複数の新しい知見を得た.

著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

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

著者

木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

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

著者

大渡 勝己 木谷 裕紀

雑誌

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

巻号頁・発行日

vol.2020, pp.131-138, 2020-11-06

---

二人単貧民はトランプゲームの大富豪(大貧民)を簡略化した二人零和確定完全情報ゲームである.二人単貧民において勝敗のみに着目した場合,必勝プレイヤと必勝の戦略は手札の総数N に対してO(N)時間で計算できることが知られている.一方本研究では,二人単貧民において負け側の残り手札枚数を得点として扱い,できる限り相手に出させずに勝ち,逆に負けるとしてもできる限り多く出すことを競う設定を考え,検証を行った.結果として,この得点のミニマックス値と得点を最大化する提出札の必要十分な範囲のいずれもO(N) 時間で計算できることを示し,得点最大化とゲーム中のパスの回数や手数との間に密接な関係があることも確かめた.