以前の記事（↓）の続きです。 eukaryote.hateblo.jp 符号なし64bit整数を8x8 bitboardとみなして(1)横方向に鏡映 (2)縦方向に鏡映 (3)行列転置 という3つの処理をこの順番でやってもやらなくてもよいとしたとき、結果得られる最大8通りのbitboardのうち整数…

棋譜は f5f4e3d2d3c3f3e6b3g3f6d6e7g7c6d7f7g5c7b7c8b4b2b1c2f2 です。 オセロの局面。黒の手番、34マス空き、h1以外の33マスに着手可能。経緯については前の記事を参照してください。 eukaryote.hateblo.jp

tl;dr 棋譜は f5f6e6f4g7c6g3e7d6f3e3d3b7d7c2g2g1c3b2b3b4f7g5c4c7c8e2 です。 オセロの局面。33マス空き、白の手番、33マスすべてに着手可能。WZebraで画像作成 経緯（2020） オセロには相手の石を1つ以上裏返せる場所にしか石を置けないというルールがあ…

news.mynavi.jpこの記事で、Scalable Vector Extension 2(SVE2)について語られています。出典は以下のページの右上の"download presentation"ボタンから得られます。connect.linaro.orgこのプレゼンの26ページ目（＝一番上の記事のphoto 02）によると、SVE2…

符号なし64bit整数を8x8 bitboardとみなして、(1)横方向に鏡映 (2)縦方向に鏡映 (3)行列転置 という3つの処理をこの順番でやってもやらなくてもよいとしたとき、結果得られる最大8通りのbitboardのうち、整数としての値が最小のものを得たいという問題を考え…

pext命令を軸としてmagic bitboardについて振り返ってみます。計算速度が重要なソフトで、そのなかである固定されたマスク値でpext命令を頻繁に計算する必要があるがpext命令を使いたくないとします。具体的な問題設定としては、 マスク値で立っているビット…

前回の記事で、符号なし64bit整数を8x8 bitboardとみなして転置する方法として、基本RISC命令のみでやる方法と、AVX2のmovemask命令などを使う方法があるという話について書きました。今回はそれの続きで、ハッカーのたのしみ第7章7.5を改良した方法も加えて…

最近broadcast+sllv+movmskでbitmatrixの転置ができることを知ってスゲーになりました— そすうぽよ(すごい)(早寝早起き) (@_primenumber) 2021年10月1日 このツイートを見かけたんですがやり方が見当たらなくて一瞬考えてしまったたので、備忘録として以下に…

ウマ娘のサンプル音声と声優のサンプル音声が与えられたとき、どのウマ娘がどの声優なのか機械学習で当てられるのかっていうやつを思い出したので、一瞬でちょっとだけやってみました。 Methods いい感じの解くやつを探す ディープラーニングのなんかいい感…

github.comYavalathというボードゲームの2人向けルールのAIを、Bitboardを多用して実装しました。思考部分はMCTSで実装してあり、コマンドラインで遊べるようになっています。 盤面の表現 Yavalathは1辺5マスの六角形の盤面を使います。2人で交互に石を置い…

algorithm-study/hackers_delight_7_5 at master · eukaryo/algorithm-study · GitHub ハッカーのたのしみ第7章7.5では、「ワードの一般的順列演算」と呼ばれている演算の実装方法について論じられています。「ワードの一般的順列演算」は、愚直に書くと以下…

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よりなぜか悪い。 ハイパーパラメータの設定によって精度が良かったり悪かったりする。 そもそも玄…