著者

富沢 大介 池田 心 橋本 隼一

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.9-16, 2011-10-28

---

1991年にコンパイルから発売された対戦型パズルゲームぷよぷよにおいてコンピュータAIの強さは4~5連鎖程度であり,中級者以上が満足できるレベルではなかった.本研究では,ぷよぷよのAIを強くすることを目的として,強いぷよぷよのプレイヤーに必要な要素の内の一つである,長い連鎖を効率的に組むことに着目し,囲碁の“定石”や将棋の“囲い”にあたる人智の結晶である“定型連鎖”を構成する方法に取り組む.関連性行列という形での状態表現・テンプレート表現を用いた構成法により,定型連鎖を構成することに成功した.さらに従来の探索型連鎖構成法を組み合わせることで従来法を上回る平均11.75連鎖を達成することに成功した.

著者

長井 歩

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.1-8, 2011-10-28

---

将棋の終盤戦をパズル化した問題として,詰将棋以外に必至問題がある.その違いは,攻め側の手として王手以外に詰めろも許される点にある.詰将棋では攻め側の指せる手は王手のみであるのに対し,必至問題では王手と詰めろで相手の玉を受けなしに追い込む.攻め側の手が増える分,必至問題に強いアルゴリズムは,実際の将棋の終盤戦で役立つ機会は詰将棋に比べ格段に多くなる.しかし問題としての難易度は,一般に詰将棋よりも必至問題の方が難しい.詰将棋を高速に解くアルゴリズムは近年著しく進歩したが,必至問題を高速に解くアルゴリズムは未開拓である.本研究では,難解な必至問題を高速に解くアルゴリズムとしてdf-pn+ を応用し実装した.実験の結果,難解な必至問題集として有名な『来条克由必至名作集』全81 問のうち79 問を解くことに成功した.また,余必至探索にて3つの早必至を含む27 の余必至を発見できた.

著者

滝瀬 竜司 田中 哲朗

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.25-31, 2011-10-28

---

現在の将棋プログラムの多くは入玉が絡む局面の扱いを不得意としているが,トッププロに勝つためには,入玉が絡む局面を正しく扱い「自玉が入玉できそうな時は入玉を目指す」,「敵玉の入玉を正しく阻止する」将棋プログラムの作成が不可欠だと考えられる.本稿ではオープンソースの将棋プログラムBonanzaの評価関数と定跡を変更することにより入玉志向の将棋プログラムを作成する試みをおこなう.その結果,元のBonanzaの評価関数に「入玉ステップ数」という特徴を加えて学習した評価関数を用いることにより,勝率を落とさずに入玉率を大幅に上げることができた

著者

田中 慶悟 藤本 典幸

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.76-83, 2011-10-28

---

近年,汎用計算ができるようになったGPU上でCUDAを用いて,Somersの高速なN-Queens問題求解アルゴリズムをさらに高速化する手法を提案する.提案手法はN-Queens問題をSomersのアルゴリズムで計算可能かつ独立な部分問題の集合にCPU上で分割し,生成した部分問題をGPUのVRAM上へと転送し,各スレッドへ動的に割り当て,効率よく並列計算を行う.評価実験を行ったところ,NVIDIA GeForce GTX480と2.93 GHz Intel Core i3 CPUを用いた場合,提案手法はSomersのアルゴリズムと比べN=19で24.5倍高速であった.また,GPUを用いたFeinbubeらの既存手法に比べ,提案手法は2倍高速であった.

著者

佐々木 宣介

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.112-115, 2011-10-28

---

本研究の大きな目標は、世界の将棋類においてルールの変遷が各変種に対して与える影響を探ることである。計算機による自動プレイを用いて、現代将棋とは異なる系統の大きな盤と多数の駒を持つ中将棋について評価を行った。中将棋には現代将棋にはないいくつかの特別なルールが存在するため、それらのルールの影響を評価した結果を報告する。

著者

大島 真 山田 孝治 遠藤 聡志

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.84-87, 2011-10-28

---

本研究では囲碁のヒューリスティックとして碁石をポテンシャルと見なした静的解析手法の実験を行っている.囲碁の解法に物理モデルを用いた研究は幾つか成されているが、従来研究では群や領域や石の影響度といった局所を構成する要素の評価を目的としているのに対し,本研究では対局序盤での勝敗に関わる碁盤の重要な領域の直接的な抽出を目標としている.実験では計算機同士の対局に提案手法を適用した場合の勝率の変化傾向や,モンテカルロ碁による評価と提案手法が抽出する領域との一致率などを求め,碁盤上の石の配置と勝敗に関わる重要な領域との間に幾何学的な規則性がある事を例証した.

著者

古居 敬大 三輪 誠 近山 隆

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.46-53, 2011-10-28

---

ナッシュ均衡的な戦略は多人数ゲームでは有効な戦略であるが,非合理的なプレイヤが存在する場合には必ずしも最適な行動であるとは言えない.本稿では多人数ポーカーゲームにおいて,より搾取が可能であると予想されるナッシュ均衡戦略を取っていないプレイヤを判別し,そのプレイヤのみに応じた戦略を取るプレイヤについての提案する.実験を行ったところ,特定の単純な行動を取るプレイヤに対しては大きく搾取することができ,結果としてナッシュ均衡的な戦略をとったプレイヤより報酬が大きくなる場合があることを確認した.

著者

瀧澤 武信

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.92-95, 2011-10-28

---

数理ゲーム理論(Mathematical Game Theory)は組合せゲーム理論(Combinatorial Game Theory)とも呼ばれ,組合せ数学(Combinatorial Mathematics)の一分野である.この理論は1960 年代に本格的な研究が始められ,1970 年代にCalifornia 大学Berkeley 校のE.Berlekamp 教授,英国Cambridge 大学のJ.Conway 教授,カナダCalgary 大学のR.Guy教授らにより確立された. 筆者はBerlekamp 教授がこの理論を囲碁の最終盤に適用し始めた直後の1991 年から,同教授らの研究グループと共同研究を行ってきた. 本論文では数理ゲーム理論の囲碁の最終盤への適用について述べる.

著者

渡邉 裕 中村 貞吾

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.62-67, 2011-10-28

---

人間がゲームをプレイする際には癖などの個人の特徴がプレイスタイルとして現れる.囲碁においてプレイスタイルは棋風と呼ばれており,本研究はプロ棋士の棋風を囲碁AIに模倣させることを最終目的としている.しかし,棋風を形成する要素は今のところ不明なので,それらを統計的分析によって明らかにすることを試みた.「盤上における着手の絶対位置」「獲得しようと狙う領域の相対的な位置関係」「攻撃/防御に対する積極性」の3つの要素を定式化し,特定の棋風を持つ棋士と棋士全体とで特徴要素の比較を行ったところ,いくつかの要素で有意差が見られた.

著者

渡邉 裕 中村 貞吾

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.62-67, 2011-10-28

著者

佐藤 佳州 高橋 大介

雑誌

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

巻号頁・発行日

vol.2011, no.6, pp.135-142, 2011-10-28

---

近年,ゲームプログラミングの分野において機械学習は急速に発展しており,評価関数の重みの決定,探索深さの調整,モンテカルロシミュレーションにおける指し手の予測など,幅広い課題に対して有効であることが示されている.現在のゲームプログラミングにおける機械学習は,あらかじめ評価項目(特徴)を用意し,プロの棋譜などを基にその重みを学習するというものが主流である.このような手法は,人間では調整できないような膨大な数の特徴に対しても,自動的に適切な重みを算出できるという利点がある.一方で,学習に用いる特徴自体は人間が手動で設計する必要があり,性能を決定する大きな要因となっている.現在,特徴の設計に関しては,人手による試行錯誤的な調整が行われているが,機械学習に有効な特徴を手動で生成することは一般的に非常に困難な問題である.本論文では,この問題を解決するため,特徴の自動生成と機械学習の重み付けを組み合わせることにより,有効な特徴を生成する手法を提案する.具体的には,機械学習の反復計算の過程に特徴の生成を組み込むことで,性能の向上を目指す.実験の結果,提案手法が現在ゲームプログラミングの分野で用いられている各学習手法において有効であることを示した.