mayoko’s diary

プロコンとかいろいろ。

javascript で 2048 を実装してみた

何をやったのか

javascript 初心者が javascript で 2048 を実装した話です。

javascript で初めてアプリっぽいものを作ったのでやったことを残しておこうかなーと思って書いています。
作ったものはこちらです。
github.com

  • index.html, main.js, style.css を同じフォルダに置いて index.html をブラウザで開くと遊べます。
  • 「AUTO」を押すと AI が起動して勝手に動かしてくれます。「AUTO」を押すとボタンが「STOP」に変わりますが, それを押すと AI が止まります。

追記:遊べるようにしました
https://mayoko.github.io/myGame/
AI はなんとモンテカルロをやっているのでかなり重いです

クラス構成

javascript は private とかなくてガバガバですが 一応クラスがあります(altjs とか使うとそういうのもちゃんとするんですかね?)。
作法的に private method を作りたいときは 関数名の最初に "_" を付けるっぽいです。

で, クラス構成ですが, 以下のようになっています。

  • Game クラス
    • 以下で述べる State クラス, Animation クラスをまとめて動かします
  • State クラス
    • ゲームの論理部分を担当するクラスです(上に動かしたらセルがどう動くーとか)(セルというのは「2」とか「128」とか書いてある一マスのことです)
    • 本当は分けて書いた方が良いと思うのですが, 面倒なのでアニメーションに必要な情報もここで計算しています
  • Animation クラス
    • 下で述べる Cell クラスを用いて, セルが動くとかセルが表れるといった Animation を制御します
  • Cell クラス
    • セル単体のアニメーションをサポートするクラスです
  • GameAI クラス
  • State を受け取って, どういう風に動けば良さそうかを考えるクラスです

以下で各クラスの説明をしていきます

State クラス

主な役割は, 「上/右/下/左に動かしたときに, 各セルがどこに行くか」を計算することです。
これは calcNextState というメソッドて計算しているのですが, まぁこの記事を見ている人なら簡単に実装できると思います。
といいつつ定数倍遅くなりつつ楽に実装できる方針をとったのでちょっと説明します。

  • まず, 上に動かしたときにどういう風に動くかを計算できるようにしましょう。
    • これは, 上の行から順番に上に動かす, というような方針を取れば実装できます。
  • 上に動いた場合さえ計算できれば, 例えば右に動いた場合の計算は, 「board を 3 回時計回りする -> 上に動かす -> board を 1 回時計回りする」というように実装することによって, 上に動かすのを利用して実現することができます。

Animation クラス, Cell クラス

これが一番大変でした。
アニメーションは結局要するに,

  • アニメーション開始からどれくらい時間たったかを計算することによって, 進捗率を求める
  • 進捗率に応じて, 位置なり角度なりを制御する
  • 進捗率が 100% 出ないのであれば, setTimeout なり requestAnimationFrame なりを呼び出して続きをやらせる

ということをやればいいです。

コードにして書くと以下の通りです(適当に書いたので間違ってるかもしれません。また, const に値を入れていないので当然コピペしても動きません)。

// アニメーション開始時間
let start = null;
// アニメーションにかける時間[ms]
const time = 1000;
// 例えば fromX から toX に動かすアニメーションを作りたい
const fromX, toX;
// 動かす対象
const elem;

// アニメーション更新関数
const update = () => {
    if (!start) {
        start = new Date();
    }
    // 進捗率
    let progress = (new Date() - start) / time;
    progress = Math.min(1, progress);
    const x = fromX + (toX - fromX) * progress;
    // 位置指定
    elem.style.left = `${x}px`;
    // まだ進捗率 100% でないなら続き
    if (progress < 1) {
        requestAnimationFrame(update);
    }
};
// アニメーション開始
requestAnimationFrame(update);

これだけ聞くとかなり簡単に聞こえるのですが, 個人的にややこしかったのは, setTimeout なり requestAnimationFrame は, while 文みたいに「一回実行したらアニメーションが終わるまで続きを実行しないで待つ」みたいな関数ではないということです。

これのどこに注意が必要なのかというと, 例えば今回の場合, 4 と 4 が合体して 8 になる, というようなアニメーションをする場合,

  • 2 つの 4 が移動するアニメーションをやる
  • アニメーションが終わったのを確認してから合体して消える片方の 4 を消す
  • 4 を 8 に変化させるアニメーションを入れる

というようにアニメーションを進行させていきたいわけですが,

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 合体して消える要素は削除
removeChild(elem);

というように書いてしまうと, アニメーションをしている間に elem 要素が消えてしまうので, update 関数から「そんな要素ねぇぞオラァ」と怒られてしまいます。

また,

// アニメーション更新関数定義
const update = () => {...};
// アニメーション開始
requestAnimationFrame(update);
// 2 つ目のアニメーション更新関数定義
const update2 = () => {...};
// アニメーション2開始
requestAnimationFrame(update2);

という風に書いてしまうと, 1 つ目のアニメーションが終わる前に 2 つ目のアニメーションが始まるので「オイオイ待ってくれよ」ということになります。

ただ逆に, アニメーションを同時に動かしたいときは, for 文で requestAnimationFrame を発火させておくだけでいいので楽っちゃ楽かもしれないです。
2048 の場合, 複数セルを同時に動かさなければならないことが多々あるので, for 文 requestAnimationFrame 同時発火手法はイケそうな感じがしましたが, 今回はそのような実装方針にしていません(後で説明します)。

で, じゃあどうすれば良いかということなんですが, 主に 3 つ工夫(?) しました。

  • アニメーションされる要素を用いずに, どういうアニメーションがされるのかを前計算しておく
  • アニメーションを連続させるときは, 1 つ目のアニメーションが終了したタイミングで次のアニメーションが発火するように setTimeout でタイミングを測る(これもっとうまくできる方法あったら知りたいです。知っている方いたらお知らせください。)
  • 進捗ごとにどのように要素が動くのか定義する関数(progress を引数にとって要素を動かす関数) と アニメーション更新関数(update 関数) を分ける

それぞれについて説明していくのですが, その前に Animation クラス, Cell クラスがどのようなクラスなのかを説明しておきます。
2048 のアニメーションですが, 大きく分けると「移動」, 「出現」に分けられて, 「出現」はさらに 2 つに分けられます。

  • ランダムにセルが出現するときにあるような, 何もないところからだんだん膨らんで現れるやつ
  • 2 と 2 が合体して 4 が表れるときにあるような, セルが普段の高さ, 幅よりもちょっと膨らんでからもとに戻るやつ
  • Cell クラス
    • アニメーションの進捗率を受け取ると, 「移動」の場合は今セルがどこにいるべきか, 「出現」の場合は今セルがどれくらいの大きさか, を計算してくれる
  • Animation クラス
    • Cell クラスの集合を保持しておく
    • アニメーションするときには, 進捗率を管理しながら, 「移動」, 「出現」を各 Cell にやらせる
    • アニメーション更新関数(update) を呼び出すのはここであって Cell クラスの中でではない
前計算

これはまぁわかりやすいですね。
どういうアニメーションにするかあらかじめ計算しておくことによって, コードが読みやすくなります。
javascript はオブジェクトを参照で受け取るっぽいので, Cell のまま管理しようとすると想定外の Cell がいつの間にか消えていたりしてややこしいです。

発火タイミングを調整

1 個目のアニメーションに 100ms 使うとかわかっている場合には, 2 個目のアニメーションは 1 個目のアニメーションが発火した 110ms 後とかに発火すると良さげですね, というようなことです。setTimeout は呼び出す関数が次にいつ呼び出されるかを指定できるので, 最初の呼び出しだけ setTimout を使って後は requestAnimationFrame を使う, みたいなことをやりました。

javascript のライブラリで anime.js というアニメーションをやってくれるすごいやつがいるっぽいです。
anime.js で連続したアニメーションをやりたい場合は, 1 個目が発火した後何秒後に次のアニメーションを発火させるか, みたいのを指定して連続アニメーションを実現しているようです。
今回のやり方も同じように発火させるタイミングを時間で指定しているので, 結局やったことは anime.js 手法を自分で書いた感じになったのでしょうか(詳しく知らないので想像でしかないですが)。

animejs.com

Animation クラスと Cell クラスで役割を分割

今回は, Cell クラスは「進捗率を受け取ると, それに合わせて二次元位置であったりセルの大きさを調整する」ということを行い, Animation 関数の中でアニメーション更新関数(update)を呼び出すようにしました。
こっちの実装方針の方が, アニメーションが終了したときの処理を柔軟に書きやすいという利点があるような気がします。

例えば, セルの「移動」, 「出現」のアニメーションが終わるまでは, 別の矢印キーが押されても反応しないようにするために, Animation クラスには finish という bool 値があるのですが, これは update 関数内の進捗率が 100% になったら finish を true にする, というような処理を行うことによって簡単にできます。
一方で, Cell の中で update 関数を書くような方式にした場合, 全ての Cell のアニメーションが終わってから finish を true にする, というような処理を書くのが面倒な気がします。
(一つの方法として, ある Cell にのみ finish を参照渡しして, その Cell のアニメーションが終わったら finish = true にする, という方法があると思いますが, あんまりきれいじゃない)

なんか冷静に考えると別にどっちでもいいような気がしてきました, はい。

ACM-ICPC 2017 アジア予選に参加しました

参加しました。しばらく競プロはお別れな気がする。

前日まで

前回のDCCCでなんか言っていたが特に達成していない(9/25 AC)

せっかくなので JAXA エクスカーションに行った


なんかあるのかと思ったけど普通の見学だったのでうん, まぁという感じ
せっかくなので風船飛行機を買った(324 円)
たまに飛行機を飛ばして害悪行為をしておりましたすみません

割とグダグダしながら会場入り

会場も割とグダグダだったけどホイホイしながら練習
まぁここらへんは逆に企業間イベントが頑張ってるんだよなぁとか思った
ddccとかこどふぇすとかのスタッフさんすごい

  • 英字キーボードヤバすぎて vim を使う気を起させなかった
  • gedit で行こうかなぁとか思ったけど最後何気なく使った eclipse が案外優秀だったので eclipse で行くことに

ごはんを目の前にひたすら待たされる作業
早く食べたかったよー

ホテル
OpenGL の勉強しようかと思ったけどそういえば環境は my PC にはなかったのでスプラをやる
丁度ガチアサリをやっていたのでやったけどなかなか難しいね


C帯で 29 キルするな

本番

8:00 頃に起床 AC
風船飛行機をしぼませるストローをなくして邪魔だったのでストローを買った

本番の動き
僕がログインしてる間にどりきゃすに A 問題, 住建に B 問題を読んでもらった
A は dp らしいので書き書き
B は全探索らしいので書き書き
C はどりきゃすが式を生成していたので書き書き
I は住建が解いてくれたので一部書き書き
G はなんか知らんけど解かれてた
ここまでで 2 時間半で, ここからの 2 時間半は,

  • 僕とどりきゃすが E 問題で適当な貪欲をして意味不明をする
  • 住建が F 問題を解こうとしてなんかダメ

で終了。コンテスト時間 3 時間で良かったよ

11 位でした。10 位からなんかいい感じだったので惜しい

解説
ただでさえわからない競プロ解説を英語でやるとどうなるか…

閉会式

一位114514知ってた
sigmaさんが負けたの辛いみたいなツイートしてたけどそれでも続けてるのすごいなぁとか思った

懇親会

思ったより就活イベントっぽかった
たまに就活イベントとか行ってるんですけど、そこであった人が割りといてビックリ
いい生活とレトリバから景品もらえたのでハッピー
バランスボールはとりあえず家に一週間くらいおいて使ってみたいです
あとは知り合いも新しい知り合いも含めて色んな人と話せたので良かったです

mayoko と競プロ お別れの時

実際のところ, 国内予選で終わりかなぁと思っていたんですが, なぜかアジア予選に通ってしまったのでここまで伸びてしまいました。
競プロは楽しいんですけど, 解けないと面白くないのでちゃんと練習したいんですが, 最近は別の娯楽(switch とかね)をやってるし研究室とか別のことが忙しいので, 全然解けなくて面白くないを錬成しているのでまた時間が取れたら戻ってきます。

戻って来れるのかは分かりませんが・・・・・・・・・・・

まとめ

SHIROBAKO はいいぞ

ISUCON 7 final に参加しました

ISUCON 7 final になぞなぞチームで参加しました。
意外に座るだけじゃなかったので良かったです。

チームリーダー(?) が詳しいことを書いている
brookbach.com

競技前



やったこと
  • 二人が構成を頑張っている間に app.py とか game.py とか見て遅そうなところを見つける
    • 僕は完全にのんびり読んでたんですけど, 二人はプロファイル作るのに苦戦していた模様
  • 1 秒先までの未来を見るみたいのが calc_status にあったけど遅いやろって思ってたら実際に遅いらしいので適当に実装
    • test_game.py と言うのがあったので非常にありがたかった
    • test_game.py のテストは通るけどベンチは通らないみたいな感じだったので相談しながら実装して点数上げる(イエーイ)
  • なんかこれが一番やった感あるやつで, あとはいろいろ試したけどベンチ通らなくて悲しいというやつだった
    • 点数上がりそうだなーと思っていたのは, calc_state まわりで前のデータから更新された新しいところだけとってくるってことだけど無理でした
      • 今更ながら, これと Redis に乗り換えるの同時進行でやるのは難しかったのではとか思った
      • データベースは実質グローバル変数だからちょっと変えようと思うだけでもめっちゃコードいじらないといけなくて難しい
へーとか思ったこと

python は型がなくてクソと思ってたけど一応 total_milli_isu : int = 0とかで宣言出来たりするらしい(関数の引数の定義でも似たようなことが出来る)(少し見直した)

  • 3.6 からだった(自分の PC に入っていたのが 3.5 のため)
終わり
  • 去年の反省を生かさずまた大量に食べてしまう
    • おいしいから仕方ないね
    • ケーキ久しぶりに食べた




(解説:僕は web サービスとかサーバーとか全然知らないのに ISUCON に出ている)

模擬地区予選に参加しました

shuriken チーム(僕, 住建, どりきゃす)で参加しました。
jag2017autumn.contest.atcoder.jp

国内予選が初手で僕が早解きする流れだったのでその流れを踏襲

コンテスト

A 問題を見たんだけど, イマイチサンプルの意味がわからず
他の二人が B, C あたりを相談してて話しかけづらい雰囲気だったんだけどわからないのはマズイので聞いてみる->解決
かなりデオクレティアヌス帝だけどまぁなんとか AC

B 問題を住建が読んでたので任せる(エディタ慣れてないのも合わせてかなり時間食ってしまったので僕に実装投げてくれたほうが良かったかも)
その間にどりきゃすと C 問題を見る
ふーん…とか思って 5 分 10 分考えたらわかったので次に行く
E, H が問題文短くてすぐ読めたけど解法はわからず~とか言ってる
その後 F を見て, どうせ全部通れるやろwとか思いながら解法を考えたらなんか浮かぶ
実装めんどくせーとか言いながらもまぁなんとなく実装方針は立つ

B で割と詰まってたのでコーディング変わって C, F を解きにかかる(なんか B はエディタが保存してなかったのが原因だったらしい)

C はまぁあっさりAC
F は途中まで書いたところで出力見たらバグってて, 住建が B 変わりたいとのことだったので印刷して交代
どりきゃすとコードにらめっこして間違い見つける
B 問題 AC

その後 1 WA のち F 問題 AC
僕が F 書いてる間に G 解けるやろと後ろで相談していたらしく, G 実装してあっさり AC

順位表見て, E と H がねらい目だよねという話をしつつもよくわからないので暇
適当にみんなでバラバラに考え始めるけど結局 E 問題を僕とどりきゃすで, H 問題を住建が考える形になった
最終的に解けたのは H なので住建すごい(解説聞いてえぇ…と思ってしまったけどそういうのも出るんですね)

E 問題は 3 回くらい印刷してどりきゃすとにらめっこしてたけど結局解けなくて悲しい
後で結果見たらスターグラフの場合で落ちているらしい

解説

tokoharu さんが全体的に難しい問題を解説してたんだけど, 知らんってのが多くてあんまりわからなかった(すみません)
今回は全体的に短い行数で書けるのが多かったらしい

解散後

計数の人々がめっちゃいたので, 住建と後 4 年メンバーでご飯を食べに行く
計数 3 年生が競プロ部作ってるとかいろいろあるらしくて計数が競プロ学部になってる感ある(頑張ってくれ)

感想

つくばでも頑張ります

DDCC 2017 に参加しました

参加しました。久しぶりに競技プログラミング系イベントに出た感じがしますが楽しかったです。

前日

やざてんさんに誘われて飲み会に行ってきました。


コンテスト前

10:00 くらいに行けばよかったので 30 分くらい前に着けば良いかなぁと思っていたら 8:30 とか 9:00 とかに会場入りしてる人がいてビビった


後最近僕がファンになっているチノちゃん競プロなりきり bot の中の人に会えました。チノちゃんかわいい。
他にも昔なじみの知り合いとか Indeed ツアーで知り合った人とか前日の飲み会で知り合った人とか次々と会いました。

コンテスト中

A, B の 2 完でした。
20 分程度で 2 問解いたので残り 1 時間 40 分座っているだけでした。

山本一成さん, 西尾さん, chokudai さん対談

面白い話が聞けました。
印象に残ったことを書いていく(575)

  • 競技プログラミング AI がいつ超えるのか?
    • 今も論文が出ているらしい
      • 入力, 出力の関係を見てそれに合致するアルゴリズムをひたすら提出するらしい
      • AtCoder レート 1000 程度は出るとか
    • 競技プログラミングはプログラミングの中ではある意味単純(入力, 出力がきれいにフォーマットされている)ので問題文解釈して論理的にそれに答える等価なコードを書いていけば案外早く超えられるのではと
    • そういうことでまだまだ若い人には競プロ以外のチャネルを試してほしい
  • 人間機械学習千田さん
    • (将棋盤面の)学習セットとテストセットを分けて学習セットの評価値を学習しながらテストセットの盤面の評価値を最小二乗法で最小化する(は?)
  • プログラマーは PC に論理を与えるのをやっている
    • プログラム自体は論理を理解していない

DISCO 紹介, 見学

就活性だし聞いておくべきだったのではとか思ったけどあんまり聞いてない
ていうかどこも調子の良いことしか言わないからか, 話を聞く任意の企業が優良企業に見える

懇親会

btk さんとかヘクトさんとかとしゃべる
btk さんに 114514 回競プロやってと言われた

  • のでちょっと自分にしては珍しいことをやった(今いいねしても遅いですよ)

  • kuuso さん初めてお会いした気がする(ありがとうございました)
  • 他にもいろいろな人に会った気がするけど忘れた(ごめん)

何も知らないのに ISUCON 2017 に参加した

チーム「座るだけのコンテストってな~んだ?」で OKeiGo さん, しょラーさんと一緒に ISUCON 2017 に参加しました。

僕がやったのは, チーム名を考えることと, それを実際に実行することだけです。

前日まで

Vagrant で ISUCON の環境を再現できるものがあり, それでホーンとか言ってた
github.com

これ使ってなんか勉強しようとネット資料とか見てたけどみんな難しい言葉使っていてわかりませんと言う感じ

サーバーの概念に多少詳しくなったけど肝心の実装は何もわからない

  • 冷静に考えてお前コード読むことしか能ないんだからもうちょっと app.py とか読んでおけばよかったのにと始まってから思った
  • というかしょラーさんと OKeiGo 君だったら僕いらないだろとチーム組んだ時から思ってた

当日

一番いろいろ勉強できた気がする
他の二人が頑張ってセットアップしてる間にへーとかホーとか言ってた

  • ていうか二人が詳しそうなのでなんか思いついても言いづらいなぁみたいな気持ちはあった
  • ssh でどう接続すれば良いのかもよくわからなかったし, web サービス自体どうやって閲覧するのかもよくわからなかった
    • 理解するのに 30 分くらいかかった

後ほかの二人が slack で話してるのを見てヘーとか言ってた

  • python でやってたんですけど, os.environment.get() ってやると環境変数が取れるらしい
    • それでヘーと思って echo $ISUBATA_DB_HOST とかやってみたけど特に何も起きなくて解せなかった

app.py を読んどけと言われたので読む

  • flask とか言うのが web アプリケーションのフレームワークになってることを初めて知った
  • おそらく ISUCON ではそんなに大事な部分ではなさそうですが, login とか logout ってこうやって実装するんだーみたいのも初めて知った
    • flask.render_template(filename) で filename を渡すとか(GET でよく使う)
    • POST の時には flask.request.form['hoge'] で hoge を受け取るとかしてるっぽいですね
    • flask.session がよくわかってない
      • 複数の人がいるのに flask.session.pop() とかで除外するみたいな感じで良いんだろうか

後まぁ flask でやるときはデコレーションで「ここにアクセスしたときはこういう操作すれば良いよ」というのを書けば良いってのもここで知りました

  • 世の中の人いろいろ考えるなぁっていう

話を聞いていると今回は GET /icons/* を高速化するのが大事っぽかったんですが, しょラーさんの提案していた解法が僕にはよくわからなかった(なんか nginx 使って何かするらしい)

その後僕が見てたのは mysql 周り(見てただけ)

  • まだ見てないメッセージ数を求めるやつは, 各チャンネルごとに合計のメッセージ数を覚えておき, 各ユーザーが各チャンネルのメッセージをいくつ読んだか覚えておけば(メッセージを消すことが出来ないので)求まるよねという話をした
  • GET /fetch のところで, プログラムが sql クエリを何回も呼び出すやつやってて頭悪いな~と思ってたら しょラーさんが解決してた
    • sql でもらった結果を配列として持っておいて, 配列で for 文を回せば OK
      • python 詳しくないので書き方がわからなかった
  • 世の中には slow query というボトルネッククエリを調べられる便利機能があるらしい
    • 使い方イマイチわかってない

その他気になったこ

  • password に salt つけてハッシュ化するってやつ, たまに見るけどそれ意味ある?と思っているのでやる必要性が気になる

感想

世の人々はこんな複雑な web 系プログラミングに詳しくてすごいなーと思いました。

ICPC 国内予選 2017 に参加しました

4 位でめでたい!

開始前

Sleep, 114514, lsplpl, catsatmat の次で 5 位くらい入ればワンチャンあるのでは?とかそれ無理でもドワンゴ賞と NTT 賞が美味しそうとかいう話をする
結構時間余裕を持って会場入りしたので暇
戦略としては僕が基本的にコーダーをやる感じに

本番

問題文は印刷してもらってその間に僕は A と B を解く
A ははい
B はめんどいけどなんとか
A と B 解いてる間に C と D 見てもらってて, C はなんか解けて D は難しいらしいので C は解いてもらって D の相談
「ユーて n*m 小さいし場合分けして行けない?」と聞いて最初えーって言ったけど行けるやんと気づいて C 問題 AC の直後書き始める -> AC
D 解いてる間に E の解法が大体出来ていて, 「書いて」と言われたので書く
バグバグ
バグバグしてる間に F わかったらしいので書いてもらう -> AC(天才か?)
E もなんかバグ取れて AC
予選通過ワンチャンあるんじゃね?という空気になり始める(たしか 4 位くらい)
G もなんか考えられていて, 「右手法っぽくやればいいんじゃない?」という話だったのでじゃあ実装するか〜ということに
バグバグ
実装の思いがこっちに伝わってなかったっぽいのでいろいろ言いながら実装完成させる->AC
G を AC するだいぶ前に catsatmat とかが 7 完してたっぽいので今更かな〜と思ったけど順位表見たら 4 位!
そのまま終わって終了

終了後


みんなお祝いしてくれてとてもうれしい
チームメートのこのツイートなんか心に来る