Robin Hood Hashing ハッシュテーブルのinsertクエリにおける衝突処理をオープンアドレス法でやるとします。具体的にはハッシュ値を1ずつ増やして見ていくとします。このとき、既に入っている要素のほうが「本来の場所からの距離が短い」ならば、それを今入…

こいこいのナッシュ均衡解を求めたいと思い、Counterfactual Regret Minimization (CFR) の論文とその発展手法の論文をいくつか読み、内容を日本語でまとめるというのを最近やっていました。分量が多くなったので本文はここではなくGitHubにpdfで載せました…

以前、pdep命令がRyzenでめっちゃ遅いことについて調べました。 pdep、pdep抜きで - ubiquitinブログその記事のベンチマークではpdepの使いみちについては特に書きませんでした。圧縮全文索引の話で出てくるrank/selectデータ構造のselect1関数をpdepで高速…

前回の記事から少し調べたところ、Lucas-Lehmer testの乗算ではSchönhage-Strassen法は使われていないと知りました。代わりにirrational base discrete weighted transform (IBDWT)というアルゴリズムが使われているそうです。 (cf. GpuOwL - Prime-Wiki)Sch…

Visual StudioにはNuGetというパッケージマネージャがあって、様々なパッケージをうまくいけば一瞬で導入できます。うまくいけばインストールバトルが発生しないので便利です。（うまくいかなかった場合は、Microsoftのやる気なさげな企画が発する独特の雰囲…

edaxの置換表は1エントリ192バイト 24バイト(192bit)で、パラメータh（ただし ）を受け取って、2.25 個のエントリをメモリに確保します。（2.25 2.0625と中途半端な値なのは、3種類のテーブルを使い分けているためです）デフォルトはh=21です。最小値のh=10…

前回はedaxというオセロソフトのboard_score_1関数を分岐不要に書き換える話をしました。cmov命令がそれに使えるのがポイントでした。私はcmov命令の存在を最近知ったのですが、記事を投稿したあとで"cmov"でググったら達人の間では昔から当たり前だったみた…

edaxというオセロソフトでは、探索処理の中でも最後の1手を打つ部分を計算する関数を個別に用意しています。board_score_1という関数です。edax-reversi/endgame.c at master · abulmo/edax-reversi · GitHub inline int board_score_1(const Board *board, …

はじめに一般の詰将棋などの問題設定について説明します。 局面をノードとし、指し手を有向エッジとする木（ゲーム木）があるとします。プレイヤーは「攻め」と「受け」の２人とします。葉ノード（詰将棋の場合は、即詰みor王手をかけられない局面のこと）に…

edaxが使っている枝刈り手法を説明します。 stability cutoff: オセロの終盤では「今後絶対にひっくり返らない石」が生じます。これをstable discと呼びます。四隅が最も有名ですが、それ以外にも例えば上下左右斜めの8方向に空白が一切存在しない石は自明に…

edaxというオセロソフトのソースコードをガチャガチャいじって遊んでいたのですが、いろいろわかって満足したので忘れる前に書いておきます。 探索アルゴリズムの基本的な説明 最初なので基本的というか、将棋ソフトとかと共通していてedaxでも使われている…

前回から引き続き、「オセロの初期局面から合法的に到達可能で、かつ合法手の数が34通りあるような局面は存在するのか？」を調べました。前回の最後に言及したように、flip関数をz3で書き下すことで、主問題そのものをソルバーに投げられるようにしました。…

前回の記事では合法手の数が34通りあるようなオセロの局面を生成しましたが、あれは初期局面から到達可能かどうかを考慮していませんでした。初期局面から到達可能で、かつ合法手の数が34通りあるような局面は存在するのでしょうか？ いっぱい存在すると期待…

将棋の最大分岐数（すべての局面における合法手の数の最大値）は593であることが証明されています。http://www.nara-wu.ac.jp/math/personal/shinoda/bunki.htmlこの証明は実際の局面を構成してはいませんが、簡単に構成可能でして、やっている人がいます。l…

edaxというオセロソフトがあるのですが、そこでは『1を左シフトする操作』が表引きで実装されています。マクロがbit.hで宣言されていて、表の実体はbit.cにあります。https://github.com/abulmo/edax-reversi/blob/master/src/bit.h extern const unsigned l…

2進数(binary number)は0と1だけからなりますが、3進数(ternary number)は0と1と2からなります。2進40桁以下の符号なし整数を受け取って、それを『偶然0と1だけでかけるような3進数だった』と解釈して、その値を2進数にして返す関数は以下のように書けます。…

pdepという命令があります。ビット演算のための命令セットBMI2に属していて、タイミング的にはSSE4.2とAVXの間くらいに登場したものです。2つのuint64_tを受け取ってuint64_tを返す命令で、計算の中身は以下のように書き下せます。 inline uint64_t pdep_nai…

とかの範囲で一様乱数をサンプリングできるとします。そのうえで、ある正の整数kについて[0,k]の範囲内で一様に分布する擬似乱数が欲しい場合を考えます。雑な方法としてkで割った余りを使っちゃうやつがありますが、そもそも一様でないじゃんとか整数除算が…

適当に調べた。 Adam arxiv.orgおなじみのやつ。欠点 最初だけ学習率を小さくする"warmup"をしないと発散することがある。 最終的に収束したときの精度がSGDよりなぜか悪い。 ハイパーパラメータの設定によって精度が良かったり悪かったりする。 そもそも玄…