Marathon Match 68
(2011年6月1日の記事を移行したものです。)
結果
9位/147 Rating --→1754
大反省点
- 開始日になんでもいいから提出して追い込む！
- 準備完了までは集中！
- ちゃんとスコアがでるようになると、面白いので集中できる。準備の段階が面白くないので脱線しやすい）
- 異常を早めに察知するために、ときどきArenaにいって、サブミット＆まわりの人のチェック（提出時間・得点）
- テストケース50個では少なすぎ
- 誤差でまくり論外！！！テストケースは最悪でも300,500は必要
- 疲れているときにできること、疲れているときにできないことにタスク分けして作業をすすめる。
- 10秒間の計算時間があるのを有効に使ったアルゴリズムにする
- 最後のほうまで、即終わるアルゴリズムだったので…
反省点
- サブミッションの問題（1時間３０分次の提出ができないのでお早めに。
- 早めに知ってれば、「へび」配置をいれるかいれないかも含めて調整できたのに・・・。
- タイマーの問題（１０秒）Clock関数。とくにアリーナ上では、時間がかかるよう。
- gettimeofdayのほうがよい？
- 序盤の準備にわりと時間がかかる。
- やってみて気づくことはたくさん。なので、後で追い込むのではなく、最初から少しずつやってったほうがいい。
- ソースは丁寧に書く。リファクタリングは、時間に余裕があるときなら、多少眠くても疲れててもできる。
- ネット切断は効果的だったけど、たまにはアリーナものぞくべきだった。
ポイント
「回」型の配置パターンで62.5ptsは取れるのは予想がついたけど、「回」型の配置に気づくのが遅すぎた。また、正方形のときにしか対応できないアルゴリズムを書いてしまったので、「田」型への応用が難しくなってしまった。
唯一良かったのは、大きさの違う正方形「回」を組み合わせることにより、rcFillingScoreが満点のままで「田」型にする方法を思いついたこと。これのおかげで、上位になんとか食い込むことができた。
例えば、3等分の「田」にしたいときは、横幅がN%3==0,N%3==1は以下のような配置にできる。普通の「田」だと隙間の行ができてrcFillingScoreが下がってしまうが、これならＯＫ．
4等分の「田」にしたいときは、以下のような配置もある。
あと、上位の方は
- 「回」「田」以外でも点対称な配置はいろいろあった
- 置き換えが可能なアルゴリズムにしていた。
といった点で大きく差がついた。
「海外で働く人が驚いた日本とのギャップ」に、ツッコミました
Naverまとめの記事「海外で働く人が驚いた日本とのギャップ http://matome.naver.jp/odai/2129410761628592301 by なぁーこさん」が、とても面白かったのですが、納得するケースと、これは違うなと思うケースと、いろいろだったので、自分の経験を元にツッコミを入れてみました。
以下の点については、ご了承ください。
- 環境や、個人の感じ方で、全然違ってくると思うので、一般論だとは思わないでください。
- 自分が今までは働いたのは、日本のゲーム会社と、海外のゲーム会社の２社です。「東京」が日本の会社、「バンクーバー（カナダ）」「バルセロナ（スペイン）」「シンガポール」は海外の同じ会社です。
- ゲーム会社しか知らないので業界による偏り、海外については「同じ会社」でしか働いてないという偏りは、かなりあると思います。
- 「海外」と表記してても、基本、働いた３ヶ国だけを指してます。
それでは、ここからスタートです。長文です。
長期休暇はしっかり取る
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときも２週間程度の長期休暇は取れてましたが、プロジェクト終了後に、休日出勤分の振替休暇を使っていたというかんじです。有給休暇は年に１・２日しか使えてなかったので、△にしました。
海外では、ほぼ全員が振替休暇・有給休暇を使っていると思います。余って消える場合は、休暇買い取りになってます。
あと、スペインは有給休暇が長いです（年27日でした）、振替休暇と組み合わせて、２・３ヶ月の休暇を取っている人は普通にいました。前年の分の有給休暇と組み合わせて、半年ぐらい休んでる人もいました。
決して謝らない
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
たぶん、「I'm sorry. というと責任を全部認めたことになるので、そう簡単に言うべきではない」というのが日本に広まってるからかもしれませんが、謝らないってことはないです。謝るべきケースで謝らない人も、まれにいましたが、そういう人は信用をただ失っているだけでした。それは、日本でも海外でも同じだと思います。
ロシアの社長は平社員と一緒に飲まない
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
ロシアはそうなのかもしれませんが、東京・バンクーバー・バルセロナ・シンガポールいずれも飲んでますｗ
残業はしません
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | × |
残業する必要があったら、多くの人はしますが、どんなことがあってもしないという人の割合は、バンクーバーが多かったかもしれません。海外だと、残業時間が長いと、管理職の管理能力が低いとみなされるので、残業時間を減らす工夫はいろいろしてる気がします。残業時間には大きな差がありますね。
仕事中でも平気で私用電話する
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
これは、今でも違和感を感じるギャップです。ミーティング中でも、家族から電話があったら、普通に電話にでる人がほとんどです。日本だったら、電話の着信音がなった時点で、相当まずいケースだと思うのですが…。
14時から16時にかけて昼休み
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
スペインには、シエスタ（長い昼休み）があるのですが、大きな会社やスペイン北部では、なくなりつつあるようです。実際、バルセロナでは14時〜15時が昼休みでした。
残業があるときなど、皆必ず残業に入る前にしっかり夕食を食べる
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本でも、しっかり夕食食べる気がするのですが、もしかしてゲーム業界だけなんでしょうか…。
違いといえば、海外では、残業のための夕食はOT Mealと呼ばれて、会社が払います。会社が出前をとったり、自分で夕食を買いにいって後で代金を払い戻したりです。ただ、たまに働かずにOT mealを食べる人や、OT mealを食べて19:30ぐらいに帰ったりする、ずるい人は割といます（もちろん、怒られます）。
賞与は一切無しでインセンティブのみ
キムチ作りにボーナス（諸手当についてと解釈しました）
| 東京 | △ |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
通勤手当、住居手当など王道なものから、ちょっと変わった諸手当まで、日本は意外とあると思います。海外は基本は年俸だけです。年俸だけ＝実力勝負というかんじがするので、自分は海外の形式のほうが好きです。ゲームが大きな利益をあげたらインセンティブがもらえるのは、日本も海外も一緒ではないでしょうか？
ただ、他社に転職する際には、交渉があるので、そこで手当などがつく場合があります。自分の場合も、引っ越し手当と、日本への帰省の手当がありました。ちなみに、バンクーバーの元上司が、イギリスからカナダの別会社に移る際に、交渉で「ペットの引っ越し手当も契約に含めてくれ」とお願いしてOKがでたのですが、それでペットとして馬を飛行機で輸送させてました…。
男性育児休暇が当たり前にとれる
| 東京 | × |
| バンクーバー | △ |
| バルセロナ | ？ |
| シンガポール | × |
日本では、見たことなかったです。バンクーバーでは数ヶ月の育児休暇を取ってる男性はいました。シンガポールは、制度が複雑ですが、短いので、取ってる人は見たことがありません。
あと、女性の育児休暇についてですが、バンクーバーでは、数週間で職場に戻ってくる人も、それなりにいました。日本だと、女性が育児休暇をとった場合は、だいたいは長期間休むと思いますので、あまりこういうケースはないかもしれません。
人の席の電話は鳴ってもとらない
| 東京 | × |
| バンクーバー | ？ |
| バルセロナ | ？ |
| シンガポール | ？ |
そもそも、ほとんど会社に電話がありません…。電話を受けるのは事務の人だけです。日本では、５席に１個ぐらいあって、外線・内線ともに電話を取ることが多くあったのですが…。日本でなぜ会社に電話がかかってきていたのか、あまり覚えてません…。
顧客のメールを1週間以上普通に放置する
メールの返事が嫌い
催促されなければ仕事をしない
責任感がなく、ミスを指摘すると「マイペンライ（問題ない）」と答える
| 東京 | × |
| バンクーバー | △ |
| バルセロナ | × |
| シンガポール | × |
この４つについては、日本・海外云々じゃないですね。日本であろうと、海外であろうと、仕事で結果を出してる部署・支店についてはちゃんとしてますし、結果を出してないところはダメです。断言できます。全部、仕事に直結することですし、そうなるのも当然かと。
ブログでクビになる
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
今の海外の会社との契約で「常識的な使用範囲なら、仕事の間にSNS等をやっても問題ない」と明記されてるので、問題ありません。心配だったら契約の際に聞けば良いだけです。もちろん、会社の秘密等を書き込んだらクビになりますが、それは日本も海外も同じでしょう。
仕事より家族
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときの会社は、「仕事より家族が大事」ということに理解がありましたが、個人レベルでは、「仕事より家族が大事」か「家族より仕事が大事」は考え方はバラついてると思いますし、実際、家族を犠牲にして、不幸な感じになってる例も数例見かけました…。海外では、「家族より仕事が大事」と言ってる人を、ひとりも見たことがありません…。家族の問題があったときは、制度的にも融通がきくので、助かっています。自分の場合、身内の病気があったのですが、「無給の休暇については、何か月とってもOK」と言われて、とても助かりました。
バンバン転職する
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | ○ |
バンクーバー、シンガポールでは、バンバン転職してます。うちの会社のシンガポール支店は、出ていく人が少ない（といっても年に１・２割はやめる）ですが、明らかに例外で、シンガポール全体では、とても多いそうです。
あと、「海外では、転職する人ほど、能力が高いとみなされる（能力が低い人は転職できない）」というのは、日本にいたときには耳にしてたのですが、実際はケースバイケースです。本人の実力次第です。
納期が自己都合で延長される
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
さすがにゲームの開発でそれはないですが、海外の事務系の仕事は、てきとーすぎるので、そういうケースは見られます。
終業時刻は厳守する
| 東京 | × |
| バンクーバー | × |
| バルセロナ | △ |
| シンガポール | × |
日本でも海外でもコアタイムがありますが、終業時刻はそんなに気にしてないと思います。タイムカードをちゃんときってたバルセロナが一番終業時刻を気にしてたかも。
遅刻は平気でする
| 東京 | △ |
| バンクーバー | △ |
| バルセロナ | △ |
| シンガポール | △ |
全部△にしましたが、意味的には結構違います。バンクーバーの場合は、時間を守る意識はむしろ低いのですが、そもそも朝早く来て早めに帰る人が多かったです。朝にランニングしたり、昼にジムにいったり、健康を意識した生活をしている人が本当に多いので、そもそもギリギリにくる必要がないかんじです。でも、遅く来る人は、自分のペースですごい遅くきてたので、△にしました。マイペースの結果です。バルセロナ・シンガポールは、大遅刻する人はいませんが、コアタイム間際にくる人が多く、多少遅れる人もいるかんじです。日本にいたときは、最初の部署が何時に来ても良い感じで、次の部署は時間に厳しい感じだったので、まちまちです。
仕事中に飲食可
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
どこでも、いつでも、普通に食べてます。IT系の会社で、ダメって言われてるところは、あるのかなぁ。
仕事中にカウンター内で弁当を食べたり、PCでチャットやオンラインゲームをしたり、従業員同士で大声でべちゃくちゃおしゃべり（飲食部分はダブってるので無視しました）
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | △ |
これは、日本・海外によらず、チームの雰囲気による気がします。結果重視なので、迷惑をかけなければ、何してもOKではありますが。
大卒の学歴がいらないような仕事に就く
| 東京 | ？ |
| バンクーバー | △ |
| バルセロナ | ○ |
| シンガポール | × |
シンガポールは、明らかな格差社会になってますし、×でしょうね。バルセロナは、この問題をよく聞きましたが、経済危機による若者の失業問題の影響なので、時間がたてば、たぶん学歴にあった仕事に就くのではと思います。
ゲーム業界だけで言えば、日本のほうが、学歴を気にせず、雇っていると思います。
女たちが汗水垂らして働く横で、男たちがグータラと寝そべっている
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
どんな仕事でも、上記の４か国では、見かけないですね…。
チップがもらえる
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | × |
もちろん、ゲーム業界では一切ありませんので、一般論として。シンガポールは日本と同じでチップ不要。バルセロナは良いサービスを受けたらって感じで、基本はいりません。バンクーバーはチップあります。チップは慣れるまでは面倒ですね…。
チームの同僚が仕事をやめる日のfarewell partyとかでも定時後の時間ではなく、ランチの時間を使ってる
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
ランチの時間も使いますが、プロジェクトの忙しさによりけりです。日本の場合は、そもそも辞める人が少なく、プロジェクト終了後とか辞める時期を考えて辞めていきます。海外の場合、プロジェクトの時期を気にせず、いつでも、しかも頻繁にやめていくので、ランチの時間にせざるをえないケースが結構あります。プロジェクトが忙しくないとき・やめる人が飲み好きで夜にしたいとき・影響の大きい人のときは、ふつうに夜にfarewell partyをやってると思います。
会社のイベントは自由参加
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときは、自分はイベントは喜んで全参加してたので、あまり分からないですが、日本でも断ろうと思えば断れたと思うので、自由参加なのかな？一般的には、強制参加というケースも多いのかもしれませんね。
海外だと、会社イベント（忘年会・新年会・打ち上げ）で、内容によって、家族同伴可のイベントや、恋人同伴可のイベントになったりします。むしろ、恋人同伴可のイベントに、１人で参加するのが、プレッシャー…（; ;）。
仕事に関することは勤務時間内
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
これは、個人によります。基本、勤務時間内ですが、勤務時間外でも勉強できることは、無限にありますし、影で努力している人はいくらでもいます。ちなみに、「ゲームエンジンアーキテクチャ」という業界内ではとても有名な本を書いた人がいるのですが、毎朝５時に出勤して本を書いていたそうです。逆に、勤務時間内にめっちゃ集中して仕事をして、すごい結果を出している人もいます。
出社後は、ゆったりコーヒー飲んでたり朝ご飯食べてたりする
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | △ |
バンクーバーは◎つけたいです。出社後すぐに仕事を始める人は、あまりいなかったかも。キッチンで朝飯を調理してる人もいました。バルセロナ・シンガポールでも、それなりにいます。日本ではアウトでしょう。
こんなかんじです。所詮１人の見識なので、あてにしないように。ただ、いろんな人が、こういうツッコミをいれたら、海外での実態が見えやすくなるかもしれませんね。他の人のツッコミにも期待しましょう。
それでは！
健康について考える(1) - セカンドオピニオンは重要！
実は先月、身内の手術・入院のため（自分じゃないよ）に、兵庫県の病院に3週間ほど滞在してました。近くの施設から入院病棟に通う生活です。そのときに、いろいろ健康について考えさせられました。シリーズになるか分かりませんが、第１回。
(1) セカンドオピニオンは重要！
簡単に書くと、地元の病院（東北では評判良い病院）での診断は、
| 「２つの脳の血管がつながっているところに異常があるので、カテーテル手術は不可能。開頭手術してみないと分からないし、治せない可能性が高い。開頭手術だけでも後遺症もありうる。治さないと、いつでも突然死ありうる。」 |
という感じで、絶望していたのですが、インターネットでいろいろ調べたところ、その症状に詳しそうな先生がいたので、セカンドオピニオンをお願いしてみました。結果、
| 先生「この角度からの写真ではつながって見えるけど、本当はつながってないかも」 →診断受ける 先生「血管の１つに造影剤を入れてみて、つながってたら両方光るし、つながってなかったら片方だけ光るはず」 →確かにそうだと思ったので、検査入院する 先生「１つしか光らなかったので、血管はつながってない別々のもの。カテーテル手術可能です」 →入院・カテーテル手術 →無事退院 |
と、治ってしまいました…。ここまで、医者の能力差があるのかと、驚きました。セカンドオピニオンは活用すると良いと思います。
ただ、お医者さんを探すときに、いろいろ胡散臭そうな人もでてきます…。ちゃんとした人を探すのに、論文とか文献とか調べる能力は、かなり役立つと思います。たとえば、
- 医者のもってる資格・実績は、正当なものか、価値はあるものか調べる。
- 医者の言っている薬・病気・技術などの専門用語を検索してみる。
- 論文発表してるか、発表先がちゃんとした学会を調べる
- 良さげな医者と名前が並列にでてる医者も調べてみる。
というわけで、理系な方はたぶん得意だと思うので、ぜひ良く調べて探してみましょう。もちろん、２人目の意見が必ずしも正しいとは限らないし、悪い結果になることもあると思います。それでも、選択肢が増えるので、良くなる確率は、確実に上がると思いますので、セカンドオピニオンおすすめします。
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。
動的計画法(Dynamic Programming, DP)についての記事です。
12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました
12/11 前編の図２つを差し替えました。
はじめに
まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。
- プログラミングコンテストでの動的計画法
- 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
でも、苦手な人視点からのアドバイスはあまりない気がするので、敢えて書いてみることにしました。ただ、
- 自分以外は誰も悩まなかったポイントかもしれません。
- すこしはコツみたいなことも書いてますが、負け組の考え方である可能性は高いです。
- よって変な癖とかついてしまうかもしれません。
でも、そこはうまく取捨選択してください。というか、むしろ、良い考え方を教えてほしいですorz
対象の読者
- 動的計画法の基本的な問題（0-1ナップザックとか）は、何をやってるかは理解できる。
- プログラミングコンテストチャレンジブック第2版のP52-P55は理解できる
- 自力で動的計画法の問題を解くのは、ほぼ不可能。
- 動的計画法はイメージ？何をイメージしたらいいの？DPテーブルの値が決まってく様子？分からん！
- そもそも漸化式が思いつかないので、イメージ以前の問題
- DPテーブル、変数に何を使えばいいのか、さっぱり分からん
- 動的計画法は中学受験算数の出題範囲→そんなの一般人はやらない。来世に期待！
- 上位の人「DPに逃げました」→ハラスメント
お断り
- 基本的に、プログラミングコンテストチャレンジブックの用語を使います。
- 動的計画法での計算結果を保存する変数を「DPテーブル」と呼び、配列変数の名前をdpとします。
- 「メモ化再帰」「漸化式」等の用語も、そのまま使います。
前編：再帰のやり方とか知ってるのに、どうも「メモ化再帰」がしっくりこないあなたへ
※ 前編で登場する、「枝刈り探索」と「メモ化再帰」のサンプルプログラムです→（http://ideone.com/2B7f4v）あわせてご利用ください。
動的計画法の問題で求めるのは、たいてい次のA,Bだと思います。
| A. 最小値・最大値を求める B. 数え上げ。何個か何パターンかを求める |
自分の場合は、こういうのを求めるとき、仕事でも日常生活でも、以下のような手順で考えていました。
| (1) 選択肢を羅列する (2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。 (3) A. 制約条件を満たしたやつの中での最大値を求める。 B. 制約条件を満たしてたら+1して数えていく。 |
ただ、この手順は、動的計画法（≒メモ化再帰）的な考え方とは、かけ離れているのですよ…。例えば以下の問題を考えてみましょう。
| 0-1ナップザック問題（プログラミングコンテストチャレンジブックより） 重さと価値がそれぞれ、wi,viであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めなさい。 1≦n≦100, 1≦wi,vi≦100, 1≦W≦10000 入力例 n=3, (w,v)={(2,3), (3,4), (1,2)}, W=3 |
「全探索が基本」「樹形図をかけば分かる」というのは、知ってたので、自分は以下のように考えました。
これは「メモ化再帰」ではありませんし、ここから「メモ化再帰」に改良することすらできません。確かに最大値も求まっているし、これでも良い気もしますが、すぐにn≦100という条件をみて、
n=100のとき、2^100通り→こんな問題解けるわけがない→そっとじ
とやってました…。「メモ化再帰」のように、状態の少なさを生かした高速化ができなくなります。
あと、こんな発想をするタイプの人にとっては、「(2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。」は、単にひと手間を複雑にしているだけの邪魔者にしかみえないでしょう…。制約条件は、動的計画法のともだちなんですよ…。（後編で説明します。）
「メモ化再帰」とは、以下の図のようなかんじです。根のほうにデータを集めるような樹形図です。先ほどの図とはデータの流れが真逆なことが分かるでしょう。
ちなみに、「メモ化再帰でない全探索」のあと、少し成長しました。制約条件を破ってたら、以下の図のように、もう計算しないようにしましたが…
「メモ化再帰」では、枝先のほうをまとめて端折っているし、似たような樹形図を見かけますが、これでも「メモ化再帰」とは違います！！ これは、俗にいう「枝刈り探索」です。「メモ化再帰」と「枝刈り探索」を比較してみました。
「メモ化再帰」
-
- int func(int x, int y)のように、関数は値を返す
- 根のほうにデータを集める樹形図。
- 同じ入力値をこの関数の結果を返す、int memo[x][y]のようなメモ用の配列変数がある。
- 計算をはしょれるのは、入力x,yのときの出力（返り値）を、既に知ってるから。
- 計算量が予測しやすい。「メモ用の配列変数の要素数（入力するx,yのパターン数）」*「関数内の計算量」
「枝刈り探索」
-
- void func(int x, int y)のように、関数は値を返さなくてよい。
- 枝のほうにデータが流れていく樹形図、それを集計するかんじ。
- 今まで呼んできた関数（根のほう）での計算結果を、グローバル変数などに保存しておいて（上記の例だと、どの品物を今まで選んできたか）、それを生かすことが多い。
- 計算をはしょれるのは、制約条件を既に違反してたり、最大値・最小値をもう達成することが不可能なため、先の関数を呼ぶ必要がないから。
- 計算量が予測しにくい。
逆に、両者の共通点といえば、「深さ優先探索(Depth First Search)で全探索する」部分ですね。後はいろいろ違うのでごっちゃにしないようにしてください。どちらかが優秀という訳ではないです。同じように混乱したことがある人は、プログラミングコンテストチャレンジブック第２版のP54のCOLUMN、「全探索の書き方」もぜひ読んでください。
メモ化再帰については、先ほど示した資料も含め、良い資料がたくさんあるので、説明は省きます。Have fun and good luck!
後編：動的計画法の意味はわかるけど、問題は解けません！なあなたへ
動的計画法の嫌なところ
- バリエーションが豊富すぎて、手におえない。
- どこから手をつけたらいいか分からない。
バリエーションが豊富すぎて、手におえないのは、しょうがないです。ただ、そのバリエーションの多さに、基本的なことの検討を見逃して、動的計画法の割には簡単な問題をおとしてしまうのは、避けたいです。
あと、どこから手をつけたらいいか分からない問題について。DPで問題を解くためにクリアするべき点が3つあります。
- (1) DPテーブルの定義 dp[?][?]=?
- (2) 漸化式をたてる
- (3) 状態・計算量を減らしてみる
これらが、(1)→(2)→(3)のように、順番にクリアしていくことができればいいのですが、多くの問題の場合は(2)ができないので(1)を直すとか、(1)を変えたら(3)の計算量が増えたとか、3つとも複雑に絡み合うので、やっかいなんですよね…。まぁ、1つずつ見ていきたいと思います。
(1)DPテーブルの定義 dp[?][?]=?
- まずは基本的な形から検討しましょう。
- 一番の基本は、「dp[?][?]=問題で求めるもの（最大値とか個数とか）」です。まずは、これから検討しましょう。これが通用しない場合もあるのですが、それでも基本から検討しましょう。
- インデックスのほうで、dp[0番目〜i番目までの何か]のように、何かの番号がくることが多いです。
- DPテーブルの定義のバリエーションは、無限にあるわけではない
- 問題に出てくる変数の種類はせいぜい2種類〜5種類程度です。例えば、ナップサック問題だったら、重さ・価値・品物番号の３種類です。dp[番号][重さ]=価値とか、dp[番号][価値]=重さとか、いろいろつくれますが、それでも無限にあるわけではないです。がんばれ！
- 変数の定義はちゃんとしましょう。
- 動的計画法とは、直接関係ないのですが、変数の定義をちゃんとするのは、動的計画法では特に重要な気がします。結構、人によって、要素が1個ずれてたり（iがi+1になったりi-1になったり）ということはあるのですが、それは変数の定義が違うからですが、ちゃんと漸化式とつじつまがあってれば正解になります。
- 具体例1 ナップサック問題
- × dp[品物番号i][重さ]=価値
- ○ dp[品物番号i][0〜i-1番目までの重さ]=0〜i-1番目までの価値の合計 （特に0〜i-1とか範囲の部分が重要）
- 具体例2 SIRO Challenge http://jag2013autumn.contest.atcoder.jp/tasks/icpc2013autumn_c
- × dp[訪問都市（ビットで）][現在いる都市]=時間
- ○ dp[ラーメン屋のある訪問した都市（ビットで）][現在いる都市]=スタート地点から現在の都市までの移動時間＋現在いる都市でラーメン食べる時間も含めた合計時間
- 複数の解法がありうるので、ちょっと無駄な要素があってもOKな場合がある。
- O(n^2)のDPだけど、O(n^4)でもOKみたいな問題もあります。メモリ・計算量の許すのであれば、ちょっとぐらい無駄な要素があってもOKです。分かりやすい、書きやすいほうを選びましょう。
- DPの配列に慣れましょう。
- 動的計画法で、出てくる配列は、dp[100000][4][4][4]とか、dp[50][50][50][50]とか、日常プログラミング生活では、あまり見ないような配列がでてくることがあります。メモリ・計算量の許す限り、どんな形でもとりうるので、念頭に置いておきましょう。
(2) 漸化式をたてる
- まずは基本から
- kinabaさんの昔の記事にあるとおり、http://www.kmonos.net/wlog/90.html#_1712081024、dp[x][y]と定義したら、dp[x][y]とdp[x-1][y]、dp[x][y]とdp[x][y-1]にどういう関係があるかというのを着目したほうが良いと思います。例外は腐るほどあるのですが、例外から考えるとバリエーションがあまりに多すぎて死にます。まずは基本から検討しましょう。
- 確率のほうがやりやすい
- 確率問題は、わりと自然と漸化式がでてきやすい気がします。1/3の確率で+100点、2/3の確率で-50点だったら、dp[turn+1] = (dp[turn]+100)/3 + (dp[turn]-100)*2/3 のように、確率の公式そのものが漸化式になりうるので。
- 法則を見つけるコツ
- 小さいケースで考えてみる（n=1,n=2,n=3のときとか）
- 樹形図を書くと、法則が見えてくることもある。SRM531 DIV1 Easy NoRepeatPlaylistが好例
- 分割する。範囲DPや、グループ分けするようなビットDPでは、dp[全体]は、dp[分割した部分1]とdp[分割した部分2]の関係式で表せることが多いです。用語「最適性原理」も一度はチェックしてみてください
(3) 状態・計算量を減らしてみる
「状態」とは、DPテーブルでいったらdp[x][y]、再帰関数だったら int dfs(int x, int y)の(x,y)の組み合わせのことを指します。状態が多すぎると、計算時間が間に合わないので、解けません。どんな減らし方があるか書いてみました。
- 制約条件
- まず、制約条件が重要です。例えば、ナップサック問題で、「重さ≦1000000、価値≦100」という条件をみたら、「価値の範囲が狭い」→「dp[価値]のようにDPテーブルを定義したら、うまくいくのでは？」と思いましょう。
- 結果が同じになる状態はないか？
- 例えば、dp[100000000000]と、状態が無数にあるような場合でも、例えば、インデックスが奇数・偶数で値が同じになるなら（dp[0]=dp[2]=dp[4]=...、dp[1]=dp[3]=dp[5]=...）となるなら、dpテーブルはdp[2]で十分になります。
- 周期性、鳩の巣原理、偶数奇数のような法則があれば、結果が同じになる状態があるはずです。状態を減らすチャンス！
- もう古い状態は無視できるのではないか？
- 例えば、3手前以前に何の手をうったかは影響ないのであれば、dp[手数][2手前][1手前][現在]という風に削ることもできます。
- プログラミングコンテストチャレンジブックP177「ドミノ敷き詰め」のように、上から順番に埋めてって、もう下のドミノに影響を与えないような上部内側の部分も、無視できますね。
- 中は無視して、端だけで良いのでないか？
- 区間DPは典型例です。例えば文字列を使う問題なら、dp[左端][右端]としただけで、文字列が定まります。dp[左端][右端][上端][下端]とやれば、2次元の範囲が定まります。
- 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」、「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」と、計算量を落とせないか考える
- 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」については、巡回セールスマン問題等で使うテクニックです。最小移動時間を求めるのに、dp[3→2→7→5]もdp[2→3→7→5]もdp[7→3→2→5]も、同じ状態とみなして良いです。なぜなら、これらから次の都市も含めた場合の最小移動時間を求めるときに、どうたどってきたかを知る必要はなく、すでに通過した都市（順序なし）と、現在いる都市が分かれば、次の都市を選べるからです。
- 「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」で計算量を落とせることもありますが、見破るのはかなり難しいことも。例題としては、SRM511 DIV1 500pts FiveHundredEleven。
- (1)に戻って、dpテーブルの定義を見直せば、状態を減らせるかも。
- 「○○がX以下で，△△を最大化しなさい → △△がいくらまでなら，○○の最小値はX以下になるか？」の置き換えで、配列のインデックスと、配列の値を交換することができます。
おわりに
- メモ化再帰と枝刈り探索は、違います。普段、枝刈り探索っぽい考え方をしている人は、頭を切り替えましょう。
- 動的計画法は、問題のバリエーションが多いのですが、まずは基本的なところから検討しましょう。
- 企画倒れ感のある内容になってしまいました。超苦手な人向けになってない気がします。
- 他の方のフォロー記事に期待！
焼きなまし法のコツ Ver. 1.2
↓改訂版 Ver1.3はこちらから↓
shindannin.hatenadiary.com
2016年8月18日 Ver. 1.2 内容を更新しました。
4.遷移確率と温度の部分を全般的に修正
この記事は、Competitive Programming Advent Calendar Div2012の24日目の記事です。
http://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9
素晴らしい企画をしていただいたtanzakuさん（https://twitter.com/_tanzaku_）、今年もどうもありがとうございます！
焼きなまし法そのものの解説は少しだけにして、焼きなまし法の使い方のコツをメインに書こうと思います。
焼きなまし法の概要
2015年5月26日 内容を更新しました。
最適化（=最大値か最小値を求める）の手法の１つです。以下は、てきとーな擬似コードです。
あらかじめ、計算する時間をTを決める。
以下のスコープ内のコードを時間T経過するまで繰り返す。
{
適当に、次の状態（近傍）を選ぶ。
(1) 次の状態のスコアが、今の状態のスコアより良くなった場合は、常に、状態を次の状態にする（遷移）。
(2) 次の状態のスコアが、今の状態のスコアより悪くなった場合でも、ある確率で、状態を次の状態にする。
確率は以下のように決める。
(2.A) 序盤(時刻t=0に近いとき)ほど高確率で、終盤(t=Tに近いとき)ほど低確率。
(2.B) スコアが悪くなった量が大きければ大きいほど、低確率。
}
最後に、今まで一番スコアのよかった状態を選ぶ。
次の状態が悪くてもそれを選ぶ可能性がある(2)の部分が、焼きなまし法の最大の特徴です。
「状態」「スコア」というのがピンとこないかもしれませんが、
- もし、巡回セールスマン問題であれば、
- 状態 →ルート
- 次の状態（近傍）→元のルートをちょっとだけかえてみたルート
- スコア →総距離
- もし、y=f(x)の最大値を求める問題であれば、
- 状態 →x
- 次の状態（近傍）→ x' = x + a (aは小さめの値)
- スコア →y
といったかんじです。
一応、参考までに、Marathon Match 60で使ったコードの断片を貼っておきます。全然難しくないです。
2015年4月20日 追加
以下のコード例は、上記の(2.B)の部分を無くした、スコアが悪くなった量は考慮しない焼きなまし法です。もっと効果的な方法「4. 遷移確率と温度」は必ず見てください。
vector <int> PolymerPacking::mirrorSequenceSI(ll msec) { vector <int> currentSeq; // 現在の状態。この問題では、vector <int>が状態だけど、問題によって大きく異なる。 // 現在の状態の初期化。この部分は問題によっていろいろなので、あまり気にしないでください。 const int L = 5; const int MAXMIR = 5; for (int i = 0; i < MAXMIR; i++) { currentSeq.push_back(0); } vector <int> bestSeq = currentSeq; // ベストの状態 double bestScore = getScore(currentSeq); // ベストスコア。getScoreは、状態からスコアを求める関数 double currentScore = bestScore; // 現在のスコア { const ll saTimeStart = getTime(); // 焼きなまし開始時刻。getTimeは、時間を返す関数 const ll saTimeEnd = m_startTime+msec; // 焼きなまし終了時刻。m_startTimeはこのプログラム自体の開始時間 ll saTimeCurrent = saTimeStart; // 現在の時刻 while ((saTimeCurrent = getTime()) < saTimeEnd) // 焼きなまし終了時刻までループ { vector <int> nextSeq(currentSeq); // 次の状態 nextSeq[rand()%MAXMIR] = rand()%(L-1); // 次の状態を求める。ランダムで1要素選んで、変えてみる。 const double nextScore = getScore(nextSeq); // 最初t=0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用 // 最後t=Tのときは、スコアが改善したときのみ、nextを使用 const ll T = saTimeEnd-saTimeStart; // 焼きなましにかける時間 const ll t = saTimeCurrent-saTimeStart; // 焼きなまし法開始からの時間 const ll R = 10000; // スコアが悪くなったときでも、次の状態に移動する遷移する場合はtrue。１次関数を使用。 const bool FORCE_NEXT = R*(T-t)>T*(rand()%R); // スコアが良くなった or 悪くなっても強制遷移 if (nextScore>currentScore || (FORCE_NEXT && currentScore>0.0f) ) { currentScore = nextScore; currentSeq = nextSeq; printf("current Score=%.8f time=%lld\n",currentScore,t); } // ベストスコアは保存しておく。 if(currentScore>bestScore) { bestScore = currentScore; printf("New best Score=%.8f time=%lld\n",bestScore,t); bestSeq = currentSeq; } } } // ベストスコアをしたときの状態を返す。 return bestSeq; }
焼きなまし法のコツ
★が多いところほど、自分では重要だと思ってます。自信がないので、「こういうやり方もあるよ」「それはない…」「嘘乙」など、アドバイス大歓迎です！
1. 高速化
たくさんwhileループ内を回せば回すほど、スコアが伸びる可能性があります。基本的にはボトルネックを調べて、そこを高速化しましょう。だいたい以下のところがボトルネックになるでしょう。
★★★★ 変更がある変数だけを保存して、戻す
先ほどのコードだと、
vector <int> nextSeq(currentSeq); // 次の状態 nextSeq[rand()%MAXMIR] = rand()%(L-1); // 次の状態を求める。ランダムで1要素選んで、変えてみる。
とやっていますが、これでは時間がかかります。。次の状態を全てコピーしたのち、１つの要素を変えています（しかもvectorで動的にメモリ確保もしてます…）。高速化するなら、
const int index = rand()%MAXMIR; // 変更する要素 const int backup_value = currentSeq[index]; // 変更前の値 currentSeq[index] = rand()%(L-1); // 以下currentSeqをnextSeqとみなす。 const double nextScore = getScore(currentSeq); // 最初t=0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用 // 最後t=Tのときは、スコアが改善したときのみ、nextを使用 const ll T = saTimeEnd-saTimeStart; // 焼きなましにかける時間 const ll t = saTimeCurrent-saTimeStart; // 焼きなまし法開始からの時間 const ll R = 10000; // スコアが悪くなったときでも、次の状態に移動する遷移する場合はtrue確率。この場合は単に１次関数を使用。 const bool FORCE_NEXT = R*(T-t)>T*(rand()%R); // スコアが良くなった or 悪くなっても強制遷移 if (nextScore>currentScore || (FORCE_NEXT && currentScore>0.0f) ) { currentScore = nextScore; // currentSeq = nextSeq; ←すでにnextSeqになってる。いらない。 printf("current Score=%.8f time=%lld\n",currentScore,t); } else { // アンドゥ。次の状態に移動しないので、バックアップしてた値に戻す currentSeq[index] = backup_value; }
とやりましょう。
★★ 逆の手で、戻す
逆の手をやれば、前の状態に高速に戻せるのであれば、そうしましょう。例えば、上下左右に駒をうごかせるというパズル問題であれば、左に動かした後、右に動かせば、戻せるかもしれません。
★★★★ スコア関数の高速化
スコア関数の求め方は問題によって大きく異なるので、計算時間も異なってきます。ボトルネックになってたら高速化しましょう。
また、スコア関数の正確さを犠牲にしてでも、高速化したほうが良い場合もあります。１つのコツとして覚えて置きましょう。
★★ C言語のrand()を使わない。
C言語のrand()は遅いので、高速なxor128を使いましょう。
unsigned int randxor() { static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; unsigned int t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); }
★★ 時間計測の関数を呼びすぎない。
上にあげたコードは、時間計測の関数を呼びすぎです。。getTime関数は高速ではなく、それがボトルネックになる可能性もあります。例えば、最初のコードなら、以下のように100回に1回だけ時間を測るというようにできます。
while ((saTimeCurrent = getTime()) < saTimeEnd) // 焼きなまし終了時刻までループ { for(int loop=0; loop<100; ++loop) {
ただ、TopCoderだとループ回数を増やしすぎると、ループしている間に、制限時間オーバーしてしまうという可能性もあります。そういった点も考えて、適切な回数だけ時間をはかるようにしましょう。残り時間が少なくなったら、ループ回数を減らすといった安全策をとる方法もあります。
あと、高速化に夢中になる前に、
★★★★ 高速化がどれだけ効果的か検討する。
のも重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。
- 時間をかければかけるほどスコアが伸びる
- 高速化しよう＆スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
- 時間をかけてもスコアが伸びない & スコアが高い
- 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
- 時間をかけてもスコアが伸びない & スコアが低い
- 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに。
2. 次の状態（状態近傍）をどう決めるか？
ここは鍵になる部分ですが、コツとしてまとめるのは難しいところですね…。
★★★★ スコアが改善しやすくなるように、次の状態を選ぶ。
これは、問題ごとによく考えて対処しなければいけないので、あまり「コツ」というかんじではないのですが…。
[問題] タスク数aの仕事Aと、タスク数bの仕事Bがある。作業員はx人いて、それぞれ、1時間あたりにこなせる仕事Aのタスク数と、仕事Bのタスク数は決まっている。ただし、仕事Aの仕事Bのどちらかしか行うことができない。仕事Aと仕事Bの両方が終わるのに時間が最小になるように、作業員を仕事Aか仕事Bのどちらかに割り当てよ。
焼きなまし法で解くなら、まず最初にてきとーに作業員をA,Bに割り振り、ここからスコア＝作業時間として、改善させていきます。こういった問題を解くときに、次の状態として以下の２つを考えてみましょう。
- 移動：ある作業員をA→B または B→A に移動させる。
- 交換：Aの作業員の誰かと、Bの作業員の誰かを交換する。
移動２回は交換になることもあるので、とりあえず移動をさせておけば、交換もたまにしてくれるし良さそうに見えますが、そうとは限りません。この場合は、交換を主に行い、たまに移動させるぐらいがちょうど良いと思います。移動では、人数が偏り、片方の仕事の作業時間が増えやすくなります。２回移動すれば、交換になって、作業時間が減る可能性がありますが、
- 移動：良スコア → 悪いスコア → とても良いスコア
- 交換：良スコア → とても良いスコア
と考えると、移動だけだと、スコアが悪い状態を経由しないとダメなので、運がよくないと、とても良いスコアまで辿りつけません。その点、交換ならば、人員が偏った悪いスコアになりやすい状態をスキップできるので、スムーズにとても良いスコアまで改善できます。
もちろん、正しい人数割り当てもしなければいけないので、移動も少しは試したほうがいいですが、こういった点も考えて次の状態を決めると、スコアが改善しやすくなります。
★★ Greedyに、次の状態を選ぶ。
先ほどの問題であれば、「仕事Aと仕事Bそれぞれから、常に作業時間が一番多くかかっている人を1人ずつ選び、交換」とGreedyに、次の状態を選ぶことができます。こういう選び方をすると、ベストスコアは序盤はどんどん伸びていきますが、局所最適に陥りやすいです。また、ありがちなのが、Greedyに選ぶアルゴリズムが、計算時間のボトルネックになってしまうパターンです。複雑なアルゴリズムより、ランダムでとにかくいろいろ試すのが焼きなまし法の強みです。Greedyにやるにせよ、多少ランダムを入れたり、計算時間はかからない単純な選び方をしたりする工夫が必要です。
★★ 序盤は大きく変化、終盤は小さく変化させたほうがいい。
山登り法と同じ考えです。
単純にy=f(x)のyを最大化する問題なら、
- 序盤(t=0に近いとき) 次のx'は x'=x+rand()%1001 - 500
- 終盤(t=Tに近いとき) 次のx'は x'=x+rand()% 11 - 5
とか、
作業員割り当ての問題なら、
- 序盤(t=0に近いとき) 交換を100回やる
- 終盤(t=Tに近いとき) 交換を 1回やる
といったかんじです。スコアが局所最適でハマっている場合は有効です。ただ、焼きなまし法自体が、局所最適にはまりにくいアルゴリズムなので、あまり効果がない場合も多いです。
★★ 良い初期状態からスタートする
2015年5月26日 追加しました。
これは問題に大きく依存する項目です。初期状態はてきとーでも良い場合と、すこし時間をかけて計算して良い状態から始めたほうが良い場合があります。特に、初期状態が悪いと状態を改善する近傍の選択肢が少なすぎる、逆に言えば、状態を改善すればするほどさらに改善できる可能性が増えるタイプの問題は、初期状態に少し時間を書けて求めて、それから焼きなましたほうが良い結果がでる場合があります。
3. スコア関数
スコア関数（scoring function）とも、評価関数（evaluation function）とも呼びます。
★★★★★ 良い状態を正しく評価できるような、スコア関数を新たに用意する
問題のスコア関数をそのまま使うと、焼きなまし法がうまく行かないことがあります。良い状態を正しく評価できるような、新たなスコア関数を用意しましょう。
[問題] （大きく略）… i番目の人の満足値をs(i)とする。「満足度の最小値 min s(i) 」を、最大化しなさい。
この問題は「満足度の最小値 min s(i) 」を最大化する問題なので、素直に考えると、スコア＝「満足度の最小値 min s(i) 」としたくなりそうですが、これは良くありません。仮にそうした場合、
状態A s(0)= 10, s(1)=10, s(2)= 10 のとき、スコアはmin{s(0),s(1),s(2)} = 10
状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 10と状態Aと状態Bのスコアは同じになってしまいます。これはスコアは同じといえ、状態Bのほうが明らかに良い状態です。なぜなら、s(1)の点が仮に300点に増えたとしたら
状態A' s(0)= 10, s(1)=300, s(2)= 10 のとき、スコアはmin{s(0),s(1),s(2)} = 10
状態B' s(0)=1000, s(1)=300, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 300と状態Bのほうは一気にスコアが増えます。しかし元のスコア関数のままだと状態Aと状態Bは同じスコアで、状態A→状態Bはスコア改善になりません。つまり焼きなまし法を行っても、状態A→状態Bには運が良くないと移動しません。
この問題であれば、例えば、
スコア＝1番小さいs(i) + 0.0001 * 2番目に小さいs(i)
とすれば
状態A s(0)= 10, s(1)=10, s(2)= 10 のとき、スコアは 10 + 0.0001 * 10 = 10.001 状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアは 10 + 0.0001 * 1000 = 10.1
と状態Bの方が好スコアになり、状態A→状態Bに移動しやすくなります。
ここは問題によって大きく有効かどうか大きく異なってきますが、必ず考慮に入れたほうがいいでしょう。結果に大差がつきやすいポイントです。
★★★スコアが改善しやすくなるようなスコア関数を決める。
2015年5月26日 追加しました
上記の言い換えともいえるのですが、わりと焼きなまし法のスコア関数をつくるときに、問題のスコア関数をそのまま使ったり、違う状態を正しく評価しなかったりすると、同じスコアになりがちで、青い線のような飛び飛びの平坦な関数になることが多いです。近傍に同じ値が続くと、焼きなまし法をやっても状態が行ったりきたりするだけで、解がなかなか改善しません。赤いように、山登りしやすいスコア関数を作れないか考えましょう。必ずしも、問題のスコア関数の最大値と、焼きなまし法で使うスコア関数の最大値が一致する必要はありません。最大値をとりうるような状態（argmax）を一致させることが重要です。
4. 遷移確率と温度
たいていの焼きなまし法の解説書には、expを使った方法が載っています。
焼きなまし法 - Wikipedia
遷移確率 P(e, e' , T) は e' < e の時に 1 を返すよう定義されている（すなわち下りの移動は必ず実行される）。
そうでない場合の確率はexp((e−e' )/T) と定義
注：wikipediaの引用なので、本文の設定と違います。
ここでのTは温度（=時間とともに減っていく値）です。
最小化問題なのでe−e'となってます（最大化問題ならe'-eです）。
★時刻tに置ける温度Tを調整する
最初の例の以下のコードの部分です。
const bool FORCE_NEXT = R*(T-t)>T*(rand()%R);
上の例だと、
- t=0のとき、常にtrue
- t=Tのとき、常にfalse
になるような線形関数にしています。だいたいの場合は、これで問題ありませんが、バリエーションはいろいろ考えられます。実際には、ベストスコアの更新状況をみて、更新があまりに序盤と終盤に固まっているときは、２乗してみるとか、ロジスティック曲線をつかうとか、その程度で良いと思います。
★★★★exp(e-e')/Tを使う。（e-e':スコアの悪化量）
2015年5月26日 重要度を★★★から上げました。全般的に内容を更新しました。
wikipediaでは以下のように書いていますが、exp(e-e')/Tの形にしたほうが良いでしょう。（理由は、次回の改定時に書きます）
関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。 つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、 どんどん上昇している場合よりも高いという考え方である。しかし、この条件は 必ずしも必須ではなく、上記の必須条件が満たされていればよい。
ただ、このexpの式、分子はスコア差なので分かりますが、分母の温度をどう決めれば良いかは分かりづらいです。目安としては、たまには許容しても良いスコアの悪化量を温度とすると良いです。 最大の山を越えられるようにと考えると、考えられるスコアの最大値-最小値を初期温度を設定したほうが良いと思います。（理由は、次回の改定時に書きます）
double startTemp = 100; double endTemp = 10; double temp = startTemp + (endTemp - startTemp) * t / T; double probability = exp((nextScore - currentScore) / temp); // 最大化なので、分子はnextScore - currentScoreで良い。 bool FORCE_NEXT = probability > (double)(mXor.random() % R) / R;
時刻t=0（最初）でtemp=startTemp、時刻t=T（最後）でtemp=endTempとなります。
例えばスコアが100悪化したとき、nextScore - currentScore = -100なので、startTempを100にしてみます。endTempはとりあえず10にしてみましょう。
時間t=0であれば、exp(-100/100) = exp(- 1) = 0.36787944117と、3回に1回ぐらいは遷移します。
時間t=Tであれば、exp(-100/ 10) = exp(-10) = 0.00004539992と、まず遷移はしません。
このような感じでやると、良いと思います。
5. アレンジ
★★★★ 山登り
最初の例をFORCE_NEXT=0にすれば、山登り法になります。そもそも関数が凸であれば、山登り法も焼きなまし法も結果は一緒で、しかもrand()を使わない分、山登り法のほうが高速で、スコア改善のチャンスも多くなります。簡単に試せるので、試しましょう。
★ 多点スタート
2015年5月26日 重要度を★★から下げました。内容を更新しました。
焼きなまし法をつかっても、局所解にはまりやすい場合は、初期値を毎回かえた、多点スタートにする方法もあります。山登りと同時に使う方法もあります。ただ、多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。
★★★ 1変数ごとに焼きなまし
焼きなまし法で、たとえば、y = f(x1,x2,x3,x4,x5)と、状態変数が多いとき、次の状態のパターンが多くなり、結果的にあまり多くの状態を試せず、良い解が求められないときがあります。このような場合は、x2=x3=x4=x5を固定して、x1を焼きなまし、x1=x3=x4=x5を固定して、x2を焼きなまし、x1=x2=x4=x5を固定して、x3を焼きなましというふうに１変数ずつ焼きなまししていく方法があります。xの値がそれぞれ独立性が高い(?)場合は、この方法は有効です。 ←要検討…
ゲームプレイとモーションの依存について
ネットの記事や本では、取り上げられることはほとんどなく、新しいことでもないですが、製作が長期に渡ることが多い市販のゲームでは、重要になってくる部分なので、まとめてみました。ゲームのジャンルによって、認識が大きく異なってくる部分でもあるので、いろんな視点からご意見をいただけると非常に嬉しいです。
読者対象：モーションを使って、ゲームを作ったことがあるプログラマ
注：この記事内の用語について ・ゲームプレイ：ゲームスレッドで動く、入力・移動・コリジョン判定・スコア更新といった、ゲーム部分を指します。 ・レンダリングスレッド：ゲームスレッドから結果を受け取り、モデルを描画するために、GPUに描画コマンドを送るスレッドです。 ・モーション計算：モーションデータから骨の位置・回転データを取ってきて、骨の木構造に沿って計算をし、各骨の位置や向きを求める計算の部分です。 ・アニメーション：この記事では、絵の部分だけを指します。 ・ゲームデザイナー：この記事では、「レベルデザイナー」「企画」と読み替えてもらってかまいません。
1 はじめに
図１：格闘ゲームのパンチ
2Dのゲームでは、図１のように「移動・コリジョン判定」と「キャラクターアニメーション」は別であり、「キャラクターアニメーション」が「移動・コリジョン判定」に直接影響を与えることは、まずありませんでした。
その後、ゲームに3Dの技術が導入されると、「モーション」が現れました。「モーション」は、「移動・コリジョン判定」にも「キャラクターアニメーション」にも両方に使用できます。現実の世界では、これらは完全に一致します。例えば、パンチをすれば、手が移動し、手があるところにコリジョンがあり、手があるところに手が見えます。ここから
「『移動・コリジョン判定』と『キャラクターアニメーション』を一致させれば、ゲームはリアルになる」
という考えもでてきました。これ自体は問題なく、それを目指してうまくいっているゲームもあります。
しかし、「移動・コリジョン判定」＝「キャラクターアニメーション」と理解し、これらの依存関係などを気にせずゲームをつくると、後で大きな問題を引き起こしてしまうことがあります。今回の記事では、それについて述べたいと思います。
2 モーションに依存する実装と依存しない実装
2.1 例1 「弾を詰めて、大砲をうつ」
図２：弾を詰めて大砲をうつ、モーションの１ループ
ボタンをおすと、図２のようにキャラクターが大砲に弾を詰めたのち、弾をうつという状況を考えます。
(A)ゲームプレイがモーションに依存している実装例
注：今後出てくる擬似コードは、ゲームプレイ側のコードです。モーションライブラリのコードではありません。
if (弾を詰めるモーションが終了している && Aボタンを押した)
{
弾を発射
弾を詰めるモーションを再生する
}
(B)ゲームプレイがモーションに依存しない実装例
t = モーションの長さ（時間）
if (モーション再生開始からt秒経過した && Aボタンを押した)
{
弾を発射
弾を詰めるモーションを、ちょうどt秒間で再生が終了する速度で、再生開始する。
}
これらは、ほとんど同じに見えますが、全然違います。(A)はモーション側に、モーションの再生終了を問い合わせるので、ゲームプレイがモーションに依存しています。それに対して(B)は、ゲームプレイ側からモーション側に時間を渡していますが、モーションからデータを受け取ることはなく、モーションの経過時間もゲームプレイ側で管理しています。
例えば、「弾をどんどん発射したい。」という要望があった場合、(A)は、モーションデザイナーがモーションデータを変更して、モーション再生時間を短くするでしょう。(B)は、プログラマーがtの値を減らすか、ゲームエディタでtが調整可能な場合は、ゲームデザイナーが変更することになるでしょう。
一見、役割がかわるだけで、あまり変わらないように見えますが、(B)にはメリットが多くあります。
2.2 (B)モーションに依存しない実装のメリット
モーションに依存しない実装のメリットを5つあげてみます。
(B)のメリット1 : ゲームバランスの調整がしやすい
ゲームデザイナーが自由にパラメータを変更できる(B)は、いちいちモーションデザイナーにモーションの長さの変更を頼む必要もなく、ゲームバランスの調整がしやすく、有利です。
(B)のメリット2 : モーションデザイナー・ゲームデザイナーともに、時間を有効に使える
ゲームプレイがモーションに依存している場合は、モーションデザイナーがモーションを変えると、ゲームバランスが変わってしまいます。これでは、ゲームバランスの調整をいったんしたとしても、モーションの変更でゲームバランスが崩れてしまうので、
「モーションデータの変更を締め切る」→「その後、ゲームデザイナーがゲームを調整」
という流れにせざるをえません。こうなると、
- モーションデザイナーは、締め切りが早まってしまい、プロジェクトの締め切りギリギリまで、モーションを改善するということはできなくなる。
- ゲームデザイナーは、モーションデザイナーがモーションを完成するまで、待つことになる（それ以前にもゲームバランスの調整はできるけど、無駄になる可能性もでてくる）
となり、双方とも時間を損します。
(B)のメリット3 : デバッグがしやすくなる。
モーションがゲームプレイに影響しないということは、モーションデータやモーションのソースコードが変わっても、ゲームへの影響はありません。例えば、
「もともと1秒おきに砲弾をうてたのに、なぜか10秒おきにしかうてなくなってしまった」
というバグが発生したとしましょう。(B)であれば、このバグは明らかにゲームプレイのバグなので、先ほどのコードの部分だけ確認すればデバッグは容易でしょう。しかし(A)だと、ゲームプレイのバグかもしれませんし、モーションデータがおかしいだけかもしれませんし、モーションコンバーターのバグかもしれません。デバッグで疑うべき部分が一気に増えてしまい、デバッグに時間がかかってしまいます。
(B)のメリット4 : 早回しができる
早回しとは、ゲームを通常の速度より高速に実行することです。これには様々なメリットがあります。
- 同じ時間で、ゲームをより多く実行することができるので、ゲームプレイ部分のデバッグの際に有利。例えば、10msで動いてたゲームが、5msで動けば、バグ再現までの時間が半分になる。10時間に1回しか発生しないバグを、5時間に1回発生させることができる。
- 対戦モードがあるゲームであれば、CPU同士の対戦時間を高速化することができる。この結果は、ゲームのバランス調整に使うこともでき、また、CPU同士の対戦を実際に行うシミュレーションゲームなどでは、そのまま使用することもできる。
(B)の場合はいっさいモーションの計算をせずにゲームを実行することが可能です。モーションの計算時間は、ゲームの処理時間の中でも大きな割合を占めることが多いです。モーションの計算時間を短くすることで、早回しの際に有利になります。
ちなみに、早回しをしたい場合は、ゲームスレッドだけを実行できる（グラフィックは無視する。もちろん垂直同期も待たない）必要があります。そもそも、その設計ができてないゲームエンジンを過去に見たことがあるので、気をつけてください。
(B)のメリット5 : 低スペックマシンへの移植がしやすくなる
スマートフォン・携帯ゲーム機・コンソール機・PC、マシンの性能はさまざまです。例えばPS3版で3Dポリゴンを使ってたゲームを、スマートフォンに移植することを考えます。スマートフォン版では2Dスプライトで表示、ただしゲームプレイはPS3版のまま変えたくないとしましょう。このとき、モーションに依存してないのであれば、スマートフォン版は単に2Dスプライトに置き換えれば終了です。しかし、モーションに依存した実装だと、スマートフォン版でも、モーション計算をせざるを得ず、処理落ちを起こしてしまうかもしれません。
2.3 (A)モーションに依存する実装のメリット
(A)にもメリットはあります。
(A)のメリット1 : モーション制御技術を必要としない。プログラマーが、モーション制御の技術を持ってなくても良い。
例えば、(B)の場合、「もともとt秒だったモーションを、s秒で再生する」という機能が必要になります。これはさすがに「再生速度を変更する機能を追加し、s/t倍速で再生する」だけで、まぁ良いでしょう。ただ今回のケースはもっとも単純で、実際にはモーション制御は、もっと難しいです。
(A)のメリット2 : 無理なモーション制御による、アニメーション品質の低下がおきにくい。
例えば、(B)の場合、ゲームデザイナーが、「0.3秒おきに砲弾を打てるようにしたい」とするかもしれません。これだけ短くなると、単に0.3/t倍速再生しただけでは、アニメーション的には、とても変になることが想像できると思います。
また、仮に1.1倍速で、ほとんど再生速度が変わらないといった場合でも、人間の動きはそんなに単純ではありません。速く動こうとすれば、動作自体も違ってきます。それであれば、1.1倍速用のアニメーションを、モーションデザイナーに作ってもらったほうが良いでしょう。
ただ、(B)でも、まずゲームデザイナーがいったん調整して、アニメーションの時間を確定したのち、モーションデザイナーにアニメーションを作ってもらうという風にすれば、問題はありません。
3 ゲームプレイ用のモーションデータを用意する方法
3.1 例2 「ボールをしゃがんで避ける」
図３：ボールをしゃがんで避けるゲーム
主人公の頭をめがけて、ボールがどんどん飛んできます。ぶつかったらゲームオーバーです。主人公は普段は動けませんが、ボタンを押すとしゃがんで避けることができます。タイミングよくボールを避けましょう。
(A2)ゲームプレイがモーションに依存している実装例
if (避けるモーションが終了している && Aボタンを押した) { 避けるモーションを再生する } 現在の時間のモーションの骨位置を計算し、頭の位置を求める if(頭の位置がボールと重なった) { ゲームオーバーへ }
さて、この例で、モーションに依存せずに、実装することはできるでしょうか？
「頭の位置を計算しないといけないから、モーションに依存するのは当たり前だろう」
と思うかもしれませんが、何個か対策はあります。
(B2.1) ゲームのルールを単純にする。
「Aボタンを押して、避けるモーションが再生している間は、無敵」としてしまいましょう。モーションはt秒間再生するということにします。それであれば、以下のような実装で済み、モーションに依存しません。
t = モーションの長さ（時間） if (モーション再生開始からt秒経過した（=避けてない） && Aボタンを押した) { 避けるモーションを、ちょうどt秒間で再生が終了する速度で、再生開始する。 } if((モーション再生開始からt秒経過した && もともとの頭の固定位置に、ボールがある){ ゲームオーバーへ }
ゲームによってはこれで良い場合もありますが、厳密ではありません。例えば、実際ボールが頭にかすってるように見えるのにもかかわらず、避けるモーション再生中ということで、ゲームオーバーにならないといった問題が起こりえます。また、ゲームが少し複雑になり、いろんなところにボールが飛んでくるようになったら、この方法ではうまくいきません。
(B2.2) 頭の位置yはゲームプレイ側で動かす。そして、モーションの頭の位置がyにくるようにモーションを制御する。
モーション経過時間uから、頭の位置yを決める（例えば y = 1.5+0.5*cos(u*2π); ) モーションを計算するスレッドに、頭の位置yを渡す if(頭の位置yと、ボールが重なった) { ゲームオーバーへ }
この実装の問題としては、まず頭の位置をてきとーに三角関数で動かしてみましたが、実際は、これで人間っぽい動きでなくなってしまう可能性が高いです。普通、しゃがむときの頭の動きはもっと複雑です。
また、モーションを計算するスレッドでは、受け取った頭の位置yから、アニメーションを決める必要があります。ここでモーションの制御方法も、いくつかあります。
- (1) 頭の位置yとモーションのマッピング（yごとに対応する姿勢を用意する）
- (2) モーションブレンド（立っている姿勢と、しゃがんでいる姿勢のブレンド）
- (3) IK（腰・足・頭を決め、その他の骨の位置をInverse Kinematicsで決める）
この例だと、どれもあまり旨くいかず（(1)が一番マシかと思いますが…）、アニメーション品質は落ちる可能性が高いです。
つまり、(B2.1)ではゲームの質が下がる、(B2.2)ではアニメーションの質が下がる可能性があります。
3.2 ゲームプレイ用のモーション
(A)(B)とは違った別の解決方法もあります。
(C) ゲームプレイに使うモーションデータと、アニメーションに使うモーションデータを分け、ゲームプレイはゲームプレイ用のモーションデータにのみ依存する。
- ゲームプレイ用のモーションは、ゲームプレイで使用する。
- アニメーション用のモーションは、ゲームプレイでは使用しない。
- ゲームプレイ用のモーションは、ゲームプレイに使う部位のデータだけを抽出。
つまり(A)(B)の中間のような解決策です。これは、最初に述べた2D時代の考え方に近いともいえるでしょう。今回の場合だと、ゲームプレイ用のモーションは頭の部分だけでよいです。頭の位置は、ルートからの相対座標として保存します。ゲームによっては、頭・腰・手先・足先のように、もうちょっと増えるでしょう。
アニメーションに使うモーションデータを変更したら、結局それにあわせてゲームプレイに使うモーションデータに合わせないといけないので、(A)と同じで意味がないように見えます。
しかし、ゲームプレイに使用するモーションの計算時間は、非常に短くなるため、(B)にあった
(B)のメリット4 : 早回しができる
(B)のメリット5 : 低スペックマシンへの移植がしやすくなる
といったメリットを少し持っています。
また、ゲームプレイ用のモーションに、アニメーション用のモーションを合わせるようなモーション制御をすれば、ゲームプレイで使うモーションデータとアニメーションに使うモーションデータを、完全に一致させる必要はありません。しかも、それらのデータは似ているはずなので、制御も(B)に比べたら難しくありません。つまり、ある程度なら、ゲームプレイに影響なくアニメーションも変更可能になるので、
(B)のメリット2 : モーションデザイナー・ゲームデザイナーともに、時間を有効に使える
というメリットも少しでてきます。
また、ゲームによっては、
(C)のメリット1 : ゲームプレイに使うモーションデータを、ゲームデザイナーによって編集させ、ゲームを改善させることができる
といったメリットもあります。例えば、格闘ゲームなら、パンチする位置を少し前にして、ゲームバランスがどうなるか試すといったかんじです。アニメーション用のデータにくらべデータは少なく単純で編集はしやすいし、そのためのツールを作ることも簡単でしょう。この場合、ゲームプレイのデータ変更が大きすぎると、アニメーションがおかしくなる可能性がありますが、ゲームが改善しているのであれば、ゲームプレイのモーションデータにあわせて、アニメーションを作り直して同期させるということも可能でしょう。
4 どの実装を選ぶべきか？
今まで述べてきたメリット・デメリットの重みは、製作するゲームの内容、ゲームの製作期間、メンバーの人数や能力によって全然違ってくると思います。
- 小さいゲームや個人製作のゲームであれば、(A)で十分。(B2.1)のような手抜きも有効。
- 長期のプロジェクト（続編など含む）であればあるほど、(C)が有利。
- モーションデザイナーが多ければ優秀であれば、(A)が有利。
- プログラマーがモーション制御が得意なら、(C)が有利
ゲーム内容で考えると、RPG等、移動が主体で、他のキャラや物体とのインタラクションが少ない場合は、(A)で良いと思います。格闘ゲームやスポーツゲームのように、物体とのインタラクションが多く、しかも(B)のような実装も難しい場合は、(C)を選ぶのが良いと思います。
また、(B)→(C)→(A)への変更は比較的簡単ですが、(A)→(C)→(B)の変更は難しい場合が多いです。こういった点も考慮にいれましょう。
5 関連トピック
5.1 ゲームプレイのプロトタイピング
ここでは、ゲームプレイのプロトタイピング＝「単純にゲーム部分が面白いかどうか試すために、ゲームの簡易版をつくること」とします。
ゲーム開発の序盤ですので、そもそもモーションデザイナーがチームにいないということすらありえます。ここで、モーションなしで面白いゲームを作れたとします。
設計としては、既に(B)のモーションに依存しないゲームができているので、良いことではあるのですが、落とし穴もあります。あとでモーションを入れることを全く考慮せずにゲームを作った場合、
「プロトタイプでは面白かったのに、プロダクションに入り、モーションが入ったら面白くなくなった。」
というケースです。極端な話、一番最初の大砲の例で、
「モーションなしで、待ち時間0秒で、弾がバンバンうてて、気持ちいい！」
という実装にしたら、モーションを入れることができず、だからといって待ち時間を変えてモーションを入れたら、プロトタイプのときとゲームが変わってしまいます。プロトタイプとはいえども、モーション再生用の、現実的な待ち時間は考慮しましょう。
5.2 モーションを検索して動くAI
ゲームによっては、
「現在使用できるモーションを検索し、その中でベストなモーションを使用する」
ということをやりたくなる場合もあります。例えば、野球ゲームでフライを取ろうするとき、「ジャンピングキャッチ」「スライディングキャッチ」等のモーションの中から、タイミングよくフライが取れそうなものを検索する。検索結果によりAIの行動も決める。といった実装もできます。これが、人間の知能により近い考え方なのか、リアルな動きになるのか、ゲームとして面白くなるのか、これから議論されていくところです。
ただし、そういった議論以前に、この実装は、強くゲームプレイがモーションに依存しているということに注意してください。これで(A)のような実装をすると、モーションを検索するだけで莫大な時間がかかったりということもあります。最悪でも(C)のような形にするか、高速な検索方法を考える必要があるでしょう。
5.3 どのスレッドでモーションの計算を行うか
(A)であれば、ゲームスレッド側でモーションの計算をします。
(B)であれば、レンダリングスレッド側でモーションの計算をさせることもできますが、処理時間が足りなければゲームスレッド側で計算させるということも可能です。
(C)であれば、両方から呼び出すということがありえます。
XBOX360やPS3では、モーション計算用のスレッドを独立させるというのも有力な選択肢になります。逆にゲームスレッドとレンダリングスレッドが分けられないようなマシンもあるかとは思います。
ということで、どこでモーションの計算を行うかというのは、思ったよりも選択肢があります。モーションエンジンの部分は独立させて、柔軟に対応できるようにはしておきましょう。
6. まとめ
ゲームプレイとモーションの依存関係は、ゲームバランスの調整やデバッグ期間など、ゲームの品質に直接影響してくることがあるので、事前によく考えましょう。
また、モーション制御の技術は、「アニメーションの品質を改善する」「少ないアニメーション数で、多くのアニメーションをみせる」といった、グラフィック的な改善のためだけはなく、ゲームプレイとモーションの依存を減らすためにも使われます。制御技術を生かしましょう。
2011年 なぞなぞ
今年Twitter等で出題したなぞなぞをまとめました。誰得？
- 仙台に住んでいる２人の学生が、東京に行きました。１人は電車で、１人は飛行機で東京に行きました。さて、就職活動中の学生はどちらでしょう？
- 昔は浮気ばかりしていて、今はデスクワークばかりでちょっと疲れ気味の人が住んでいる都市はどこじゃ？
- 紙が大好きな都道府県はどこでしょう？
- カレーが大好きな人がいる国はどこでしょう？
- ある会社に行ったら、皆でじゃんけんをすることになりました。チョキを出したら、チョキは自分1人だけで、あとは皆グーで負けてしまいました。さて、この会社はどこでしょう
- 買い物が好きな動物は？
- パリの2人が好きな相撲の技はなんでしょう？
- 主人公が、なぜか今日はすっかり疲れきっています。さて、何をしていたからでしょう？
- 大火事になった家の中から、魚がでてきました。なんの魚でしょう？
- カビはカビでも、さわるとあっついカビはなーんだ？
- 鹿児島県の人と宮城県の人が、拳法で戦いました。どちらが勝ったでしょう？
- 動物医の免許も持ってない歯医者が、診察できる動物は（人間以外で）？
- 魚が子供をうみました。その子供のサッカーセンスは抜群でした！さて何の魚でしょう？
- 三国志なぞなぞ。武将たちが、野球をはじめました。一人だけ、快音を放っている打者がいます。誰でしょう？
さて、あなたの称号は？
- 14問正解 なぞなぞターゲット
- 12問〜13問正解 なぞなぞレッド
- 9問〜11問正解 なぞなぞイエロー
- 6問〜 8問正解 なぞなぞブルー
- 3問〜 5問正解 なぞなぞグリーン
- 1問〜 2問正解 なぞなぞグレー
答え 1 電車（りくルート） 2 コルカタ（こる肩。昔はカルかった）3 宮城（み山羊） 4 ルーマニア（カレールーのマニア）5 google（グー、グル） 6 牛(cow) 7 つっぱり 8 プログラマー（主人公が疲労困憊していた→ヒーロー、コンパイ（る））9 鯛（大火→鯛か…） 10 直火 11 鹿児島県（鹿児島県のほうが、アタタ（か）勝った） 12 しか 13 にしん（カズの子）14 かきん
