このエントリーは、KLab Advent Calendar 2017 の12/4の記事です。
今年のISUCONはKLabが作問するということで、ゲームが題材だと予想していた方も多かったと思います。 その期待(?)に応えるべく、本選ではCookie Clickerを元にしたゲームを出題しました。 これを複数人で協力プレイできるようにして、WebSocketを使っていて、クッキーではなく椅子を増やし、椅子の数が多倍長整数になる、というゲームでした。
この記事では @hasi_t がISUCON7本選の作問でやったことを書きます。
まずプロトタイプ作成を担当しました。 Cookie Clickerを元にする、という案が出ていたので、自分がやりたい要素を入れたプロトタイプを作りました。
一つ目の要素は未来計算と操作遅延です。 サーバが未来の値を計算できるようなデータを返し、クライアント側で各時点での値を計算するようにする、という設計です。 そして操作を遅延させることで可能な限り同時刻での見え方が同じになるようにしました。 このような設計によって通信頻度を下げる、というのは、 CEDEC 2015で発表したことの実践で(参考)、 それを実現するための技術や開発体制について普段の業務で日頃考えていたりするのですが、 その実態を見せる機会と考え、この要素を入れました。
二つ目の要素は多倍長計算です。 以前、 ICFPC 2016 というプログラミングコンテストに参加したときに多倍長有理数を使って、 こういう多倍長計算を使った問題を作りたいと思っていた、というのがあります。 あと、メモリを消費させて、ただキャッシュするだけでは駄目なようにしたい、というのも考えていました。
ちなみに、作問チームのうち3人 (@mecha_g3, @___Johniel, @hasi_t) はここ4年ほど、この3人だけではないですが、DiamondPrincessというチームでそのICFPCに参加しています。そして今年は2位でした!
プロトタイプの時点ではWebSocketではなく、普通のHTTP通信で、サーバはPHPで雑に書いた状態でした。 ver0とver1を作ったのですが、ver0の時点ではミリ秒単位ではなく秒単位だったりしました。 あと、命名が雑すぎて抽象的な一文字変数名だらけになっていたので、本実装時に名前の調整が結構大変でした。
WebSocketを使うことになり、初期実装は他の人に任せて、 ゲーム画面を作るためにJavaScriptコードをロジックとビューに分割したり、 いい感じのフォントを探したりしていました。
未来計算の設計時点で、ベンチマーカから見て検証可能にすることを考えていました。 誤差を許容するには、許容範囲やそれに合わせた計算など、考えることが多く、それを避けた結果、厳密な検証になりました。 そのため、値が1でもずれるとfailするという厳しいコンテストになりました。
負荷走行前の検証はaddIsu, buyItemに対するレスポンスが必ず存在するので良かったのですが、 負荷走行後の検証はタイムアウトなどでレスポンスが無い場合を考える必要があり、 上限と下限を考えて検証する必要があってちょっと大変でした。
エラーメッセージを参加者にとってわかりやすくする、という作業をするのがぎりぎりになってしまい、 初期実装作成者には苦労をかけてしまいました。
当然といえば当然ですが、初期実装そのままで検証していたら、 負荷走行後の検証の実行時間が長すぎる問題が発生し、高速化をしました。
やったこととしては、指数表記変換関数の高速化、item価格と生産速度のキャッシュ、1000回ループの回避、指数表記変換関数内の10のn乗のキャッシュ、addingの累積和を使う、などです。
実装は以下の通りです。指数表記変換関数(big2exp)はutil.goにあります。
とりあえず、Go言語のbig.Intは、つらい、という感想でした。
いい感じのマスタデータにしないと多倍長使う意味が無い、と思っていたので、 1分間のベンチマークで10の10万乗ぐらいまで到達できるようにマスタデータを調整しました。 調子に乗って1個目の購入価格が10の10万乗ぐらいあるアイテムを作ったら、 初期実装の時点でそこが重すぎて、リハーサルやってみたけどまともにチューニングできない、 みたいなことも起きたりして申し訳ない感じだったりしました。
ちなみに、Excelで値を調整して、Pythonスクリプトで雑なシミュレーションをする、ということをしていました。 もちろん、値を直接扱えないので、対数をとって計算していました。
参加者の皆様、運営の皆様、お疲れ様でした! いろいろご迷惑おかけしましたが、出題することができて嬉しく思っています。 ありがとうございました!
KLabのゲーム開発・運用で培われた技術や挑戦とそのノウハウを発信します。
合わせて読みたい
KLabのゲーム開発・運用で培われた技術や挑戦とそのノウハウを発信します。