## Posts Tagged ‘**math**’

## Prime Generator

Inspired by the last post, just thought this was too cool not to share. The function generates primes!

def prime_gen(): '''Generate primes.''' offset = 2 index = offset sieve = range(offset, offset ** 2) found = [] while 1: start = index ** 2 end = (index + 1) ** 2 sieve.extend(range(start, end)) num = sieve[index - offset] if num: found.append(num) sieve = sieve[index - offset:] offset = num yield num i = 0 while i < len(found): curr = found[i] j = start / curr * curr while j < len(sieve) + offset: sieve[j - offset] = 0 j += curr i += 1 index += 1</pre>

## The Quadratic Sieve

Just got done with a terrible day of magic numbers. To spare everyone the trouble, here’s a fairly clear version of a quadratic sieve for generating prime numbers that ought to be self-explanatory and easily modified– as opposed to many other algorithms out there.

def primes(n): '''Get all primes up to n.''' n = int(n) if n < 2: return [] sieve = range(n) sieve[1] = 0 root = n ** 0.5 index = 0 while index <= root: if sieve[index]: i = index ** 2 while i < n: sieve[i] = 0 i += index index += 1 return [x for x in sieve if x]

## Jellybean Jars Done Right

It’s fairly close to Easter, so I figure a few of these will be popping up in the future, and I thought I’d just write a post about how to game the system properly and guess the correct number with a good deal of precision.

So back in senior year of high school, we had a week long contest known as Spirit Week where the school was divided into two teams to compete in a series of events for no reason other than bragging rights. As you can imagine, most of the stuff was rather silly and I didn’t bother. However, one event was more suited to my tastes: The moderators filled up two decent sized jars with Jolly Ranchers and gave each of us one guess. The person who submitted the closest number to the real count would win some points for their team as well as the two jars of candy.

My friend Vinh and I decided to take up the challenge for some kicks. In order to do this, I took a bunch of 2×4 Lego bricks from my house, a small jar, and then bought some Jolly Ranchers from a nearby convenience store. (I thought the Lego bricks were a good approximation, but it turned out later I didn’t need them.) I then proceeded to fill up the jar with all the Jolly Ranchers I had, measured the height, and calculated the jar volume to Jolly Rancher ratio (measuring Jolly Rancher volume is impractical because of the weirdness of the shape and the chaotic way that they stack, so this is the only reasonable way). It came out to be that 66% of the jar was empty space! (And for those interested, a jar of 2×4 lego bricks is 50% empty space. In other words, if you don’t know what to do with all of your bricks and hate how much space they take up, you might compress them by pressing them together rather than just throwing them all into a box for a 50% reduction!)

Now typically they don’t let you measure the jar, and in that case your guess is as good as mine. (I would suppose taking a picture of the jar next to a meterstick would be useful in the case.) But in this case they let people measure. Unfortunately, the one jar was kind of round, so a simple height x width x length was insufficient, but fortunately, my friend Vinh knew how to do curve fitting on our TI-83s, so I simply recorded a few widths at various heights and we took a few integrals to get the volume. Multiplying the volume by the space to Jolly Rancher ratio gave us an approximation, and being a team event, Vinh and I printed out a bunch of numbers for our friends to guess that gave us plenty of room to be off by.

Subsequently, one of my friends, Max, won,with a guess off by three of our original approximation. Max kept one of the jars, I got one (offered to split it with Vinh but he didn’t care. Me either really, it’s now preserved as a trophy in my basement.), and the team scored a bunch of points. (We still lost though unfortunately.)

And that’s how you do it the nerd way.

## Curve Fitting using Linear Algebra

My initial interest in curve fitting came a while ago when programming tanks for Robocode, but realizing the complexity given my limited knowledge of calculus, my plans came to a screeching halt. However, I recently got into the concept of hacking, and subsequently found HackThisSite, which poses training puzzles to the hackers of the future. One, required the player to reverse engineer an encryption algorithm (an extremely simple one at that) but the puzzle made me realize that I could probably use what I was learning in my math classes to automate the process and tackle any simple encryption algorithms. And then I realized that actually, this is how targeting algorithms are built.

Linear algebra is cool because it let’s us compose functions that take map an arbitrary number of arguments to a real. This is useful in a lot of cases. For one, I could map angular velocity, angular acceleration, and distance of a target to firing angles. Alternatively, I could map the value of a pot, the number of opponents, and my current winnings to an amount to bet.

Let’s start simple. Let’s say we wanted to fit a curve of power 2 through the points (1,2), (3,4), and (5,6). To do this, we want to find the general solution to y=ax^2+bx+c where a, b, c are unknown. So let’s write our matrices out.

a*(1)+b*(1)+c*1=(2)

a*(9)+b*(3)+c*1=(4)

a*(25)+b*(5)+c*1=(6)

Using linear algebra, we can turn all of this into three matrices of the form Ax=b. In this case, A=((1,1,1), (9,3,1), (25,5,1)), x=((a), (b), (c)) and b = ((2), (4), (6)). In this form, this solution unfolds itself very clearly: x=A^-1*b. The solution is a=0, b=1, c=1.

Now let’s get a little more complex. The next question is what if we have more rows than columns? In this case, A has no inverse. The solution: we turn to projection. For those who are unfamiliar, the details are messy, but basically, we come up with (A^t)Ax=(A^t)b. Since (A^t)A is square, we can invert it, and therefore we get x=((A^t)(A))^(-1)(A^t)b. It’s a bit messy, so I won’t present an example, but it works.

What that equation basically gives us is actually the least squares approximation. So basically, if we were to take A as a column vector of the x’s, and b a column vector of the y’s, and if A had a bunch of rows with some noise in the data, we would end up with a line that goes through them all pretty nicely.

The next question is, how we do fit a plane through a set of data points- and subsequently, how do we fit an n-dimensional object through a set of data points?

The solution is surprisingly simple. Just add a column for the new input! So let’s say we wanted to fit a straight plane through some data points- Well, the equation for a plane is ax+by+cz=d. Or more relevantly, ax+by+d =z (the negative signs don’t really matter since a, b, and d will take care of that). Now it looks like something we can handle. Simply write out each row in A to be (x, y, 1), x to be a column vector of (a, b, d) and b to be the corresponding z’s. Use the equation presented above, and you’ve got your solution!

This is awesome, because now we can add as many variables as we want, and add dependencies as well. Say the enemy tanks are factoring in some amount of distance*velocity into their equations in order to trip us up a little- we simply add in a distance*velocity vector into A, another variable in x, and now we’ve got it covered.

The only problem as I see it is the enormous scale we are looking at here. Basically, if we look to include all dependencies, the width of our matrix A is equal to n^v, where n is the degree of the polynomial that we’re trying to fit through the data, and v is the number of variables we have. Not the worst, especially considering we generally want small polynomials (since large polynomials tend to behave oddly) but with a bunch of variables, even inititally small amounts of computation could become costly.

Next objective: Build a program that updates a curve with new data without recalculating the whole thing.

## Research

So a recent post on the TDG forums got me thinking about the value of upgrades and research, and it’s really rather simple, but I think worth saying anyhow since they are so common and to amateurs often a bit bizarre.

**Research**

Research enables new the construction of new units and technology can often be researched in a variety of ways. New units can often be unlocked by simply building or upgrading structures, and upgrades or new abilities can often be unlocked via researching the technology directly at a building.

However, the difficult part is really just determining if it’s really worth it to buy many of these upgrades or research the technology. Sometimes the choice can be simple- If for example, a player already owns a hundred soldiers and researching an attack upgrade is cheap, it’s a no brainer. The player will get his money’s worth as soon as the research is completed.

If however, a player is spending resources to simply unlock the *ability* to construct a new unit (or alternatively use a new ability) the price at first is a little more difficult to figure out. If we assume that the new units is more cost effective than existing units, the player could simply determine if he will reasonably build enough units to get his money’s worth. If for example, the current tier of units get a 100:10 strength to resource ratio, and the new tier would get a 200:10 strength to resource ratio, but initially costs 200 resources, then to make those lost resources back, the player would have to purchase 10 of the new tier units. Beyond that is a profit in strength.

It’s in my opinion though, that having such strict tiers, with each new tier nullifying old ones, is often bad design. (Sometimes, as in the case of Tower Defense War games this is necessary.) The alternative approach, as appears to be most common in RTS games, is to make units cost effective in certain scenarios, say good at defeating groups of units via splash or effective at combating biological units via poison, such that no unit is truly superior to any other, except in certain scenarios. It then becomes the player’s job to guess at how often the player will be able to effectively use unlocked units, and if the benefits outweigh the costs, then to purchase the technology.

To give an example- Consider you are playing StarCraft. You are the Terran (an army of gritty future humans) playing against the Zerg (an alien army that has evolved to kill). The game begins, and you start building Marines, the basic component of early Terran armies. Very quickly, the option to purchase Medics arrives, which are extremely useful units when the opponent is unable to kill your Marines quickly. Knowing that the Zerg only has access to Zerglings and Hydralisks, both of which are relatively fragile and also unable to overwhelm the healing effects of Medics, it’s a logical decision to buy them. The benefits greatly outweigh the costs, and you will make up the money spent on the research very quickly. You will not however, proceed to buy Firebats, because despite their splash attack, which is effective against clustered enemies, their short range makes them particularly weak against Hydralisk, which your enemy will have many of, and therefore, your Firebats will always be fighting in situations where they are not cost effective, and they will not make up the money spent on research.

As designers, this effectively means that the price of research is effectively arbitrary. Higher costs however, will mean that the research will much less often be purchased, since players will only see it as useful if they can pretty much guarantee that the unlocked units will be able to be deployed in cost effective circumstances.

Research is kind of interesting because players will shape their armies based on the conditions they are fighting in. Based on the map, it may or may not be cost effective to purchase certain units. For example, ground units lose a lot of their effectiveness of island maps. Additionally, the race of the opponent will have to be factored in. For example, Science Vessels are pretty much a must have against Zerg, with their ability to Irradiate enemy units and detect Lurkers. And perhaps even more interestingly, the units that you have already unlocked has to be considered. Certain units may work extremely well together, such as Marines and Medics.

So basically, research is kind of the depth aspect of RTS games. It takes experience to figure out what’s worth researching and what’s not, and these decisions, strategically, are often the most important, and really fuel the interesting interplay behind the RTS.

Rethinking research in the frame of context of group combat, it occurred to me that beyond the points covered in my original post on research, the real value of research comes from the ability to construct more specialized units, which in turn result in stronger heterogeneous groups. From this perspective, I would claim that in any well made RTS, the lowest tiered units would be largely unspecialized- namely, stats that are effective for 1v1 combat and as more research permits the creation of more units, the new units become more and more specialized. We see this in Starcraft- Terrans have the well rounded Marines, Zerg have well rounded Hydralisks, and Protoss typically produces well rounded combinations of Zealots and Dragoons.

## Prioritizing Targets

Not sure where this belongs exactly yet, but I figured it was worth mentioning. In regards to all of these Hit Points and Damage things, there is a way to prioritize which targets you take out besides what’s most convenient and it’s simple really: Determine which unit is dealing the most damage per hit point, and kill him first.

Take for example, Halo 3. Consider you encounter the two enemies above simultaneously. The one on the left is called a Hunter, armed with a large Assault Cannon, and on the right is a Grunt, armed with a Fuel Rod Cannon. Both weapons are extremely dangerous. However, the Hunter is very difficult to kill, possessing thick armor and a large metallic shield on his left arm which no projectile can penetrate, while the Grunt is very easy to kill, possessing no armor and very little hit points.

The decision before you is this: To target the Hunter first and attempt to dodge both weapons while attempting to find a weak spot in its armor, or to shoot at the Grunt and kill him quickly and then to fight the Hunter alone. Not much of a choice unless you like a challenge.

Mathematics tell us to take exactly the same course of action in RTS battles. Put simply, to figure out which unit to strike first, determine the DPS of all enemy units and divide it by their hit points and then strike the unit which has the highest result. Usually though, this is intuitively obvious.

**Factor in Capital**

In strategy games though, there is also capital. That is, while in most cases a damaged unit can be regenerated or repaired, sometimes even for no cost besides time, a dead unit stays dead, and is a permanent loss of resources. With this in mind, the priority can shift to striking the unit with the highest cost to hit point ratio.

Ultimately, it comes down to whether or not you can successfully ensure a kill. If it’s not possible, then it’s best to prioritize by damage to health ratios in order to preserve the hit points of your force. Otherwise, it’s significantly better to take out what you can and then regenerate your units before fighting again on much less level ground.

**Why Cheap Units Are Still Useful**

The idea of worrying about capital losses usually means trying to invest minimally in weak units since they die very easily. I’ve often wondered if I should make a new formula to adjust for this problem, making expensive units less and less cost effective. I think though that cheap units are underestimated. The one power that they have over their more expensive counterparts is that they can be in multiple places at once. Utilized correctly, this feature can overwork an enemy defense and allow you to penetrate where a more expensive force couldn’t. (The trick is to set it up so that the cheap provides provide an extra kick for your other more expensive units, making each one more powerful individually, and then striking the enemy. He’ll be unable to divert his resources as necessary since they are all centralized in expensive units.) However, this is based off of my experiences with Naval Commander, which accidentally was balanced “incorrectly” since the attack mechanism would choose a random target in range instead of focusing on the weak units, effectively making the strength of units scale linearly. I’ll have to play with the idea a little more in the future.

## Flanking – Part 1

With the math behind pricing in mind, it’s obvious that forces grow in strength exponentially with each unit in the party. Not only is our force stronger though, but we take less damage. However, party strength is limited by space. If a unit can’t get the enemy in range, he can’t help the party.

**Basics**

The basic idea here is rather simple. All of that math explained before assumes that all units in a force can attack. But that isn’t necessarily the case. What battles are really all about are creating situations where you have more units attacking than your opponent does.

The simplest and perhaps most common of these scenarios is the flank of a line formation. In the image to the right, the black army is positioned to flank the white army. All three of the black units can attack the bottom white unit, but only the bottom white unit can strike back. The other two white units don’t have any targets in range.

If white does not react quickly, black will fight each unit individually, and crush all three of them losing only one unit in the process.

(Line formations are extremely effective at flanking because of their ability to wrap around vertices, but their vertices are also extremely vulnerable.)

**The Impact of Formation**

Besides the actual size of units, formation can affect the effectiveness of an enemy flank. Consider the two images presented here.

In the image above, four black units are surrounded by an army of white. Due to their shape, they reduce up to 16 attacks down to 8.

Now consider this second image. In it, an army of nine black units fend off a larger army of white. Due to their shape however, they reduce up to 36 attacks down to 12.

Notice the number of vertices stays the same despite the increasing amount of units. Side length increases instead, decreasing the percentage of your units being flanked. Consequently, bigger shapes are better. Furthermore, if the terrain is favorable, it can sometimes be possible to construct a straight line from one impassable point to another, eliminating vertices altogether!

This knowledge is particularly useful when using units that are expensive since, at least in my experience, they are balanced assuming that the enemy strikes in full force. By rearranging your army’s formation or exploiting impassable terrain, you can force enemy units to strike individually and increase the effectiveness of your units exponentially!

**The Impact of Range**

Besides collision size, the other factor that affects a player ability to flank is range. Basically, more range means more unit can sit along the circumference of the range from the target, and increase the effectiveness of a flank. Furthermore, if a group of units possess a range greater than their targets, not only will they able to position themselves along a wider circumference, but units can position themselves in a series of lines, drastically increasing the effectiveness of their attacks.

In the picture above, the white army has a small range, and the circumference along which they can align is also fairly tiny.

Compare the above picture to the previous one. In this, the white army has significantly increased attack range, permitting many more units to join in the attack.

Because of this property of Range, it can easily disrupt the balance of games. Given enough time, a patient player might construct an large army of long-ranged units that knock-out enemy units before receiving any return fire, instantly spelling defeat for his opponent. (I’ve seen this happen in many Tower War games, including my own Expansion. But this is not at all an uncommon phenomenon.)

**Conclusion**

So basically, at this point, it should be obvious that besides collision size, formation and range can impact the effectiveness of a flank.