カメヲラボ

主にプログラミングとお勉強全般について書いてます

Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tips

保存版

ある日、マラソン王者のPsyhoさんがつぶやきました。

要約すると、

これから24時間、1いいね毎にヒューリスティック/ボット プログラミングコンテストのヒントを投下します。

という話です。このまとめ記事を更新する時点で1000を超えるいいねがついていて、皆Psyhoさんのありがたいお言葉を楽しみにしています。というわけで、私が1つ残らず捕捉して順次日本語にしていきます。基本的にはDeepLとChatGPTで翻訳して、そこからさらにざっくりと私が適当にまとめました(意訳がちょっとあるのと、見出しや補足のために多少の追記があります)。まずは精度よりも速度重視でやっていきますので、翻訳に問題がある場合はご指摘いただけるとありがたいです。 英語を読むのが辛くなければ実際のツイートを見るのがベストですが、どうしても英語がツライという方はどうぞご利用ください。

一般的な話題(その1)

#0: 無料のアドバイス

誰もが個性的で、いろんな背景を持っています。一人一人が異なるテーマで苦労しています。 すべてのアドバイスがあなたに当てはまるわけではありませんが、できるだけ一般的なものにするよう心掛け、状況に特化したものがある場合はその旨を述べるようにします。

#1: 1週間あれば、コンテスト中にあらゆる研究ができる

たとえ経験が浅くても、ひとつのコンテストに一所懸命取り組めば勝つチャンスはあります。これは何年も練習が必要な短期のプログラミングコンテストとは対照的です。

#2: 高度な数学は必要ない

シミュレーションのコードを書くという選択肢は常にあります。私が参加した約200のコンテストで、数学の知識があったために良い成績を収めた例は1つもありません。例外があるとすれば、ベイズの定理くらいですね。ちなみに私は微積分を知りません😅。

#3: ヒューリスティック(以下H)コンテストでは、ビームサーチと焼きなまし

グラフ理論、動的計画法、線形計画法、フロー問題などをきちんと経験しておくと便利な場合もあります。

#4: タッチタイピングは超重要

もしタッチタイピング(いわゆるブラインドタッチ)ができないなら、最優先すべきです。だいたい10時間から30時間くらいかかると思います。 タッチタイピングをすることで、コーディング中に他のことを考えることができるようになります。バグの数を減らし、プロトタイピングをスムーズにする、などなど。

#5: H(ヒューリスティック)コンテストとB(ボット)コンテスト、どちらが良い？

標準的なテクニックの違い以外に、主な違いは、Hコンテストでは迅速かつ正確なフィードバックが得られるのに対し、Bコンテストでは一般的により楽しいということです。 Hコンテストでは、より速いペースで学習することができます。

#6: コンテストを開催するのに最適なサイト

H: Topcoder (マラソン), AtCoder (AHC) B: CodinGame (今、コンテストが開催されています！) どのサイトも、良い問題、公平な評価システム、コンテスト後に解法について話し合うコミュニティが特徴です。 UIが荒いサイトもあるかもしれません;)

#7: [H]問題についてググるのは大体時間の無駄

良い問題デザイン(上記のサイト)とは、問題作成者が問題がユニークであることを確認したことを意味します。 ※まれに例外もあります。特定の部分問題でよく知られているものを研究するのはアリかもしれません。

#8: プロトタイピングのスピード

ほとんどの人にとって、最も制約の多いスキルはプロトタイピングのスピードです。 ある程度の経験を積めば、実装したいアイデアが常に何十個も出てくるようになります。それをいかに早く反復できるかということが、限界の要因です。速ければ速いほど、問題点を早く知ることができます。

#9: 1つのコンテストに集中する

早く上達するためには、中途半端に多くのコンテストに参加するのではなく、一つのコンテストに集中することが一番です。 基本的な解法ばかりやっていても、あまり身につきません。正しい学習期間は、壁にぶつかってどうしたらいいかわからなくなったときから始まります。自分を追い込まないと結果は出ません。

焼きなまし法(SA)について

#10: SAに代わる局所探索はすべて(ほとんど常に)ダメ

遺伝的アルゴリズム、タブーサーチ、蟻コロニー、などなど。これらは忘れてください。これらは効果が薄いだけでなく実装に時間がかかります。

#11: なぜSAなのか？

  • 山登り法(HC)から始めて、2行追加でSAに変換することができる
  • 高速な動的評価が可能
  • 適切に調整すれば、他の手法よりも高いポテンシャルを発揮する(高速なので)
  • 非常に高速なイテレーションが可能

#12: 標準的なSA

温度スケジュール: t = t_start * (t_final / t_start) ^ time_passed、time_passed は 0..1 の範囲

受理(最小値が良い場合): RNG() < exp((cur_result - new_result) / t)、RNG() は 0..1 を均一に返す

出発点としては、ほとんどの場合でこれが最も良いです。

#13: SAにおける温度管理は受理率がゆっくりと減少するようなものが良い

同じ受入率の値にずっと留まっていると、効果がありません。

#14: 局所最適解に陥りやすいときの対処法

  • 非常に高い温度/加速度
  • 複雑な遷移状態(※訳注:遷移状態を複雑にして解の変更を緻密にすることで、局所最適化から抜け出しやすくなる？)
  • (まれに)キック(※訳注:解を強制的に変更する)
  • (まれに)ソフトリスタート(解法は変えずに温度管理をやりなおす)
  • (まれに)複数回実行

#15: 制約のために多くの状態が無効になる場合に行うこと

a) 初期重み0、最終重み∞の衝突回数に基づくスコアリング要素を追加する。 b) (可能であれば)部分的な解に対して高い温度で短いSAを何度も実行する。

#16: 評価が非常に高速の場合に行うこと

これはあなたの想像以上にずっとよく起こります。

#17: SAの全体的な優先順位

  • 異なる遷移関数のプロトタイプを作る
  • 評価関数を非常に高速にする(つまり動的にする)
  • 適切な温度管理を見つける(通常3-4回実行するだけで十分)
  • たくさんテストする
  • 上記が終わってから、他のことに移る

#18: 常に最良結果を更新し、最終結果ではなく最良結果を返すようにする。

このミスを何度見たかわかりません。常に最良結果を更新することで、最終的な温度をより高くすることができます。

#19: SAがイマイチな場合

  • 局所最適に陥りやすい: #14にヒントがあります。
  • 単純な遷移と複雑な遷移が混在している: 各遷移に対して別々の受容関数を用意する。
  • 遷移中に評価が非常に不安定になる場合: 運が悪かったとしか言いようがない さて、SAについてはもう十分でしょう。

コンテストは基本的に単純なフィードバックループです。 a) 何かをする b) 結果を得る c) 情報を抽出する

このうちのどれかを改善することで、より良くなることができます。しかし、最も軽視されているのは(b)の部分です。

テストについて

#20: テストはコンテストで最も軽視されている点である

テストは、フィードバックを得るための手段です。もしテストが遅ければ、進歩は非常に遅くなります。テストが不正確だと、正しい次のステップを見つけるのが非常に難しくなります。 Bでのテストは非常に難しく、ほとんど実行不可能なことが多いので、これは主にHに焦点を当てます。

#21: [H]ローカルのテスターを使う

もしあなたが評価のために仮のテストを使うだけなら、あなたは自分自身にとってすべてを非常に困難にしています。時間を節約するのではなく、無駄にしているのです。 (※訳注:ローカルでテストせずに提出してスコア確認するのは時間の無駄ですよ)

#22: [H]良いローカルテスターを使う

絶対に必要なのは、次の2つの機能です。 - マルチスレッド(複数のテストを別々のスレッドで実行する機能) - 相対スコアリング(これはtopcoderの標準機能です) もし自分で持っていないなら、私のものを使ってください: https://github.com/FakePsyho/mmtester

#23: テストの速度は制約になりやすい

あなたの解法がコンパクトで簡単に拡張できる場合、数秒で機能を追加/削除することができます。つまり、コンテストのある時点で、解法の異なるバージョンをテストすることが主なボトルネックになりそうなのだということです。

#24: 素早いテストのために外部VMを使用する

強力なマシンを持っていない場合は、AWS/GCP/Azureを使用して素早くテストすることができます。Linuxの知識があれば、1-2時間で習得できます。スポットを使えば、5ドルであなたのノートパソコンと同等のものを1週間稼働させることができます。

#25: テストをできるだけ頻繁に実行する

コンテストでは、自分でテストができるようにテスターが用意されています。 テストを行えば、あなたがどこかでミスをしたのかがよくわかりますし、改良点についてのフィードバックも得られます。

一般的な話題(その2)

#26: バージョン管理は悪

あなたはgitの使い方にとても慣れていて、それでスピードが落ちることはないと感じているかもしれません。そしてそれは真実かもしれません。とはいえ、もしそれが自分にとって便利だと感じているのなら、あなたはプロトタイピングが下手なのです。プロトタイピングのスキルを見直しましょう。

#27: バージョン管理は悪だがテストを実行するときは別

テストを実行するときは現在のソースファイルを保存しておくと便利です。これは、予期せぬ結果が出たときのサニティチェック(※訳注: ある状態や結果が正しいかどうかを確認する)として機能することが多いです。テスト時にソースファイルを保存する短い.sh/.batスクリプトを作るだけでよいでしょう。

#28: コードを最適化する価値があるかどうか迷ったら、制限時間を延ばして実行してみる

これは非常によく使われるシンプルなテクニックです。潜在的な利益が非常に低い場合は、コードを最適化しないようにしましょう。

#29: 言語の選択 - C++は孤高の王者

マクロはC++の問題の多くを解決することができますが、あなたが何をしているかを知っていれば、C++から他の言語よりもはるかに多くのものを絞り出すことができます。 *私はRustの経験がない+非常に複雑なトピックなので、あまり真に受けないでくださいね。

#30: 何よりもバグを取り除くことを優先すべき

バグがある場合、その解法はあなたが思うようには機能しません。これは、テストを実行するたびに、間違った結果を得ることを意味します。問題に対する直感が正しく育たなくなるのです。 とても重要なことです。

#31: 直感に反する結果が突然出たら、その度に調査をする

バグがあるのか(上記参照)、直感が狂っているのか、どちらかです。後者の場合は、これを学習経験として扱い、なぜ間違っていたのかを突き止める必要があります。

#32: 解答コードは小さくまとめる

コードが多くなると - バグが増える - コードの内容を全部覚えるのは、精神的にもっと大変です。 - (通常)依存関係が多くなる -> リファクタリングのコストがかかる 上位の多くは、400-1000行程度のコードです。

#33: コンテスト参加後は必ずフォーラムを読むこと

これまで述べてきたすべてのプラットフォームにおいて、(ほぼ)すべてのトップクラスの競争相手が、コンテストが終了した後に自分の解法を説明しています。コンテストに参加した後、他の人が何をしたかを読まないのは、信じられないほど無駄な機会です。 では、なぜそのようなコンテストで常に優秀な人がいる一方で、常に苦戦している人がいるのか、その理由を説明しましょう。

#34: 良い解法には時間がかかる

まず当たり前のことですが、良い解法を開発するには時間がかかります。 魔法のようなテクニックや回避策はありません。でも、時間が経てば速くなりますよ。

#35: 実行 > アイデア

なぜ、多くの異なるアプローチが上位にあるにもかかわらず、どれも同じようなスコアなのか、不思議に思うかもしれません。このような場合、「完璧なアイデア」を持つことよりも、「うまく実行すること」が重要です。

#36: 問題文やテスターのコードを隅々まで読む

問題文の細かい部分を思い出せるようになるまで、問題文を読み直しましょう。テスターのコードも同様に読みましょう。 最初に読んだときには見逃していたような小さな詳細がよくあります。特に、非自明な論理を含む場合は、提供されたコードも読んでください。

#37: 何が自分のモチベーションになるかを見つける

多くの競技者にとっての最大の原動力は、自己研鑽の喜びです。HでもBでも、未来の自分が過去の自分より良くなろうとする孤独なゲームであることがほとんどです。他の競争相手をベンチマークとして扱い、自分の目標とはしないことです。

#38: 大して良くならない解法に時間を浪費しない

現在の解法が良い結果を出せないことがわかっているなら、それを最大限良くしようとしても意味がありません。 リーダーボードの頂点に立つ最も簡単な方法は、高い目標を掲げて失敗することです。

#39: ツールで生産性が爆上がり

Hの場合は主にローカルテスター。Bの場合はローカルリーグ方式です(信頼性は低いですが)。私の試算では、ローカルテスター(リンク先)を改良した後、コンテストに費やす時間が30～40％程度減りました。

#40: 優れた競争者はアイデアが尽きない

テストを実行したり、ビジュアライザー(H)/ゲーム(B)を見たりすることで、より多くのインスピレーションを得ることができます。解法に取り組むことで、アイデアを得ることができるのです。最初のうちは、どんなに優秀な人でも、何がベストな解法なのか、まったくわからないものです。

競プロ(アルゴ)的なお話

また切り替わる。CodeForcesからたくさんの人が参加してくれたので(マイクありがとう😁)、古典的な競技プログラミング(CP)とH/Bコンテストの違いについて話してみようか。 ちなみに、今はもうクラシックCPはやっていませんが、topcoderで4位になった時期もありました。

#41: CPとH/Bコンテストは全く違うスキルが必要

CPは短距離走で、非常識な集中力と豊富な知識が必要です。 H/Bはマラソンで、長期的な計画と創造的思考・問題解決が主体です。

#42: CPの場合「相手」は問題設定者であり、H/Bでは(主にH)、相手は過去の自分である

H/Bでは問題解決に終わりはなく、解決は継続的なプロセスです。コーディングセッションの間に自分の生活を合わせなければならない。問題の切り替えが非常に難しいのです。

#43: CPでは最悪のケース、H/Bでは平均的なケースを気にする

これにより、完全に新しいクラスの技術が開かれます： - ランダム化アルゴリズム - 特殊なケースを素早く処理するための様々なバージョン - プルーニング(早期終了) (※訳注: プルーニングは計算時間やリソースを削減するために処理を途中でやめることで、探索アルゴリズムだと枝刈りのようなものだと思ってください)

#44: CPの経験があると、H/Bコンテストの基礎が固まる

CPのアルゴリズム知識はある程度しか役に立ちませんが、非常に比較的短時間で繰り返しコードを書くため、プログラミング言語の練習やバグのないコードの書き方を身に付けるにはとても効果的です。

#45: CPは就職に有利、H/Bは仕事ができるようになる😁

多くの企業が採用活動でプログラミングパズルを使用しますが、CPはそれ以上に大して役に立ちません。H/Bコンテストは、AI企業に入社するとよく遭遇する小規模な研究に似ています。

初心者向けアドバイス

では、初心者の方へのアドバイスです。

#46: プログラミングの初心者にはH/Bコンテストを勧めない

もしあなたがプログラミングの初心者なら、H/Bコンテストはお勧めしません。 まずCPに挑戦し、言語のシンタックスを学び、BFS/DFSや1次元DPなどの簡単なアルゴリズムを学びましょう。基本的なことを素早く理解するためには、より速いフィードバックサイクルが必要です。

#47: コンテストを見つけ、そのための時間を確保し、ベストを尽くそう

おそらく失敗するでしょうが、それでいいのです。失敗することは学ぶことであり、勝つことは何も教えてくれません。自分がうまくいかなかったと思う理由をすべて書き留めておいてください。自分が苦労しているところを見つけるのです。

#48: 出場しなくても、問題を読むのはアリ

以前見たことのあるような新しいコンテストを見かけたらフォーラムを全部読んで、何か応用できそうなことがないか見てみましょう。 少ない経験で良い成績を残すには、圧倒的に簡単な方法です。

#49: コンテスト開始当初は(コンセプト的に)シンプルな解法の実験に集中すること

あなたの目標は、問題に対する直感を養うことであって、手っ取り早く得点を稼ぐことではありません。アドレナリンが出るのは良いことですが、長期的には何の役にも立ちません。

#50: 可能性のあるアプローチを評価する良い方法は、良い答えで終わるために、どのようなステップを実行しなければならないかを考えてみること

もし、それが不可能であったり、非常にあり得ないと思うのであれば、おそらくそれは良いアプローチではないでしょう。

#51: 小さな漸進的な変更に集中する

解法を書き換えることは避けましょう。 小さな変更＝速いフィードバックサイクル、少ないバグ、より良いモチベーション。ちなみに、私は自分の解法を書き換えたことはありませんし、テストせずに10～15分以上経過することはほとんどありません。

#52: コードの最適化は、悪い解法を素晴らしい解法に変えることができる

ほとんどの反復的アプローチ(SAなど)では、そのアプローチが良い結果を生むまでに、ある程度の重要な反復回数/ステップを必要とします。コードの最適化によって、全く新しい可能性が開けることもあるのです。

#53: もしテストやゲームの結果に一貫性がないと感じたら、それはテストやゲームの数を増やせということ

解法が改善される一方で、テストの精度を高めるために、より多くのテストが必要になります。1回の実行で 2-5K テストを使用することは珍しくありません。

#54: Pythonをコンテストに使わない

Pythonはある用途には最適ですが、通常の操作ではおよそ100倍も遅くなります。妥当な速度を得るためには、コーディングやアルゴリズムで非常に創造的になる必要があり、それはあなたのコードがずっと複雑になることを意味します。そこまでする必要はありません。

#55：自分を信じること。

自分はうまくいかない、手が届かない、と盲目的に思い込んでしまうと、モチベーションを維持するのはとても難しいです。私は、考え方を変えただけで、突然良いパフォーマンスを発揮する人にたくさん会いました。

最適化のお話

さて、次はコードの最適化に関する一般的なテクニックを紹介します。

#56: コードの最適化に理論的考察の必要なし

ターゲットマシーン上でコードを実行し、それを測定しましょう。 コンパイラのバージョン、OS、プロセッサの違いは大きな影響を与えます。

#57: N次元の座標は1次元に統合する

これは非常によくあるテクニックです。2次元のグリッドがあり、その上でBFSを実行するとします。(行, 列)を使う代わりに、それらを1つの値にマージします。メモリフットプリント(※訳注:メモリ使用量と考えてください)、演算数、コード自体を減らすことができ、通常は10-30%高速化されます。

#58: メモリ割り当ては非常に遅い

メモリプールの経験(※訳注:自分でメモリの割り当てをやり繰りする経験と思ってください)がない限り、一般に、すべての配列を一度だけ割り当てるようにしたいものです。時間計算量と空間計算量がO(N)の関数では、呼び出すたびにメモリを再割り当てすると、最大で10-50倍の速度になることがあります。

#59: 本当に必要なデータ構造は配列だけ

本当に必要なデータ構造は配列だけです。すべてのデータを単純な配列に置き換えることができないのは非常に稀です。 とはいえ、データ構造の最適化は複雑さを増す可能性があるので、時期尚早と考えることもできます。

#60: 剰余演算子は驚くほど遅い

正直なところ、理由はわかりません。でも、そういうものなんです。 次のように書き替える、かなり高速になることが多いです。

x = (x + y) % m

を

x = x + y
x -= x >= m ? m : 0
(y < m, y > 0, m > 0 と仮定して)

の方が速い場合が多いです。 (※訳注: typo修正済み)

#61: できることはすべて事前に計算し、それらの値を配列に格納しておく

常に良いというわけではありませんが、いくつかの演算は思ったより遅いかもしれません。例えば、"x ^ y"を事前に計算することは、その場で計算するよりもかなり速い場合があります。 (※訳注: これはxのy場を意味しています)

#62: 大きな配列を扱う場合、可能であればできるだけ小さな変数型を使用する

メモリコピー/クリアはバイト数だけを考慮します。これにより全体的なキャッシュ効率も改善します。単一の変数に対しては行わないでください。

#63: Fast-Clearing Arrayを使う。

3つの異なる操作を必要とするboolean配列をイメージしてください：

set(pos, value)
check(pos)
clear() - 配列全体をクリアする

ナイーブな実装ではO(1)+O(1)+O(N)ですが、カウンター(clear -> counter++)を持つint配列を使用することで、O(1)+O(1)+O(1)にすることができます。 (※訳注: tomerunさんのブログが参考になります)

#64: Fast-Clearing Arrayを拡張する

  • クリアするたびにカウンタがxずつ増えるなら、0..x-1に値を格納できる。
  • 衝突が許容されるなら、多くの場合、これはセット/マップを置き換えることができます。

#65: グラフには番兵を置く

グラフ内に特別なガード/境界を追加することで、経路探索中の操作数を削減できます。 例えば2DグリッドでBFSを実行する場合、境界条件のチェック(グリッドの外へのステップ)を避けるために、すべての方向に1ずつグリッドを拡張するとよいでしょう。

#66: 一般的に最も重要な高速化は、アルゴリズムを差分にすること

例えば、TSP(Traveling Salesman Problem)にSAを適用して、都市をパス上の別の地点に移動させる場合、Δにしか関心がないので、evalはO(1)であるべきです。

(※訳注: Δは変化量、差分という言葉は時間計算量が定数時間であると読んでください。)

(※訳注2: 当初は「差分」と書かれている部分を「動的」としていましたが、動的ではなく差分と解釈した方が良いのではとtoast-usさんからご指摘いただきました。確かに、ある状態を計算する場合や盤面の評価関数を計算する場合、前の状態を利用して差分計算するのは高速化にかなり良い影響を与えるという文脈だと思うので、それが良さそうです。)

#67: 時間の計測はコストがかかる(ことがよくある)

一番早いのは rdtscを呼び出す方法ですが、サイトによっては別の方法で時間を計測しているところもあります。c++でよく使われるgettimeofday()はシステムコールで、 プラットフォームによっては非常にコストがかかります。1Kコールで1秒以上かかったこともありました。

#68: プルーニング/早期終了/単純化された計算を使用する

これはあまり起こらないことですが、単純に計算をスキップする場合があります。これは主に評価関数で発生し、いくつかの遷移でスコアが完全に壊れてしまうので、すぐにわかります。 (※訳注: ちょっとわかりにくいですが、「評価関数において、ある遷移がスコアを完全に壊してしまうような場合、つまりスコアが良くなる見込みが全くないとわかった場合、その遷移を完全に打ち切る(枝刈りする)と良いですよ」という意味かと思います。)

#69: 非常に重いコードの最適化を行う場合は、ジャッジマシンをミラーリングする

gccの正確なバージョンを持っていることが一番重要です。 とはいえ、私は一般的に5%未満のスピードアップを目指す程度ならお勧めしません。パラメータの最適化の方がはるかに簡単です。

#70: SIMD/自動ベクトル化は超強力

私は最近これを使うことはありませんが、それでも強力なツールです。SSE/AVX命令セットを使うのは、ミニパズルを解いているような気分です。最高のコンパイラを上回るのは簡単で、重要な場所で2-20倍のスピードアップが可能です。

#71: [gcc]コンパイラのフラグ

"#pragma GCC optimize (...)"でコンパイラのフラグを(ほとんど)オーバーライドできるようになっています。 私は"Ofast,omit-frame-pointer,inline,unroll-all-loops"を使っています。理論上"omit-frame-pointer"は"-O1"に含まれますが、こちらの方が速かったです🤷。コンパイラのフラグでHC(山登り法)ができる😅。

(※訳注: 「inline、-O3、-ffast-math、-funroll-loops、... 他の便利なフラグはありますか?という質問に対してのツイートです」)

ボットコンテスト(コドゲ)について

ボットコンテストに特化した話をあまりしてきませんでしたので、ここからはそのお話をしましょう。 Bコンテストは形式も問題の内容もさまざまです。ここではCodinGame(コドゲ)に焦点を当てます。コドゲは頻繁にコンテストを開催する唯一のサイトです。

#72: ボットゲームの新しい概念

ボットゲームには新しい概念があります。それはメタゲームです。最良の戦略は、他のプレイヤーが採用する戦略によって大きく変わります。これは特に、不完全情報のあるゲームで問題が発生しやすいです。自分の解法をまともに評価することは忘れてください。

#73: 勝つか負けるのみ

各テストは本質的には、二者対戦ゲームであり、勝ちか負けかという2値の結果になります。どれだけ大きな優位/劣勢があっても、勝ちか負けかにしか過ぎません。自分の解法をまともに評価することは忘れてください。

#74: ローカルテスト

ローカルでうまくテストを実施できるようにするには、リーダーボード上のボットに代表される様々なアプローチを持つ必要があります。 解法をまともに評価することは忘れてください。 (※訳注: 自分のボットをテストするには、他のさまざまなボットと対戦するとよいといういみだと思います)

#75: フィードバックは重要

#20を覚えていますか？コンテストはフィードバックのループです。自分の解法を効果的に評価できない場合、直感力を高めることは困難です。 ボットコンテストでは、ノイズの多いフィードバックを受け、次のステップについて非常に大胆な推測をする必要があります。

#76: ボットコンテストは時間投資が大きい

ボットコンテストは、ヒューリスティックコンテストよりはるかに大きな時間投資を必要とします。 - フィードバック機構が非常に弱い - 常に進化するメタゲーム - すべてのリプレイにアクセスできるため、誰もがあなたのボットのプレイを知ることができる(そして、それに対抗することができる) - (しばしば)より複雑なルール

#77: 楽しいけれども初心者向けではない

ボットコンテストはインタラクティブなため、同じようなヒューリスティックコンテストよりもずっと楽しいものになる傾向があります。しかし、私は一般的にボットコンテストを初心者のための良い学習プラットフォームとして勧めません。フィードバックループが効果的でないため、自分の行動と結果を関連付けることが難しくなります。

#78: HスキルはBでも役立つ

Hで得たスキルや知恵のほとんどは、Bコンテストにも適用できます。 プロトタイピング。良いワークフロー。コードの最適化。多くのアルゴリズムとテクニックが適用できます(ビームサーチも使えます)。

#79: 2種類のテクニックのタイプ

多くのテクニックは2つのタイプに分類されます。1つは複雑な状態評価(別名ヒューリスティック)関数、もう1つは検索(ビームサーチ、ロールアウト、MCTS)です。 どちらが有効かは問題によって大きく異なりますが、成功するためには両方をマスターする必要があります。状態評価にニューラルネットが使えれば最強です。

#80: ノイズを無視する

評価は非常にノイズが多いので、それを完全に無視して、うまくいくと思われる解法に集中するのが良い場合があります。 検索ベースの解法は、メタゲームにあまり依存しない傾向があります。また、ローカルリーグのシステムを開発し、状態評価の調整を自動的に行うのもよいでしょう。

ボットコンテスト用のツール

これはヒントではありませんが、私は自動マッチメイキングを行う簡単なローカルリーグシステムに取り組んできました。mmtesterと似たようなものですが、ボットコンテストのためのツールです。 近い将来、PyPIパッケージとして公開できればと思っています。

#81: [コドゲ限定]持ち時間の使い方

通常、最初のターンの制限時間は1秒ですが、次のターンでは50ミリ秒になります。相手の行動が限られている場合は、最初のターンで2-3ターン先を「考える」ために使うのは非常に有効です。

#82:

現在のメタゲームを追いかけ、トッププレイヤーを真似ることで順位が良くなるかもしれませんが、長期的にはあまり多くの学びにはなりません。 もしあなたの目標が自分自身のレベルアップなら、そういったことを避けてみてください。

ここで一区切り

お話ししたいことは一通り触れたと思います。もちろんTwitterのスレッド上なので、共有すべき知識や知恵が大量にあることに比べればとても浅いものですが。 あとはQ&Aとまとめのために残しておこうと思う。 おやすみなさい💤。

この記事の作成者より

この先はQ&Aがいくらか続くと思いますが、何か目についたものがあれば追記しておきます。内容的な修正と見やすくする作業は続けます。