Hacker News Reader

Comment by thewarrior | Hacker News Reader

This piece was really interesting. That you can hide network delays by building a “fake” model of the other player that replicates what a real player would do and rolling back when this prediction fails. So you can train some neural nets on what players do in such situations and you get a certain accuracy. And yet you can keep making this “fake” player better and better until it’s indistinguishable from fighting a human and we arrive a nice little paradox. These kinds of games and algorithms are really good proving grounds for AI. And I begin to get why the author is so passionate about this stuff and it’s possibilities.

View on HN

Where did you get the thing about neural networks? I read your comment before reading the article and was really disappointed the prediction "algorithm" (pioneered by GGPO in 2006 [0] and still used today) is literally "assume nothing changed", ie. the opponent is still holding down the same keys as the last frame.

[0]: magazine article by the author of GGPO [pdf] https://drive.google.com/file/d/1cV0fY8e_SC1hIFF5E1rT8XRVRzP...

You shouldn't be disappointed. Nothing has changed is overwhelmingly the correct answer.

It is incredibly jarring to assume a remote player takes an action, display them taking that action, then roll back when you realize they didn't. From your local perspective, it looks like they blocked for a few frames, which makes you assume they're going to block, then they flash back to being defenseless, and your attack weirdly goes through even though you anticipated that it did not.

Even if you can get your fancy neural net to figure out that the enemy is likely to block you - which is a feat worth writing some papers about - you're still going to be wrong about the frame on which they do it. Was their reaction time 160ms? 176ms? 182ms?

If you're right about the action they take and wrong about the frame, that's going to cause each action in the game to have weird timing. You anticipate a block, then it doesn't come so you roll it back, then wait, it actually has come it was just late! The remote player flays around like they don't know what the hell they're doing, and it's not clear to you when you land your hit whether the timer started from when they first telegraphed their block or when the glitch occurred. Your punch appears to land at random.

And blocking is an insignificant action - what if you're playing something like DayZ and the neural net decides that some random other neutral player is likely to try to attack you, say because they happened to mouse over you qucikly.

It looks like they just shot you for a few frames, but weirdly your health goes down and springs back up again, but you're not going to figure out it is the netcode playing tricks on you. Instead you unload your magazine at the other player that's clearly trying to kill you.

And since you are actually shooting now, of course they're going to return fire. Your prediction algorithm just caused two peaceful players to fight to the death.

Just because the algorithm is simple doesn't mean it's possible to do better.

Yeah it probably is an optimal strategy (and certainly relative to return on investment).

I didn't mean disappointment that the tech hadn't advanced, I meant that my expectations were set really high by the grandparent comment ("Neural networks? In 2006? Surely not! But it must be something really fancy, judging by all these flowcharts!" [0]) and by how they kept hyping up the "prediction algorithm" for half the article, when it's just

1. take the data you already had

2. (there is no step 2)

[0]: https://drive.google.com/file/d/1cV0fY8e_SC1hIFF5E1rT8XRVRzP...

I think you're missing the point of the article (and the material you included). It's not that the method of inference is that interesting, its the fact that the game is able to make use of that inference at all. Every thing else about the algorithm is interesting: rollback, reconciliation, (de)synchronization, choice of delay, the the separation of game logic from rest of the game loop, etc. As the article details, it's extremely complex to do this right, to the point where many games just don't bother trying.

Think about the time scale under which this prediction is made: 60Hz. Even the best players do not change input at nearly that rate. So it's clear that the current value is going to be the best estimate for the next value. That realization doesn't even begin to solve the problem though!

Oh right, that makes sense. I was actually going to write a similar reply to the parent comment but got distracted.

This is a lovely illustration of the fact that "not very powerful but highly predictable" is often far better than "powerful but unpredictable" when it comes to tools.

As in this article, the base assumption is that a lot of the lag happens at moments where the input doesn’t matter that much. In fighting games, when characters are moving left and right or locked in a motion, in FPS when just moving around or shooting at hard to hit targets.

Predicting right is only important in short bursts at critical moments, and it’s also the hardest to predict and less forgiving moments, so I’d assume being conservative is the more cost effective and pragmatic choice.

Not sure you would want the prediction to take non-dumb actions. You need to maintain the hypothesis of least surprise for the local player, otherwise you local player could start to act based on the wrongly predicted actions of the remote player, and that's even worst than nothing.

For instance, say the local player tries to hit the remote one. If the prediction for the remote player is to evade, the local player can choose to chase him. However if you now rollback and the remote player did not evade but charge in, the local player has been fooled.

Also, don't forget than in these games, input could be polled every 1ms. So a player pressing down "left" for 1s in fact is considered to have 1000 down inputs on left. Since players don't change inputs very fast, just replicating the last input is in fact 99.9% accurate.

> Since players don't change inputs very fast, just replicating the last input is in fact 99.9% accurate.

Sadly, fighting games, and to the same extent FPS casually break that assumption. 1s is an eternity in a close fight, and players don’t just react, they also read ahead and align inputs based on the situation they expect, regardless of the speed of the game.

Commands will be entered in as low as one to three frames depending on the players, and it will be common to train to do some combos to input them faster. Basically “shooting twice” could actually be “shoot once, go left, go right, shoot again” if doing that has any advantage (canceling the shooting cooldown time for instance). And players don’t do these consistently, or succeed every time.

It’s really complicated :)

>1s is an eternity in a close fight, and players don’t just react, they also read ahead and align inputs based on the situation they expect, regardless of the speed of the game.

This was a pretty obvious result when LinusTechTips did their different frame rate testing in first person shooter games. Higher frame rate benefited worse players more than skilled players. My assumption is that skilled players have learned the pattern. Kind of like martial arts - you practice a flow of moves so that you can execute them without having to think about the next move. (Perhaps this is also how people type very quickly.)

> Sadly, fighting games, and to the same extent FPS casually break that assumption. 1s is an eternity in a close fight.

Sure, but that's nothing compared to the speed of just polling inputs.

I would assume a pro player in a fighting game to have what, say 180 APM at peak ?

That's 3 actions per second, so if we assume a uniform holding time and a 60 FPS game that's 1 input change every 20 polled inputs. Assuming repeated inputs does seem like a good strategy in this situation.

An other way of seeing it, is that if a player with 180APM realistically can only change inputs every 333ms, then with a remote input lag of 25ms (50ms ping / 2) there is just a 1/13 chance that an input change would occur in this time slice.

I actually agree that assuming input didn’t change is the most pragmatical course of action, as even if the input changed I’d assume there’s just no way to efficiently anticipate it at this point. With that strategy the best case scenario is optimal, and worse case scenario is not worse than for any other option.

On the 1 change every 20 polls calculation, it’s true locally, but for a ping of 200ms for instance, 333ms of loss is ‘only’ 3 times the one way trip time. I think momentarily losing 3 times the connection speed happens often enough, and of course the bar for losing an actual action due to lag is yet lower for intercontinental games.

I don't think those predictions are that sophisticated, maybe there is some Bayesian probability, but I can't see a neural net fitting inside a single frame. However, lots of progress has been made in using neural nets for training fully autonomous NPCs:

https://cns.utexas.edu/news/game-bots-pass-turing-test

"In order to most convincingly mimic as much of the range of human behavior as possible, the team takes a two-pronged approach. Some behavior is modeled directly on previously observed human behavior, while the central battle behaviors are developed through a process called neuroevolution, which runs artificially intelligent neural networks through a survival-of-the-fittest gauntlet that is modeled on the biological process of evolution."

Why would you bother training neural nets? They already found a solution that can be computed in literally 0 cpu time that works for >90% of the cases (their theoretical model was an above average active player moving 5 times in a second, which is 5 frames of input you can't predict as being the same as the previous, which is 8% of the time).

Why would you waste time trying to shove neural nets into a solution which has such amazing properties? It really terrifies me that that's the first place you went to.

You also have the issue of performance. If you have a NN churning predicting every frame what your remote player would do, it would add even more load to that 16ms loop of calculating and rendering everything else. At best maybe some very basic ML might help, but the "assume no input changed" seems to be best guess from the sounds of empirical testing in the article.

Makes me even more curious about Stadia’s “button anticipation” code

human can learn what the ai will think they will do and act differently to maximize the reality dissonance for the other player.

this is not fundamentally different than what we already do in these games though, which is to choose tactics that work to your advantage given how the game deals with lag.

client side hit detection? be the aggressor and do the moving into view and get milliseconds advantage to start shooting.

Reply on news.ycombinator.com