四路の碁アプリ開発

(1)

四路の碁アプリ開発

情報論理工学研究所

09-1-037-0169

高倉秀斗

(2)

本研究の目的

現在、強い囲碁

AI

を製作するにあたってモンテカルロ法を用いた

AI

が有効。

しかし本研究ではモンテカルロ法を用いた

AI

を作成する以前の基本となる一定手数の先読みを行うだけの

CPU

を作成する。この方法の

AI

ならばどれほどに強くなるのか、

処理時間はどれほどにかかるのかを調べるこ

とを目的とする。

(4)

「よんろのご」とは



「よんろのご」とは

^[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] ^田中哲郎⁽²⁰⁰⁹⁾ 　　　　

等、多数のゲームが解析されている。

(7)

囲碁の場合

 4×4

双方最善手を打つと引き分け

^[7]

 5×5

黒（先手）の

25

目勝ち

^[8]

 6×6 ^以上の碁

現在まだ解析されていない

(8)

囲碁 AI

４

×

４の碁盤の囲碁　

3,047,783

通り

　　　 ↓

データベース持てば最強！！

しかしデータベースはミニ碁しか使えない

よって、先読みを行う囲碁

AI

を作成本研究

　← 　　　

＋

モンテカルロ囲碁

AI

を作成

(9)

評価関数・先読み方法

ある局面の評価を行う評価値は地を数え、

黒の地・白の地の多少により決定する。

現在着手可能な手の中から評価値の高い所

　　　　↓

プレイヤー側の評価値の高い所

ループ後、最も評価値が高かった所へ

(10)

四路の碁アプリケーション

四路の碁アプリケーションは以下の

3

つのクラスから成る。

 goApplet

クラス

 List

クラス

 CPU

クラス

(11)

goApplet クラス

　1.

先攻・後攻を選択

2.16

のボタンから着手す

る手を選択

リセットボタンで

1

へ

図 2 はアプリケーションを実行した画像である。

^図 ²

(12)

List クラス

List

クラスでは



局面の状況を表す配列

ターンが終了する都度行われる



連を設定するメソッド



連が取り除かれるか判定を行うメソッド



連を取り除くメソッド



着手可能な場所を判定するメソッド



指定した場所へ着手するメソッド



現在の局面の評価値を出すメソッド

等を保持している。

(13)

CPU クラス

CPU

クラスでは



先読みし、最も評価値の大きい手に着手するメソッド



ランダムに着手するメソッド

^{を保持している。}

(14)

結果 / 対ランダム CPU

表ランダムに着手する CPU との勝率（ 100 回）と 1 手目にかかる処理時間

勝率 (%)　　　　　　　処理時間 (ms)

先読み回数 1 回 2 回 3 回 4 回 5 回勝率 (%) 73 88 99 100 100

処理時間(ms) 63 110 390 4134 57267

1回 2回 3回 4回 5回

0 20 40 60 80 100 120

1回 3回 2回 4回 5回

0 10000 20000 30000 40000 50000 60000 70000

(15)

結論



対ランダム

CPU

に対して先読み回数を増やすごとに勝率を伸ばす

AI

を作成できた。



しかし、処理時間が非常に時間が掛かること

がわかった。

(16)

今後の課題

処理時間が非常にかかる理由としては、アプリケーションを作成する際に予めきちんとした設計を行ってなかったことが挙げられる。

よって今後の課題としては、



それぞれの処理を最適化、処理時間を短縮すること。



より強い

CPU

と対戦させより高い勝率を目指すこと。



今回用いなかったモンテカルロ法を組み合わせ、より大きな碁盤での軽い囲碁アプリケーションを作成すること。

が挙げられる。

(17)

参考資料

[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

四路の碁アプリ開発