四路の碁アプリ開発

四路の碁アプリ開発
情報論理工学研究所
09-1-037-0169
高倉秀斗
目次









本研究の目的
四路の碁とは？/囲碁のルール
現在完全解析されているゲーム
作成した囲碁AIの方針
評価関数・先読みの方法
囲碁アプリケーションの説明
結果・結論
今後の課題
参考文献
本研究の目的
現在、強い囲碁AIを製作するにあたってモ
ンテカルロ法を用いたAIが有効。
しかし本研究ではモンテカルロ法を用いた
AIを作成する以前の基本となる一定手数の先
読みを行うだけのCPUを作成する。この方法
のAIならばどれほどに強くなるのか、処理時
間はどれほどにかかるのかを調べることを目
的とする。
「よんろのご」とは

「よんろのご」とは[1]よんろのご
幻冬舎エデュケーション
2011年7月に発売された張栩九段(棋聖・王座)
が考案した4*4の盤面と囲碁のルールを用い
たパズルである。
図1
囲碁のルール
囲碁のルール

二人で黒と白の石を交互に碁盤の交点へ打っていく

呼吸点のない石は碁盤から取り除かれる。

呼吸点の無くなる所へは打てない。

1手前と全く状況が同じになる所へは打てない。（刧）

勝敗は地の多少で決定する。
完全解析されているゲーム

連珠[2]Janos Wagner and Istvan Virag(2001)

チェッカー[3]Jonathan Schaeffer, Neil Burch, Yngvi Bjorsson, Akihiro
Kishimoto,
Suphen(2007)
Martin Muller, Robert Lake, Paul Lu, and Steve

シンペイ[4]田中哲朗

6×6リバーシ[5]Joel Feinstein(1993)

どうぶつしょうぎ[6]田中哲郎(2009)
等、多数のゲームが解析されている。
囲碁の場合



4×4
双方最善手を打つと引き分け[7]
5×5
黒（先手）の25目勝ち[8]
6×6以上の碁
現在まだ解析されていない
囲碁AI
４×４の碁盤の囲碁 3,047,783 通り
↓
データベース持てば最強！！
しかしデータベースはミニ碁しか使えない
よって、先読みを行う囲碁AIを作成
＋
モンテカルロ囲碁AIを作成
←本研究
評価関数・先読み方法
ある局面の評価を行う評価値は地を数え、
黒の地・白の地の多少により決定する。
現在着手可能な手の中から評価値の高い所
↓
プレイヤー側の評価値の高い所
ループ後、最も評価値が高かった所へ
四路の碁アプリケーション
四路の碁アプリケーションは以下の3つのク
ラスから成る。

goAppletクラス

Listクラス

CPUクラス
goAppletクラス
1.先攻・後攻を選択
2.16のボタンから着手す
る手を選択
リセットボタンで1へ
図2はアプリケーションを実行した画像で
ある。
図2
Listクラス
Listクラスでは

局面の状況を表す配列
ターンが終了する都度行われる






連を設定するメソッド
連が取り除かれるか判定を行うメソッド
連を取り除くメソッド
着手可能な場所を判定するメソッド
指定した場所へ着手するメソッド
現在の局面の評価値を出すメソッド
等を保持している。
CPUクラス
CPUクラスでは

先読みし、最も評価値の大きい手に着手するメソッド

ランダムに着手するメソッド
を保持している。
結果/対ランダムCPU
表ランダムに着手するCPUとの勝率（100回）と1手目にかかる処理時間
先読み回
数
勝率(%)
処理時間
(ms)
勝率(%)
120
1回
2回
3回
4回
5回
73
88
99
100
100
63
110
390
4134
57267
処理時間(ms)
70000
60000
100
50000
80
40000
60
30000
40
20000
20
10000
0
1回
0
2回
3回
4回
5回
1回
3回
2回
4回
5回
結論


対ランダムCPUに対して先読み回数を増やす
ごとに勝率を伸ばすAIを作成できた。
しかし、処理時間が非常に時間が掛かること
がわかった。
今後の課題
処理時間が非常にかかる理由としては、アプリケーシ
ョンを作成する際に予めきちんとした設計を行ってな
かったことが挙げられる。
よって今後の課題としては、



それぞれの処理を最適化、処理時間を短縮す
ること。
より強い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-GI22 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

Download Report