完全探索データ

全探索を行った結果です。
なんか出たらとりあえず書いてってください。

	オセロ	オセロ	黒石ゲーム	黒石ゲーム	黒石ゲーム２	黒石ゲーム２
手数	最大着手可能数	全棋譜数	最大着手可能数	棋譜数	最大着手可能数	棋譜数
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
16	◎ 25	◎ 20301281202588
17	○ 26	○222743917275036
18-31
32	? 29
33	? 28
34	? 27
35	? 26
36	? 25
37	? 24
38	? 23
39	? 22
40	? 21
41	? 20
42	? 19
43	? 18
44	? 17
45	? 16
46	? 15
47	? 14
48	? 13
49	? 12
50	? 11
51	? 10
52	? 9
53	? 8
54	? 7
55	? 6
56	? 5
57	? 4
58	? 3
59	? 2
60	? 1

確認したひと
オセロ
◎ = ２人以上が確認
○ = １人が確認

黒石ゲーム
○ = 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)
• ずいぶんはやくなりましたねぇ。64bitx2って2bit/1石x64ってことですよね。たしかに。今8bit x 64でやってますので。 -- 271 (2006-03-16 01:08:34)
• 14手9時間10分・・・。ビット化したら余計に遅くなったorz。あと1～15手と31～59手の数え方、整合性が取れてないような。。上はｎ手目を打つ時の数で下はｎ手目を打った後の数ですよね？ -- 284 (2006-03-18 23:52:16)
• そういえばそうですね。修正してみました。これでいいでしょうか。 -- 256 (2006-03-19 04:25:25)
• 分散だ -- 名無しさん (2009-05-20 14:52:35)
• オセロの9手目以降、9手目で詰みになる 228 パターンが抜けてます。 -- S (2010-09-24 14:53:38)
• 同じく、10手目以降で、10手目で詰みになる 356 パターンが抜けてます。10手目では計 584 パターンが抜けてます。 -- S (2010-09-24 14:56:13)
• 添付のプログラムでは、途中で詰みになる棋譜を無視しているようです。 -- S (2010-09-24 15:13:07)
• >>S氏 途中で詰みになる棋譜数はe=で別カウントされてます。 -- 名無しさん (2010-11-18 12:59:09)
• 上の表の全棋譜数に、途中で詰みになる棋譜数を足さないと正確な値にならない。と思う -- S (2011-10-17 17:51:27)
• http://abulmo.perso.neuf.fr/perft.htm　オセロプログラムEdaxの作者による検証値等。 -- 256 (2012-10-27 01:30:59)