FPGAで将棋プログラムを作ってみるブログ:dfpnの詰将棋を作成中 - livedoor Blog（ブログ）
YSSの詰将棋は長いこと脊尾さんの証明数だけを使ったものを採用してたのだが、 東大７（８）で使われているdfpnの性能（解答時間＋探索局面）が はっきり優れているので「一念発起して（拝借しました）」試作中です。 具体的には東大７はだいたい15手から25手詰くらいを YSSの半分から10分の1といった局面数で解いてしまう。 反証数は今までも少しだけ使っていたのだが（ハッシュに手がある時に、王が逃げる手の選択で、評価関数みたいな感じで反証数の小さい手を優先的に読むように） こうも性能の差を見せられては、である。 それに不詰がほとんど解けないのも気になってたし。 で、実は長いこと長井さんの進歩４の論文のdfpnのコードを誤解してました。 下の部分で、 // 多重反復深化(長井さん論文) while (n->pn > DN_Min(n) && n->dn > PN_Sum(n) ) { // pn
All by myself df-pn
読んだ本や指将棋・詰将棋について書いてます。倶楽部24は最高2700点くらい。平成20年度看寿賞（長編賞）を受賞。詰パラ大学院の担当やってました。 こんばんは。しばらくの間、コンピュータ将棋の話題を積極的に書いていこうと思います。大学の研究室で参加する世界コンピュータ将棋選手権も近いですしね。（自分は当日行くかどうかわかりませんが…） ということで、わけあってdf-pnに関係する論文を読んでいるのですがなかなか理解できません。証明数・反証数といった用語の意味をネットで調べようとしても、サイトによって定義がバラバラだったり。うーむ。 ４月１７日追記。ちょっとずつわかってきました。参考にしたサイトをメモしておきます。 http://d.hatena.ne.jp/GMA0BN/20090520/1242825044 http://www.logos.ic.i.u-tokyo.ac.jp/~h-i
df-pnアルゴリズムの詰将棋を解くプログラムへの応用 | CiNii Research
タイトル別名 df pn アルゴリズム ノ ツメショウギ オ トク プログラム エ ノ オウヨウ Application of df-pn Algorithm to a Program to Solve Tsume-shogi Problems アルゴリズム理論 詰将棋を解くプログラムの研究はこの10年の間に大きく進歩した．その原動力となったのは，証明数や反証数という概念の導入である．詰将棋に適用すると，直感的にいうと，証明数は玉の逃げ方の総数を，反証数は攻め方の王手の総数を表す．前者は攻め方にとって，後者は玉方にとって非常に重要な値である．証明数・反証数を対等に扱った，最もナイーブなアルゴリズムは，Allisによるpn-searchという最良優先探索法である．我々は近年，df-pnアルゴリズムという，pn-searchと同等の振舞いをする深さ優先探索法を提案している．この論文では，df-
df-pn探索おさらい - 思うだけで学ばない日記 2.0
df-pnが難しいという声がちらほら見聞されるが、ポイントを正しく押さえればこれはさほど難しくはない。 準備 まず「詰み」(=必至)を自明なものとそうでないものに分けよう。 自明な詰み そのノードの局面を見るだけで判断がつき、子ノードを見る必要がない形の詰み。 これは通常のゲームのルールの下では勝負がつくことと同義だ。例えば、将棋なら片方(敗者)の玉が取られた(事後の)局面、五目並べなら片方(勝者)の石が5個(以上)並んだ(同じく事後の)局面等。 敗北した側にもはや合法手は残されていないから、そうした局面のノードはそもそも子ノードを持たない(葉ノードである)。子ノードを持つ自明な詰みとしては、局面のハッシュ辞書等にすでに詰み登録がなされているケース等がある。 df-pn探索のねらい df-pn探索の第一目的は実は次の仮説の検証である(後述するように、必ずしも勝負に勝つことではない)。 pの
コンピュータで詰将棋 - 詰将棋メモ
[２０１３年１１月６日最終更新] ２００６年以降の情報を追加、リンク切れなど修正 ２００４年５月２８日、コンピュータ将棋や囲碁の掲示板で、高橋さんが昔のコラムを紹介。 １９９８年１０月５日、東公平 将棋雑話「電子計算機と将棋」 １９６８年に初めてコンピュータで詰将棋を解いたときの話。高橋さんによると、このとき日立の１台１０億円の大型計算機で３６秒かかった詰将棋を現在の謎的電棋で解かせたら約０．００５秒で、「1968年から36年経って約7000倍速くなった」。 現在では１５２５手のミクロコスモスも解けるようになった「コンピュータで詰将棋」の研究の軌跡をWeb上の論文などからまとめてみた。なお、コンピュータ将棋全般についてはコンピュータ将棋協会のコンピュータ将棋関係の文献リストを参照されたい。最近では、情報処理学会のゲーム情報学研究会で、関連する研究が発表されることが多い。 こうした研究の成果
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
コンピュータゲーム研究の現状・動向、完全情報二人ゲームの探索法
Alpha-Beta-Suche – Wikipedia