エンターテイメントと認知科学研究ステーション/講演会/20060821
・第5回招待講演会 開催日：2008年６月１４日（土）13時から18時頃まで 場所：電気通信大学 西９号館３階ＡＶホール 参加無料（事前申し込み不要） ------------------------------------------------------------------------- 13:00-14:30 「コンピュータ囲碁におけるモンテカルロ法」（理論編） ←発表資料 美添 一樹氏（科学技術振興機構 研究員） 概要 囲碁は，主なボードゲームの中でコンピュータの挑戦を拒み続けてきた唯一の ゲームである．囲碁の難しさは良い評価関数を作ることが困難であるということ に起因していた． しかし2006年にコンピュータ囲碁の世界に全く新しいアルゴリズムがもたらさ れた．評価関数が不要という画期的な探索アルゴリズム，通称，モンテカルロ木 探索と呼ばれるものである．登場から2年あまりで9
『【DiGRA公開講座】モンテカルロ木探索とは何か？』
将棋と比べて囲碁の評価関数を難しくしているのは、 ・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。 ・リバーシにおける角のように、明らかな特徴を持った場所が少ない。 ・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。 ・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。 などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。 ・石の厚い薄い 石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。 ・形の良し悪し 複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。 「代表的な悪い形」 ┼┼┼┼┼┼ ┼┼●┼┼┼ ┼┼●●┼┼ アキ三角 ┼┼┼┼┼┼ ┼┼●
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
Web上の膨大な写真からローマを1日で構築する方法 - A Successful Failure
前回、『写真に基づく3D空間構築手法の到達点』としてバラバラの写真から3D空間を構築する手法について取り上げた。コメントで言及された人もおられたが、MicrosoftはPhotosynthとして、同様にStructure-from-Motion (SfM)を用いて写真をつなぎ合わせ、インタラクティブにブラウズできるPhotosynthを公開している。 Photosynth Overhead View on Vimeo Photosynth + Bing Maps on Vimeo 現在、研究レベルではWeb上にアップされた不特定多数のユーザによる膨大な写真から街一つを再現するプロジェクトが推進されている。その名も"Building Rome in a Day"（ローマを一日にして成す）だ。下の動画はFlickr検索された画像から生成された3Dモデルを示している。本エントリでは、論文*1に基
計算機プログラムの構造と解釈 第二版
[ 目次, 前節, 次節, 索引 ] 2014-03-06 更新 [ 目次, 前節, 次節, 索引 ]
パターン認識の人手最強伝説 - 武蔵野日記
午前中は機械学習の基礎勉強会の最終回。1冊全部通読できてよかった。 昼から研究室配属の説明会。誰がうちの研究室を希望してくれるかな？ 連続して学部3年生のプロジェクト実習の最終発表会。学生たちが各自チームで半年間研究した成果を発表してくれた。トップバッターの女の子4人組チームがとてもプレゼンがうまく、出した数値も段違いによく、他のチームのほぼダブルスコアで、最優秀発表賞を受賞していた。ポスター発表を聞くと、ポスターにはアルゴリズムが前面に書かれていたが、質問してみたところアルゴリズムが問題なのではなく、驚くべき手法によってその精度が達成されていた。 タスクは顔画像認識で、人物の映る画像が与えられたとき、それが誰か当てるという課題。ただ、この実験は設定が特殊で、画像に手を加えてもいいことになっていた。そこで、彼女たちは数千枚の写真画像からなる訓練事例とテスト事例の両方で、まず顔の中心点を決め
「捨て駒」がなんだかわかってない奴、多杉 - やねうらおブログ(移転しました)
今日は『将棋世界』の取材があるのだが、将棋のこと考えていたら寝れないので将棋について日頃思っていることをぶちまけてみる。 もう何度目にしたかわからないのだが、小説やドラマでよく「捨て駒のように俺を粗末に扱いやがって」みたいな表現が出てくるのだが、これが将棋指しから見ると極めておかしい、誤った表現である。将棋について理解のない人にとって「捨て駒」とはそういう認識なのだろうが…。今回はこのことについて詳しく説明する。 まず、将棋は捕獲した駒を手駒に出来る。これはチェスとは違った特徴である。チェスは手駒という概念がないので、取った駒はただ盤上から消えていく。将棋は違う。手駒になる。銀は４枚しかなく、初期盤面では先後２枚ずつ割り振られているが、相手から１枚取るとこちらは盤上に２枚、手駒で１枚と併せて３枚になる。相手は盤上に１枚だけであるから、３対１の戦力になる。 銀の価値が300点だとしたら、相手
Python Speed - www.peignot.net
多くの人々が頻繁にPythonプログラムの実行速度を心配しています。でもPythonを使わないと、堪らないくらいパフォーマンスのロスがありますよね？ 中には「なんだ、インタプリタのスクリプト言語か、まるっきり遅いや」なんて結論づける人もいます。その一方で、Pythonを実際に試してみて、十分な実行効率をもっていることに気づいた人もいます。もちろん、時にはとっても遅いプログラムができあがることもあります。 なぜ素のスピードが重要か？ あるいは重要でないか?多くの人が必要以上に速度に取りつかれていて、この種の問題ではCが優れた実績を示していることから、（Cが）全ての面で優れた言語であると考えています。他の人々は「開発の速度」がより重要で、Pythonを選ぶのはそのような時に限り、まあそれなりの速度だろうと考えています。そして頻繁に、Pythonのコードが期待以上の速度で動いていることに彼らは驚
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
単純ベイズ分類器 - Wikipedia
単純ベイズ分類器（たんじゅんベイズぶんるいき、英: Naive Bayes classifier）は、単純な確率的分類器である。 単純ベイズ分類器の元となる確率モデルは強い（単純な）独立性仮定と共にベイズの定理を適用することに基づいており、より正確に言えば「独立特徴モデル; independent feature model」と呼ぶべきものである。 確率モデルの性質に基づいて、単純ベイズ分類器は教師あり学習の設定で効率的に訓練可能である。多くの実用例では、単純ベイズ分類器のパラメータ推定には最尤法が使われる。つまり、単純ベイズ分類器を使用するにあたって、ベイズ確率やその他のベイズ的手法を使う必要はない。 設計も仮定も非常に単純であるにもかかわらず、単純ベイズ分類器は複雑な実世界の状況において、期待よりもずっとうまく働く。近頃、ベイズ分類問題の注意深い解析によって、単純ベイズ分類器の効率性に
ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。 はじめに 昨今のコンピュータビジョン・パターン認識分野で特徴ベクトルのバイナリベースの記述法が流行っています。その利点の一つとして、特徴ベクトル間の距離としてコンピュータにとって計算が容易な「ハミング距離」が使える、というものがあります。これはXOR演算と PopCount演算（いくつのビットが1かをカウントする演算）で構成されており、特に近年のCPUにはまず搭載されているベクトル計算命令セットの一つ「SSE4.2」の専用命令「POPCNT」が高速演算の根拠としてよく引き合いに出されます。二つともかなりプリミティブな命令ですから確かに高速に計算できそうな感じはします。しかしながら、例えばL
いもす法 - いもす研 (imos laboratory)
いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています． いもす法の基本: 1 次元 0 次いもす法 最もシンプルな「いもす法」は 1 次元上に 0 次関数（矩形関数や階段関数などのように上部が平らな関数）を足すものです． 問題例 あなたは喫茶店を経営しています．あなたの喫茶店を訪れたそれぞれのお客さん i\ (0 \leq i \lt C) について入店時刻 S_i と出店時刻 E_i が与えられます（0 \leq S_i \lt E_i \leq T）．同時刻にお店にいた客の数の最大値 M はいくつでしょうか．ただし，同時刻に出店と入店がある場
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
正規表現入門 星の高さを求めて
Programming Praxis – Dijkstra’s Algorithm
How to implement Dijkstra Algorithm in Haskell
Sign in - Google Accounts
Change-Point Analysis: A Powerful New Tool For Detecting Changes - Taylor Enterprises