囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.

Slides:



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

『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩(あや)と読みま す.
Microsoft PowerPoint IT講習会 /22 (Tue) テックサポーター 熊谷武将.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
囲碁プログラミングの探索における小目標間の依存関係解決に向けて
CPUとGPUの 性能比較 -行列計算およびN体問題を用いて-
将棋名人のレーティングと棋譜分析 山下 宏 2014年11月7日 GPW 箱根.
コンピュータ囲碁の仕組み ~ 将棋との違い ~
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
将棋プログラム「激指」  鶴岡 慶雅.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
東京経営短期大学 経営総合学科 准教授 玉田 和恵
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
スコアによるキューブアクションの違い なにが“学会”発表にふさわしいのか考える。結論自体は分かっていた。そこに至るまでのプロセスが新しい。(かもしれない) 少なくとも整理されていて、わかりやすい。また、視覚的に覚えやすい。
慶應義塾大学商学部 吉川肇子 (きっかわとしこ)
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
モンテカルロ法と囲碁・将棋ソフトの人知超え
単位 おねだり ☆オセロ おねだり隊☆D班.
第7回 卒研進行状況 04A2029           古賀慎也.
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
UCB+ 法を用いた Big Two AI の研究
春の統計学・計量経済学勉強会 第1回:2017年2月21日(火) 市野泰和
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
管理的側面 管理者に必要な経営知識 経営学の基本 ①マネジメントと組織.
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
~オセロゲーム~ アルゴリズムとそのプログラム
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
東京経営短期大学 経営総合学科 准教授 玉田 和恵
小山工業高等専門学校 電子制御工学科 4年 小山田 晃
CPUの仕組み 1E16M002-5 阿部知也 1E16M007-3 伊藤達哉 1E16M026-9 小島祥太郎 1E16M069-8 峰晴晃優 1E16M070-0 宮路暁久 1E14M070-5 南元喜.
計算機実験の計画 References 研究目的 囲碁・将棋での強化学習 高信頼性人工知能システムへの展望 大規模な強化学習技術の実証と応用
高速剰余算アルゴリズムとそのハードウェア実装についての研究
コンピュータを知る 1E16M009-1 梅津たくみ 1E16M017-8 小沢あきら 1E16M035-0 柴田かいと
思考支援ツールを用いた 情報処理技術知識の学習方式
第5章:特徴の評価とベイズ誤り確率 5・3:ベイズ誤り確率とは
Copyright (C) 2011 Hideki Kato
1. MC/UCT アルゴリズムの 並列化に伴う挙動の変化 2. 探索木共有型並列と マスタスレーブ型並列 ― プラットフォームとの関係 ―
情報とコンピュータ 静岡大学工学部 安藤和敏
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
(昨年度のオープンコースウェア) 10/17 組み合わせと確率 10/24 確率変数と確率分布 10/31 代表的な確率分布
個人の動画配信のためのWebサーバ構築 06A1058 古江 和栄.
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報A 第15回授業 04情報のディジタル化 対応ファイル:12exp15.xls
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
ベイズ最適化 Bayesian Optimization BO
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
自己組織化マップ Self-Organizing Map SOM
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
全体ミーティング (5/23) 村田雅之.
数値解析ⅡーI ~オセロゲームのプログラム~
Othelloのプログラム 班長:佐々木 悠二 班員:石黒 護     井上 雄滋     齊藤 良裕     清水 裕亮.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
第28回世界コンピュータ将棋選手権アピール文章 作成:井本 康宏 作成日:2018/3/吉日
関数教育における数式処理 電卓の短期利用とその効果
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
Othello G班         山崎 木下 山本 上手      .
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
第3章 統計的推定 (その2) 統計学 2006年度 <修正・補足版>.
複数ホストにまたがるVMの 高速かつ柔軟な 部分マイグレーション
情報とコンピュータ 静岡大学工学部 安藤和敏
Presentation transcript:

囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008

モンテカルロ法の衝撃 1996年 囲碁プログラム「彩」を作りはじめる 2007年 GnuGoがKGSで6級、彩は8級 2007年 10月にモンテカルロ法に移行 2008年 2月、モンテカルロ法の彩が3級に 12年かけてGnuGoにすら届かなかったのが4ヶ月でGnuGoを遥かに追い越した! 従来の人間の思考の真似をしていたプログラマには大ショック

モンテカルロ法の仕組み 1.乱数で黒石、白石を交互に置く 2.打つ場所がなくなったら終了 3.点数を計算する 4.1. - 3. を何度も繰り返す (実際のサンプルを表示)

シンプルな評価関数 人間の知識が少ない 人間の棋譜から特長を学習 大量の単純な計算を繰り返すことで正確な評価が可能 泥臭い作業は不要! 好形、悪形の認識 相手の直前の手からの距離 大量の単純な計算を繰り返すことで正確な評価が可能 コンピュータらしい方法

パターンを利用して乱数を賢くする 3x3のパターンを学習 人間の棋譜から統計を取る 着手確率を求める 高確率 低確率

黒石の着手確率 数値が大きいほど着手確率が高い

パターンを利用したサンプル サンプルを再生

局面評価の結果 単純な乱数 パターンを利用 黒いほど黒の陣地になりやすい 白いほど白の陣地になりやすい

局面評価の結果(極端な例) 単純な乱数 パターンを利用 単純な乱数は上下の黒石が接続しているのが分かってない パターンを利用した方がより正しく局面を理解している

9路盤と19路盤での違い 探索速度 9路盤では枝刈しなくてもそこそこ強いものが作れる 9路盤 6300 playout/秒 Core Duo 1.83GHz 19路番 1600 playout/秒 1 coreのみで それほど速いわけではない 9路盤では枝刈しなくてもそこそこ強いものが作れる 19路盤では可能な手の数が多いため「手をしぼる」作業を行わないとあまり強くできない。

19路盤での候補手の選択方法 3x3のパターン 盤の端からの距離での確率 直前の相手の手からの距離 2手前の自分の手との距離 連の死活探索の結果 「死んだ」石が動き出す確率を極端に下げる 上位20手程度だけを探索

時間をかけると強くなる? レーティング(強さを点数化) 2倍の思考時間を使うとレーティングは 囲碁も将棋も同じ程度強くなる 100点で1段差 100点上がると勝率は0.64上昇 2倍の思考時間を使うとレーティングは 将棋 63点上昇(将棋プログラムYSSの場合) 囲碁 65点上昇(囲碁プログラム彩の場合) 囲碁も将棋も同じ程度強くなる しかし並列化した場合は…?

並列化がしやすい 将棋 αβ法は並列効率が悪い 囲碁 モンテカルロ法は並列効果がよい!

将棋よりも囲碁も方が先に?! モンテカルロ法が本格的になって1年で9路でプロに近いレベルに 2年でプロに19路で8子で勝利 8コアで。コア数が4倍になれば1子減る? 将棋は2010年に名人に勝つ?予想 このペースで進むなら将棋よりも先に囲碁の方が名人に勝ってしまうかも