私のブックマーク
ゲームプログラミング(将棋を中心に)
竹内 聖悟(科学技術振興機構 ERATO湊離散構造処理系プロジェクト)
はじめに
コンピュータ将棋の棋力向上を背景として,プロ棋士との対局イベントが開催されるなど,コンピュータ将棋が世間の注目を集めています.
ゲームやパズルはルール及びゴールが明確であるなど研究対象として扱いやすいこともあり,人工知能研究において初期から研究されてきました.
ゲームプログラミングやゲーム情報学のゴールとしては,強いプログラムの作成や完全解析などが挙げられます.
人工知能学会「私のブックマーク」では1999年に「ゲームプログラミング(囲碁を中心に)」が取り上げられています.
本稿では,将棋を中心とした二人零和有限確定完全情報ゲームを対象として扱い,近年の主な研究動向と研究開発に有用なリソースを紹介していきます.
ゲーム情報学全般
はじめに,ゲーム情報学全般を概観する解説記事として,2012年の情報処理学会誌ゲーム情報学特集を紹介します.
- 松原 仁: ゲーム情報学:1.ゲーム情報学の現在-ゲームの研究は日本で疎外されなくなったのか-,情報処理,53(2),102-106 (2012-01-15)
- 小谷 善行: ゲーム情報学:2.ゲーム情報学におけるパズル研究,情報処理,53(2),107-111 (2012-01-15)
- 瀧澤 武信: ゲーム情報学:5.将棋,情報処理,53(2),126-132 (2012-01-15)
- 村松 正和: ゲーム情報学:6.コンピュータ囲碁の現状,情報処理,53(2),133-138 (2012-01-15)
- 岸本 章宏: ゲーム情報学:7.その他の2人ゲーム, 情報処理,53(2),139-145 (2012-01-15)
- 小谷 善行: ゲーム情報学:2.ゲーム情報学におけるパズル研究,情報処理,53(2),107-111 (2012-01-15)
続いて紹介するのは,ゲーム情報学とコンピュータ将棋を扱った書籍です.これらはもう少し技術的な内容を扱った書籍となっています.
- 小谷善行 編著; 岸本章宏, 柴原一友, 鈴木豪 著: ゲーム計算メカニズム – 将棋・囲碁・オセロ・チェスのプログラムはどう動く –, コロナ社, 2010
- ゲームプログラミングの技術全般を取り扱った書籍です.評価関数の学習やモンテカルロ木探索についてはあまり触れられていません.
- 瀧澤武信,松原仁,小谷善行,鶴岡慶雅,山下宏,金子知適,保木邦仁,伊藤毅志,竹内章,篠田正人,古作登,橋本剛 著; コンピュータ将棋協会監修: 人間に勝つコンピュータ将棋の作り方, 技術評論社, 2012
- あから2010 に関連した書籍で,各プログラムの作者による解説やコンピュータ将棋の対局から見た特徴について紹介されています.
- 松原仁編: コンピュータ将棋の進歩6, 共立出版, 2012.
- 将棋プログラムBonanza, GPS将棋, 激指, 大槻将棋について開発者により解説される他,合議と詰将棋探索についても第一人者が詳しく解説しており.上述の書籍よりも専門的な内容となっています.
ウェブ上のリソース
続いて将棋を中心としてゲームプログラミングに関する,ウェブ上のリソースを紹介します.
コンピュータ将棋で重要である,盤面のデータ構造や探索,評価関数について解説のあるサイトを紹介します.
- ミニマックス法とアルファベータ法 (M.Hiroi’s Home Page)
- ゲームで使われる基本的な探索であるミニマックス法とアルファベータ法について解説とPython によるコードが掲載されています.
- 将棋プログラムの作り方(「うさぴょん」「ねこにゃ」開発日記)
- 将棋での流行の盤面データ構造Bitboard ではありませんが,盤面データ構造の作り方とアルファベータ探索に基づく探索手法のサンプルとして参考になります.
- 囲碁プログラムの作り方(勝也のページ)
- 囲碁で主流となったモンテカルロ木探索は使われていませんが,盤面のデータ構造の作り方は参考になると思います.
- Chess Programming Wiki
- コンピュータチェスの技術について非常によくまとまったサイトです.コンピュータ将棋はコンピュータチェスを参考にすることが多く,大変に有用です.
盤面表現や探索,評価関数はBasics にあり,ここから興味のある項目を辿るのが良いと思います.
情報交換や技術交流の場としては次のようなものがあります.
また,技術情報やリンクについてまとめられたサイトとしては,前述のChess Programming Wiki 以外にも次のようなサイトがあります.
- YSSと彩のページ
- コンピュータ将棋の勉強メモ (ず’s 将棋)
- 将棋ソフト・コンピュータ将棋 (詰将棋おもちゃ箱)
- Computer Go at Sensei’s Library
- コンピュータ将棋の勉強メモ (ず’s 将棋)
オープンソースのプログラム
自分で全て作るにせよ,他のプログラムがどのようなことをしているかを知るのは重要です.
また,自分のアイデアを試したいという場合には,一からプログラムを作る必要はなく,公開されているプログラムに対して実装するので十分です.
以下に,代表的なオープンソースのプログラムを挙げます.
- Bonanza (将棋)
- 評価関数の重みの学習に成功し,手法及びソースを公開したことでも有名な強豪ソフトです.学習や合議のコードも含まれています.
- GPS将棋 (将棋)
- 600台超のマシンでの分散並列探索を行った強豪ソフトです.GPS将棋の他,将棋ライブラリOpenShogiLib,チェスプログラムStockfish を将棋向けにしたGPSFish,分散並列探索のコードなどが公開されています.
- Stockfish (チェス)
- トップレベルのチェスプログラムで,多くの将棋プログラムが参考にしています.ソースだけでなく,何を試したか,どの程度有用であったかなど開発まで公開されています(Stockfish Testing Queue).
- Fuego, Pachi (囲碁)
- モンテカルロ木探索が実装されたトップレベルの囲碁プログラムです.
- コンピュータ将棋選手権使用可能ライブラリ
コンピュータ将棋の大会やネット対局場
コンピュータ将棋の大会やネット対局場について紹介します.
- 世界コンピュータ将棋選手権
- コンピュータ将棋協会が主催する,コンピュータ将棋の進歩を目的としたコンピュータ将棋の大会です.選手権などCSA が主催した大会等の棋譜は,CSA のサイトにまとめられています.
- 電王戦
- 電王戦は将棋プログラム同士の対局イベントです.トップ5のプログラムがプロ棋士と対局していましたが,この形式でのイベントは2015年で終わりとのことです.コンピュータに限らず,様々な将棋イベントが行なわれています.
- Computer Olympiad
- ICGA が主催する,様々なゲームを対象としたコンピュータの国際大会です.囲碁や将棋だけでなく,幅広いゲームが見られます.
- コンピュータ将棋対局場, floodgate
- 将棋プログラムが24時間ネット対局しています.floodgate では,対戦結果から各プログラムのレーティングを算出しており,強さの目安として使われています.対局数が少ないか,同程度の強さのプログラムが少ない時はあまり信用できません.floodgate で指された棋譜は年ごとにまとめられており,2014年までで60万局以上となっています.
上記の選手権や対局サーバで使われるプロトコルやサーバプログラムなどを紹介します.
- CSA通信プロトコル
- コンピュータ将棋協会が制定するプロトコルです.TCP/IPプロトコル は,世界コンピュータ将棋選手権で使われている他,floodgate でも使われています.
- Universal Shogi Interface (USI)
- チェスではUniversal Chess Interface (UCI) により,プログラムとGUI とが接続しています.その将棋版がUSI です,対局サーバへの接続もGUI が処理をしてくれるので,プログラム開発者はUSI だけ使えるようにすれば良く,思考部分の開発に集中することができます.
- shogi-server
- floodgate で使われているネット対局用サーバでCSA のTCP/IPプロトコルとそれを拡張したプロトコルに対応しています.GPL で配布されています.
ネット対局場としては次の2つのサイトもあります.基本的に人間同士が対局する場ですが,許可を得てプログラムが対戦,常駐しています.
- 将棋倶楽部24
- 将棋プログラムボンクラーズやponanza が参加し,レーティングのトップになるなど,将棋ファンの注目を集めました.
- 81Dojo
- 国際的なネット対局場で,様々な機能や将棋類をサポートしています.また,プログラムが常駐しています.
最近の研究動向
ここからは,将棋を中心とした,最近の研究動向について紹介していきます.
<レクチャーシリーズ>「コンピュータ将棋の技術」
2011年5月から2012年7月にかけて人工知能学会誌において<レクチャーシリーズ>「コンピュータ将棋の技術」が全7回で連載されました.
探索枝刈りや並列化,評価関数の重みの学習に詰将棋探索など多岐にわたり,最先端の技術が解説されています.(これらはオープンアクセスではありません).
- 保木 邦仁: Craftyと比較したBonanzaの有効分岐因子, 人工知能学会誌 26(3), 295-300, 2011-05-01
- 岸本 章宏: 詰将棋を解くための探索技術について, 人工知能学会誌 26(4), 392-398, 2011-07-01
- 伊藤 毅志: コンピュータ将棋における合議アルゴリズム, 人工知能学会誌 26(5), 525-530, 2011-09-01
- 横山 大作: 「激指」におけるゲーム木探索並列化手法, 人工知能学会誌 26(6), 648-654, 2011-11-01
- 金子 知適: コンピュータ将棋の評価関数と棋譜を教師とした機械学習, 人工知能学会誌 27(1), 75-82, 2012-01-01
- 山下 宏: 囲碁と将棋のプログラミングの違い, 人工知能学会誌 27(2), 211-215, 2012-03-01
- 竹内 章: コンピュータ将棋における大局観の実現を目指して, 人工知能学会誌 27(4), 443-448, 2012-07-01
- 岸本 章宏: 詰将棋を解くための探索技術について, 人工知能学会誌 26(4), 392-398, 2011-07-01
棋譜を教師とした,評価関数のパラメータの自動調整
棋譜の指手を教師として,プログラムが教師の手を最善手として選ぶようにパラメータを調整する手法は比較学習として研究がされていましたが,明確には成功していませんでした.
保木邦仁はこの手法に探索を組み合わせることで成功し,プログラムBonanza を2005年に公開し,2006年の世界コンピュータ将棋選手権で優勝,同年のGPWでの招待講演においてその手法を講演しました.その後多くの将棋プログラムがこの手法を採用し,棋力の向上に非常に大きく貢献しました.
チェスでも様々に試されていましたが,大規模なパラメータを対象として成功した例はないようです.
- Kunihito Hoki, Tomoyuki Kaneko: Large-Scale Optimization for Evaluation Functions with Minimax Search, Journal of Artificial Intelligence Research, Vol. 49, pp. 527-568, 2014.
比較学習を用いるとプログラムが棋譜の指手を真似るようになりますが,このことと強さとの関係は明確ではありません.
佐藤佳州 らはそこに着目し,棋譜の指手とどれだけ一致するかに加え,局面の情報などから局面に重みをつけてパラメータ調整の行う手法を提案しました.
目的関数のメタパラメータを,勝率を適応度とした遺伝的アルゴリズムの一種を用いて調整し,対戦実験では有意な結果を得ました.
- Yoshikuni Sato, Makoto Miwa, Shogo Takeuchi, and Daisuke Takahashi: Optimizing Objective Function Parameters for Strength in Computer Game-Playing, Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13), pp. 869–875, 2013
探索の分散並列化
探索について,多数のマシンを利用する研究も行なわれています.
「あから」についての書籍やレクチャーシリーズで解説された合議も効率的ではないですが分散並列化の手法と言えます.
以下では,将棋における分散並列化,特に大規模な分散並列化についての研究を取り上げます.
横山氏による講演スライドでは分散並列化のための課題やチェスで研究されてきた手法(Young Brothers Wait Concept, Transposition table Driven work Scheduling),将棋での研究例について詳しく解説しています.
Ura らは将棋プログラム激指と1,536コアを利用した大規模分散の研究を行いました.効率的な探索のために必要最低限の部分木を予測し,それを探索のタスク割振りに利用する手法です.論文中の関連研究では前述の手法の他,Asynchronous Parallel Hierarchical Iterative Deepening も紹介されています.
GPS将棋は,世界コンピュータ将棋選手権やプロ棋士の三浦八段(当時)との対局において,600台以上のマシンをネットワークで接続した環境での疎結合並列探索を行いました.選手権や対局イベントの結果,探索深さの比較から有効な並列探索が実現していると言えます.探索の仕組みやその性能向上については情報処理学会の電王戦特集に紹介されています.
- 横山 大作: コンピュータ将棋と並列化~緻密ないい加減さ~, Electronic Design and Solution Fair 2013, セッション3. 2013.
- Akira Ura, Yoshimasa Tsuruoka, Takashi Chikayama: Dynamic Prediction of Minimal Trees in Large-Scale Parallel Game Tree Search, Journal of Information Processing, Vol. 23, No. 1, Jan. 2015. (論文はオープンアクセスではありません)
- 金子 知適, 田中 哲朗: 多数の計算機を活用したゲーム木探索技術の進歩 -三浦弘行八段と GPS 将棋との対局を振り返って-, 情報処理 54(9), 914—922, 2013.
(2015年1月15日現在,記事はオープンアクセスではありません) - Akira Ura, Yoshimasa Tsuruoka, Takashi Chikayama: Dynamic Prediction of Minimal Trees in Large-Scale Parallel Game Tree Search, Journal of Information Processing, Vol. 23, No. 1, Jan. 2015. (論文はオープンアクセスではありません)
棋力の解析や棋譜の解説
プログラムの棋力向上を背景として,人間プレイヤの棋力・レーティング解析の他,コンピュータによる棋譜の解説など,強さ以外の目的を持った研究が増えています.
以下に紹介する文献は,コンピュータを使い人間プレイヤの棋力を解析した研究です.前者はチェスを対象とした研究で,後者は将棋を対象としています.古今の人間プレイヤのレーティング推定は,将棋ファンの興味を惹く内容です.
- Kenneth W. Regan, Guy McC. Haworth: Intrinsic Chess Ratings, Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11), pp. 834–839, 2011.
- 山下 宏: 将棋名人のレーティングと棋譜分析, ゲームプログラミングワークショップ2014論文集, pp.9-16, 2014
次に紹介するのはコンピュータ将棋を使い,棋譜の解説を行う試みです.
前者はネット上で中継が行なわれているタイトル戦の棋譜を対象に,将棋プログラムの読み筋や評価値,さらに詰みや詰めろ,狙いなどをリアルタイムでtwitter 上で行ったことについて述べられ,後者は,棋譜と解説文から特徴を取り出し,実際の棋譜に対して特徴を取り出し,自然言語で出力することを試みた研究です.
- 金子 知適: コンピュータ将棋を用いた棋譜の自動解説と評価, 情報処理学会論文誌 53(11), 2525-2532, 2012
- 亀甲 博貴, 森 信介, 鶴岡 慶雅: 将棋解説文のグラウンディングのための指し手表現と局面状態の対応付け, ゲームプログラミングワークショップ2014論文集, pp.202-209, 2014
モンテカルロ木探索
囲碁では2000年代中頃からモンテカルロ木探索と呼ばれる探索手法が提案され,大きな成功を収めました.
モンテカルロ法に木探索を組み合わせた手法で,モンテカルロ法,すなわちランダムプレイによる評価を使うため,評価関数が不要ということが大きな特徴です.
その後,多くのゲームへと応用されるだけでなく,ゲーム以外の分野へも応用されるなど,手法の有用性が示されています.
モンテカルロ木探索のバリエーションやヒューリスティック,応用など多岐に渡りまとめられた2012年時点での調査論文,モンテカルロ木探索についてのわかりやすい解説となっている講演スライド,コンピュータ囲碁とモンテカルロ木探索について,詳しく書かれた日本語の書籍を紹介します.
- Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton: A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, Volume: 4, Issue: 1. 2012. (論文はオープンアクセスではありません)
- 美添 一樹: コンピュータ囲碁における モンテカルロ法 ~理論編~, エンターテイメントと認知科学研究ステーション 第5回講演会 (電気通信大学) 2008年6月
- 松原仁編; 美添一樹, 山下宏著 コンピュータ囲碁―モンテカルロ法の理論と実践―, 共立出版, 2012
- 美添 一樹: コンピュータ囲碁における モンテカルロ法 ~理論編~, エンターテイメントと認知科学研究ステーション 第5回講演会 (電気通信大学) 2008年6月
- 著者の一人, 山下氏によるweb pageではサンプルコードや参考文献が公開されています.
ゲームを解く
ゲーム研究の究極的なゴールの一つとして,ゲームの勝敗を知ること,すなわち初期局面からプレイヤが最善を尽くした場合に先手必勝か後手必勝,または引分となるかを解析することが挙げられます.
ゲームの難しさとして,ゲーム木サイズや可能な局面数が見積もりとして使われます.
これまで解かれた中では,ゲーム木サイズが1030のチェッカーが最大です.よく知られたゲームでは,オセロが1060,チェスが10120,将棋が10220,囲碁は10360となっており,これらのゲームが解かれるまでにはまだまだ時間がかかりそうです.
有名なゲームの解析は非常に大きなインパクトを持ちます,実際チェッカーを解いた結果はサイエンス誌に掲載され,その年のThe Runners-Up に選ばれています.
- Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P. and Sutphen, S.: Checkers Is Solved, Science, Vol. 317, No. 5844, pp. 1518-1522(Sept. 2007).(論文はオープンアクセスではありません)
- 日本語記事としては,チェッカー解析プロジェクトの一員である岸本章宏氏による解説記事「チェッカー解明秘話」(情報処理,48(11),1257-1263,2007)があります.
「どうぶつしょうぎ」は3×4の小さな盤面の将棋類で,初期局面から最善を尽くすと78手で後手が勝つことが解析されました.一般に将棋類は先手が有利なゲームが多く,後手が勝つこと,小さな盤面で78手かかることなど意外な結果が得られています.
- 田中 哲朗: 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告ゲーム情報学(GI), Vol. 2009-GI-22, No. 3, pp. 1-8(2009).
- 「どうぶつしょうぎ」の完全解析 においてプログラムのソースやデータが公開されています.
二人零和有限確定完全情報ゲームの解析に使われる有効な手法は,Depth-First proof number (df-pn) 探索です.Proof Number Search はAllis らにより提案されたAnd-Or木探索の手法ですが最良優先探索であるためにメモリ使用量が問題でした.これを深さ優先で行い,かつ反証数を取り入れた手法が長井らにより提案され,その有効性が示されました.その後,グラフを辿るにあたって起こる問題を岸本が改善し,さらに金子によって並列化が行なわれるなどの進歩がありました.
以下に紹介する文献は,証明数探索に関するここ20年の動向がまとめられたものとなっています.
- Akihiro Kishimoto, Mark HM Winands, Martin Müller, Jahn-Takeshi Saito: GAME-TREE SEARCH USING PROOF NUMBERS: THE FIRST TWENTY YEARS, ICGA Journal, Volume: 35, Number: 3, pp. 131–156, 2012
学会・研究会・国際会議
ゲーム情報学に関連する学会,研究会および国際会議は以下のようなものがあります.
- ゲーム情報学研究会
- ゲーム情報学を扱う研究会です.情報処理学会の研究会の一つで,年に二度の研究会の他,11月に箱根でワークショップGame Programming Workshop (GPW)を主催しています.それらの予稿は電子図書館においてオープンアクセスで公開されています.
- International Computer Games Association (ICGA)
- ゲーム情報学を扱う国際的な学会です.国際会議Computer and Games (CG)及び,Advances in Computer Games (ACG) を主催する他,論文誌ICGA Journal を発行しています.また,様々なゲームを扱ったコンピュータプログラムの国際大会Computer Olympiadも主催しています.
- 情報処理学会
- 情報処理全般について幅広く扱う学会で,前述のゲーム情報学研究会が所属しています.学会誌ではゲーム情報学やコンピュータ将棋についての小特集.論文誌ではゲーム情報学の特集号が企画されることがあります.また,2010年には創立50周年記念事業の一つとしてコンピュータ将棋プロジェクト,「あから2010」と清水市代女流王将(当時)との対局イベントを主催しました.
- 人工知能学会
- ゲームと人工知能との関連が深く,コンピュータ将棋に関するレクチャーシリーズや「私のブックマーク」などが掲載されている他,学会誌や全国大会でゲームが取り上げられることがあります.
- IEEE Computational Intelligence Society
- Computational Intelligence (CI) についての国際的な研究コミュニティです.ゲームについては,国際会議Computational Intelligence and Games (CIG) を主催の他,論文誌IEEE Transactions on Computational Intelligence and AI in Games を発行しています.
- The AAAI Conference on Artificial Intelligence
- Association for the Advancement of Artificial Intelligence が主催する人工知能についての国際的なトップ会議.ゲームについての研究発表や競技会があります.
- International Joint Conference on Artificial Intelligence
- 人工知能についての国際的なトップ会議です.こちらもゲームについての研究発表や競技会があります.
- European Conference on AI
- 2年に一度開催される人工知能についての国際会議で,こちらもゲームについての研究発表や競技会があります.
おわりに
将棋を中心として,ゲームプログラミングについて,概観する記事から有用と思われる情報源,研究動向について紹介してきました.
コンピュータ将棋の棋力はプロ棋士レベルに達し,一つの目標を達成したように思えます.しかし,10年以上前にその目標を達成したコンピュータチェスは未だに研究・開発が続いており,コンピュータ将棋でも棋力向上の研究・開発が続いていくことでしょう.
これまでの,そして将来の研究・開発によって更なる棋力が得られるようになると,対局の解説や棋力解析のような新しい研究が促進されていきますので,今後現れる新しい研究に注目して行きたいと思います.
本稿が,この分野に興味を持つ方の参考になる,あるいは研究や開発を始める方の助けとなれば幸いです.
謝辞
本稿の執筆にあたり有益なアドバイスを頂いた,金子知適准教授(東京大学),美添一樹博士(科学技術振興機構)に感謝いたします.