2020年 進化計算コンペ

進化計算コンペティションは，進化計算の実応用と産学交流を促進するために，2017年に始まった最適化コンペティションです．過去3年のコンペティションでは，現状の進化計算の主な応用先である製造業や航空宇宙分野における連続最適化問題を出題してきました．

• 2017年：複数車種の同時設計
• 2018年：月着陸地点の選定
• 2019年：発電用風車の設計

今回は，進化計算の新しい応用先を開拓する目的で，ゲーム業界における『ゲームを楽しくする乱数の設計問題』を取り上げます．通常，ゲームに使われる乱数はメルセンヌ・ツイスターやXorshiftなどのごく一般的な方法で生成します．しかし，これらの数学的には偏りの小さいはずの乱数が，ゲームのプレイヤーにとっては偏っているように（時には恣意的に操作されているようにさえ）感じられ，強い不満をもたらすことがしばしばあります．人間は確率的な事象に対して様々なバイアスをもっていることが知られており，偏りのない乱数は人間にとってむしろ偏っているように感じられるのです．そこで今回のコンペティションでは，いかにしてプレイヤーにとって偏りのないように感じられる（実際には偏った）乱数を設計できるかを競います．進化計算コンペティション初の組合せ最適化問題です！

お知らせ

• 2021年01月13日10時30分: 結果を公開しました！今年もたくさんのご参加ありがとうございました．
• 2020年12月08日14時30分: 競技終了を12/16(水) 23:59に延長しました！よりたくさんの方のご参加をお待ちしております！
• 2020年11月28日03時30分: クライアントv1.2.0を公開しました．参加者の皆様には更新をお願いします．
  • 更新方法：$ pip install -U opthub-client-cli
  • 変更点：
    • ログインから30日が過ぎるとアクセストークン更新エラーが発生してプレイできなくなる問題を修正しました．
    • ログインの有効期限を30日間から90日間に延長しました（競技期間中に突然ログアウトしてしまうのを防ぐため）．
• 2020年11月11日13時30分: 協賛と問題提供者からのメッセージを公開しました！
• 2020年11月02日15時30分: コンペ問題を考察するための情報を公開しました！
  • コンペサーバ上で実行されているソースコードを公開しました．ご自身のPCで実行することができます．ご自身で実行したぶんはコンペの評価回数にはカウントされません．ただし，非公開パラメータの値は本番の問題とは異なります．
    • 問題のコード
    • 単目的部門の評価指標のコード
    • 多目的部門の評価指標のコード
  • いっぱい試行錯誤できるようにチュートリアル問題の評価回数を100万回に増やしました💪💪💪（チュートリアル問題のスコアはコンペ本番の成績には関係ありません．解の送受信テストにご活用ください）
    • 単目的部門のチュートリアル問題
    • 多目的部門のチュートリアル問題
• 2020年10月30日20時00分: 🚀EC-Comp 2020がスタートしました🚀
• 2020年10月30日08時00分: チュートリアルにてEC-Comp 2020と同じタイプの問題を公開しました．解の送受信のテストにご利用ください．
• 2020年10月30日06時00分: コンペティションは10月30日20時00分より開始いたします．（終了日時に変更はありません）
• 2020年10月30日06時00分: 問題の詳細を公開しました．
• 2020年10月30日06時00分: クライアントv1.1.0を公開しました．参加者の皆様には更新をお願いします．
  • 更新方法：$ pip install -U opthub-client-cli
  • 変更点：
    • 誤ったフォーマットの解を送信したときに応答しなくなる問題を修正しました．
      • 誤った解を送信した場合はエラーが返ります．エラーは評価回数にカウントされません．
    • 解の評価結果にエラーメッセージを追加しました．
      • 目的・制約計算時のエラーはevaluation_errorに，スコア計算時のエラーはscoring_errorに格納されます．
• 2020年10月23日21時40分: アカウントは必ず所属組織のメールアドレスで登録していただきますようお願いします．複数アカウントを防止するため，GmailやiCloud等のアドレスではコンペに参加できません．
• 2020年10月23日21時40分: 所属組織のメールアドレスではないと思われるアカウントが確認されたため，開催を再び延期させていただきます．新しい開始日時は，アカウントの確認がとれ次第、本ページと進化計算学会MLにてアナウンスいたします．度重なる延期となりますことお詫び申し上げます．また，参加者の皆様には所属組織のメールアドレスにてアカウントを作成していただきますようお願いいたします．
• 2020年10月23日17時50分: EC-Comp 2020の開始時刻を2020年10月23日22:00 (JST)に延期させていただきます．楽しみにしていただいた皆様にはお詫び申し上げます．

結果発表

• 単目的部門
  • トップ賞：tomtkg
  • 準トップ賞：kushida
  • 審査員特別賞：harada
• 多目的部門
  • トップ賞：tomtkg
  • 準トップ賞：harada
  • 審査員特別賞：sakaki_tohru

結果発表スライド

スケジュール

結果発表に参加するためには，進化計算シンポジウム2020へのお申込みが必要です．詳しくは進化計算シンポジウム2020のページをご覧ください．

参加方法

どなたでも無料で参加できます．

今年からオンラインでの競技方式に変わりました．こちらのチュートリアルにしたがって，所属組織のメールアドレスでアカウントを作成してください．

==9月の進化計算学会研究会のハンズオンに参加された方へ
ウェブサイトの正式公開に伴い，ハンズオンで使用したアカウントは削除させていただきました．また，クライアントをアップデートしました．ハンズオンに参加された方も，改めてチュートリアルをプレイしていただきますようお願いいたします．==

コンペティションは単目的部門と多目的部門に別れており，各アカウントはいずれか一方または両方の部門に参加することができます．それぞれの部門には，問題を解くことで参加したとみなされます．1つの部門は複数の問題からなり，参加した部門のすべての問題を解く必要があります．

1人で参加することも，複数人が1チームとして参加することもできます．1チームの人数に制限はありません．チームで参加する場合は，代表者を1人決めて代表者がアカウントを作成してください．１人の参加者が複数のチームに所属することはできません．ただし指導教員は禁止事項に違反しない範囲で複数のチームにアドバイスできます．Q&Aもご覧ください．

禁止事項

以下に違反した場合は失格となります．

• 1人で複数のアカウントを作成してはいけません．
• アカウントおよびアクセストークンを他人に譲渡してはいけません．
• 競技期間中は，サーバに送受信したデータおよびその派生物（データを使って構築した応答曲面やソルバプログラム等）をチームメンバー以外の人に教えてはいけません．また，SNS等の不特定多数が閲覧できる場所に公開してはいけません．
• コンペティションに関するソフトウェアをリバースエンジニアリングしてはいけません．
• 悪意をもってコンペティションサーバを停止または不安定化する行為をしてはいけません．

結果発表について

12月19日のプログラム（暫定）

表彰

単目的部門・多目的部門のそれぞれに複数の賞を用意します．受賞者には進化計算学会から表彰と，KLab株式会社様から賞品がございます．詳しくは後日発表いたします．

参加者へのお願い

• 参加者には，結果発表において5～10分程度のプレゼンテーションをお願いします．以下の点について説明してください．スライドは12月18日までにお問合せ先に提出してください．
  • 利用したアルゴリズムの説明（工夫した点を含む）
  • 結果
• 「結果の総括」において，皆さまから提出していただいたデータの比較を行いますのでご了承ください．
• 実問題の研究を促進するために，皆さまから提出していただいたデータは後日コンペサーバ上で公開させていただきます．特にご希望がなければ，データの所有権はデータを送信したアカウントの所有者に帰属するものとし，ライセンスはクリエイティブコモンズ 表示 - 継承 3.0とさせていただきます．これは，誰もが皆さまのデータを利用して研究を行ったり，論文を執筆したりできることを意味します（データを利用した論文には皆さまの名前が記載されます）．もし問題がありましたらお知らせください．

協賛

KLab株式会社様より優勝賞品をご提供いただきました．

問題提供者からのメッセージ

KLab株式会社の於保です。

今回の進化計算コンペティション2020では、出題原案のアイディア提供と協賛というかたちで当社が関わらせていただいております。どうぞよろしくお願いいたします。

さて、今回の問題ですが、これまでとはかなり趣の異なるものではあるのかなと思います。せっかくなのでこの問題ができた裏話を少しお話ししようかと思います。

今回の問題の元になったアイディアは、私が10年ほど前に仕事でソーシャルゲームの運営をしていた時に遭遇した課題がきっかけです。詳しいことは諸事情によりあまりお話しできないのですが、ざっくり言うとユーザー体験を向上させるためにそれまで手作業で作成していた乱数のもとになるデータを、遺伝的アルゴリズムを活用して計算するツールの開発をして解決したというものでした。

この事例を弊社の濱田に話したところ、実はこういった課題は私の手がけた事例に限らず多くのゲームに現れるものであり、既存の研究とも繋がりがあるとわかったため、今回のコンペティションに出題することにしました。当時片手間に考えたことがこんなにも大きな広がりを持っていたのかという驚きと、そこまで至らなかった過去の自分に少しの悔しさを感じています（笑）。ゲームの中でつかわれる乱数は、それぞれのゲームの「ゲーム性」に非常に密接に関わる部分でもあり、ここでの知見が新たな応用に結び付く可能性があるとも言えると考えています。

ゲームというと一般的には遊びのコンテキストで捉えられ、たかが遊びと思われがちですが、実際のところ現代のゲームは、皆さんが想像している以上に巨大なテクノロジーの集大成となっています。例えば、今回のテーマになっている乱数はもちろん、写実的な画面表示に関わる数学や、敵味方のAIの仕組み、物理計算や効率的な探索アルゴリズムやデータ構造、データの圧縮や暗号化、チート対策などのセキュリティなど、数学とコンピュータサイエンスのオンパレードです。また、ユーザーの行動などの様々な情報が、リアルタイムにデータ化されていることも面白いところだと思います。

今回のテーマをきっかけに、研究対象としてのゲームの魅力に気付いていただけたら、非常にエキサイティングだと思いますし、それによってさらにゲームの可能性が広がることが楽しみです。きっと我々現場の開発者は気付いていないだけで、もっと面白い課題が埋もれているはずです。

今回のコンペでは是非、ゲームのように楽しんで問題に取り組んでいただければと思いますし、皆さんの知的好奇心を満たし、新たな知見と広がりを見出すきっかけになれば幸いです。

2020年11月11日　KLab株式会社　エンジニアリングマネージャー　於保　俊

総合順位の決定方法

単目的部門・多目的部門それぞれ部門ごとに総合順位を決定し，総合順位の上位者を表彰します．

総合順位は，各部門16問の順位の総和（小さいほど良い）で決定します．問題ごとの順位は，単目的部門では目的関数の最小値，多目的部門ではHypervolumeの最大値で決定します．

Q&A

Q1. 進化計算を使って解かなければいけませんか？

A. どんな方法で解いても構いません．人力でいくつか解を送って様子をみたり，応答曲面を構築したり，途中でソルバーを打ち切って再スタートすることもできます．ホワイトボックスな関数については，ローカルでプログラムを組んで好きなだけ評価しても構いません．要するに，禁止事項に抵触しない限りは何でもアリです．もし判断に迷うことがあれば，お問合せ先までご質問ください．

Q2. 間違って解データを送信してしまいました．やり直せますか？

A. 今年のコンペは一定の評価回数で競うため，一度送信したデータを取り消すことはできません．チュートリアル問題で十分にテストしてから本番の問題を解くようにしてください．

Q3. 問題を解いている最中にソルバープログラム（またはコンペサーバ）が落ちました．途中から再開できますか？

A. 一度送信したデータはサーバに記録されており，opt list solutionsコマンドで取得できます．しかし，ソルバーを同じ状態から再開するためには，ソルバーの状態変数や乱数種なども復元する必要があるはずです．これらはご自身で定期的にファイルに保存するなどして，突然のトラブルに備えてください．

Q4. コンペ運営に関わっている教員とその学生はコンペに参加できますか？

A. 参加できます．代表幹事以外の委員は，問題を解くうえで有利になるようなインサイダー情報は知ることができません．そのため，運営に関わる教員やその学生であっても，一般参加者と同じ公平な条件で参加できます．

Q5. うちの研究室からは複数のチームが参加します．教員はすべてのチームに参加したいのですが？

A. 教員は指導目的で複数のチームにアドバイスできるものとします．ただし，お互いのチームのデータを教えないようにしてください．アドバイスの内容も，個々のチームのデータだけから分かることに限定してください．

Q6. アカウントを削除できますか？

A. 競技期間終了後に削除できます．お問合せ先までご連絡ください．なお，アカウントを削除すると，そのアカウントで送信したデータも削除されます．

Q7. 解は並列に送信できますか？

A. 複数の問題に同時に解を送信することもできますし，同じ問題に複数の解を同時に送信することもできます．並列数に上限はありません．解はサーバに登録された順番に評価されます．解を並列に送信するには，以下のような方法があります．

• 複数の端末を起動してそれぞれでopt submitコマンドを実行する．
• 1つの端末で複数のopt submitコマンドをバックグラウンド実行する．
• opt submitコマンドに--no-waitオプションを指定する．この場合，サーバでの評価・採点を待たずにコマンドが終了します．評価・採点の結果を取得するには，しばらく待ってからopt list solutionsコマンドを実行します．

Q8. WindowsコマンドプロンプトでHuge問題 $(N=27720)(N=27720)$ に解を送信するとエラーが発生します

A. Windowsのコマンドプロンプトでは，コマンドの長さが8192文字までに制限されています．コマンドラインに解を直接記述するとこの制限をオーバーしてしまいます．そのため，解をファイルに保存して，ファイル経由で送信する必要があります．
Pythonの例：

import json
from subprocess import check_output

def evaluate(x):
    with open("solution.json", "w") as f:
        json.dump(x, f)  # Write a solution to the file
    stdout = check_output("opt submit --match=3 --solution=solution.json", shell=True)  # Submit the solution
    y = json.loads(stdout.decode("utf-8"))  # Convert a JSON string into dict
    return y


if __name__ == "__main__":
    x = "12345123451234512345123451234512345123451234512345"
    res = evaluate(x)
    print(res)

お問合せ先

進化計算学会 実世界ベンチマーク問題分科会
eccomp2020@googlegroups.com