Help us understand the problem. What is going on with this article?

D-Waveでスーパーマリオを解く方法

はじめに

誰でも寝てる間に仕事が終わってたら幸せですよね。そのために量子コンピュータを使って自動的に仕事をしてくれる仕組みを作りました。それを応用してスーパーマリオを解く仕組みを作ってみましたので紹介します。

1_1bi8_pBhPPRuCp4gYImPog.gif

マシンはD-Wave

マシンは今回D-Waveというカナダのマシンを利用しました。契約をしていますので、クラウド経由で使えます。

https://www.dwavesys.com/

D-Waveは超電導といって、抵抗がなくチップ自体の消費電力が0に近いです。そんな消費電力の小さいマシンでスーパーマリオを解いてくれるなんてとっても得した気分です。

イジング定式化の自動化

今回は俗にいうAIでときます。全体の構成はそんなに難しいものではなく、シンプルな機械学習という構成です。下記が今回新しく作った仕組みです。世界でも珍しいらしく、米国からもたくさん問い合わせが来ます。

無題のプレゼンテーション (2).jpg

基本的にはこれまで数学を駆使して行なっていたイジングモデルの定式化部分を機械学習を使って自動学習をします。それにより、専門家不要で簡単な問題は定式化を自動化することができます。定式化は多数のトライアルの結果によって分析され、なるべく悪い評価のものは取り上げず、いい評価のものを取り上げてそれをイジング定式化のパラメータに反映させます。

イジングモデルはせいぜい2次式で、D-Waveのパラメータは局所磁場で2000、相互作用で12000なので、14000パラメータを大体最適化できれば大丈夫です。

一度に最適化や定式化できませんので、なんども繰り返してパラメータ最適化をかけてイジング式を作っていきます。

サンプリングとシミュレーション

D-Waveで最適化で1つの解を求める代わりに、わざと局所解を含むエネルギーの分布を取ります。それによって局所解のたくさんあるイジングモデルではサンプリングという手法を通じて、たくさんの解を取り出すことができます。今回はこのサンプリングもしくはサンプリングに近い形で多数の解を求め、それを通じて配列をとりだします。

配列はシミュレーションに相当し、0もしくは1のactionを取ることができます。actionの種類を増やしたい場合には、量子ビットをセットで使い、00,01,10,11のように組み合わせを使って4アクション作ることができます。

そうやってサンプリングを得られた配列の通りにシミュレーションをすると通常ゲームの場合には、スコアが出ますのでそのスコアを報酬として取り出します。ちなみにスコアの付け方によって最適化は結構変わってきますので、スコアのつけ方も大事です。

報酬の集計と最適化

報酬にはもちろんばらつきがあり、その背景には量子ビットの01のバイナリの配列があります。今回はこの報酬の良し悪しによってもともとサンプリングをしたイジング式の更新もしくは置き換えをします。それによって、より良い解を出した配列の要素と悪い解を出した配列の要素を合わせて評価することで、大域最適もしくは局所最適を実行することができます。

この出た配列から逆算してイジング式の局所磁場と相互作用を最適化することによって、PDCAサイクルを通じてより良いイジング式をたくさんのサンプルのトライアルから導き出すことができます。この最適化をかけるアルゴリズムは既存の古典最適化や量子アルゴリズムを使うことができ、用途に合わせて調整します。

繰り返し

一定のイジング定式化を機械学習で最適化をすると一定の方向に収束することがあります。そのパラメータが最適かどうかは評価次第ですが、少なくともPDCAのサイクルは自動で、かつ一定方向にある程度いい収束を見せればパラメータの自動化が成功したことになります。

マリオ

マリオではクリボーや穴に落ちたりとクリアするまでの障壁がたくさんあります。ただランダムサンプリングをするだけでは、簡単にはクリアすることができません。ある程度のサンプリングを通じて、サンプリング結果を最適化することで効率的にクリアをすることができます(多分)。

モデル

現状のマシンはあまり複雑なモデルを作ることができません。生成モデルを複雑にすることによって少ない量子ビット数で豊かなサンプリング表現をすることができ、ディープな構成にしたり、有名なのはボルツマンマシンを使います。

ただ、現状はやはりそこまで有用な学習をするのは難しいのでこの辺りのモデルの構築手法に関しても工夫が必要となっています。今回はこのモデル作りに関してはかなり面倒なことをしていて、ノウハウの塊になっています。

今後

今後の課題はサンプル数を減らしながら、生成モデルを最適化して表現を豊かにし、集計部分の最適化手法で計算量の少ない方法を探しながらパラメータを最適化していきます。課題というよりも通常の機械学習のステップを量子コンピュータでも再現することになると思いますので、楽しみながらやっていければと思います。

今後は簡単なモデルでイジング最適化を再現できるような仕組みも紹介していきたいと思います。以上です。

mdrft
量子コンピュータのアプリケーション、ミドルウェア、ハードウェアをフルスタックで開発
https://blueqat.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした