コンピュータで囲碁の解析を夢見るスレ (80ﾚｽ)
上下前次1-新
1(1): 2010/11/05(金)20:34 ID:JaVYdbjO(1/12) AAS
コンピュータでの囲碁の解析について語るスレです。
どんなアルゴリズムでどんな解析ができるか？
効率的なアルゴリズムは？
その時の計算量は？
正しいコミ（双方最善で引き分けとなるコミ）はいったいいくつか？
などを語ってください。
姉妹スレ
コンピュータで将棋の解析を夢見るスレ
2chｽﾚ:bgame
2(1): 2010/11/05(金)20:46 ID:JaVYdbjO(2/12) AAS
とりあえず非常に簡単に、普通にツリー検索で解析するプログラムを組んでみました。
ある局面に対し、勝つ手が1個見つかった時点で検索終了します。
コミを0.5から1ずつ増やし、コミ n-0.5 だと黒の勝ち、コミ n+0.5 だと白の勝ち
となるnを探します。
この時のnが正しいコミとなります。
このような単純な方法では、
打つ点が5点くらいまでなら結果（正しいコミ）がすぐ求まります。
ルールは純碁と（終盤を省略しない）中国ルール。
日本ルールでのプログラムは難しいので頭で考えた参考値です。
それぞれ正しいコミを結果として載せます。
省3
3(1): 2010/11/05(金)20:51 ID:JaVYdbjO(3/12) AAS
--- △ ---
打つ場所が3点で、すべての点が繋がっている盤面
{{a,b},{a,c},{b,c}} // a,b,cの3点と、a-b, a-c, b-c の3本の線からなる盤を表します
純碁：0
中国ルール：0
日本ルール：(0)
--- □ ---
2路盤
{{a,b},{a,c},{b,d},{c,d}}
純碁：1
省8
4(1): 2010/11/05(金)20:55 ID:JaVYdbjO(4/12) AAS
--- 五角形 ---
五角形
{{a,b},{a,c},{b,d},{c,e},{d,e}}
純碁：0
中国ルール：0
日本ルール：(0)
--- △_ ---
{{a,b},{a,c},{a,d},{b,c}}
純碁：2
中国ルール：4
省6
5(1): 2010/11/05(金)21:05 ID:JaVYdbjO(5/12) AAS
単純に結果だけ書いても面白くないので解説
--- 2路盤 ---
┌┐ ●┐ ●┐ ●● ┌┐ ┌● ○┐ ┌● ┌● ●●
└┘ └┘ └○ └○ ○○ ○○ ○○ └┘ ○┘ ○┘
┌┐ ●┐ ●┐ ●● ┌┐ ┌● ┌● ●●
└┘ └┘ └○ └○ ○○ ○○ ○○ ○┘
純碁や中国ルールでは、取ったり取られたりが続くが、
最終的には白が同一盤面禁止の超コウルールに引っかかって取れなくなって
そこで終局。
日本ルールは、どちらも活き石が作れないので、
省10
6(1): 2010/11/05(金)21:08 ID:JaVYdbjO(6/12) AAS
--- 五角形 ---
純碁や中国ルールでは、取ったり取られたりが非常に長く続くが、
最終的には超コウルールにより打てなくなってジゴ
日本ルールでは、2路盤と同様に双方とも活き石が作れずジゴ
7(1): 2010/11/05(金)21:22 ID:JaVYdbjO(7/12) AAS
19路盤囲碁の盤面の組み合わせは、
点の状態のすべての組み合わせ3^361 のに対して、黒の存在出来ない石をすべて取り除いた盤面にカウントするとした場合、
最大2^181回重複して数える盤面が出てくる。
よって、
3^361 / 2^181 ＜ 盤面総数 ＜ 3^361
となる。
計算すると、
『 5.67*10^117 ＜ 盤面総数 ＜ 1.75*10^172 』
日本ルールの囲碁の場合、同型反復の制限が無い為、厳密には有限ゲームではないが、
同一の [手番、盤面、ハマ差、コウによる着手禁止点] になった時点で同型反復による引き分け
省9
8: 2010/11/05(金)21:34 ID:JaVYdbjO(8/12) AAS
日本ルールの場合、
それまでの手順に関係無く、
[手番、盤面、ハマ差、コウによる着手禁止点]
による最善手が決まる。
よって、総ゲーム数 10^10^178.67 近くあるすべての解析を行う必要は無く、
[手番、盤面、ハマ差、コウによる着手禁止点] による遷移図（ゲームグラフ）を作成することで、
解析することが出来るので、
1.83*10^178 程度の局面の解析で済む。
ただし、終局局面から正しい点数計算を行うアルゴリズムは簡単ではなく、
膨大な計算が必要な局面も存在する。
省9
9(1): 2010/11/05(金)21:59 ID:JaVYdbjO(9/12) AAS
●コミとゲーム開始時の形勢の関係
すべての終局局面でのコミと形勢の関係は[a] [b]のいずれかである....☆1
（通常の終局の場合は[a], 同型反復終局の場合は[b]）
[a]〜[e]の形の関数複数個のmax, min関数は[a]〜[e]の形となる....☆2
コミが十分大きければ白必勝、コミが十分小さければ黒必勝である ....☆3
以上より、コミとゲーム開始時の形勢の関係は[a],[c]のいずれかとなる。
[a]
. ／
／
[b]
省12
10(1): 2010/11/05(金)22:28 ID:JaVYdbjO(10/12) AAS
>>2-6 の純碁は超コウルール有りの場合です。
（単純なコウ以外で）同一盤面となる石打ちを行った場合に引き分けのルールとする場合は
結果が異なります。
たとえば、2路盤はどちらも一方的に同型反復の形に持ち込めますので、結果は0になります。
>>5
なんか微妙に1手抜けましたね。訂正。
┌┐ ●┐ ●┐ ●● ┌┐ ┌● ┌● ●● ●●
└┘ └┘ └○ └○ ○○ ○○ ○○ └┘ ○┘
11: 2010/11/05(金)22:37 ID:JaVYdbjO(11/12) AAS
>>10
> たとえば、2路盤はどちらも一方的に同型反復の形に持ち込めますので、結果は0になります。
すみません。これ嘘です。
正しいコミは、-2 〜 +2 の範囲です。
この範囲すべてで、双方最善で引き分けです。
>>9 でいう[c] の形です。
12: 2010/11/05(金)22:44 ID:JaVYdbjO(12/12) AAS
--- □ ---
2路盤
{{a,b},{a,c},{b,d},{c,d}}
純碁（超コウ無し）：-2 〜 2
純碁（超コウ有り）：1
中国ルール（超コウ無し）：-4 〜 4
中国ルール（超コウ有り）：1
日本ルール：(0)
13: 2010/11/12(金)22:13 ID:xJrT1Vgr(1) AAS
19路盤の盤面総数の組み合わせの範囲をもうちょっと絞りました。
10^167.3 ＜ 盤面総数 ＜ 10^172.2
3^361 のうち、存在出来ない石が存在しない割合はそれほど低く無いようです。
頑張ればもっと絞れそうです。
14: 2010/11/18(木)18:42 ID:925DBQem(1/2) AAS
もうちょっと絞ってみました。
10^169.958 < [19路盤 盤面総数] < 10^170.482
10^169.055 < [19路盤 盤面総数 対称形同一視] < 10^169.579
10^168.754 < [19路盤 盤面総数 対称形同一視 白黒同一視] < 10^169.278
[1路盤 盤面総数] = 1 = 10^0
[2路盤 盤面総数] = 57 ≒ 10^1.756
[3路盤 盤面総数] = 12675 ≒ 10^4.103
[4路盤 盤面総数] = 24318165 ≒ 10^7.386
[5路盤 盤面総数] = 414295148741 ≒ 10^11.617
[6路盤 盤面総数] = 62567386502084877 ≒ 10^16.796
省14
15: 2010/11/18(木)23:25 ID:925DBQem(2/2) AAS
5路盤〜10路盤の挟み込みの予想と実際の値との関係から、
以下の範囲に入ることはほぼ確実。
10^170.31856 < [19路盤 盤面総数] < 10^170.31892
16(1): 2010/11/26(金)18:56 ID:U5HnVghy(1) AAS
11路盤の正確な盤面総数が求まりました。
[11路盤 盤面総数] = 793474866816582266820936671790189132321673383112185151899 ≒ 10^56.900
17: 2010/12/14(火)01:26 ID:qfdZYx1+(1/2) AAS
sage
18: 2010/12/14(火)01:28 ID:qfdZYx1+(2/2) AAS
(;GM[1]FF[4]CA[UTF-8]AP[CGoban:3]ST[2]
RU[Japanese]SZ[19]KM[6.50]
PW[白]PB[黒]
;B[dd];W[pd];B[dp];W[pp];B[jd];W[cc];B[cd];W[dc];B[ec];W[eb];B[fb]
;W[fc];B[ed];W[gb];B[db];W[fa];B[cb])
19(1): 2011/03/05(土)22:40 ID:Sq2vs+jo(1) AAS
>>16は呼吸点のない石が置けないのを知らないのか
そんなに簡単に計算できるわけないだろう
20: 2011/03/05(土)22:59 ID:eSNNg1+M(1) AAS
>>19
もちろん考慮してる。
Corei7で一週間位はかかってる。
普通に計算したらこの桁数だから当然計算は終わらない。
すごく工夫してこの計算時間。
計算方法は今のことろ公開はしていないが、
どうしてもというならヒントくらいは出す。
上下前次1-新書関写板覧索設栞歴
あと 60 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.553s*