オセロ局面・非局面である証明

オセロ局面・非局面である証明

その盤面がオセロ局面である証明は幾分易しい。その盤面に至る棋譜を提示すればよい。
逆に非局面である証明は難しい。ありえない局面にある条件があればその盤面は非局面であるが、
条件が入ってないからといって非局面とは限らない。
この場合、今のところ一手づつ戻して逆ゲーム木なるものを完全に作成し、初期局面がその木に入っていないのを
確認しなければいけない。

親話題→ありえない局面

---

504 256 sage 2006/05/06(土) 14:03:33 
>>501-502 
初期配置まで盤面を戻すプログラムを作ってみました。 
全部埋まった状態から初期配置まで戻すのは難しいようです。 
多くのありえる局面を戻すのは今のところ１５～２５手くらいが限度のようで、 
それ以上はいつ終わるか分からないような状態です。 
>>257、>>263、>>314の２個目、>>455、>>479などは、 
ありえない局面で、数秒以内に結果が出ました。 
その他は259、314の１個目、475、489、490などは、 
なかなか終わらなかったので途中でやめました。 
戻すのに掛かる時間は局面依存がかなり強いようです。 
例えば、１６手打ったある局面は１分くらいで解けたのに、 
そこから１手進めた１７手の局面は３時間４０分くらい掛かったり。 
多分パスがあると急激に処理時間が多くなるようです。 

505 よんけた ◆Tl2oC4lIZ2 sage 2006/05/07(日) 02:24:47 
６４マス埋まっている盤面の話で 
>>501-502みたいに 
直前可能盤面数を算出したんですが 
すべてオール黒の場合　153705 通りありました。  

オール黒、オール白は実戦的に凄いというイメージがありますが、 
数ある盤面の中で一番多く棋譜を含んでいる盤面なのかもしれません。 
つまり、それだけ到達しやすい盤面なのかもしれません。 

506 よんけた ◆Tl2oC4lIZ2 sage 2006/05/07(日) 02:32:24 
>>すべてオール黒。。。。orz 

507 256 sage 2006/05/07(日) 06:21:25 
>>505 
＞すべてオール黒の場合　153705 通りありました。 
これどうやって求めました？ 
プログラムを作って数えてみたんですけど、 
91648とかって数字がでてきました。 
実装が間違ってるのかな・・・。 

508 284 sage 2006/05/07(日) 11:27:40 
>>504 
ありえない局面でなかなか結果が出なかったものは盤面の一部がありえない配置のものが多いですね。 
ありえない配置以外の石は局面を遡れてしまうのでなかなか結果が出ないのだと思われます。 
それと、速度ＵＰには最善手探索のときのαβ法のような上手い枝狩りを考える必要があるでしょうね。 

>>505-507 
オール黒の直前可能盤面数を計算で出して見ました。 
直前手がA1（隅）の場合、右、下、右下方向それぞれ返せる石の数は０～６の７通り。 
全て返さない場合は直前盤面にならないので総数は「７×７×７－１」となる。 
A1＝(7×7×7-1)×4＝1368 
隅は４箇所あるので４倍しています。以下同様に 
B1＝(6×6×7-1)×8＝2008 
C1＝(5×5×7×2×2-1)×8＝5592 
D1＝(4×4×7×3×3-1)×8＝8056 
B2＝(6×6×6-1)×4＝860 
C2＝(5×5×6×2×2-1)×8＝4792 
D2＝(4×4×6×3×3-1)×8＝6904 
C3＝(5×5×5×2×2×2×2×2-1)×4＝15996 
D3＝(4×4×5×3×3×2×2×2-1)×8＝46072 
トータルは91,648になりました。 

509 よんけた ◆Tl2oC4lIZ2 sage 2006/05/08(月) 01:18:48 
>>508 
やっと　91648　に会いました。真ん中４つを入れたり、符号が抜けてたりしてました。精進。 

510 284 sage 2006/05/09(火) 18:06:12 
>>505 
＞オール黒、オール白は実戦的に凄いというイメージがありますが、 
＞数ある盤面の中で一番多く棋譜を含んでいる盤面なのかもしれません。 
一番多く棋譜を含んでる、かどうかは現時点で証明出来ませんが508で書いた式を考えると 
「91,648は、ある盤面の直前可能盤面数の上界」であり、また 
「直前可能盤面数が最大(91,648)となるのはオール黒とオール白の２盤面のみ」 
という事は言えますね。 [[@wikiへ>http://kam.jp"><META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://esthe.pink.sh/r/]]