スーパーマリオシリーズで「クリア不可能なコース」が作成できることを数学的に証明 米MITの研究者ら【研究紹介】 レバテックラボ（レバテックLAB）
米マサチューセッツ工科大学（MIT）に所属する研究者らが発表した論文「You Can’t Solve These Super Mario Bros. Levels: Undecidable Mario Games」は、任天堂のスーパーマリオシリーズの一部のゲームにおいて、プレイヤーがクリアすることが理論上不可能なコースを数学的に証明した研究報告である。 keyboard_arrow_down 研究内容 keyboard_arrow_down 研究結果 対象となったゲームは、「New スーパーマリオブラザーズ」シリーズ（オリジナル版、Wii、U、2）と、「スーパーマリオメーカー」1および2の全ゲームスタイル（スーパーマリオブラザーズ1、3、ワールド、New スーパーマリオブラザーズU、3Dワールド）である。 研究チームは、これらのゲームにおいて、ステージがクリアできるかどうかの判定が決定不可
クッキークリッカーで学ぶアルゴリズム入門 : あすなろの雑記
0. 目次 1. クッキークリッカーとは? 2. クッキークリッカー100万枚RTA 3. 解答? 4. 解答 5. 余談 6. おわりに 1. クッキークリッカーとは? 皆さんはクッキークリッカーというゲームをご存じでしょうか？ 2013年に公開され同年に日本でも爆発的に流行を見せたゲームです。知らないよという方もご安心ください、最初の方だけですがざっくり説明します。 上の画像がプレイ画面です。左にあるクッキーをクリックします。 クッキーが1枚焼けました。やったね。 クッキーが15枚貯まりました、右側にあるカーソルをクリックしてみます。 指はどこだ！？ クッキーの周りにある指が10秒に1回クッキーをクリックしてくれます。助かるー。 100枚貯まりました。アップグレード「強化された人差し指」を買ってみます。 クッキーの上に、クリックした回数分「+2」と書かれています 1回のクリックでクッキ
図解即戦力 暗号と認証のしくみと理論がこれ1冊でしっかりわかる教科書
この本の概要 テレビ会議やリモートワークが普及する中，情報を守る暗号や本人確認のための認証技術の重要性が増しています。本書は公開鍵暗号や署名などの理論を基礎から詳しく解説し，TLS1.3やHTTP/3，FIDOなどの新しい技術も紹介します。更にブロックチェーンで注目されている秘密計算，ゼロ知識証明，量子コンピュータなど最先端の話題も扱います。 こんな方におすすめ 暗号と認証の基礎を学習したい人 Web担当者やセキュリティ担当者など 1章 暗号の基礎知識 01 情報セキュリティ 情報セキュリティの三要素 情報セキュリティと暗号技術 利便性とコスト 追加された要件 02 暗号 暗号とは よい暗号と使い方 暗号の動向を知る 03 認証 パスワードによる認証 パスワード攻撃者の能力 パスワードの攻撃手法 認証の分類 認可 OAuth 04 古典暗号 シフト暗号 換字式暗号 符号化 2章 アルゴリズ
輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
ぷよぷよのアルゴリズムとMSX BASIC
再帰が現実的でないBASICで「盤面が与えられた時にどのぷよが消えるか」を計算するアルゴリズムが当時どうしても思いつかず「ぷよぷよ」にハマった時からずっと考えていました。 そしてある授業中に突然アルゴリズムがひらめきました。 以下がそのアルゴリズムのご紹介です。 フィールドが以下の様になっていると想定します。形だけ見ると「連鎖を作ろうとしてたけどやらかしちゃった」形ですね。 この場合、赤い「ぷよ」が消えることになります。 基本的な方針としては「左上から注目する場所（セル）を右下まで走査する」「注目したセルにある「ぷよ」がいくつつながっているか調べる」です。 1. まず、左上のセルに注目します。 2. 左上のセルには何も無かったので次のセルに注目します。 このセルには赤い「ぷよ」が居ました。 これ以降はこの赤い「ぷよ」がいくつつながっているか（=消せるか）をチェックします。 3.「この「ぷよ
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
解析不能！30年以上前のレトロゲームから謎の「自動生成アルゴリズム」が見つかる - ナゾロジー
Point ■レトロゲームには容量不足や技術的制約を解決するため、現代の我々から見ても解析できない謎の技術が使われていることがある ■今回、ATARI2600から82年に発売されたゲーム『Entombed』に、全くロジックが不明の迷路自動生成プログラムのコードが発見された ■迷路の壁を完全ランダムに配置すればクリア不能になってしまうが、このプログラムがなぜ通行可能なパターンで迷路を生成しているかは、まったくの謎だという ほんの数十年前、コンピュータ関連の技術が飛躍的に向上しました。 特にデータ容量の向上はめざましく、現代の若い人たちにとって容量の単位は「ギガ」が標準になっています。 しかし初代のスーパーマリオの全ゲーム容量は40KB、初代ドラゴンクエストの全容量は64KBでした。 これはこの記事のトップに貼られている画像の容量よりも遥かに小さい容量です。 レトロゲームの開発は、そんな小さな
画像のノイズを落としたり容量を小さくしたりするにはどのようなコードを書く必要があるのか？
手書きのメモをスキャンししたときにどうしても発生してしまうノイズを取り除くとともに、ファイルサイズも減らす方法を、スワースモア大学准教授のMatt Zuckerさんが具体的に公開しています。 Compressing and enhancing hand-written notes https://mzucker.github.io/2016/09/20/noteshrink.html Zuckerさんが持つクラスの中には教科書を使用せずに行うものもあり、そうした場合Zuckerさんは「学生書記官」を任命してノートを取ってもらい、スキャンしてアップロードするそうです。 例えば、以下の画像のようなページをスキャンする場合を考えてみます。この画像は300DPIでスキャンされており、約7.2MBのPNG形式で保存されています。それを画質85でJPGに変換すると約790KBになりますが、1ページで7
NVIDIAが｢この画像をあの画像っぽく｣できる高速で高品質なAIアルゴリズム｢FastPhotoStyle｣を公開
NVIDIAが｢この画像をあの画像っぽく｣できる高速で高品質なAIアルゴリズム｢FastPhotoStyle｣を公開2018.03.28 12:4531,133 たもり 本物かと見間違うクオリティ。 以前取り上げた雪原を草原に変えるAdobeのアルゴリズムなど、画風変換のアルゴリズムは何も真新しいものではありません。しかし、NVIDIAが発表したAIアルゴリズム｢FastPhotoStyle｣は、既存のアルゴリズムより各段に速い処理スピードを誇り、出来上がった画像のクオリティも高いのです。 FastPhotoStyleを開発したのは、 NVIDIAとカリフォルニア・マーセッド大学の科学者チーム。先月、｢A Closed-form Solution to Photorealistic Image Stylization｣という論文を発表しました。 PetaPixelによれば、従来のこういった
BitCoinとBlockChainにまつわる誤解ーそんなことはできない - Qiita
言いたいことを一行で BlockChainはいろいろと面倒な制約がありますので，KISSの原則を忘れないようにしましょう．権力分立の原理をどうやっても守りたいという政治的な主張がない限り，BlockChainを応用するのはナンセンスです． はじめに BitCoinの中核をなすBlockChainと呼ばれる技術が今ホットですね，いろんなところで耳にします．BlockChainとはようは皆で合意（AさんがBさんにXを渡したという取引記録）を形成していく分散型合意形成アルゴリズムです．ボランティアで参加したコンピュータ全員で協力して改ざんが困難な取引記録を作っていこうというアルゴリズムです． BlockChainアルゴリズムを銀の弾丸，あるいは魔法の杖か何かだと勘違いしている人がたくさんいて，音楽や電子書籍のデジタルライツ，はたまたマイナンバー制度の管理に使えると主張している方々をちらほら見かけ
機械学習のスタックしていた案件をFacebook Prophetで３日で返済した話 - にほんごのれんしゅう
機械学習のスタックしていた案件をFacebook Prophetで３日で返済した話 背景 広告代理店業を行なっており、クライアント企業から予算を預かって、インターネット広告やマーケティング業をしているのだが、クライアントの予算消化の異常値を監視したい 2016年半ばに外部のデータ分析専門の会社に、その日の予算消化が異常の場合、アラートを鳴らすシステムを外注開始、2016年10月に納品 2017年9月半ばに進捗率が芳しくないことが判明した。終わる見込みが立たなかったので、私が解決に当たる （ついでに"Machine Learning: The High-Interest Credit Card of Technical Debt[2]"と呼ばれる負債化してしまう機械学習のシステムとはという評価軸があったので、これらから今回使えそうなプラクティスを取り出して適応してみたいというモチベーションが
せめてはっきり言おうではないか. Googleは無能であると - yuko-hirom’s blog
デマや偽情報の拡散問題において,WELQの問題でDeNAは叩いても結局Googleを叩く人は少なかった. 私はここでまたもや大きなる権威の前では日本人はおとなしい奴隷となると言う実例を見てしまった.日本人にはGoogleほど巨大な存在に対しては盲目的に追従するのだ. bylines.news.yahoo.co.j 上記のニュース *1は見方によればGoogleはデマ情報を重要な情報としてそのリンクを編集してwebページを作成してるとも言える.ただそうしてるのがアルゴリズムか人かがDeNAやNaverまとめとの違いである. これらのサービスによって得られる負の側面はほとんど本質的には変わらないではないか？ なぜアルゴリズムがやったことは責められず、人間が直接編集したことは責められるのだろうか？人間がやったのだからその馬鹿な人間が悪く,そのような分別のない人間は許されないと人は言う. しかし分
【みんな】Caffeより手軽かつ高速! Cで書かれた必要十分な深層学習フレームワーク darknetを試す【意外と知らない】:電脳ヒッチハイクガイド:電脳空間カウボーイズZZ(電脳空間カウボーイズ) - ニコニコチャンネル:生活
チャオ! オレだ。 深層学習を手軽に使いたいというニーズは日に日に高まっているはずなのに、ガクシャ先生どもと来たら、やれMatlabだ、やれPythonだのと軟弱言語の話しかしやしねえ。どこかに気骨溢れたナイスガイはおらんのか! と思ったら、居た。 それが今回紹介するdarknetだ。 darknetという名前から想像する異常にダークである。 バーン どうよこのダークネス感 いまどき黒いページというのは珍しい。 そして無駄に凝った魔法陣のようなロゴ。ダークだ。 しかしダークネット、厨二満開とせせら笑っていられるのもいまのうちだ。 このダークネット、実に必要十分な機能を最短で試せる超絶優れたツールなのである。 CaffeやTensorFlowほどの知名度はないが、実用性皆無なTensorFlowに比べてdarknetはものすごく実用的。Cが分かる人ならばこれほど使いやすいものもちょっと他にな
日本取引所グループがブロックチェーンをぼろくそに言ってる - 蟻地獄
日本取引所グループ(東証と大証の総元締め)がブロックチェーンの実証実験をやるっていうのが以前話題になっていましたが、その結果がついに出ました。ありがたいことになんとレポートを全文無料で読むことができます。 http://www.jpx.co.jp/corporate/research-study/working-paper/tvdivq0000008q5y-att/JPX_working_paper_No15.pdf そんなに長くないのでぜひ原文を読んでほしいのですが、要点をまとめると以下のような感じです。 実証実験内容 コンソーシアム型ブロックチェーン。ノードを持つのは市場管理者・金融機関・株式発行体(要は上場企業)の三者 市場管理者と金融機関が認証処理を行う権限を持つ。株式発行体はデータの参照のみ可能で、書き込みはブロックチェーン外で市場管理者に依頼する。投資家は金融機関に受託して取引
［CEDEC 2014］「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net
［CEDEC 2014］ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート ライター：箭本進一 神奈川のパシフィコ横浜で行われた，ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日，「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。 登壇したバンダイナムコスタジオ HE技術部 加来量一氏 この講演のユニークな点は，旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は，旧ナムコの初期作品50本を解析し，それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが，講義の主旨なのである。 1980年代のナムコアーケ
せっき～のゲーム屋さん ドルアーガの塔 乱数の工夫の正体
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。 ＣＥＤＥＣの講演 「ゲーム世界を動かすサイコロの正体 ～ 往年のナムコタイトルから学ぶ乱数の進化と応用」 より、 乱数を使った ドルアーガの塔の 迷路生成のアリゴリズムについて紹介です。 講演内容は、こちらです http://sekigames.gg-blog.com/Entry/288/ 講演者の方も、 「ナムコの乱数を取り上げるなら、ドルアーガの塔をせざるえない」 という程、外せない内容との事です 「このテーマだけで講演時間を全て使っても説明しきれない」 （講演では、時間の関係で 触りのみでしたので ある程度、せっき～の解釈で補完しています） -------------------------------------------------------------------
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムビジュアル大事典
「フーリエ級数」から「高速フーリエ変換」まで全部やります！【2019.07.20更新】
