スライド 1
|
|
|
- あきみ このえ
- 7 years ago
- Views:
Transcription
1 モンテカルロ法によるゲームAIの可能性 美添一樹 スライドの最後に 当日説明しきれなかった内容の補足があります
2 自己紹介 ( 最初の ) 大学院生時代には並列計算を研究 その後 某研究所に就職 携帯関係の研究開発 なぜか大学院に戻って 人工知能の研究 今はいわゆるポスドクで 量子計算機の研究中 コンピュータ囲碁の研究も続けている 専門はたぶん 探索アルゴリズム 囲碁は自称三段 強い囲碁プログラムを作って自慢したい けど時間がない あとゲームは好きです いろいろと 2
3 あらすじ : モンテカルロ木探索 (MCTS) コンピュータ囲碁を革命的に強くするアルゴリズムが発見された (2006 年 ) なぜ 2005 年までは囲碁が弱かったのか ついでに他のゲーム AI 研究についてちょっと紹介 MCTS はどういうアルゴリズムか 理論的に奥が深い ( でも今日は理論は省略 ) 見た目の性質も面白い 長所と短所を紹介 特に 汎用性が高い 現在の応用例について紹介 二人ゲーム : 囲碁, 将棋, アマゾン, Hex, Lines of Action 等 その他ゲーム : ハーツ, カタン, Magic the Gathering, さめがめ等 ゲーム以外 : 最適化 プランニング バイオメトリクスなど ゲームAI 開発者に新しい選択肢を提供できれば嬉しい 3
4 コンピュータ囲碁に起きた革命 2008 年 3 月末 パリ囲碁トーナメントのエキシビションでプロ対コンピュータの対戦が実現 ( プロ : タラヌ カタリン五段 ( 日本棋院中部総本部所属 ) コンピュータ :MoGo 9 路盤はハンデなしで 3 局対戦 MoGo の 1 勝 2 敗 19 路盤は MoGo が 9 子のハンデをもらい 1 局対戦 カタリン五段の勝利 ここが革命です 念のため 囲碁が弱かったから新しいアルゴリズムが産まれた それが他の問題にも波及しつつある
5 モンテカルロ法 = モンテカルロ木探索 2009 年 4 月 8 日付朝日新聞夕刉 コンピュータ囲碁が急激に強くなりつつあるという記事が載りました 5
6 4 つの背景 モンテカルロシミュレーション ゲーム AI MCTS Monte Carlo Tree Search 機械学習 Multi-armed bandit 計算機の速度向上 6
7 ゲーム AI 研究 人工知能の分野では まじめな研究対象 商業ゲームもよく研究対象になる 学会によっては FPS や戦略シミュレーションなども AI のトップレベルの学会でもゲームが題材になる 主にチェスや囲碁だが freeciv に関する論文が出たことも 様々な技術のテストベッドとして有用である 研究のための研究はすみやかに淘汰される傾向がある 理屈倒れの研究は見向きされない min-max 探索 (alpha-beta 探索 ) の発展 チェス オセロ チェッカーなど 二人ゼロサム完全確定情報ゲーム 知識ベースのアプローチ 初期のチェスなど 機械学習 ( ニューラルネットなど ) バックギャモンなど モンテカルロシミュレーションの活用 バックギャモン Scrabble ポーカーなど 7
8 二人零和完全確定情報ゲーム 二人 (1 対 1) ゲーム 零和である 全て情報が見えている 不確定要素がない ( サイコロを振らない ) 2005 年時点でのコンピュータの強さ チェッカー オセロ チェス 1994 年に世界チャンピオンに勝利 (2007 年に初期配置の引き分け証明 ) 1997 年に世界チャンピオンに完勝 1997 年に IBM の DeepBlue が当時世界チャンピオンの Kasparov を破る ここに大きなギャップがあるこれはなぜか? 将棋 囲碁 アマトップレベルの強さと言われている アマ 3 級くらい? ( 深い突っ込み禁止 ) 二人零和完全確定情報ゲームは ゲーム理論的には一番簡単 しかし人間との比較では? ポーカー ( テキサスホールデム ) は人間のチャンピオンにプログラムが勝利 (2008 年 ) バックギャモン Scrabble などは かなり前から人間より強い 8
9 余談 ポーカー ( テキサスホールデム ) はコンピュータが強い 人間ペア対プログラム 2 対 2 の対戦 AAAI で開催 ( 全米人工知能会議 : AI では 2 番目に格が高い ) 2008 年に Polaris( プログラム ) が人間のチャンピオンペアに勝利 The Second Man-Machine Poker Competition オンラインポーカーのサイトで リアルマネーを使えるところもあるので かなり問題 コンピュータはいろいろなゲームで強いが例外もある 一人ゲーム : 倉庫番 実は人間にしか解けない問題が多数ある 二人ゲーム : 囲碁 ただし 今は急激に強くなっている 多人数ゲーム : これはたくさん弱い物がある 9
10 機械学習 機械学習の理論 長年研究されてきた強固な理論 あとでちょっと説明 Multi Armed Bandit 問題 与えられた枚数のコインでできるだけ多くの報酬を得るための戦略を考えよ コンピュータの速度向上 速いコンピュータを必要とするアルゴリズム alpha-beta 探索 知識ベースより強くなった LDPC 符号 (1950 年代提案 ) 地上デジタル放送など トマスロのアルゴリズム (1960 年代提案 ) superscalar プロセッサ ボナンザメソッド 将棋で大きな成功 モンテカルロ木探索 これが本題 コンピュータが十分速いことに最初に気づく人は偉い 10
11 モンテカルロシミュレーションとは? 一番簡単な例 ( よく説明に使われる例 ) 円周率を求める 乱数がたくさん必須 モンテカルロはカジノで有名 主な応用例 物理シミュレーション 経済シミュレーション 様々な分野で使われている歴史のあるアルゴリズム 本当は凄く奥が深い ランダムにたくさん点を打つ 数える 割り算する 点が多いほど正確 投げやりです 11
12 モンテカルロシミュレーションとゲーム 不確定要素があるゲームにモンテカルロシミュレーションを使うのは自然なアイデア バックギャモン Scrabble ポーカー ( テキサスホールデム ) このアイデアはかなり成功した 人間のチャンピオンレベルに近いものも 完全確定情報ゲームにモンテカルロシミュレーションを使うアイデアが実はあった 原始モンテカルロ囲碁 12
13 モンテカルロシミュレーション 機械学習 Multi-armed bandit 以上が 2005 年時点でのゲーム AI 研究の状況です ゲーム AI 計算機の速度向上 なぜ囲碁だけこんなに弱いのか? 二人零和完全情報ゲームでは完全な仲間外れ チェスもオセロも将棋も強いのに 他のゲームだって強いものが多い ポーカーとかバックギャモンとか メジャーなゲームなのに弱いのは囲碁だけ 13
14 普通の二人零和完全情報ゲーム min-max 探索 +ab 枝刈り a カット b カットにより探索が省略される 候補手が理想的な順番にソートされていれば 探索ノード数は元のツリーのノード数のほぼ sqrt になる [Knuth and Moore 1975] Max node Min node 探索順序 14
15 囲碁の難しさその 1 探索空間が大きい 19 路盤囲碁は探索空間が巨大 チェッカーは初期局面が引き分けになることが解明された (2007 年 ) 同様に 5 路盤の囲碁は最善手順が完全解明されている チェッカー オセロ チェス ところが 9 路盤の探索空間はチェス以下 それでも 2005 年までは 19 路同様に弱かった どっちも ( 建前は ) アマ初段くらい これはおかしい だって他のゲームだと 性質の似たゲームなら探索空間が小さい方がコンピュータ有利 将棋 チェス 中国将棋などの比較 チェッカー (8 路 ) とドラフト (10 路 ) の比較 なぜ 19 路盤と 9 路盤の強さに差が無いのか? 将棋 囲碁 (9 路盤 ) 囲碁 (19 路盤 ) 探索空間 ( 可能な局面数 ) 15
16 囲碁の難しさその 2 評価関数が作れない この数値はゲームのスコアを示す しかし 実際のスコアは勝敗がつくまで深く探索しなければ分からない よって 探索を途中で打ち切り その時点でのスコアを近似する評価関数を用意する 評価関数はどうやって作るもの? 16
17 評価関数の例 囲碁以外のゲーム オセロ 隅や辺の重要な箇所のパターンを学習して評価関数を作成 オセロでの学習は簡単にうまくいく logistello や Zebra が有名 チェスや将棋 駒の価値 玉の安全度 駒が自由に動けるか等 チェスの例 : ポーン 1 点 ビショップとナイト 3 点 ルーク 5 点 クイーン 9 点 キング 点 ボナンザメソッドなどもあり 人間の棋譜から自動的に評価関数を作成 17
18 囲碁の評価関数の難しさ 石の価値は平等 なので 駒の価値などは用いることができない オセロのような明らかに特徴のある箇所が少ない これは特に 19 路盤で顕著 18
19 囲碁の評価関数の難しさ 領域の広さを競うなら 広さを基準にする? しかし領域が確定するのはゲームの最後 布石終了時中盤戦終局時 白 8.5 目勝武宮正樹趙治勲 19
20 囲碁の評価関数の難しさ 局所的な最善手 全局的な最善手 石を取るのは局所的には得 しかし捨石は基本的なテクニック 白は取られたが全ては作戦 最終的には 白の快勝 20
21 囲碁の評価関数の難しさ 石の価値は平等 なので 駒の価値などは用いることができない オセロのような明らかに特徴のある箇所が少ない これは特に 19 路盤で顕著 領域の広さを競うなら 広さを基準にする? しかし領域が確定するのはゲームの最後 局所的な最善手 全局的な最善手 石を取るのは局所的には得 しかし捨石は基本的なテクニック 21
22 人間はどうやってプレイしてるの? 説明不能です 特に中盤は難しいです 石が厚かったり薄かったり 形が良かったり悪かったり 味が良かったり悪かったり 地に辛かったり甘かったり 石が軽かったり重かったり 初段くらい無いと用語の意味が通じません 22
23 つまり囲碁は難しい ( 難しかった ) チェスや将棋の駒得のような明らかな評価基準がない 何かの要素の足し算で局面の優务を評価するのは難しい 評価関数は速く 正確である必要がある 最低でも 1 秒に 1 万回くらいは計算できないとダメ 囲碁の評価関数は 遅いか 不正確である 遅い上に不正確 というと怒られるかな 23
24 囲碁の評価関数は難しいが 中盤の評価関数は非常に難しい しかし終局後ならスコア判定は簡単 中国ルールの終局図ならもっと簡単 24
25 従来の囲碁プログラムの例 GNU Go 商用ソフトの中身は分からないので オープンソースの囲碁プログラム GNU Go について説明 GNU Go は最強の商用プログラムよりも少し弱い 多数の複雑な評価関数を用いている コードは C で約 80,000 行 ( 当然 ほぼ全て思考ルーチン ) パターンデータベースがテキストで約 52,000 行 棋力はアマ初段より少し弱い 19 路でも 9 路でも同じくらいの強さ 25
26 GNU Go の着手選択 職人芸の結晶 (?) 盤面の状況を分析する 連絡 切断をある程度調査 それから石の安全度を調査 パターンデータベースにマッチする手を発見し 評価値を割当てる 着手の目的別に候補手を生成し 評価値を割当てる 目的 : 自分の石を守る / 相手の石を攻める / 自分の領域を広げるなど 複数の評価値の依存関係を調査 全部意味の違う値 一番評価値の高い手をプレイする 26
27 原始モンテカルロ囲碁 乱数を用いて囲碁をプレイする [Brügmann][Bouzy][Cazenave] 囲碁は終盤に近づくに連れて合法手が減少する 合法手の中からランダムに選んで打つだけのプレイヤーでも終局可能 ただし 少し制約が必要 自分の 眼 には打たないようにする 二つ 眼 を持つ石は取られない 原始モンテカルロ囲碁 は説明の都合上つけた名前 変わったアイデアだと思われていた 不確定な情報がないゲームにモンテカルロシミュレーションを使う? 27
28 プレイアウトとは 乱数を用いて 終局までプレイすることをプレイアウトと呼ぶ ( 新しい用語 ) 普通の用語はシミュレーション 機械学習だとエピソードとも 28
29 プレイアウトによる局面評価 要するに たくさんプレイアウトを行って 勝てそうな手を選ぶ 凡例 黒の手番 白の手番 黒勝ちのプレイアウト 白勝ちのプレイアウト 29
30 もちろん原始モンテカルロ囲碁は弱い 深さが 2 段以上の木に対しては 最善手を返す保証は無い 相手がミスをしたら得だが 正しく応じられると損をする手があるとする 正解の手が少なければプレイアウト中には正解を打つ確率は低い 相手がミスをすることに期待して その手を打つ どれくらい弱いのか調べた論文あり ( 私も共著者 ) GNU Go 相手の勝率は 1 割くらいでした H. Yoshimoto, K. Yoshizoe, T. Kaneko, A. Kishimoto and K. Taura, Monte Carlo Go Has a Way to Go, AAAI-06, pp
31 CrazyStone の登場 2006 年の Computer Olympiad 囲碁 9 路盤部門優勝プログラム [Rémi Coulom 2006] モンテカルロを使っているらしい しかも打ち方が他のプログラムと全然違う 優勢だと手加減してきっちり僅差で勝つ 負けていると無理な手を打ってくる 単純なモンテカルロ囲碁は弱いはず 自分たちでそういう論文も書いたところなのに なんで? CrazyStone は原始モンテカルロ囲碁を改良したアルゴリズムを用いていた それがモンテカルロ木探索 コンピュータ囲碁界だけでなく ゲーム AI 研究に革命を起こした 31
32 モンテカルロ木探索によるプログラム 囲碁の評価関数は難しい これは今でも本当だとみんな思っている しかし 囲碁でも終局した状態なら簡単に勝敗の判定が可能 終局してるよ と教えてくれれば 計算は簡単 この性質をうまく利用したプログラムが CrazyStone 32
33 モンテカルロ木探索 Monte Carlo Tree Search 原始モンテカルロからの変更点は 2 つ 有利な手に多くのプレイアウトを割当てる プレイアウトの回数が閾値を超えたら木が成長する さらに以下の工夫が重要 プレイアウトが返す値は スコアでなく 勝ち / 負け スコア差ではなく 勝率を最大化するようにプレイする リードしているときは安全に 負けている時は無理な手も 勝率最大化により 対 GNU Go 勝率が 3 割台から 6 割以上に跳ね上がった 黒の手番 白の手番 黒勝ちのプレイアウト 白勝ちのプレイアウト 33
34 理論的背景 Multi-Armed Bandit 問題 統計学や機械学習の分野で研究されてきた Multi-Armed Bandit とは? 腕が複数あるスロットマシンのこと 空想上の存在 One-Armed Bandit = 一本腕の山賊 = スロットマシーン 善良な人から金を盗んでしまう一本腕の悪いヤツ 34
35 Multi-Armed Bandit 問題 与えられた枚数のコインで できるだけ多くの報酬を得るための戦略を考えよ 35
36 最善の戦略は? Multi-Armed Bandit 問題の最善の戦略は知られている [Lai and Robbins 1985] しかし 最善の戦略の性質が知られているだけで 実際に計算するのは大変 よって 計算量が簡単で かつ性能もそれほど悪くない戦略が求められる 36
37 全部に同じ枚数を投入しよう! そして平均を比べればいい? 原始モンテカルロ囲碁と同様の戦略つまり全然ダメ 37
38 UCB1 という戦略 各マシンについて UCB1 値という値 (Upper Confidence Bound) を計算 [Auer, Cesa-Bianchi, Fischer 2002] UCB1 値が最大になるマシンにコインを投入 X j : j 番目のマシーンの報酬の期待値 X j c 2logn n j n n j : それまでに投入したコイン数の合計 : j 番目のマシーンに投入したコインの数 c : アルゴリズムの性格を決める定数 定数 c は 実際には実験して決めるべき 38
39 UCB1 値の意味 期待値 X j c 2logn n j X j n n j c : j 番目のマシーンの報酬の期待値 : それまでに投入したコイン数の合計 : j 番目のマシーンに投入したコインの数 : アルゴリズムの性格を決める定数 バイアスと呼ばれる値コインが少ないほど多い コインが少ないマシーンほど 優遇するようにする! コインをちょっと投入した ハズレばっかりだけど タダ運が悪いのかも コインをいっぱい投入したけどハズレばっかり たぶん本当にダメ 39
40 有望なマシンにたくさんコインを投入しよう! それがつまり UCB1 有望な手に多くのプレイアウトを割当てる 40
![理論的背景 UCT (UCB applied to Trees) CrazyStone の成功を受けて提案された木探索アルゴリズム [Kocsis and Szepesvári 2006] UCB1 を木探索に応用 UCB1 値の高い候補手を辿って探索を行う](/docs-images/47/23733637/images/41-0.png "末端の候補手でプレイアウトの回数が閾値を超えると その手を展開する 探索回数 n が大きくなると UCB1 値が以下のように 期待値に収束することが証明されている 2logn logn X j c X j O n j n UCTはCrazyStoneの方法を改良し")
41 理論的背景 UCT (UCB applied to Trees) CrazyStone の成功を受けて提案された木探索アルゴリズム [Kocsis and Szepesvári 2006] UCB1 を木探索に応用 UCB1 値の高い候補手を辿って探索を行う 末端の候補手でプレイアウトの回数が閾値を超えると その手を展開する 探索回数 n が大きくなると UCB1 値が以下のように 期待値に収束することが証明されている 2logn logn X j c X j O n j n UCTはCrazyStoneの方法を改良し さらに理論的な基盤を与えた 41
42 UCT を使えば深さ 2 以上の木でも ( いつかは ) 最善手に到達する! 最初に UCT を取り入れた囲碁プログラムが MoGo [Gelly et al. 2006] 42
![2006 年に一気に成立 CrazyStone [2006 Rémi Coulom] 2006Computer Olympiad 囲碁 9 路盤部門で優勝 勝率最大化リードしているときは安全に 負けているときは冒険をする 重要な概念をほぼ網羅 5 月 UCT](/docs-images/47/23733637/images/43-0.png "Algorithm [2006 Kocsis & Szepesvári] 最善解に収束する証明 9 月 MoGo [2006 Gelly, Wang, Munos & Teytaud] UCT を用いた初のプログラム 19 路盤でアマ初段程度に到達 11 月 全部")
43 2006 年に一気に成立 CrazyStone [2006 Rémi Coulom] 2006Computer Olympiad 囲碁 9 路盤部門で優勝 勝率最大化リードしているときは安全に 負けているときは冒険をする 重要な概念をほぼ網羅 5 月 UCT Algorithm [2006 Kocsis & Szepesvári] 最善解に収束する証明 9 月 MoGo [2006 Gelly, Wang, Munos & Teytaud] UCT を用いた初のプログラム 19 路盤でアマ初段程度に到達 11 月 全部 2006 年の出来事!
44 複数の背景からブレイクスルー [2006 Rémi Coulom] [1950 年代 Robbins 等 ] [2002ごろ Auer, Cesa-Bianchiら ] [2006 Kocsis & Szepesvári] コンピュータ囲碁研究の歴史は長い 始まりは 1960 年代 しかし全然うまくいってなかった 山下さん ( 彩作者兼 AI 将棋作者 ) 12 年かけて作ったプログラムを MCTS で作ったプログラムが 2 ヶ月で逆転 暗黒面に墜ちた 当初の私の感想 こんなアルゴリズムでうまくいくはずがない! 私が間違ってました
45 その後の進歩 MoGo が UCT を採用して猛威を奮って以降 CrazyStone を含め 多くのプログラムが UCT を採用 Computer Olympiad 電通大で開催された UEC 杯コンピュータ囲碁大会などでモンテカルロ木探索を用いたプログラムが上位を独占 全て UCT か又は同様に木が成長するモンテカルロ木探索を用いている 19 路盤でも強くなった 当初は 9 路盤はアマ 3 級程度 19 路盤では非常に弱かった 現在では 19 路盤でもアマ有段者並み (CrazyStone は KGS という囲碁サイトで 2 級 = 普通の碁会所なら二段?) 何が改良されたのか説明したい 45
46 MCTS の強化 Mogo Zen の登場 CrazyStone は 19 路盤では弱かった 9 路盤はアマ 3 級程度 19 路盤では非常に弱かった しかし MoGo が登場 (UCT を初めて使用 ) 手生成のパターンを使って強化し 19 路盤でも強くなった Computer Olympiad 電通大で開催された UEC 杯コンピュータ囲碁大会などでモンテカルロ木探索を用いたプログラムが上位を独占 全て UCT か又は同様に木が成長するモンテカルロ木探索を用いている 現在最強は Zen というプログラム 19 路盤でアマ三段以上 ( クセを見抜かれると微妙 ) 9 月 18 日発売予定 商品名 天頂の囲碁 開発者は尾島陽児氏 ( 当初は Yamato という仮名で活動 ) RPG ツクール アスキーエンターテイメントソフトウェアコンテスト 46
47 コンピュータ囲碁の革命 かつ探索の革命 古典的な囲碁プログラム ( 古典 =2005 年以前 ) 19 路盤 2 級から 3 級 9 路盤 2 級から 3 級 MCTS Monte Carlo Tree Search 近代的なプログラム ( 近代的 =2006 年以後 ) 19 路盤 2 段以上 9 路盤アマ高段並 囲碁だけが弱かった チェス 将棋 ポーカーなどはコンピュータが非常に強い 今までのアルゴリズムは 評価関数が無いとお手上げだった 2006 年 5 月に発表された MCTS によって状況が一変 [2006 Rémi Coulom] 9 路盤では既に複数のプログラムがプロに勝利した 19 路盤では 公開対局で 7 子のハンデでプロに勝利している CrazyStone 対青葉かおり MoGo 対周俊勲 47
48 木探索部分の改良 Progressive Widening 囲碁の知識を用い 良さそうな手から順に候補手をソート それを徐々に探索木に加えていく 要するに前向き枝刈り All Moves As First (AMAF) プレイアウト中に打たれた初手のみを用いるのが通常の考え方だが AMAF では 全ての手を初手に打ったとみなす Rapid Action Value Estimation (RAVE) とも呼ぶ 手順を無視して近似する 勝ったプレイアウトで打たれた手は全部良い手 UCT のパラメータの調整 定数の部分を増減させると 性格が変わる UCT よりも最善手を優遇する探索手法 48
49 プレイアウトの改良 初期の CrazyStone のプレイアウトは単純 19 路盤では非常に弱かった パターンを用いてプレイアウトを改良 プレイアウトの回数は数分の 1 になった しかし全体としての棋力は大幅に向上 初期の CrazyStone ( 秒間 4 万プレイアウト程度 ) 強化版 CrazyStone ( 秒間 1 万プレイアウト程度 ) 49
50 強さのためには プレイアウトの強化が大事 必要な性質は? 完全に決定的なプレイアウトは意味がない 完全にランダムなプレイアウトを使うと弱い それらしいプレイアウトを使えば 回数が少なくてもそれなりに強い たとえば fuego ( 囲碁プログラム ) は 100~1000 回程度のプレイアウトでもそれなりに強い それらしいけど ランダムなプレイアウトが必要 あと 速さもそれなりに必要 囲碁だと 秒間 1 万回くらい実行している 50
51 プレイアウトに必要な性質は? 理論的にはまだよく分かっていない ICML2009 に新しい論文あり (International Conference on Machine Learning) 機械学習のトップカンファレンス Monte Carlo Simulation Balancing *Silver and Tesauro 2009] 必ずしも プレイアウト単独で強い必要はない 実際に 強いプログラムの部品をプレイアウトに使ったが 手で作ったパターンの方が強かった [Gelly and Silver 2007, 2008] 棋譜からの学習と手生成のパターンの両方が効果がある やってみたら強かった という側面が強い MCTS の弱点をカバーできることが重要 ありがちな一本道を高い確率で通るのが良い 強さを競わないなら適当でもそれなりに良い 世界信長の野望 AI 選手権 があるならがんばらないと駄目 51
52 MCTS はなぜ囲碁に有効なのか? プレイアウトで普通に終局するゲームだから チェスや将棋では普通に終局を迎えるのは難しい しかし将棋では初段レベルの物が開発された オセロや五目並べは終局に至る 囲碁同様に有効であると思われるが 誰もやってない ( たぶん もう十分強いから ) 囲碁では 最善手と次善手の価値の差が小さい ( ことが多い ) 手順に関係なくある位置を占めておけば有利という点が多い 52
53 モンテカルロ木探索の弱点 確率的探索だから 勝率の高い手を調べる 勝てる手順が一本だけあって 他は全部負け という場合を苦手とする シチョウ 負 負 負 負 負 勝 53
54 モンテカルロ木探索の弱点 細く長い正解手順がある場合 最善手が 1 手だけある という局面が長手順連続すると 確率的に正解にたどり着かない 現在の対処法 プレイアウト中には ありがちな一本道はたどるようにする 囲碁のシチョウ ( アタリを逃げるようにして回避 ) 良くあるナカデ セキ (CrazyStone はパターンで回避 ) ありがちでない一本道 は まだ弱い 囲碁の死活 攻め合いはまだ間違える 他の探索アルゴリズムとの組合せなどが研究されている 54
55 コンピュータ囲碁の現状 モンテカルロ木探索の利点 単純に強い プログラミングの労力が少ない 探索部分とプレイアウトの実装だけ プレイアウトの強化には機械学習も有効 多くの研究者が参入 機械学習のプロなど 並列化の研究も行われている 1000 コア以上のクラスターを使ったプロとの対戦も実現 進歩が非常に速いので 来年のことも分からない 55
56 alpha-beta 探索に MCTS が追いついた例 アマゾン ( 非常にググりにくい ) 乱数を使うと自然な終局になりにくいゲームだが プレイアウトを打ち切って評価関数を呼ぶ手法により強くなった [Lorentz2008] [Kloetzer,Iida,Bouzy2007] Lines of Action モンテカルロ木探索と ab 探索ベースのプログラムが互角くらいという研究 [Winands,Björnsson,Saito2008] 56
57 将棋 (alpha-beta には务る ) プレイアウトで自然に終局しにくいため MCTS に不向きなゲームと思われていたが パターンを学習して初段くらいまで強くなった [ 佐藤, 高橋.2008.] さめがめ問題集を解かせて スコアを競う モンテカルロ木探索ベースのプログラムが記録を更新 [Schadd,Winands,Herik,Cahslot,Uiterwijk2008] 57
58 多人数ゲームでも有効 カタンの開拓者たち ドイツ製の有名なカードゲーム MCTS により強いプログラムが作成された 関係ないがグーグルにはカタン部があるそうである [Szita, Chaslot and Spronck 2008] ハーツ (Windows に付いてくる ) モンテカルロ木探索を用いたプログラムが 既存のプログラム以上の強さを示す研究あり [Sturtevant2008] 58
59 汎用性が高い ( 囲碁以外でも高性能 ) 一人用ゲーム ( パズル ) SameGame( さめがめ ) 二人用ゲーム Amazons Lines of Action Hex ( 将棋 ) 多人数ゲーム ハーツ (Windows に付いてくるヤツです ) カタンの開拓者たち Magic the Gathering General Game Player Competition ( 汎用ゲームプレイヤー大会 ) 大会の場で架空のゲームのルールが提示される その場でプログラムがルールを分析し 直後に対戦する 一人ゲーム 二人ゲーム 多人数ゲームなどごちゃまぜ 総合点が高かったら優勝 CADIA Player (UCT をベース ) が 2 年連続で優勝 [Finnsson,Björnsson2008] ゲーム以外 最適化 プランニング バイオメトリクス 59
60 MCTS を実装するには モンテカルロ木探索 = 木探索 + プレイアウト + 評価基準 戦略を選択肢の連続 つまり 木 で表現し その中を探索する ちょっとそれらしいけど適当なプレイヤーに何万回かプレイさせるとにかく速ければ良い スコアや評価関数など ( 勝敗を使うと勝率最大化 ) 20 級も三百万人集まれば有段者の知恵 ただし うまく集めれば ただし 頭のいい20 級ならば ( ランダム性必須 ) ただし 良い評価基準があれば 60
61 の AI を作れ と言われたら? MCTS の実装 応用について想像 今までのアプローチで普通に作る そのノウハウをプレイアウトと枝刈りに使って MCTS も試す うまくいけばラッキー 木探索は最初の一回の実装は大変 しかしノウハウは各ゲームで共通 プレイアウトは各ゲームの知識を利用する 既存のノウハウがほぼ使える しかしちょっと難しい 決定的なものは駄目だけど 完全なランダムも駄目 評価基準 評価関数をそのまま使っても良い 61
62 木探索部分の実装 UCT とか UCB とかは 理論はともかく結果の式だけ使っても大丈夫 たぶん適当な近似でも十分良い データ構造はツリーで OK (DAG でなくていい ) まじめに探索をすると 合流を考えるからツリーでは無くなる オセロは DAG だし 将棋や囲碁はサイクルもある 合流を無視してツリーにしてもほとんど問題無いことが囲碁では知られている ハッシュテーブルなどは必要ないのでその分簡単 ヒューリスティックな枝刈りが有効 ここは既存のアルゴリズムと変わらない 例えば A* と比べてそれほど実装が難しいとは思わない 公開されているサンプルコードもある Fuego : オープンソース最強の囲碁プログラム ちょっと難しい 彩 : MCTS のコア部分だけ (cf. YSS と彩のページ ) 62
63 プレイアウトの実装 プレイアウトは 決定的でなく 完全なランダムでもなく しかも速い必要がある でも 実は適当でもそれなりにうまくいく 強さを競うのならば やっぱり大変 世界いたスト AI 選手権 とかがあれば大変 プレイアウトで自然に終局しないゲームも何とかなる アマゾンではプレイアウトを途中で打ち切って評価関数と組み合わせる手法が提案されている ab 探索 + 評価関数よりも強かった 評価関数の不具合を MCTS がカバーしてくれる 将棋でもそれなりの強さのものはできている 評価関数や詰探索と組み合わせた例 [ 橋本, 橋本, 長嶋 2006] うまくプレイアウトを作ったらちゃんと終局した [ 佐藤, 高橋 2008] 63
64 MCTS によるゲーム AI の実例 ( 論文 ) カタンの開拓者たち [Szita, Chaslot and Spronck 2008] (Chaslot は MoGo プロジェクトにも参加 ) 木探索部分はたぶん普通 プレイアウトは開拓者を置く確率を高めるなどの工夫あり 他のプログラム (JSettlers) と対戦 (1 手当たり )1000 プレイアウトで互角 プレイアウトで大きく勝ち越し Magic the Gathering [Ward and Cowling 2009] Magic the Gathering の一部について UCB を適用 既存のプログラムをそのままプレイアウトに利用 少ない回数のプレイアウトでも元より有意に強くなることを示した この論文では一段読みまで 今後はもっと実例が増えると思われる 64
65 MCTS の長所と短所 強さが思考時間次第 PS3 や Core2Quad に向いているが DS は無理ではないか いつ止めてもその時点で最善の結果を返す (anytime 性がある ) ( ある意味で ) 強い しかし制御が難しい MCTS に限らず 探索を使った AI に共通の性質 細く長い一本道の手順は弱い しかしある意味で 自然な弱さが生まれる ( うっかりミスをする ) 勝率最大化だと 負かされると非常につまらない 強さを犠牲にすれば つまらなさを解消可能と思われる 勝つときは面白い じり貧を嫌うので 負ける前に勝負に出てくるプログラムになる 汎用性が高い 戦略が木構造で現せるなら使える 65
66 Civilization 4 で MCTS という妄想 ご存じとは思いますが 中毒性の高いゲーム ターン性戦略シミュレーションの最高傑作 僕の主観です 文明を一番繁栄させると勝利 注 : 僕は Civilization 4 は嫌いです その証拠に もう 7 回ほどアンインストールしてます 66
67 Civ4 で妄想 長所 : ある程度強くなる このように戦略を木で表現することを考える プランニング +MCTS モンテカルロ木探索による AI の場合 戦争した方が勝率が高い ( しないとほぼ負け ) だから戦争する 最後の勝負を仕掛けてくる 対人戦の練習によさそう でも面白いかどうかは? 上級者向け? 戦争する ライフル兵 騎兵隊 少しは勝てる 現在 戦争しない ほぼ負ける 67
68 Civ4 で妄想 短所 : 思い通りに動かない 戦争を禁じ手にして平和主義者にしたつもりの AI 戦争しない範囲でできるだけのことをする 平和主義者のはずが悪の組織の黒幕に! つまり 頭が良いので言うことを聞かせにくい 狙い通りの挙動をさせるのは難しいかも? 戦争する 現在 戦争しない 住民毒殺 建造物爆破 他国を扇動して戦争させる 68
69 最後に MCTS は 理論的には奥が深いが実装は簡単 手強い AI を作れる 既存のアプローチとは違った個性を持った AI を作れる リアルタイムゲームに全く使えないということは無いように思います しかし 戦略を木構造で表せない物には使えない 今までとは個性の違う AI が おもしろいゲームにつながったらうれしく思います ゲーム AI 開発の手助けになれば嬉しいです 個人的には Civilization 4 の AI が強くなったら嬉しいです 69
70 [Auer,Cesa-Bianchi,Fischer2002] P. Auer, N. Cesa-Bianchi and P. Fischer, Finite-time analysis of the multi-armed bandit problem, Machine Learning, vol. 47, pp , [Coulom2006] R. Coulom, Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search Export, 5th International Conference on Computer and Games (CG2006), pp , [Coulom2007] R. Coulom, Computing Elo Ratings of Move Patterns in the Game of Go, Computer Games Workshop, [Gelly,Wang,Munos,Teytaud2006] S. Gelly, Y. Wang, R. Munos and O. Teytaud, Modification of UCT with patterns in Monte-Carlo Go, Technical Report No.6062, INRIA, [Kocsis,Szepesvári2006] L. Kocsis and C. Szepesvári, Bandit Based Monte-Carlo Planning, LNCS vol.4212 (ECML 2006), pp , [Lai,Robbins1985] T. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, vol. 6, pp. 4-22, [Yoshimoto,Yoshizoe,Kaneko,Kishimoto,Taura2006] H. Yoshimoto, K. Yoshizoe, T. Kaneko, A. Kishimoto and K. Taura, Monte Carlo Go Has a Way to Go, AAAI-06, pp , [ 小泉, 石井, 美添, 三好, 菅原, 稲葉, 平木 2009] 小泉賢一, 石井康雄, 美添一樹, 三好健文, 菅原豊, 稲葉真理, 平木敬, FPGA 基板を用いたモンテカルロ碁の高速化, 信学技報, vol. 109, no. 168, CPSY , pp , 2009 年. 70
71 [Sturtevant2008] N. R. Sturtevant, An Analysis of UCT in Multi-player Games, Computers and Games (CG2008), pp.37-49, [Schadd,Winands,Herik,Cahslot,Uiterwijk2008] M. P. D. Schadd, M. H. M. Winands, H. Jaap van den Herik, G. M. J. -B. Chaslot and J. W. H. M. Uiterwijk, Single- Player Monte-Carlo Tree Search, Computers and Games (CG2008), pp.1-12, [Lorentz2008] R. J. Lorentz, Amazons Discover Monte-Carlo, Computers and Games (CG2008), pp.13-24, [Kloetzer,Iida,Bouzy2007] J. Kloetzer, H. Iida, and B. Bouzy, The Monte-Carlo Approach in Amazons, In Proc. Computer Games Workshop, [Winands,Björnsson,Saito2008] M. H. M. Winands, Y. Björnsson and J.-T. Saito, Monte-Carlo Tree Search Solver, Computers and Games (CG2008), pp.25-26, [ 橋本, 橋本, 長嶋 2006] 橋本隼一, 橋本剛, 長嶋淳, コンピュータ将棋におけるモンテカルロ法の可能性, In Proc. 11th Game Programming Workshop, 2006 [ 佐藤, 高橋 2008] 佐藤佳州, 高橋大介, モンテカルロ木探索によるコンピュータ将棋, In Proc. 13th Game Programming Workshop, [Finnsson,Björnsson2008] H. Finnsson and Y. Björnsson, Simulation-based Approach to General Game Playing, In 23rd AAAI Conference on Artificial Intelligence, pp ,
72 [Gelly and Silver 2007] S. Gelly and D. Silver. Combining Online and Offline Knowledge in UCT, ICML 2007, 2007 [Szita, Chaslot, Spronck 2009] S. Szita, G. Chaslot, and P. Spronck. Monte-Carlo Tree Search in Settlers of Catan. 12th Advances in Computer Games (ACG2009), [Ward Cowling 2009] C. D. Ward and P. I. Cowling. Monte Carlo Search Applied to Card Selection in Magic: The Gathering, IEEE Conference on Computational Intelligence in Games (CIG 2009), [Silver and Tesauro 2009] D. Silver and G. Tesauro. Monte-Carlo Simulation Balancing, ICML 2009, [Nakhost an Mueller 2009] H. Nakhost and M. Müller. Monte-Carlo exploration for deterministic planning, IJCAI 2009, [Tesauro and Galperin 1996] G. Tesauro and G. Galperin. On-line policy improvement using Monte-Carlo search, Advances in Neural Information Processing 9 (NIPS), pp , [Sheppard2002] B. Sheppard. World-championship-caliber Scrabble Artificial Intelligence vol. 134, pp , [Billings, Castillo, Schaeffer, Szafron 1999] D. Billings, L. P. Castillo, J. Schaeffer and D. Szafron. Using Probabilistic Knowledge and Simulation to Play Poker, AAAI-99, pp ,
73 MCTS の残る課題 Simulation (Playout) の性質 合流への対処 並列化 乱数の初期値に鋭敏 まだ分からないことだらけ 73
74 強さのためには プレイアウトの強化が大事 必要な性質は? 完全に決定的なプレイアウトは意味がない 完全にランダムなプレイアウトを使うと弱い それらしいプレイアウトを使えば 回数が少なくてもそれなりに強い たとえば強い囲碁プログラムは 100~1000 回程度のプレイアウトでもそれなりに強い それらしいけど ランダムなプレイアウトが必要 あと 速さもそれなりに必要 囲碁だと 秒間 1 万回くらい実行している それらしい って何? 74
75 プレイアウトに必要な性質は? 理論的にはまだよく分かっていない ICML2009 に新しい論文あり [Silver and Tesauro 2009] Monte Carlo Simulation Balancing 必ずしも プレイアウト単独で強い必要はない 実際に 強いプログラムの部品をプレイアウトに使ったが 手で作ったパターンの方が強かった ( 囲碁の例 ) RLGo と MoGo の組合せの研究 [Gelly and Silver 2007, 2008] 棋譜からの学習と手生成のパターン 両方が効果がある やってみたら強かった という側面が強い MCTS の弱点をカバーできることが重要 ありがちな一本道を高い確率で通るのが良い? 75
76 モンテカルロ木探索の弱点 確率的探索だから 勝率の高い手を調べる 勝てる手順が一本だけあって 他は全部負け という場合を苦手とする シチョウ 負 負 負 負 負 勝 76
77 探索を playout で補う必要 細く長い正解手順がある場合 最善手が 1 手だけある という局面が長手順連続すると 確率的に正解にたどり着かない 現在の囲碁での対処法 プレイアウト中に ありがちな一本道をたどるようにする 囲碁のシチョウ ( アタリを逃げるようにして回避 ) 良くあるナカデ セキ (CrazyStone はパターンで回避 ) ありがちでない一本道 は まだ弱い 囲碁の死活 攻め合いはまだ間違える 他の探索アルゴリズムとの組合せなどが研究されている 弱点を補うことが重要 必ずしも playout 単独で強い必要は無い 必ずしも playout と棋譜との一致率が高い必要もない (?) 77
78 合流時の UCB 値計算? 勝 回数 合流がある場合の計算は自明でない 理論を示した論文あり [CBK2008] まだ決定版かどうか分からない 難しいので (?) トップレベルの囲碁プログラムでも合流を無視する派が多い hash table 派 (CrazyStone 等 ) vs tree 派 (MoGo 等 ) treeは無駄なはずだが 実際は十分強い treeなら実装が簡単 特に並列化も簡単 つまり よほど強さを目指すので無い限り ツリーで十分 合流は無視してもたぶん問題無い 78
79 並列化について どのような並列化手法が良いのかまだ試行錯誤中 ルート並列化という非常に単純な手法がかなり有効 乱数のシードを変えて並列に探索を行い 最後に合計する 特にクラスタではルート並列化がそれなりに良い MoGo, Fuego など 理由は不明だが 乱数の初期値に敏感な性質のせいか? 共有メモリマシンでは virtual loss という手法がある 並列実行中の playout は全部負けると仮定する 多数のコインを同時に投入するケースの multi armed bandit との関連 FPGA による試みもある [ 小泉 石井 美添 三好 菅原 稲葉 平木 2009] GPGPU はまだ論文無し 今自分でやってます しかし AI が複数存在するなら それぞれに 1 CPU 割り当てれば十分 79
80 初期の乱数に鋭敏 初期の乱数への敏感さ 初期の乱数に長期間影響されるらしい 対称性を考慮すると同じ価値のはずの手が 大きく異なる評価をされることが多い root 並列化が有効な理由の一つではないか First Move Urgency が有効であることと関係するか 勝てる手がある場合はその 1 手に集中して探索する手法 これはそもそも解決する必要がある問題ではなく そういう性質のあるアルゴリズムだということ 最初に運良く高い評価をされた手が 長いこと優遇される 80
81 探索時間 探索木のサイズ 強さ 考慮時間と強さ 囲碁では 4 倍の考慮時間で一段ちょっと強くなる 16 倍なら二段ちょっと 64 倍で三段ちょっと 逆に言えば 64 倍速くしても 三段強しか変わらない 競争相手がいなければ そんなにがんばらなくていい 探索木の目安 囲碁 9 路盤では 初手の分岐数が 81 でプレイアウトの手数は 100 程度 この探索木はかなり大きい ランダムに近いプレイアウトで 10 級程度 囲碁 19 路盤は 初手の分岐数は 361 で プレイアウトは 400 手程度 ランダムに近いプレイアウトだと非常に弱い このサイズだと プレイアウトをかなり工夫しないと駄目 ゲームの場合も 探索木のサイズに注意 分岐が多くて手数が長ければ プレイアウトを工夫する必要がある 途中で打ち切って評価関数を呼ぶ あるいは 本当にがんばる ( 囲碁の場合のように ) 時間の制約の許す範囲で 木が大きい方が良い ( 強い ) ( ここは職人技 ) ゲームによって許される考慮時間は違うと思われるので そこは調整 81
82
コンピュータ 囲 碁 に 起 きた 革 命 2008 年 3 月 末 パリ 囲 碁 トーナメントのエキシビショ ンでプロ 対 コンピュータの 対 戦 が 実 現 (http://paris2008.jeudego.org/) プロ:タラヌ カタリン 五 段 ( 日 本 棋 院 中 部 総 本 部 所
コンピュータ 囲 碁 における モンテカルロ 法 ~ 理 論 編 ~ 美 添 一 樹 コンピュータ 囲 碁 に 起 きた 革 命 2008 年 3 月 末 パリ 囲 碁 トーナメントのエキシビショ ンでプロ 対 コンピュータの 対 戦 が 実 現 (http://paris2008.jeudego.org/) プロ:タラヌ カタリン 五 段 ( 日 本 棋 院 中 部 総 本 部 所 属 ) コンピュータ:MoGo
p-9-10.eps
Root 08M37189 21 22 1 29 Root Tree Fuego Root Tree Root Root 2 Fuego Root CPU Root 64CPU Chaslot Root Root 1 1 7 1.1................................ 7 1.2................................. 8 1.3..................................
1 自 己紹介と概要 最近の研究テーマ ( あるいは世を忍ぶ仮の姿 ) 探索索アルゴリズムの 大規模並列列化 本当のテーマ コンピュータでプロ囲碁棋 士に勝つ 今 日はモンテカルロ 木探索索の 成 立立の経緯 最初しばらく囲碁の話 理理論論と実践 どちらも深くは 立立ち 入らない モンテカルロ 木探
モンテカルロ 木探索索 Monte-Carlo Tree Search の理理論論と実践 美添 一樹 Kazuki Yoshizoe JST ERATO 湊離離散構造処理理系プロジェクト / 東 工 大 IBIS2014 企画セッション離離散アルゴリズムの機械学習応 用 1 自 己紹介と概要 最近の研究テーマ ( あるいは世を忍ぶ仮の姿 ) 探索索アルゴリズムの 大規模並列列化 本当のテーマ コンピュータでプロ囲碁棋
2015 3
JAIST Reposi https://dspace.j Title ターン制ストラテジーゲームにおける候補手の抽象化 によるゲーム木探索の効率化 Author(s) 村山, 公志朗 Citation Issue Date 2015-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/12652
The 19th Game Programming Workshop 2014 SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algori
SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algorithm in Go and Gobang Masahiro Honjo 1,a) Yoshimasa Tsuruoka 2 Abstract: Today, UCT is the most
PowerPoint プレゼンテーション
モンテカルロ木探索 並列化 囲碁 マリオ AI 美添一樹 ETATO 研究員 湊離散構造処理系プロジェクト 2013 年度秋のワークショップ 2013 年 11 月 26 日 並列モンテカルロ木探索の意義 コンピュータ囲碁で人間を超える 情報科学の有効性を示す 大規模並列探索ライブラリ 近い将来 全てのアルゴリズムは大規模並列化が必要 並列探索は実装が 非常に 大変なのでライブラリとして提供できると良い
dlshogiアピール文章
第 28 回世界コンピュータ将棋選手権 dlshogi アピール文章 山岡忠夫 2018 年 5 月 1 日更新 下線部分は 第 5 回将棋電王トーナメントからの差分を示す 1 特徴 ディープラーニングを使用 指し手を予測する Policy Network 局面の勝率を予測する Value Network 入力特徴にドメイン知識を活用 モンテカルロ木探索 並列化 自己対局による強化学習 既存将棋プログラムの自己対局データを使った事前学習
[1] AI [2] Pac-Man Ms. Pac-Man Ms. Pac-Man Pac-Man Ms. Pac-Man IEEE AI Ms. Pac-Man AI [3] AI 2011 UCT[4] [5] 58,990 Ms. Pac-Man AI Ms. Pac-Man 921,360
![[1] AI [2] Pac-Man Ms. Pac-Man Ms. Pac-Man Pac-Man Ms. Pac-Man IEEE AI Ms. Pac-Man AI [3] AI 2011 UCT[4] [5] 58,990 Ms. Pac-Man AI Ms. Pac-Man 921,360](/thumbs/93/114217704.jpg "[1] AI [2] Pac-Man Ms. Pac-Man Ms. Pac-Man Pac-Man Ms. Pac-Man IEEE AI Ms. Pac-Man AI [3] AI 2011 UCT[4] [5] 58,990 Ms. Pac-Man AI Ms. Pac-Man 921,360")
TD(λ) Ms. Pac-Man AI 1,a) 2 3 3 Ms. Pac-Man AI Ms. Pac-Man UCT (Upper Confidence Bounds applied to Trees) TD(λ) UCT UCT Progressive bias Progressive bias UCT UCT Ms. Pac-Man UCT Progressive bias TD(λ)
Vol. 52 No (Dec. 2011) Ms. Pac-Man IEEE CIG Ms. Pac-Man Ms. Pac-Man AI AI Ms. Pac-Man Ms. Pac-Man Competition Ms. Pac-Man Monte
Vol. 52 No. 12 3817 3827 (Dec. 2011) Ms. Pac-Man 1 2 2007 IEEE CIG Ms. Pac-Man Ms. Pac-Man AI AI Ms. Pac-Man Ms. Pac-Man Competition Ms. Pac-Man Monte-Carlo Tree Search in Ms. Pac-Man Nozomu Ikehata 1
Research on decision making in multi-player games with imperfect information
Research on decision making in multi-player games with imperfect information 37-086521 22 2 9 UCT UCT 46 % 60000 9 % 1 1 1.1........................................ 1 1.2.....................................
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 例題 二人で交代に, から順に までの数を言う.
Logistello 1) playout playout 1 5) SIMD Bitboard playout playout Bitboard Bitboard 8 8 = black white 2 2 Bitboard 2 1 6) position rev i
SIMD 1 1 1 playout playout Cell B. E. SIMD SIMD playout playout Implementation of an Othello Program Based on Monte-Carlo Tree Search by Using a Multi-Core Processor and SIMD Instructions YUJI KUBOTA,
DR実施日のWP
囲碁 AI AlphaGo はなぜ強いのか? ~ ディープラーニング モンテカルロ木探索 強化学習 ~ 大槻知史 目次 背景 囲碁AIにおけるディープラーニング 囲碁AIにおける探索 囲碁AIにおける強化学習(など) まとめ 2 AlphaGoに関する最近のニュース AlphaGo以前 日本の囲碁プラグラムZen等はプロ棋士に4子局で勝利(アマチュア高段者レベル) 人間チャンピオンレベルになるのは10年後位と思われていた
Taro-プレミアム第66号PDF.jtd
ソフトテニス誰でも 10 倍上達しますプレミアム PDF 版 no66 攻め 守りの新機軸 著作制作 :OYA 転載転用禁止です 2013/2/25 編 1, 攻め 守り後衛と対峙する前衛にとっては 相手後衛が攻撃してくるのか 守ってくるのかは とても重要な問題です 相手後衛が攻めてくるのであれば ポジション的に守らなければならないし 相手が守りでくるならば スマッシュを待ったり 飛び出したりする準備をしなければいけません
しています. これには探索木のすべてのノードを探索する必要がありますが,αβカットなどの枝刈りの処理により探索にかかる計算時間を短縮しています. これに対して, 探索するノードを限定したり, 優先順位をつけて選択的に探索する 選択探索 という探索方式があります. 本チームはノードの選択方式としてノー
芝浦将棋 Softmax のチーム紹介 2017 年 3 月 14 日芝浦工業大学情報工学科五十嵐治一, 原悠一 1. はじめに本稿は, 第 27 回世界コンピュータ将棋選手権 (2017 年 5 月 3 日 ~5 日開催 ) に出場予定の 芝浦将棋 Softmax ( シバウラショウギソフトマックス ) のアピール文書です. 本チームは 芝浦将棋 Jr. から分離した初参加のチームです. 探索手法が従来の
The 18th Game Programming Workshop ,a) 1,b) 1,c) 2,d) 1,e) 1,f) Adapting One-Player Mahjong Players to Four-Player Mahjong
1 4 1,a) 1,b) 1,c) 2,d) 1,e) 1,f) 4 1 1 4 1 4 4 1 4 Adapting One-Player Mahjong Players to Four-Player Mahjong by Recognizing Folding Situations Naoki Mizukami 1,a) Ryotaro Nakahari 1,b) Akira Ura 1,c)
2. AI 囲碁の準備 本章では AI 囲碁を使うための準備について解説します 2.1 AI 囲碁に入っているディスクについて AI 囲碁の商品には以下のディスクが入っています AI 囲碁 Version 20 CD-ROM このディスクにはインストーラや AI 囲碁のプログラムといった AI 囲碁を動作 させるのに必要な各種ファイルが入っています 2.2 AI 囲碁のインストールとアンインストール
25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games
25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games 1165065 2014 2 28 ,,, i Abstract Study on Effectiveness of Monte Calro Tree Search for Single-Player Games Norimasa NASU Currently,
AI
JAIST Reposi https://dspace.j Title プレイヤの意図や価値観を学習し行動選択するチーム プレイ AI の構成 Author(s) 吉谷, 慧 Citation Issue Date 2013-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/11300
Microsoft PowerPoint _人工知能とロボット2_rev.pptx
名古屋市立大学システム自然科学研究科渡邊裕司 日付 通算回 講義内容 0/7 第 4 回 人工知能の概要 基礎的研究 0/24 第 5 回 ゲーム情報学 生物に学んだ機械学習 0/3 第 6 回 データマイニング スマートフォンのセキュリティ /7 第 7 回 サイボーグ ロボット 203/0/24 人工知能とロボット 2 2 ゲーム情報学 生物に学んだ機械学習 ニューラルネットワーク 研究事例 :
Microsoft PowerPoint - 計算機科学入門2014.pptx
第三回計算機科学入門 ( アプリケーション ) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ 小テストの予定 来週 (/) は小テスト内容 :. 制約充足問題を解く. 問題の表現方法は与えられており, 解法はバックトラック.. ある問題を制約充足問題として定式化し,
Microsoft PowerPoint - ゲーム理論2016.pptx
125 126 ゲーム理論 ( 第 6 回ゲーム木探索 II) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ 先読みの効果 基本的には, 深く読めば読むほど強い 終盤の方が静的評価関数の値が信用できる そうでない場合は, 先読みの効果は必ずしも自明ではない
情報 システム工学概論 コンピュータゲームプレイヤ 鶴岡慶雅 工学部電子情報工学科 情報理工学系研究科電子情報学専攻
情報 システム工学概論 2018-1-15 コンピュータゲームプレイヤ 鶴岡慶雅 工学部電子情報工学科 情報理工学系研究科電子情報学専攻 DEEP Q-NETWORK (DQN) Deep Q-Network (Mnih et al., 2015) Atari 2600 Games ブロック崩し スペースインベーダー ピンポン etc. 同一のプログラムですべてのゲームを学習 CNN+ 強化学習 (Q-Learning)
世界コンピュータ将棋選手権 [30] CSA CSA 電王戦 [31] Computer Olympiad [32] ICGA コンピュータ将棋対局場 [33],floodgate [34] 24 floodgate floodgate
![世界コンピュータ将棋選手権 [30] CSA CSA 電王戦 [31] Computer Olympiad [32] ICGA コンピュータ将棋対局場 [33],floodgate [34] 24 floodgate floodgate](/thumbs/91/106682622.jpg "世界コンピュータ将棋選手権 [30] CSA CSA 電王戦 [31] Computer Olympiad [32] ICGA コンピュータ将棋対局場 [33],floodgate [34] 24 floodgate floodgate")
254 30 2 2015 3 ゲームプログラミング ( 将棋を中心に ) 1 竹内聖悟 ( 科学技術振興機構 ERATO 湊離散構造処理系プロジェクト ) 1 1999 [1] 2 2012 松原仁 : ゲーム情報学 :1. ゲーム情報学の現在 ゲームの研究は日本で疎外されなくなったのか [2], 情報処理,Vol. 53, No. 2, pp. 102-106(2012) 小谷善行 : ゲーム情報学
Microsoft Word - 11 進化ゲーム
. 進化ゲーム 0. ゲームの理論の分類 これまで授業で取り扱ってきたゲームは 協 ゲームと呼ばれるものである これはプレイヤー同士が独立して意思決定する状況を表すゲームであり ふつう ゲーム理論 といえば 非協力ゲームを表す これに対して プレイヤー同士が協力するという前提のもとに提携形成のパタンや利得配分の在り方を分析するゲームを協 ゲームという もっとも 社会現象への応用可能性も大きいはずなのに
Information Theory
前回の復習 情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 クラフトの不等式 2 l 1 + + 2 l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1 前回の練習問題 : ハフマン符号 符号木を再帰的に構成し, 符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1
Information Theory
前回の復習 講義の概要 chapter 1: 情報を測る... エントロピーの定義 確率変数 X の ( 一次 ) エントロピー M H 1 (X) = p i log 2 p i (bit) i=1 M は実現値の個数,p i は i 番目の実現値が取られる確率 実現値 確率 表 裏 0.5 0.5 H 1 X = 0.5 log 2 0.5 0.5log 2 0.5 = 1bit 1 練習問題の解答
Microsoft PowerPoint - DA1_2018.pptx
木の利用例 ( ゲーム木 ) データ構造とアルゴリズム ⅠB 第 回 自分の手番 / 相手の手番で分岐していく 77 例題 二人で交代に,1 から順に までの数を言う. 言う数の個数は,1 個, 個,3 個のいずれか好きなのを選んでよい 最後に を言った方が負け 必勝法 を言って, 相手に順番を回せば絶対勝ち 一方,0 を言って, 相手に順番を回せば, 相手が何個を選んでも, 次に を言える ---
Microsoft PowerPoint - vc2013.s.takeuchi.pptx
コンピュータ将棋の技術と GPS 将棋について JST ERATO 湊離散構造処理系プロジェクト 竹内聖悟 概要 GPS 将棋の紹介 コンピュータ将棋で使われる技術 形勢判断と先読み GPS 将棋の技術 今後の将棋 AI と研究 コンピュータ将棋と可視化 近年のコンピュータ将棋 2007 年 : 渡辺明竜王 -Bonanza 渡辺竜王の勝利 2010 年 : あから 2010- 清水市代女流王将 あからの勝利
DL_UCT
Deep Learning for Real- Time Atari Game Play Using Offline Monte- Carlo Tree Search Planning Guo, X., Singh, S., Lee, H., Lewis, R. L., & Wang, X. (2014). InAdvances in Neural Information Processing Systems
Microsoft PowerPoint - mp11-06.pptx
数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般
レーティングと棋譜分析
将棋名人のレーティングと棋譜分析 山下宏 2014 年 11 月 7 日 GPW 箱根 大山 15 世名人と羽生名人 全盛期に戦えばどちらが強い? 大山康晴 15 世名人 タイトル獲得 80 期 昭和の覇者 羽生善治名人 1996 年に7 冠達成 平成の覇者 歴代名人の強さを調べる 対局の結果から 対局者の棋力を点数で表す 勝てば点数プラス 負ければマイナス いわゆるEloレーティング 棋譜の内容から
ボルツマンマシンの高速化
1. はじめに ボルツマン学習と平均場近似 山梨大学工学部宗久研究室 G04MK016 鳥居圭太 ボルツマンマシンは学習可能な相互結合型ネットワー クの代表的なものである. ボルツマンマシンには, 学習のための統計平均を取る必要があり, 結果を求めるまでに長い時間がかかってしまうという欠点がある. そこで, 学習の高速化のために, 統計を取る2つのステップについて, 以下のことを行う. まず1つ目のステップでは,
PowerPoint Presentation
ゲーム木の探索について ミニマックス法のアルゴリズム アルファベータ法のアルゴリズ 三目並べゲームの例 1 ゲーム TicTacToe Othello Chess Let us find game and play! 三目並べ http://perfecttictactoe.herokuapp.com/ オセロ http://atohi.com/osg/default.aspx 将棋 2 ゲーム木の探索問題
戦略的行動と経済取引 （ゲーム理論入門）
展開形表現 戦略的行動と経済取引 ( ゲーム理論入門 ) 3. 展開形ゲームとサブゲーム完全均衡 戦略形ゲーム : プレイヤー 戦略 利得 から構成されるゲーム 展開形ゲーム (extensive form game): 各プレイヤーの意思決定を時間の流れとともに ゲームの木 を用いて表現 1 2 展開形ゲームの構成要素 プレイヤー (player) の集合 ゲームの木 (tree) 枝 ( 選択肢
Microsoft PowerPoint - DA2_2018.pptx
1//1 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I). 単一始点最短路問題 第 章の構成 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ 特定の開始頂点 から任意の頂点
UCT探索を用いた大貧民クライアント
UCT.. ( ) UCT 1 / 34 1 2 UEC 2012 3 4 UCT UCB1 UCB1-Tuned 5 ( ) UCT 2 / 34 1 http://uguisu.skr.jp/othello/ http://matome.naver.jp/odai/2128989764455845801 ( ) UCT 3 / 34 1 : (1997) : (1997) : (2010) :
…好きです 解説
好きです 解説 いろはちゃんコンテスト DAY4 ~BOSSRUSH~ この問題は はじめに はじめに この問題は BossRush のボス はじめに この問題の作問者は E869120 (79%) + square (21%) です 私はひらきちにこの問題を出したら 1 週間考えて解法が分からなかったぽ かったので BossRush の最後に置かれました でも意外と解いている人は多そうなのですね
Microsoft PowerPoint - ca ppt [互換モード]
![Microsoft PowerPoint - ca ppt [互換モード]](/thumbs/91/107496045.jpg "Microsoft PowerPoint - ca ppt [互換モード]")
大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習
論文の内容の要旨
論文の内容の要旨 論文題目 Superposition of macroscopically distinct states in quantum many-body systems ( 量子多体系におけるマクロに異なる状態の重ね合わせ ) 氏名森前智行 本論文では 量子多体系におけるマクロに異なる状態の重ねあわせを研究する 状態の重ね合わせ というのは古典論には無い量子論独特の概念であり 数学的には
特集01-2c.indd
特集 ゲーム情 基応専般 ゲーム情の現在 ゲームの研究は日本で疎外されなくなったのか 松原仁 ( 公立はこだて未来大 ) ゲーム情 ゲーム情という名称ができたのはそんなに古いことではない. 本会でゲームに関する研究会を立ち上げることを計画していた 1998 年頃に研究会の名称を何にすればよいか関係者で検討をしていた. なかなかよい案が出てこなかったが, 筆者が橋田浩一氏 ( 当時電子技術総合研究所現産業技術総合研究所
世界コンピュータ将棋選手権大会ルール補足 (2019 年 2 月 15 日版 赤字は 2 月 8 日版からの追加 ) Q 主要な開発者 の定義について 主要な開発者 とは何ですか? 主要な貢献 とは何ですか? 主要な開発者 になるとどうなりますか? A 開発者のうち 参加者が参加プログラムの開発部の
世界コンピュータ将棋選手権大会ルール補足 (2019 年 2 月 15 日版 赤字は 2 月 8 日版からの追加 ) Q 主要な開発者 の定義について 主要な開発者 とは何ですか? 主要な貢献 とは何ですか? 主要な開発者 になるとどうなりますか? A 開発者のうち 参加者が参加プログラムの開発部の作成において主要な貢献をしたとみなした一名以上の人 ただし 10% 以上貢献した人 ( 例えば アルゴリズム的に
将棋吊人のレーティングと棋譜分析
歴代名人の強さ 山下宏 2017 年 10 月 13 日 札幌 NoMaps 大山 15 世名人と羽生棋聖 全盛期に戦えばどちらが強い? 大山 15 世名人昭和の大名人 羽生棋聖将棋史上最強と言われる (19 世名人 ) 時代が違う二人を直接戦わせることは不可能 しかし二人が指した棋譜は残されている 棋譜から強さを推定 将棋ソフトを使って解析 初心者からアマ高段者まで1800 局を調べた ソフトが悪手と指摘した手と棋力に関連性
内容梗概 本論文の目的は モンテカルロシミュレーションを取り入れた囲碁プログラムの作成である 今回は去年同研究室の上野謙二郎氏が作成した囲碁プログラムをベースに その棋力を上げるために候補手の思考部分に改良を加えた 具体的には 候補手のパターン化とモンテカルロ法の並列化である 候補手のパターン化はあ
卒業論文 頻出パターンを用いたコンピュータ囲碁候補手の 選定と並列化の検討 氏名 : 中川聖也学籍番号 :2260070068-9 指導教員 : 山崎勝弘教授提出日 :2011 年 2 月 18 日 立命館大学理工学部電子情報デザイン学科 内容梗概 本論文の目的は モンテカルロシミュレーションを取り入れた囲碁プログラムの作成である 今回は去年同研究室の上野謙二郎氏が作成した囲碁プログラムをベースに
AI 三目並べ
ame Algorithms AI programming 三目並べ 2011 11 17 ゲーム木 お互いがどのような手を打ったかによって次にどのような局面になるかを場合分けしていくゲーム展開を木で表すことができる 相手の手 ゲームを思考することは このゲーム木を先読みしていく必要がある ミニマックス法 考え方 では局面が最良になる手を選びたい 相手は ( 自分にとって ) 局面が最悪となる手を選ぶだろう
ï¼™æ¬¡å¼‘ã†®åł€æŁ°å‹ƒè§£
== 次式の因数分解 == [1]~[IV] の公式は中学校の復習となっているが, 高校では 置き換え による因数分解などやや高度なものも含まれている 共通因数でくくる [I] ma+mb=m(a+b) [I] の例 (1) () 5y+0y =5( y+4y )=5y(+4y) 注意途中経過として (1) のような式を書くのは自由である ( 解答者が思いついた順序によっては y(5+0y) など他の形となる場合もあり得る
The 21st Game Programming Workshop 2016 ポケモン対戦に対する UCT アルゴリズムの有効性の調査 猪原弘之 1,a) 小山聡 1 栗原正仁 1 概要 : ゲーム AI はコンピュータ黎明期から盛んに研究されており, コンピュータが扱いやすいものから順に研究して
ポケモン対戦に対する UCT アルゴリズムの有効性の調査 猪原弘之 1,a) 小山聡 1 栗原正仁 1 概要 : ゲーム AI はコンピュータ黎明期から盛んに研究されており, コンピュータが扱いやすいものから順に研究していく意味で特に完全情報ゲームの研究が中心だった. しかし, チェス, 将棋, 囲碁などの主要な完全情報ゲームにおける研究は人間のトッププロよりも高い実力が発揮できるレベルまでに達し,
Microsoft PowerPoint - DA2_2017.pptx
1// 小テスト内容 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I) 1 1 第 章の構成. 単一始点最短路問題 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 1 1 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ
連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 概要 17 2 ゲーム木探索 必勝 必敗 引き分け 盤面の評価値 αβ 法 指し手の順序付け (mo
連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 概要 17 2 ゲーム木探索 17 2.1 必勝 必敗 引き分け 17 2.2 盤面の評価値 18 2.3 αβ 法 19 2.4 指し手の順序付け (move ordering) 20 3 Andersson の詰み探索およびその並列化 21 3.1 Andersson
小次郎講師のトレーダーズバイブル第53回
こういう賭けだ 100万円の元金を元にトランプで勝負をする 勝てば20 増える 負ければ20 減る 公平だろ 公平ですね 100万円が勝てば20万増える 負ければ20万減るという ことですね で 勝つか負けるかは50 公平だと思います 2回目は最初勝った場合は120万を投資する 負けた場合は80万を投資 する つまり増えた額も投資していくわけですね そういうこと 2回目も勝てば20 増え 負ければ20
2 1 2 2 1 i
25 Improvement of Simulation Accuracy in Monte Carlo Daihinmin Players 1165064 2014 2 28 2 1 2 2 1 i 2 2 1 3 15,000 15,000 69% 2 3 3 ii Abstract Improvement of Simulation Accuracy in Monte Carlo Daihinmin
Microsoft PowerPoint SIGAL.ppt
アメリカン アジアンオプションの 価格の近似に対する 計算幾何的アプローチ 渋谷彰信, 塩浦昭義, 徳山豪 ( 東北大学大学院情報科学研究科 ) 発表の概要 アメリカン アジアンオプション金融派生商品の一つ価格付け ( 価格の計算 ) は重要な問題 二項モデルにおける価格付けは計算困難な問題 目的 : 近似精度保証をもつ近似アルゴリズムの提案 アイディア : 区分線形関数を計算幾何手法により近似 問題の説明
JAIST Reposi Title モンテカルロ碁における多様な戦略の演出と形勢の制 御 : 接待碁 AI に向けて Author(s) 池田, 心 ; Viennot, Simon Citation ゲームプログラミングワークショップ 2012 論文集, 201
JAIST Reposi https://dspace.j Title モンテカルロ碁における多様な戦略の演出と形勢の制 御 : 接待碁 AI に向けて Author(s) 池田, 心 ; Viennot, Simon Citation ゲームプログラミングワークショップ 2012 論文集, 2012(6): 47-54 Issue Date 2012-11-09 Type Conference Paper
スライド 1
Keal H. Sahn A R. Crc: A dual teperature sulated annealng approach for solvng blevel prograng probles Coputers and Checal Engneerng Vol. 23 pp. 11-251998. 第 12 回論文ゼミ 2013/07/12( 金 ) #4 M1 今泉孝章 2 段階計画問題とは
Microsoft PowerPoint - 10.pptx
m u. 固有値とその応用 8/7/( 水 ). 固有値とその応用 固有値と固有ベクトル 行列による写像から固有ベクトルへ m m 行列 によって線形写像 f : R R が表せることを見てきた ここでは 次元平面の行列による写像を調べる とし 写像 f : を考える R R まず 単位ベクトルの像 u y y f : R R u u, u この事から 線形写像の性質を用いると 次の格子上の点全ての写像先が求まる
今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順 ) になるよう 並び替えること
C プログラミング演習 1( 再 ) 4 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 ( 前回の課題で取り上げた )data.txt の要素をソートして sorted.txt というファイルに書出す ソート (sort) とは : 数の場合 小さいものから大きなもの ( 昇順 ) もしくは 大きなものから小さなもの ( 降順
ワンダー ライヴズとは? 世界の様々な特徴 能 を持つ生物たちが 自然界での生き残りをかけて戦うカードゲームです
遊べる! 生物のすごい能力大図鑑 ワンダー ライヴズ体験プレイ用スライド ワンダー ライヴズとは? 世界の様々な特徴 能 を持つ生物たちが 自然界での生き残りをかけて戦うカードゲームです ワンダー ライヴズとは? V.S. ワンダー ライヴズは 2 人で対戦するゲームです 今回は 海デッキと陸デッキに分かれて戦います 準備 : カードの重ね順を確認 説明のため カードの重ね順が決まっているため 今回はシャッフルをしないでそのまま遊びましょう
ビッグデータ分析を高速化する 分散処理技術を開発 日本電気株式会社
ビッグデータ分析を高速化する 分散処理技術を開発 日本電気株式会社 概要 NEC は ビッグデータの分析を高速化する分散処理技術を開発しました 本技術により レコメンド 価格予測 需要予測などに必要な機械学習処理を従来の 10 倍以上高速に行い 分析結果の迅速な活用に貢献します ビッグデータの分散処理で一般的なオープンソース Hadoop を利用 これにより レコメンド 価格予測 需要予測などの分析において
Mastering the Game of Go without Human Knowledge ( ) AI 3 1 AI 1 rev.1 (2017/11/26) 1 6 2
6 2 6.1........................................... 3 6.2....................... 5 6.2.1........................... 5 6.2.2........................... 9 6.2.3................. 11 6.3.......................
第1回 羽曳野レイティングシステム大会
レイティング説明 日本卓球レイティング推進協議会 http://www.kcn.res.kutc.kansai-u.ac.jp/~ihaya/tt_rating/ レイティング概要 1. 本大会は日本でレイティングを開始するための試験大会です. 大会の勝敗結果から種々のレイティングの計算方法やレイティングの公開方法などを検討します. ご不便をお掛けしますが, 日本でレイティングを導入するためにご協力下さい.
将棋プログラムの現状と未来
将棋プログラムの現状と未来 鶴岡慶雅 2 1. はじめにコンピュータ将棋の実力はプロ棋士のレベルに近づきつつある その理由の一つは ハードウェアの進歩により探索を高速に実行できるようになったことにあるが ソフトウェアの面での進歩も大きい 本稿では 第 15 回世界コンピュータ将棋選手権で優勝した将棋プログラム 激指 ( げきさし ) の探索手法を中心にして 現在トップレベルにある将棋プログラムの中身
基調講演
8 衰退期になっていくのではないかとも言われ るものかどうか調査にきたのが ワトキンス るくらいであります 調査団 ですが その報告書の中に載ってい 一方 薄型テレビは今 大変な成長期にあ るのが この日本の道路であります 図 1 ると思われます 毎年猛烈な勢いで増えてい そこには有名な言葉がありました 日本の道 る状況であります ですが これもいずれは 路は信じられないくらい悪い 世界の工業国 飽和状態に達します
明治大模擬2
Ⅴ: 分野 6 次の文章を読んで, 下の問いに答えなさい ゲーム (Tic-tac-toe), チェッカー, オセロ, チェス, 将棋, 囲碁などの, 決まった盤面の状態から先手と後手で交互に手を進めていくゲームを 完全情報ゲーム と言う 完全情報ゲームは, 原理的にはすべての手を読み切ることができる たとえば ゲームは, 少し練習すれば誰でも手を読み切るほどの熟練者になれる そして, 熟練者同士がプレイヤーとなって対戦すれば必ず引き分けになり,
スライド 1
知能制御システム学 画像処理の高速化 OpenCV による基礎的な例 東北大学大学院情報科学研究科鏡慎吾 swk(at)ic.is.tohoku.ac.jp 2007.07.03 リアルタイム処理と高速化 リアルタイム = 高速 ではない 目標となる時間制約が定められているのがリアルタイム処理である.34 ms かかった処理が 33 ms に縮んだだけでも, それによって与えられた時間制約が満たされるのであれば,
Kumamoto University Center for Multimedia and Information Technologies Lab. 熊本大学アプリケーション実験 ~ 実環境における無線 LAN 受信電波強度を用いた位置推定手法の検討 ~ InKIAI 宮崎県美郷
熊本大学アプリケーション実験 ~ 実環境における無線 LAN 受信電波強度を用いた位置推定手法の検討 ~ InKIAI プロジェクト @ 宮崎県美郷町 熊本大学副島慶人川村諒 1 実験の目的 従来 信号の受信電波強度 (RSSI:RecevedSgnal StrengthIndcator) により 対象の位置を推定する手法として 無線 LAN の AP(AccessPont) から受信する信号の減衰量をもとに位置を推定する手法が多く検討されている
Autodesk Inventor Skill Builders Autodesk Inventor 2010 構造解析の精度改良 メッシュリファインメントによる収束計算 予想作業時間:15 分 対象のバージョン:Inventor 2010 もしくはそれ以降のバージョン シミュレーションを設定する際
Autodesk Inventor Skill Builders Autodesk Inventor 2010 構造解析の精度改良 メッシュリファインメントによる収束計算 予想作業時間:15 分 対象のバージョン:Inventor 2010 もしくはそれ以降のバージョン シミュレーションを設定する際に 収束判定に関するデフォルトの設定をそのまま使うか 修正をします 応力解析ソルバーでは計算の終了を判断するときにこの設定を使います
Windows10の標準機能だけでデータを完全バックアップする方法 | 【ぱそちき】パソコン初心者に教えたい仕事に役立つPC知識
ぱそちき パソコン初心者に教えたい仕事に役立つ PC 知識 Windows10 の標準機能だけでデータを完全バックアッ プする方法 パソコンが急に動かなくなったり 壊れてしまうとパソコンに保存していたテキストや写真などの データも無くなってしまいます このように思いがけない事故からデータを守るには バックアップを取っておくしかありません Windows10のパソコンを使っているなら データをバックアップするのに特別なソフトは必要ありません
目次 はじめに... 3 基本戦略編... 4 基本戦略 1:1キーワード1サイト戦略... 5 基本戦略 2:1サイト1 商品戦略... 7 基本戦略 3:0.2 秒の法則... 8 基本戦略 4: 画像リンクよりもテキストリンク... 9 基本戦略 5: パラサイトカラーマーケティング... 1
知らないと損する サイト作成 7 つの戦略 1 目次 はじめに... 3 基本戦略編... 4 基本戦略 1:1キーワード1サイト戦略... 5 基本戦略 2:1サイト1 商品戦略... 7 基本戦略 3:0.2 秒の法則... 8 基本戦略 4: 画像リンクよりもテキストリンク... 9 基本戦略 5: パラサイトカラーマーケティング... 10 基本戦略 6:PCサイトとスマホサイトを両方作成する...
Microsoft PowerPoint - mp13-07.pptx
数理計画法 ( 数理最適化 ) 第 7 回 ネットワーク最適化 最大流問題と増加路アルゴリズム 担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ 頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたもの ネットワーク 頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの
情報処理学会研究報告 IPSJ SIG Technical Report Vol.2009-GI-22 No /6/26 ( ) GPCC (Games and Puzzles Competitions on Computers) 200
(007 10 008 10 ) 1 1 GPCC (Games and Puzzles Competitions on Computers) 007 10 7 008 10 008 197 GPCC 8) chair 009 The report of Computer BlokusDuo Championship TSUKIJI Tsuyoshi, 1 OSAKI Yasuhiro, 1 SAKAI
PowerPoint プレゼンテーション
ロボットの計画と制御 マルコフ決定過程 確率ロボティクス 14 章 http://www.probabilistic-robotics.org/ 1 14.1 動機付けロボットの行動選択のための確率的なアルゴリズム 目的 予想される不確かさを最小化したい. ロボットの動作につての不確かさ (MDP で考える ) 決定論的な要素 ロボット工学の理論の多くは, 動作の影響は決定論的であるという仮定のもとに成り立っている.
Microsoft PowerPoint - pr_12_template-bs.pptx
12 回パターン検出と画像特徴 テンプレートマッチング 領域分割 画像特徴 テンプレート マッチング 1 テンプレートマッチング ( 図形 画像などの ) 型照合 Template Matching テンプレートと呼ばれる小さな一部の画像領域と同じパターンが画像全体の中に存在するかどうかを調べる方法 画像内にある対象物体の位置検出 物体数のカウント 物体移動の検出などに使われる テンプレートマッチングの計算
進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2
連立 1 次方程式の数値解法 小規模な連立 1 次方程式の解法 消去法 Gauss 消去法 Gauss-Jordan 法 ( 大規模な連立 1 次方程式の解法 ) ( 反復法 ) (Jacobi 法 ) 講義では扱わない 1 進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2 パターン認識入門 パターン認識 音や画像に中に隠れたパターンを認識する 音素
Microsoft PowerPoint - 05.pptx
アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明
ICDE’15 勉強会 R24-4: R27-3 (R24:Query Processing 3, R27 Indexing)
R24-4: The DBMS - your Big Data Sommelier (R24: Query Processing 3) R27-3: A Comparison of Adaptive Radix Trees and Hash Tables (R27: Indexing) 小山田 (NEC) ICDE 15 勉強会 R24-4: The DBMS - your Big Data Sommelier
JVRSJ Vol.18 No.3 September, 2013 173 29 2 1 2 1 NPC 2004 1 RTS Real-time Simulation NPC NPC NPC AI NPC 4 AI 2 AI 2 3 4 図 1 ゲームとユーザエクスペリエンス reality a
28 172 日 本 バーチャルリアリティ 学 会 誌 第 18 巻 3 号 2013 年 9 月 1 [1] 1 [2-5] NPC Non-Player-Character 80 90 NPC 2000 NPC 2 AI AI AI [6-8] RPG AI NPC AI AI RPG AI [5][9][10] 3 AI 2 AI 1 [11] 28 JVRSJ Vol.18 No.3 September,
できない領域であり, 盤上の地を数えやすくし, 途中局面での評価付けを容易にした. 最後に, 絶対石群 絶対死閉領域と本論文で提案する溢れ碁ルールとの関係について述べる. 2.1 絶対石群 1976 年,Benson は Life in the Game of Go 5) の中で, 無条件生きの石の
溢れ碁ルールの提案とそれを用いた囲碁の小路盤探索 松本祐輔 1 小谷善行 2 囲碁のゲーム研究において, 探索空間を狭めた小さいサイズの碁盤での研究が行われている.2003 年には Werf らが絶対石群を用いて 5 路盤を解析し, 中川は絶対石群を拡張した絶対死閉領域を提案した. ところが, それらの概念は終局判定にのみ使用されており, 途中局面では活用されていない. そこで本論文では, 絶対石群と絶対死閉領域のより効率的に活用する溢れ碁ルールを提案した.
スライド 1
ICT IoT やビッグデータ時代の ケモメトリックス / 人工知能を知って 新たなチャレンジを 株式会社インシリコデータ 湯田浩太郎 http://www.insilicodata.com 時代の新しい三大潮流 ICT : Information and Communication Technology ( 情報通信技術 ) 情報技術に通信コミュニケーションの重要性を加味した言葉 IoT : Internet
Microsoft Word - 【6.5.4】特許スコア情報の活用
Q 業界における自社および競合他社のポジショニングを確認する際など 様々な場面で特許情報分析を行うことがあるが 特許の量的側面 ( 件数 ) のみではなく 特許の質 価値的側面からの分析ができないだろうか? 1. 特許の質 価値を機械的 客観的 定量的に評価した情報として提供される特許スコア企業の知的財産戦略の策定にあたり 業界における自社および競合他社のポジショニングを確認する際など 様々な場面で特許情報分析を行うことがあるが
集中理論談話会 #9 Bhat, C.R., Sidharthan, R.: A simulation evaluation of the maximum approximate composite marginal likelihood (MACML) estimator for mixed mu
集中理論談話会 #9 Bhat, C.R., Sidharthan, R.: A simulation evaluation of the maximum approximate composite marginal likelihood (MACML) estimator for mixed multinomial probit models, Transportation Research Part
<8B D BC91BA91A58B762E656339>
安田女子大学紀要 37,221 226 2009. 新しいコンピュータ将棋の練習試合環境について TheNewPraciceMachEnvironmenofCompuerShogi NorihisaNISHIMURA はじめにコンピュータ将棋とは, コンピュータの演算処理能力を用いて将棋の各局面で最善と思われる指し手をコンピュータに選ばせることにより, コンピュータに将棋を指させるプログラムである
Microsoft PowerPoint - mp11-02.pptx
数理計画法第 2 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 前回の復習 数理計画とは? 数理計画 ( 復習 ) 数理計画問題とは? 狭義には : 数理 ( 数学 ) を使って計画を立てるための問題 広義には : 与えられた評価尺度に関して最も良い解を求める問題
プレスリリース_ _AIシリーズ_fix
2011年2月10日 思考ゲームのベストブランド AI シ リーズ 最新作 AI 囲碁 Version 19 AI 将棋 Version 18 AI 麻雀 Version 13 発売のお知らせ 株式会社イーフロンティア 本社 東京都新宿区 代表取締役 安藤 健一 は 20 年来常にトップ クラスを維持し続ける思考ゲームブランド AI シリーズ の最新作 AI 囲碁 Version 19 AI 将棋
この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができる形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の
計算機システム Ⅱ 演習問題学科学籍番号氏名 1. 以下の分の空白を埋めなさい. CPUは, 命令フェッチ (F), 命令デコード (D), 実行 (E), 計算結果の書き戻し (W), の異なるステージの処理を反復実行するが, ある命令の計算結果の書き戻しをするまで, 次の命令のフェッチをしない場合, ( 単位時間当たりに実行できる命令数 ) が低くなる. これを解決するために考案されたのがパイプライン処理である.
将棋ソフトウェアにおける棋譜データの利用と機械学習
2013/12/16-18 NINSコロキウム 分 科 会 1 将 棋 ソフトウェアにおける 棋 譜 データの 利 用 と 機 械 学 習 佐 藤 佳 州 筑 波 大 学 システム 情 報 工 学 研 究 科 パナソニック 株 式 会 社 先 端 技 術 研 究 所 2013/12/16-18 NINSコロキウム 分 科 会 2 目 次 コンピュータ 将 棋 の 現 状 とこれまでの 歴 史 ゲームの
Microsoft Word - lec_student-chp3_1-representative
1. はじめに この節でのテーマ データ分布の中心位置を数値で表す 可視化でとらえた分布の中心位置を数量化する 平均値とメジアン, 幾何平均 この節での到達目標 1 平均値 メジアン 幾何平均の定義を書ける 2 平均値とメジアン, 幾何平均の特徴と使える状況を説明できる. 3 平均値 メジアン 幾何平均を計算できる 2. 特性値 集めたデータを度数分布表やヒストグラムに整理する ( 可視化する )
較バンディットアルゴリズムを いた クラウドソーシングにおける 品質 コストトレードオフの 動調整 畠正和, 宮 純平, 場雪乃 北海道 学 /NTT, 東京 学, 京都 学
較バンディットアルゴリズムを いた クラウドソーシングにおける 品質 コストトレードオフの 動調整 畠正和, 宮 純平, 場雪乃 北海道 学 /NTT, 東京 学, 京都 学 今 のお話 ( 枚概要 ) 2 問題 クラウドソーシングの品質 コストトレードオフを調整 最終成果物の品質をできるだけ下げず コストを削減 法 較バンディットアルゴリズムを利 有 な Worker を推定しながら Task を依頼
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき
AI 1,a) 1,b) 1,c) , AI branching factor AI AI AI Proposal of Challenges and Approaches to Create Effective Artificial Players for Tur
JAIST Reposi https://dspace.j Title 戦術的ターン制ストラテジーゲームにおける AI 構成の ための諸課題とそのアプローチ Author(s) 佐藤, 直之 ; 藤木, 翼 ; 池田, 心 Citation 情報処理学会論文誌, 57(11): 2337-2353 Issue Date 2016-11-15 Type Journal Article Text version
コンピュータ将棋と並列化
コンピュータ 将 棋 と 並 列 化 ~ 緻 密 ないい 加 減 さ~ 東 京 大 学 横 山 大 作 自 己 紹 介 横 山 大 作 東 京 大 学 生 産 技 術 研 究 所 助 教 並 列 計 算 処 理 系 クラウド 環 境 などの 研 究 に 従 事 1999 年 鶴 岡 らと 激 指 開 発 スタート トップレベルソフト 世 界 コンピュータ 将 棋 選 手 権 4 回 優 勝 など 探
Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]
![Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]](/thumbs/96/128100373.jpg "Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]")
情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2 0.
資金量 方針 性格等を考慮して 自己売買ルールを確立してください 売買シミュレーションの手仕舞いマークは 仕掛けマーク ( 通常は終値 ) に対して発生します 実際の仕掛け位置が違う場合は 予定利益から計算して判断してください 取引マークはメニューの売買条件 全ペア売買条件詳細設定から確認 変更可能
チャプター 5 1. 手仕舞いの手順 仕掛けペアのサヤの動きを観察し 売買ルールに従い手仕舞いを実施します 手仕舞いには 利食い 損切り 手仕舞い期限の 3 種類があります 1. 手仕舞い情報を確認する 手仕舞い情報 には現在の日付 単価 金額 サヤ 利益が表示されますので確認してください カーソル 手仕舞い時の日付はグラフ画面のカーソルが指している情報です 通常はカーソルを当日に合わせた状態 (
ゲーム情報学研究の事例 将棋
ゲーム情報学研究の事例将棋 なぜ将棋? 2002 年の秋に中東のバーレーンで行われたチェスの対局で 最強のチェスプレーヤーの一人であるクラムニクがコンピュータと引き分けた 使用されたコンピュータは Pentium III 900MHz を8 台搭載した汎用サーバである 当時チェス世界ランキング1 位のカスパロフが IBM のディープブルーに敗れたのは 1997 年であるが 今回はディープブルーとは違って個人が使う
11yama
連立 1 次方程式の数値解法 小規模な連立 1 次方程式の解法 消去法 Gauss 消去法 Gauss-Jordan 法 ( 大規模な連立 1 次方程式の解法 ) ( 反復法 ) (Jacobi 法 ) 講義では扱わない 1 進捗状況の確認 1. gj も gjp も動いた 2. gj は動いた 3. gj も動かない 2 パターン認識入門 パターン認識 音や画像に中に隠れたパターンを認識する 音素
CONTENTS
CONTENTS ングは パラジウム触媒でなくてもいいのです ノーベル賞 ではパラジウム触媒と書いているけど 鈴木カップリングは 触媒は必要なんだけど パラジウムでなくてもいいんです ニッケルでもいいし 最近は京都大学で鉄を使う方法も考案 されました 今の段階では 僕の感じではやっぱりパラジウ ムがベストだと思いますけどね ちょっとしたエピソードがあります 2003 年だったか 現在はアメリカにいるけど当時は英国のケンブリッジにいた
技術知識 11 ディスタンスベクターとリンクステート ディスタンスベクターとは 噂話が好きな奥様達による伝言ゲームである リンクステートとは 同じカーナビをつけた走り屋の集団である... 私の先輩の格言より * * * ルーティングプロトコルの仕組みに
技術知識 11 ディスタンスベクターとリンクステート ----------------------- ディスタンスベクターとは 噂話が好きな奥様達による伝言ゲームである リンクステートとは 同じカーナビをつけた走り屋の集団である... 私の先輩の格言より * * * ルーティングプロトコルの仕組みには 大別して ディスタンスベクター型 と リンク ステート型 の 2 種類がある というようなことが
ダイジェスト 将棋ソフトは機械学習で強くなった近年 将棋ソフトの実力は人間のチャンピオンに近づいてきている 2013 年から 将棋ソフトとプロ棋士が対戦する 電王戦 というイベントが行われている 山本が開発した Ponanza( ポナンザ ) は 現役プロ棋士と対戦し 史上初の勝利を収めた その後も
公開コロキウムダイジェスト 題目 : いま あらためてコンピュータ アルゴリズムと人間の関係を考える 講師 : 山本一成 ( コンピュータ将棋ソフト Ponanza 開発者 ) 大林勇人 (( 株 )NTT データ経営研究所公共行政サービスコンサルティングユニットマネージャー ) パネル討論コーディネーター : 渡辺智暁 ( 国際大学 GLOCOM 主幹研究員 ) 日時 :2015 年 2 月 13
CLEFIA_ISEC発表
128 ビットブロック暗号 CLEFIA 白井太三 渋谷香士 秋下徹 盛合志帆 岩田哲 ソニー株式会社 名古屋大学 目次 背景 アルゴリズム仕様 設計方針 安全性評価 実装性能評価 まとめ 2 背景 AES プロジェクト開始 (1997~) から 10 年 AES プロジェクト 攻撃法の進化 代数攻撃 関連鍵攻撃 新しい攻撃法への対策 暗号設計法の進化 IC カード, RFID などのアプリケーション拡大
次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1
4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる
三者ミーティング
Corral Puzzle の 整数計画法による解法と評価 第 11 回組合せゲーム パズル研究集会 2016 年 月 7 日 ( 月 ) 大阪電気通信大学 弘中健太鈴木裕章上嶋章宏 2016//7 第 11 回組合せゲーム パズル研究集会 2 発表の流れ 研究の背景 整数計画法と先行研究 2 Corral Puzzle ルールと定義 定式化 2 種類の閉路性の定式化 7 1 6 評価 計測結果と考察