2048 の AI を読んでみた - はやくプログラムになりたい
以前第一回2048AIコンテスト 結果報告という記事を見かけて，興味がわいたので 2048 の AI について調べてみました． 2048 は 4x4 のパズルゲームで，ルールは実際にやってもらったほうが分かりやすいぐらい簡単なものですが，テンポが良くて結構ハマりました． 今回は公開されている 2048 の AI の中で一番メジャーっぽいものを TokyoVim #19 で読んでみました． ov3y/2048-AI - Github 小並感 平穏な感じ AI でした． js/grid.js に各評価関数の定義があり，js/ai.js に探索を行うメインの部分の処理があります． 評価関数 良い手を選ぶには，ある盤面が与えられたときにその盤面がどれだけ有利な状態かを知る必要があります．それを知るために必要なのが評価関数で，今回だと 2048 の 4x4 の盤面を引数に取り，その盤面のスコアを返す
世界中の空港の位置を「ボロノイ図」で表現した「World Airports Voronoi」
普段見慣れた世界地図でも、いつもより見る視点や区切り方を変えてみると全く違った形が見えてくることもあります。世界中の空港を他のどの空港に近いかによってエリア分割し、通常の地図に重ねて示したみたのが「World Airports Voronoi」です。 World Airports Voronoi https://www.jasondavies.com/maps/voronoi/airports/ (*リンク先のページは描画に時間がかかる場合があります。PC環境推奨) 「ボロノイ図」というのは「ランダムに並んだ複数の点が存在している時、それぞれの点から距離の等しい位置を通る線(垂直二等分線)を引き、点ごとの領域を示した図」です。文字で書くとわかりづらいですが、小学校の学区割りで、近隣の学校との距離を計算して極端に通学距離が長くならないようにエリア分けしたりするときに使われます。 「World
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
D:\Docs\Submitted_papers\2005RandomDouble\randomdouble.dvi
Conversion of High-Period Random Numbers to Floating Point JURGEN A DOORNIK University of Oxford Conversion of unsigned 32-bit random integers to double precision floating point is discussed. It is shown that the standard practice can be unnecessarily slow and inflexible. It is argued that simulation experiments could benefit from making better use of the available precision. Categories and Subjec
実践・最強最速のアルゴリズム勉強会 第五回講義資料(ワークスアプリケーションズ & AtCoder)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
実践・最強最速のアルゴリズム勉強会 第三回講義資料(ワークスアプリケーションズ & AtCoder)
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder)
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功 | 筑波大学 計算科学研究センター
概要 筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。 魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算
ビットコインの応用で、電子書籍を譲渡可能にするアルゴリズム
サトウヒロシ🐰 @satobtc (1)今日は、ビットコインの経済的側面ではなく、技術的側面から可能になる未来像について、連続ツイートします。 ビットコインのP2Pネットワークは、あるデジタルデータ（コインでは残高＝お金としている）の所有権を中央の認証機関なしに移転することができるというものです。 2014-02-24 15:42:36 サトウヒロシ🐰 @satobtc (2)これは、計算機科学的にいうとビザンチン将軍問題というもので、だれか管理者がいなくても分散型のコンピュータはお互いに故障や正しいデータを識別できるか、といったような問題です。これに対する実用的なはじめての回答がビットコイン的な仕組みです。 2014-02-24 15:43:49
直積量子化(Product Quantization)を用いた近似最近傍探索についての簡単な解説
"aka motsu-nabe" by chatani 概要 冬の寒さも一段と厳しくなってまいりました。おでんや鍋が恋しくなる季節です。 さて、最近ようやっと一仕事が終わりまして、長ったらしい記事が書けるようになりました。ですので、今回は2011年にTPAMIで発表された、近似最近傍探索についての論文『Product quantization for nearest neighbor search』について簡単に紹介したいと思います。 この論文は2011年に発表された、最近傍探索アルゴリズムの決定打です。シンプルな理論でありながら既存手法を打ち破るほどの強力な性能を有し、速度も非常に高速、かつ省メモリなのでスマートフォンに載せ、リアルタイムで動作させることも可能です。 以前この手法はCV勉強会@関東で紹介されたらしいのですが、具体的に紹介しているページは(最近すぎるので当たり前ですが)現在
Cluster Analysis 徳山研究室M2 鈴木 晶子 発表内容 ・ クラスタリングとは ・ 大量のデータを操作するために、クラスタリン グメソッドに要求されること ・ クラスタリング技術の紹介 ‐ 分割
Cluster Analysis 徳山研究室M2 鈴木 晶子 発表内容 ・ クラスタリングとは ・ 大量のデータを操作するために、クラスタリン グメソッドに要求されること ・ クラスタリング技術の紹介 ‐ 分割法、階層的手法、密度に基づく方法、 格子に基づく方法、モデルに基づく方法 ・ Outlier detection 1 クラスタリングとは ・ クラスタリング(Clustering) ‐ データをクラス(class)またはクラスタ (cluster)にグループ化すること ‐ 同じクラスタに属するオブジェクトを比較し た時には、互いに高い類似性をもつ ‐ 異なるクラスタに属するオブジェクトを比較 した時には、高い相違性をもつ ‐ 非類似度(dissimilarity)は、オブジェクトを 記述する属性値に基づいて評価される クラスタリングの応用(1/2) ・ クラスタリングは多く
Zobrist hashing - Wikipedia
Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures [1]) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert
Finding the Majority Item in a Stream
Going through old CACM issues I discovered a paper (PDF) on stream processing. A common problem in this field is to find frequent items in a data stream when you only get one pass through the data and you need answers in real time. This is interesting in situations where you don't have enough memory to store counters for each distinct item you see in the stream. One example is keeping track of the
mod p の逆元
おめ @omeometo @ut_math 特に名前とかはなさそうですがrng-hos法とかrng-hos-ome法とか呼ぼうとしてたこともありました たとえば23^-1 mod 97を計算するなら23*4=-5 5*19=-2 2*49=1より23^-1=(-1)^2*4*19*49=38とやるだけです 2012-01-09 21:45:44
「大きなナップサック」問題解説＆最終成績発表～神級到達者30名！ #アルゴリズム｜CodeIQ MAGAZINE
出題者Ozyさんによる「大きなナップサック」問題の解説記事です。 最適解を導くためのアルゴリズムについてわかりやすい図解付きで説明してくれています。 そして、神級到達者はなんと30名！ニックネームを公開していますよ！ by CodeIQ運営事務局 はじめに 出題者のOzyです。大きなナップサック問題解説です。 今回解説するのは、ナップサック問題の中でも“単一制約の01ナップサック問題”と呼ばれる種類のものです。ちょっと長いですから、今後は単に“ナップサック問題”と表記します。ナップサックに入れる品物には、値段と重量の2要素があり、重量が“制約”に相当します。また、品物1つひとつについては、ナップサックの中に、入れる／入れないという2つの状態がありますので、これは0と1で表現できることから、“01”と呼ばれています。 大きめのナップサック問題を解く場合に用いられる手法として有名なものは、動的
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
貪欲
Takuya Akiba on Twitter: "YouTube に NII の先生達の紹介動画がこっそり置いてあることに気づいた． アルゴリズム系だと：河原林先生 https://t.co/sOzgOisdUh 宇野先生 https://t.co/vWx6Ygyx2j 定兼先生 https://t.co/zgsLaqX67D"
信号処理 | ぼくのあたまのしくみ
Wikispaces