Qhapaq アドベント将棋記事10日目 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。 参考文献: memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn(厳密には非0のpn、dn
2020年07月13日12:44 カテゴリUnityGPGPU UnityでGPGPU応用編 バイトニックソートを高速化 バイトニックソート(Bitonic Sort)の概要バイトニックソート(Bitonic Sort)は主にGPU等の並列計算器でソートを実装しようとするときに使われるソートである。 計算量のオーダーはO(n log^2 n)であり、クイックソートのO(n log n)には負けるものの並列化による高速化が勝るという感じなのでいろんなところに使われている。 対象読者キーワード「GPU」「バイトニックソート」で検索してこの記事にたどり着いただろう方が対象。 この記事では ・バイトニックソートでなぜソートできるか ・どうやったら高速化できるか という点について重点的に書いている。 高速化については OpenCLでバイトニックソートを実装している海外サイト をパクリ参考にした。 こ
JAG の ICPC 模擬地区予選 2015 の最中に, ジャッジルームで思いついたこと. イントロ 誤差を避けるために有理数を使うとき, オーバーフローするボトルネックは, 多くの場合, 有理数同士の大小比較になる. (逆に, 有理数同士の大小比較がボトルネックにならないときは, 別のテクニックで誤差を避けられることがある) そこで, 有理数の分母分子自体はオーバーフローしていないときに, 有理数同士の比較を, なるべくオーバーフローさせずに行う方法を見る. つまり, 次のような sgn 関数を作りたい. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39template<class Int> struct Fraction{
ネタバレ ぼくのかんがえたさいきょうの手法は既出で、MCTS-Solverというようです。 はじめに モンテカルロ木探索(MCTS)は、ゲーム木の各ノードを評価しながら探索を行える優秀な探索アルゴリズムです。 Wikipedia : モンテカルロ木探索 https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2 しかしCodinGame*1のUltimate Tic-Tac-ToeというゲームでMCTSを使っていたところ、シミュレーション結果が優勢にも関わらず、ある瞬間に劣勢に反転して負けてしまうことが多々ありました。ある手を指されると劣勢なのに、それが評価に反映されずに優勢と勘違いしている状態ですね。 左図:シミュレーション勝
以下の続き。 木探索がそもそもどういうものであるかと考えると、状態をノード、行動をエッジとして構築されるグラフ上を遷移しつつ、ノード上の価値を更新していく作業だと思われる。モンテカルロ木探索の選択ステップに「一個親のノードへ戻る」という選択肢を加えれば、理論上は木の自由な遷移ができるので、たとえば以下のようなことができる。 ステップ1 ステップ2 ステップ3 ステップ4 結局各ステップで解きたい問題は「木の遷移履歴が与えられるので、現ノードを適切に評価し次に遷移するエッジを決定する問題」としてまとめられそうだ。ここで、木の遷移履歴は状態を訪問順に並べた単なる時系列入力として扱える。(無茶かなぁ……)。状態の分散表現取得や、状態価値の評価にはAlphaZero的なモデルの分岐直前までの部分などを使うとして、次のようなやり方を今のところ想定している。 木のような句構造を持つことが多い自然言語文
要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか? 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか? これが $_NC_K$ になります。例えば、$N
遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 概要 前回 → Segment Tree のお勉強 (1) を前提としています。 1点更新、区間作用、区間積取得が可能な Segment 木。いわゆる非再帰実装 1-based index$N=2^n$ を仮定しない モノイド $A$ がモノイド $X$ に右作用するとします。各々のモノイドの二項演算を、積の形で、$$\begin{align*}A\times A\longrightarrow A;\quad (a,b)\mapsto ab,\\X\times X\longrightarrow X;\quad (x,y)\mapsto xy\end{align*}$$ と書きます。作用は、$$X\times A\longrightarrow X;\quad (x,a)
セグメント木とは セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します
本文章はC言語を用いて様々な確率分布に従う乱数を生成する方法やコードをまとめたものである。rand関数やメルセンヌ・ツイスタの使い方から始まり, 正規分布・指数分布等の様々な確率分布に従う乱数の生成方法について解説する。このページは近江崇宏によって作られました。コードはご自由にお使いになってかまいませんが、バグ等によって生じた損失に対する責任は負いません。 道しるべ: ・C言語でお手軽に整数の乱数を発生させたい人 ==> C言語のrand関数の使い方 ・メルセンヌ・ツイスタの使い方を知りたい人 ==> メルセンヌ・ツイスタの使い方 ・一様乱数の生成方法を知りたい人 ==> 一様乱数 ・様々な確率分布に従う乱数生成法を知りたい人 ==> 各種の確率分布に従う乱数の生成法 入門編 C言語のrand関数の使い方 メルセンヌ・ツイスタの使い方 乱数生成の基礎 一様乱数 (Uniform Rando
1 はじめに 最近、我々+数名でスパースモデリングという分野を勉強しています。詳細はまた別の記事にて紹介するにして、今回はスパースモデリングの前段階に当たる リッジ回帰(ridge regresion) に脚光を当てます1。 読者には釈迦に説法かもしれませんが、リッジ回帰は L2 正則化とも呼ばれ機械学習の中でも非常にスタンダードな概念の一つになっています。しかし専門的に正則化法を扱ってみて、案外知らなかったことを知れたのでまとめました。 まず、リッジ回帰での損失関数は以下のような式で記述されます。 \begin{align} E = (y - X \vec{w})^2 + \alpha \vec{w}^T \vec{w} \end{align} 上記の損失を最小化するように係数の重みベクトル \(\vec{w}\) を推定します。解析的には \(\vec{w}\) について微分をしたもの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く