「完全探索データ」の編集履歴（バックアップ）一覧に戻る
完全探索データ - (2006/03/15 (水) 18:26:05) の編集履歴(バックアップ)
全探索を行った結果です。
なんか出たらとりあえず書いてってください。
|
オセロ |
オセロ |
黒石ゲーム |
黒石ゲーム |
黒石ゲーム２ |
黒石ゲーム２ |
| 手数 |
最大着手可能数 |
全棋譜数 |
最大着手可能数 |
棋譜数 |
最大着手可能数 |
棋譜数 |
| 1 |
◎ 4 |
◎ 4 |
○ 12 |
○ 12 |
◎ 12 |
◎ 12 |
| 2 |
◎ 3 |
◎ 12 |
○ 16 |
○ 176 |
◎ 13 |
◎ 152 |
| 3 |
◎ 5 |
◎ 56 |
○ 20 |
○ 3008 |
◎ 16 |
◎ 2048 |
| 4 |
◎ 6 |
◎ 244 |
○ 24 |
○ 57876 |
◎ 17 |
◎ 29444 |
| 5 |
◎ 9 |
◎ 1396 |
○ 28 |
○ 1223480 |
◎ 20 |
◎ 451376 |
| 6 |
◎ 11 |
◎ 8200 |
○ 32 |
○ 27927528 |
◎ 20 |
◎ 7354680 |
| 7 |
◎ 12 |
◎ 55092 |
○ 36 |
○ 679519480 |
◎ 22 |
◎ 126786952 |
| 8 |
◎ 14 |
◎ 390216 |
|
|
◎ 24 |
◎ 2300515224 |
| 9 |
◎ 15 |
◎ 3005320 |
|
|
○ 24 |
○ 43708282280 |
| 10 |
◎ 16 |
◎ 24571192 |
|
|
○ 26 |
○865297962824 |
| 11 |
◎ 18 |
◎ 212260296 |
|
|
|
|
| 12 |
◎ 20 |
◎ 1939892240 |
|
|
|
|
| 13 |
◎ 21 |
◎ 18429768516 |
|
|
|
|
| 14 |
◎ 22 |
◎ 184042835408 |
|
|
|
|
| 15 |
○ 23 |
○ 1891844432704 |
|
|
|
|
確認したひと
オセロ
◎ = 260 & 271 & 293 が確認
○ = 260 & 293 が確認
黒石ゲーム
○ = 271 & 293 が確認
黒石ゲーム２
◎ = 271 & 293 & 284 が確認
○ = 284 が確認
コメントフォーム、下に異動しました
- 黒石ゲーム
- ８ｘ８に１つずつ黒石を置いていくゲーム。隣８つのどれかに既に黒石がある空マスにだけ置けるとする。このゲームの全棋譜はオセロの全棋譜含む。全局面はオセロのそれを含まない（石の色があるので）。初期状態は真ん中に２ｘ２の黒石があるとする。278 初出。
- 黒石ゲーム２
- 黒石ゲームに、「２連続（以上）の黒石の延長上にのみ置ける」という制約を付加したもの。全棋譜も全局面も黒石ゲームのそれを含む。326(=284) 初出。
- 手数の数えかた
- 始めに置く黒石を１手目とし、ｎ手目が終わったあとの局面に関して、それを「ｎ手後の局面」と呼ぶことにする。つまり、ｎは（盤面に置かれている石の数＋４）と一致する。このページの表の「手数」は「ｎ手後」の棋譜や局面に関する情報であるとしておこう。
- パス[pass]の数えかた
- パスは１手に入らないとする。つまり、ｍ手目の手が先攻であり、次に後攻がパスをしたら、ｍ＋１手目の手は先攻にあたる。つまり、パスの回数にかかわらず、ｎは（ｎ手後の盤面に置かれている石の数＋４）に常に一致する。（この考え方は、棋譜を「ゲーム内の分岐点における参加者の選択の履歴」と捉えて、自動的に決定されてしまう分岐点にあたらない pass は棋譜に入れないというポリシーの基で定義しようとしたんだけどそう言いかけると最大着手数１手の時の着手は結局選択権がないではないかと言われそうで怖いがそこまで手を焼くと意味無く煩雑になるだけだしまぁそのへんは適当でいいや）
- 確認したひと
- ２人以上が確認できたかのチェックに使います。お名前をどうぞ。まぁ２人以上一致したならだいたいOKかと。同じ人間なんだから似たよなバグをはらんで一致してしまう可能性があるじゃないかと言われるかもしれないけど、それはその都度議論するしかないんじゃないかな。。。
計算時間のめやす
備考:
- うげ。黒石ゲーム２の手数８、unsigned long int の範囲を超えたのか負になってしまいますた…。変換したら誤差なく正しい値分かると思うんだけど。。 -- 271 (2006-03-02 04:18:39)
- オセロの２手目の最大着手可能数は３じゃないの？ -- 284 (2006-03-02 11:43:01)
- あ、2手目「まで」の最大着手数なので1手目も含まれて3より4の方が大きいから4ってなってるんですよ。情報量へっちゃってますね。その手数のときの最大着手数を書くほうがいいですね。また計算しなおして変更します。 -- 一番上の人 (2006-03-03 23:38:13)
- 完全探索のC言語プログラムをアップしてみますた。結構基本に忠実と思う。 -- 271 (2006-03-11 04:03:36)
- オセロ12手で104分、黒石ゲーム7手で60分くらいですた (271)
- 同じく、オセロ12手で107分でした。1手増やす毎に8～9倍といった感覚です。次は半日かけて13手探索します。(293)
- ということはだいたいアルゴリズム同じですねｗ366の対称性の枝刈り方を入れたら全ての探索が約1/4の時間でできました。13手全探索4Hです。普通にやると16Hかかります。ただ32bitを超えてしまって値がおかしくなってるのでまた後日トライします…。(271)
- 「1手増やす毎に8～9倍といった感覚です。」←これ、単純にノード数に比例してるんじゃないでしょうか？
- そのようです。(15手目までの総ノード数)/(14手目までの総ノード数)=2096497220896/204652788192=10.244 で、(15手目の探索時間)/(14手目の探索時間)=125471.130/13012.460=9.642 なので。(293)
- 盤面情報を1次元配列にしたら12手104分→10分になりました。もしかして14～15手の高速化のこつはこれですかね？(271)
- コメントを上とマージしてみました(271)
- あとプログラムv05を改良してv06をアップしました。配列を１次元化して無駄な最適化を省いたら、すっげ素直な探索をするようになりました。でもうちでは最速・・・(271)
- オセロ盤面を符号無し64bit整数2個で表現したら13手で21分くらいでした。盤面をコピーするコストが大幅に削減できたようです。 -- 256 (2006-03-14 00:10:46)
- もうちょっと高速化しました。12手128秒→72秒。 -- 256 (2006-03-15 08:15:47)
- 黒石ゲーム２の８手目、2^32-1994452072 =2300515224で>>393と同じになるので修正します。 -- 284 (2006-03-15 18:26:05)
