KLabGames Tech Blog

KLabは、多くのスマートフォン向けゲームを開発・提供しています。 スマートフォン向けゲームの開発と運用は、Webソーシャルゲームと比べて格段に複雑で、またコンシューマゲーム開発とも異なったノウハウが求められる領域もあります。 このブログでは、KLabのゲーム開発・運用の中で培われた様々な技術や挑戦とそのノウハウについて、広く紹介していきます。

KLab Advent Calendar 10日目の記事です。KLab分析基盤チームの高田です。

分析基盤チームでは、社内向けに各種KPIを提供している他、KG SDKのKPIレポートシステムを通じて、パートナー向けにシステムを提供しています。

今回は、先日re:Invent 2016で発表されたばかりのAWSの新サービスAthenaを試してみました。KLabの分析基盤システムでは、すでにRedshiftやEMRを使用していますが、Athenaには、これらを補うような役割(低コストで導入し、アドホックな分析や定型的なレポートの作成をサポートするといった用途)を期待しています。

Athenaとは?

logo

ひとことで言えば、Athenaとは、S3上に置いてあるデータを高速にSQLで集計・分析できるサービスです。内部はPrestoをベースとしつつ、独自の改修をくわえて使用しているようです。Athenaの紹介としては、Amazon Web Serviceブログのこちらの記事も参考になるでしょう。

AWSでは以前より、EMRというサービスでHadoopやPrestoの機能を提供していましたが、Athenaでは自前でクラスタを組む必要なしに、クエリ検索機能を使用できます。なお、料金はクエリ量単位(5TBスキャンあたり$5)で設定されています。検索機能のみを提供するサービス形態や、課金形態はGoogleのBigQueryに似たものになっています。

複数のサービス・システム名が登場して複雑なので、以下に関連するサービスをまとめておきました。

名称 説明 提供者
Hadoop データの分散処理用のフレームワーク。 Apache Software Foundation
Hive Hadoop上で動くクエリエンジン。SQLベースの検索機能を提供。 Apache Software Foundation
Presto Hiveに似たクエリエンジン。Hadoop上でも動作するがそれ以外のデータソースも選択可能。 Facebook
EMR AWS上でHadoop/Prestoなどの分散システムを提供するサービス。 Amazon
Athena Presto相当の検索機能のみを提供。 Amazon

クエリ実行画面を試す

では早速クエリの実行を試してみましょう。sampledb というデータベースが最初から作成されており、クエリの実行をすぐに試すことができます。

athena1

新しいデータベースやテーブルの作成も、Web画面から実行できます。

athena2

データ準備

現実的なユースケースでパフォーマンスを見たいので、自前のデータも準備し、普段の分析業務で使用するようなクエリを投げてみます。

KLabの分析基盤チームの場合、データの多くは、tsv形式でS3上に置かれています。これをそのまま検索対象にできれば理想的なのですが、残念ながら圧縮形式やディレクトリ構成の問題で、何も手をくわえずに検索対象にするということはできませんでした。

※Athenaの検索対象にするためには、ディレクトリ構成に一定のルールが必要です。また、圧縮形式としては、現状Snappy, Zlib, GZIPのみがサポートされているようです(FAQを参照)。

今回は以下の三種類のデータを用意しました。

種別 説明 1日分のファイルサイズ目安(gzip圧縮時)
dau ゲームにアクセスしたユーザー 数百KB
install インストールしたユーザーのリスト 数十KB
locale ユーザーの国情報 数十MB

それぞれ、S3上の以下のようなパスにアップロードしておきます。Athena用にカラム名を除外し、gzip圧縮しましたが、それ以外はごく普通のtsv形式です。データはすべて日別にわかれており、 dt=日付 というパスにアップロードします。それぞれ11月1日から12月5日までのデータをアップロードしてあります。この key=value というパス名は、Athenaにパーティションを認識させるためのルールになります。この形式にのっとらない場合は、手動でパーティションを追加する必要があります。また、パスはテーブルごとにわける必要があります。

s3://--bucket--/athena/dau/dt=2016-12-01/dau_2016-12-01.tsv.gzip
s3://--bucket--/athena/dau/dt=2016-12-02/dau_2016-12-02.tsv.gzip
...
s3://--bucket--/athena/install/dt=2016-12-01/install_2016-12-01.tsv.gzip
...
s3://--bucket--/athena/locale/dt=2016-12-01/locale_2016-12-01.tsv.gzip

テーブル作成

あとは、Athena上でテーブルを作成するだけで、上記のファイルを検索対象とすることができます。

今回は以下のようなテーブルを作成します。テーブルの作成は、Web画面からも実行できるのですが、単純にCREATE TABLE文を実行するだけでも問題ありません。なお、ここでは dt (日付)をパーティションに指定しました。パーティションに指定したカラムは、SQL上で疑似的なカラムとして扱われるため、テーブル本体には同名のカラムを含めることができません。そこでテーブル本体の方の日付カラムには、 dtDontQuery という名前を設定しておきます。

ちなみに、テーブル定義はあれこれ試行錯誤していたのですが、テーブルスキーマがキャッシュされているのか、同名のテーブルをDROPしたあと、定義を修正して再度CREATE TABLEを実行しても、しばらくの間、古い定義が参照されてしまうという問題がありました。

CREATE EXTERNAL TABLE IF NOT EXISTS dau (
  dtDontQuery date,
  player_id string,
  pv int
)
PARTITIONED BY (dt string)
ROW FORMAT SERDE 'org.apache.hadoop.hive.serde2.lazy.LazySimpleSerDe'
WITH SERDEPROPERTIES (
  'serialization.format' = '    ',
  'field.delim' = ' '
) LOCATION 's3://--athena--/athena/dau/'
CREATE EXTERNAL TABLE IF NOT EXISTS install (
  dtDontQuery date,
  player_id string,
  datetime timestamp
)
PARTITIONED BY (dt string)
ROW FORMAT SERDE 'org.apache.hadoop.hive.serde2.lazy.LazySimpleSerDe'
WITH SERDEPROPERTIES (
  'serialization.format' = '    ',
  'field.delim' = ' '
) LOCATION 's3://--athena--/athena/install/'
CREATE EXTERNAL TABLE IF NOT EXISTS locale (
  dtDontQuery date,
  player_id string,
  region string,
  datetime timestamp
)
PARTITIONED BY (dt string)
ROW FORMAT SERDE 'org.apache.hadoop.hive.serde2.lazy.LazySimpleSerDe'
WITH SERDEPROPERTIES (
  'serialization.format' = '    ',
  'field.delim' = ' '
) LOCATION 's3://--athena--/athena/locale/'

S3上のパーティションを認識させるには、各テーブルについて以下のクエリを実行します。

MSCK REPAIR TABLE dau

athena-msck

パーティションが正常に認識されたかどうかは以下のクエリでパーティション一覧を表示することで確認できます。

SHOW PARTITIONS dau

検索

いくつかクエリを実行し、性能を見てみます。残念ながらデータそのものはお見せできないのですが、以下、参考のため、クエリと実行時間を掲載しておきます。現状SQL上で使用できる関数なども、公式ドキュメントに記載がないため、やや試行錯誤が必要でした(ANSI SQLに準拠ということなので、ある程度は検討がつくのですが)。

今回追加したファイルのうち、このlocaleのデータがもっとも巨大です。全体で1.45GBほどあるのですが、単純なCOUNTクエリであれば6秒ほどで返ってきました(スキャン自体は行なっているようです)。

SELECT COUNT(*) FROM locale

(Run time: 6.87 seconds, Data scanned: 1.45GB)

DAUを国別に集計してみます。これもlocaleのファイルが大きいためか、20秒ほどかかりました。

SELECT dau.dt, locale.region, COUNT(*)
FROM dau
JOIN locale
  ON locale.player_id=dau.player_id
     AND locale.dt=DATE('2016-12-05')
WHERE
  dau.dt BETWEEN DATE('2016-12-01') AND DATE('2016-12-05')
GROUP BY dau.dt, region
ORDER BY dau.dt, region

(Run time: 18.45 seconds, Data scanned: 45.54MB)

インストールユーザーの3日後の継続率を集計してみます。数秒です。

SELECT i.dt, COUNT(i.player_id) AS install,
  COUNT(dau3.player_id) AS r3
FROM install AS i
LEFT JOIN (
  SELECT player_id, dt
  FROM dau
  WHERE
    dt BETWEEN DATE_ADD('DAY', 3, DATE('2016-11-01')) AND DATE_ADD('DAY', 3, DATE('2016-11-05'))
) AS dau3
  ON dau3.player_id=i.player_id AND dau3.dt=DATE_ADD('DAY', 3, i.dt)
WHERE
  i.dt BETWEEN DATE('2016-11-01') AND DATE('2016-11-05')
GROUP BY i.dt

(Run time: 3.62 seconds, Data scanned: 3.65MB)

3日連続でログインしているユーザー数を出してみます。Athenaが苦手なクエリなのか、スキャン量が少ない割に1分半もかかっています。

SELECT t.dt, COUNT(*) as cnt FROM
  (SELECT d.dt
     FROM dau AS d
     LEFT JOIN dau AS d2
        ON d.player_id=d2.player_id
          AND d2.dt>=DATE_ADD('DAY', - 2, d.dt) AND d2.dt<d.dt
     WHERE
       d.dt BETWEEN DATE('2016-12-01') AND DATE('2016-12-05')
     GROUP BY d.dt, d.player_id
     HAVING COUNT(d2.dt)=2
  ) t
GROUP BY t.dt

(Run time: 1 minutes 28 seconds, Data scanned: 24.86MB)

こちらはサブクエリを使用するように書き変えることで大きく実行時間が変化しました。RedshiftやBigQueryと同じで、直接テーブルをJOINするのはあまり効率がよくないようです。参考のため、修正後のクエリも掲載しておきます。

SELECT t.dt, COUNT(*) as cnt FROM
  (SELECT d.dt
     FROM dau AS d
     JOIN (SELECT player_id, dt FROM dau
           WHERE
             dt BETWEEN DATE_ADD('DAY', - 2, DATE('2016-12-01'))
               AND DATE('2016-12-05')
          ) AS d2
     ON d2.player_id=d.player_id
       AND d2.dt >= DATE_ADD('DAY', -2, d.dt)
       AND d2.dt < d.dt
     WHERE
       d.dt BETWEEN DATE('2016-12-01') AND DATE('2016-12-05')
     GROUP BY d.dt, d.player_id
     HAVING COUNT(d2.dt)=2
  ) t
GROUP BY t.dt

(Run time: 4.34 seconds, Data scanned: 6.97MB)

以上のように、いくつかクエリの書き方で気をつけるべき点があるようですが、基本的には十分実用的な性能です。

Parquetへの変換

より効率のよいデータの格納方法として、AthenaではApache Parquetのような列志向のフォーマットもサポートされています(列志向フォーマット: データをカラムごとに格納するフォーマット)。Parquetへの変換方法として、公式ドキュメントで紹介されているHiveによる変換を試してみました(参照)。

EMR上でHiveを立ち上げ、S3上のテーブルを読み込ませ、Hive上でテーブルをParquet形式に変換します。

概念図: parquetへの変換

まず以下のようなSQL(HiveQL)スクリプトを用意し、S3上に保存します(DAU以外のテーブルは省略してあります)。なお残念ながらParquet形式はDATE型に対応していないため、ここでは文字列に変換しています。また以下のクエリでは、ダイナミックパーティション(クエリ結果によってパーティションを決定する)を使用しているため、 最初の方にある hive.exec.dynamic.partition の設定が必要となります。

ADD JAR /usr/lib/hive-hcatalog/share/hcatalog/hive-hcatalog-core-1.0.0-amzn-5.jar;
SET hive.exec.dynamic.partition=true;
SET hive.exec.dynamic.partition.mode=nonstrict;

CREATE EXTERNAL TABLE IF NOT EXISTS dau (
  dtDontQuery string,
  player_id string,
  pv int
)
PARTITIONED BY (dt string)
ROW FORMAT SERDE 'org.apache.hadoop.hive.serde2.lazy.LazySimpleSerDe'
WITH SERDEPROPERTIES (
  'serialization.format' = '    ',
  'field.delim' = ' '
) LOCATION 's3://--bucket--/athena/dau/';
MSCK REPAIR TABLE dau;

CREATE EXTERNAL TABLE  p_dau (
  dtDontQuery string,
  player_id string,
  pv int
)
PARTITIONED BY (dt string)
STORED AS PARQUET
LOCATION 's3://--bucket--/athena/parquet/dau/';

INSERT OVERWRITE TABLE p_dau PARTITION (dt) SELECT dtDontQuery, player_id, pv, dt FROM dau where dt BETWEEN '2016-11-01' AND '2016-12-05';

awscliを利用し、Hiveを立ち上げて実行させます。

export REGION=us-east-1
export SAMPLEURI=s3://--bucket--/athena/dau/
export S3BUCKET=--bucket--


aws emr create-cluster --applications Name=Hadoop Name=Hive Name=HCatalog \
--ec2-attributes KeyName=kg-kpi-keypair,InstanceProfile=EMR_EC2_DefaultRole \
--service-role EMR_DefaultRole --release-label emr-4.7.0 \
--instance-type m1.large \
--instance-count 1 --steps Type=HIVE,Name="Convert to Parquet",\
ActionOnFailure=CONTINUE,ActionOnFailure=TERMINATE_CLUSTER,Args=[-f,\
s3://path/to/hive-script.q ,-hiveconf,INPUT=${SAMPLEURI},-hiveconf,OUTPUT=s3://${S3BUCKET}/athena/parquet,-hiveconf,REGION=${REGION}] \
--region ${REGION} --auto-terminate

ジョブの実行には1時間程度かかりました。ジョブの完了後S3を見ると、確かにファイルが作られています。つづけてAthena側でもCREATE TABLEを実行し、作成されたParquetファイルを認識させます。

CREATE EXTERNAL TABLE  p_dau (
  dtDontQuery string,
  player_id string,
  pv int
)
PARTITIONED BY (dt date)
STORED AS PARQUET
LOCATION 's3://--bucket--/athena/parquet/dau/';
MSCK REPAIR TABLE p_dau

Parquet形式の場合、単純なカウントは、ファイルスキャンの必要がなくなるようです。

SELECT COUNT(*) FROM p_locale;

(Run time: 2.95 seconds, Data scanned: 0KB)

SELECT dt, COUNT(*) FROM p_dau
WHERE
  dt>=DATE('2016-12-01')
GROUP BY dt
ORDER BY dt

(Run time: 0.99 seconds, Data scanned: 0KB)

ただし試した範囲では、スキャン量が増えてしまうこともありました。実行時間もものによっては改善しましたが、大きな変化が見られないケースが多いようです。以下、実行結果の比較をまとめておきます。

形式 csv.gz実行時間 csv.gzスキャン量 Parquet実行時間 Parquetスキャン量
localeのCOUNT 6.87s 1.45GB 2.95s 0KB
国別DAU 18.45s 45.54MB 9.52s 300.03MB
3日後継続率 3.62s 3.65MB 2.69s 12.33MB
3日連続ログイン(修正前) 1m28s 24.86MB 1m32s 86.49MB
3日連続ログイン(修正後) 4.34s 6.97MB 3.28s 24.39MB

まとめ

Athenaを使用し、データ分析基盤で日常的に使用するような検索を試してみました。

以下は、触ってみた上での個人的な感想です。

  • リリース直後ということもあり、サービスとしての完成度は、まだこれからの印象。ドキュメントなどはまだ不足しているように感じられた。
  • 今後はAPIからの操作や、データインポート方法のバリエーションが増えることを期待したい。
  • 一方、S3にテキストファイルを置くだけで使用できる気軽さや、値段の安さは魅力的。
  • 性能も、定型レポートやアドホックな調査用途を想定すれば、十分実用的なもの。

KG SDKについて

KG SDKでは、データ分析基盤システムによるKPIレポートへの対応も行なっています。KG SDKの概要についてはこちら を、お問い合わせにつきましてはこちら をご覧下さい。

(本稿はKLab Advent Calendar 2016 の9日目の記事になります)

こんにちは, @mecha_g3 です.

ISUCON6 の優勝賞金で新型の MacBookPro を購入しました. キーボードの打ち心地にどうも慣れられなかったり, USB-C の周辺機器がたくさん増えたりしていますが, 概ね満足しています.

格ゲーの攻略記事のようなタイトルですが, この1ヶ月ほど CODE VS for STUDENT というプログラミングコンテストに注力していたので, 今日はそれについて書きたいと思います.

CODE VS とは

CODE VS とは, お題となるゲームの, 最強のAIを開発するプログラミングコンテストです.

CODE VS for STUDENT 公式サイト https://student.codevs.jp

主催はチームラボさんとキャリフルさんで, KLabはスポンサーをさせて頂いてます.

決勝イベントが明日 12/10(土) に行われます. 決勝イベントでは, 予選で勝ち上がった学生 16 名 (Normalコース, Hardコース各8名) が対戦します.

また, 僕は学生を除いたランキングで 1 位だったので, エキシビジョンマッチに招待していただきました. 優勝した学生のAIと, 僕のAIが対戦します.

生放送もされるようなので, 是非観てください!

この記事の後半は, コンテストに参加していない方は興味がない内容になっているかもしれないので, 最初に宣伝しておきます.

ゲームのルール

今回のゲームは, CODEVS 2.0 のリメイク版で, 対戦形式の落ちものパズルです.

ルールの詳細は以下の PDF に記されています. https://student.codevs.jp/assets/files/rule.pdf

ゲームイメージ

ゲームのリプレイ動画を撮影しました. 動画を見ると, ルールのイメージを掴みやすいです.

ブロック

1~9 の数字が書かれた 1x1 のブロックです.

パック

3x3 の領域にブロックが 3~4 個入っています. ゲーム開始時に全300ターン分のパックが与えられます.

フィールド

幅10, 高さ16 のフィールドで, ここにパックを投下していきます.

消滅と連鎖

フィールド上で 縦, 横, 斜めのブロックの数字の和が 10 になった所が消えます. 消えたブロックの上にブロックが積まれていた場合, 上のブロックが落下します. ブロックが消えた事により上のブロックが落下し, 落下したブロックが消える. という動作を繰り返し, 連鎖が発生します.

得点

連鎖を行うと、以下の得点計算式に従って得点を得ることができます.

score = ∑ floor(1.3 ^ i) * floor(Ei / 2)
i: 連鎖数
Ei: 消滅カウント(合計が 10 になったブロックの数)

連鎖数に応じて指数的にスコアが上昇するので, 連鎖数が一番大事です. 連鎖の最後 (連鎖尾) の消滅カウントでスコアが数倍変わってくるので, 消滅カウントも無視できない存在です.

お邪魔ブロック

得られた得点に応じて, 相手にお邪魔ストックが加算されます. お邪魔ストックがある場合, パックの空いている領域にお邪魔ブロック (消すことができないブロック) が挿入されます.

自分にお邪魔ストックがある場合に得点を得た場合, お邪魔ストックが消費 (相殺) されます.

勝敗判定

パックがフィールドの外に溢れたり, 思考の制限時間を過ぎると敗北になります. 思考時間は 1 手最大 20 秒, 1 ゲームの持ち時間は 180 秒です.

基本的な考察

AIのプログラムは, 標準入力でゲームの情報を取得し, 各ターンにおいてパックを何回転させてどこに投下するかを標準出力に出力します.

全ターンのパックは事前に分かるので, 落下と連鎖のシミュレーションを行い, 大連鎖を作ることを目標に探索するプログラムを作る事になります.

長いターン使って大連鎖を作ろうとしていると, 相手が先に連鎖を発火し, 邪魔ブロックが降って来て大連鎖を発火できずに負けてしまいます.

逆に, 短いターンで連鎖を作っていると低いスコアになってしまい, 相手に邪魔ブロックが大して降らないため, 相手は連鎖を伸ばすことができてしまいます.

そこそこ短いターンで出来るだけ大きな連鎖を作る探索が, このゲームで一番大事なポイントです.

ここからは, 僕がこの探索部分をどう改良していったかについて掘り下げていきます.

アプローチ

落とし方は 1ターンあたり 48 通りあるので, 4 ターン先(48^4 = 5308416) まで調べるのに数秒かかりそうです.

実際には有効な落とし方はもう少し少ないですが, 全探索だと 5, 6 ターンが限界だと思います.

相手のフィールドを埋め尽くす程の邪魔ブロックを降らせるためには, 16 ~ 20 連鎖程度必要で, そこから考えると 20 ターン程度必要です.

このような探索の問題では, 評価関数を作り, 各深さ毎に評価値の高い上位 K個 を残すことを繰り返すビームサーチという手法がよく使われます. (K をビーム幅と呼びます)

もちろん厳密な解は得られませんが, 適切な評価関数が設定できれば, 短い時間でそこそこ良い解を得ることができます.

僕は最初ビームサーチで実装していましたが, 今回の問題では時間制限がシビアだったので, 時間調整のしやすいビームサーチの亜種である chokudaiサーチを採用しました.

ベンチマーク

探索の改良を試したり, 評価関数を調整した結果, それが良くなったか悪くなったかを比較できるようにする必要があります.

今回僕は, 公式クライアントから 300 ゲームの入力ファイルを抽出し, 各入力で 20 ターン先まで探索し, できた連鎖のスコアの平均値を見て調整しました.

1 回 15 秒かけて探索するので 1 時間半かかってしまいますが, Google Compute Engine で 16 コアのマシンを借りて並列で走らせる事で 5 分程で計測することができるようになりました.

GCE 上に Jenkins をインストールしたプリエンプティブインスタンスを用意し, ベンチマークをかけたい時だけ立ち上げて実行, 終わったら個人的に使っている slack に結果を通知し, インスタンスを停止する. という運用で使っていました. 今回 CODE VS のために使った金額は 400 円程度でした.

slackへの通知イメージ

評価関数

「連鎖数が大きくなるようにしたい」というのはどういう評価関数にしたら良いのか悩みどころですが, 評価関数の中で実際に連鎖を起こしてみて何連鎖したのかを見るのが簡単です.

各列に対して 1-9 のブロックを落とすシミュレーションをしてみると, 何連鎖する盤面なのかを正確に見積もることができます.

ただ, 1 状態を評価するのに 90 回もシミュレーションをするのはとても無駄が多く遅いので, ある程度サボらないといけません.

僕の場合は, フィールドを広く使って, 左端から右端(あるいは右端から左端) に向かって連鎖を伝搬させていくような積み上げ方を見つけて欲しかったので, 発火点を左端か右端に固定しました.

最初の評価関数は

200 * 左端の列に 4 を落としたときに発生するスコア + 連鎖前のブロック数

でした. すごく雑ですが, わりと強くて最初の 1 週間程度 1 位を維持していました.

ここから, ベンチマークの結果を見ながら評価関数を調整していきました.

最終的には

ランダム(0.0 ~ 1.0)
+ 100000 * 連鎖数
+ 1000 * 連鎖前のブロック数
+ 10 * 連鎖尾の消滅カウント
- 100 * 連鎖あたりの平均消滅ブロック数
- 1 * 連鎖後に残っているブロック数

としました.

お邪魔ブロックが混入してきた場合は発火に使うブロックを 1-9 で試すようにしましたが, 他は同じです.

各パラメータの重みは比較の優先度を決めているだけです.

ランダム

連鎖数が増えるまでの盤面は優劣をうまく付けれないので, 同じスコアが並びやすいです.

同じスコアが並んだ場合, 特定の順序 (探索キューに入れた順など) で偏りが出てしまうので, これを分散させる目的で入れています.

連鎖数

発火目標ターンのパックをフィールドの端に落とした際に発生する連鎖数です.

この方法で評価した場合, 発火点は固定なので, 連鎖尾を伸ばしていくような探索になります.

スコアをそのまま評価関数にしてしまうと, 連鎖数を伸ばすよりも同時消し数を増やしてしまうほうが良いと評価してしまうことになるので, 最終的に連鎖が伸びにくくなってしまいます.

連鎖前のブロック数

フィールド中に存在する, お邪魔ブロックを除いた 1-9 のブロックの数です.

連鎖を積み上げていく途中で, 無駄に消してしまうとそれだけでもったいないので, ブロック数が多い方が良い状態としました.

連鎖尾の消滅カウント

連鎖尾も一応評価したいのですが, それよりも連鎖数を伸ばして欲しいので評価値としてはかなり優先度を低くしてあります. 気持ちです.

連鎖あたりの平均消滅ブロック数

連鎖で消えたブロック数 / (連鎖数+1) で計算しています.

限られた数のブロックで大きな連鎖を作って欲しいので, 同時消しが多いのは無駄です. 連鎖あたりの平均消滅ブロック数が少ないほうが良い状態としました.

連鎖後に残っているブロック数

8 や 9 といった大きい数字のブロックは 1 や 2 が来ないと消えません. 一方 1 や 2 は他の数字のブロックとも消えます. 連鎖が終わった後で 8 や 9 が残りやすく, これが実質的にお邪魔ブロックになって次回連鎖のスコアが下がってしまう現象が見られたのでこれを入れました.

高速化

速い方がたくさんの盤面を探索できるので, 制限時間内に良い連鎖を見つけやすいです.

テストの作成

シミュレータのテストがあると安心してリファクタリングや高速化に着手できます.

今回のルールでは, CODEVS のクライアントのリバースエンジニアリングは禁止されていませんでした.

クライアントの jar をライブラリとしてインポートした Java プロジェクトを作る一般的なテクを用いて, ログファイルから入出力を抽出するプログラムを作りました.

オンライン対戦のログファイルを大量に用意し, そこから入出力を作ってテストケースとしました.

評価用の落とし方の固定

ある程度探索が進むと, 発火に使うパックの落とし方はほぼ決まってしまうので, 評価関数の中で色々な落とし方を試して評価するのは無駄が多いです. なので, 4 連鎖以上が発生した場合は, 次から評価関数内での連鎖数の評価に使うパックを固定するようにしました.

精度は落ちますが, かなり無駄が省けるのでスコアは上がりました.

同一盤面の除去

高速化とは少し違う話ですが, 一般的に探索の途中で同じ盤面を 2 回探索しないようにするのは多くの場合必須な処理です. これを同一盤面の除去と呼んでいます.

今回はゲームの性質上, 完全におなじフィールドは現れにくいので効果は薄いですが, 探索中のフィールドをビジュアライズしてみると, 少なからず現れていたので除去を行いました.

フィールドのハッシュ値を計算し, 探索済のハッシュ値を保持しておきます. 同じハッシュ値のフィールドが現れた場合, 処理をスキップします.

探索のキューに入れるタイミングではなく, キューから取り出すタイミングで判定することでほとんどコストをかけずに除去することができます.

同一盤面を除去することで, 多少ですが無駄な探索を減らす事ができました.

落下処理の高速化

予選の対戦サーバは Xeon E5-2670 v2 だったのですが, 決勝参加者向けに提供された環境は Xeon E5-2666 v3 でした. (おそらく c4.large)

調べた所 v3 では Haswell 世代の命令が使えます.

Haswell から使える命令に PEXT (Parallel bits extract) という命令があります. これは値 val と ビットマスク mask を入力し, val のビット列の中から mask 指定したビットを抽出し, それを下位ビットに寄せたビット列を作る命令です.

さて, ブロックの数字は 0~11 (お邪魔ブロックは11で表される) なので 4bit あれば表現でき, フィールドは幅10 高さ16なので, 64bit 整数 10 個で表現することができます.

このようにフィールドを表現すると, PEXT を消去が行われた列に対して使うだけで落下処理が実装できます.

// erased_y_mask := 消えたブロックの位置が 1111 となるようなビットマスク
// m_[x] := 1列を表す uint64_t 型の変数
m_[x] = _pext_u64(m_[x], ~erased_y_mask);

落下処理のために生まれたかのような命令ですね.

消去処理の高速化

消去処理では, フィールド中にある隣接したブロックの数字の和が 10 になる場所を探さなければなりません.

和が 10 になるかどうかの計算は, しゃくとり法というテクニックを使うことで, 各列に対して 1 度走査するだけで行うことができます.

あるブロックが落下した結果, そのブロックに隣接したブロックの数字の和が 10 になることで消去が発生するので, 落下が発生していない領域は調べる必要がありません.

落下が発生した行, 列と, それに対応する斜めの行を記録しておき, 消去が発生しえない範囲に対しては消去判定を行わないようにしました.

もう少し具体的に説明すると, あるブロックが落下し (x, y) で止まったとしたとき, 以下のビットマスクをつくります.

x_mask |= 1 << x
y_mask |= 1 << y
z_mask |= 1 << (x + y)
w_mask |= 1 << (9 - x + y)

x_mask, y_mask はそれぞれ縦消し, 横消しが発生する可能性のある列を表します. z_mask, w_mask はそれぞれ左上から右下, 左下から右上に向かっての斜め消しが発生する可能性のある列を表します.

ビットが立っている縦, 横, 斜めだけを調べ, さらに横と斜めは x_mask によって調べる範囲を絞ることができます.

これらの評価関数の調整や高速化により, 20 ターン発火での平均得点は 400 点程度から 730 点程度まで上がりました.

また, 20 ターン発火では火力不足で負けてしまう事があったので, 最終的には 22 ターン発火にしました. 22 ターンでは平均 1070 点程になりました.

今夜勝ちたい実装

エキシビジョンマッチ向けに実装した勝ちたいだけのちょっとズルい実装です.

ルール的に禁止していないことを確認した上で実装しています.

相手の思考時間を使う

ゲーム開始直後の 1 ターン目で 22 ターン先まで探索して落とし方をキューに入れておき, その後は邪魔ブロックが降ってこない限り, キュー入れた落とし方を再生するような実装になっています.

相手が 1 ターンあたり 1 秒つかって探索してくるタイプの場合, 20 秒程 CPU が暇することになります.

なので, キューの内容を再生中も裏で探索を継続しておき, よりよい連鎖が見つかったら途中で乗り換えるという実装をしました.

相手に合わせて発火ターン数を調整する

十分にダメージが与えられる量のお邪魔ブロックを送ることができるなら, 先に発火したほうが勝ちやすいルールになっているように思います. なので, 対戦時のログをファイルに記録しておき, 以下のルールに従って初回攻撃のターンを調整する機能を実装しました.

前回の対戦で勝利した場合

  • 前回の初回攻撃のターンを使用する

前回の対戦で敗北した場合

  • 相手の方が先に初回攻撃を行っていたら, 相手の初回攻撃ターンでこちらも初回攻撃を行う
  • 自分の方が先に初回攻撃を行っていたら, 初回攻撃ターンを +1

ボツネタ

考えたけど上手く行かなかった事, 実装できなかったことなどです.

発火点を成長させる

連鎖を組んでいく際に, 発火点を成長させるのと, 連鎖尾を成長させるのでどちらが強いのでしょうか.

当たり前のことですが, 上から落下させたブロックは, 下から上に積み上がっていきます.

発火点を固定し, 連鎖尾を成長させる場合, 発火点は必然的にフィールドの下の方になってしまいます. フィールドの下の方でブロックを消すと, 上に乗っているたくさんのブロックが落下し, 多くのブロックがズレることになります. たくさんのブロックズレるということは, たくさんのブロックが消える可能性があるわけですが, 連鎖数を稼ぎたいので, 同時消しではなく 2, 3 個ずつ消えて欲しいです. 一度ズレたけど消えなかったブロックは, 今後同様のズレの状態になったとしても消えません.

この消えないズレの組み合わせが徐々に連鎖の成長を制限するため, 連鎖尾を成長させる方針はある程度で頭打ちになります.

発火点を成長させていくと, 発火点が上になるためこの制限を受けづらくなり, フィールド全体を使って連鎖を作ることができます.

ズレの理論に関しては, CODE VS 2.0 の colun さんの説明がわかりやすいです.

また, 連鎖尾の同時消しはスコアにそこそこ大きな影響を与えます. 発火点を伸ばす場合, 連鎖尾の同時消しを作った後に発火点を伸ばすことができるので, 高いスコアを取りやすいと考えられます.

つまり, 発火点を成長させる方針は, 以下のようなメリットがあります.

  • フィールド全体を使って大連鎖を作ることができる
  • 連鎖尾の同時消しを作ることができる

一方で, 連鎖尾を伸ばす連鎖は, 以下のようなメリットがあります.

  • 少ないブロックで柔軟な連鎖を組みやすい
  • 発火点を固定することで評価が高速にできる
  • 邪魔ブロックが降ってきても発火点さえ潰れなければ連鎖は残る

CODE VS 2.0 予選では発火点を成長させる連鎖が強かったのですが, 今回の CODEVS for STUDENT では, スコアに対して相手に送る邪魔ブロックの数が多く, 素早く連鎖を作ることが大事だったため, 連鎖尾を伸ばす方針にしました.

マルチスレッド化

CPU を使い切るために, 探索をマルチスレッドで動かす実装を行いました.

できるだけロック時間が減るように探索の仕方を工夫し, 手元の PC では 2 スレッドにした際に約 2 倍探索できるようになりました.

しかし, 決勝の環境はハイパースレッディングの 2CPU だったので, 1 スレッドと比べて 1.2 倍程度にしかなりませんでした.

プログラムが複雑になってしまったのと, 探索順序が実行するたびに微妙に変わってしまい, 他のチューニングがやりにくくなってしまったので破棄しました.

ベクトル演算による高速化

連鎖のシミュレーションのうち, 一番ボトルネックになるのは, 加算や減算をたくさんして部分和が 10 になるところを探す消去判定です.

加算や減算をたくさんするので, ベクトル演算を使いまとめて演算を行うことで高速化できるはずだと考えて, 3 日ほど AVX2 の関数の使い方を覚えベクトル演算版のシミュレータを書きました.

消去判定のしゃくとり法において, 10 を超えた部分に関して戻って減算をする部分でどうしても演算回数を減らすことができず, 影響範囲のあるところだけ調べるナイーブなしゃくとり法に比べ, 1/3 程度の速度しか出せませんでした.

もっとベクトル演算に慣れて, ベクトル演算しやすいアルゴリズムを思いついたら速くなるかもしれませんが, 今回はあきらめました.

評価関数の自動調整

各評価パラメータの重みが, 比較優先度を決めているだけになってしまいました.

ブロックの位置関係など, もう少しパラメータを増やし, 重みを機械学習的な手法での自動調整に挑戦してみたかったです.

僕が今夜勝ちたいだけの実装をしている間に, 決勝に出場する piroz さんはこの自動調整に挑戦していたらしく, とても尊敬しています.

結果的にうまく調整できなかったようですが, コンテストを通しての成長という観点で僕は完全に負けています.

pirozさんの記事

ソースコード

エキシビジョン提出時のソースコードを公開します.

後に気づいたバグがそのままだったり, 人に読ませるつもりのない思考ログやコミットログが残っていますが, コンテスト参加時のリポジトリをそのまま公開します.

https://bitbucket.org/mecha_g3/codevsfs/src

まとめ

明日は CODEVS for STUDENT の決勝イベントが行われます. エキシビジョンマッチで僕の今夜勝ちたいAIが優勝者と対戦します.

生放送是非観てください!

2017年は機械学習勉強するぞ!!!!


@mecha_g3

KLab Advent Calendar 8日目の記事です。 こんにちは knsh14 です。

KLabではUnityを使って iOS、Android の端末で遊べるようなゲームを開発し、提供しています。 その一方で、それら以外の環境でも遊べるゲームが作れないかということで常に技術検証を行っています。 最近では 「ユニティちゃんのホームランスタジアム」 を Apple TV で提供したりしています。(紹介記事)

その活動の一環として、今回はブラウザで快適に動作する 3D のゲームを作るべく、Unity ではないゲームエンジンを使って開発したのでその紹介をしようと思います。

なぜUnityを使わなかったのか?

ブラウザ動作するためのゲームを開発するにあたって、幾つかの制約がありました。

  1. モバイル、PC のブラウザで動作すること
  2. 容量が小さい(理想は 3MB 以下におさまる)こと

僕らが普段使い慣れている Unity でも WebGL ビルドができ、PC やモバイルのブラウザで遊ぶことができます。ですが、試しに「ユニティちゃんのホームランスタジアム」をビルドしてみたところ、20MB 以上の容量になってしまいました。 これではとてもリリースできないので、Unity を使う選択肢を諦め、別のエンジンを使う道を探し始めました。

色々調べた結果、PlayCanvas というゲームエンジンが海外での利用実績などもあり良さそうだという結論になったので実際に試してみました。

PlayCanvasってなに?

  • 公式サイト
  • WebGL で動作することを主な目的としたゲームエンジンです
    • iOS で動作するように吐き出されるオプションもあります
  • その為吐き出されたゲームのサイズが最小で 10KB 程度と非常に軽いのが特徴です
  • 使用する言語は Javascript です
  • ゲームエンジンが Github で公開されているので、Unity と異なり動作をかなり細かいところまで追いかけることができます
  • エディタ上でチャットすることができ、お互いがその場にいなくてもペアプロのようにして開発することができます。

実際の開発画面

オブジェクトなどをいじるエディタ画面はこのような感じです。

シーンエディタ

だいぶUnityに近い感じで操作できます。

コードエディタ

Ace Editor を利用した感じのエディタになっているのでシンタックスハイライトもありますし、あまり使いにくいことはなさそうです。 このスクリーンショットだとわかりにくいですが、多少のコード補完もしてくれます。

実際にゲームを作ってみる

公式チュートリアル からタップでリフティングして落とさないようにするゲームを作ってみると一通りの使い方などがわかると思います。

PlayCanvas のメリット

開発環境のセットアップが要らない

ブラウザさえあればどこでも開発できるので便利です。

エディタ上で複数バージョンのプロダクトを管理できる

プロダクトを公開するときは、エディタ上から簡単に世界に公開することができます。 また複数バージョンをスタンバイさせておくことができるので、バグが有った場合にも簡単に前のものに差し戻すことができます。

Chrome でデバッグができる

Google Chromeは開発者ツールを使うことでかなり高機能なデバッグができます。 ブレークポイントをはって処理を止めながらデバッグすることができるのはもちろんですし、プロファイラで時間がかかっている処理を調べながら開発することができるので、初期からパフォーマンスを意識しながら開発することができます。

苦労話

PlayCanvas 上でバージョン管理できなかった

PlayCanvas からパブリッシュした成果物は PlayCanvas 上で一覧でき、昔のものを復活させることができます。 ですが、プロジェクトの状態は復活してくれないので、リファクタする時にかなり覚悟が必要でした。 Githubなどとコードを連携する方法 もありますが、Legacy なシステムなのでいつなくなるかわからないのが現状です。 Git でコミットするように成果物を Download しておいて Github で管理するか、Google Drive などに置いておくのが鉄則になりそうです。 どっちの方法でもシーンの状態を戻すことができないのでいい方法を模索中です。

なぜかありえない場所で衝突イベントが走る

物体を動かすために毎フレーム pc.Entity.setLocalPosition() で物体を動かしていました。 ですが、ある日物体が何もない場所でいきなり衝突イベントが走るバグに悩まされていました。 物理演算に任せて動いている場合は何事もないのですが、setLocalPosition() で物を移動させた後おかしくなることがわかりました。

いろいろ試した結果、pc.Entity.setLocalPosition() では Entitypc.Model は移動しますが、 rigidbody の位置が移動しないことが原因でした。

rigidbody がついた Entity を動かすときは

Sample.prototype.move = function(x, y, z) {
  this.entity.setLocalPosition(x, y, z);
  this.entity.rigidbody.teleport(x, y, z);
};

というメソッドを生やしてこれを使うほうが良さそうです。

まとめ

今回は Unity ではないゲームエンジンで WebGL ゲームを開発してみました。 PlayCanvas はどちらかと言うと個人でささっとプロトタイプを作ってすぐに見せるような場合に非常に便利なのではないかと思いました。 大人数で高品質なゲームを作るには Unity 少人数でとにかくスピード感を重視するような開発では PlayCanvas というように状況に応じて使い分けていけたらと思います。

↑このページのトップヘ