How Counterstrike Works

(it’s about time)

Copyright © 2018

Chris Colohan

How does it work?

?

Client-server model

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

When is now?

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

Time

Input

Now

Server

Now

Display

Now

Latency (lag)

Speculation

Time

Execution

if()

Now

if()

if()

if()

if()

Speculation

Time

Execution

if()

if()

if()

if()

if()

Speculation

Time

Execution

if()

if()

Speculation

Time

Display

Now

Input

Now

Speculation

Time

Progress

• Client-server model was strongly consistent
• Server is one true arbiter of what happened
• Adding speculation makes us weakly consistent
• Each player observes a slightly different game
• Server is still one true arbiter of what happened
• Problem: Server is lagged vs clients

What about the enemy?

• Shooting at where players were,�not where they are
• From the server’s perspective

Lag compensation

Server side:

• Record history of player motion
• Rewind position to t=t-lag

That’s It!

• Input speculation + lag compensation =� how video games work today
• Can we improve on this?
• Also improve our understanding?

Shot by a ghost! (Server perspective)

Shot by player you never saw,

through a wall!

Shot by a ghost! (Shooter perspective)

Einstein’s theory of relativity

applies to CSGO?

Consistency is Good!

• Lag compensation has made game inconsistent
• Score is still consistent, player motion is not
• Best of both worlds:
• Consistent, and low lag?
• Apply speculation to all players
• Predict the next 200ms of behavior
• Only of players in view
• Better predictor = better gameplay

Predicting the future?

• Linear extrapolation
• Use derivative of motion
• Use AI to predict motion
• On misprediction:
• Rewind speculation, replay with new data

Predicting the future?

• Linear extrapolation
• Use derivative of motion
• Use AI to predict motion
• On misprediction:
• Rewind speculation, replay with new data

AI

Side-channel improves prediction

• ½ the lag
• n² bandwidth
• New way of cheating?

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

The Hard Parts

• Is it fresh?
• Keystroke newer than last update from server.

• How new?
• Applies to which speculative update?

Time

Display

Now

Is it fresh?

How new?

Broadcast Keystrokes Everywhere

Problems:

• High bandwidth
• How to deal with loss?

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

Use Time of Day

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

Clocks are Hard

• Need
• High resolution
• Monotone
• Synchronization over a network is hard
• May be impossible to get accurate enough
• GPS based synchronization?
• Used by Google’s Spanner database

Sequence numbers

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

P1:3,1,4�P2:1,5,9

B1:2,6,5

3

P1:3,1,4�P2:1,5,9

B1:2,6,5

2

P1:3,1,4�P2:1,5,9

B1:2,6,5

1

Can we do better?

• Better predictors
• Use machine learning?
• Eliminate the server!
• Colyseus and Donnybrook
• Makes cheating-resistance harder
• Optimize communication
• Area-of-interest filtering
• Randomize gunfire
• Matchmaking matters
• Have a LAN party!

Want More?

Useful articles:

• What Every Programmer Needs to Know About Game Networking (goo.gl/o7mc5f)
• Source Multiplayer Networking (goo.gl/u9J9Ya)

�Read up on:

• Lamport clocks
• Vector clocks
• Spanner