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

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

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

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

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

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

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

6 完全解析されているゲーム 連珠[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) 　　　　　　等、多数のゲームが解析されている。

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

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

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

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

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

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

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

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

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

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

17 参考資料 [1]よんろのご　幻冬舎エデュケーション [2] Janos Wagner and Istvan Virag, Solving renju, ICGA Journal, Vol.24, No.1, pp (2001) [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 (2007) [4] 田中哲朗,ボードゲーム「ジンペイ」完全解析 （修正版） [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) [6]田中哲郎, 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告Vol.2009-GI-22 No.3, pp.1-8(2009), [7]清慎一, 川嶋俊：探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, Vol GI-004, pp.69-76, [8] 5路盤の完全解析の結果