四路の碁アプリ開発 情報論理工学研究所 09-1-037-0169 高倉秀斗.

Slides:



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

HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
強豪囲碁ソフト「彩」について 山下 宏 2009 年 9 月 11 日 機械振興会館 ※彩(あや)と読みま す.
Othello Let us cling together. メンバー 班長 杉本友宏 プログラマー 京谷貴平 アルゴリズム 佐野祐之 パワーポイント 菊澤遼平 発表 川本敏和.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
VsOtha version /08/13 xhl. vsOtha version /08/13 xhl.
5路盤の完全解析の結果 論文名:Solving Go on Small Boards 著者: Eric C.D. van der Werf
囲碁プログラミングの探索における小目標間の依存関係解決に向けて
ファイルキャッシュを考慮したディスク監視のオフロード
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
近畿大学理工学部情報学科 情報論理工学研究室 滝口 直
コンピュータ囲碁の仕組み ~ 将棋との違い ~
群論とルービックキューブ 白柳研究室  水野貴裕.
リバーシの並列化 並列化するときに起こる問題を定義しろ おぷてぃまいざー SSAIとMSAIは比較しろ  前田昂寛.
インタラクティブ・ゲーム制作 <プログラミングコース>
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
クロスワードゲームの 作り方を学ぼう/やってみよう ‐ボードゲームの動作機構‐
モンテカルロ法と囲碁・将棋ソフトの人知超え
単位 おねだり ☆オセロ おねだり隊☆D班.
第7回 卒研進行状況 04A2029           古賀慎也.
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
モンテカルロ碁 電気通信大学 村松研究室 下川和也.
UCB+ 法を用いた Big Two AI の研究
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
情報論理工学 研究室 第6回: リバーシの合法手生成.
第四回 ゲーム                 05A1054         前田嵩公.
Handel-Cを用いた ちょっとレトロ な 「よけゲー」 の設計
プログラム実行履歴を用いたトランザクションファンクション抽出手法
1DS04173G 勝田恒士郎 1DS04188W 田中甲太郎 1DS04218W 上野義貴
オブジェクト指向 プログラミング 第十四回 知能情報学部 新田直也.
P2P方式によるオンラインゲームの研究、開発
シャノンのスイッチングゲームにおけるペアリング戦略について
高速剰余算アルゴリズムとそのハードウェア実装についての研究
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
情報論理工学 研究室 第10回 完全解析されたゲーム.
コード配色の変更を認めるマスターマインドの 推測回数に関する考察
テトリスにおけるAI の開発 情報論理工学研究室 13— 川原 翔太.
二人零和不完全情報ゲームであるジャンケンにおけるゲームの洗練法
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
情報検索(6) メディア検索の仕組み 教員 岩村 雅一
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
BLACK JACKの作成 ブラックジャックのルール 概要 勝敗の判定 開発中の問題点 Aの扱いについて 配り直し(DEAL) 工夫した点
三次元チェスアプリケーションの開発 およびUIの機能向上
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
暗号技術 ~暗号技術の基本原理~ (1週目) 情報工学科  04A1004 石川 真悟.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
JavaScript プログラミング演習 - じゃんけんゲーム - 「ホームページを動的に制御したい…」
プログラミング言語論 第四回 理工学部 情報システム工学科 新田直也.
シューティングゲームにおける 未経験者と経験者の差異の解析
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
理工学部情報学科 情報論理研究室 野中章宏 2016年2月5日
麻雀ゲームにおけるAIの開発    日高大地   近畿大学理工学部情報学科  
コーディングパターンの あいまい検索の提案と実装
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
数値解析ⅡーI ~オセロゲームのプログラム~
指導教員 石水 隆 講師 情報論理工学研究室 木ノ下 翔大
メソッドの同時更新履歴を用いたクラスの機能別分類法
リバーシ 06a1056 藤田将義.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
Othello G班         山崎 木下 山本 上手      .
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
Presentation transcript:

四路の碁アプリ開発 情報論理工学研究所 09-1-037-0169 高倉秀斗

目次 本研究の目的 四路の碁とは?/囲碁のルール 現在完全解析されているゲーム 作成した囲碁AIの方針 評価関数・先読みの方法 囲碁アプリケーションの説明 結果・結論 今後の課題 参考文献

本研究の目的 現在、強い囲碁AIを製作するにあたってモンテカルロ法を用いたAIが有効。  しかし本研究ではモンテカルロ法を用いたAIを作成する以前の基本となる一定手数の先読みを行うだけのCPUを作成する。この方法のAIならばどれほどに強くなるのか、処理時間はどれほどにかかるのかを調べることを目的とする。

「よんろのご」とは 「よんろのご」とは[1]よんろのご 幻冬舎エデュケーション 「よんろのご」とは[1]よんろのご 幻冬舎エデュケーション 2011年7月に発売された張栩九段(棋聖・王座)が考案した4*4の盤面と囲碁のルールを用いたパズルである。        図1

囲碁のルール 囲碁のルール 二人で黒と白の石を交互に碁盤の交点へ打っていく 呼吸点のない石は碁盤から取り除かれる。 呼吸点の無くなる所へは打てない。 1手前と全く状況が同じになる所へは打てない。(刧) 勝敗は地の多少で決定する。

完全解析されているゲーム 連珠[2]Janos Wagner and Istvan Virag(2001) チェッカー[3]Jonathan Schaeffer, Neil Burch, Yngvi Bjorsson, Akihiro Kishimoto,             Martin Muller, Robert Lake, Paul Lu, and Steve Suphen(2007) シンペイ[4]田中哲朗 6×6リバーシ[5]Joel Feinstein(1993) どうぶつしょうぎ[6]田中哲郎(2009)       等、多数のゲームが解析されている。

囲碁の場合 4×4  双方最善手を打つと引き分け[7] 5×5  黒(先手)の25目勝ち[8] 6×6以上の碁  現在まだ解析されていない

囲碁AI 4×4の碁盤の囲碁 3,047,783 通り ↓ データベース持てば最強!! しかしデータベースはミニ碁しか使えない +  4×4の碁盤の囲碁 3,047,783 通り         ↓     データベース持てば最強!! しかしデータベースはミニ碁しか使えない よって、先読みを行う囲碁AIを作成 ←本研究         +    モンテカルロ囲碁AIを作成

評価関数・先読み方法 ある局面の評価を行う評価値は地を数え、黒の地・白の地の多少により決定する。 現在着手可能な手の中から評価値の高い所 ↓  ある局面の評価を行う評価値は地を数え、黒の地・白の地の多少により決定する。 現在着手可能な手の中から評価値の高い所          ↓   プレイヤー側の評価値の高い所   ループ後、最も評価値が高かった所へ

四路の碁アプリケーション  四路の碁アプリケーションは以下の3つのクラスから成る。 goAppletクラス Listクラス CPUクラス

goAppletクラス 1.先攻・後攻を選択 2.16のボタンから着手す る手を選択 図2 リセットボタンで1へ 2.16のボタンから着手す る手を選択  リセットボタンで1へ  図2はアプリケーションを実行した画像である。      図2

Listクラス 局面の状況を表す配列 連を設定するメソッド 連が取り除かれるか判定を行うメソッド 連を取り除くメソッド ターンが終了する都度行われる 連を設定するメソッド 連が取り除かれるか判定を行うメソッド 連を取り除くメソッド 着手可能な場所を判定するメソッド 指定した場所へ着手するメソッド 現在の局面の評価値を出すメソッド            等を保持している。

CPUクラス CPUクラスでは 先読みし、最も評価値の大きい手に着手するメソッド ランダムに着手するメソッド               を保持している。

結果/対ランダムCPU 表ランダムに着手するCPUとの勝率(100回)と1手目にかかる処理時間 勝率(%) 処理時間(ms) 先読み回数 1回 2回 3回 4回 5回 勝率(%) 73 88 99 100 処理時間(ms) 63 110 390 4134 57267

結論 対ランダムCPUに対して先読み回数を増やすごとに勝率を伸ばすAIを作成できた。 しかし、処理時間が非常に時間が掛かることがわかった。

今後の課題 それぞれの処理を最適化、処理時間を短縮すること。 より強いCPUと対戦させより高い勝率を目指すこと。  処理時間が非常にかかる理由としては、アプリケーションを作成する際に予めきちんとした設計を行ってなかったことが挙げられる。 よって今後の課題としては、 それぞれの処理を最適化、処理時間を短縮すること。 より強いCPUと対戦させより高い勝率を目指すこと。 今回用いなかったモンテカルロ法を組み合わせ、より大きな碁盤での軽い囲碁アプリケーションを作成すること。                  が挙げられる。

参考資料 [1]よんろのご 幻冬舎エデュケーション http://www.gentosha-edu.co.jp/products/post-95.html [2] Janos Wagner and Istvan Virag, Solving renju, ICGA Journal, Vol.24, No.1, pp.30-35 (2001) http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf [3] Jonathan Schaeffer, Neil Burch, Yngvi Bjorsson, Akihiro Kishimoto, Martin Muller, Robert Lake, Paul Lu, and Steve Suphen, Checkers is solved, Science Vol.317, No,5844, pp.1518-1522 (2007) http://www.sciencemag.org/content/317/5844/1518.full.pdf [4] 田中哲朗,ボードゲーム「ジンペイ」完全解析 (修正版) http://media.itc.u-tokyo.ac.jp/ktanaka/simpei/20060307-rev.pdf [5] Joel Feinstein, Amenor Wins World 6x6 Championships!, Forty billion noted under the tree (July 1993), pp.6-8, British Othello Federation's newsletter., (1993) http://www.britishothello.org.uk/fbnall.pdf [6]田中哲郎, 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告Vol.2009-GI-22 No.3, pp.1-8(2009), http://dobutsushogi.net/ [7]清慎一, 川嶋俊:探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, Vol. 2000-GI-004, pp.69-76, http://id.nii.ac.jp/1001/00058633/ [8] 5路盤の完全解析の結果 http://www.yss-aya.com/5x5-cgf.ppt