Computer Algorithm and Information Technology

全73件の内、新着の記事から10件ずつ表示します。

1 2 3 4 5 6 7 8 | 《前のページ | 次のページ》

外部ソート書きました

投稿者：和投稿日：2005年 4月25日(月)10時40分28秒

しかしHDDが複数もってないのでベンチマーク取れませんでした。余裕があったら見てやってくださいね。ホントに速くなるのかな～？

http://urrryyy.hp.infoseek.co.jp/computer/outer_sort.htm

(無題)

投稿者：DO++ 投稿日：2005年 4月21日(木)20時55分49秒

編集済

>英語ですねぇ。年末に1年ぐらい英語覚えに留学行くので読めるようになってみせます　一年も行くのですか。かなり英語をマスターできるでしょうねぇ。俺も英語はきちんと身に付けないと。。 >このソートって多分Web上には普通に載ってないので出来れば誰かの役に立つかもしれませんね。　そうですね。ソース付きだとさらにみんな喜びます（俺も） 　

PDFは

投稿者：和投稿日：2005年 4月21日(木)10時46分51秒

英語ですねぇ。年末に1年ぐらい英語覚えに留学行くので読めるようになってみせます。今重複をなくすためファイルをソートするのに4台HDDを使ってランダムアクセスのないマージソートを実装しています。このソートって多分Web上には普通に載ってないので出来れば誰かの役に立つかもしれませんね。

うーむ

投稿者：DO++ 投稿日：2005年 4月11日(月)20時39分28秒

編集済

10^28というのはさすがに回転反転を適用したものじゃないのかなぁ。それらを適用して劇的に減るのだろうか。オセロって計算量理論ではどのクラスに属するんだろう、ときいてみたところPSPACEらしいです。（ちなみにNP⊆PSPACE) これ論文　http://arxiv.org/PS_cache/cs/pdf/0106/0106019.pdf 。かなり難しいのではと思います

計算量は

投稿者：和投稿日：2005年 4月 7日(木)16時41分42秒

探索木の葉数は10^58で重複を除くと10^28らしいです。この重複除きはこの多彩な回転反転白黒反転全てを適用したものかどうかはわかりません。もししてなければ現実的に全部求めれる可能性がありますね。

途中のは

投稿者：和投稿日：2005年 4月 7日(木)14時15分16秒

もちろん保存しますよ。打っていない場所、白黒で単純に3^64の組み合わせになります。ありえない局面はそれは大量にあるでしょうね。たとえば ●●○○●●○○ ○○●●○○●● ●●○○●●○○ ○○●●○○●● ●●○○●●○○ ○○●●○○●● ●●○○●●○○ ○○●●○○●● で終わる局面はないですね。

途中の

投稿者：DO++ 投稿日：2005年 4月 7日(木)10時50分16秒

局面って保存しないんですか？終わった後の表現が白黒で64bitで表現できるという話ですよね？回転などの重複があったとしても2^64を全て列挙するというのはかなり大変そう。絶対ありえない局面とかってのも結構あったりするんでしょうかね

局面は64ビット変数で白と黒の盤面のパターンそれぞれ2変数で表現し、保存するときはそのままではなく左右反転、回転の組み合わせでまず8パターン作り、さらに白番の場合は白黒の64ビット変数を入れ替えることで常に黒番として表現し、作ったパターンの黒変数、白変数をソートし最小値(最大値でも)で保存します。回転、反転の理由は重複局面を増やすことが出来、容量の節約になります。検索時も同じく8パターン作り最小値(最大値)で検索できますし。白黒局面を黒番に統一するのは白番か黒番かを保存するフラグが必要ないし、これもパスがあった手順の場合は重複局面になり容量節約になるかもしれないです。オンラインってCPUによる動的な探索のことですよね？現在考えてるのはいずれも完全解が求められたあとのことなんでもどかしいですね。

焼け石に水の枝狩り

投稿者：和投稿日：2005年 4月 6日(水)08時33分16秒

局面は64ビット変数で白と黒の盤面のパターンそれぞれ2変数で表現し、保存するときはそのままではなく左右反転、回転の組み合わせでまず8パターン作り、さらに白番の場合は白黒の64ビット変数を入れ替えることで常に黒番として表現し保存します。回転、反転の理由は重複局面を増やすことが出来、容量の節約になります。検索時もちょっと工夫すれば検索できますし。白黒局面を黒番に統一するのは白番か黒番かを保存するフラグが必要ないし、これもパスがあった手順の場合は重複局面になり容量節約になるかもしれないです。オンラインってCPUによる動的な探索のことですよね？現在考えてるのはいずれも完全解が求められたあとのことなんでもどかしいですね。

解数の見積もり

投稿者：DO++ 投稿日：2005年 4月 6日(水)02時01分31秒

をしておくといいのかもしれませんね。６＊６と８＊８でそれほど違うというのは、微妙なゲームバランスってことですよね（後半で意外な逆転が期待できる） >そうではなくひたすら解を求め続け、最終的には最強になることができるオセロができるんじゃないかと思うわけです。　やはり全ての完全解を求めるのは難しいので、近似とかできないんでしょうか。予測木に重みをつけて探索の深さを変えたりするのはしっていると思いますけど、それと似たことをしてある程度オンライン探索も組み合わせると現実的になるようなきもします

以上は、新着順31番目から40番目までの記事です。