JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May 偶然性が入らないゲームか ( 確定ゲームか ) という性質によって

Size: px

Start display at page:

Download "JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May 偶然性が入らないゲームか ( 確定ゲームか ) という性質によって"

かずまさわくや
5 years ago
Views:

1 ゲーム情報学コンピューター将棋を超えて Game informatics Beyond computer shogi 松原仁 1 MATSUBARA Hitoshi 1 1 公立はこだて未来大学 1 Future University Hakodate ゲーム情報学はゲームを対象とした情報処理の研究分野であるチェスがゲーム情報学の中心のゲームであったが, チェスでコンピューターが世界チャンピオンに勝った後は将棋が注目されていた将棋はまだ世界チャンピオンに勝ってはいないが, 対戦すれば勝つ可能性が高いレベルに達した囲碁はチェスや将棋と比べて場合の数がはるかに大きいのでまだ世界チャンピオンを倒すまで 10 年はかかるとみられていたが, 深層学習 ( ディープラーニング ) の利用によってすでにトップのプロ棋士に勝ち越すまでになった今後は人狼など不完全情報ゲームがゲーム情報学のテーマになっていくであろうチェス, 囲碁, 将棋, 人狼, 探索, 人工知能原稿受理 ( ) 情報管理. 2016, vol. 59, no. 2, p doi: 1. はじめにゲームは, ルールが明確である勝ち負けによって手法の良しあしが明確に評価できる目標にできる強い人間が存在するなど, 情報処理の研究の題材として優れているゲームを対象とした情報処理の研究を行う領域をゲーム情報学と呼ぶ 1) チェス, 将棋を超えて最近では, 囲碁および不完全情報ゲームがゲーム情報学の対象となっているここではゲーム情報学の経緯について述べる 2. 人工知能のハエとしてのチェスチェスは西欧で知性のシンボルとされているので, 人工知能の例題としてチェス ( の世界チャンピオンに勝つコンピューターを開発すること ) は, 人工知能の研究が始まって50 年間ずっと中心的な例題となっていた Shannonが1950 年にコンピューターチェスの論文を書いている 2) ( 同じ時期にTuringも彼とは別にコンピューターチェスの論文を書いている ) McCarthyはチェスのことを人工知能のハエと称した遺伝学がハエを題材として大きな進歩をしたように, 人工知能はチェスを題材として大きな進歩をしたという意味であるチェスの場合の数 ( 初手から勝負がつくまでを全部読む ) はほぼであるある局面でルール上, 指せる合法手の数を分岐数というが, チェスの平均分岐数は約 35であるチェスは平均 80 手で勝負がつくので,35の80 乗すなわちが場合の数となるゲームは, 何人でプレーするゲームか( 何人ゲームか ) 勝ちをプラス, 負けをマイナスとして, 全体としてゼロになるか ( 零和ゲームか ) 理論上, いつか終わるゲームか ( 有限ゲームか ) 敵の情報がこちらに全部わかっているか( 完全情報ゲームか ) 89

2 JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May 偶然性が入らないゲームか ( 確定ゲームか ) という性質によって分類されるチェスは, 二人零和有限完全情報確定のゲームの代表格であるチェッカー, オセロ, 五目並べ, 将棋, 囲碁などは同じ性質を持っているこれらのゲームには理論上必勝法が存在すること ( 先手および後手が最善を尽くせば, 先手必勝か後手必勝か引き分けになることが決まっていること ) がゲーム理論によって証明されているコンピューターにとって完全情報ゲームの方が扱いやすいのでこの研究が先に進んだが, バックギャモン, コントラクトブリッジ, ポーカー, マージャン, 大貧民など不完全情報ゲームの研究もその後盛んに進められている現実の社会は自分以外のことはわからないので不完全情報であるしたがって不完全情報ゲームの方が現実の社会に近いので, 傾向としては完全情報ゲームから不完全情報ゲームへと研究は進んでいる ShannonとTuringはチェスの探索にゲーム理論で von Neumannらが開発したミニマックス法 ( 味方はこちらにとって最善の手を, 敵はこちらにとって最悪の手を選ぶという方法 ) を使うことを提案し, このミニマックス法がその後のゲームの探索の基本となったゲームのプログラムを強くするには, ミニマックス法を基本とした探索手法の改良局面を点数化する( 静的 ) 評価関数の精緻化の2つが求められる理論的には例外が存在するものの, 経験的にほとんどの場合ゲームはより深く先読みした方が強くなるので, 同じ時間でできるだけ深く先読みできる探索手法が望ましいことになるチェスのプログラムを強くすることを目指してさまざまな工夫が試みられたミニマックス法は探索の末端の局面のすべての評価値をしらみつぶしで求めなくてはならないので時間がかかり, その分深く読めないという欠点があるミニマックス法と探索結果は同じで, それより効率のよい手法が経験的に開発されたそれがアルファベータ法であるチェスのプログラムで経験的に使われているのをアルゴリズムとしてまとめたのがKnuthである Knuthは末端の局面の数がN 個のときに, アルファベータ法は最も効果が高い場合に N 個だけ評価値を求めればいいことを明らかにした 3) アルファベータ法の効果が高くなるのは, 展開した探索木が評価関数の値の大きい順番になっているときであるしたがって1 手先を読むたびに, 評価値を計算して大きい順に並べ替えておくのがよいことになるチェスのプログラムで経験的にそのことがわかり, それが後に反復深化 (iterative deepening) という探索手法として定式化された新しい探索手法の多くはチェスを例題として開発されたといってよいたとえば, ある指し手の評価値だけが他の評価値とかけ離れているときにその指し手に注目して, その指し手だけをより深く読むという選択的深化 (selective deepening), 評価値がどの程度信頼できるかを表す共謀数 (conspiracy number) とそれを拡張した証明数 (proof number) 反証数(disproof number) などが有名である探索を効率的に行うためのハッシュ表, ビットマップなどデータ構造の工夫もチェスを通して確立したチェスは ( アルファベータ法を使って ) ルール上指せるすべての手を読むという全数探索が有効だったので, スーパーコンピューターやチェス専用マシンを使うことによって探索の速度を上げようという試みが盛んになされたまた並列に探索するアルゴリズムもチェスを例題にして盛んに研究された ( アルファベータ法は探索全体をアルファ値, ベータ値によって制御するので並列に探索するには困難があった ) またチェスは駒の再利用ルールがないので, ゲームの進行に伴って駒の数が単調に減少していく駒が盤面に数個しか残っていない局面になると, コンピューターは ( ほぼ ) しらみつぶしの探索によってその局面を解く ( 双方が最善手を続けたら先手が勝つのか, 後手が勝つのか, 引き分けになるのかを求める ) ことができるこの探索をあらかじめ行ってデータベース化したものが終盤データベースであるコンピューターはこれを持っていればこのデータベースに含まれる局面で最善手を指すことができ 90

3 る 1980 年代には盤面残り5 駒のすべての局面の終盤データベースが作られた 1990 年代から2000 年代にかけて盤面残り6 駒のほとんどの局面の終盤データベースが作られた ( その間にコンピューターが世界チャンピオンに勝ってしまったので, 終盤データベースを作る意味が薄くなったといえる ) チェスはコンピューターにとってかなり難しいゲームであったので, チェスよりも場合の数が小さいチェッカー ( 場合の数は10 40 ), オセロ ( 場合の数は10 60 ) なども例題として取り上げられたチェッカーは1994 年 ( その後 2007 年に理論的に引き分けのゲームであることが判明した ) に, オセロは1997 年にコンピューターが世界チャンピオンに勝利したチェスは何度も人間との対戦を経た後,1997 年に Deep Blueが世界チャンピオンのKasparovに勝利した 6 回戦勝負で5 回戦が終わった時点では,1 勝 1 敗 3 引き分けのイーブンであったが, 最終戦でKasparov が緊張のあまり序盤で大悪手を指して負けてしまったこれはフロック勝ち ( まぐれ勝ち ) で, この時点ではまだKasparovの実力がDeep Blueに勝っていたと思われるその後の進歩によりコンピューターは人間より明らかに強くなっている Deep Blueはスーパーコンピューターにチェス専用マシンを数百台並べた構成であったが, もはやパソコン1 台でも人間がかなわないまでになっている 3. チェスの次は将棋チェスよりも場合の数が大きいゲームに中国将棋 ( ), 将棋 ( ), 囲碁 ( ) が存在する中国将棋は探索問題としてみるとチェスに近い ( すでに人間よりもコンピューターの方が強くなっている ) が, 将棋と囲碁はチェスよりはるかに場合の数が大きく, チェスとは異なる手法が必要なので, チェスに続く例題として適切である将棋はチェスと同じ敵の重要な駒 ( キングあるいは玉 ) を捕まえるゲームであるが, チェスは敵から取った駒が使えないのに対して将棋では敵から取った駒を再利用できる ( 持ち駒制度と呼ばれる) ため, 終盤は序盤より分岐数が大きくなるチェスは収束型 ( 終盤に近づくほど指し手の可能性が低くなる ) ゲームであるが, 将棋は発散型 ( いつまでも指し手の可能性が高い ) ゲームなのである将棋は日本固有のゲームなので, 将棋を対象とした研究は当然のこととして日本が中心になった 4 )~ 9 ) このことが日本におけるゲーム情報学研究を活発にして, ゲーム情報学において, 世界で日本が主要な立場を占める原動力になったと思われる将棋のプログラムの開発は1970 年代に始まったが, 当時のコンピューターの能力では将棋はチェスのような全数探索は到底無理だったので, 前向き枝刈りの探索手法注 1) が盛んに研究されたミニマックス法 ( アルファベータ法 ), 反復深化などチェスで有効だった手法で将棋でも使える手法はおよそすべて使った将棋は発散型ゲームなので, チェスで有効だった終盤データベースの手法は使えないその代わりに詰め将棋という将棋から派生したパズルを解くアルゴリズムの研究が盛んになされた詰め将棋の研究は1990 年前後から本格的に進められ, その中でさまざまな探索の手法が試された有効だったのはチェスで提案された ( そしてチェスではあまり有効でないとされた ) 証明数反証数を用いた手法である詰め将棋のプログラムは2000 年前後にはすでにプロ棋士を超える能力を示した評価関数はチェス同様に手作業で作成と改良を行っていたが, チェスの評価関数は駒の損得という明快な基準があったものの, 将棋の評価関数は複雑でなかなか強くならなかった 2000 年代の半ばに登場した保木邦仁のボナンザ (Bonanza) によってコンピューター将棋は革命的な進歩を遂げた保木の工夫は, (1) それまで将棋は前向き枝刈りの探索をしていたのをチェスのように全数探索にした 10) (2) それまで評価関数は手作業で作っていたのを棋譜からの機械学習で作るようにした 11) の2 点であるこの工夫をしたボナンザが圧倒的な強さでコンピューター将棋のトップに立ったので, 他の研究者開発者もこぞってこれらの方法を取り入 91

JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May http://jipsti.jst.go.

年代になってコンピューターとプロ棋士が対戦するようになった 2010 年には情報処理学会の50 周年記念のイベントとして, 女流プロ棋士の清水市代女流王将 ( 当時 ) と合議制のコンピューター将棋あから2010 が対戦してあから2010 が勝利した( 図 1, 図 2) 2013 年,2014 年と電王戦と称してプロ棋士 5 人とプログラム5つが対戦したが,3 勝 1 敗 1 分け,4 勝

4 JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May れた特に上記の (2) の方法は強豪のプログラムすべてに導入されており, ボナンザメソッドと呼ばれている保木はボナンザのアルゴリズムをすぐに公開し, またプログラムのソースコードも無償で公開したこれは後述するようにコンピューターチェスの文化を引き継いだものであるが, 研究成果を公開するという習慣がこの研究領域の発展を支えているものと思われる 2010 年代になってコンピューターとプロ棋士が対戦するようになった 2010 年には情報処理学会の50 周年記念のイベントとして, 女流プロ棋士の清水市代女流王将 ( 当時 ) と合議制のコンピューター将棋あから2010 が対戦してあから2010 が勝利した( 図 1, 図 2) 2013 年,2014 年と電王戦と称してプロ棋士 5 人とプログラム5つが対戦したが,3 勝 1 敗 1 分け,4 勝 1 敗と, ともにコンピューターが圧勝したすでにコンピューターはトップクラスのプロ棋士 ( 竜王, 名人 ) のレベルに達したと思われる今トッププロ棋士とコンピューターが対戦すれば勝率的にはコンピューターが勝ち越す可能性が高い現在のトップ棋士である羽生善治氏との対戦はすぐに実現しないと思われるので, 情報処理学会は2015 年 10 月に, 将棋で人間とコンピューターの強さを問うことは学問的には結論が出たという終了宣言を行った 4. 将棋の次は囲碁囲碁は中国発祥のゲームであるが, 中国では廃れて日本で盛んになった ( 今中国で盛んなのは, いわば日本からの逆輸入である ) 囲碁は, 他に似たルールのゲームが存在しない漢字を使っていないので親しみやすいなどの理由で世界的に普及している最初にコンピューター囲碁の研究がなされたのは 1960 年代のドイツである ( チェスよりは遅いが将棋より早い ) 囲碁もチェスのように探索によって次の手を決めようとしたが, 囲碁の場合の数はとチェス ( や将棋 ) よりはるかに大きく, 普通の探索によってよい手を見つけるには候補手が多すぎて強くならなかった 2000 年代になってもまだとても弱い状態であった ( 初心者レベルよりはましでも, せいぜい初級者レベルであった ) 囲碁にも将棋のボナンザメソッドのような革命的な手法が現れたそれがモンテカルロ木探索であるこの元となったモンテカルロ法はvon Neumann の命名といわれるシミュレーションによって解を求める方法である 1990 年代にこれを囲碁に適用するというアイデアが発表されたものの, そのときは成功しなかった 2000 年代になってCoulomが Crazy Stone という囲碁プログラムの中でモンテカルロ法を応用した (UCTという見込みの高い手を集中的に読むアイデアを付け加えた ) モンテカルロ木探索を採用し, このCrazy Stoneが圧倒的な強さを示した囲碁にモンテカルロ法を適用するということは, ある局図 1 清水市代女流王将とあから 2010 の対戦図 2 清水市代女流王将とあから 2010 の対戦後の記者会見 ( 右端が筆者 ) 92

5 面から白と黒が交互にランダムに終局まで打ち進めるというシミュレーションを多数行って, 勝つ確率が一番高い手を選ぶということであるそこには囲碁の知識はほとんど何も入っていないこの一見単純な方法 ( 実はUCTなど細かい工夫が重要ではある ) で強くなることに驚き, その後の囲碁プログラムはみんなこの方法を取り入れているそれで囲碁プログラムは一気にアマチュアの六段程度の実力に達した 12) 最近までは日本の ZEN ( これもモンテカルロ木探索を用いている ) がCrazy Stoneを抜いて最も強い囲碁プログラムであったこれらのプログラムはまだたがいせん互先 ( ハンディなし ) で戦うのは無理であるが, トッププロ棋士と4 子 (4 個の石をあらかじめ隅の星の位置に置く ) のハンディで勝つまでになっていたトッププロ棋士に勝つのはまだ10 年はかかると思われたそこに2016 年 1 月にGoogleの AlphaGo というプログラムが二段のプロ棋士に互先で5 戦 5 勝の成績を上げたと発表して大ニュースになった 13) AlphaGoは, 深層学習( ディープラーニング ) モンテカルロ木探索強化学習という3つの手法をうまく組み合わせている大量のプロ棋士の棋譜をデータとして, 深層学習によってある程度の強さのプログラムを作り, そのプログラム同士の強化学習によってさらに強くしたこれまでコンピューター囲碁で成功しなかった評価関数を実質的に作ったことがAlphaGoの大きな特徴である手を決める部分では従来手法であるモンテカルロ木探索を使っている 2016 年 3 月には世界のトップクラスのイセドルという韓国人のプロ棋士と対戦して勝ち越して大きな話題になった事実上囲碁でもコンピューターが人間を抜いたことになる 5. 囲碁の次は二人零和有限完全情報確定のゲームで世界的に有名なものの中では, 囲碁の場合の数が最も大きいということでもし囲碁で人間よりもコンピューターの方が強くなってしまえば, もはや残っているゲームは存在しない前述したように流れとしては完全情報ゲームよりもコンピューターにとって扱いが難しい不完全情報ゲームに関心は移りつつある ( 囲碁は完全情報ゲームであるが場合の数がと圧倒的に大きく, その点で完全情報ゲームと不完全情報ゲームの橋渡しの役割を担っているといえる ) 不完全情報ゲームとしてはバックギャモン, コントラクトブリッジ, ポーカー, マージャンなどが研究の題材として取り上げられているバックギャモンは強化学習によって世界チャンピオンに勝つようなプログラムが開発された ( 強化学習の成功例として有名である ) コントラクトブリッジはトランプのゲームとして世界で最もプレーされているゲームで, 探索を含めてさまざまな研究が行われているがまだ人間に追い付いていないポーカーはさまざまなルールが存在するが, その一部のルールのポーカーについてはプログラムが世界チャンピオンを破っている ( 後で述べるように, あるルールのポーカーは解かれている ) マージャンは日本や中国などで非常に盛んで敵が 3 人もいる (4 人 1 組 ) ゲームで, 現実の社会に近く例題として優れているが, ギャンブル性が高く不健全な印象がある ( マージャンというゲーム自体に罪はないが賭けてプレーされることが多い ), 世界的にさまざまなルールがあって統一されていない ( 標準となるルールを仮定しにくい ) などの理由で以前は研究が少なかった最近インターネット上で ( 賭けない ) 標準ルールのマージャンが盛んになってきたので, それを対象としたマージャぱいふンの研究が盛んになってきたたとえば多数の牌譜 ( マージャンのプレー記録 ) のデータをインターネットマージャンから集めていわゆる格言の妥当性を統計的に調べる研究が行われているゲームを解く ( 一般的な言い方であれば必勝法を見つける ) のも, 探索のよい例題である ( 最強の ) 人間に勝つよりもそのゲームを解く方が一般に探索問題としては難しい五目並べ ( 連珠 ) はハンディなしだと先手がとても有利なので, 後手にハンディを与えて対戦するのが普通であるが, ハンディなしの五目 93

6 JOHO KANRI 2016 vol.59 no.2 J ournal of Information Processing and Management May 並べは先手必勝であることが1990 年代に解明されているオセロの盤面は8 8であるが, それを6 6に小さくしたミニオセロは後手必勝であることが, 同じく1990 年代に解明されている 8 8の本当のオセロは現在解く試みがなされているが, まだ解かれたという報告はない ( おそらく6 6と同様に8 8も後手必勝と想像されている ) チェッカーは1990 年代にコンピューターが世界チャンピオンに勝った後に解く試みがなされ,2007 年に解かれている ( 引き分けであることがわかった ) 不完全情報ゲームは偶然性があるので完全情報ゲームと同じ意味では解けない ( いわゆる必勝法は存在しない ) が, 最適戦略を見つけることを解くと見なせば解くことは可能である最近ポーカーの一種が解かれているじんろうなんじごく最近になって人狼 ( 正式には汝は人狼なりや? 英語ではWerewolf) というゲーム注 2) がゲーム情報学の研究対象となっている 14) 人狼は不完全情報で非対称の多人数ゲームであるが, 自然言語によるコミュニケーションが重要な役割を果たしている今まで対象としてきた思考ゲームとはかなり異なるゲームなので, 人狼を対象とした研究によって新たな知見が得られることが期待される CEDEC (Computer Entertainment Developers Conference) 2015では, 人狼のプログラム同士が戦う第 1 回人狼知能大会が開催されている 6. おわりにゲーム情報学は日本では長いこと疎外され続けてきたゲームという遊びを研究の例題にするなどもっての外であるという風潮が強かったためである一方で米国とヨーロッパはチェスなどのゲームを例題にした研究開発を盛んに進めてきた例題はゲームであるが, その研究成果はゲーム以外の多くの現実の社会問題に対して広く使われている Shannonと Turingという2 人のコンピューターのパイオニアがチェスを例題にした研究をしたことも大きかったと思われる日本のコンピューターのパイオニアは, 日本には将棋と囲碁という, ゲームの中でもコンピューターにとってとても難しい, すなわちとてもよい例題が存在するのに, 見向きもしなかった日本は長い間それを疎外し続けてきたために, 情報処理の極めて大事な部分で大きく出遅れてしまったことを認めなくてはならない幸い1999 年に情報処理学会にゲームをテーマにした研究会 ( ゲーム情報学研究会 ) が発足し, ゲームの中心がチェスから将棋と囲碁に移行してきたこともあって日本にもゲーム情報学の研究者が増えてきて, よい研究成果を出しつつあるかつてチェスがそうであったように, 将棋と囲碁を例題とした研究からゲーム以外の現実の社会に適用される研究成果が日本から出ることが強く期待される ( たとえばボナンザメソッドを将棋以外の対象に適用する試みが始まっている ) 世界的に対象とするゲームが完全情報から不完全情報に移行しつつある ( 囲碁がちょうどその中間にある ) 前述したように不完全情報ゲームの方が現実の社会に近いので, この研究領域が基礎から徐々に応用の方にシフトしていくと思われるたとえばシミュレーション技術やVR 技術などと結び付いて人生のシミュレーションを行うことも視野に入ってくるであろうこれまでチェスのプログラムはチェスだけ, 将棋のプログラムは将棋だけ, であったが, あるゲームのルールを入力すればそのゲームをプレーする ( できるだけ強い ) プログラムを出力するという汎用ゲームプレー (general game playing) の研究が盛んになりつつあるこれは最近盛んになりつつある汎用人工知能 (artificial general intelligence) の1つの例であり, 今後の人工知能の研究開発の流れを示すものとして注目される松原仁 ( まつばらひとし ) 1981 年東京大学理学部情報科学科卒業 1986 年同大学院工学系研究科情報工学専攻博士課程修了同年通商産業省工業技術院電子技術総合研究所 ( 現産業技術総合研究所 ) 入所 2000 年公立はこだて未来大学教授人工知能, ゲーム情報学, 観光情報学などに興味を持つ人工知能学会会長, 情報処理学会理事, 観光情報学会理事 94

7 本文の注注 1) 注 2) 先読みの浅い部分ではすべての枝を読み, 深い部分では見込みの高い枝だけを残し他は読まないという方法人間に化けられる人食い狼 ( 人狼 ) が, 夜に村人を一人ひとり殺していく村人と人狼チームに分かれ, 正体をあばいていくゲーム参考文献 1) 松原仁. ゲーム情報学 :1. ゲーム情報学の現在 : ゲームの研究は日本で疎外されなくなったのか. 情報処理. 2012, vol. 53, no. 2, p ) Shannon, C. E. Programming a computer for playing chess. Philosophical Magazine. 1950, ser. 7, vol. 41, no. 314, p ) Knuth, D. E.; Moore, R. W. An analysis of alpha beta pruning. Artificial Intelligence. 1975, vol. 6, no. 4, p ) 松原仁編著. コンピュータ将棋の進歩. 共立出版, 1996, 152p. 5) 松原仁編著. コンピュータ将棋の進歩 2. 共立出版, 1998, 150p. 6) 松原仁編著. コンピュータ将棋の進歩 3. 共立出版, 2000, 122p. 7) 松原仁編著. コンピュータ将棋の進歩 4. 共立出版, 2003, 148p. 8) 松原仁編著. コンピュータ将棋の進歩 5. 共立出版, 2005, 178p. 9) 松原仁編著. コンピュータ将棋の進歩 6: プロ棋士に並ぶ. 共立出版, 2012, 132p. 10) 保木邦仁. コンピュータ将棋の新しい動き :3. コンピュータ将棋における全幅探索と futility pruning の応用. 情報処理. 2006, vol. 47, no. 8, p ) 保木邦仁. 局面評価の学習を目指した探索結果の最適制御. 第 11 回ゲームプログラミングワークショップ 2006 論文集. 情報処理学会, 2006, p ) 美添一樹, 山下宏著 ; 松原仁編. コンピュータ囲碁 : モンテカルロ法の理論と実践. 共立出版, 2012, 222p. 13) Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis. Mastering the game of go with deep neural networks and treesearch, Nature. 2016, no. 529, p ) 片上大輔, 鳥海不二夫, 大澤博隆, 稲葉通将, 篠田孝祐, 松原仁. エンターテイメントにおける AI: 人狼知能プロジェクト. 人工知能. 2015, vol. 30, no. 1, p Author Abstract Game Informatics is one of research topics in information processing. Chess was the major game in game informatics about 50 years from 1950, in 1997 Deep Blue won the world champion Kasparov. Next to chess was shogi (Japanese chess). Computer shogi does not play against the world champion yet, but it will win if play. Go is very difficult for computers because its search space is much larger than chess's and shogi's. Recently computer go won against a professional player by application of deep learning. It will win against the world champion with several years. From now imperfect games such as Werewolf will become the target of game informatics. Key words chess, go, shogi, Werewolf, search, artificial intelligence 95

Microsoft PowerPoint - ゲーム理論2018.pptx

Microsoft PowerPoint - ゲーム理論2018.pptx 89 90 ゲーム理論 ( 第回ゲーム木探索 I) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ ゲーム木探索行動の選択が一回だけではなく交互に繰り返し生じる前の番に相手の選んだ手は分かる 9 9 例題二人で交代に, から順にまでの数を言う.