プログラムなどを使って
一つ一つ辿って手の数(棋譜数)を数えていく。
当スレッドの主軸となる話題である。
棋譜のツリーを一手目からたどっていく探索とよばれる方法が主に使われる。
問題点はなんといっても時間である。
今のところ個人活動では、16手が最高である。
棋譜数の上界を下げるに貢献。
基本アルゴリズムの解説を一番下に載せました [New!]
63 名無しさん＠３周年 05/01/22 20:52:17
3^(8*8)通りです
67 名無しさん＠３周年 05/02/09 08:31:06
単純な状態空間なら>>63より遥かに小さいのだが、
プランニングを考えるとなると打つ場所の履歴を保存しなきゃならんわけで、
その場合の数はめちゃくちゃに膨れ上がる。
オセロだと10^60通り程度、チェスだと10^120通り程度、
将棋だと10^220通り程度、囲碁だと10^360通り程度、
と、この手の研究をやってる人は言ってる。
ちなみに今のコンピュータではオセロでも完全解析は全然無理。
それでもオセロに関してはコンピュータは人間より遥かに強い。
チェスは、有名だと思うけど、
IBMがdeep blueっていうそれ専用のコンピュータを作ってようやくチャンピオンに勝った。
（但し、他の人には対応できないし、数回の対局の合間にプログラマが手を入れたりしていた。
短時間で完璧にアルゴリズムを弄る腕は素晴しいが・・・。）
将棋はやっとアマチュア5段に達するかどうかというところ。
囲碁は・・・だめぽ。
118 名無しさん＠３周年 2005/05/13(金) 21:20:12
計算始めました。
死ぬまでに結果が出たらいいのだが。
119 名無しさん＠３周年 2005/05/13(金) 23:55:29
>>118
まさかとは思うが全通り計算してるのか？
122 名無しさん＠３周年 2005/05/14(土) 23:06:42
>>118
おまいが死ぬ前にパソコムが昇天するに３０００ガバス
124 名無しさん＠３周年 sage 2005/05/15(日) 06:49:03
>>67
オセロでも地球上の全ての物質を素粒子メモリーに変換したとしても間に合わんのね。
チェス以降だと宇宙の全素粒子を使用しても記録できない、と。
141 名無しさん＠３周年 2005/06/29(水) 10:01:44
で、結局全局面は何通りあるの？
>>124
1局面100バイトとして、89,475,692,478,931,200バイト
1000で考えて89ペタ。
1テラ=1000円レベルでコスト的にも不可能じゃなくなる
148 名無しさん＠３周年 2005/06/30(木) 13:05:25
ねえ何か思いついたから聞いて。プログラミングの素人ですが。。
まず、一局目から始まり、最後まで勝負つくまでの全通りはツリー状でイメージできるよね。
んで全通りの計算方法なんだけど
まず適当に勝負つくまで局を進ませる。一局一局の手は記憶させておく。
んで次に最後の一手が他に無いか探す(特殊な場合以外最後は一通りだけど)。
最後の一手が他に無かったら、最後の一手の情報を消す。
最後の一手の情報を消すごとにカウントを一つ増やす。
一手戻り最後から二手目が他に手がないか探す。
あったら、局を進ませる。
以下つづける。。。
この方法だと今カウントしている属のみの手を記憶してればいいから容量がなくてもいいんじゃない？
149 名無しさん＠３周年 sage 2005/06/30(木) 14:30:06
深さ優先探索だね。まぁ確かに容量は無くてもいけるかも知れんが、やってみ？
先に結論を言っておくと時間が足りない。4×4で実験してみてどれくらい時間がかかるか報告よろしく
150 名無しさん＠３周年 sage 2005/06/30(木) 18:56:14
でもこれで容量の問題は解決するよね？
かなり説明は省いたけど。
時間短縮は途中十局目ぐらいまで横ローラー探索をして、そのあとその結果をネットに載っける。
んで個々のPCがそれぞれの通りから縦探索をすればかなり時間短縮になるのでは？
151 名無しさん＠３周年 2005/06/30(木) 20:00:09
これは面白くなってきたな。
呼びかけるか？
152 名無しさん＠３周年 sage 2005/06/30(木) 20:52:45
へへーん。もしかして俺凄い？(・∀・)
世界的にもまだ算出されていないんでしょ？
数年掛かりでもヤる価値はあると思うよね。。
8ヶ月経過
260 256 2006/02/20(月) 07:59:34
プログラムを作って実際の数を調べてみた。
1・・・4
2・・・12
3・・・56
4・・・244
5・・・1396
6・・・8200
7・・・55092
8・・・390216
9・・・3005320
10・・・24571192
24571192*33*33*...*33*32*...*3*2*1=1.39e+70
急ごしらえなのであんまり速くないからとりあえず10手まで。
あと、まだバグがあるかも知れないから誰か検証お願い。
332 293 sage 2006/03/02(木) 17:58:43
全探索（11手まで）してみたら>>260と微妙に違ってた。
[ 0] -> 1( 0)
[ 1] -> 4( 0)
[ 2] -> 12( 0)
[ 3] -> 56( 0)
[ 4] -> 244( 0)
[ 5] -> 1396( 0)
[ 6] -> 8200( 0)
[ 7] -> 55092( 0)
[ 8] -> 390216( 0)
[ 9] -> 3005320(228)
[10] -> 24571192(356)
[11] -> 212260296(6384)
括弧内はゲーム終了数（内数）。9手目でのゲーム終了数分を足すと10手目も同じなんだけど…
Wikiにある11手目のデータも9手目・10手目での終了分を足せば同じ結果に。
…私が悪いの？
333 293 sage 2006/03/02(木) 21:51:00
12手まで出したついでによんけたﾀﾝの分岐平均（どうやって出したの？）と比較してみた
手数平均分岐←の積実際の数誤差[%]
11440
2312120
34.664555561.785714286
44.36062392442.049180328
55.8582140013960.286532951
65.8361817082000.365853659
76.723554930550920.294053583
86.94363814113902162.256442586
97.5566288217030053204.097733353
107.900522770584245711927.328126368
118.376819074462821226029610.13645435
128.7781674356344193989224013.68817765
平均分岐数を単純に掛け合わせるのは危険っぽい。
334 293 sage 2006/03/02(木) 21:51:40
ごめん>>333じゃ読めないね。Wikiに入れておく。
336 284 sage 2006/03/03(金) 08:02:23
12手の全検索、というか1/4検索です。
初手は１手固定にして、全棋譜数、パス、終了数は結果を４倍しています。
|手|最大手数| 全棋譜数 |パス |終了 |
|-1|-------0|---------------4|-------0|-----0|
|-2|-------3|--------------12|-------0|-----0|
|-3|-------5|--------------56|-------8|-----0|
|-4|-------6|-------------244|-------0|-----0|
|-5|-------9|------------1396|-------0|-----0|
|-6|------11|------------8200|-------0|-----0|
|-7|------12|-----------55092|-------0|-----0|
|-8|------14|----------390216|-------0|-----0|
|-9|------15|---------3005320|------24|-----0|
|10|------16|--------24571192|-----228|---228|
|11|------18|-------212260296|-----932|---356|
|12|------20|------1939892240|----7396|--6384|
ゲーム終了の考え方は>>332に近いですが
10手目が打てない場合に10手目の終了としています。
(332とは１手ずれる）
実は一晩かけて13手目までやったんですが結果がおかしいです。
変数は８バイト用意しておいたんですが、出力をミスったかもしれない。
|13|------21|------1249899332|---35588|-16384|
337 293 sage 2006/03/03(金) 09:10:51
ちょっと遅れたかな。一応こちらも13手探索終了
64bit整数を使ったつもりなので出力は大丈夫なはずです。
|手| 全棋譜数 |終了 |
|-1|---------------4|-------0|
|-2|--------------12|-------0|
|-3|--------------56|-------8|
|-4|-------------244|-------0|
|-5|------------1396|-------0|
|-6|------------8200|-------0|
|-7|-----------55092|-------0|
|-8|----------390216|-------0|
|-9|---------3005320|-----228|
|10|--------24571192|-----356|
|11|-------212260296|----6384|
|12|------1939892240|---16384|
|13|-----18429768516|--299624|
ゲーム終了の考え方は10手目を打った後に両者が置けなくなったら10手目の終了としています。
確かに変ですね。改良します。
338 284 sage 2006/03/03(金) 10:15:20
>>337
乙です。12手目まで一致してますので安心しました。
ゲーム終了の考え方は336と337(332初出)のどちらが良いでしょう？
私の場合(336)はプログラミングの都合だけだったので、他の皆さんの意見も聞きたいです。
>>333-335手数平均の積と実数の誤差ですが
これは平均の算出誤差というより手法としての誤差でしょうね。
全検索で手数平均を算出しても同じくらいの誤差があるでしょう。
１２手で１４％の誤差で、手が進むにつれて誤差は大きくなるでしょうし
平均１０手で２０％の誤差があるとして0.8^(60/10)=0.26
６０手目で９９％（実数との割合が１００倍違う）としても
10^51～10^56くらいではないでしょうか。（もう少し大きくなるかもしれないが）
まあ、これくらいざっくりした数値でしかないのは確かですが、無意味な値ではないと思います。
339 284 sage 2006/03/03(金) 11:28:43
ごめん。>>336の表の３手目のパスの値 8 は 0 が正解です。
（動作チェックルーチンの消し忘れ）
>>337も表はコピペみたいだから３手目の終了は0ですね。
すみませんでした。
340 293 sage 2006/03/03(金) 14:04:32
さらに進めて14手探索しました。>>336と同じく1/4探索ですが。
|手|分|--全棋譜数--|--パス-|--終了-|
|-1|-0|-----------4|------0|------0|
|-2|-3|----------12|------0|------0|
|-3|-5|----------56|------0|------0|
|-4|-6|---------244|------0|------0|
|-5|-9|--------1396|------0|------0|
|-6|11|--------8200|------0|------0|
|-7|12|-------55092|------0|------0|
|-8|14|------390216|------0|------0|
|-9|15|-----3005320|-----24|------0|
|10|16|----24571192|------0|----228|
|11|18|---212260296|----576|----356|
|12|20|--1939892240|---1012|---6384|
|13|21|-18429768516|--19204|--16384|
|14|22|184042835408|--67536|-299624|
私は全探索は一旦この状態で手を引こうと思います。
時間がかかる（↑で200分弱）割になかなか前へ進めないので。
n手目のパス数と終了数はn-1手目を打った後の状態で
パスをする必要がある局面数と終わった局面数です。
これらは全棋譜数には内数として含まれてますが
パス数と終了数とは排他的に数えてます。
389 271 sage 2006/03/11(土) 22:04:53
>>388
お疲れです。うちのより１０倍速いですねｗ
さっき14手の結果が上がってきたのですが40時間かかってました。
計算しながら普通にパソコン使ってますが。
12手までは同じ速度だったのにねぇ
390 293 sage 2006/03/11(土) 22:56:58
フフフ、あの12手検索から微妙にプログラムを変更してるんですよ。
395 256 sage New! 2006/03/13(月) 17:30:26
全探索プログラムをC言語で書き直しました。
今15手やってます。
ぼくも13手までは確認しました。
520 名無しさん＠５周年 sage 2006/07/01(土) 17:58:36
２週間ほど前にこのスレ見つけて、面白そうだったので自分も全探索にチャレンジ。
自己満足な意味合いが強いけれど何とか高速化を行い、初手固定の14手目までの探索で
60分強と言うところまで来ました。
環境はWIN2k、XP1800+、VC2005Express。一応cygwin上のgccでもコンパイルできることを確認。
15手目までやってみたかったけど、家のマシンは負荷を掛け続けるとなぜか落ちるようなので
断念しました。
MMXやら64ビット専用やらと、まだ高速化はいろいろ出来そうですし、実際そういうソースも
公開されてるようですが、ソースレベルの高速化はとりあえず一旦ここでお終いにしようかと
思います。
次の手としては、同じ局面が発生した時の対処となりますでしょうか。
ちょっと試してみたいと思います。
523 名無しさん＠５周年 sage 2006/07/12(水) 12:59:52
>>520 乙です。
＞同じ局面が発生した時の対処
これが意外と難しいんだよね。
同じ局面を判断するためのデータベースが必要になるし回転や反転をどこまで考慮するかも悩み所。
このスレでも全探索は大勢チャレンジしてるけど、その次の一歩が踏み出せない感じだね。
524 520 sage 2006/07/21(金) 23:48:51
どもです。
あれからも細々とやっておりますが、難しいですね。
局面データの保持がやはり厳しいです。
検索速度は無視してでも、何とかできないかと考えております。
高速化の方は成果がありまして、初手固定14手まで50分弱となりました。
今のところそんな感じです。
525 523 sage 2006/07/28(金) 08:01:55
>>524
14手まで50分弱とはかなり速いですね。このスレでもトップクラスじゃないかな？
私は13手で数時間掛かってそこで挫折ですorz
局面データを保持するためのメモリ量を考えてみました。
６４枡のそれぞれに黒の有無、白の有無、と考えると、１盤面あたりに128ビット＝16バイトのデータ量が必要。
６４枡に空き、黒、白の３値を保持して最小完全ハッシュ関数を作ったとして、3^64通り＝13バイト。
ここで考えたのがx手目が決まれば盤上の駒数ｎはn=x+4個に決まるのでこれを使えないだろうか。
６４枡にｎ個の石を配置出来るパターンは64!/(64-n)!/n!
ｎ個の石が黒か白かは2^n
これらを最小完全ハッシュ関数で表現出来れば
ｎ＝10の時配置は５バイト、黒白情報は２バイト。計７バイト
ｎ＝15の時配置は６バイト、黒白情報は２バイト。計８バイト
これを使えば初期十数手まではメモリ節約出来ると思う。
ただしハッシュ関数、逆ハッシュ関数を使うので速度的にはかなり不利だと思う。
それと上手い最小完全ハッシュ関数と逆関数が作れるか、というのも問題ですね。
526 名無しさん＠５周年 sage 2006/08/12(土) 23:18:58
>>525
コンパイラの吐くソースを見ながら、ビット演算と場合分けをちまちまとやった成果です。
局面データについてですが、配置情報と黒白情報が分かれてるのが良いですね。
片方（この場合は黒白情報か？）をくくり出すというか、indexにすれば実際の保持量を減らすことが
出来ますし。自分の場合は算術圧縮の頻度表（石の数）で試してみました。
とはいえ結局のところ局面数そのものが多いため、1局面を１ビットとしても持ち切れなくなると
思われるので、重複チェックは適当な所で妥協した方が良い気がしてきました。
つまり、一定数を超えたら適当にデータを捨てていくのはどうだろうかと。
探索数と保持数で上手くバランスが取れて成果が出るか、どっちつかずで意味が無かった
という結果になるか分かりませんけど。
しかしいずれにしろ局面を少ないデータで表現できるに越したことは無いので、何とかならないかと
引き続き思案中であります。
次に試そうと思っているのが、外周の空きマスをランレングスで圧縮してから算術圧縮というものです。
529 名無しさん＠５周年 sage 2006/09/02(土) 23:25:54
ネタとしてwikiの方にソース(othello_count.cpp)をアップさせてもらいました。
高速化の理由がバグのせいだったと言うこともあるかもしれませんので、
検証や更なる高速化をどなたかお願い致します。
（バグ入りじゃないと良いナァ…）
532 256 2006/09/09(土) 04:49:56
みなさんお久しぶりです。
520氏のプログラムのソースをいじってみました。
最終1手を最適化しただけですが、僕のマシン上（CeleronD3.06GHz）で、
処理時間を５９％くらい削減できました。（12手：27.44秒->11.28秒）
僕がちらっと見た限りでは520氏オリジナル版にバグは見当たりませんでしたが、
ぼくの変更により新しくバグが入ってしまったかもしれません。
ぼくはC++があんまりわかってませんし。
ソースは>>531と同じ場所にアップしときました。（othello_counter2.cpp）
こういう事ができる余地を残しておきながらあれだけ速いのは驚きました。
533 名無しさん＠５周年 sage 2006/09/10(日) 21:42:46
以前挑戦した時は13手で数時間かかっていたのですが、
久しぶりに書き直して、ちまちま改良を重ねたら13手で70分程というところまできました。
>>532のと比べると、まだまだ大きな差がありますが、もう少し頑張ってみようと思います。
534 293 sage 2006/09/11(月) 01:35:22
スレ復活の兆しが見えてきたので活力剤を投入してみます。
ご存じの方もいらっしゃるでしょうが、とある行きつけのスレでここ向きな話題を見つけたので
纏めておきました
>>520氏のプログラムに近い感じの流れだと思いますがどうでしょう？
ちなみに後半の回転に関しては、ユニークな盤面数を出すときに必要だろうということで。
542 名無しさん＠５周年 sage 2006/10/27(金) 20:34:42
自分独自のやり方では限界が見えてたので>>534を参考にしたら
11手12秒まで到達
基本アルゴリズムの解説
- よく使われる othello_counter{3,4}.cpp の大雑把な解説です。
static uint32 mobility[MAX_TURN];// 打てる可能性のある最大数
static uint64 record[MAX_TURN];// 棋譜数
static uint64 gameover[MAX_TURN];// ゲーム終了
static uint64 passcount[MAX_TURN];// パス数
main(){
...
//初期化
int tmax = 引数で与えられた手数制限;
uint64 black = 0x0000000818080000ULL;//初手固定
uint64 white = 0x0000001000000000ULL;//初手固定
mobility[tmax-1] = 4;//初手固定
record[tmax-1] = 1; //初手固定
gameover[tmax-1] = 0;
passcount[tmax-1] = 0;
//探索開始
SearchMove(white, black, tmax-2);
//結果表示
for(i){
printf(mobility[i]);
printf(record[i]*4); //初手固定による対称性により４倍
printf(passcount[i]*4);//初手固定による対称性により４倍
printf(gameover[i]*4); //初手固定による対称性により４倍
}
}
/* own = 次に着手する色の bitboard
opp = 次に着手しない色の bitboard
turn = この手を含む深化残数。1 だとさらなる SearchMove 呼び出しなし */
SearchMove(board own, board opp, int turn){
board move = 着手可能手;
if(!move.f){
//打つ手がない→パス
own と opp の swap;
board move = 着手可能手;
if(!move.f){
//打つ手がない→相手もパス
++gameover[turn];//終了数カウント
}
++passcount[turn];//パスカウント
}
--turn;
if(turn>0){
uint32 mobcnt = 0; //着手可能数カウントリセット
while(move){
board x = move の中から 1 ビット選んで新たに置く石とする;
board reverse = x を打ったときに裏返る石;
board nextopp = opp.f ^ reverse.f; //裏返りを反映
board nextown = own.f ^ reverse.f; //裏返りを反映（これって要らないような…）
nextown.l |= x; //新たに置く石を反映
if(turn>0){
SearchMove(nextopp, nextown, turn);
}else{
//othello_counter4.cpp では対称性のある盤面数の計算のために最終盤面でこれを呼ぶみたい
LastMove(nextopp, nextown, turn);
}
++mobcnt; //着手可能数インクリメント
}
record[turn+1] += mobcnt; //着手可能数記録
if(mobility[turn+1] < mobcnt) mobility[turn+1] = mobcnt; //着手可能数の最大を更新
}
}
最終更新：2009年11月28日 01:18
