This problem isn't based on a role-playing game, but rather on a tabletop wargame, but it is still too good to pass up.
The game this problem is based on is Warmachine. Warmachine is a wargame in the same vein as Warhammer Fantrasy or Warhammer 40k, where you have miniatures that you move around on a board measuring distances rather than on a square or hex grid. However, Warmachine has several features that make it so I like it more than those other games:
1. There are fewer models you have to put together to form a decent army, and each model has fewer pieces.
2. There is more variety in units - each different type of unit has unique special powers. This makes the game much more interesting and more strategic because you have to look at what the opponent has brought to the table (you are allowed to look at the "stat cards" that have the opponents' units' stats and powers on them) and figure out how best to counter their powers with your own. Also there is more strategy in army selection as you try to put together an army that has powers that complement each other. For example one very useful combo is the "Bile Thrall", which applies a "corrosion" effect to targets it hits with its Bile Cannon, combined with the "Cankerworm," a large worm-shaped "warjack" (i.e. battle robot) which has an Ablation ability that allows it to ignore half the target's armor when it hits an enemy unit that has corrosion on it. In one game I successfully used this combo to kill an enemy warjack in one turn that was so heavily armored it would have been very difficult to kill any other way. Unfortunately I then made a tactical blunder: I left my "warcaster" (the army's leader) exposed in a place where the enemy could use one of his last remaining units to charge and kill him.
Anyway this is an RPG Math post so let's get right to the puzzle:
Problem 8: "Focus Fire!"
In Warmachine, there are some units (like squads of infantry) that are composed of lots of identical models. Some of these units have the "Combined Melee Attack" or "Combined Ranged Attack" special ability. This special ability allows the unit to, rather than having each model in the unit attack separately and make separate attack and damage rolls, combine several models' attacks into one attack with bonuses to the attack and damage rolls.
When using combined attacks, the player can choose how to group the models into attacks. For example, if a unit had 8 models, the player could choose to make 8 separate attacks, to make one attack that combined all 8 models, to make two attacks using 3 models each and one attack using the remaining 2 models, etc.
Assume that the unit has N models, and the player's goal is to maximize the total expected amount of damage done to the target. Let F(x) be the expected damage done from one attack with x models. Suppose you are given the values of F(x) for each value of x between 1 and N inclusive. Find a polynomial-time algorithm* to compute the best possible grouping.
Hint: Let G_i(j) be the best possible expected damage using j models in groups of no more than i each. Think about how to calculate the values of G_i if you already know the values of G_(i-1).
The solution is here.
*This means that the running time of the algorithm is bounded by A(n^B) for some constants A and B.
Wednesday, September 30, 2009
Wednesday, September 23, 2009
RPG Math - Problem 7
I already gave you one problem about algorithms, so it's time to give you a problem related to what I am studying in the other class I am taking this semester - combinatorics.
Problem 7: By Our Powers Combined
In the Xbox 360 game "Marvel: Ultimate Alliance 2," the player controls a team of superheroes as they battle evil. One of the key weapons in this fight is "Fusion" attacks, which are special attacks that combine two heroes' superpowers. Each pair of heroes has a Fusion attack., and when the player chooses to use a Fusion attack he chooses which two heroes to do the attack with. (For example, a team of 4 would have 6 different possible pairings of heroes and thus 6 different Fusion attacks.) There are three types of Fusion attacks: "Targeted," which are attacks that do a lot of damage to a single target (useful for fighting bosses), "Clearing", which attack all enemies in a wide area (useful for clearing out large groups of enemies), and "Guided", which allows the player to steer the attack after it fires to sweep up as many enemies as possible in the attack.
Since every pair of heroes has a Fusion attack, this situation can be represented as a complete graph with the vertices representing heroes, the edges representing pairs of heroes, and each edge labeled with what kind of Fusion attack that pair has.
There are 24 heroes in the game, and the player can bring 4 of them into battle at a time. Show that it is not possible to assign Fusion types to pairs of heroes in such a way that no matter what team of 4 the player chooses, he will always have at least one of each kind of Fusion attack available.
Major Hint: If there were only 6 heroes in the game, teams only consisted of 3 heroes, and there were only two types of fusions, then the problem would be the special case of Ramsey's theorem described in the first "Example" in the link, and there would be no way to do it. You may use this result in solving the problem, and the technique used to solve the problem is very similar to the technique used in proving that result.
The solution is here.
Problem 7: By Our Powers Combined
In the Xbox 360 game "Marvel: Ultimate Alliance 2," the player controls a team of superheroes as they battle evil. One of the key weapons in this fight is "Fusion" attacks, which are special attacks that combine two heroes' superpowers. Each pair of heroes has a Fusion attack., and when the player chooses to use a Fusion attack he chooses which two heroes to do the attack with. (For example, a team of 4 would have 6 different possible pairings of heroes and thus 6 different Fusion attacks.) There are three types of Fusion attacks: "Targeted," which are attacks that do a lot of damage to a single target (useful for fighting bosses), "Clearing", which attack all enemies in a wide area (useful for clearing out large groups of enemies), and "Guided", which allows the player to steer the attack after it fires to sweep up as many enemies as possible in the attack.
Since every pair of heroes has a Fusion attack, this situation can be represented as a complete graph with the vertices representing heroes, the edges representing pairs of heroes, and each edge labeled with what kind of Fusion attack that pair has.
There are 24 heroes in the game, and the player can bring 4 of them into battle at a time. Show that it is not possible to assign Fusion types to pairs of heroes in such a way that no matter what team of 4 the player chooses, he will always have at least one of each kind of Fusion attack available.
Major Hint: If there were only 6 heroes in the game, teams only consisted of 3 heroes, and there were only two types of fusions, then the problem would be the special case of Ramsey's theorem described in the first "Example" in the link, and there would be no way to do it. You may use this result in solving the problem, and the technique used to solve the problem is very similar to the technique used in proving that result.
The solution is here.
Saturday, September 19, 2009
Breaking News: Dungeons & Dragons Evidence of Socialist Takeover Plot
Recently, many conservatives have accused President Barack Obama of trying to turn the United States into a socialist country. Although the "liberal-elite" mainstream media have so far refused to report on this shocking development, there's yet another area that has been infiltrated by socialist propaganda - Dungeons and Dragons.
Yesterday during my Dungeons and Dragons game my character got killed. Since the death panel decided that my character's "level of adventuring productivity" wasn't high enough to warrant spending scarce health care resources on resurrecting him*, I had to create a new character. The new character I am planning to create is an "artificer" - a healer class with an unusual healing ability, which requires some explanation. In D+D, each character has a limited number of "healing surges." Most healing powers require the recipient of the healing to spend a healing surge, and once a character runs out of healing surges he can no longer be healed (until he takes an "extended rest" which resets his healing surges)**. The Artificer's healing power works differently - his healing doesn't require the recipient to spend a healing surge, but at the end of the battle the healing power must be recharged, which requires a character (any character in the party) to spend a healing surge. This effectively allows the character to pool healing resources between his party members, similar to a socialized medicine system. (Just like in real life, this socialized medicine system actually works pretty well.)
Also, my college roleplaying club has a "club campaign" of D+D, and anyone who wants to can go to each adventure. But of course this would lead to a problem because people who go to more adventures would go up in level and gain treasure faster, and if you were to start in the middle then you would be at low level and have a hard time contributing to the group. The way they solve this problem is classic socialism. Everyone levels at the same rate regardless of how often they play - on the campaign web site it says what level the characters are so you create a character of that level. There is also an "audit value" that indicates how much treasure you are supposed to have, and if you fall below that amount then you can ask a DM to "audit" your character, which gives you an amount of treasure to get your total treasure value up to the audit level. A similar system is used on a larger scale in the RPGA, which is a set of "official" adventures published by Wizards of the Coast, the company that makes D+D. There are "official RPGA events" where you go to play, and sign in, and after signing in a certain number of times you can get "rewards cards" mailed to you that give you special bonuses in play (like being allowed to reroll a die roll.) Or at least that used to be the way they did it - they eventually changed it so the rewards cards are on a freely downloadable PDF, so you can just print them all out and bring them to the game (although you are only allowed to use a certain number of cards per game, depending on your character's level).
Also one more thing that may be interesting, although only tangentially related to socialism. In D+D there are six character attributes - Strength, Constitution, Dexterity, Intelligence, Wisdom, and Charisma. Different character classes require different attributes to work well - for example fighters require Strength, wizards require Intelligence, etc. Additionally, there are different "races" like human, elf, etc. Each race has two attributes that it gets a +2 bonus to (except humans, who only have one +2 bonus but can apply it to any attribute). This means that races that don't have a bonus to a particular character class's attribute are weaker choices for that character class. One common goal of "house rules" discussed on D+D fan sites is aimed at eliminating this disparity by changing how racial stat bonuses are determined, like by allowing players to move one of their stat bonuses to a different stat. In other words, it's like an affirmative action system. And more than that, it's an affirmative action system based on a point system***.
*This isn't the actual reason. In reality the DM told me that I could have the character revived by our party's employer next session, or I could create a new character. I chose to create a new character because I wanted to try out the Artificer class. But I'll still try to use the explanation above as an "in-game" explanation for why my character couldn't get revived.
**This may seem unnecessarily complicated, but there's actually a good reason for it. In the 3rd edition of D+D, there were only two character classes that could do healing, and their healing spells took a "standard action" to cast. (Characters get one standard action per turn, and standard actions are used to do most things like spellcasting and attacking.) This basically meant that you had to have one of those characters in your party to provide healing, but that playing those characters was often uninteresting because in tough fights you would spend most of your actions just healing others rather than doing anything to the enemy - hence they were sometimes called "hit point vending machines." In 4th edition, which is what we are playing, they fixed these problems by giving more classes healing abilities, giving everyone the ability to heal themselves to full at the end of the fight, and making most healing spells a "minor action" which means that you can use a healing spell and attack in the same turn. But of course this created another problem - a party full of healers would be almost unstoppable because they could keep healing each other while still pumping out just as much damage on the enemy. Sot the healing surge system is designed to limit the amount of healing one character can get.
***Another instance of something similar was in Planetside, a massively multiplayer shooter. Players got rewarded with experience points when they participated in a successful assault on an enemy base, so if one side started losing, the players would realize they were unlikely to win and pull out, moving to another front looking for more experience point potential in other areas. This meant that once one side started to win, they would usually continue to win, and it was hard to find a battle in serious contention for very long. The solution? Give the side with fewer people in a particular area bonus health and experience points to encourage them to stay. This of course led to complaints that the game was "becoming most like the University of Michigan every day." (At the time, the University of Michigan was in the news due to its controversial affirmative action policy, later overturned by the courts, that rated applicants according to a point system gave members of underrepresented races bonus points during the admission process.)
Yesterday during my Dungeons and Dragons game my character got killed. Since the death panel decided that my character's "level of adventuring productivity" wasn't high enough to warrant spending scarce health care resources on resurrecting him*, I had to create a new character. The new character I am planning to create is an "artificer" - a healer class with an unusual healing ability, which requires some explanation. In D+D, each character has a limited number of "healing surges." Most healing powers require the recipient of the healing to spend a healing surge, and once a character runs out of healing surges he can no longer be healed (until he takes an "extended rest" which resets his healing surges)**. The Artificer's healing power works differently - his healing doesn't require the recipient to spend a healing surge, but at the end of the battle the healing power must be recharged, which requires a character (any character in the party) to spend a healing surge. This effectively allows the character to pool healing resources between his party members, similar to a socialized medicine system. (Just like in real life, this socialized medicine system actually works pretty well.)
Also, my college roleplaying club has a "club campaign" of D+D, and anyone who wants to can go to each adventure. But of course this would lead to a problem because people who go to more adventures would go up in level and gain treasure faster, and if you were to start in the middle then you would be at low level and have a hard time contributing to the group. The way they solve this problem is classic socialism. Everyone levels at the same rate regardless of how often they play - on the campaign web site it says what level the characters are so you create a character of that level. There is also an "audit value" that indicates how much treasure you are supposed to have, and if you fall below that amount then you can ask a DM to "audit" your character, which gives you an amount of treasure to get your total treasure value up to the audit level. A similar system is used on a larger scale in the RPGA, which is a set of "official" adventures published by Wizards of the Coast, the company that makes D+D. There are "official RPGA events" where you go to play, and sign in, and after signing in a certain number of times you can get "rewards cards" mailed to you that give you special bonuses in play (like being allowed to reroll a die roll.) Or at least that used to be the way they did it - they eventually changed it so the rewards cards are on a freely downloadable PDF, so you can just print them all out and bring them to the game (although you are only allowed to use a certain number of cards per game, depending on your character's level).
Also one more thing that may be interesting, although only tangentially related to socialism. In D+D there are six character attributes - Strength, Constitution, Dexterity, Intelligence, Wisdom, and Charisma. Different character classes require different attributes to work well - for example fighters require Strength, wizards require Intelligence, etc. Additionally, there are different "races" like human, elf, etc. Each race has two attributes that it gets a +2 bonus to (except humans, who only have one +2 bonus but can apply it to any attribute). This means that races that don't have a bonus to a particular character class's attribute are weaker choices for that character class. One common goal of "house rules" discussed on D+D fan sites is aimed at eliminating this disparity by changing how racial stat bonuses are determined, like by allowing players to move one of their stat bonuses to a different stat. In other words, it's like an affirmative action system. And more than that, it's an affirmative action system based on a point system***.
*This isn't the actual reason. In reality the DM told me that I could have the character revived by our party's employer next session, or I could create a new character. I chose to create a new character because I wanted to try out the Artificer class. But I'll still try to use the explanation above as an "in-game" explanation for why my character couldn't get revived.
**This may seem unnecessarily complicated, but there's actually a good reason for it. In the 3rd edition of D+D, there were only two character classes that could do healing, and their healing spells took a "standard action" to cast. (Characters get one standard action per turn, and standard actions are used to do most things like spellcasting and attacking.) This basically meant that you had to have one of those characters in your party to provide healing, but that playing those characters was often uninteresting because in tough fights you would spend most of your actions just healing others rather than doing anything to the enemy - hence they were sometimes called "hit point vending machines." In 4th edition, which is what we are playing, they fixed these problems by giving more classes healing abilities, giving everyone the ability to heal themselves to full at the end of the fight, and making most healing spells a "minor action" which means that you can use a healing spell and attack in the same turn. But of course this created another problem - a party full of healers would be almost unstoppable because they could keep healing each other while still pumping out just as much damage on the enemy. Sot the healing surge system is designed to limit the amount of healing one character can get.
***Another instance of something similar was in Planetside, a massively multiplayer shooter. Players got rewarded with experience points when they participated in a successful assault on an enemy base, so if one side started losing, the players would realize they were unlikely to win and pull out, moving to another front looking for more experience point potential in other areas. This meant that once one side started to win, they would usually continue to win, and it was hard to find a battle in serious contention for very long. The solution? Give the side with fewer people in a particular area bonus health and experience points to encourage them to stay. This of course led to complaints that the game was "becoming most like the University of Michigan every day." (At the time, the University of Michigan was in the news due to its controversial affirmative action policy, later overturned by the courts, that rated applicants according to a point system gave members of underrepresented races bonus points during the admission process.)
Sunday, September 13, 2009
RPG Math - Problem 6
We haven't had one of these in a while. It's time for another round of...
Problem 6: Taking Inventory
This problem is related to algorithms. For this problem, we will need to introduce some new terminology. This new terminology may appear in other algorithm-related problems in the future.
A decision problem is a problem which asks, given a certain input, whether that input satisfies a certain condition. For example, the Boolean satisfiability problem asks, given a Boolean formula (such as "A and B or (not (C and A))" whether or not there exists an assignment of "true" and "false" values to the variables (A, B, and C in this case) that will make the result of the formula "true". The independent set problem asks, given a graph G and an integer L, whether it is possible to choose L vertices such that no two of the vertices chosen have an edge between them.
An instance of a decision problem means a particular input for the decision problem. For example an "instance" of the Boolean satisfiability problem means a particular Boolean formula. An instance of a decision problem of course has one answer, "true" or "false".
To reduce a decision problem P to another decision problem Q means to show a simple* way to, given an instance of problem P, find an instance of problem Q that has the same answer. For example, consider the following two problems:
P: Given a graph G and an integer N, is there a way to color the vertices of G with N colors so that no edge of G has endpoints that are the same color?
Q: Given a partition M of the plane into regions, and an integer N, is there a way to color the regions of M in such a way that no two adjacent regions have the same color?
In this example, there is a way to reduce Q to P - given an instance of Q, create a graph with one vertex for each region, with edges between vertices corresponding to adjacent regions, and feed that to P. There is not, however, a corresponding way to reduce P to Q. (For instance, if N >= 4, then the answer to Q is always yes, but the same is not true of P.)
A problem P is equivalent to a problem Q if P can be reduced to Q and Q can be reduced to P.
---
Now with all the terminology taken care of, it's time to get to the problem.
Many computer games use a "grid inventory" system. This means that items that the character is carrying are arranged in a grid, with larger items taking up more space. For instance, a small item such as a gem might only take up one square of the grid, while a large item such as a suit of armor might take up, say, a 3x4 area of the grid. All items your character is carrying must fit in the grid, so you cannot pick up an item if you can't fit it in the grid. This image gives an example of what an inventory grid looks like. (If you can't see the image, hover over the line "NWN_inventory.jpg image by..." and click the "Zoom in" item on the menu bar that appears.)
The Inventory Grid Problem (IGP) is as follows: Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid? (Note: Objects cannot be rotated.)
Just today I came into a real life situation that is very similar to the inventory grid situation. I have just bought miniatures for a miniatures combat game called Warmachine. In order to safely transport the miniatures without them being damaged, they sell large blocks of foam that are perforated in a grid pattern (see this image for an example) and you can remove the squares of foam in order to insert your miniatures. This way each miniature is stored separately and surrounded by a cushion of foam. This image is an example of foam being used to store miniatures.
Suppose that you have a whole bunch of miniatures, and a block of foam of a given size, and you want to see if it is possible to fit all the miniatures into that block. This problem is similar to the Inventory Grid Problem above, with the exception that objects cannot be adjacent to each other - there must be a "cushion" or "buffer" of at least one square between each object. Thus, we have the...
Buffered Inventory Grid Problem (BIGP): Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid such that no two objects are adjacent? (Again, objects cannot be rotated. While this isn't very realistic in terms of the miniatures problem, it makes the problems below much simpler.)
-----
There are two problems here:
6.1. Show that the Inventory Grid Problem and the Buffered Inventory Grid Problem are equivalent.
(Hint. Reducing BIGP to IGP is fairly straightforward. Reducing IGP to BIGP is a little trickier.)
6.2. Show that the bin-packing problem** can be reduced to the Inventory Grid Problem. (This implies that IGP is NP-complete, meaning that there is (almost certainly) no algorithm that solves it in a time polynomial in the length of the input. I might go into further detail on this topic in future questions.
Solutions are here.
* "Simple" means "can be done in a time polynomial in the length of the input."
** The problem as described in the link is the optimization variant of the problem - find the minimum number of bins necessary. The decision problem variant of the problem is: given a number N, can you do it with N or fewer bins (thus the answer is "yes" or "no" as described above). Since we're dealing with decision problems here this is the one you want to use.
Problem 6: Taking Inventory
This problem is related to algorithms. For this problem, we will need to introduce some new terminology. This new terminology may appear in other algorithm-related problems in the future.
A decision problem is a problem which asks, given a certain input, whether that input satisfies a certain condition. For example, the Boolean satisfiability problem asks, given a Boolean formula (such as "A and B or (not (C and A))" whether or not there exists an assignment of "true" and "false" values to the variables (A, B, and C in this case) that will make the result of the formula "true". The independent set problem asks, given a graph G and an integer L, whether it is possible to choose L vertices such that no two of the vertices chosen have an edge between them.
An instance of a decision problem means a particular input for the decision problem. For example an "instance" of the Boolean satisfiability problem means a particular Boolean formula. An instance of a decision problem of course has one answer, "true" or "false".
To reduce a decision problem P to another decision problem Q means to show a simple* way to, given an instance of problem P, find an instance of problem Q that has the same answer. For example, consider the following two problems:
P: Given a graph G and an integer N, is there a way to color the vertices of G with N colors so that no edge of G has endpoints that are the same color?
Q: Given a partition M of the plane into regions, and an integer N, is there a way to color the regions of M in such a way that no two adjacent regions have the same color?
In this example, there is a way to reduce Q to P - given an instance of Q, create a graph with one vertex for each region, with edges between vertices corresponding to adjacent regions, and feed that to P. There is not, however, a corresponding way to reduce P to Q. (For instance, if N >= 4, then the answer to Q is always yes, but the same is not true of P.)
A problem P is equivalent to a problem Q if P can be reduced to Q and Q can be reduced to P.
---
Now with all the terminology taken care of, it's time to get to the problem.
Many computer games use a "grid inventory" system. This means that items that the character is carrying are arranged in a grid, with larger items taking up more space. For instance, a small item such as a gem might only take up one square of the grid, while a large item such as a suit of armor might take up, say, a 3x4 area of the grid. All items your character is carrying must fit in the grid, so you cannot pick up an item if you can't fit it in the grid. This image gives an example of what an inventory grid looks like. (If you can't see the image, hover over the line "NWN_inventory.jpg image by..." and click the "Zoom in" item on the menu bar that appears.)
The Inventory Grid Problem (IGP) is as follows: Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid? (Note: Objects cannot be rotated.)
Just today I came into a real life situation that is very similar to the inventory grid situation. I have just bought miniatures for a miniatures combat game called Warmachine. In order to safely transport the miniatures without them being damaged, they sell large blocks of foam that are perforated in a grid pattern (see this image for an example) and you can remove the squares of foam in order to insert your miniatures. This way each miniature is stored separately and surrounded by a cushion of foam. This image is an example of foam being used to store miniatures.
Suppose that you have a whole bunch of miniatures, and a block of foam of a given size, and you want to see if it is possible to fit all the miniatures into that block. This problem is similar to the Inventory Grid Problem above, with the exception that objects cannot be adjacent to each other - there must be a "cushion" or "buffer" of at least one square between each object. Thus, we have the...
Buffered Inventory Grid Problem (BIGP): Given an NxM inventory grid, and a set of objects with associated sizes (e.g. you have an 8x10 grid, and you have one 4x6 object, three 3x3 objects, five 2x1 objects, etc.) is it possible to fit all the objects in the grid such that no two objects are adjacent? (Again, objects cannot be rotated. While this isn't very realistic in terms of the miniatures problem, it makes the problems below much simpler.)
-----
There are two problems here:
6.1. Show that the Inventory Grid Problem and the Buffered Inventory Grid Problem are equivalent.
(Hint. Reducing BIGP to IGP is fairly straightforward. Reducing IGP to BIGP is a little trickier.)
6.2. Show that the bin-packing problem** can be reduced to the Inventory Grid Problem. (This implies that IGP is NP-complete, meaning that there is (almost certainly) no algorithm that solves it in a time polynomial in the length of the input. I might go into further detail on this topic in future questions.
Solutions are here.
* "Simple" means "can be done in a time polynomial in the length of the input."
** The problem as described in the link is the optimization variant of the problem - find the minimum number of bins necessary. The decision problem variant of the problem is: given a number N, can you do it with N or fewer bins (thus the answer is "yes" or "no" as described above). Since we're dealing with decision problems here this is the one you want to use.
Wednesday, September 9, 2009
Politics as usual in Illinois, part 2
According to the Associated Press, Rod Blagojevich has come out with a new book in which he claims he did not intend to take money in exchange for appointing someone to fill Obama's Senate seat.
Instead, he claims, his intention was to appoint Illinois Attorney General Lisa Madigan to the senate seat, in exchange for a deal where her father, Illinois House Speaker Michael Madigan, would push through public works and health care legislation that Blagojevich wanted.
In other words, according to him, it's okay to be corrupt as long as it's all done with taxpayer money.
Instead, he claims, his intention was to appoint Illinois Attorney General Lisa Madigan to the senate seat, in exchange for a deal where her father, Illinois House Speaker Michael Madigan, would push through public works and health care legislation that Blagojevich wanted.
In other words, according to him, it's okay to be corrupt as long as it's all done with taxpayer money.
Saturday, September 5, 2009
Independent Study
This semester I have decided to do an independent study with Professor Jeff Erickson.
The project we are working on (like several of the projects I have worked on in the past) involves numerical simulations of physical systems. Consider a function F(x,t) which represents the value of a particular physical variable at a particular point in space (x) at a given time (t). For example, in an application modeling heat transfer, F could represent the temperature at a given point in the material. The function F is defined by a set of initial conditions (at t=0) and then a set of differential equations that define how the value of F at each point x changes over time. The goal is to calculate (or at least estimate) the values of F over time.
Of course there are an infinite number of different values of X, and so an infinite number of variables to track. In order to solve this problem it is necessary to divide the region of interest up into a large number of smaller "cells," and keep track of one value at each cell. The pattern of cells is referred to as a "mesh". In a one dimensional case the "mesh" is trivial, but in a two dimensional problem there are lots of different mesh patterns, such as a square grid or a triangular grid. (I worked on a project with exactly this theme several years ago.)
One way of understanding the point of the "mesh" is by analogy to wargames like Dungeons + Dragons. In a real battle, movement is continuous, but in the game it is necessary to approximate that continuous movement by a discrete grid. And the shape of that grid (square in D+D, hexagonal in many other war games) is like the "mesh", and each point in that mesh is dealt with separately.
Of course in real life time is also continuous, so there are an infinite number of points in time. So just like with space, it is necessary to approximate the continuous time interval with a set of discrete points in time.The standard way of solving these problems doing this is to choose a "time step" dt - so for example if dt=6 seconds, you calculate the values of F at t=6 based on the values at t=0, then repreat the process to get the values at t=12 from t=6, and so on. (To continue with the D+D analogy, in a real life battle things are happening continuously in real-time, but the game divides up the time into a series of discrete "combat rounds".)
Now we come to the main part of our project. The part of our project that is different is to, rather than choose a mesh once and do a series of iterations where the time increases by dt each time, you keep track of a separate value of t for each vertex in the mesh, and increase the t value one vertex at a time. The advantage of doing this is that in many applications, there's a known maximum speed at which effects can propagate, and you can use this to limit the number of simultaneous equations that it is necessary to solve. Suppose that the equations are modeling sound waves, and the speed of sound in the material in question is 1000 meters per second, and suppose that the cells are spaced 1 meter apart. Then if, you use a dt of 0.001 seconds, then in one time step effects can propagate at most one mesh cell, so at each step rather than having to solve simultaneous equations for all the cells in the mesh, you only have to do so for one cell and its nearest neighbors, because those are the only cells that can affect the given vertex. This can significantly speed up the algorithm, and it also allows you to take better advantage of multiple processors, because different processors can be working on different parts of the mesh.
As for the D+D analogy for that, this is more of a stretch but here goes. Let's say you have a gigantic battle with 100 different characters arranged in a 10x10 array, and let's say each character only has powers that can affect other characters adjacent to him, and none of them can move.* Of course this battle is going to be slow going because once one person declares his actions he has to wait for 99 other characters to declare their actions before they can go do them and start theire next round. But as it turns out you don't need to keep everyone in sync like that - you can have some players start their second and subsequent rounds even before everyone finishes their first round. This is possible for the slow speed of interaction - since it will take nine rounds for anything happening in, say, the top left corner of the board to affect the character in he bottom right corner, one of those corners can be up to nine rounds "ahead" of the other and the game will still work just as normal. Basically, let's say that the guy in the top left corner just finished his 10th round while the guy in the bottom right corner is still deciding on his action for the 5th round. This will still work because the bottom right guy's 5th round action won't affect the first guy until at least the 14th round (it has to get through nine intervening spaces at one space per round), so he doesn't need to know about it yet. The condition that the "time difference" between two cells is no greater than the time it takes for information to move between them is known as the "causality" constraint.
However, there is an important complication. It is possible in certain circumstances, depending on how the mesh is laid out, to get "stuck" - i.e. there is no way to progress any vertex without violating a causality constraint.** If this happens then you have to (at least temporarily) go back to the original method of pushing up all the vertices at once*** (this is analogous to having everyone take their turns in sync, in the previous analogy). The problem is how to progress in such a way that you avoid getting stuck. There are also lots of other complications, like it you want to refine (i.e. make denser) a part of the mesh in the middle of the program execution, etc.
There is already a program that does this, and a paper about it, for the case of two dimensional meshes. The part that remains to be done is doing this for three dimensional meshes. Some of the algorithm design work is already done so a lot of the work is just coding it up (but after that we'll get to the other parts where the algorithms that are needed are not known yet).
In Erickson's words, "most computer science Ph.D. students can't program their way out of a wet paper bag, and that applies to most computer science professors as well.****" Since I am not one of those "most computer science Ph.D. students" he thought it would be a good idea for me to work for him.
---
* This analogy is technically inaccurate because in D+D, each player's turn happens sequentially, so A can do something to affect B, then that affects what B does, which affects C, so C chooses an action which affects D, and so on, all in the space of one round. For this analogy to work you have to assume that all turns happen simultaneously so that each link in the chain requires another round.
** It might appear that it is never possible to get stuck - if you increment the t value on the vertex that currently has the lowest t value, then you're not increasing any gaps. The explanation is that my description is significantly simplified - in reality it's not actually about the difference between the t values of the vertices, it has to do with the slopes of the sides of the "cells" in the n+1 dimensional space consisting of the n space dimensions plus the time dimension. But I couldn't figure out how to explain that part concisely and this post is long enough as it is.
***I'm actually not 100% sure how this part works. I just talked to Erickson yesterday and haven't read the papers yet.
****Erickson is not the first of my professors to express a similar sentiment. University of Maryland professor Samir Khuller said that when people find out that he is a computer science professor, sometimes that ask him to help fix their computer, and he says that "I can't even fix my own computer, how can I fix yours?" Michelle Hugue even once said that she "hates computers."
The project we are working on (like several of the projects I have worked on in the past) involves numerical simulations of physical systems. Consider a function F(x,t) which represents the value of a particular physical variable at a particular point in space (x) at a given time (t). For example, in an application modeling heat transfer, F could represent the temperature at a given point in the material. The function F is defined by a set of initial conditions (at t=0) and then a set of differential equations that define how the value of F at each point x changes over time. The goal is to calculate (or at least estimate) the values of F over time.
Of course there are an infinite number of different values of X, and so an infinite number of variables to track. In order to solve this problem it is necessary to divide the region of interest up into a large number of smaller "cells," and keep track of one value at each cell. The pattern of cells is referred to as a "mesh". In a one dimensional case the "mesh" is trivial, but in a two dimensional problem there are lots of different mesh patterns, such as a square grid or a triangular grid. (I worked on a project with exactly this theme several years ago.)
One way of understanding the point of the "mesh" is by analogy to wargames like Dungeons + Dragons. In a real battle, movement is continuous, but in the game it is necessary to approximate that continuous movement by a discrete grid. And the shape of that grid (square in D+D, hexagonal in many other war games) is like the "mesh", and each point in that mesh is dealt with separately.
Of course in real life time is also continuous, so there are an infinite number of points in time. So just like with space, it is necessary to approximate the continuous time interval with a set of discrete points in time.The standard way of solving these problems doing this is to choose a "time step" dt - so for example if dt=6 seconds, you calculate the values of F at t=6 based on the values at t=0, then repreat the process to get the values at t=12 from t=6, and so on. (To continue with the D+D analogy, in a real life battle things are happening continuously in real-time, but the game divides up the time into a series of discrete "combat rounds".)
Now we come to the main part of our project. The part of our project that is different is to, rather than choose a mesh once and do a series of iterations where the time increases by dt each time, you keep track of a separate value of t for each vertex in the mesh, and increase the t value one vertex at a time. The advantage of doing this is that in many applications, there's a known maximum speed at which effects can propagate, and you can use this to limit the number of simultaneous equations that it is necessary to solve. Suppose that the equations are modeling sound waves, and the speed of sound in the material in question is 1000 meters per second, and suppose that the cells are spaced 1 meter apart. Then if, you use a dt of 0.001 seconds, then in one time step effects can propagate at most one mesh cell, so at each step rather than having to solve simultaneous equations for all the cells in the mesh, you only have to do so for one cell and its nearest neighbors, because those are the only cells that can affect the given vertex. This can significantly speed up the algorithm, and it also allows you to take better advantage of multiple processors, because different processors can be working on different parts of the mesh.
As for the D+D analogy for that, this is more of a stretch but here goes. Let's say you have a gigantic battle with 100 different characters arranged in a 10x10 array, and let's say each character only has powers that can affect other characters adjacent to him, and none of them can move.* Of course this battle is going to be slow going because once one person declares his actions he has to wait for 99 other characters to declare their actions before they can go do them and start theire next round. But as it turns out you don't need to keep everyone in sync like that - you can have some players start their second and subsequent rounds even before everyone finishes their first round. This is possible for the slow speed of interaction - since it will take nine rounds for anything happening in, say, the top left corner of the board to affect the character in he bottom right corner, one of those corners can be up to nine rounds "ahead" of the other and the game will still work just as normal. Basically, let's say that the guy in the top left corner just finished his 10th round while the guy in the bottom right corner is still deciding on his action for the 5th round. This will still work because the bottom right guy's 5th round action won't affect the first guy until at least the 14th round (it has to get through nine intervening spaces at one space per round), so he doesn't need to know about it yet. The condition that the "time difference" between two cells is no greater than the time it takes for information to move between them is known as the "causality" constraint.
However, there is an important complication. It is possible in certain circumstances, depending on how the mesh is laid out, to get "stuck" - i.e. there is no way to progress any vertex without violating a causality constraint.** If this happens then you have to (at least temporarily) go back to the original method of pushing up all the vertices at once*** (this is analogous to having everyone take their turns in sync, in the previous analogy). The problem is how to progress in such a way that you avoid getting stuck. There are also lots of other complications, like it you want to refine (i.e. make denser) a part of the mesh in the middle of the program execution, etc.
There is already a program that does this, and a paper about it, for the case of two dimensional meshes. The part that remains to be done is doing this for three dimensional meshes. Some of the algorithm design work is already done so a lot of the work is just coding it up (but after that we'll get to the other parts where the algorithms that are needed are not known yet).
In Erickson's words, "most computer science Ph.D. students can't program their way out of a wet paper bag, and that applies to most computer science professors as well.****" Since I am not one of those "most computer science Ph.D. students" he thought it would be a good idea for me to work for him.
---
* This analogy is technically inaccurate because in D+D, each player's turn happens sequentially, so A can do something to affect B, then that affects what B does, which affects C, so C chooses an action which affects D, and so on, all in the space of one round. For this analogy to work you have to assume that all turns happen simultaneously so that each link in the chain requires another round.
** It might appear that it is never possible to get stuck - if you increment the t value on the vertex that currently has the lowest t value, then you're not increasing any gaps. The explanation is that my description is significantly simplified - in reality it's not actually about the difference between the t values of the vertices, it has to do with the slopes of the sides of the "cells" in the n+1 dimensional space consisting of the n space dimensions plus the time dimension. But I couldn't figure out how to explain that part concisely and this post is long enough as it is.
***I'm actually not 100% sure how this part works. I just talked to Erickson yesterday and haven't read the papers yet.
****Erickson is not the first of my professors to express a similar sentiment. University of Maryland professor Samir Khuller said that when people find out that he is a computer science professor, sometimes that ask him to help fix their computer, and he says that "I can't even fix my own computer, how can I fix yours?" Michelle Hugue even once said that she "hates computers."
Subscribe to:
Posts (Atom)