著者

塩田 雅弘 伊藤 毅志

雑誌

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

巻号頁・発行日

vol.2021, pp.42-45, 2021-11-06

---

京都将棋は 1976 年に田宮克哉によって考案された二人零和有限確定完全情報ゲームである.5×5マスの盤を使用し,駒を一手ごとに裏返すというルールが特徴である.本論文では京都将棋エンジンを開発し,本将棋で広く使われている強化学習アルゴリズムを京都将棋に適用することで十分に強いプレイヤを作成した.そしてこのプレイヤを用いて証明木を効率良く発見した.この結果,京都将棋を弱解決し,本ゲームの初期局面が先手必勝であることを示した.

著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

ゲームプログラミングワークショップ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 完全である.

著者

高橋 昇太 阿原 一志

雑誌

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

巻号頁・発行日

vol.2021, pp.46-48, 2021-11-06

---

トレーディングカードゲーム (TCG) には,手札枚数や個々のカードの攻撃力など様々なパラメータが存在する.一般にこれらの値は勝敗に大きく関わるとされているが,科学的実証はほとんど報告されていない.そこで本研究では,パラメータ変更による勝率の変化についてサンプリング手法を用いた調査を試みた.本論文では特に,初期手札の枚数差を意図的に生じさせ,どのように勝率が変化するかをこの手法を用いて調査した.その結果,初期手札枚数が多いプレイヤーは勝率が高くなる傾向を数値化できることが分かった.

著者

田中 哲朗

雑誌

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

巻号頁・発行日

vol.2021, pp.138-143, 2021-11-06

---

R-Rivals はカナイセイジ氏がデザインした 2 人用カードゲームで 2014 年に発売された.R-Rivalsはサイコロのようなランダムな要素を含まない 2 人零和ゲームだが,同時手番ゲームなのでじゃんけんと同様にナッシュ均衡が存在するのは双方のプレイヤが混合戦略を用いたときになる.本研究では,同値な状態は同じであるとみなして,R-rivals のすべての状態を数えた.そして,得られた約 54 万の状態すべてのゲーム値を計算した.その結果,初期状態で出せる 8 枚のカードのうち,道化,姫,将軍を除く 5 枚のカードをある確率で出すのが最適な戦略であること,ポイントが 0-3 から勝てる状態があることなどの性質をみつけることができた.

著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

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

巻号頁・発行日

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

著者

高橋 翔太 松原 仁

雑誌

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

巻号頁・発行日

vol.2021, pp.98-101, 2021-11-06

---

人間はタスクを実行する際に,しばしば最適解以外の行動,つまりミスを犯す.言い換えると,行動の中でミスをすることは人間らしい行為と言える.そのため,ある特定のタスクを実行するエージェントに認知バイアスによるミスを実装し,人間らしい AI の設計を試みる.本研究では,タスクを将棋に設定し,将棋で起こりうる認知バイアスを分析した.分析の結果から,直近効果が将棋に作用していることが分かった.今後は直近効果を実装した将棋 AI を用いて,定性的な実験を行う.

著者

山下 宏

雑誌

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

巻号頁・発行日

vol.2021, pp.20-27, 2021-11-06

---

将棋の駒落ちを人間の知識なしでゼロから深層強化学習した。6 種類の駒落ち (香落、角落、飛落、2 枚落、4 枚落、6 枚落) と平手、の合計 7 種類を同時に学習し、勝率は 5 割になるように下手 (先手) の強さを自動調節した。980 万棋譜を自己対戦で作成した結果、平手から 6 枚落ちまで、上手、下手、どちらを持っても高段者レベルの着手を返す AI ができた。

著者

中本 光彦 鶴岡 慶雅

雑誌

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

巻号頁・発行日

vol.2021, pp.160-165, 2021-11-06

---

部分観測環境における深層強化学習の適用は困難である.また,複雑なタスクにおいては適切な報酬関数を設計することも難しいとされている.本研究では,これらの課題を解決するために,部分観測環境における教師なし強化学習のアルゴリズムを提案する.部分観測性に対処するためにエージェントに外部の記憶機構を与え,外部報酬を用いる代わりに相互情報量に基づいた内発的報酬を提案する.提案する内発的報酬は,エージェントに観測情報が非常に限られている状態空間を優先的に探索しながら,有効な記憶を学習させることを可能にする.実験では,HalfCheetah エージェントに限られた観測だけで,外部報酬を一切使用せずに,前後に走ることを習得させることができた.