2015年 競技プログラミングの目標
評価
目標:2015年は100点以上
200~ | 偉大すぎるので、誰かが奢ってくれるはず |
150~199 | PERFECT |
120~149 | GREAT |
100~119 | GOOD |
60~99 | 進歩なし |
30~59 | 怠惰・堕落(FUJIYAMAに乗る) |
0~29 | 人としてダメ(FUJIYAMAに乗る) |
(なお、2014年は60点でした)
得点表
SRMに56.6%以上参加*1 | 20点 |
SRMに56.6%以上参加したうえでRating1800以上 | 20点 |
TCO15 SRM Round 3 | 20点 |
マラソンマッチ レッドコーダー | 80点 |
TCO15 マラソン予選10位以内 1回ごとに | 20点 |
TCO15 マラソンワールドファイナル出場 | 300点 |
Google Code Jam Round 3 | 10点 |
プロコンTシャツゲット1枚ごとに | 5点 |
プロコン賞金10万円ごとに | 10点 |
プロコンでオンサイト決勝出場 | 50点 |
ニコ生放送200枠分(=100時間) | 10点 |
海外でプロコンオフ会をやる | 10点 |
Codeforcesで栗原市ランキングいり | 10点 |
*1:2015/8/2 SRM30回参加にしてましたが、当初予定されていた月4回SRMでなくなってしまったので、割合に変えます。30回/53回(SRM48回+TCO5回)=56.6%
ランダムフォレストのつくりかた(C++の実装例つき)
この記事は24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。
ランダムフォレストのつかいかた - じじいのプログラミング
ランダムフォレストは、機械学習の中でも、確率統計の知識がほぼ無しで実装できる簡単なアルゴリズムで、しかも性能もなかなかのものです。TopCoder機械学習マッチのいくつかは、コードを提出してTopCoderサーバで実行するルールなので、実装しやすいランダムフォレストは有力な選択肢です。実際にランダムフォレストが1位をとったコンテストもかなりあります。
決定木の作り方さえ理解すれば、ランダムフォレストは実装できたも同然ですので、この記事では、決定木を作る部分をメインに取り上げます。
- アドバイスをいただけると、とてもうれしいです。間違いのご指摘は大歓迎です。
- 実装は、TopCoderの他の競技者(PsyhoさんやJacoCronjeさん)のをベースに作ったものです。
- ランダムフォレストもバリエーションがあり、実装もいろいろあるので、注意してください。
- ランダムフォレストの概要を知るには、以下の記事がとても良いと思います。ぜひ事前に目を通してもらえればと思います。
C++の実装例
とにかくコードを見れば分かる人のために最初に載せておきます。
- 回帰(regression, 予想したい変数(目的変数)yが実数のとき)
- ランダムフォレスト回帰の実装例 https://ideone.com/BmvLEq
- 分類(classification, 予想したい変数yが正整数や列挙型のとき)
- ランダムフォレスト分類のジニ係数を使った実装例 http://ideone.com/1einvv
- (注:こちらは実践でまだ使ってないので、間違いがあるかもしれません。あったらぜひ教えてください)
- ランダムフォレスト分類のジニ係数を使った実装例 http://ideone.com/1einvv
出力を見れば、木が増えるほど、誤差が少なくなっていくのが分かると思います。
問題と方針
ランダムフォレストで、分類も回帰もできますが、ここでは、ランダムフォレストで分類する問題を例として挙げます。
ある競技で、レートと年齢に応じて「プロ」「趣味」と呼ばれることがあるとしましょう。すでに8人分のデータがあります。このとき、年齢35歳・レート1500の人(白丸の部分)は、「プロ」「趣味」どちらでしょうか?
他の人のデータを見る限り、近い年齢とレートの人が「趣味」なので、おそらくこの人も「趣味」ではないかと予測できそうです。実際に「プロ」の人が多い「プロ」の領域と、「趣味」の人が多い「趣味」の領域を分ければ良く、良さげな領域の分け方を決める良いアルゴリズムがあれば、予測できます。この領域分けに決定木を使います。
決定木をつくる
グラフを左に、決定木の両方を示しながら説明します。
- グラフの点が、1つのデータに相当します。
- グラフの領域が、決定木のノードに相当します。
- グラフの太いオレンジの仕切り線が、決定木の条件(x0<2500など)に相当します。
- ノード内に書かれている番号は、グラフの領域に含まれている点番号に相当します。
まずルートノードを作ります。全領域に全点が含まれているので、0,1,2,3,4,5,6,7となっています。
(なお、ランダムフォレストでは、通常は重複を許しランダムに選びます(例:5,1,1,3,7,2,5,0)。また全部の点を使わず2/3程度の点だけを使う場合も多いです。ただ、ここでは決定木を分かりやすく説明したいのでバラで全部を選びました。)
次に分割する線を決めます。分割する軸(x0,x1)と分割する場所(0,1,2,3,4,5,6,7)の候補は、オレンジの線になります。この中でベストな分け方を選びます。ベストな分け方については、次の章で説明します。なお、ランダムフォレストでは、全部の候補を試すと遅いので、この中から、いくつかだけを試します。
ベストな分け方がx1<2500と決まったとしましょう。まず、領域を分けます。2つの領域に分かれるので、子ノードを2つ作ります。左の子ノードにx1<2500を満たす点を、右の子ノードにx1<2500を満たさない点を入れます。
次は子ノードを見ていきます(探索順は幅優先でも深さ優先でもどちらでも良いです)。対象の領域はx1<2500を満たす、グラフの下の部分。今回は分割する場所の候補は(0,2,5)だけになります。
ベストな分け方が決まったので、ノードを分けます。
もう、後は繰り返しです。次のノードに行きます。x1≧2500の領域です。
ベストな分け方を決めます。
もし、領域内の点が全て趣味(青)か全てプロ(赤)になったら、もう領域を分割しても無意味なので、終了です。このノードは葉となります。なお、ランダムフォレストでは、領域分割を打ち切る条件として以下のようなものも使う場合があります。
- ノード内の点の数が一定以下になった
- ノードの深さが一定以上深くなった
次のノードに行きます。まだ、ここは青と赤の両方あるので、分けます。
ベストな分け方を決めます
すべてのノードが葉になったので終了です。
決定木ができたので、もう予測するのは簡単です。年齢35歳・レート1500の人がどの領域に属するかは、決定木のルートから条件をたどっていけば良いだけです。簡単ですね。
ベストな分け方はどうやって決めるのか?
公式については、最初に挙げた資料を参考にすると良いと思いますので、具体的な計算例だけ書きます。
分類
上の例であげた「プロ」「趣味」のように、yが列挙型とか0,1,2...といった値しかとらない場合は分類(classification)と呼びます。
分類の場合は、ジニ係数を使う方法とエントロピーを使う方法が知られています。以下の図を見てもらえれば計算方法は分かると思います。この値が最小となる分け方を選びます。データ個数による重みづけの部分(*10/15, *5/15の部分)は忘れないようにしてください。左側の点がすべて同種(yが同じ値)、右側の点もすべて同種であれば、ジニ係数もエントロピーもどちらも0になります。
回帰
yの値が実数を取るときは、回帰と呼びます(regression)。
回帰の場合には、左側・右側でそれぞれ平均をとり、それぞれ平均との差の2乗の総和を取ればよいです。重みづけは必要ありません。この値が最小となる分け方を選びます。データ個数による重みづけは必要ありません。左側の点のyが全て同じ、右側の点のyが全て同じときは、0になります。
実践での応用
ただ、これらの分け方は絶対なやり方というわけではありません。例えば、こういう応用があります。
- 多クラス分類の性能が悪い時に、2クラス分類に落とす。例えば、4クラスa,b,c,dに分類するときに、「クラスaとクラスa以外(クラスb,c,d)」「クラスbとクラスb以外」「クラスcとクラスc以外」「クラスdとクラスd以外」と、クラスの数4つのランダムフォレストをつくって、評価する。
- 回帰の平均との2乗差の方法を、分類で使う。実際のところ、2クラス分類であれば、回帰のコードを分類で使っても、それなりに良い性能がでることも。
- ジニ係数やエントロピーなどに、クラスごとに重みづけの係数をかける。TopCoderの場合、問題によっては、クラスxをクラスyと間違えたときと、クラスyをクラスxと間違えたときでは、ペナルティスコアが異なることがあります。平たくいえば、許される間違いと、許しがたい間違いがあるということです。こういう場合、分け方の評価関数に重みづけをすることで、良い結果が出せる場合があります。
決定木をたくさんつくって、ランダムフォレストにする。
あとは、ランダムフォレストにするだけです。といっても、単に多くの決定木をつくるだけです。もちろん、決定木をつくる際にランダムな要素があるので、決定木は同じにはなりません。全ての決定木で値を予想してみて、分類のときは多数決で、回帰のときは平均をとるだけです。本当にそれだけなので、実装を見た方が早いと思います。
みなさんも実装したら、ぜひ教えてください。楽しいランダムフォレストライフを!
ランダムフォレストのつかいかた
この記事はCompetitive Programming Advent Calendar 2014 - PARTAKE24日目の記事です。関連記事に実装編もあります。
ランダムフォレストのつくりかた(C++の実装例つき) - じじいのプログラミング
今年は、TopCoderの機械学習マッチに積極的に参加して、経験もいろいろ詰めたので、そのノウハウを公開しようと思います。
- 自分のやり方は我流なので、アドバイスをいただけると、とてもうれしいです。
- この記事にはランダムフォレストの説明はありません。ネット上に良い記事が多くあります。「はじめてでもわかる RandomForest 入門-集団学習による分類・予測 -」 -第7回データマイニング+WEB勉強会@東京の記事は読みやすいと思いました。
- この中のコツのいくつかは、ランダムフォレストに限らず使えると思います。
- 実装はないので、RやPythonパッケージ等のツールを使う方にも使えると思います。実装したい方は、上記の記事をみてください。
まずはデータを眺める。
ビジュアライズしてデータを眺めるのが、まず第一歩です。「データに不正値が混ざっていないか」「人間が見ればすぐ分かるような法則はないか」などをチェックします。ExcelでもRでもいいので、見ましょう。極端な話ですが、TopCoderの過去の機械学習マッチ中で、答えが必ず「ある実数*整数倍」になるデータというのもありました。こういった特別な法則を見逃すと、大きく不利になります。
説明変数を、自己判断で削らない。
これはありがちな失敗です。機械学習では、説明変数x0,x1,x2...から目的変数yを予想しますが、たいていの問題では、説明変数の内容が書かれあります。ただ、問題文で内容説明を読み、「あ、これは今回の問題に関係ないな。」と思って、削るのはやめましょう。自己判断で追加するのは良いですが、削るのはダメです。
例えば、TopCoderのOctaveClassifier("http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15879&pm=13017")という問題ではsetIDという変数を、説明変数に残したかどうかが、上位に入れるかどうかの鍵になりました。本体データ分析の依頼者は意味なくつけた値だったはずなのですが、実際にデータを眺めてみると以下のように、近くのsetIDのものが、なんとなく似たような配置になっているのが分かると思います。
説明変数が多すぎて、削りたくなることはあるかと思います。ランダムフォレストの場合は、説明変数の寄与度が求められるので、寄与度が低い変数を取り除くというのはありです(ただ、経験上、あまり大きな効果はないです)。もしくは次元削減のアルゴリズムで説明変数を削りましょう。
説明変数を追加する。
問題で与えられたデータをそのまま説明変数にツッコむだけだと、それは他の人もやっているので、上位10%とかに入るのは難しいと思います。すでにあるデータから、新たな説明変数を求め追加することで、性能をぐっとあげることができます。いいかえれば、説明変数x0,x1,x2しかないような問題でも、x3,x4…を自分で定義して追加すると、性能が上がる場合があるということです。
(1)同種のデータとのかかわりを表す変数を追加する
これは意外と見落としがちです。どうしても1つ1つ別のデータとして見がちなのですが、他のデータとの関係は重要です。例えば、以下の図で、同じ色の点が同種のデータだったとします。黒淵の緑の点が、他の緑点を含む矩形領域のどの辺にあるかというのは、明らかに特徴の1つといえます。他にも、重心・回帰直線・共分散行列など、集合から求まる統計情報はいろいろとあります。さらに応用して、重心からの距離とか、密度とか、同じラベル内でxの値が何番目に大きいとか、そういった変数を追加するのも有効な場合はあります。
また、同種のデータであるという情報が、データの説明変数に含まれていない場合も、同種とみなせる場合もあります。以下の例では、「右斜め上に伸びるデータの集合が緑ラベルになる」という法則がありそうです。こういう場合は、k-meansのようなクラスタリングアルゴリズムで同種とみなしたり、密度が高い領域をUnionFindでつないで、それを同種のデータをみなせば取り扱えます。
(2)不正値の数を追加する
データがおかしいということ自体が特徴ともいえるので、不正値の数をカウントして、説明変数として追加したほうが良いです。
(3)x1-x2, x1+x2等を追加する
ランダムフォレストは、軸に平行な分け方しかできないので、x1-x2といった差分を追加するのは有効なことがあります。でかい決定木1本だけを作るというわけではないので、足さなかったからと言って、そこまで悪い結果になるってことはないのですが、そこそこ効果があるときはあります。
(4)他のジャンルの機械学習で使われる特徴量を追加する
文字列が出てきたらそのまま列挙型にせずいったん単語に分けて単語別にIDを付けたりとか、化学式に対してn-gramを使ってみたりとか、いろいろ工夫できます。他のジャンルの機械学習で使われる特徴量もいろいろと追加できないか考えましょう。
木は少しずつ増やす
ランダムフォレストで木を増やすことで結果が悪くなるということは、まずありません。つまり、計算時間が余っているなら、どんどん木を増やしていったほうが良いです。特にTopCoderルールの場合は、計算時間制限があるので。最初に木を作る本数を多めで決め打ちしてしまうと、時間ギリギリまで木を増やすということはできません。10本とか100本とか少ない本数を足していき、その都度時間を計測して、時間ギリギリまで追加する形がよいです。自前でコードを書いた場合は簡単にできますし、R言語でもforest <- grow(forest, 100)のように書いて繰り返し呼べば少しずつ増やすことができます。
また、TopCoderルールの場合は、メモリ制限もあるので、その制限にひっかからないようにするためにも、木を少しずつ増やす手法は有効です。
データの一部を過学習チェック用にとっておく。
正直ランダムフォレストでは、あまり重要ではありませんが、それでもデータが少ない場合、調整すべき変数が多い機械学習手法の場合は、やはりやったほうが良いと思います。
自分の場合は、以下のような手順で行っています。
- データを90%(クロスバリデーション用)と10%(過学習対策用)にわける
- クロスバリデーション。この90%のデータをさらに2つに分けて、片方を訓練データ、片方をテストデータとする。これで、説明変数を増やしたり、定数の調整をしたりして、良いスコアがでるようにする。これをデータの分け方を変えて、何度も繰り返す。
- 満足がいったら、残り10%の過学習対策用をテストデータとして使う。これで結果がぐっと悪くなったら、過学習が疑われるので(2)からやり直し。(ただ、(2)(3)を何度も繰り返すと、データを分けた意味がないので、注意)
ちなみに、TopCoderの通常のマラソンマッチでも、最終調整時の最適化(=最後にプログラム上に残った定数を調整することでスコアを稼ぐ)のときも、調整時に使わなかったテストケースを使って実行し、同じぐらいの得点がとれるか確認します。これでガクンと点数が下がったら、過学習を疑います。
/////
以上です。みなさんも、ぜひランダムフォレストを使ってみてください。
明日12/25最終日は、Advent Calendar主催者の tanzakuさん(毎年ありがとうございます)と、いつも衝撃の記事で楽しませてくれるli_sakuさんです。お楽しみに!
TopCoderマラソンマッチのはじめかた
注意:TopCoderマラソンマッチはデザインが大きく変わってしまいました。これから始める方はphocomさんの以下の記事をお勧めします!
qiita.com
TopCoderマラソンマッチは、1-2週間ぐらいの長期間で、正解を出すのではなく、より良い性能のプログラムを書き、高スコアを出すことを競うコンテストです。短時間マッチのSRM(シングルラウンドマッチ)とは違った魅力があります。
ただ、SRMと比べると、参加方法がわかりにくいです。公式の解説はあるのですが、マラソンマッチをやったことがない方向けに、おおまかな参加方法を書きました。
まずTopCoder自体に参加したことのない方は、TopCoderへの登録が必要です。http://www.topcoder.com/の右上の"sign up"から登録を。うまくいかなければTwitterの@nico_shindanninまでご連絡ください。
また、この記事では、マラソンマッチの攻略法については述べません。特別なアルゴリズムの知識はなくても参加できます。ただ、TCO World Finalsに進出した方々による、とても良い記事がありますので、知りたい方はこれらを参考にしてください。
2012-05-02 - TopCoderの学習のお時間 - TopCoder部 by tomerunさん
マラソンマッチの取り組み方 – システム工房コルン by colunさん
マラソンマッチ トップページ
こちらの古い方(http://community.topcoder.com/longcontest/)のトップページを使って説明します。
*1
右側には、現在開催されているコンテストが表示されます。
- discuss : フォーラムです。問題の変更・公式テスターのバグ修正など、とても重要な連絡がされることがあるので、マメにチェックしてください。
- standings : 現在までの仮順位が表示されます。
- Problem : 問題文です。
- Register/Submit : 自分の解答コードを提出します。
- Start Time, End Time : 時間が表示されます。日本標準時ではなく、東部標準時で表示されるので、注意してください。
左側にも、いくつか機能があります。現在無くなっているので、リンクを追加しました。
- Match Archive : 過去のマラソンマッチの結果があります。他の人の提出コードも見れます。
- Practice : 練習ページです。過去のマラソンマッチの問題で練習できます。Practice内でも、standingsで順位をみたり、submitで提出できます。自分の好きなときにできて締切もないので、活用しましょう。
- Queue Status : 現在、結果を待っている人がいるかが分かります。
コンテストの流れ
開催中のコンテストに参加する場合の流れです。Practiceで練習するときには関係ありません。
ルール
- 個人戦です。他の人と相談してはいけません。
- コードは自分で書く必要があります。ただし、問題によっては、特殊ルールで、外部ライブラリ使用可能だったり、他人のコードが使用可能ということもあるので、問題を良く読みましょう。
- コンテスト期間中は、ネタバレ禁止です。コードをさらすのはもちろん、観察・考察をさらす(「こうやると○○点取れそうとか」「このアルゴリズムを試してみよう」)のも禁止です。
- 残念ながら、賞金がもらえるマッチは、年齢制限(18歳以上)があるときが多いです。
スケジュール
スケジュールは以下のようなかんじです。
開始 → コード提出期間(3日~1ヶ月)→ コード提出終了・採点(1日~5日)→ 採点終了・順位確定
- 突然始まるマッチもかなり多いです。TopCoderからのお知らせメールなどはマメにチェックしてください。
- マラソンマッチの期間は1週間が一番多いですが、3日~1ヶ月ぐらいまでと幅広いです。
- コード提出期間内には、standingsのリンクで、仮順位が分かります。スコアを上げて、上の順位を目指しましょう。
- コード提出期間本採点終了後に、順位が確定します。結果に応じてレーティングが上下したり、上位に入れば賞金がもらえたりします。
問題文
多くの問題では、問題文のページと公式テスターのページと、2つのページがあります。どちらも読む必要があります。公式テスターのページへのリンクは、以下のように問題文のページにまぎれてあるので、絶対に見逃さないようにしましょう。
SRMと違って、英語を読む時間はじっくりあるので、ちゃんと読みましょう。特にメモリ制約・制限時間は毎回異なりますし、間違うと0点になるので、必ずチェックしましょう。あと、どうしても問題の意味が分からないなら、以下で述べる公式テスターを先に実行してみるのも良いかもしれません。
スコアの算出方法も書いてあります。他の参加者との相対スコアか、絶対スコアかなど、細かいことまで書いてあります。スコアで順位が決まるので、とても大事です。必ずチェックしてください。
コーディングとオフライン実行環境
問題の解答のコーディングだけではなく、問題の解答をオフライン実行する環境が必要になってきます。一番よくある形は以下のとおりですが、公式テスター/ビジュアライザが無い場合もあります。その場合は問題文ページを良く読んでください。
公式テスターのページは、[A][B][C]を取り扱っています。以下のようなページになっています。
また、[B]と[C]の各言語ごとの例をダウンロードとすると、コードは以下のようになっています。
[A] 公式テスター(ビジュアライザ)
- 公式テスターを使うと、自分のパソコンで、オフラインで自分の解答の得点を確認したり、ビジュアルつきで実行結果が見れます。
- 公式テスターはほぼ常にJavaです。Java runtimeかSDKを予めダウンロードしておいてください。
- まずは公式テスターのページ上部 Executable JAR of the visualizer からダウンロードしてきましょう。
- 実行は、コマンドラインから行います。公式テスターのページの下の方に説明があります。
- 実行する場合は、[B][C]のコードを書いてコンパイルをして、実行ファイルを作る必要があります。その実行ファイルのパスを、コマンドラインの引数として渡します("..\..\Release\marathon_main.exe"の部分)
java -jar Tester.jar -exec "..\..\Release\marathon_main.exe"
- 公式テスターのソースコードもダウンロードできます。もし改良したい場合は、これを書き換え、javacでコンパイルしましょう。
[B] main
- [A]と標準入出力で、データのやりとりをします。
- [B]と[C]はJava,C++,C#,VB,Pythonのどれか好きなものを使えますが、同じ言語を使ってください。
- 上記の各言語ごとの例を丸ごと使えば、問題ないでしょう。書き換えることはないと思います。
難しくはないのですが、1つでも入出力を間違えると、全く動作しないので、公式テスターのページをよく読んで、正確に書いてください。Javaから実行されるコードになるので、間違えたときエラーメッセージもJavaで出るので、どこで間違えたのかデバッグがしづらく、ハマりやすいです。
- C#,Java等他の言語を使用する場合の、実例は http://apps.topcoder.com/forums/?module=Thread&threadID=670892&start=0 に書いてあります。
[C] クラス
- 上記の各言語ごとの例から、はじめましょう。
- Topcoder SRMと同じように、ここに自分の解答コードを書きます。
- よくあるハマる例として、[C]で標準入出力を使ってはいけません。[B]が動かなくなります。つい、デバッグの際にprintfとか書きたくなりますがダメです。何かログを表示させたいなら、標準エラー出力か、ファイル出力を使いましょう。
- また、次に述べる"Submit"で提出するときは、すべてのログ出力コードは消した方がよいです。プログラムの実行時間が遅くなるだけなので。
提出
Submitボタンを押すと、以下の画面に移動します。
まず、画面右上で、言語を選択しましょう。そして、[C]のクラスのみを貼り付けて提出します。[B]は入れてはいけません。(なお、TopCoderでは、提出時に、複数ファイルのコードを提出するということはできません。よって1つのテキストにまとめて提出する必要があります。最大の難点です…。)
提出には"Test Example"と"Submit"の2種類あります。
- Test Example
- 実行するケース数は少ないです。通常のマラソンマッチだと10ケース程度です。
- 1ケースごとの得点・実行時間・ログ出力が見れます。(Standingsページで、自分のExample提出回数のところをクリックします)
- Standingsのスコアには反映されません。
- 1度"Test Example"で提出したら、次の"Test Example"での提出までは15分待たないといけません。
- Submit
- 実行するケース数はやや多めです。通常のマラソンマッチだと100ケース程度です。
- 100ケースの平均得点が見れます。
- Standingsのスコアに反映されます。仮順位も変動します。
- 1度"Submit"で提出したら、次の"Submit"での提出までは2時間待たないといけません。
通常は、まず"Test Example"で提出してみて、オフラインの結果と同じになるかをチェックします。もし良さげであれば"Submit"で同じコードを提出、何かおかしければ修正して"Test Example"でもう1度提出、というふうにすると思います。
提出が受理され、実行が終わると、TopCoderからメールが届きます。1度提出すると、15分間or2時間提出できません。最終的な順位は、一番最後に"Submit"で提出したコード決まります。例えば、残り時間2時間以内で、誤って0点のコードを提出したら、もう再提出はできませんので、0点確定です。締切ギリギリの提出は避けることをお勧めします。
マラソンマッチが終了したら
- メインメニュー左側のMatch Archiveから、最終順位を見ることができます。また、他の参加者のコードは、右のほうにあるSubmissionの数字をクリックすると、過去の提出も含め、全て見ることができます。復習にぜひ活用してください。
- discussのリンクから行けるフォーラムに行きましょう。
- "Post your approach"というスレッドが立っていることがあります。ここで、他の人の解法を知ることができます。非常に勉強になるので、ぜひ見に行ってください。また、自分の解法を書くのも良いと思います。
- 賞金つきマッチでは、たまに「追加マッチ」の情報が載っていることがあります。チェックしましょう。
- 賞金つきマッチで入賞したら、賞金を受け取る手続きをして、もらいましょう。しないと、消えるのでご注意ください。
以上です。さぁ、みんなで楽しいマラソンマッチライフを!
*1:もう1つの新しいトップページ(http://www.topcoder.com/challenges/data/active/?pageIndex=1) は工事中で、結局古い方へリンクがつながってたり、新しい方から提出できないなどの問題も起きているので、古い方の画面を使って説明したいと思います。
PS4「信長の野望 創造」の感想
老後に、戦国シミュレーションゲームを作ってみたいので、そのときに向けての感想。
- 信長の野望シリーズは、全国版・戦国群雄伝・武将風雲録・天翔記・蒼天録・天下創世・革新はかなりプレイしました。他のコーエーのシミュレーションゲームもかなりやっています。
- 発売してからだいぶ経っているので、アップデートでいろいろ改善されている状態での感想です。
- プレイ時間は全部で150~200時間ぐらいで、エンディングまで行ったのは5回です。
- 1551年「家督相続」、中級、宇都宮家で、惣無事令
- 1582年「夢幻の如く」、上級、筒井家で、従属のまま惣無事令
- 1570年「信長包囲網」、上級、葛西家で、天下統一
- 1560年「桶狭間の戦い」、上級、今川家で、惣無事令
- 1584年「独眼竜、起つ」、上級、能島村上家で、天下統一
その他設定は、史実・戦国伝あり・姫なしです。
○が多いほど良く、×が多いほど悪い。
内政
○○○ | (1) 政策システム(「創造」も含めて)が秀逸。 |
○○ | (2) 国人衆がいろいろな役立ち要素があり、面白い。 |
○ | (3) 施設もバラエティにとみ、微妙に役立つ。 |
過去作品においても、内政はめんどくさがられやすく、だからといって単純にしすぎると、奥深さはなくなり、また、ゲーム後半に米・金が余り、無意味になったりしやすく、作るのが非常に難しいところ。しかし、今回は政策コマンドの出来が素晴らしい。
(1)政策コマンドでは高い金額を使って、大きなメリットとそれなりのデメリットがある効果を受けることができる。例えば「刀狩令」だったら、メリットは「実施月数に応じて次回の収穫が増加」「民忠低下時に一揆が発生しにくくなる」、デメリットは「支配下の国人衆の最大兵数が大きく減少する」といったかんじ。これにより、
- パラメータの「創造性」により使える政策が異なり、大名ごとの個性がでている。また、大名固有の政策もあり、そういった大名の個性が大きくでている。
- 「甲州法度次第」「一領具足」など、政策は史実を元にしているので、歴史好きの人も大満足。
- 政策コマンドの実行がかなり高コストで、メリット・デメリットも大きいので、何を使うかで大きくゲーム展開が変わってて面白い。
- ある時点で政策を発動した敵大名が急成長してくることがあり、「自分が最大勢力なので、あとはのんびりやろうが、天下統一できるだろう」といった、中だるみもかなり減っている。
(2)国人衆の部分もかなり考えられている。国人衆の能力自体もバラエティにとみ、それ自体も面白い。また「取込」という要素があり、
- 国人衆を取り込まないと、兵士として、戦闘に使える。国人衆ごとの特殊能力(鉄砲献上・どこからでも戦闘に参戦・能力上昇速度アップ)なども大きい。
- 国人衆を取り込むと、上記のメリットはなくなってしまうものの、人口が大きく増える。
長期的にみると、はやめに取り込んだほうが有利、ただメリットがでてくるのはすぐではないので。短期的・長期的なメリットどちらをとるかという選択が生まれてくる。
(3)の通常の施設建設は、過去作のと似ていて真新しさはそんなにないけど、これも悪くない。戦闘がちょっと有利になったり、人口が増えやすくなったり、創造性が変わったりとか、それぞれ地味に後半に効いてくる
外交
○ | (1) 信用システムがややリアル。 |
× | (2) 援軍による停戦同盟が有利すぎる。 |
信用システム自体は良い。「信用」は金をかけても急に増やすことはできず、上げるのには時間がかかる。ゆえに、長期的な視野で、どの大名と同盟を結ぶかというのを考える必要がでてくるので面白い。また、過去に裏切ったりしたりすると、信用に関係なく、絶対に同盟が結べなくなったりするのも良い。
ただ、援軍による停戦については、ゲームバランスがちょっとおかしい気がする。
- 援軍 消費信用40 9か月間敵が攻め込んでこない+援軍がくる+関係が「信頼」になり信用が上がりやすくなる。
- 同盟6か月 消費信用60 6か月間敵が攻め込んでこない。たまに兵糧・軍馬を少しもらえる。
- 同盟12か月 消費信用70 12か月間敵が攻め込んでこない。たまに兵糧・軍馬を少しもらえる。
- 同盟24か月 消費信用80 24か月間敵が攻め込んでこない。たまに兵糧・軍馬を少しもらえる。
なぜか援軍のコストパフォーマンスが同盟よりも高い。同盟6か月よりも長い。これだったら、消費信用70ぐらいでもおかしくはない。調整忘れ・仕様バグというかんじがする…。
「同盟は必ず成功する」「援軍は必ず成功する」確定的にしようという方針はいいのだろうか?自分は確率があるほうが好きなのだけど…。
人事
○○ | (1) 忠誠度のシステムは良い。 |
× | (2) 忠誠度のシステムは良いのに、裏切ったり、能力が減ったりする機会が、ほぼないので、忠誠度自体意味がない。 |
× | (3) 滅亡時に捉えた武将・大名が全て味方になる、しかもほとんどは裏切らないのは、さすがに不自然な気がする。 |
(1)忠誠度は、お金を上げてあげるのではなく、武将との相性や過去の事実(仇敵であるとか、主義とか)で決まる形なので、金さえあれば全員忠誠度満タンなんてことはできない。家宝で忠誠度を上げることもできるけど、そんなにはあがらない。また、忠誠度が低い武将は、出奔するだけでなく、やる気をなくし、大きく能力が下がる。これは史実でもありそうだし、面白いシステム。むしろ三国志でほしい(魏にいった後のジョショとか)。
(2)ただし、出奔も能力低下も、かなりまれ。天下統一までに数人いるかというぐらいなので、システム自体があまり生きてない。もったいない。
(3)あと、滅亡時に全員味方になるのはいいのか。強い武将を全部集めたいユーザーとかは、味方にならないのを極度に嫌う可能性があるので、その要望に応えのかも。ただ、リアリティは減ってる気がする。武田信玄も上杉謙信も織田信長も簡単に部下になるからなぁ…。
軍事(通常)
× | (1) 通常戦闘で工夫できることが、挟撃効果ぐらいで、少ない。 |
○○ | (2) 敵の思考AIが悪くない。 |
会戦以外の戦闘。全体的にバランスは良いけど、戦闘で工夫できる要素が少ないかな。挟撃自体は悪くないけど、敵を簡単に挟撃する方法が、いろいろ存在するので、あまり奥深くならない。
AIは悪くなく、三国志シリーズとか過去の信長に比べるとずっと良いと思う。ちゃんと要所をあらかじめ抑えるような動きをする。敵にわざと攻めさせて、がらがらになった敵の城を落とすって方法は使えるけど、過去作に比べるとそこまで変な動きはしない。ただ、大名行列をつくりやすい気はする。もうちょっと、進路をあらかじめバラして攻めてくればいいのに。
軍事(会戦)
××× | (1) ほぼ自軍の被害なしで、敵軍を倒す、裏ワザっぽい方法が存在する(会戦キャンセル)。 |
×× | (2) 「1次元の線上で戦う」「全滅以外の勝利条件がない」というルールが、シンプルすぎて、面白くするにも限界がある。 |
× | (3) 采配コマンドの種類が少なく、バランスもいまいち。 |
○ | (4) 突撃・鉄砲・足止め系の使い方は、プレイヤーが工夫できる余地がある。 |
会戦は部隊を操作して行う近接戦闘。開発者側の狙いは以下のようなことだったと思われる(記事にも出てます)
A. 会戦はたくさん起こりうるので、シンプルに分かりやすく、短時間で終わるようにしたい。
B. プレイヤーの腕次第では、少ない兵でも、多くの兵に勝てるようにしたい。
まず、このゲーム中最大の問題点が(1)。「会戦中に、会戦をいつもキャンセルできる」こと。以下のようなズルができる…
- 会戦が始まったら、突撃か斉射をする。敵軍が被害を受けてるうちは会戦続行。自軍が被害を受けそうになったら、会戦をキャンセルを繰り返せば、敵軍を被害なしで倒せる。
- 自軍が混乱する等、不利になったら、会戦をキャンセルすれば、混乱が直った状態で一から会戦を仕切り直しできる。
しかも、これは誰でも気づく。少ない兵で多くの兵に勝てる…というかほぼ無敵だけど、それはプレイヤーの腕ではなく、ズルっぽい方法で勝ててしまうのが大問題。
ただ、仮に(1)が直っていたとしても、会戦が面白かったかは微妙。まず(2)、過去の作品だと、本陣をとるとか、全滅以外の勝利条件もあったので、「ふつうに戦う」か「リスクをとって本陣を狙う」かの、読みあう面白さがあった。今回はそれがない。これだけ単純だと、AIプログラマーの仕事も難しい。たぶん最適解な動きを作ることは簡単だけど、そうすると逆転の要素が一切なくなる。逆転させるためには、意図的にかなりバカなAIをつくらなければいけないし、それだと「AIがバカで面白くない」という評価を下すプレイヤーもいるでしょう。
(3) 采配コマンド自体はいろいろあるけど、近接戦闘・騎馬・鉄砲の能力上昇、動けなくする等の組み合わせなので実質そんなにない。(特性のほうはいろいろあるので良い)。また采配コマンドの一部が強すぎ。例えば詭計百出は「敵全部隊が大幅に弱体して、動けなくなる」。例えば三国志大戦だったらとんでもないチート計略になるけど、このゲームだとそのレベルのが会戦開始時に即使えてしまう。
ただ、突撃・鉄砲・足止めについては、うまく組み合わせて、相手の采配ゲームをムダに減らしたり、効率的にダメージを与えたりするといった、組み合わせることの面白さがある。三国志大戦とか見習って、組み合わせたら、面白い采配コマンドをもっと考えてほしかった。
最後に、仮に(1)(2)(3)すべて直ったとしても、今回の会戦の面白さが、購入前のユーザーに伝わったか微妙。過去作「蒼天録」は1次元の線上*3列で戦う形式ですら、単純すぎという評価が見られた(実際やりこめば結構奥が深いけど)。「1次元の線上で戦って何が面白いのか?」と疑問にもつプレイヤーのために、宣伝記事でもゲームの中でも、面白さを早めにアピールする工夫が必要。会戦はゲームの中でも最もアピールできるパート。「見た目は面白くなさそうだけど、やりこめば面白い」では、プレイヤーに手にとってもらえないので…。
会戦については、パッチをあてて
- 会戦は月に1回だけにする、会戦キャンセル直後に通常戦闘が発生するなどのペナルティを設ける。
- 会戦自体に手を入れるのが難しいのであれば、もうあきらめて「会戦ありなし」をゲームの初期設定できるようにして、せめて会戦なしでクリアするやりがいを与えられるようにする。
のが良いと思う。
やりこみ等その他
○ | (1) 戦国伝がかなり多い。 |
○○ | (2) シナリオ・武将・音楽追加も多い。 |
戦国伝(ストーリーモード)は、そんなに手を付けてないけど、歴史にそった条件がいろいろとあるので、面白い。
その他追加データについては、本当に良いところだらけ。過去シリーズの音楽を使えるのは、非常に良い。戦国群雄伝の「時の調べ」が入ってたら、○○○にしてたかも。追加シナリオ等も、サービス期間内なら無料でダウンロードできるのも良い。お金をとらないサービスが多く、どうしたのコーエーって思えるぐらい。
操作性・わかりやすさ・グラフィック
ここは個別に箇条書き。
(1) フォントがPS4,1080Pで文字が小さすぎる問題。アップデートで治って本当に良かった…けど、最初から気づいてほしかった。
(2) チュートリアルシナリオは、話は面白いけど、文章が多すぎ。教える内容も、絞ってよかったかも。援軍とか必要?
(3) 会戦のはじめ方に気づいたのは、1回目のプレイの統一間近だった…。常に表示されるアイコンではないので、存在が分からなかった。使えるタイミング自体もちょっと分かりづらいので、アイコン自体は常に表示で、ONOFFで明暗したほうが良い気がした。
(4) 会戦できる状態である・挟撃状態になってるなどの表示は、全体マップで分かる形にしてほしかった。凸マークになって、ちゃんとピッチりくっついたら会戦ができるというのは分かるのけど、そんな自明ではない。挟撃については、自軍Aと敵軍BがA-B-A-Bになった場合など、こちらも自明ではない。
(4) フリーズが1度ありました。PS4自体は動いてたので、完全にゲームのほうの問題。
(5) ゲーム後半部隊が多いと、処理落ちが発生する。グラフィックより操作性のほうが重要なタイプのゲームなので、処理落ちするぐらいならグラフィックは軽めにしてほしかった(CPUで処理落ちする可能性もありますが、PS3で動いているんだから、まぁたぶんないでしょう。)
(6) 戦闘が動いているのか止まっているのかが、最初はいまいち分からなかった
(7) 反面、ゲーム中のコマンドを初めてやるときに出てくる、ポップアップヒントはとても良かった。
(8) 兵士数・移動時のキャラアイコン良く重なる。ときどき完璧に重なってるときもあった。場所をずらして表示できるケースのほうが多いので、そうしてほしかった。
(9)入城時の兵士数。兵が急に消えるので、どきっとした。よくメッセージをみると「自城に帰還」とかでるのだけど、もうちょっと分かりやすくしてほしかった。
(10) 特定の部隊を、矩形選択でまとめて選択して、1つの城へ移動させる機能がほしかった。
(11) 会戦で、画面外のやつは戦略がつかえないけど、戦闘にでる武将は固定で、全員が基本使えるのに、そうするメリットは全くない気がする。「1度采配コマンドを使ってしまい、今は采配が使えなくなってる武将は表示しない」だったら理解できるんだけど。
マラソンマッチ Asteroid Tracker 惨敗反省メモ
問題
地上にあるレーダーを使って、宇宙からくるアステロイドの情報を効率よく集める。どのレーダーでどのアステロイドを捕捉するかを考える問題。
NASA's Asteroid Tracker - YouTube
結果
仮順位 21位/43位ですが、得点は、ほとんど最下位と変わらない得点で、大敗です…。
反省点1 やる気がでない
今回は時間はふつうにあったはず。締切り1.5日前になってから、やっとやる気がでたけど、手遅れでした。
原因1 問題文がすごく長い
問題文・数式・変数、いずれも多かったです。たぶん過去最長の問題文だったかも…。
対策
- 数式が複雑なのは、色分けしたら分かりやすくなったので、今後はそれで。問題文はプリントアウトすれば書き込みしやすいので、そうしたほうが良かったかも。
原因2 誘惑にまける
参加登録してから、50時間ぐらいはゲームをしてた気がします。やりかけのゲームがあったのが不味かった…。
対策
- 誘惑には勝てないので、ハマってるゲームを狂ったようにやって、早めに終わらせて、そしてから登録する。
- 問題の面白い部分までたどり着けばマラソンマッチのほうが面白くなるので、最初だけでもとにかくがんばる。
原因3 最低限の解答を出す前にはまる
時間0のときのコマンドがうまくいかず、そこからずるずると誤解する方向にいって、4,5時間ハマってしまいました…。
対策
- ハマってしまうリスクは予想しずらいので、やっぱり早めにはじめることで、リスクを減らすしかない…。
反省点2 方針ミス
ギリギリではじめても、多くの場合はそれなりのスコアまではいけるのに、今回は、それすらできませんでした
原因1 スコア関数(数式)の理解ができてなかった
スコア関数が複雑で、スコアがレーダーグループ内のレーダー数の2乗になるになるのを見逃してしまいました。
対策
スコア関数にある全ての変数について、
- この変数の値が大きくなったら、スコアがどうなるか?
- この変数の値が小さくなったら、スコアがどうなるか?
もれなく検討すること。表を書くとよいかも。
原因2 考察がおかしい
1→2→3→4のように、かなり低い得点の方針を詰めていってしまいました…。数式の理解ができてなくても、間違いに気づくチャンスはいくらでもあったはず。
問題点
- 1→2で得点が増えたのをみて、ちゃんと考察するべきでした。得点が増えた可能性として以下の2つがありえるのに、Bの検討をしませんでした。
- A.「照射をバラして、複数の隕石から点が入るようになったから」
- B.「重要な隕石も照射されるようになったから」
- 2の解答でもかなり低い得点なので、詰める前に、他の方針はないか疑うべき。
- 特に3の時点で、点が明らかに伸びてないのをみて、おかしいというのに気付き、1つ戻って考えるべき。
対策
- 考察を丁寧に。得点が増える・増えない理由を、丁寧に考える。
- 思考過程をまとめれば、変なのに気付くの自明なので、メモを必ずとる。
- 点が平均以下のときは、絶対に簡単な解法を見逃している
C++11 forループの速度比較と、コンパイラのループ展開
C++11 forループの速度比較と、コンパイラのループ展開についてテストをしたときの結果です。構造体のメンバを、5で割った余りごとに分けて、頻度を数えるようなソースコードで実験しました(ソースコードは最後にあります)。プロセッサは、Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHzですが、実行結果は、コンパイラ・CPU・メモリ・キャッシュで大きく異ってくると思うので、ざっくりとだけ参考にしてもらえればと思います。
1. ループの方法ごとの速度の比較
Visual Studio 2012は、Release、その他は初期設定のままでコンパイルしました。
g++ 4.8.2は、--std=c++0x -O2 -W -Wall -Wno-sign-compareでコンパイルしました。
方法 | Visual Studio 2012(秒) | g++ 4.8.2(秒) |
(1) 通常のforループ | 2.995 | 3.562 |
(2) 通常のforループとconst参照 | 3.035 | 3.579 |
(3) c++11のrange-based forループ | 3.604 | 3.502 |
(4) for_eachとc++11のラムダ式 | 3.619 | 3.462 |
(5) for_eachと関数オブジェクト | 3.604 | 3.477 |
- Visual Studio 2012で(1)(2)が速いのは、ループ展開が行われているからです。g++ 4.8.2は、(1)から(5)までおおよそ同じ時間です。デフォルトのオプションでは、ループ展開しないようです。
- (4)と(5)は、http://msdn.microsoft.com/ja-jp/library/dd293608.aspx にあるように、C++11のラムダ式は関数オブジェクトを使用したものと同じになります。実際に、Visual Studio 2012でコンパイルすると、DebugでもReleaseでも(4)と(5)は、全く同じアセンブリになりました。
2. コンパイラのループ展開の仕方
(同じコードを使いましたが、ちょっと前に違う状態で実験したので、当時の簡易的な実験の結果として見てもらえれば)
ループ展開とは、コンパイラの高速化の手法です。
for (int i = 0; i < 10000; ++i) { frequency[positions[i].x%SZ(frequency)]++; }
上のようなコードを、下のようなコードに置き換えて、ループ回数を減らします。(動作はかわりません)
for (int i = 0; i < 10000/5; ++i) { frequency[positions[i*5].x%SZ(frequency)]++; frequency[positions[i*5+1].x%SZ(frequency)]++; frequency[positions[i*5+2].x%SZ(frequency)]++; frequency[positions[i*5+3].x%SZ(frequency)]++; frequency[positions[i*5+4].x%SZ(frequency)]++; }
メリット・デメリットについて、詳細はこちらのリンクを参考にしてみてください→ http://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%97%E5%B1%95%E9%96%8B
Visual Studio 2012
- Nを定数にした場合、6以下の約数で最も大きい個数に展開するようです。Nが素数のときや、2でしか割り切れないときは遅くなりました。
N | ループ展開の個数 | 実行時間(秒) |
9996 | 4 | 2.839 |
9997 | 1 | 3.213 |
9998 | 2 | 3.136 |
9999 | 3 | 2.854 |
10000 | 5 | 2.871 |
10001 | 1 | 3.276 |
10002 | 6 | 2.855 |
10003 | 1 | 3.214 |
- Nを変数にした場合(標準入力でNに値を渡した場合)は、ループ展開はされませんでした。
g++ 4.8.2
- Nを定数にした場合、コンパイルオプションに-funroll-loopsを追加すると、ループ展開されます。12個までループされる展開を確認できましたが、8個や12個まで展開されたときは、かえって遅くなりました。
- Nを変数にした場合(標準入力でNに値を渡した場合)は、 -funroll-all-loopsを追加すると、ループ展開されます。この場合、8個にループ展開されましたが、Nが8で割り切れないことを考えて、ループを途中で抜けるジャンプ命令が入ってしまうため、かえって遅くなってしまいます。
ソースコードです。
#include <vector> #include <algorithm> #include <iomanip> #include <iostream> #include <fstream> using namespace std; typedef long long ll; #define SZ(a) ((int)a.size()) #include <sys/time.h> unsigned long long getTime() { struct timeval tv; gettimeofday(&tv, NULL); unsigned long long result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL; return result; } struct POS { int x; int y; }; class FunctorClass { public: explicit FunctorClass(vector <int>& frequency) : m_frequency(frequency) { } void operator()(const POS& pos) const { m_frequency[pos.x%SZ(m_frequency)]++; } private: FunctorClass& operator=(const FunctorClass&); vector <int>& m_frequency; }; int main() { int N = 10000; vector <POS> positions(N); for (int i = 0; i < N; ++i) { positions[i].x = rand(); positions[i].y = rand(); } const int DIVIDE = 5; vector <int> frequency(DIVIDE); const ll start = getTime(); for(int k = 0; k < 100000; ++k) { #if 1 // (1) 通常のforループ for (int i = 0; i < N; ++i) { frequency[positions[i].x%SZ(frequency)]++; } #elif 0 // (2) 通常のforループとconst参照 for (int i = 0; i < N; ++i) { const POS& p = positions[i]; frequency[p.x%SZ(frequency)]++; } #elif 0 // (3) c++11のrange-based forループ for (const POS& p : positions) { frequency[p.x%SZ(frequency)]++; } #elif 0 // (4) for_eachとc++11のラムダ式 for_each(positions.begin(),positions.end(), [&frequency] (const POS& pos) { frequency[pos.x%SZ(frequency)]++; }); #else // (5) for_eachと関数オブジェクト for_each(positions.begin(),positions.end(), FunctorClass(frequency)); #endif } cout << " Time=" << getTime()-start << endl; for (int i = 0; i < SZ(frequency); ++i) { cout << " frequency[" << i << "]=" << frequency[i] << endl; } return 0; }