Ceasar's Mind

I’ve recently reignited my interest in Robocode but this time armed with everything I’ve learned since September.

For the uninitiated, Robocode is an educational programming game, originally written with Java in mind, where players code up algorithms to guide virtual tanks in destroying each other. It’s a unique challenge, combining fields like programming, statistics, linear algebra, and game theory all into one.

Originally intended for students, the game was quickly picked up by experienced programmers and is now rather competitive. Many players use sophisticated algorithms in order to dodge enemy bullets and make sure their own find their mark.

Anyway, let me continue to explain wave surfing- but first I need to explain segmentation.

Segmentation

Since in Robocode neither bot can see any of the bullets, developers have to find ways to track their enemy through alternative means. Segmentation is a targeting technique that involves finding which firing angles are most likely to hit the target by dividing the continuous range of firing angles into discrete bins, and finding which bins are most popular. To implement segmentation, one needs to track each bullet with “waves”.

A wave is basically analogous to a ripple in a pond after tossing a stone into the water. We track the bullets until the “wave” hits our opponent. At that point, we can determine what the correct firing angle was at the time of firing, and subsequently increment the value in the bin which contains the correct firing angle. We then proceed to fire at the center of the most popular bin whenever we get the chance.

If our bins looked like this, we would fire into the 15% bin.

A primitive approach of segmentation might only segment by firing angle. However more sophisticated approaches first segment by distance, and then angle. (And even more sophisticated approaches segment by even more dimensions.) However, these improvements come at a cost of slowing down the rate of learning, but the accuracy gain is typically well worth the price.

Optimal segmentation (I think anyway) ought to reduce the number of bins down to the minimum needed to hit every possible position of the opponent. For example, an opponent at point blank range would only require one bin, since all firing angles within the escape angle would be guaranteed to hit the target. As the distance increases however, more and more bins become necessary (I believe at an exponential rate). By reducing the number of bins in this fashion, we increase learning speed, and reduce memory costs.

Wave Surfing

Wave Surfing is an evasive technique first developed and implemented by ABC in mid-2004. To put it succinctly, wave surfing is anti-segmentation. Every time the enemy fires a shot, we create a wave, and see whether or he not the bullet hit when the wave reaches our bot, and subsequently increment our own bin. In this way, we know what our opponent believes to be the most popular firing angle, and therefore make sure to avoid it, producing a near uniform distribution at all ranges.

Why this is optimal

Refer back to my earlier post on the game theoretical solution to Rock-Paper-Scissors. Basically, to do anything else is to tip our opponent off to a flaw in our strategy. If you know for example that your opponent will play Rock 2/3 of the time and Paper 1/3 of the time, your optimal strategy becomes to keep playing Paper.

Implementation Issues

A literal implementation of the above is still susceptible to intelligent algorithms. For example, at the start of a game or Rock-Paper-Scissors, if your opponent first plays Scissors, it would be illogical to assume that because your opponent has so far only played Scissors, it would be logical to assume he would do so again. This illustrates the problem of determining when the opponent is playing sub-optimally with an unequal probability distribution. Thankfully, statistics provides an answer. Using statistical methods to determine statistically significant variance will lead to a solution- typically, with low amount of data, statisticians say nothing can be concluded, and when more data, more confidence can be placed on inferences. A simple implementation of confidence intervals ought to be sufficient.

So in Stat class a short while ago, we learned about the Gambler’s Ruin. The idea goes like this,

Two gamblers, Alice and Bob, bet on the outcomes of successive flips of a coin. On each flip, if the coin comes up heads, Alice collects $1 from Bob, whereas if it comes up tails, Bob collects $1 from Alice. They continue to do this until one of them runs out of money. If it assumed that the sucessive flips are independent and each flip results in a head with probability p, what is the probability that Alice ends up with all the money if she starts with $A and Bob starts with $B?

The solution, in all its glory, is explained here for the statistically inclined. For those who’d rather just know the answer though, it ends up working out to be that Alice will beat Bob with probability 1 – (q/p)^A / ( 1 – (q/p)^(A + B) ) if her probability of winning a flip isn’t 1/2, and simply A / (A + B) if the game is fair.

Eight examples of the way the game could go.

This is an interesting result with fairly straightforward implications. Since your chance of cleaning the other player out is equal to the amount of money you bring over the total amount of money at the table then if your opponent is a casino you lose. It’s also interesting to note that even if you always bet $2, $5, or any number of dollars for that matter at each flip, the end result is the same.

It’s far more interesting to note however that using a Martingale betting strategy completely nullifies what we have here. In an earlier post, I explained how a Martingale strategy always has an expected value of $0. However, since both Alice and Bob are playing for finite amounts of money, it’s possible that Alice could enter with less money than Bob and still clean him out! Unfortunately, I don’t know the math behind this and when I asked the professor about it he only said we might cover the answer later in the course and referred me to studying stochastic processes, so expect a post on that soon!

A short while ago my friend Boreal asked me what the role of luck ought to be in strategy games. Unfortunately, at the time I wasn’t able to give a particularly good answer, and I kind of just spewed out everything I knew so far- namely some of the research done by Kahneman and Tversky in behavioral economics and some formulations on how chance replaces tactical thinking with more strategic thinking, etc. It didn’t come out very well.

I recently saw in my feed a post over at Flash of Steel, which led to an hour long podcast between some game enthusiasts on the role of luck- and how insightful it was. Much of the first ten minutes or so revolves around how two of the enthusiasts were playing a particular wargame simulating a battle in the American Revolution and how luck just completely was screwing over the player controlling the American forces. Notably though, despite playing an extremely rough opening, the luck eventually turned in the Continental Army’s favor, and the British managed only an extremely narrow victory.

What’s important here though is how luck came together to form a narrative for these players. As one of the other speakers pointed out, if the luck had simply led to a game that went something like “yeah, we both had our ups and downs, but in the end I eventually pulled out a win” the game would have remained very game-y. But because the ups and downs of the game were clustered, the players were led to form a narrative from these completely random events.

Nassim Nicholas Taleb discusses this extensively in his book, The Black Swan, coining the term “narrative fallacy” to describe what I just described above. However, Taleb writes as a warning to investors on Wall Street. Namely, he tries to point out how big investment firms are typically just employing a modified form of a Martingale betting system, thus giving the illusion of constant steady gains, when in fact, the system is only prolonging the mandated expected value of 0, which, in this case, it will achieve through catastrophic failure.

I'm not sure what the labels say exactly, but this is most certainly a graph of Earnings vs. Rounds using a Martingale betting strategy. Notice the steady gains and then the catastrophic loss.

To explain the Martingale betting system briefly, imagine you play a game where you bet some amount of money and then a fair coin is tossed. If it comes up heads, you win double your bet, if tails, you lose your bet. Math predicts your expected value to be 0. Assuming you bet $1 each time, it’s pretty clear it is the case. However, some of us think we’re clever and point out that if you were to adopt a strategy where you start by betting $1, double your last bet whenever you lose, and bet $1 again once you win, you would steadily gain $1 over repeated iterations, and profit indefinitely. And true, if you had an infinite bankroll, this would indeed work. However, an infinite bankroll is infeasible, and given that, we’re doomed- The graph above shows why. For the most part, our strategy will work as intended, producing steady gains. But over enough iterations, we will eventually get a horrible losing streak, repeatedly double our bets, and lose everything we ever made (and possibly more).

Same with a lot of investment firms.

Taleb pointed this out before the economy collapsed a few years ago and built up an investment strategy that actually would profit on such a catastrophic failure. He’s now extremely rich, and extremely well respected.

It happens other places too though- typically, a lot of people attribute coincidence to religion in some way. (I personally used to thank God for not having homework collected when I would forget to do it back in high school.) People simply don’t realize that occasionally the unbelievable has to happen.

Anyway, just wanted to make the connection.

At first, randomness and strategy games would seem like unlikely partners. Strategy games emphasize the role of information in making decisions, while randomness is chaotic, and undermines planning. Despite their differences however, when used properly they can combine nicely.

First off, let me begin with some terminology. When I refer to tactics, I refer to a series of maneuvers designed to accomplish a specific task. In other words, tactics are the little tricks that you can calculate in your head. When I refer to strategical moves, I refer to moves that are made in the absence of calculation, and instead guided by heuristics (in particular, experience).

With those definitions in mind, it is clear that when randomness is introduced into the low-levels (like, at an individual unit level) of a game, it elevates many tactics to the level of strategy. This can be good or bad, depending on your intentions with the game.

Randomness should not however come into high-levels of a game. I often debate the idea of macro-strategies, and how if done improperly, there can very easily be a rock-paper-scissors game disguised as a strategy game. This is bad, just in general.

Randomness should also be predictable. Not like, in the sense that it isn’t random, but in the sense that it shouldn’t be a 1% chance to create some uber-unfair effect. Again, depending on your intentions, the proc-rates will vary, but typically, I would claim that higher values are worse than lower values, the reason being, high proc-rates will cause players to depend on them working, and when they don’t it’ll cause a lot of frustration, while with low values, a player will find it more like it was just good luck.

For those unfamiliar with the idea, check out prospect theory. To make things brief though, marginal gains and marginal losses both decrease. Put in another way, let me present to you a classic problem. An impending disease will strike a city, and you are put in charge of choosing a plan that will protect the lives of its inhabitants. In Case 1, you are presented two options: Plan A will save 100 people. Plan B has a 50% chance to save 200 people, and a 50% chance to save none. Record your choice. In Case 2, you are again presented two options: This time, Plan A will result in the death of 100 people and Plan B has a 50% chance to result in the death of 200 people, and a 50% chance to result in the death of none. Record your choice. Now, if you are like most people, you chose Plan A in Case A and plan B in case B, despite both being equally rational choices. Here’s why: In Case 1, the value of the first 100 lives saved is to our brains worth more than the value of the next 100 lives saved. Thus, a 50% chance to double the number of lives saved doesn’t cut it. In Case 2, the value of the first 100 lives lost is worth more than the next 100 lives lost. In this case, where we want to minimize loss, taking the risk is a good idea.

What does this mean for designers? Well, for one, it means that if people are going to use something, they will prefer a 100% proc with a small effect rather than anything less than a 100% proc with a bigger effect. If they’re opponent is going to use something, they prefer the inverse. And finally, it means that testers will likely report on randomness in ways that pretty much mean nothing.

Debatably, it may make sense to not even make randomness random at all. I believe it was Civilization Revolution that completely did away with randomness altogether, and instead opted for an approach that guaranteed that a 1/x proc would proc once every x times, citing that players typically felt that the game was cheating them when abilities proc-ed repeatedly in their opponent’s favor. I personally think that if this idea can be reasonably implemented, it’s a better approach, as people tend to remember the negative experiences a lot more strongly than the positive ones. (This is scientifically verified, not just opinion. This is why when we are unsure we keep our original answers on tests rather than changing them, despite evidence that says to do the opposite. That is, we remember when we change an answer and got something wrong, and as opposed to changing an answer and getting it right.)

Randomness also removes a player’s sense of agency, which is vital in games. I can’t remember where I read it, but player’s prefer an opponent to be buffed than for them to be negatively buffed (and, I presume, the opposite for their enemies). Randomness has the same effect, and should be used sparingly.

Anyway, while you should factor all of those thoughts in, the real aim of this post was how it relates to strategy games. As said before, we want our randomness to not be so random, in order to develop sounder strategies. I would rather have a 50% proc which forces me to plan for what happens in either case, as opposed to a >50% proc in which I will count on it working, and totally be screwed, or perhaps better yet, a <50% proc, where I will count on the proc failing, and be happy when it turns out to go well.

In order to maintain senses of agency, which are of utmost importance in strategy games, randomness ought to have minimal effect, which means the range of its possible outcomes should be small. That is, if a unit is to deal on average 50 damage, it’s better to have it deal 40-60 with equal weights as opposed to 0-100 with equal weights. Furthermore, careful effort should be made to ensure that luck never (directly, or rather, noticeably) affects the outcome of a game.

Finally, let me refer back to this post on the TDG forums that I made a while ago, detailing randomness and its effects on intensity.