深層強化学習論文リストを作り始めた

機械学習

前にDQNの再現の記事を書いてからほぼ1年が空いてしまいました．DQNの新しい論文が2月にNatureに載ったのは記憶に新しいですが，それから研究はさらに加速し，最近では自分の感覚としてはarxiv含めて平均すると1週間に1論文くらいのペースで深層強化学習の研究が発表されているのではないかと思います（ちゃんと計算してないので全然違ってたらすみません）．

これだけ論文が増えるとまとめのようなものが欲しくなるので，自分で作ることにしました．
https://github.com/muupan/deep-reinforcement-learning-papers
まだだいぶ不完全ですし，論文リストをきちんとした形で作るのははじめてなのでいろいろと迷う部分があるのですが，これから少しずつ充実させていく予定です．

CaffeでDeep Q-Networkを実装して深層強化学習してみた

機械学習 ゲームAI

概要

深層学習フレームワークCaffeを使って，Deep Q-Networkという深層強化学習アルゴリズムをC++で実装して，Atari 2600のゲームをプレイさせてみました．

Deep Q-Network

Deep Q-Network（以下DQN）は，2013年のNIPSのDeep Learning Workshopの"Playing Atari with Deep Reinforcement Learning"という論文で提案されたアルゴリズムで，行動価値関数Q(s,a)を深層ニューラルネットワークにより近似するという，近年の深層学習の研究成果を強化学習に活かしたものです．Atari 2600のゲームに適用され，既存手法を圧倒するとともに一部のゲームでは人間のエキスパートを上回るスコアを達成しています．論文の著者らは今年Googleに買収されたDeepMindの研究者です．

NIPS2013読み会で自分が紹介した際のスライドがこちらになります．

他の方が作成したスライドもあります．

必要なもの

ソースコード

GitHubで公開しています．DQN-in-the-Caffe

ネットワークの構成

ネットワークの構成は元論文の通り，

  1. 入力層：84x84x4（ラスト4フレームのダウンサンプリング&グレイスケール化）
  2. 隠れ層1：8x8のフィルタx8（ストライド4）による畳込み+ReLU
  3. 隠れ層2：4x4のフィルタx16（ストライド2）による畳込み+ReLU
  4. 隠れ層3：fully-connectedなノードx256+ReLU
  5. 出力層：fully-connectedなノードx18（18種類のアクションそれぞれの行動価値）

としました．このネットワークを逆伝播により学習するためには，複数ある出力のうち1つの出力のみに対して誤差を計算する必要があるのですが，それを可能にするためにCaffeのELTWISEレイヤーを使い，1つの要素のみ1で残りは0であるようなベクトルをネットワークの出力に掛け合わせることで望みの出力だけを取り出せるようにしています．Caffeのネットワーク表記でネットワーク全体を書くと下のようになりました．


パラメータの学習

パラメータの学習のためには，「状態{s_t}で行動{a_t}を選択したところ，報酬{r_t}を獲得し，次の状態が{s_{t+1}}であった」という状態遷移{(s_t,a_t,r_t,s_{t+1})}の経験をreplay memoryというメモリに保管していき，パラメータ更新の際にはそこからランダムサンプリングした一定数の遷移それぞれについて
{Q(s_j,a_j) \leftarrow r_j + \gamma max_{a'} Q(s_{j+1},a')}
となるように勾配を計算した上で，まとめて更新を行うミニバッチ学習を行います．

元論文ではここでRMSPropというパラメータ更新量の自動調節アルゴリズムを用いていますが，Caffeには今のところRMSPropは実装されておらず，その代わりAdaDeltaというRMSPropによく似たアルゴリズムをすでに実装してpull requestを投げている人がいたので，それを使いました．ただし，AdaDeltaをそのまま使用するとパラメータが発散してしまうことが多かったため，AdaDeltaによる更新量にさらに一定の係数（最初の100万イテレーションでは0.2，次の100万イテレーションでは0.02）を掛けて用いました（同じようなことをやっている？人）．ミニバッチの大きさは元論文と同じ32，割引率{\gamma}は元論文では示されていませんが0.95としました．

元論文ではreplay memoryの容量は100万フレームでしたが，メモリの都合上，半分の50万で実験しました．

学習時間

実行環境は

です．CaffeはGPUモードで，さらにcuDNNを使いました．この構成でミニバッチ5万個の学習に45分ほどかかりましたが，元論文では5万個分を30分ほどで学習しているので，1.5倍ほど遅い結果となりました．

結果

上の動画はPongというゲームを200万イテレーション（およそ30時間）学習させた後のプレイ動画です．右の緑がDQNで，元論文と同じく各フレームごとに5%の確率で完全にランダムにアクションを選ぶようにしています．3回の試行のスコアがそれぞれ16，13，19と，元論文の20という平均スコアには達していませんが，元論文では1000万イテレーションの学習を行っているので，より学習が進めば同等のスコアが出せるかもしれません．

元論文ではHuman Expertのスコアは-3とされていますが，現時点でもそれよりは大幅に上回っているので，DQNは人間より強いという結果が再現出来て何よりです．

流行りの深層学習フレームワークCaffeをC++から使ってみた

C++ 機械学習

Caffeとは

CaffeはBerkeley Vision and Learning Centerというところが中心となって開発している深層学習（Deep learning）フレームワークです．公式サイトの記述によれば

といった特徴があるようです．ちょうどC++から簡単に使える深層学習ライブラリを探していたところ，なんだか流行っていて（Caffeで手軽に画像分類 - Yahoo! JAPAN Tech Blog，Deep learning実装の基礎と実践，Python - Deep Learningで猫の品種識別 - Qiita）良さそうだったので使ってみることにしました．

Caffeのインストール

公式サイトのインストール手順に従ってインストールします．自分のOSはOS X 10.9.5で，インストール手順には

  • OS X 10.9のデフォルトコンパイラはlibc++を使う
  • でもCUDAは今のところlibstdc++としかリンクできない
  • だから依存ライブラリは全部libstdc++を使ってビルドしろ

とだるいことが書いてありますが，今回はCPU-onlyの設定でインストールすることにしていたのでこれは無視してOS X 10.8向けの手順の通りにインストールしました．CPU-onlyの場合はMakefile.configのCPU_ONLY := 1の行をアンコメントします．

CaffeをC++から使う

以下，$HOME/caffe以下にインストールしたとして話を進めます．Caffeをライブラリとして別のC++プログラムから利用するという利用方法は，公式にサポートされた方法ではないようで，ほとんど情報がありません．GithubのIssuesやメーリングリストを検索したりtools/caffe.cpp等のコードを参考にした結果，以下のようなごくシンプルなモデル（入力が2変数，出力が1変数の線形近似）でひとまず学習を行うことができました．

net.prototxtではネットワークのアーキテクチャと損失の定義をしており，solver.prototxtでは損失を最小化する最適化アルゴリズムの設定をしています．詳しくは公式のチュートリアルを見てください．

上のC++コード（caffe-sample.cpp）をコンパイルするには，次のようにします．

$ clang++ -std=c++11 -DCPU_ONLY -I$HOME/caffe/include -I/System/Library/Frameworks/vecLib.framework/Versions/Current/Headers -L$HOME/caffe/build/lib caffe-sample.cpp -lcaffe -lglog

（CPU-onlyの場合は）-DCPU_ONLYを指定すること，Caffeのヘッダファイルへのパス（$HOME/caffe/include）と共有ライブラリへのパス（$HOME/caffe/build/lib）を通すことが必要です．さらにOS Xでは/System/Library/Frameworks/vecLib.framework/Versions/Current/Headersのヘッダファイルへのパスが必要なようです（Makefile参照）．さらに，$HOME/caffe/include/caffe/proto/caffe.pb.hが見つからないとエラーが出る場合は，$HOME/caffe/src/caffe/proto/caffe.protoに対してprotocコマンドを使って作成します．

# $HOME/caffe/include/proto以下にcaffe.pb.hとcaffe.pb.ccが作成される
$ protoc $HOME/caffe/src/caffe/proto/caffe.proto --cpp_out=$HOME/caffe/include/proto

実行結果は以下のようになり，バイアスを含めた3つのパラメータをそれなりに正しく学習できているのが確認できます．

$ ./a.out
3.00199x + -1.99783y + 3.99781 = target
10a + 20b + c = -5.93897

おわりに

今回はごく単純なモデルしか扱いませんでしたが，より複雑なモデル（多層，畳み込み＋プーリング等）の場合でもC++から扱うインタフェース自体は変わらないものと思います．どうしてもC++から深層学習をした（いけど自分で一から実装はしたくな）い場合は，Caffeを使ってみてはいかがでしょうか．コードが読みやすいところ，Protocol Bufferが書きやすいところも魅力だと思います．

General Game Playingの世界大会（IGGPC2014）の参加記録

ゲームAI

2014年のInternational General Game Playing Competition（IGGPC）の参加記録です．IGGPCは2005年から毎年開催されているGeneral Game Playingの世界大会です．

General Game Playingとはなにか

ゆるい概要についてはゲームAI研究について何も知らなくてもわかるGeneral Game Playingの概要をご参照ください．競技としてのGGPは，以下のような動作ができる「強い」ゲームAIプログラムを作るというものです．

  1. ゲームマネージャーと呼ばれるサーバーから以下のものを受信する
    • Game Description Languageで書かれたゲームルールと，そのゲームでの自分の役割（e.g. 先攻or後攻）
    • ゲーム開始前の思考時間（start clock）
    • ゲーム開始後の1ターン毎の思考時間（play clock）
  2. start clockを使ってゲームを分析する
  3. ゲームが始まり，以下をゲームが終わるまで繰り返す
    1. ゲームマネージャーから他のプログラムがどの手を選んだかを受信する
    2. play clockを使って現在の局面に対する手を選び，ゲームマネージャーに送信する

どんなゲームをプレイするかは事前には知らされません．強いAIを作るためには，限られた時間の中でゲームルールを読んで（もちろん人間が読んではいけない）ゲームを分析したり，自己対戦の結果から評価関数を学習したりすることが必要となります．

GGPのためにこれまでに使用されてきたゲームは，8パズルのような1人ゲームからオセロやチェスのような2人ゲーム，Chinese Checkersのような多人数ゲーム等，多岐に渡ります．ゲームの例はGamemasterやTiltyard GGP Serverで見ることができます．

これまでの優勝プログラム

2005 ClunePlayer
2006 Fluxplayer
2007-2008 Cadiaplayer
2009-2010 Ary
2011 TurboTurtle
2012 Cadiaplayer
2013 TurboTurtle

この中ではCadiaplayerのみソースコードが公開されています．2007年のCadiaplayer以降，優勝プログラムは全てモンテカルロ木探索を使用しています．モンテカルロ木探索はランダムシミュレーションを使った探索アルゴリズムで，囲碁での成功が有名ですが，その正確な評価関数を必要としないという性質からGGPにおいても支配的なアルゴリズムとなっています．

自分のプログラム

Knowerという名前のプログラムで参加しました．start clockの間に自己対戦からの強化学習によって評価関数を学習し，それをモンテカルロ木探索の中で利用するというAIになっています．ソースコードの全体は今のところ公開していませんが，Yet Another Prologを用いたゲームルールの推論部分だけ公開しています（https://github.com/muupan/ggpe）．

予選

7/3-21の間に6回予選があり，そのうち好きなものに参加することができ，いずれか1つの予選で日程で基準点を上回れば本戦に進むことができるという形式でした．

予選参加のためにはまず自分のプログラムを公式サイトで登録する必要があり，それから参加したい日程を選ぶということになるのですが，自分が予選期間の途中で確認した時点では48のプログラムが登録されていました．登録だけして結局参加しなかったプログラムや，自分が確認した後で登録したプログラムもあるかもしれないので，正確な予選参加者はわかりませんが，例年の数よりずっと多いことは確かです（2013年はたった16プログラムでした）．この参加者の増加にはCourseraでGGPの講義が行われたことの影響が大きいと思われます．

予選では1人ゲームと2人ゲーム，合わせて10のゲームをプレイしました．2人ゲームは運営側が用意したベンチマークプレイヤ（アルゴリズム不明）との勝負でした．1人ゲームが多く，強化学習とランダムシミュレーションが武器であるKnowerにとって少し厳しい物でした．例えば8パズルに「完成したら100点，しなかったら0点」というスコアが与えられている場合，いくらランダムシミュレーションを繰り返しても偶然完成してしまわない限りスコアは0点にしかならず，強化学習もモンテカルロ木探索も歯が立ちません．こういうゲームでは，ゲームルールを読んで分析する（例えば，8パズルのピースのうち何個が正解の位置にあるかを数えて評価に使うようにする）ということが求められます．Knowerは1度予選に落ちた後，1人ゲーム向けの改良を加えた後に再度挑戦し，無事に予選を通過出来ました．

予選では，8パズルの他に，Multiple Tic Tac Toeという，三目並べの盤面が9個並んでいるけど1個以外はダミーで勝敗に影響しない，という明らかにAIをいじめたいだけのゲーム（これもゲームルールの分析が求められます）などもありました．Connect FourやAlquerqueといったより複雑な実在するゲームも使用されました．

最終的に，Knower含め17のプログラムが予選を通過しました．

本戦

本戦は7/29-30の2日間に分けて行われました．1日目はみんなで同じ1人ゲームをプレイしたり，2人ゲームを互いにプレイしたりして，合計18ゲームがプレイされました．プログラムは18ゲームの合計スコアによってランク付けされ，これにより2日目に進むことができるプログラムが決められました．1日目の結果ををブログにまとめてくれている人がいます（Sancho GGP Player: Finals Day 1 round-up）．BreakthroughやPentagoといったゲームの他に，数独などもプレイされました．

2日目に進めるのは12プログラムのみで，2日目は上位4プログラムを勝者サイド，その下の8プログラムを敗者サイドとするダブルエリミネーション方式のトーナメントでした．Knowerは11位でギリギリ2日目に進むことができました．特筆すべきは，勝者サイドになった1日目の上位4プログラム全てが，去年までのIGGPCに参加していない新参者だということです．Courseraの講義で知名度が増えた結果，これまでGGPを研究してきた人たちを押しのけて新たな勢力が台頭してきたようです．

2日目は全て2人ゼロサムゲームで，その結果はhttp://challonge.com/iggpc2014で見ることができます．Knowerは残念ながら1回戦で敗退してしまいました．優勝したのはSanchoという，1日目を圧倒的なスコアで1位通過したプログラムでした．

Carbon vs. Silicon

IGGPC2014を優勝したSanchoは「Carbon vs. Silicon」（人間 vs. コンピュータ）と題したマッチを戦いました．Carbonを代表するのはIGGPCを運営するスタンフォード大の学生達です．プレイされたゲームはJoint Connect Fourと呼ばれるGGP向けに人工的に作られたゲームで，Connect Fourの盤面が2つ並んでおり，一方は普通のConnect Four，もう一方は勝敗が逆になっているConnect Four（4つ並べてしまったら負け）になっていて，2人のプレイヤが交互に別々の盤面に石を置く同時着手ゲームになっています．結果はSanchoの圧勝で，ケイ素生物の強さを見せつけました．

Sanchoの勝因

Sanchoの特徴としては，参加者用のチャットで聞いた限りでは

  • ゲームルールの分析にかなり力を入れている
    • 例えばJoint Connect Fourを2つのゲームに分解して別々に探索を行うことができる
  • ゲームに応じてアルゴリズムを選択できる
    • 8パズルにはA*を使っていた
  • ゲームルールの推論（局面から合法手を列挙したり，局面と手から次の局面を求めたりする処理）が高度に最適化されている
    • 参加したプログラムの中でおそらく最も高速なシミュレーションが行える

のようなことが挙げられます．Sanchoのソースコードは公開されており（https://github.com/SteveDraper/ggp-base），また使われている戦術についてもブログ（http://sanchoggp.blogspot.jp/）に書かれています．

2014/10/03追記：SanchoのソースコードのURLが間違っていたので修正

Magic: The Gathering + word2vec = "card2vec" 〜M:TGで自然言語処理〜

機械学習 ゲームAI

概要

最近word2vecという単語のベクトル表現を学習して単語の意味を足したり引いたりできるものが流行っていて面白そうだったので試しにMagic: The Gatheringについて学習させてみました．card2vecは勝手に作った造語です．

手順

自然言語処理をなにも知らない私がword2vecを走らせるまで: 最尤日記，自然言語処理の最新手法"word2vec"で艦これ加賀さんから乳を引いてみる - あんちべ！を参考にしました．

1. 必要なソフトウェアをインストールする
2. M:TGについて書かれた文章を用意する

とりあえず以下の3つをwget -rとか使いながらダウンロードして，タグなどを消して必要そうなところ（MTG Wikiなら記事の本文，Astral Guildと2chは各書き込みの本文）だけ抽出しました．

これらを繋げた文章（分かち書き前）のサイズが400MBくらいでした．

3. MeCabのユーザー辞書を作る

MeCabのデフォルト辞書には当然M:TG用語は入っていないため，そのままだと単語の区切りがおかしくなりますし，なによりカード名を1つの単語として認識させたかったので，それらが入ったユーザー辞書をMTG Wikiの記事タイトルから作成しました．mecabの辞書に新しい単語を登録する方法 - Hive Color，MeCab: 単語の追加方法などを参考にしました．

基本的にMTG Wikiの記事名を機械的に単語として登録し，日本語名と英語名が併記してあるもの（例：極楽鳥/Bird of Paradise）はさらに両方を登録するようにしました．コストの設定はよくわからなかったので，とりあえず使われやすいように小さい値1を設定してしまいました．後のために，原形のカラムには日本語名を持つものは日本語名を，英語名のみのものは半角スペースを_に置き換えたものを書いておきます．

"ディミーアのギルド魔道士/Dimir Guildmage",,,1,名詞,一般,*,*,*,*,"ディミーアのギルド魔道士",*,*
"ディミーアのギルド魔道士",,,1,名詞,一般,*,*,*,*,"ディミーアのギルド魔道士",*,*
"Dimir Guildmage",,,1,名詞,一般,*,*,*,*,"ディミーアのギルド魔道士",*,*
"Underground Sea",,,1,名詞,一般,*,*,*,*,"Underground_Sea",*,*
4. MeCabで文章を分かち書きする

word2vecは単語が半角スペースで分かち書きされた文章のみを入力として受け付けるので，作成したユーザー辞書を使って文章を分かち書きします．

"Underground Sea"のような半角スペースを含む単語はそのままでは別の2つの単語として扱われてしまい，好ましくありません．また"ディミーアのギルド魔道士/Dimir Guildmage"，"ディミーアのギルド魔道士"，"Dimir Guildmage"の3つは同じ1つの単語として学習したほうが効率的だと思われます．分かち書きの前に置換処理をしても良いですが，ここでは分かち書きの際に単語を全て原形に変換してしまうことにしました．

# content.txtをユーザー辞書mtg.dicを使って分かち書きする．単語は原形に直す．
cat content.txt | mecab -u mtg.dic --node-format="%f[6] " --eos-format="\n" > wakati.txt
5. word2vecで学習する

windowの値はデフォルトでは5ですが倍の10にしてみたら精度が少し向上したように感じました．

./word2vec -train wakati.txt -output mtg.bin -window 10 -binary 1
6. 遊ぶ
./distance mtg.bin

として好きな単語を入力するとそれに近いものを表示してくれます．

./word-analogy mtg.bin

として好きな単語を3つ，スペース区切りでA B Cのように入力すると，B-A+Cに近いものを表示してくれます．

結果

（M:TG的に）わかりやすい結果だけ載せます．

ラノワールのエルフ - クリーチャー + エンチャント =
                                              Word              distance
------------------------------------------------------------------------
                                              繁茂		0.620990
                                        肥沃な大地		0.612975
                                ブランチウッドの鎧		0.605195
                                              怨恨		0.584213
                                        不屈の自然		0.580197

繁茂と肥沃な大地．マナの出るエンチャント．

飛行 - 青 + 黒 =
                                              Word              distance
------------------------------------------------------------------------
                                              絆魂		0.794237
                                              接死		0.784229
                                              威嚇		0.772298
                                          先制攻撃		0.772254
                                        トランプル		0.761075

Top3がまさに黒の得意な能力．

神の怒り - 白 + 黒 =
                                              Word              distance
------------------------------------------------------------------------
                                              滅び		0.871883
                                          突然の死		0.832915
                                              恐怖		0.831339
                                        不敬の命令		0.824064
                                その場しのぎの人形		0.818364

1位は期待通りの黒い神の怒り．

Wood Elemental - クリーチャー + 土地 =
                                              Word              Distance
------------------------------------------------------------------------
                                リスティックの洞窟		0.637866
                                     Sorrow's_Path		0.625077
                                        蒼ざめた月		0.611142
                                  隕石のクレーター		0.601391
                                    テフェリーの島		0.600804

ひどい土地がぞろぞろ．蒼ざめた月は土地ではないが土地が絡んでいるので間違いとも言えない？

アトランティスの王 - マーフォーク + キスキン =
                                              Word              Distance
------------------------------------------------------------------------
                                        聖なるメサ		0.725760
                                      皺だらけの主		0.711722
                                  川の案内者、シグ		0.709027
                                  思考の糸の三人衆		0.708851
                                            動員令		0.706689

キスキンのロードは惜しくも2位．

恐怖 - 黒 + 青 =
                                              Word              Distance
------------------------------------------------------------------------
                                          霊魂放逐		0.810830
                                          神の怒り		0.789171
                                      使い魔の策略		0.782109
                                        妖精の計略		0.777077
                                      海賊の魔除け		0.771080

青にとっては打ち消し＝除去．神の怒りも青いデッキで使われるので理解できなくはない．

復活の声 - ドラゴンの迷路 + テーロス =
                                              Word              Distance
------------------------------------------------------------------------
                            太陽の勇者、エルズペス		0.692638
                                嵐の息吹のドラゴン		0.674960
                                            波使い		0.657235
                              ヴィズコーパの血男爵		0.656863
                                      ワームの到来		0.656152

テーロスの高額神話レア？

嬉しさ

自分がやったこと自体はただの人の真似と暇つぶしでしかないですが，TCGのカードの良いベクトル表現が得られると次のような嬉しさがあるのではないかと思います．

  • カード検索やリコメンデーションに使え，デッキ作成支援等に役立つ
  • カードの能力について人間のような抽象化能力を持ったAIが作れる

特にTCGのAIはあまり研究が進んでいない分野だと思うので期待したいところです．

charをstd::stringに変換する

C++

C++でcharからstd::stringへの変換（文字から文字列へ，例えば'a'から"a"へ）をどうするか，すごく簡単そうに見えていざ検索してみるとchar[]とstd::stringの間の変換についての記述しか見つからなかったので書いておこうと思います．

  1. 「std::stringのコンストラクタstring(size_t n, char c)でn=1とおく」おそらく最もお手軽な方法です．
  2. 「boost::lexical_cast(char c)を使う」Boostライブラリが必要になりますが，1というマジックナンバーを書く必要が無いのが利点かもしれません．
#include <cassert>
#include <iostream>
#include <string>
#include <boost/lexical_cast.hpp>

int main() {
  assert("a" == std::string(1, 'a'));
  assert("a" == boost::lexical_cast<std::string>('a'));
  std::cout << "Hooray!" << std::endl;
}

なおstd::to_string('a')は"97"になります．

GCC 4.8.2をビルドしてホームディレクトリにインストール

C++

概要

あるサーバ上でC++11の機能をフルに使いたかったがGCCが古かったのでGCC 4.8.2を新たにインストールした．管理者権限が無いのでソースからコンパイルして$HOME/localにインストールした．

環境

OS Linux x86_64
元のGCC 4.3.2

手順

# Download GCC 4.8.2
wget http://ftp.tsukuba.wide.ad.jp/software/gcc/releases/gcc-4.8.2/gcc-4.8.2.tar.bz2
tar xjf gcc-4.8.2.tar.bz2
cd gcc-4.8.2

# Download GMP 5.1.3
wget https://ftp.gnu.org/gnu/gmp/gmp-5.1.3.tar.bz2
tar xjf gmp-5.1.3.tar.bz2
mv gmp-5.1.3 gmp

# Download MPFR 3.1.2
wget http://www.mpfr.org/mpfr-current/mpfr-3.1.2.tar.bz2
tar xjf mpfr-3.1.2.tar.bz2
mv mpfr-3.1.2 mpfr

# Download MPC 1.0.1
wget http://ftp.gnu.org/gnu/mpc/mpc-1.0.1.tar.gz
tar xzf mpc-1.0.1.tar.gz
mv mpc-1.0.1 mpc

# Configure & build
mkdir build
cd build
../configure --prefix=$HOME/local --enable-languages=c,c++
make
make install

gcc-4.8.2/contrib/download_prerequisitesを使えば必要なGMP，MPFR，MPCをftp://gcc.gnu.org/pub/gcc/infrastructure/からダウンロードしてくれるらしいが，残念ながら外部にFTP接続ができる環境ではなかったので別途探してダウンロードした．それぞれ別にインストールしておく必要はなく，解凍したものをgcc-4.8.2のディレクトリ内にそれぞれgmp，mpfr，mpcという名前で置いておけばいい．

なお，configureの--enable-languages=c,c++を設定しないとcannot find neither zip nor jar, cannot continueというエラーが出てmakeが失敗してしまった．参考：http://www.linuxquestions.org/questions/linux-from-scratch-13/lfs-7-3-6-17-gcc-error-cannot-find-neither-zip-nor-jar-4175458842/