枝刈り


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

棋譜数のカウントを行う際、一番の問題点は、時間である。
時間短縮のため、違う盤面だがその後同じような振る舞いをする盤面を一つにまとめ
また、異なる手順で同じ盤面(Transposition)を一つにまとめる試み、
一つにまとめることでその分その後の探索が省ける。

親話題→棋譜数のカウント
親話題→終局局面数
姉妹話題→Transposition

160 名無しさん@3周年 2005/07/09(土) 01:27:15 
自分は素人ですが、真ん中に線を引いて対象的に動かしたら(鏡に写す様に)、
もう一通りの結果がわかりますよね?これってみなさんの計算のプラスになりませんでしょうか? 
無知の自分がレスってすみませんです。。。 

357 名無しさん@5周年 sage 2006/03/05(日) 22:13:08 
完全探索の話 
>>348の話を踏まえて対称形による枝刈りを一般化したらいいかな。 
対称形の盤面をみつけたときは対称形の中のひとつだけ深化して 
あとで k 倍すれば探索空間が減らせて探索がより高速になりますね。 
対称形(とその復元のための倍率 k)は 
90°回転対称(k=4), 180°回転対称/鏡面対称(k=2)、非対称(k=1) 
ですね。 
ちょっと入れてみましょう。分岐が減って速くなるか、 
あまり対称形が発生せず対称形の判定に時間がかかって逆に遅くなるか見ものです。

っていうかもうみんなやってるのかもしれない。。

358 293 sage 2006/03/05(日) 23:03:00 
>>357 
重複チェックと似てますね。ただk倍ってのは簡単にはいかない気がしますが。 
1.探索した盤面が初めてなら、探索後に分岐数と一緒にDataBaseに登録する。 
2.これから探索しようとするものと(対称形で)同じ盤面がDBにあれば、その分岐数を使う。 
ってのが実際的かな?正確には盤面の状態と黒番・白番って情報もいるけど。 

359 名無しさん@5周年 sage 2006/03/06(月) 08:28:19 
>>358 
重複チェックってやってます? 
盤面多いんで結局10手以上になるとメモリ的にDBの実装が難しいと思うんですが。 

0.深化の際に累計対称倍率Kというものを再帰関数の引数として与えることにする。 
1.0手目、K=4を引数に与えて深化開始。 
2.再帰関数中、対称形チェック。形によってその盤面の倍率 k を求める。 
3.K*k を次の再帰関数の引数に与えて深化。 
4.試合終了または深度最大になったらKの値を棋譜数カウントに加える。 
5.バックトラックの際には既に深化した分岐の対称形には手を出さない 
(たとえば、x軸鏡面対称なら盤面の半分より以東の探索をカットする) 

これでどれだけ深い階層の探索にもメモリを使わなくて済みます。 
(直系の盤面データ(最大60個)と対称倍率とバックトラック位置だけスタック領域として持てばいいので) 

361 284 sage 2006/03/06(月) 13:18:36 
>>359 
なるほど、とある盤面の対称形を使うわけですね。 
0手目(初期配置)で言えばu軸対称(k=2)、v軸対称(k=2)、180°対称(k=2)ですがk=4ですよね。 
v   | 
 \++++/ 
 ++++++ 
_++○●++_x 
 ++●○++ 
 ++++++ 
 /++++\ 
u   |y 
u軸&v軸 あるいは x軸&y軸 が成立する時は180°対称は無視する必要があります。 
また、u軸対称の時、u軸上に打てる場合もk=1になります。(v軸も同様)

366 名無しさん@5周年 sage 2006/03/07(火) 01:27:34 
対称性の話 
手数tに対して対称形がいくつ出てくるかを調べてみました。 
t=1 x= 0 y= 0 u= 1 v= 1 
t=2 x= 0 y= 0 u= 0 v= 0 
t=3 x= 0 y= 0 u= 0 v= 0 
t=4 x= 0 y= 0 u= 0 v= 4 
t=5 x= 0 y= 0 u= 4 v= 0 
t=6 x= 0 y= 0 u= 0 v= 0 
t=7 x= 0 y= 0 u= 0 v= 0 
t=8 x= 0 y= 0 u= 0 v= 60 
t=9 x= 4 y=14 u=88 v=152 
注:実装上の関係からv軸u軸に関しては>>361と比べて逆になっています。

8手目から結構でてきます。 
またこのチェックを入れたコストは9手全探索で0.2秒でした。 
入れた方がいいかもしれません。

375 名無しさん@5周年 sage 2006/03/09(木) 03:36:52 
対称性の盤面数、ちょっと計算方法が間違っていたので訂正。 
t,u, v, n 
1,1, 1, 4 
2,0, 0, 12 
3,0, 0, 56 
4,0, 1, 244 
5,1, 0, 1396 
6,0, 0, 8200 
7,0, 0, 55092 
8,0,12,390216 
t=手数、v(,u)=v(,u)軸対称な盤面数、n=全棋譜数

これなんですが、対称性を用いた枝刈りのコスト削減が 
どれだけ深い手数まで調べても1/4にしかならなかったんですよね。 
よく考えてみると、4手目にひとつ対称な盤面がでてきて、 
これ以降のこのノードの探索範囲は1/2になるんですが、 
すでに棋譜数が244もあるので、ひと枝だけがコスト1/2になっても 
全体の計算量は243/244にしかならないんですよね。 
結局うまくコスト削減できてるのは1手目のuv対称の1/4だけで、 
それ以降のはほとんど無視できちゃうんです。 
ってことで「対称性による計算量削減は1手目しか意味がない」 
というのが今日の私の結論でした。

376 284 sage 2006/03/09(木) 12:59:58 
>>375 
対称性を用いた枝狩りの有効性は低いですか。実は期待していただけに残念。 
今、黒石ゲーム2で対称性の枝狩りをやってみようかと考えてます。 
オセロの全(1/4)探索よりノードを減らせれば、各手数での最大着手可能数を探索できるかな、と考えてます。 
まあ、既に全探索で14手目最大22着手が出てるので、無駄になる可能性大、ですが。

393 284 sage 2006/03/12(日) 14:52:00 
黒石ゲーム2の完全探索を盤面対称性を考慮してやってみました。 
9手までで47分。 
|手|最大手数|手数--------|xyuv|xy---|90r--|uv---|x-----|y-----|u-----|v-----|180r--|Non------| 
|-1|------12|----------12|---1|----0|----0|----0|-----0|-----0|-----0|-----0|-----0|--------0| 
|-2|------13|---------152|---0|----0|----0|----0|-----0|-----0|-----1|-----0|-----0|--------1| 
|-3|------16|--------2048|---0|----0|----0|----1|-----2|-----1|-----2|-----1|-----1|-------12| 
|-4|------17|-------29444|---0|----0|----0|----0|-----0|-----0|----12|-----5|-----0|------198| 
|-5|------20|------451376|---2|----3|----5|----5|----38|----28|----60|----38|----24|-----2765| 
|-6|------20|-----7354680|---0|----0|----0|----0|-----0|-----0|---439|---267|-----0|----43038| 
|-7|------22|---126786952|---0|----0|----0|--221|--2143|--1779|--3196|--2307|--1692|---693109| 
|-8|------24|--2300515224|---0|----0|----0|----0|-----0|-----0|-30214|-20625|-----0|-11954263| 
|-9|------24|-43708282280|1779|-5871|-8399|-8410|164331|139821|280193|210498|128439|215800673| 
|10|------26|865297962824|----|-----|-----|-----|------|------|------|------|------|---------| 
xyuv:X軸、Y軸、U軸、V軸の4軸に同時に対称な盤面数 
xy:X軸、Y軸の2軸に対称 
90r:90度回転に対称(表現がおかしい?90度回転しても同じという意味) 
uv:U軸、V軸の2軸に対象 
x: y: u: v: 各々1つの軸にのみ対象 
180r:180度回転に対称 
Non:対称性無し 
以上は全て、排他です。

396 名無しさん@5周年 sage 2006/03/14(火) 03:31:28 
気分転換に幅優先の全探索してみました。 
手---棋譜数--盤面数-計算時間[s] 
1--------4------4----0.00 
2-------12-----12----0.00 
3-------56-----56----0.02 
4------244----240----0.02 
5-----1396---1344----0.23 
6-----8200---7572----3.31 
7----55092--47624--261.99 
データベースが1本リストなので遅いです。

397 名無しさん@5周年 sage 2006/03/15(水) 03:21:20 
t=手数,m=最大着手数,b=盤面数,ti=処理時間[s] 
t= 1, m= 4, b= 4, ti=0.02 
t= 2, m= 3, b= 12, ti=0.00 
t= 3, m= 5, b= 56, ti=0.00 
t= 4, m= 6, b= 240, ti=0.03 
t= 5, m= 9, b= 1344, ti=0.06 
t= 6, m=11, b= 7572, ti=0.31 
t= 7, m=12, b= 47624, ti=1.53 
t= 8, m=14, b= 302418, ti=15.45 
幅探索ずいぶん速くなった。 
パスのない8手までの完全な盤面。

399 よんけた ◆Tl2oC4lIZ2 sage 2006/03/16(木) 15:25:58 
>>396 
おつどす。 
トランスポジションがなかなかの勢いで増えてますね。

405 284 sage 2006/03/18(土) 18:55:54 
>>396 
幅優先ではないんだけど、盤面数を出してみたら396と少し違いました?? 
手---棋譜数--盤面数 
1--------4------4-(100%) 
2-------12-----12-(100%) 
3-------56-----56-(100%) 
4------244----236-(96.7%) 
5-----1396---1288-(92.3%) 
6-----8200---7092-(86.5%) 
盤面の反転・回転による対称性は考慮していません。 
つまり、>>274での上2つは同一、一番下は別物としてカウントしてます。 
演算量を減らすには対称性も考慮したほうがいいね。

408 284 sage 2006/03/19(日) 11:46:23 
>>405に対称性を追加しました。あんまり自信ないので誰か検証お願いします。 
手--A棋譜数-B盤面数-(B/A) 
1--------4------1-(25.0%) 
2-------12------3-(25.0%) 
3-------56-----14-(25.0%) 
4------244-----60-(24.6%) 
5-----1396----322-(23.1%) 
6-----8200---1773-(21.6%)

対称性の考慮は次の8パターン。 
1)オリジナル盤面 
2)X軸反転=上下反転 
3)Y軸反転=左右反転 
4)XY軸反転=180度回転 
4)U軸反転(右下がりをU軸としてます。>>361とはu,vが逆) 
6)V軸反転(右上がりをV軸としてます) 
7)U→X反転(U軸反転したものをX軸反転)=左90度回転 
8)U→Y反転=右90度回転 
発生した盤面が以前に出た盤面の上記8パターンのどれかに該当すれば同一、とします。

実際にそうするとデータベースが大きくなるので 
過去の盤面の上記8パターンのハッシュ値を発生させ、その中の最小値(最大値でもいいけど)を記憶。 
発生した盤面の8パターンのハッシュ値の最小値(あるいは最大値)と以前のを比べて同一性を確認してます。

プログラムでは各盤面のminhushだけ出して、エクセルでカウントしました。

409 名無しさん@5周年 2006/03/20(月) 21:43:53 
忙しくてのぞいていなかった一ヶ月ちょっとの間に 
なんだかすごいことに... 

回転と裏返しで最大8つの盤面を 
1つにまとめられることから思い付いたけど、 
白と黒が反対の盤面もまとめることができるよね?

例えば、 
++++++++ 
+●●●●●●+ 
+●○○○●●+ 
+●○○○●++ 
+●○○●●●+ 
+●○○○○●+ 
+●●●●●●+ 
++++++++ 次○が置く 
と 
++++++++ 
+○○○○○○+ 
+○●●●○○+ 
+○●●●○++ 
+○●●○○○+ 
+○●●●●○+ 
+○○○○○○+ 
++++++++ 次●が置く

は、最後の勝ち負けを反転させれば等価な局面といえる。 
これは、データベースのメモリの節約に使えないかな?

これで最大16の盤面を1つにまとめることができる。

既出だったらごめん 

412 256 sage 2006/03/20(月) 23:57:42 
>>409 
石数が同じで手番が違うのでパスが関与しなければなりません。 
その上で色違いの同局面になるということなので、 
>>274のような例よりも存在割合は格段に低いと思います。 
たしかに、わずかなメモリの節約にはなりそうです。  

413 名無しさん@5周年 sage 2006/03/21(火) 02:18:34 
対称性はうまくいっても恩恵が1/4だし気休めにしかならないような。

414 409 2006/03/21(火) 14:04:59 
>>412 
確かに・・・ 
気休め程度ですね。 

>>413 
俺も基本はtrancepositionだと思います。 
対象性も白黒の反転もささやかな後押しです。

417 284 sage New! 2006/03/22(水) 10:29:56 
>>409 
なるほど、白黒反転は面白いですね。>>412で言われてるように存在割合は少ないと思いますが、 
例えば、パスがあったときに手番を替えるのではなく盤面の白黒を反転させれば 
奇数手番は黒番、偶数手番は白番、と固定出来ますね。 
これで手番情報を残す必要がなくなるのでその分DBを減らせると思います。

・・・と、思ったけどこれだと勝ち負け情報がなくなりますね。棋譜数を数えるだけなら問題はないですが。

>>413>>414 「対称性」について私の考えを述べます。 
「対称性」には2つあります。(と言っても2つ目を「対称性」と言えるかどうか・・・) 
1)「ある盤面の対称性」 
盤面自体が線対称、回転対称に当たる場合。 
初期盤面などはこれに当たるので1/4探索などが有効ですね。 
しかし初期盤面以降はあまり発生しないようです。(>>375)

2)「ある盤面と別のある盤面の反転、回転による同一性」 
盤面Aを反転、あるいは回転すれば盤面Bになる。 
transpositionを考える時に>>274の3つめのような盤面を同一と考えるのに 
>>408のような方法でどうか、ということです。

2)の方はあくまでtranspositionを考える為ですので恩恵が1/4に固定されるものではないと思います。 
また手数が増えればtransposition自体増えて行くでしょう。 
また2)の考えを入れれば1)の盤面は次の手で2)に吸収されるので1)は考慮しなくても良いと考えます。 

2)の考え方のことを>>408で「対称性」と言ってしまったことで誤解を与えてしまったかもしれない。 
すみません。
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。