モンテカルロ碁 電気通信大学 村松研究室 下川和也.

Slides:



Advertisements
Similar presentations
コンピュータ囲碁における Root 並列化について 発表者 副島 佑介. 目次 研究背景 – 囲碁の難しさ – モンテカルロ木探索について – 並列化手法の先行研究 提案手法 – Root 並列化における合議制 実験結果 まとめ.
Advertisements

G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩(あや)と読みま す.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
5路盤の完全解析の結果 論文名:Solving Go on Small Boards 著者: Eric C.D. van der Werf
囲碁プログラミングの探索における小目標間の依存関係解決に向けて
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
コンピュータ囲碁の仕組み ~ 将棋との違い ~
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
群論とルービックキューブ 白柳研究室  水野貴裕.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
整数計画法を用いた ペグソリティアの解法 ver. 2.1
モンテカルロ法と囲碁・将棋ソフトの人知超え
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
単位 おねだり ☆オセロ おねだり隊☆D班.
VI-7 連続分布(面データ)を分析する方法
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
UCB+ 法を用いた Big Two AI の研究
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
回帰モデル・クラス分類モデルを 評価・比較するための モデルの検証 Model validation
情報論理工学 研究室 第6回: リバーシの合法手生成.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
~オセロゲーム~ アルゴリズムとそのプログラム
計算機実験の計画 References 研究目的 囲碁・将棋での強化学習 高信頼性人工知能システムへの展望 大規模な強化学習技術の実証と応用
決定木とランダムフォレスト 和田 俊和.
情報論理工学 研究室 第10回 完全解析されたゲーム.
Copyright (C) 2011 Hideki Kato
1. MC/UCT アルゴリズムの 並列化に伴う挙動の変化 2. 探索木共有型並列と マスタスレーブ型並列 ― プラットフォームとの関係 ―
前回の練習問題.
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
データ構造とアルゴリズム論 第6章 整列(ソート)のアルゴリズム
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
決定木 Decision Tree DT 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
A Simple Algorithm for Generating Unordered Rooted Trees
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
JavaScript プログラミング演習 - じゃんけんゲーム - 「ホームページを動的に制御したい…」
スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
疑似乱数, モンテカルロ法によるシミュレーション
Hoffman符号 2011/05/23.
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
コミュニケーションと ネットワークを探索する
超短期トレードで生き残るためのテクニックと考え方
ベイズ最適化 Bayesian Optimization BO
Data Clustering: A Review
自己組織化マップ Self-Organizing Map SOM
遺伝的アルゴリズム (GA) を活用した スペクトルの波長選択および時系列 データにおけるプロセス変数かつその時間 遅れ (ダイナミクス) の選択 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
全体ミーティング (5/23) 村田雅之.
数値解析ⅡーI ~オセロゲームのプログラム~
Advanced Data Structure 第3回
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
実験計画法 Design of Experiments (DoE)
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
Presentation transcript:

モンテカルロ碁 電気通信大学 村松研究室 下川和也

モンテカルロ碁とは モンテカルロ法を囲碁に応用したもの プレイアウトを繰り返し、最も勝率の高い着手 を選ぶ 2006年、Crazy Stoneがコンピュータオリンピ アード9路盤で優勝

プレイアウト ある局面から、ランダムに着手して、終局まで プレイすること 互いに自分の「眼」を埋める以外の合法手がなく なれば終局 中国ルールで勝敗を計算

プレイアウトの例 終局面

考え方 … … … 各候補手の着手後の局面でプレイアウト :局面 :着手 :プレイアウト :黒の勝ち :白の勝ち 勝率 30% 勝率 60% 勝率 10%

問題点 明らかに悪い手にもプレイアウトを均等に実行 してしまう 有望な候補手により多くのプレイアウトを割り 当てたい

UCB(Upper Confidence Bound) 選択回数が 少ないものほど 高く 勝率が 高いものほど 高く UCB値が最も高い候補手に対してプレイアウト

最もUCB値が高い候補手に対してプレイアウト :局面 … … … :着手 :プレイアウト :黒の勝ち :白の勝ち UCB値 :0.8 UCB値 :0.9 UCB値 :0.7

着手選択の基準 勝率が高いものを選ぶ UCB値が高いものを選ぶ プレイアウト回数が高いものを選ぶ ―勝率の信頼性が低い可能性 ―勝率が低い可能性 プレイアウト回数が高いものを選ぶ ―通常はこれを用いる

まとめ プレイアウトはランダムに着手していき、中国 ルールで勝敗を判定する UCB値を用いることで効率的にプレイアウトを 割り当てることができる 現在のコンピュータ囲碁は、UCB値を用いて木 探索を行うUCT(UCB for Tree)が主流である