ネットワーク対戦ゲームの実装に関する考察（リバーシ編）

サマリー

サーバー ↔ クライアント間の通信は常に遅延する可能性があります。そのため、ステートフルなアプリケーションを実装する際には、因果関係を適切に扱うように実装しないと想定外の状態になってしまう可能性があるので注意が必要です。

実装予定のリバーシ

リバーシのネットワーク対戦ゲームを考えます。

右側のプレイヤーは●（黒石）をボードに置きます。左側のプレイヤーは○（白石）をボードに置きます。

リバーシのボード(盤面)の情報はゲームサーバー側で管理します。プレイヤーの操作にもとづき、ゲームクライアントはインターネット越しにゲームサーバーに対してどのようなアクションを取ったかのメッセージを送信します。

クライアントとサーバーの通信はTCPなどのリアルタイム通信でも良さそうですし、今回の例ではREST APIなどでも実装できるかもしれません。

このリバーシのゲームでは1ターンあたりの制限時間n秒があり、制限時間までにプレイヤーのアクションがゲームサーバーで実行されなかった場合はサーバーが選んだボード上の位置に自動的に石を置きます。

エッジケース

このリバーシではエッジケースの考慮が必要になってきます。

まず、下記の図のように右プレイヤーが●（黒石）をボードのe3の位置に置こうとしたので、クライアントからサーバーにPutStoneイベントを送信します：

しかしネットワークの遅延で、制限時間内にサーバーに届きませんでした。この場合、サーバーが選んだボード上のc5の位置に●（黒石）が自動的に置かれます：

左側のプレイヤーが○（白石）をボードに置きます：

再び右側のプレイヤーのターンがやってきました。そして、ちょうどそのタイミングで遅延していた「右側のプレイヤーが●（黒石）をボードのe3の位置に置くアクション（前のターンのもの）」がサーバーに届きました。

サーバーはこのアクションを受け入れたため、下記のボードの状態になってしまいました。：

このときのボードの状態は右側のプレイヤーが想定していたものとは異なっています。

右側のプレイヤーとしては、下記のようなボードの状態を想定していたはずです：

原因

このような状況が発生してしまった原因としては、「遅延して届いたプレイヤーの石を置くアクション」をサーバー側で弾くことなく盤面に適用してしまったためです。プレイヤーの意図したアクションなのか、遅延して届いたアクションなのか、をサーバー側で区別できなかったため発生してしまいました。

回避策

これを避けるためには、クライアントとサーバーとでゲームの進行具合を非同期でも良いので同期する必要があります。

今回の場合は下記の方式などが考えられます。

• 対策のパターン A

  • プレイヤーからのアクションを送る際には、「どのターンに対するものなのか」をつけてもらう（メッセージにいわゆる論理クロックのようなものを必ず付与する）
    • 例: PutStone: ●e3 @turn#1

• 対策のパターン B

  • ターン切り替わり時にAckメッセージを返してもらう
    • ターン切り替わり時にサーバーはクライアントにターン番号を送ります。それに対してクライアントからサーバーにAckを返送してもらいます。
      • Ackより後であれば、どのターンに対するアクションなのか、因果関係が判断つきます
    • こちらの方式のほうが他のメッセージの修正が不要ですし、「一定時間Ackが返ってこなかったので切断状態」みたいな判断もしやすそうです。

このあたりの話は、O'Reilly Japan - データ指向アプリケーションデザイン の「9.3.1 順序と因果関係」の話が参考になりそうな気がしています。

対策のパターン B: ターン切り替わり時にAckメッセージを返してもらう

「対策のパターン B: ターン切り替わり時にAckメッセージを返してもらう」の処理がどのようになりそうかを考えてみます。

まず、サーバーは3ターン目が始まったことを右側のプレイヤーに通知します：

その直後、今回も右側のプレイヤーの「e3に●（黒石）を置くアクション」が遅延してサーバーに届きます。しかしこの場合、3ターン目に対するAckがまだ来ていないため、サーバーはこのアクションを無視します：

右側のプレイヤーは自分の1ターン目の石を置くアクションが失敗し、ゲームが進行していることに気づきます。そこで3ターン目のAckを返送した後に再度石を置くアクションを実行します：

この場合であれば、サーバー側とクライアント側とでゲーム進行が一致しているのでアクションが受け入れられます。

状態遷移のABA問題

ちょっとした遅延なら良いのです（ギリギリ間に合わなくて相手のターンになってから自分のアクションが届いたなら、すでに相手のターンになってしまっているのでそもそも置けるはずがない）。しかし、ちょうど自分のターンが再び来てしまっていた場合には、「自分のターンかどうか」だけで判断するのでは不十分そうです。

このケースに対応するためには、アクションの因果関係がどうなっているかを特定する必要があります。つまり、上記のような「何ターン目に対するアクションなのか」で弾くようにする必要が出てきます。（これを 状態遷移のABA問題 とでも言ったら良いんでしょうか…？）