「枝刈り」の編集履歴（バックアップ）一覧に戻る
枝刈り - (2006/03/27 (月) 15:30:25) のソース
*枝刈り
[[棋譜数のカウント]]の一番の問題点は、時間である。
時間短縮のため、違う盤面だがその後同じような振る舞いをする盤面を一つにまとめる試み
親話題→[[棋譜数のカウント]]
親話題→[[終局局面数]]
姉妹話題→[[Transposition]]
----
160 名無しさん＠３周年 2005/07/09(土) 01:27:15
自分は素人ですが、真ん中に線を引いて対象的に動かしたら(鏡に写す様に)、
もう一通りの結果がわかりますよね？これってみなさんの計算のプラスになりませんでしょうか？
無知の自分がレスってすみませんです。。。
357 名無しさん＠５周年 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倍ってのは簡単にはいかない気がしますが。
１．探索した盤面が初めてなら、探索後に分岐数と一緒にDataBaseに登録する。
２．これから探索しようとするものと(対称形で)同じ盤面がDBにあれば、その分岐数を使う。
ってのが実際的かな？正確には盤面の状態と黒番・白番って情報もいるけど。
359 名無しさん＠５周年 sage 2006/03/06(月) 08:28:19
>>358
重複チェックってやってます？
盤面多いんで結局10手以上になるとメモリ的にDBの実装が難しいと思うんですが。
０．深化の際に累計対称倍率Kというものを再帰関数の引数として与えることにする。
１．0手目、K=4を引数に与えて深化開始。
２．再帰関数中、対称形チェック。形によってその盤面の倍率 k を求める。
３．K*k を次の再帰関数の引数に与えて深化。
４．試合終了または深度最大になったらKの値を棋譜数カウントに加える。
５．バックトラックの際には既に深化した分岐の対称形には手を出さない
（たとえば、x軸鏡面対称なら盤面の半分より以東の探索をカットする）
これでどれだけ深い階層の探索にもメモリを使わなくて済みます。
（直系の盤面データ(最大60個)と対称倍率とバックトラック位置だけスタック領域として持てばいいので）
361 284 sage 2006/03/06(月) 13:18:36
>>359
なるほど、とある盤面の対称形を使うわけですね。
０手目（初期配置）で言えばｕ軸対称(k=2)、ｖ軸対称(k=2)、180°対称(k=2)ですがk=4ですよね。
ｖ |
＼＋＋＋＋／
＋＋＋＋＋＋
＿＋＋○●＋＋＿ｘ
＋＋●○＋＋
＋＋＋＋＋＋
／＋＋＋＋＼
ｕ |ｙ
ｕ軸＆ｖ軸 あるいは ｘ軸＆ｙ軸 が成立する時は180°対称は無視する必要があります。
また、ｕ軸対称の時、ｕ軸上に打てる場合もk=1になります。（ｖ軸も同様）
366 名無しさん＠５周年 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 名無しさん＠５周年 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にしかならないんですよね。
結局うまくコスト削減できてるのは１手目のuv対称の1/4だけで、
それ以降のはほとんど無視できちゃうんです。
ってことで「対称性による計算量削減は１手目しか意味がない」
というのが今日の私の結論でした。
376 284 sage 2006/03/09(木) 12:59:58
>>375
対称性を用いた枝狩りの有効性は低いですか。実は期待していただけに残念。
今、黒石ゲーム２で対称性の枝狩りをやってみようかと考えてます。
オセロの全(1/4)探索よりノードを減らせれば、各手数での最大着手可能数を探索できるかな、と考えてます。
まあ、既に全探索で14手目最大22着手が出てるので、無駄になる可能性大、ですが。
393 284 sage 2006/03/12(日) 14:52:00
黒石ゲーム２の完全探索を盤面対称性を考慮してやってみました。
９手までで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：Ｘ軸、Ｙ軸、Ｕ軸、Ｖ軸の４軸に同時に対称な盤面数
xy：Ｘ軸、Ｙ軸の２軸に対称
90r：90度回転に対称（表現がおかしい？90度回転しても同じという意味）
uv：Ｕ軸、Ｖ軸の２軸に対象
x： y： u： v： 各々１つの軸にのみ対象
180r：180度回転に対称
Non：対称性無し
以上は全て、排他です。
396 名無しさん＠５周年 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
データベースが１本リストなので遅いです。
397 名無しさん＠５周年 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での上２つは同一、一番下は別物としてカウントしてます。
演算量を減らすには対称性も考慮したほうがいいね。
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%)
対称性の考慮は次の８パターン。
1)オリジナル盤面
2)Ｘ軸反転＝上下反転
3)Ｙ軸反転＝左右反転
4)ＸＹ軸反転＝180度回転
4)Ｕ軸反転（右下がりをＵ軸としてます。>>361とはu,vが逆）
6)Ｖ軸反転（右上がりをＶ軸としてます）
7)Ｕ→Ｘ反転（Ｕ軸反転したものをＸ軸反転）＝左90度回転
8)Ｕ→Ｙ反転＝右90度回転
発生した盤面が以前に出た盤面の上記８パターンのどれかに該当すれば同一、とします。
実際にそうするとデータベースが大きくなるので
過去の盤面の上記８パターンのハッシュ値を発生させ、その中の最小値（最大値でもいいけど）を記憶。
発生した盤面の８パターンのハッシュ値の最小値（あるいは最大値）と以前のを比べて同一性を確認してます。
プログラムでは各盤面のminhushだけ出して、エクセルでカウントしました。
409 名無しさん＠５周年 2006/03/20(月) 21:43:53
忙しくてのぞいていなかった一ヶ月ちょっとの間に
なんだかすごいことに...
回転と裏返しで最大8つの盤面を
1つにまとめられることから思い付いたけど、
白と黒が反対の盤面もまとめることができるよね？
例えば、
＋＋＋＋＋＋＋＋
＋●●●●●●＋
＋●○○○●●＋
＋●○○○●＋＋
＋●○○●●●＋
＋●○○○○●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋ 次○が置く
と
＋＋＋＋＋＋＋＋
＋○○○○○○＋
＋○●●●○○＋
＋○●●●○＋＋
＋○●●○○○＋
＋○●●●●○＋
＋○○○○○○＋
＋＋＋＋＋＋＋＋ 次●が置く
は、最後の勝ち負けを反転させれば等価な局面といえる。
これは、データベースのメモリの節約に使えないかな？
これで最大16の盤面を1つにまとめることができる。
既出だったらごめん
412 256 sage 2006/03/20(月) 23:57:42
>>409
石数が同じで手番が違うのでパスが関与しなければなりません。
その上で色違いの同局面になるということなので、
>>274のような例よりも存在割合は格段に低いと思います。
たしかに、わずかなメモリの節約にはなりそうです。
413 名無しさん＠５周年 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で言われてるように存在割合は少ないと思いますが、
例えば、パスがあったときに手番を替えるのではなく盤面の白黒を反転させれば
奇数手番は黒番、偶数手番は白番、と固定出来ますね。
これで手番情報を残す必要がなくなるのでその分ＤＢを減らせると思います。
・・・と、思ったけどこれだと勝ち負け情報がなくなりますね。棋譜数を数えるだけなら問題はないですが。
>>413>>414 「対称性」について私の考えを述べます。
「対称性」には２つあります。（と言っても２つ目を「対称性」と言えるかどうか・・・）
1)「ある盤面の対称性」
盤面自体が線対称、回転対称に当たる場合。
初期盤面などはこれに当たるので1/4探索などが有効ですね。
しかし初期盤面以降はあまり発生しないようです。(>>375)
2)「ある盤面と別のある盤面の反転、回転による同一性」
盤面Ａを反転、あるいは回転すれば盤面Ｂになる。
transpositionを考える時に>>274の３つめのような盤面を同一と考えるのに
>>408のような方法でどうか、ということです。
2)の方はあくまでtranspositionを考える為ですので恩恵が1/4に固定されるものではないと思います。
また手数が増えればtransposition自体増えて行くでしょう。
また2)の考えを入れれば1)の盤面は次の手で2)に吸収されるので1)は考慮しなくても良いと考えます。
2)の考え方のことを>>408で「対称性」と言ってしまったことで誤解を与えてしまったかもしれない。
すみません。
