Vol.30.No.2(2015/03)ゲームプログラミング（将棋を中心に）

私のブックマーク

ゲームプログラミング（将棋を中心に）

竹内聖悟（科学技術振興機構 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)

続いて紹介するのは，ゲーム情報学とコンピュータ将棋を扱った書籍です．これらはもう少し技術的な内容を扱った書籍となっています．

小谷善行編著; 岸本章宏, 柴原一友, 鈴木豪著: ゲーム計算メカニズム – 将棋・囲碁・オセロ・チェスのプログラムはどう動く –, コロナ社, 2010: ゲームプログラミングの技術全般を取り扱った書籍です．評価関数の学習やモンテカルロ木探索についてはあまり触れられていません．
瀧澤武信，松原仁，小谷善行，鶴岡慶雅，山下宏，金子知適，保木邦仁，伊藤毅志，竹内章，篠田正人，古作登，橋本剛著; コンピュータ将棋協会監修: 人間に勝つコンピュータ将棋の作り方, 技術評論社, 2012: あから2010 に関連した書籍で，各プログラムの作者による解説やコンピュータ将棋の対局から見た特徴について紹介されています．
松原仁編: コンピュータ将棋の進歩6, 共立出版, 2012.: 将棋プログラムBonanza, GPS将棋, 激指, 大槻将棋について開発者により解説される他，合議と詰将棋探索についても第一人者が詳しく解説しており．上述の書籍よりも専門的な内容となっています．

ウェブ上のリソース

続いて将棋を中心としてゲームプログラミングに関する，ウェブ上のリソースを紹介します．

コンピュータ将棋で重要である，盤面のデータ構造や探索，評価関数について解説のあるサイトを紹介します．

ミニマックス法とアルファベータ法 (M.Hiroi’s Home Page): ゲームで使われる基本的な探索であるミニマックス法とアルファベータ法について解説とPython によるコードが掲載されています．
将棋プログラムの作り方（「うさぴょん」「ねこにゃ」開発日記）: 将棋での流行の盤面データ構造Bitboard ではありませんが，盤面データ構造の作り方とアルファベータ探索に基づく探索手法のサンプルとして参考になります．
囲碁プログラムの作り方（勝也のページ）: 囲碁で主流となったモンテカルロ木探索は使われていませんが，盤面のデータ構造の作り方は参考になると思います．
Chess Programming Wiki: コンピュータチェスの技術について非常によくまとまったサイトです．コンピュータ将棋はコンピュータチェスを参考にすることが多く，大変に有用です．
盤面表現や探索，評価関数はBasics にあり，ここから興味のある項目を辿るのが良いと思います．

情報交換や技術交流の場としては次のようなものがあります．

コンピュータ将棋協会 (CSA)
コンピュータ囲碁フォーラム (CGF)
コンピュータ将棋や囲碁の掲示板
The Computer-Go ML archives
TalkChess.com

また，技術情報やリンクについてまとめられたサイトとしては，前述のChess Programming Wiki 以外にも次のようなサイトがあります．

YSSと彩のページ
コンピュータ将棋の勉強メモ (ず’s 将棋)
将棋ソフト・コンピュータ将棋 (詰将棋おもちゃ箱)
Computer Go at Sensei’s Library

オープンソースのプログラム

自分で全て作るにせよ，他のプログラムがどのようなことをしているかを知るのは重要です．
また，自分のアイデアを試したいという場合には，一からプログラムを作る必要はなく，公開されているプログラムに対して実装するので十分です．

以下に，代表的なオープンソースのプログラムを挙げます．

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: 国際的なネット対局場で，様々な機能や将棋類をサポートしています．また，プログラムが常駐しています．

学会・研究会・国際会議

ゲーム情報学に関連する学会，研究会および国際会議は以下のようなものがあります．

ゲーム情報学研究会: ゲーム情報学を扱う研究会です．情報処理学会の研究会の一つで，年に二度の研究会の他，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年以上前にその目標を達成したコンピュータチェスは未だに研究・開発が続いており，コンピュータ将棋でも棋力向上の研究・開発が続いていくことでしょう．
これまでの，そして将来の研究・開発によって更なる棋力が得られるようになると，対局の解説や棋力解析のような新しい研究が促進されていきますので，今後現れる新しい研究に注目して行きたいと思います．

本稿が，この分野に興味を持つ方の参考になる，あるいは研究や開発を始める方の助けとなれば幸いです．

謝辞

本稿の執筆にあたり有益なアドバイスを頂いた，金子知適准教授（東京大学），美添一樹博士（科学技術振興機構）に感謝いたします．

私のブックマーク

ゲームプログラミング（将棋を中心に）

はじめに

ゲーム情報学全般

ウェブ上のリソース

オープンソースのプログラム

コンピュータ将棋の大会やネット対局場

最近の研究動向

<レクチャーシリーズ>「コンピュータ将棋の技術」

棋譜を教師とした，評価関数のパラメータの自動調整

探索の分散並列化

棋力の解析や棋譜の解説

モンテカルロ木探索

ゲームを解く

学会・研究会・国際会議

おわりに

謝辞