ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita
0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
日本語形態素解析の裏側を覗く！MeCab はどのように形態素解析しているか - クックパッド開発者ブログ
こんにちは、買物情報事業部の荒引 (@a_bicky) です。 前回、「検索結果の疑問を解消するための検索の基礎」で単語単位でインデキシングする前提で説明しましたが、今回は文などを単語単位で分割するために使う技術である形態素解析について触れます。 形態素解析器には色々ありますが、中でもメジャーと思われる MeCab の仕組みについて説明します。 MeCab の解析精度を上げるために辞書に単語を追加したことのある方もいると思いますが、動作原理を理解することで単語を追加する際に適切な生起コストを設定できるようになったり、学習の際に適切なパラメータを設定できるようになったりするはずです。 なお、MeCab は汎用テキスト変換ツールとしても使用できます が、簡単のため MeCab + IPA 辞書のデフォルト設定前提で説明します。 アジェンダ 形態素解析とは MeCab における最適な解析結果の推
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
ゲームAI -基礎編- 『知識表現と影響マップ』
みなさん、こんにちは! 突然ですが…皆さんには、ひいきにしている ゲームのキャラクターはいらっしゃいますでしょうか。 手ごわいボス敵や頼れるパートナー、愛嬌のある動きをするモンスター達は 一体どのような仕組みで動いているのでしょう？ 今回の記事ではそんなゲームの中のキャラクター達を 魅力的に動かす仕組み、AIについて御紹介したいと思います。 改めまして本記事を担当させて頂きます、Cygamesエンジニアの佐藤です。 これまでコンシューマ機でのゲームAI開発に携わり、 ゲームならではのキャラクター表現の楽しさを追いかけてきました。 このブログを通じて、皆さんのゲームのキャラクターを より表情豊かに魅力的なものにする方法について、皆さんと一緒に考えていければ幸いです。 今回はゲームのAIをデザインするにあたって重要となる、 「知識表現を定義する」というステップと、 知識表現の一つである影響マッ
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
二次元画像を拡大したいと思ったことはありませんか？ - デー
うまくできましたか？ ボヤけたり、ギザギザになったりしませんでしたか？ waifu2xをお試しください。 (ブラウザの処理に影響されないようクリックで拡大おねがいします) waifu2xは、二次元画像を2倍に拡大するソフトウェアです。多くの二次元画像についてスゴイ級のクオリティで拡大できます。 waifu2xは、最新鋭の人工知能技術 Deep Convolutional Neural Networks を使って開発されました。 waifu2xの人工知能は、次の問に答えます。 いまから与える画像はある画像を半分に縮小したものである。縮小される前の画像を求めよ。 画像を拡大するのではなく、縮小される前の状態に戻します。 縮小されてないオリジナル画像を与えた場合も、やはり縮小される前の画像を答えます。 その画像は本来存在しないものですが、waifu2xはそれを想像で創ります。 二次元画像のJPE
テキサスホールデム（ポーカー）の必勝プログラムが完成 ついに不完全情報ゲームでもコンピュータが人間を上回る | ねとらぼ
カナダのアルバータ大学は1月9日（日本時間）、ヘッズアップリミットホールデム（ポーカーの1種）において、コンピュータソフト「Cepheus」が“完全プレイ”を解析したと発表しました。研究成果をまとめた論文が米科学誌サイエンス（電子版）に掲載されています。 ヘッズアップリミットホールデムとは、手札2枚と共通カード（最大5枚）を組み合わせる「テキサスホールデム」という形式を1対1（ヘッズアップ）で行うもの。リミットとは賭け金が決められているタイプです（有り金を全部賭けるオールインなどは不可）。 つまり、同ゲームでは一定額ずつチップをかけての勝負（降りてもよい）を何度も行います。これを長期的にプレイすると「Cepheus」は絶対に負けないそうです。ポーカーは「不完全情報ゲーム」であり、相手の手札がわからないことからブラフも有効でしたが、リミットゲームにおいてはこのたび実質的な“完全解”が求められ
正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話 | カメリオ開発者ブログ
あけましておめでとうございます。白ヤギの物理担当、シバタアキラ(@punkphysicist)です。 皆様はどんなお正月を過ごされましたか？日本の正月といえば、おせち、日本酒、おばあちゃん、そしてパズル、ですよね。私の正月はそんな感じでした。お節をたらふく食べ、美味しいお酒でほろ酔い気分になっている私の横で、黙々とおばあちゃんがパズルをやっているのに気づいたのです。部屋中をフワフワしている私とは全く対照的に、微動だにせずパズルを続けるおばあちゃん。御年迎えられると辛抱強さが半端ない。 そんなおばあちゃんがやっていたのはかわいいチョコレートのピースとは裏腹にこんな挑発的な文言の書かれたパズルです（この記事はアフィリエイトではありませんが、写真をクリックすると買えます） 何時間たっても答えが出ないおばあちゃん、辛抱強さは人一倍強いですが、私も何とか助けてあげたいと思いトライ。しかし日本酒が・・
Situs Judi Slot Online Terlengkap dan Terpercaya Indonesia
MORE INFORMATION Nama : QQDeluxe Website : http://qqdeluxe6.com Server : QQSLOT Negara : Indonesia Min Deposit : Rp 20.000 Deposit via : Bank, Pulsa, E-wallet Platform : Windows, IOS, Android Situs Slot Indonesia, Judi Slot Online Terpercaya Game Slot Online merupakan jenis permainan yang saat ini menjadi primadona di kalangan masyarakat Indonesia. Permainan slot online memiliki sistem yang sangat
Evernote Synchronization via EDAMを読みました - soutaroブログ
Documentation - Evernote Developersの「Synchronization spec」の文書です。こういうWebサービスとクライアントアプリがいて、データ同期をとるようなアルゴリズムって、別に難しいことはないような気もしますが、一方で綺麗に書くためのベストプラクティスってなかなか見つからないような気がします。まあ力技でなんとかなるとも思いますが、それはそれとして上手くやる方法をずっと探していました。例えばgitとかちょっと機能が豊富すぎるし、Unisonとかそれはまたちょっと違うし。 こないだ気づいたのですが、Evernoteってローカルなキャッシュが存在することがかなり前提のサービスですよね。で、APIのドキュメントを見てみたらそんな感じのドキュメントがありました、という話。今となってみれば、けっこう当たり前の話ですよねーという感じだったので、一年くらい読む
wavelet行列で高速な「もしかして友だち？」検索 | 株式会社サイバーエージェント
業務経歴： Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。 アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。 好きな分野はグラフ探索とチューリングマシン。 ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。 つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。 そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。 しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。 即ち、「つながり」類似度の算出には時間がかかる、ということです。 この「つながり」類似度算出
Chronoつくった - ✘╹◡╹✘
* * * * * T T T T T | | | | `- wday --- 0 .. 6 | | | `--- month -- 1 .. 12 | | `----- day ---- 1 .. 31 | `------- hour --- 0 .. 23 `--------- minute - 0 .. 59 https://github.com/r7kamura/chrono Rubyでcron形式の構文を利用するために、Chronoというライブラリをつくった。開発動機はRubotyというHubotクローンで利用するためで、チャットからcron形式でジョブを登録することで定期的に発言をしてくれるような機能をつくろうと考えてた (こういうやつ)。 既存のもの clockwork - A clock process to replace cron rufus-scheduler - J
NSArrayやNSDictionaryからNSNullを効率よく取り除く - 24/7 twenty-four seven
iOSアプリケーションでWeb APIから返ってきたJSONを処理するのにNSNullの扱いに困っていて、事前にNSNullを取り除いてしまうのが事故を防ぐための確実な方法なのですが、再帰的にすべての要素を検査する以外になにかいい方法がないかと思って考えていたらちょっとおもしろい方法を思いついたので書いてみました。 kishikawakatsumi/CollectionUtils · GitHub ↑ に含まれるCUCompactArrayとCUCompactDictionaryです。 NSArrayとNSDictionaryのサブクラスとして実装されていて、次のようにして生成します。 （普通にalloc/initを使って生成することも可能です） NSArray *array = @[@"0", @"1", [NSNull null], @"2", [NSNull null], @"3"]
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
PageRankアルゴリズムを使った人事評価実験 | 株式会社サイバーエージェント
2-2-1.一般的な360度評価による評価方法 問題点 一般的に評価プロセスが公開されていないため、最終評価までのプロセスが不透明である 全員が全員を評価するのは多数の社員がいる場合は不可能である ランダム抽出によるお互いの評価を行うと、まったく違う専門分野を評価したり、まったく関わりあいのない人を評価することになり精度が下がる 2-2-2.専門分野での評価者による評価方法 問題点 *評価者になる人材の不足 高い専門スキル、会社とのビジョンマッチ、メンバーからのその専門分野での高い信頼の全てを備えている人材が専門分野毎に必要。 さらに、評価の納得性を保つためにはメンバーからの信頼がある人材ではないと評価できない。 *評価者によって評価ポイントの違いがある 同じ分野の技術者でも、スキルの価値をどこに置いているかというスタンスの違いから評価ポイントにゆらぎが発生する。 さらに評価者自体
『ピグ麻雀のアルゴリズム』
皆様初めまして。 12年度新卒のぱっとしない方のハカマタです。 アメーバピグの制作部署で、サーバサイドエンジニアとして陰ながら頑張っています。 さて、突然の告白ですが最近私は仕事中にアメーバピグで麻雀をしています。 しかし私は今まで一度たりとも叱られたことがありません。 それは、私が叱責に耐えうるメンタルが無いと先輩方に諦められているからでしょうか？ 違います、私は麻雀ゲームの制作者メンバーで、デバッグという名目で、ピグで麻雀をしているためです。 本日の記事は、ピグでリリースしたピグ麻雀についてお話します。 ピグ麻雀はエンジニア・ディベロッパー・デザイナー各1名で制作したもので、 私はエンジニアとして参加しました。 サイバーエージェントのクリエイターブログに過去の記事として、デザイナーの鈴木さんの記事『ピグ麻雀におけるデザインのポイント』と、ディベロッパーの鈴木さんの記事『ピグ麻雀がリリー
最近投げたpull requestとかソーシャルコーディングとかリファクタリング - ainameの日記
RubyMotionを相変わらずいじってるのだけど、最近は業務に疲れてあんまり趣味開発が捗ってない。 趣味開発しようとする前に使うgemがまだいい感じに枯れてないので不満が出るからまずそっちを直そうみたいなことを繰り返している気がする。 最近直したgemで、ibというRubyMotionでInterface Builderを使うために、app/*以下のRubyのコードをparseして、Outletとかが定義されたダミーヘッダーファイルを作ってくれる奴がある。 $ rake ib:open というコマンドを叩くとローカルにib.xcodeprojを作ってくれて、その中にあるStubs.hとxibファイルをマウスでうにょーってoutletの連携する事ができる。 吐き出してくれるStubs.hには、OSXアプリを作る時は#import <UIKit/UIkit.h>じゃなくて、#import <
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SciPy — SciPy v0.14.0 Reference Guide