機械学習に魂を売ったコンピュータ将棋 - 武蔵野日記
今月号の会誌「情報処理」(2010年8月号目次)の特集は「コンピュータ将棋の不遜な挑戦」というタイトルで、ここ数年のコンピュータ将棋の発展の技術的な解説。こうやって毎年のように情報がアップデートされると非常にありがたい。 見所は鶴岡さんによる「選手権優勝記--激指の技術的改良の解説--」とktanaka先生・kanekoさんによる「大規模クラスタシステムでの実行--GPS将棋の試み--」の2記事。特に鶴岡さんによる記事は、Bonanza のよい解説にもなっており、必読である。実は、激指は 評価関数というのは，局面の形勢判断をコンピュータで行うための関数で，任意の与えられた局面に対して，どちらがどれだけ有利なのかを数値化する関数である．[...] このようなパラメータの調整は非常に手間のかかる作業だが，かつては完全に手作業で行われており，将棋プログラム開発における作業の多くの割合を占めていた
yebo blog: ルービックキューブはどんなポジションでも20回動かせば解決
2010/08/10 ルービックキューブはどんなポジションでも20回動かせば解決 Googleからコンピュータの空き時間として35CPU年を提供してもらい、ルービックキューブの全てのポジションにおける解法を調べたところ、どんなポジションでも20回動かせば解決できる事が分かったそうだ。神のアルゴリズム(ルービックキューブを解くアルゴリズム)が年々短くなってきているのが分かる。キューブの全てのポジションは43,252,003,274,489,856,000との事で、どうやってそれが分かったかというと、19,508,428,800ポジション毎の2,217,093,120セットに分類対称と集合(set covering)を使って解決すべきセットを55,882,296に抑えるそれぞれのポジションの最適解を見つけれなかったが、代わりに20以下の解決法だけを見つける約20秒で1つのセットを解決するプログ
コンピュータサイエンス史上最大の課題「並列処理による性能向上」～情報処理学会創立50周年記念全国大会の招待講演
「いま、並列処理の壁というコンピュータサイエンス史上最大の課題に直面しています。しかしこれはチャンスでもあります。新しい時代を切り開いていきましょう」。IBM名誉フェローのFran Allen氏は、昨日3月10日に行われた日本の情報処理学会創立50周年記念全国大会の招待講演の演壇からこんなメッセージを聴衆に投げかけました。 Fran Allen氏は、コンパイラやプログラミング言語が専門で、女性で初めてチューリング賞を受賞した人。今回の招待講演のためにわざわざ来日したと紹介されました。 講演のタイトルは「The Challenge of the Multicores」。ここからは、Allen氏の講演の内容を紹介しましょう。 （この講演は英語で行われたものです。内容にはできるだけ正確を期したつもりですが、理解不足のところや聞き取れなかったところもありました。もし誤解や不正確なところがありました
就職活動インタビュー反省記録 with Yahoo
Yahoo とのインタビューは、明らかに失敗だったとインタビュー中に分かったケースです。というのも、電話インタビューの最中に私のプリペイドの携帯の残高がゼロになり、会話が 8 分も途切れてしまったからです。前回残高を追加したのが夏学期の途中だったので、残高をチェックするのを忘れて、電話インタビューをしてしまいました。これは問答無用でアウトです ;( だって、interviewer からしてみれば、「おいおい、こっちは貴重な勤務時間を割いてインタビューしてるのに、残高ゼロで会話できませんってどういうことだよ。スキル以前の問題じゃないか」て思いますもんね、普通。 このインタビューに関しては、反省すべき点は火を見るより明らかなので、以降は Yahoo にアプライした経緯やインタビューで聞かれた問題を紹介したいと思います。 私がアプライしたのは、Back End Engineer、Qualit
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer ::SEM R (#SEMR)
「ランキングアルゴリズムを1日当たり2回変更している」 Google Marissa Mayer グーグル・マリッサ・メイヤーのインタビュー記事。1日2回と小さな改良をランキングアルゴリズムに加えていき、検索をユーザにとってより便利なものにしていく。 公開日時：2009年11月12日 13:27 米Google VP・Marissa Mayer氏のインタビュー記事。ユーザがわかる範囲で週あたり2～5の変更を加えているほか、ランキングアルゴリズムも1日2回ほどの割合で変更を加えていると答えている。日々小さな改良を加えて、検索をより便利なものにしている。 また、2007年5月から始まったユニバーサル検索は現在、全検索クエリの25%で表示されているとも説明。 We have two, three, five changes every week that are visible to the e
驚くべきテクニックで「スーパーマリオ」をクリアしていく人工知能
ゲームがゲームをクリアする時代に？ 「New スーパーマリオブラザーズ Wii」で、初心者向けに新しく搭載されるという噂の「スキップ機能」は、もしかしたらこんな感じなのかもしれません。 土管や砲台、敵キャラクターなど多くの障害物が設置されたコース上を、驚くべきスムーズさで、マリオがひたすら右へ右へと進んでいくこちらの動画。迫りくる敵の間を難なくすり抜けたり、パックンフラワーの間をギリギリでくぐり抜けていったりと、確かに上手いプレイであることは分かるのですが、何かがちょっと違うことに気付いたでしょうか。 実はこれ、すべてAI制御による自動プレイ。マリオの前方に表示されている赤い放物線は、この先進むルートの候補を表したもので、どうやらこの中から安全で、なおかつ最短でゴールにたどり着けるルートを自動で選択するようプログラムされているようです。途中、何度かはヒヤリとさせられる場面もあるのですが、き
お手軽に強い将棋プログラムを作る10の方法 - aki.の日記 (2009-02-19)
猛暑を乗り切った服・小物・その他 とにかく2025年の夏は暑かった。 と、毎年言っている気がするけど、今年は特別暑かったのではないか。これが地球温暖化なのだと見せつけられているような気がする。スノーボーダーとしてはそれに全力で抗う必要があるんだけど、自分の態度がまだ追いついていない。 生…
SSD がコモディティになっても状況はかわらない - kazuhoのメモ置き場
脊髄反射。 Oracle や MySQL など近年の RDBMS はインデックスのデータ構造にB木 (の変種) を採用していますが、その理由はここにあります。 SSD がコモディティになると状況は変わる (中略) 二次記憶上での検索用のインデックスにはこれまで B木のようなディスクに最適なデータ構造が必然的に選択されてきましたが、SSD に変わると、現実的に利用可能なデータ構造にも幅が出て、アプリケーションによっては劇的な改善が可能になるというわけです。 この先 SSD の普及によって、色々なソフトウェアで、驚くような改善が行われる機会を目にすることが多くなるのではないかと思います。その時、単に SSD に変わったから速くなったと捉えるのではなく、どのようなデータ構造が選択されて、そのデータ構造の特性が SSD とどのようにマッチしたのかという視点で見ていくことが大切ではないかと思います。
孤独なプログラマー : 新規保存で劣化していくJPEG形式の画像の様子をとらえ・・・てない気がする
2009年04月19日14:08 カテゴリ 新規保存で劣化していくJPEG形式の画像の様子をとらえ・・・てない気がする ソースコードを見ると、 ＞ float q = map(i,0,numberOfFrames,1,0);＞ p.setQuality(q,true); だから、多分0〜numberOfFramesまでの間にあるiを1〜0にマッピングして、それをJPEGの圧縮率に指定しているんだと思う。 記事内容見ると「JPEG形式で保存を繰り返すだけで画像がどんどん劣化していき、最後は見るも無残なことに」と解釈されているみたい。でも、それならsetQualityに設定されるべき値は一定であるべきだと思うんだけどなーー ということで実験実験。 --- A=0 while [ $A -lt 6000] do echo "$A" OLD=`expr $A` A=`expr $A + 1` co
新規保存で劣化していくJPEG形式の画像の様子をとらえたムービー
JPEG形式の画像は基本的に非可逆圧縮で、保存するたびに劣化してしまいます。1度や2度の保存では違いが分かりにくいのですが、保存を繰り返すことですぐに分かるほどに劣化していきます。そんな少しずつ圧縮されて劣化する画像の様子がムービーでまとめられていたのでご紹介します。 詳細は以下から。 新規保存を600回繰り返して劣化していく20秒のムービー。 GENERATION LOSS | HADTO.NET 4秒(約120回)付近で明らかな違いが出ています。 10秒(約300回)付近。粒状感たっぷり。 もう空には見えません。 最終的にはテレビの砂嵐のような画像になっています。 2009/04/19 22:04追記 これは単純に同じ圧縮率でJPEG保存を繰り返しているのではなく、少しずつ圧縮率を上昇させていって保存した画像をつなげたムービー。プログラムのコードの中身としては、MAPクラスとJPEGの
2の冪 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "2の冪" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年6月) 2の冪 2n の直方体による図示。 左上1 (=20) から右下 1024 (=210) まで。 2の冪（にのべき、（英: power of two）は、2 を底とし整数の指数を持つ冪である。2の冪は、指数を n として一般に、2n の形で表される（例えば n = 0, 1, 2, 3, … に対してそれぞれ 20 = 1, 21 = 2, 22 = 4, 23 = 8, …）。 1に2倍のみを繰り返すことによって得られる数であり、ごく基本的な数量操作で得られる
GIFライセンス問題についてわかるページ
【集中企画】 GIFライセンス問題についてわかるページ さきごろ、Webブラウザーやメールソフトなど、Internet Explorer（IE）コンポーネントを呼び出しているソフトがいくつか、公開中止や仕様変更となった。これは、GIFフォーマットで使われているLZW圧縮伸張アルゴリズムに関して米Unisysが特許を持っており、これを使ったソフトを開発するにはライセンスを受ける必要があることによるもの。Microsoftは自社のライセンスについて、Microsoft製品を部品として使う開発者には適用されないと声明しており、ソフト作者がライセンス違反を懸念して今回の動きとなった。 今回の集中企画では、このGIF（LZW）ライセンス問題についてWebで論じているページを見てみる。 注意：ここで紹介するのはあくまでも各サイトの論点であり、その見解そのものを保証するものではありません。
3 NOT problem - あどけない話
和田先生が紹介されていた3 NOT problemを解こうといろいろ考えましたが、結局できませんでした。orz 答えが分らないと、気になって次の仕事に進めないので、検索して答えを見つけました。 Haskell でアルゴリズムを書いておきます。 import Data.Bits input = map triple [0..7] where triple :: Int -> (Bool,Bool,Bool) triple n = (testBit n 2,testBit n 1,testBit n 0) output = map (\(x,y,z) -> (not x, not y, not z)) input threeNot (x,y,z) = let aa = y && z ab = x && z ac = x && y ad = y || z ba = x && aa bc = x
パラメトロン計算機
久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした. 翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである. 短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ. 私がやっても多分こういうアプローチになるであろうという風に話は展開していく. まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒. 次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見る
フランスの地でアルゴリズムの未来を切り開く男 高橋直大
Microsoftが主催する学生向けの技術コンテスト「Imagine Cup」。そのアルゴリズム部門で世界の頂点に挑むのは、プログラミング歴が2年にも満たない一人の数学好きだった。 Microsoftが主催し、全世界の学生を対象にする技術コンテスト「Imagine Cup」。今年は日本時間の7月4日からフランスのパリで開催される。幾つかの部門が用意されているが、その中の1つであるアルゴリズム部門の日本代表としてフランスの地を踏んだことで、この男の今後はどのように変化するのだろうか。 Imagine Cupのアルゴリズム部門で世界大会に進むのはわずか6名。高橋氏についてもアルゴリズム部門日本代表というよりは、ファイナリストと表記した方が正確だろう。このファイナリスト6名が24時間で10問の問題に挑み、世界の頂点を目指す。今回は、7月3日に20歳の誕生日を迎え、大きな変化の波のまっただ中にいる
ユビキタスの街角: Knuth先生にアルゴリズムを教えたよ
Donald Knuth先生の 弟子の播口さんに誘われて、 Knuth先生と夕食を御一緒させていただいた。 185cm以上はある大きな人で、想像よりも若かった。 1938年生まれだからまだ70歳らしい。 とても頭が良さそうな顔をしている。当たり前か。 世間話の中で先生の執筆環境について聞いてみた。 M: 「文章書きとかどういう環境でやってるですか?」 K: 「大きなマシンも使ってるけど文章とかはLinuxノーパソでEmacsだね」 M: 「Emacsなんですか。仕様が変で困ったりしませんか?」 K: 「変な機能は使わないからね。自分で色々カスタマイズしてるし」 K: 「たとえば行に色をつけるElispを使ってる。参考文献リストとか書くときに、 大事なのとそうじゃないので色を変えるんだ」 K: 「CWEBを書くための仕組みも作ってる。まだ書いてないモジュールのリストは全部 木構造でダンプして
書評 - javaによるアルゴリズム事典 : 404 Blog Not Found
2006年11月05日21:15 カテゴリ書評/画評/品評 書評 - javaによるアルゴリズム事典 土と芋とユンボに戯れ、ご機嫌で過ごした三連休の最後をしめくくるかのように宅配ボックスに入っていたのがこちら。 javaによるアルゴリズム事典 奥村 晴彦他 404 Blog Not Found:Mastering Algorithms with Perl-siuyeさんのコメントjava版が数年前出てましたよ。＞アルゴリズム辞典 を見て注文のが本書「javaによるアルゴリズム事典」、なのだけど.... これは、ヨイショしづらい。 まず、コード。あまりに「C言語による最新アルゴリズム事典」からのコピペが多い。 int main (int argc, char **argv){ /* コードはこちら */ } を、 class Example{ public void main(String[
2007-12-22
牧野さん，ありがとうございます． http://grape.mtk.nao.ac.jp/~makino/journal/journal-2007-12.html#20 書くことで整理するっていうのは確かだと思いますね．ただ私の場合は本にすることを目的にして書くよりもまず散発的な文章をいくつか書いて，考えを整理してから本を書く段にうつったほうがいいと思います．あまりにもダメなので． それで，またああいえばこういうみたいですけど，記号でできるといっても「実数a,bを入力してその和を出力するプログラム」が本当に「a+b」という記号を返してもなんだかなーという気はしますけど (例が悪いですが)． できなかった…．HDを認識してくれない．BIOSでは認識されてるんだけども．月曜日に再チャレンジ．
2007-12-19
牧野さんにちょっと質問されている気がするので，書きます．私の「アルゴリズムとプログラム」についてコメントですが． http://grape.mtk.nao.ac.jp/~makino/journal/journal-2007-12.html#18 個人的には「キャッシュ再利用のための方法や並列化のための方法」というのもアルゴリズムだと思っていて，私の書いたアルゴリズムの説明 (私自身は定義だとあんまり思ってませんが) にも外れないとは思うんです．しかし，おそらくアルゴリズムとプログラムを対比させてしまったのがよくなくて，「アルゴリズムはプログラムとして実現されなくてはならない」ような印象を文章からは受けてしまいますね．でも，アルゴリズムはプログラムとして (ソフトウェア的に) 実現されていなくてもよいですし，ハードウェア的でもよいですし，そうでなくても，例えば人間が手を動かしてソートとかし
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ベイジアンアルゴリズムは効くのか? - アメリカでがんばりましょう