リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 09-037-0164 前田昂寛.

Slides:



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

Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
Othello Let us cling together. メンバー 班長 杉本友宏 プログラマー 京谷貴平 アルゴリズム 佐野祐之 パワーポイント 菊澤遼平 発表 川本敏和.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
VsOtha version /08/13 xhl. vsOtha version /08/13 xhl.
MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
コンピュータオセロ ~人類を超えた知能~ 海野裕也・大倉務 林崎弘成・藤田肇.
リレーショナル・データベース データベース論 第10回.
ラベル付き区間グラフを列挙するBDDとその応用
ML 演習 第 8 回 2007/07/17 飯塚 大輔, 後藤 哲志, 前田 俊行
コンピュータ囲碁の仕組み ~ 将棋との違い ~
ブロック運びゲーム.
全体ミーティング (4/25) 村田雅之.
四路の碁アプリ開発 情報論理工学研究所 高倉秀斗.
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
Lispとは ゲーム理論 minimaxアルゴリズム αβアルゴリズム ソースコードの一部
2004年度JAVAゼミコンテスト作品 「Othello」
インタラクティブ・ゲーム制作 <プログラミングコース>
仮想マシンの並列処理性能に対するCPU割り当ての影響の評価
コンピュータオセロ ~人類を超えた知能~ 海野裕也・大倉務 林崎弘成・藤田肇.
15パズルの解法について 北海道情報大学 情報メディア学部 情報メディア学科 新井山ゼミ  大石 貴弘.
多数の遊休PC上での 分散ゲーム木探索 導入 ゲーム木探索 ⇒遊休PCを利用して高速化 例)コンピュータ将棋における次手の計算
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
クロスワードゲームの 作り方を学ぼう/やってみよう ‐ボードゲームの動作機構‐
モンテカルロ法と囲碁・将棋ソフトの人知超え
数独パズルの難易度判定 ~解法ロジックを用いた数値化の提案~
単位 おねだり ☆オセロ おねだり隊☆D班.
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
中距離走におけるバウンディング トレーニングの有効性について
京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
情報論理工学 研究室 第6回: リバーシの合法手生成.
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
~オセロゲーム~ アルゴリズムとそのプログラム
高速剰余算アルゴリズムとそのハードウェア実装についての研究
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
テトリスにおけるAI の開発 情報論理工学研究室 13— 川原 翔太.
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
三次元チェスアプリケーションの開発 およびUIの機能向上
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
不確実データベースからの 負の相関ルールの抽出
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
理工学部情報学科 情報論理研究室 野中章宏 2016年2月5日
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
全体ミーティング (5/23) 村田雅之.
ガイダンス 電子計算機 電気工学科 山本昌志 1E
数値解析ⅡーI ~オセロゲームのプログラム~
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
リバーシ 06a1056 藤田将義.
リレーショナル・データベース J2EE I (データベース論) 第2回 /
飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
Presentation transcript:

リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ 09-037-0164 前田昂寛

目次 1:本研究の目的 2:本研究で使用した評価関数 3:序盤・中盤の評価関数 4:終盤の評価関数 5:本研究で用いたプログラム 6:実験 7:結論 8:今後の課題 9:参考文献

本研究の目的 ・一般的なリバーシプログラムは先読み数が少ない といった解析にあたっての問題がある ・本研究ではマルチスレッド処理によりリバーシプロ グラムが高速化できることを示す   

リバーシプログラムの現状 ・現状完全解析には至っていない ・強いプログラムにするために定石データベースを使用  -Logistello:https://skatgame.net/mburo/log.html  -Zebra:http://radagast.se/othello/ ・評価関数  -必勝読み:最終局面で自分の勝敗を評価  -着手可能手数:自分が打てるマスの数

強いリバーシプログラム ・Logistello -定石データベースを使用したプログラム -1997年、村上健八段に勝利  -定石データベースを使用したプログラム  -1997年、村上健八段に勝利  -定石データベースに依存しているため、定石以外の   手を打たれた場合の動作は未知 ・Zebra  -定石データベースと先読みを使ったプログラム  -先読み数を変更できる  -定石データベースである「book」を上書きで学ばせ   ることができる

・定石とは一般的に有利になりやすいと言われるパター ン 兎定石後の5手目 虎定石後の5手目 牛定石後の5手目   兎定石後の5手目      虎定石後の5手目      牛定石後の5手目   a b c d e f g h 1 2 3 4 5 6 7 8 a b c d e f g h 1 2 3 4 5 6 7 8 a b c d e f g h 1 2 3 4 5 6 7 8

評価関数 ・リバーシにおける評価関数 (ex. ・山、ウィング、開放度、着手可能数、C打ち、X打ち判 定、確定石 ・その他にも盤面評価値、直線性、中割り、引っ張り etc・・・ ・これらは先読みを加えることでより高度な評価が可能

本研究で使用した評価関数 ・序盤・中盤の評価関数 ・終盤の必勝読み ・終盤の完全読み

本研究で使用した 序盤・中盤の評価関数 ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山 終盤 必勝読み 完全読み ・着手可能手数、確定石 ・C打ち、X打ち判定 ・ウィング ・山 ・開放度   ※リバーシのアルゴリ ズム[1]より

着手可能手数、確定石 ・着手可能手数:着手可能手数では自分が打てる石が 多ければ多い程高評価である。これは、戦略が膨らむ からである ・確定石:ゲーム終了まで二度と裏返らない石のことをいう。確 定石は有利な局面を作るためには非常に重要で、角を取れば 有利に対戦を進められるという一般的見解はこの確定石である ことが大きな意味を持つ。周囲に空きマスがない状態で、連接 する石が裏返らない時になる。

・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。 C打ち、X打ち ・角の隣と斜め隣の事を言う。一般的に不利と言われて いる場所である。

・ウィングは一般的に不利な形と言われているマイナス 評価である

・ウィングは一般的に不利な形と言われているマイナス 評価である

・山とは一般的に有利な形と言われている。 左は山の形。右側は山の有利な例。次が黒番の時、白は必ず隅を取 れる

開放度 ・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる → 相手の打てる場所を少なく する為、小さいほど高評価 ・自分が打った手によって裏返る石の周辺8マスが空き マスかどうかを調べる → 相手の打てる場所を少なく する為、小さいほど高評価 A=3 H=6+2=8 B=3 I =6 C=3 J =5 D=3+2=5 E=2+1+4=7 F=1 G=3               

・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より 本研究で使用した 終盤の評価関数 序盤・中盤の 評価関数 終盤 ・必勝読み ・完全読み ※リバーシのアルゴリズム[1]より 必勝読み 完全読み

必勝読み、完全読み ・終盤の評価関数の特徴 -終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい  -終盤では単に勝敗や自分の取れる石の数が多い か少ないかを見ればよい ・完全読み:color*(count(BLACK) – count(WHITE)) ・必勝読み:完全読みと違いWIN=1,LOSE=- 1,DRAW=0しか見ず石の数を無視するため、比較演算 子を用いる時に計算量を軽くできる

・SSAI ・MSAI 本研究で用いたプログラム

SSAI   ・SSAI:本研究で用いたJava言語によるシングルスレッドプログラミングによるリバーシ 評価関数 決定 探索 評価         SSAI

SSAIの処理 ・クラスAIで探索処理 ・評価関数決定: ー序盤・中盤の評価関数 ー終盤の必勝読み -終盤の完全読み ・探索:   ・クラスAIで探索処理 ・評価関数決定:  ー序盤・中盤の評価関数  ー終盤の必勝読み  -終盤の完全読み ・探索:  ーα-β法による再起処理

・MSAI:本研究に用いたJava言語によるマルチスレッド プログラミングによるリバーシ 評価関数 決定 探索 評価 MSAI

MSAIの処理 枝木一つに対し1スレッド ・クラスAIとクラスMultiAIで探索 ・評価関数決定: -序盤・中盤の評価関数  -序盤・中盤の評価関数  -終盤の必勝読み  -終盤の完全読み ・探索:  -α-β法による再起処理  -候補手の分だけサブスレッド作成  枝木一つに対し1スレッド

実験環境 実験内容 先読み設定数 Let'sNote,VT64の実験結果  実験環境  実験内容  先読み設定数 Let'sNote,VT64の実験結果 実験

実験環境 ・Let'sNote: ープロセッサ:Intel Core2Duo L7800 2コア 2GHz -メモリ(RAM):2GB  -OS:WindowsVista  -Java実行環境:eclipse ・VT64:  -プロセッサ:(AMD Opteron 1.9GHz 12コア)*4  -メモリ(RAM):128GB  -OS:CentOS  -Java実行環境:ターミナル 48コア

実験内容 ・対戦方法:SSAI,MSAIをランダムなAIと実験環境下で 先攻、後攻分けて対戦させる ・実行:ある先読み設定数で100回実行 ・処理時間の見方:ある先読み設定数で100回実行し た時の合計実行時間を見る

先読み設定数 ・

Let'sNote実験結果(勝敗) 後攻 先攻

VT64実験結果(勝敗) 後攻 先攻

SSAIの実験結果 VT64 ※処理時間は秒 Let'sNote

MSAIの実験結果 VT64 ※処理時間は秒 Let'sNote

VT64とLet'sNoteによる実験 ・MSAIで見た時、先の実験ではLet'sNoteとVT64は処 理時間に差がでなかった ・eclipseによりJavaプログラムが高速動作していた可 能性があることから、MSAIに限定してターミナルによる 実験を行う。 ・後攻先攻の差がほとんど見られないので後攻に限定

先読み設定数 ・

VT64とLet'sNoteによる実験 ※処理時間は秒

結論 ・マルチスレッドプログラミングにより、探索による処理 時間を大幅に短縮することができた ・eclipseを使用することにより、Let'sNoteの様なコア数 の少ない計算機でもマルチコアコンピュータに勝る結果 を出すことが可能となった

今後の課題 処理時間を大幅に短縮したので、より複雑な評価 関数を導入する必要がある。 そうなった時、探索に並び評価に多大な時間を要 することが予測されるため、評価関数の並列化が 今後の課題である。

参考文献 [1]Seal Software ,リバーシのアルゴリズム,工学社,2003 [2]結城浩,Java言語で学ぶデザインパターン入門[マルチスレッド 編],SoftBankCreative,2006 [3]日本オセロ連盟,http://www.othello.gr.jp/beginner/s_01.html,オ セロ講座,初心者,2002 [4]大筆豊,オセロプログラムの評価関数の改善について,情報処理 学会研究報告2004-GI-11 ,p.15-p.20,2004