Game Programming

ゲームプログラミング shiget84 高専カンファレンス in 福井 2009年02月28日

まずはじめに • 発表に慣れてません 見苦しい点、聞き苦しい点などがあると思います ご了承ください • 間違ったことを言ってるかもしれません 間違いに気づいたかたは、気軽に指摘して下さい http://twitter.com/shiget84/ http://d.hatena.ne.jp/shiget84/

自己紹介 • Shiget84 • 1984年12月10日生まれ （０ｘ１８歳） • 2005年3月 福井工業高等専門学校卒業 • 2009年3月 某大学 修士課程 修了予定

ゲームプログラミング

ゲーム

コンピュータチェス vs 人間 • 1997年 Deep Blue VS カスパロフ （IBMのスパコン）

（世界チャンピオン）

2勝1敗3分け DEEP BLUEが勝ち越し

コンピュータ将棋 vs 人間 • 2005年9月 TACOS VS 橋本崇載五段（現七段） 126手で 橋本五段（当時） が勝利 80手くらいまでは互角かTACOSがやや優勢 日本将棋連盟 「連盟に断りなく、公の場でのコンピュータと の対局を禁じる」

コンピュータ囲碁 vs 人間 • 2008年 9路盤においてプロと3局対戦：1勝2敗 Mogo：256コアのクラスタ （複数のコンピュータを ひとまとまりにしたシステム）

コンピュータ囲碁 • 2008年 9路盤においてプロと3局対戦：1勝2敗

1勝 革命的な新手法:モンテカルロ木探索

ゲームプログラミング

ゲームプログラミングの話題 • 探索手法 ミニマックス探索 αβ探索 実現確率探索 証明数探索 … • 機械学習 … • …

ゲームプログラミング

Minimax 探索

モンテカルロ木探索

基礎知識

ゲームの木

ゲームを木で表現

・・・

・・・

・・・

・・・

・・・

・・・

・・・

・・・

ゲーム木 ○自分 □相手

ゲームプログラミング

Minimax 探索

モンテカルロ木探索

Minimax探索 • 前提 自分（プレイヤA） プレイヤAが勝つために着手を行う 相手（プレイヤB） プレイヤBが勝つために着手を行う プレイヤAにとっては不利な着手を行う

ゲーム木の探索

A

B

負

D 勝

○自分の局面 □相手の局面

C

負

E 負

勝

F

G

負

勝

H 勝

I 勝

ゲーム木の探索

A

B

負

D 勝

○自分 □相手

C

負

E 負

勝

F

G

負

勝

H 勝

I 勝

Minimax探索 • 勝ち負けが最初から読み切れない • 評価関数を用いて局面評価を行う – 自分に有利な局面は＋の値 – 自分に不利な局面は－の値

• 自分の着手：評価関数の値を最大にする • 相手の着手：評価関数の値を最小にする

Minimax 探索 30

A

B

-50

D 100

C

-40

E -50

○自分 □相手 30

F

G

-40

60

H 30

I 40

ゲームプログラミング

Minimax 探索

モンテカルロ木探索

モンテカルロ法 • 乱数を用いたシミュレーションを何度も行うこ とにより近似解を求める計算手法 IT用語辞典 e-Words より （http://e-words.jp/w/E383A2E383B3E38386E382ABE383ABE383ADE6B395.html）

長さが1の正方形 内接する 1/4 の円 ランダムにn個の点を落とす 円のなかに落ちた点の数で 円周率が近似できる

ゲームにおけるモンテカルロ法 両者のランダム着手でゲームを終わらせる N回行う

勝率：3割

勝率：7割

勝率：5割

モンテカルロ木探索 • モンテカルロ法 シミュレーション回数は どの手も同じ • モンテカルロ木探索 ・勝率が良い手の シミュレーション回数を多く ・閾地を超えたら木を生長

悪手

好手

悪手

好手

モンテカルロ木探索 • モンテカルロ法 シミュレーション回数は どの手も同じ • モンテカルロ木探索 ・勝率が良い手の シミュレーション回数を多く ・閾地を超えたら木を生長

悪手

好手

悪手

好手

モンテカルロ木探索 • 局面を評価するのにモンテカルロ法を用いる

局面評価関数を用いる必要がない

評価関数の作成が難しかった コンピュータ囲碁における革命的な手法

ゲームプログラミング

Minimax 探索

モンテカルロ木探索

高専生とゲームプログラミング • 柿木義一さん（石川工業高等専門学校出身）

柿木将棋

柿木将棋 for iPhone http://homepage2.nifty.com/kakinoki_y/iphone/kshogi.html より

高専生とゲームプログラミング • 野口陽来さん（富山工業高等専門学校出身） 囲碁プログラム 誤碁能美譚 メインプログラマ

北國新聞2009年01月17日朝刊

ゲームプログラミングで世界へ • Computer Olympiad コンピュータプログラム同士の世界大会 チェス、将棋、囲碁など http://en.wikipedia.org/wiki/Computer_Oly mpiad

まとめ • ゲームプログラミングをしよう！ Minimax探索 モンテカルロ木探索 • 高専生も活躍してる！ • 世界に挑戦できる！

ありがとうございました

参考文献 • コンピュータチェス ISBN 4781907237 • コンピュータ将棋の頭脳 ISSN 4910054701173 • コンピュータ将棋協会 http://www.computer-shogi.org/about_csa.html • 飯田教授らが開発したコンピュータ将棋はプロ棋士 に惜敗 http://www.jaist.ac.jp/news/2005/0920.html

参考文献 • ボナンザVS勝負脳―最強将棋ソフトは人間を超えるか ISBN 4047101079 • モンテカルロ木探索 理論編 http://www.digrajapan.org/modules/mydownloads/vi sit.php?cid=10&lid=11 • コンピュータ囲碁の入門 ISBN 4320121503

参考文献 • UCTの擬似コードなど http://blog.livedoor.jp/yss_fpga/archives/50392942. html • コンピュータゲーム研究の現状・動向、完全情報二人 ゲームの探索法 http://www2.ci.sys.fit.ac.jp/ai1/computergame.html