詰将棋アルゴリズムdf-pnのすべて | やねうら王 公式サイト
将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。 これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。 将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。 df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出
「線形代数で何を学ぶのか、何に役立つのか」大学や高専で線形代数を学び始めた人へ送るポスト→「学生時代に読んでみたかった」「意味や繋がりが理解できて初めて面白い」
三谷 純 Jun MITANI @jmitani 筑波大学 システム情報系 教授（'75生）CG/折紙/幾何/プログラミング，一風変わった折り紙の設計，制作をしてます．令和元年度文化庁文化交流使としてアジア諸国をまわってきました．主に数学と折紙と日常のことについてツイートします．折紙作品の写真をこちらで公開しています instagram.com/mitani.jun/ mitani.cs.tsukuba.ac.jp/ja/ 三谷 純 Jun MITANI @jmitani 理工系の大学生1年生の多くは まずはじめの数学で「線形代数」を学ぶことになると思います。 僕が学生だった頃、 「結局これって何を勉強しているの？」 という疑問がずっと拭えなかった記憶があります。 同じような疑問を持っている学生向けに、線形代数で何を学ぶのか説明する文章を作ってみました pic.twitter.com/1j
プロンプトを遺伝的アルゴリズムで自動最適化するプロンプトエンジニアリング手法『Promptbreeder（プロンプトブリーダー）』 | AIDB
関連研究 ■GPT-4などのLLMに「自らの論理的な整合性をチェック」させるフレームワーク『LogiCoT』と実行プロンプト ■LLMの出力から誤り（ハルシネーション）を減らす新手法『CoVe（Chain-of-Verification）』と実行プロンプト ■LLMに自身のハルシネーション（幻覚）を「自覚」させ、減らす方法 従来の課題 手作りのプロンプト戦略 現在、プロンプトエンジニアリングの分野で広く用いられているChain-of-Thought（CoT）やその派生テクニックは、基本的には手作りです。特定のタスクや問題に対して最適なプロンプトを設計する際に、人の専門家が手動でプロンプトを生成しています。 自動化の必要性 手作りのアプローチは効果的である場合も多いですが、スケーラビリティに欠けるという問題があります。大規模言語モデル（LLM）が多様なタスクで使用される現代においては、プロン
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
「ガベージコレクション 自動的メモリ管理を構成する理論と実装」を読んだ
最近「おれってガベージコレクションを勉強するにあたってめちゃくちゃ恵まれた環境にあるのでは？」とふと思い立ち、ベージコレクションの勉強を始めました。 ガベージコレクションの勉強を始めるにあたって、とりあえず「The Garbage Collection Handbook (first edition)」の邦訳である「ガベージコレクション 自動的メモリ管理を構成する理論と実装」を読むことにしました。 この記事では、読み終わってうれしいので、雑に感想を書きなぐっています。表記が「GC」だったり「ガベージコレクション」だったりするのは雑に書いたからです。 前提知識 ガベージコレクションの事前知識はほとんど不要で、何をしてくれるものか大まかにわかっていれば良い程度だと思います。つまり、ヒープに確保した領域を明示的に解放しなくても、何かのアルゴリズムでいい感じにやってくれる仕組み、ということを知って
プログラムを動かす時にメモリがどのように割り当て・解放されるのかをめちゃくちゃわかりやすいイメージ画像で解説してくれるサイト「Memory Allocation」
コンピューター上でプログラムを動作する際に必要になるのがメモリです。プログラム自体をメモリに読み込む必要があるのはもちろん、プログラムが行う動作はほとんど「メモリから値を取りだして計算し、メモリに保存する」であるといっても過言ではありません。プログラムが動作する際にメモリがどのように管理されているのかについて、ベテランプログラマーのサム・ローズさんがブログで解説しています。 Memory Allocation https://samwho.dev/memory-allocation/ C言語の標準ライブラリには「malloc」と「free」という2つの関数が用意されています。この2つはなんと1979年のUnix v7から存在している歴史ある関数で、mallocがメモリの割り当てを担当し、freeがメモリの解放を担当しています。サム・ローズさんの解説は「この2つの関数の中身を自分で実装する」
【速報】次世代の外観検査！？プロンプトを駆使した異常検知 - Qiita
先日、革新的な画像の異常検知（SAA）が出てきました。 何やら革命的な臭いがする... SAMを使った異常検知手法https://t.co/wmwFcbULdq コードはこちらhttps://t.co/3npK3FhnEz pic.twitter.com/JDs30bEJyQ — shinmura0 (@shinmura0) May 22, 2023 本稿では、操作手順 & 触ってみた感想をご報告します。 特長 本題に入る前に、どこら辺が革新的なのかざっくり説明します。 ※ SAAの詳細は論文をご参照ください。 学習データは不要 通常、学習（正常）データを数百枚用意しますが、この手法では正常データを必要としません。 ドメイン知識を導入できる 予め、異常の傾向をプロンプトに入れることにより、異常の特徴をモデルに教えることができます。 二点目が特に大きく、今までの異常検知では、積極的に異常の傾
ChatGPTに自社データを組み込んで新しい検索体験を模索してみました｜masa_kazama
イントロChatGPTやBing、NotionAIなどの大規模自然言語モデル(LLM)を活用したサービスが注目を集めています。対話、要約、翻訳、アイデア生成などの多様なタスクにおいて、とても性能が高いです。ただ、ChatGPTでは、ときどき嘘が混じっていたり、文献が捏造されたりすることがあります。 ChatGPTとの対話画面（結果の書籍は存在しない）それを防ぐために、BingやPerplexityでは、文献を引用した上で、なるべく嘘が紛れ込まない形で回答してくれます。 Perplexityでは引用もつけてくれるしかし、これらのAIは、Web上の公開されている一部のデータを元に学習しているので、公開されてないデータに対しては当然ながら、正しく回答できません。 そこで、この記事では、自社が保有しているデータをChatGPTに組み込んで、自社オリジナルのPerplexityのようなシステムを作る
クッキークリッカーで学ぶアルゴリズム入門 : あすなろの雑記
0. 目次 1. クッキークリッカーとは? 2. クッキークリッカー100万枚RTA 3. 解答? 4. 解答 5. 余談 6. おわりに 1. クッキークリッカーとは? 皆さんはクッキークリッカーというゲームをご存じでしょうか？ 2013年に公開され同年に日本でも爆発的に流行を見せたゲームです。知らないよという方もご安心ください、最初の方だけですがざっくり説明します。 上の画像がプレイ画面です。左にあるクッキーをクリックします。 クッキーが1枚焼けました。やったね。 クッキーが15枚貯まりました、右側にあるカーソルをクリックしてみます。 指はどこだ！？ クッキーの周りにある指が10秒に1回クッキーをクリックしてくれます。助かるー。 100枚貯まりました。アップグレード「強化された人差し指」を買ってみます。 クッキーの上に、クリックした回数分「+2」と書かれています 1回のクリックでクッキ
図解Stable Diffusion
ジェイ・アラマールのブログより。 AIによる画像生成は、(私を含めて)人々の度肝をぬく最新のAIの能力です。テキストの説明から印象的なビジュアルを作り出す能力は、魔法のような品質を持ち、人間がアートを創造する方法の変化を明確に指し示しています。Stable Diffusionのリリースは、高性能(画質だけでなく、速度や比較的低いリソース/メモリ要件という意味での性能)なモデルを一般の人々に提供することになったのは、この開発における明確なマイルストーンです。 AI画像生成を試してみて、その仕組みが気になり始めた方も多いのではないでしょうか。 ここでは、Stable Diffusionの仕組みについて優しく紹介します。 Stable Diffusionは、様々な使い方ができる汎用性の高いものです。まず、テキストのみからの画像生成(text2img)に焦点を当てます。上の画像は、テキスト入力と生
分かると、実に、おもしろい！ QRコードの仕組み
少しマニアックな知識、QRコードの仕組みを紹介します。 QRコード決済、リンクをQRコードで提供するなど、日常的に使用されているQRコードにあるそれぞれのパターンがどのように機能しているか、どういう役割をしているのか、なぜ上下逆さにしても読み取れるのか、なぜ一部が隠されても読み取れるのかなどが分かります。 QR codes by Dan Hollick (@DanHollick) 下記は各ポイントを意訳したものです。 ※当ブログでの翻訳記事は、元サイト様にライセンスを得て翻訳しています。 はじめに QRコードの仕組み 終わりに はじめに QRコードがどのように機能しているのか、疑問に思ったことはありませんか？ 控えめに言って、実に、おもしろい！ 注意: この記事⬇では非常にマニアックな内容が含まれています。 QRコードの仕組み QRコード（Quick Response code）は自動車部
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
Let’s 競技プログラミング! E8さんが教える アルゴリズム発想のキホン(12) アルゴリズムの基本用語 - 「グラフ」とは?
皆さんは「グラフ」という言葉を聞いて何を思い浮かべますか。Excel の折れ線グラフや棒グラフを想像する方が多いことでしょう。しかしアルゴリズムの文脈では、グラフは「モノとモノを繋ぐ関係」のことを指します。今回は、グラフの基本について整理した上で、どんな問題をグラフで表すことができるのかを紹介します。 グラフとは グラフは、モノとモノを繋ぐ関係を表すネットワーク構造のようなものです。グラフは頂点と辺からなり、頂点はモノを、辺は繋がりを表します。イメージしづらい場合は、鉄道路線図の駅を頂点、線路を辺と考えると良いでしょう。なお、頂点同士を識別するため、各頂点には 1、2、3…… と番号が付けられることが多いです。 無向グラフと有向グラフ 下図左側のように、辺に向きが付いていないグラフを「無向グラフ」と言い、下図右側のように、辺に向きが付いているグラフを「有向グラフ」と言います。例えば、一方通
リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO
Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです： サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します） クライアント x N（文書を編集する側です） そ
みんな、とにかくオセロAIを作るんだ - Qiita
オセロAIってなんか難しそう？そんなことはありません。むしろゲームAIを学ぶ様々なレベルの人にこれ以上ないくらい最適です。この記事ではオセロAIを作ると何が良いのかをひたすら語っていきます。そしてオセロAIをこれから作る人のために参考になりそうな記事をいっぱい貼り付けていきます。 私自身はもうかれこれ1年以上オセロAIにどっぷりハマっています。詳細は以前書いた記事で。 オセロAIをおすすめする3つの理由 1. 原始的なゲーム木探索を学べる オセロは「二人零和有限確定完全情報ゲーム」と呼ばれる種類のゲームです。この名称を説明すると、 二人: 二人で行われる、 零和: どちらかが得をすればもう片方が同じだけ損をする、 有限: 探索すべき範囲(ゲーム木)が有限で、 確定: 手番が一意に定まり、 完全情報: ランダム要素などの予期せぬ情報がない、 ゲーム: ゲームである という意味です。チェスとか
オセロAI世界1位になってオセロAIをｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話 - Qiita
オセロAIを作り始めた日のこと あれは2021年4月のこと、今思い返せば偶然が重なって起きた出来事でした。 第一の偶然は、ゲームAI(ゲームを自動プレイするAI)世界4連覇の方になぜかゲームAIの初歩的な話を30分程度教わっていたことです。 第二の偶然は、Twitterの知り合いが「オセロソフトRTA」なる競技をやっているのを目にしたことです。なんじゃそりゃ、と思った私はすぐに、その競技が 「オセロで遊ぶプラットフォームをどれだけ早く作るか」を競うものだとわかりました。 面白い、やってみよう。 YouTubeでライブ配信しながら、私はオセロソフトRTAをやってみました。その時のライブはこちら。3時間で完成できれば良いと思っていたのですが、思ったよりも早く終わってしまいました。 オセロAIでも作るか。 こうして私のオセロAI制作が開始しました。 何をしたら良いかわからなかった オセロAIを作
リバーシプログラムの作り方 サンプル
序章 はじめに リバーシのルール ソースコードの記述について 第１章 盤面の処理 1.1 定数と関数の定義 1.2 盤面の生成、初期化 1.3 石を返す処理 1.4 返せる石数を調べる処理 1.5 盤面をコピー、反転させる処理 1.6 その他の盤面処理 1.7 盤面の操作と表示 第２章 ゲーム木と探索 2.1 コンピュータ思考の関数定義 2.2 各関数の実装 2.3 ゲーム木 2.4 MinMax法とNegaMax法 2.5 αβ法 第３章 盤面の評価 3.1 評価関数の定義 3.2 パターンによる局面評価 3.3 評価クラスの構造 3.4 評価クラスの生成とファイルの読み書き 3.5 評価関数の実装 3.6 評価パラメータの更新 3.7 中盤の探索 3.8 自己対局による学習 第４章 性能改善 4.1 石数取得の高速化 4.2 着手の高速化 4.3 候補手リストの導入 4.4 終盤探索の
PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データベースでユニークキーにUUIDを使うメリットは何ですか？連番やタイムスタンプまたは複合などではいけないのでしょうか？どうも視認性が悪く使いにくく感じますし連番でも衝突しない気もします。
30 分でわかる！アルゴリズムの基本
