AWS Step Functionsでライフゲームを作る #AWSLambda

AWS & Game Advent Calendar 2020の5日目の記事です。

イントロダクション

振り返ってみると、今年も様々な出来事がありました。

COVID-19にまつわるニュースはいくつもありますが、2020/04/11にジョン・ホートン・コンウェイ氏が亡くなったことは大きな話題となりました。
https://www.princeton.edu/news/2020/04/14/mathematician-john-horton-conway-magical-genius-known-inventing-game-life-dies-age

コンウェイ氏は様々な業績のある数学者ですが、中でもライフゲーム（Conwey’s Game of Life）を考案したというものが最も有名でしょう。ライフゲームは状態遷移がキモですが、本記事ではAWS Step Functionsを使って状態を扱うと便利では？と思い試してみました。

ライフゲームって？

ライフゲームは、格子状に区切られた盤面の中にセル（細胞）を配置し、周囲の状態によって生死を繰り返す様を眺めるゲームです。プレイヤーができることは初期配置を決めるだけです。

……これだけでは、果たして何が面白いのか分かりませんので、未プレイの方は下記動画などをご覧になりイメージを掴んでください。初期配置を工夫することにより、様々な動きが出てきます。

何も考えずに配置すると全滅してしまうので、ルールを把握し、同じ状態を繰り返すパターンや移動してゆくパターンを駆使し、面白い図形を作るのがキモです。各セル（1マス）が従うルールは次のようになっています（隣接は周囲8マスです）。

死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

引用: https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0

例として、5x5の盤面で中央に1セルを置いた場合

.....
.....
..x..
.....
.....

ルール3により、次の世代（状態遷移）では死滅してしまいます。

.....
.....
..x..
.....
.....

逆に沢山配置すると

.....
.xxx.
.xxx.
.xxx.
.....

中心の4つのセルはルール4により死滅、周囲はルール1,2によりそのままです。また、外側にルール1により生成されます。

..x..
.x.x.
x...x
.x.x.
..x..

さらに、ルール1が適用され内側に生成され

..x..
.xxx.
xx.xx
.xxx.
..x..

また死亡したり生成され、次のようになります。

.xxx.
x...x
x...x
x...x
.xxx.

このように状態が変化してゆき、小さい盤面では全てのセルが死亡することも多いのですが、中には膠着するパターンがあります。簡単な例では2x2の四角はずっとこのままですし、

....
.xx.
.xx.
....

1x3の線は

.....
.xxx.
.....

横向きと縦向きを交互に繰り返します。

..x..
..x..
..x..

このように、よく知られたパターンを利用すると狙った動きが作りやすくなります。ブラウザ上で実行できるサイトもありますので、色々な配置を試してみてください。
http://math.shinshu-u.ac.jp/~hanaki/lifegame/

ライフゲームは実装が簡単で動きが面白いので、GUIプログラミングの題材にはもってこいです。情報系の大学であれば、授業でやった方も多いのではないでしょうか。

ゲーム性を出す

そんな楽しいライフゲームですが、普通に作っても世にあるライフゲームと比べ新規性がありません。そこで、（面白いかどうかはさておき）初期状態の自由度を下げて、一定回数以内に全滅したら負け、というシステムにしてみます。

具体的には、次のような手順に添います。

プレイヤーは文字列を与える
サーバーは受け取った文字列を使って初期状態を与える
100回世代を繰り返す
最終的に全滅したかを判定し、プレイヤーに結果を返す
プレイヤーは結果を受け取って何か反応する

設計

ここでは、どのように実装を行うかの設計を行います。

盤面の表現

ライフゲームを行う上で必要な状態は、盤面内の各座標でセルが生きているか死んでいるか、のみです。次の盤面で各セルがどうなっているかは、その前の盤面から一意に定まります。

どのようにプログラム上で盤面を表現するかですが、そのままの文字列として渡すのはメモリがもったいないです。ここでは死んでいるセルを0、生きているセルを1とみなしたビット列をhexにしたものを使ってみましょう。

例えば、次のような4x4の盤面を考えます。

...x
x..x
xxx.
....

これを0/1にエンコードすると次のようになり、

さらにhexにすると、最終的に 19d0 という形で表現ができます。

これにより比較的コンパクトに扱うことができます。特性に応じて最適な表現形式は変わります（同じ状態のセルが多いならランレングス圧縮するなど）ので、実装する際は色々試してみましょう。

初期状態の決定

手順に「サーバーは受け取った文字列を使って初期状態を与える」とありますが、ここも先ほどの表現を使うと簡単です。固定長の長さを吐くハッシュ関数を使って入力文字列を変換してあげるだけで初期状態を作ることができます。

利用するハッシュ関数によって盤面のサイズが異なりますが、今回はsha256を使って256bitを生み出し、それを16x16の盤面として利用してみましょう。

実装

実装方法は様々ありますが、今回はAWS Step Functionsで2-4の手順を遷移させます。Step Functionsは、サーバーレスなオーケストレーターです。つまり、他のサービスによる実行を制御し、状態遷移を実現する処理をサーバーを意識せずに作ることができます。今回は、それぞれの処理はAWS Lambdaで作成し、それをStep Functionsで組み合わせることにしましょう。

規模が小さいうちはLambdaやStep Functionsを使う利点が出てきませんが、将来的な拡張として、次のようなことが行いやすくなります。

巨大な盤面を扱う
- 1つのPCでは扱えないサイズの盤面でも、スケールアウトして扱うことが容易になります。盤面を格子状に分割し、それぞれをLambdaで処理し、結果はAmazon Simple Storage Service (S3) に配置し、全体の状態はStep Functionsで管理します。Map-Reduce的な処理ですね。
長期に渡って実行する
- Step Functionsの標準ワークフロー（別にExpressワークフローがあります）を使うと、最長1年（長い！）の実行が可能です。ただしイベント数は25,000がクオータとして設定されていますので、遷移が多い場合は別の実行を作り直すなどの工夫が必要です。
実行ログの自動的な記録
- デフォルト設定でもアプリケーション側の標準出力が保持されます。後々のトラブルシューティングに役立ちます。

なお、サービスの詳細な説明は省きますので、興味のある方は実際にいじってみてください。

では、個別のLambdaの処理を見てゆきましょう。各処理をコンポーネントとして作り、それをStep Functionsで組み合わせて実現します。

sha256で変換する

初期状態を決めるための文字列は、 { 'initial': 'hoge' } という形で受け取ると決めました

const crypto = require('crypto');

exports.handler = async (event) => {
    const initial = event['initial'];
    const hashResult = crypto.createHash("sha256").update(initial).digest("hex");

    return hashResult;
};

簡単ですね。

世代を進める

ルールに基づいて各セルを計算し、次の状態の盤面を作成します。ここでは1状態だけ進める関数を作ります。入出力のため、hexから盤面に戻し、再度hexにする処理があります。
なお、盤面外は生存できない領域としています。


const encode = (digit, hex) => {
    const hexArray = hex.split('');
    return hexArray.map(h => {
        const bin = Number('0x' + h).toString(2);
        return ('0'.repeat(4) + bin).slice(-4);
    }).join('').split('');
};
const decode = (binary) => {
    let chunks = [];
    for (var i = 0; i < binary.length; i += 4)
        chunks.push(binary.slice(i, i + 4).join(''));
    return chunks.map(c => parseInt(c, 2).toString(16)).join('')
};

exports.handler = async(event) => {
    const hexMap = event['map'];
    const mapSize = event['size'];

    // convert to character array
    const binaryMap = encode(mapSize * mapSize, hexMap);
    // deep copy
    let nextMap = [...binaryMap];

    for (let r = 0; r < mapSize; r++) {
        for (let c = 0; c < mapSize; c++) {
            // loop around
            let around = 0;
            for (let dr = -1; dr < 2; dr++) {
                for (let dc = -1; dc < 2; dc++) {
                    if (dr == 0 && dc == 0) continue;

                    const nr = r + dr;
                    const nc = c + dc;
                    if (nr < 0 || nr >= mapSize || nc < 0 || nc >= mapSize)
                        continue;
                    if (binaryMap[nr * mapSize + nc] === '1')
                        around++;
                }
            }

            const coord = r * mapSize + c;
            if (around === 3) nextMap[coord] = '1';
            else if (around === 2 && binaryMap[coord] === '1') nextMap[coord] = '1';
            else nextMap[coord] = '0';
        }
    }

    return decode(nextMap);
};

変換部分が大きな数値を扱うため少々複雑ですが、ルールの処理はシンプルです。

可視化

結果を分かりやすくするため、hexのマップを受け取り可視化をする関数を作ります。

const encode = (digit, hex) => {
    const hexArray = hex.split('');
    return hexArray.map(h => {
        const bin = Number('0x' + h).toString(2);
        return ('0'.repeat(4) + bin).slice(-4);
    }).join('').split('');
};

exports.handler = async(event) => {
    const hexMap = event['map'];
    const mapSize = event['size'];

    const binaryMap = encode(mapSize * mapSize, hexMap);

    let chunks = [];
    for (var i = 0; i < mapSize * mapSize; i += mapSize)
        chunks.push(binaryMap.slice(i, i + mapSize).join(''));
    const vis = chunks.join('\n').replace(/1/g, 'x').replace(/0/g, '.');

    return vis;
};

この関数により、次の入力は


{
  "Input": {
      "map": "ca3e7995c79976c23aeb7eb96f34a8e0b985bff2ee28a69993993520a5e762a7",
      "size": 16
  }
}

このように出力されます（改行コードは実際の改行に変換しています）。

xx..x.x...xxxxx.
.xxxx..xx..x.x.x
xx...xxxx..xx..x
.xxx.xx.xx....x.
..xxx.x.xxx.x.xx
.xxxxxx.x.xxx..x
.xx.xxxx..xx.x..
x.x.x...xxx.....
x.xxx..xx....x.x
x.xxxxxxxxxx..x.
xxx.xxx...x.x...
x.x..xx.x..xx..x
x..x..xxx..xx..x
..xx.x.x..x.....
x.x..x.xxxx..xxx
.xx...x.x.x..xxx

イテレータ

最後に、ループの状態を処理するLambdaを作りましょう。これはStep Functionsを使う上で定型なので、公式ドキュメントの例がほぼそのまま利用できます。

exports.handler = (event, context, callback) => {
  let index = event.iterator.index
  let step = event.iterator.step
  let count = event.iterator.count

  index += step

  callback(null, {
    index,
    step,
    count,
    continue: index < count
  })
};

状態遷移

最後に、これらのLambdaを呼び出すStep Functionsを作りましょう。ここまでLambda側では入出力をほとんど意識しておりませんでした。また、状態は1状態しかありませんでしたが、大丈夫でしょうか？

Step Functionsでは、入力と出力を加工する方法が用意されており、かつデフォルトでは入力はそのまま出力に流れてゆきます。これにより、Lambdaの出力を入力に混ぜて最終出力とする、ということが簡単に行えます。

百聞は一見に如かず、ということでステートマシンを見てみましょう。AWSコンソールからは、このようにステートマシンの可視化が行えます。

ステートマシンの定義はJSONで行います。Lambdaのarnはダミーに変えています。

{
  "Comment": "A Hello World example of the Amazon States Language using Pass states",
  "StartAt": "sha256",
  "States": {
    "sha256": {
      "Type": "Task",
      "Resource": "arn:aws:lambda:ap-northeast-1:123456:function:sha256:$LATEST",
      "ResultPath": "$.map",
      "Next": "ConfigureCount"
    },
    "ConfigureCount": {
      "Type": "Pass",
      "Result": {
        "count": 100,
        "index": 0,
        "step": 1
      },
      "ResultPath": "$.iterator",
      "Next": "ConfigureGameOfLife"
    },
    "ConfigureGameOfLife": {
      "Type": "Pass",
      "Result": 16,
      "ResultPath": "$.size",
      "Next": "Iterator"
    },
    "Iterator": {
      "Type": "Task",
      "Resource": "arn:aws:lambda:ap-northeast-1:123456:function:iterator",
      "ResultPath": "$.iterator",
      "Next": "IsCountReached"
    },
    "IsCountReached": {
      "Type": "Choice",
      "Choices": [
        {
          "Variable": "$.iterator.continue",
          "BooleanEquals": true,
          "Next": "transition"
        }
      ],
      "Default": "Done"
    },
    "transition": {
      "Type": "Task",
      "Resource": "arn:aws:lambda:ap-northeast-1:123456:function:transition:$LATEST",
      "ResultPath": "$.map",
      "Next": "visualize"
    },
    "visualize": {
      "Type": "Task",
      "Resource": "arn:aws:lambda:ap-northeast-1:123456:function:visualize:$LATEST",
      "ResultPath": "$.visualized",
      "Next": "Iterator"
    },
    "Done": {
      "Type": "Pass",
      "OutputPath": "$.visualized",
      "End": true
    }
  }
}

読むと雰囲気が掴めるかと思いますが、ResultPathがポイントです。これにより、最初の入力である次のJSONは、

{
  "initial": "Conway"
}

sha256を通った後には"ResultPath": "$.map"により

{
  "initial": "Conway",
  "map": "ca3e7995c79976c23aeb7eb96f34a8e0b985bff2ee28a69993993520a5e762a7"
}

Lambdaの返り値をmapとして追加しています。
このような挙動を繰り返し、必要なパラメーターを次の処理へ渡すことができます。

今回はStep Functions側で100回transition関数を呼び出し、100世代を進めています。最後に可視化した結果を表示しています。ここが全て.だったり、hexが0x00..0であれば負けと出力、という形に改変しても良いでしょう。

ちなみに、Conwayと入力すると、次のような出力が得られました。左上は次の状態でもそのままになるパターンです。全滅しませんでしたね

..xx............
..x.x...........
...x............
................
................
................
................
................
................
................
................
................
................
................
................
................

なお、ほとんどの入力では生き残ると思われるので、生き残った盤面の美しさを競ったり、生存数をカウントする方がゲームとしては良いかもしれません。

AWSコンソールからは各ステップの入出力、Lambdaの実行ログ、AWS X-Rayによるトレースが確認できます。開発される際はご活用ください。

改良できる点

今回は突貫だったので、改良できるポイントは様々あります。

Lambda Layerを使って共通の処理を集約する
巨大な盤面に対応する
- 「実装」の途中に出てきた話です。
Amazon API Gatewayを使ってAPI化する
Expressワークフローを使ってコスト効率を上げる

まとめ

ジョン・ホートン・コンウェイ氏の追悼を兼ね、Step Functionsでライフゲームを作成してみました。Step Functionsはとっつきにくそうな印象がありますが、慣れてくると使い勝手の良いサービスです。例も豊富なので、ぜひ触ってみてください。