Problem 12: Energy Crisis
In the collectible card game "Magic", players get "land" cards which they can play to generate "mana," which represents magical energy that can be used to play other cards which represent magical spells. Each land card can be "tapped" for one mana per turn, and different cards cost different amounts of mana to play. If you get lots of cards but not enough mana to play any of them that is called being "mana screwed." Unhinged, a "joke" Magic card set, contains a card called "Mana Screw", which allows the user to (as many times as he wants to) spend one mana to flip a coin, and if he wins the coin flip he gets two mana (for a net gain of one.)
Problem 12.1:
Suppose that a player has X mana, and he has a spell that he wants to play that costs Y mana (where Y is greater than X). He uses Mana Screw's power repeatedly until he either (a) runs out of mana, or (b) gets enough mana to cast his spell. What is the probability that he will get enough mana to cast the spell.
Problem 12.2:
There exists another Magic card called Krark's Thumb (this is not a joke card) that allows the user to, whenever he is called upon to flip a coin, flip two coins and ignore one. Thus if a player used Krark's Thumb he would have a 3/4 chance of winning each coin flip, rather than 1/2. Suppose that such a player had one mana, and wanted to play Gleemax, another "joke" card that costs 1,000,000 mana. He again continually used Mana Screw's power until he either ran out of mana or got enough to play Gleemax. What is the probability of success? (You can take the limit as Gleemax's cost approaches infinity.)
(Hint for both problems: Let f(x) be the probability of success starting from x mana, and find a recurrence relation for x.)
The solution is here.
Tuesday, December 8, 2009
Monday, November 30, 2009
Gaming Math - Problem 11
At the board game night no Sundays at the local game store there is guy who has been coming in to playtest a new card game he invented. The game is based off of computer fighting games like Mortal Kombat. The way it works is as follows: Each player chooses a character, and each character has a deck of "attack cards" and "defense cards." The players take turns attacking and defending (so the first turn player 1 attacks and player 2 defends, then the second turn player 2 attacks and player 1 defends, etc.) The sequence of play in each turn goes as follows:
(1) The attacker draws attack cards until he has 5 attack cards in his hand; the defender draws defense cards until he has 3 defense cards in his hand.
(2) The attacker plays attack cards. Each attack card has three attributes: a "range" (high, medium, or low), a numerical "attack value" indicating how much damage the attack does, and a "level" (1, 2, or 3). The attacker can either play any one attack card as a basic attack, or he can play a combo. To play a combo the first card in the combo has to be level 1, then the second level 2, then the third (if it's there) level 3 (you can play either a 2 or 3 attack combo)
(3) The defender tries to block the attack. Each defense card is either a "High Block", "Medium Block", or "Low Block." In order to block the attack he has to play a block card that matches the range of the attack. If there is a combo attacks must be blocked in order. For example if it's a 3 hit combo, and he blocks the first and second attacks, the third attack still does its damage. If he doesn't block the first attack because he doesn't have a matching block card, he takes damage from all the attacks, and he can't block the second or third attacks even if he had a matching block card.
(4) The attacker can discard attack cards he doesn't want, and the defender can discard defense cards he doesn't want.
(In the actual game there are more complicated elements, like "counters" that let you turn your enemy's attack back on himself, "special moves" that let you power up your regular attack cards with special powers, and certain characters have special rules, etc. But for the purpose of this problem we are just using the elements above.)
----
Problem 11: You've Been Blocked
Consider the game above. Assume that the defense deck has an equal quantity of high, medium, and low block cards, and ignore finite deck size effects (i.e. assume that each time you draw a card from the defense deck, you have a 1/3 chance of getting each of the types of cards, regardless of what cards have already been drawn).
Problem 11a. If the defender has just drawn a new hand of three cards, what is the probability that he will successfully be able to block a 3 hit combo where each of the attacks has a different range? How about if all the attacks have the same range (e.g. 3 medium attacks)?
Problem 11b. Suppose the defender draws a new hand of three cards. What is the probability that if I attack with a single attack (e.g. a medium attack) he will be able to block it?
Problem 11c. Suppose I've just attacked with a single medium attack, he blocks it (thus using up the medium block card). If I attack him with another medium attack on his next turn (don't forget he gets to draw a new card to replace the block card he used up) what's the probability he will be able to block it? (Assume that the defender will always block an attack if he has a block card available.)
The solutions are here.
(1) The attacker draws attack cards until he has 5 attack cards in his hand; the defender draws defense cards until he has 3 defense cards in his hand.
(2) The attacker plays attack cards. Each attack card has three attributes: a "range" (high, medium, or low), a numerical "attack value" indicating how much damage the attack does, and a "level" (1, 2, or 3). The attacker can either play any one attack card as a basic attack, or he can play a combo. To play a combo the first card in the combo has to be level 1, then the second level 2, then the third (if it's there) level 3 (you can play either a 2 or 3 attack combo)
(3) The defender tries to block the attack. Each defense card is either a "High Block", "Medium Block", or "Low Block." In order to block the attack he has to play a block card that matches the range of the attack. If there is a combo attacks must be blocked in order. For example if it's a 3 hit combo, and he blocks the first and second attacks, the third attack still does its damage. If he doesn't block the first attack because he doesn't have a matching block card, he takes damage from all the attacks, and he can't block the second or third attacks even if he had a matching block card.
(4) The attacker can discard attack cards he doesn't want, and the defender can discard defense cards he doesn't want.
(In the actual game there are more complicated elements, like "counters" that let you turn your enemy's attack back on himself, "special moves" that let you power up your regular attack cards with special powers, and certain characters have special rules, etc. But for the purpose of this problem we are just using the elements above.)
----
Problem 11: You've Been Blocked
Consider the game above. Assume that the defense deck has an equal quantity of high, medium, and low block cards, and ignore finite deck size effects (i.e. assume that each time you draw a card from the defense deck, you have a 1/3 chance of getting each of the types of cards, regardless of what cards have already been drawn).
Problem 11a. If the defender has just drawn a new hand of three cards, what is the probability that he will successfully be able to block a 3 hit combo where each of the attacks has a different range? How about if all the attacks have the same range (e.g. 3 medium attacks)?
Problem 11b. Suppose the defender draws a new hand of three cards. What is the probability that if I attack with a single attack (e.g. a medium attack) he will be able to block it?
Problem 11c. Suppose I've just attacked with a single medium attack, he blocks it (thus using up the medium block card). If I attack him with another medium attack on his next turn (don't forget he gets to draw a new card to replace the block card he used up) what's the probability he will be able to block it? (Assume that the defender will always block an attack if he has a block card available.)
The solutions are here.
Wednesday, November 25, 2009
Trip to Chicago
Since there are no classes this week since it is Thanksgiving, I decided to go up to Chicago to see some sights there.
I got to the Illinois bus terminal on Monday morning and bought a ticket for the 11:00 Greyhound bus up to Chicago. Unfortunately there wasn't enough space on the bus for all of us so they had to bump me to the 12:00 bus. I knew planes could be overbooked but I had never heard of a bus being overbooked. Anyway on the way up there the bus broke down. Fortunately there was another Greyhound bus there to rescue us. By the time I had gotten up there and checked into the hotel it was already 4:00, and most of the attractions were closed. Instead I took the subway over to downtown here I could have dinner at the ESPN Zone and explore the rest of downtown where there's lots of shopping. I got a new winter coat (my old one was really worn out) and got a cool looking miniature RC helicopter from Brookstone. Also in Chicago there was a whole store that sold nothing but Legos. Here is a picture of the display outside:
All those things are made out of Legos. On Tuesday I went to the Museum of Science and Industry. There were some cool things there - in one of the activities we got the chance to use a "Human Patient Simulator" medical training dummy of the same kind as those actually used in medical schools. The way it worked was they showed us how to check for different vital signs (pulse, heart rate, breathing etc.) and then we were assigned to go up there, check the vital signs, and diagnoes the patient by matching the results to the results on a diagnosis chart we were given. Also while I was there I ran into Courtney Fontaine, one of the people that I took the comedy class from back at ComedySportz in DC. She now works at the science museum, and is also in another comedy group (not ComedySportz, although there is a ComedySportz in Chicago). She was having a performance that night and I went to see it. There were several comedy groups performing that night, and there were lots of funny parts. Courtney's group got the suggestion "gift-wrapping", and I thought it would be a boring suggestion but they went off on lots of funny tangents with it. The last group I gave the suggestion "Dungeons and Dragons" to, and I was actually quite impressed with their knowledge of D+D themes - they incorporated lots of classic D+D elements including traps, castles, wizards, and even "elemental powers" into their routine. The climax of the scene was funny - someone was talking about going to the "center" of a castle to find treasure, but someone else misheard it as "senator", and the scene then segued into a senator on a talk show whose shtick was "gratuitous profanity" - but since this is a family friendly blog I won't go into it any further.
Then on Wednesday, I first went to the Travisa office to drop off the materials for my trip to India, then went back to get my stuff from the hotel. There wasn't really enough time to go to another attraction so I just went to the train station (I figured I might have better luck on the train rather than the bus) and got there about an hour and a half before the train was scheduled to leave. It was a good thing I got there early because I got the last available ticket to Urbana-Champaign. The train left on time and only got back to Urbana-Champaign about 20 minutes after the scheduled time.
I got to the Illinois bus terminal on Monday morning and bought a ticket for the 11:00 Greyhound bus up to Chicago. Unfortunately there wasn't enough space on the bus for all of us so they had to bump me to the 12:00 bus. I knew planes could be overbooked but I had never heard of a bus being overbooked. Anyway on the way up there the bus broke down. Fortunately there was another Greyhound bus there to rescue us. By the time I had gotten up there and checked into the hotel it was already 4:00, and most of the attractions were closed. Instead I took the subway over to downtown here I could have dinner at the ESPN Zone and explore the rest of downtown where there's lots of shopping. I got a new winter coat (my old one was really worn out) and got a cool looking miniature RC helicopter from Brookstone. Also in Chicago there was a whole store that sold nothing but Legos. Here is a picture of the display outside:
All those things are made out of Legos. On Tuesday I went to the Museum of Science and Industry. There were some cool things there - in one of the activities we got the chance to use a "Human Patient Simulator" medical training dummy of the same kind as those actually used in medical schools. The way it worked was they showed us how to check for different vital signs (pulse, heart rate, breathing etc.) and then we were assigned to go up there, check the vital signs, and diagnoes the patient by matching the results to the results on a diagnosis chart we were given. Also while I was there I ran into Courtney Fontaine, one of the people that I took the comedy class from back at ComedySportz in DC. She now works at the science museum, and is also in another comedy group (not ComedySportz, although there is a ComedySportz in Chicago). She was having a performance that night and I went to see it. There were several comedy groups performing that night, and there were lots of funny parts. Courtney's group got the suggestion "gift-wrapping", and I thought it would be a boring suggestion but they went off on lots of funny tangents with it. The last group I gave the suggestion "Dungeons and Dragons" to, and I was actually quite impressed with their knowledge of D+D themes - they incorporated lots of classic D+D elements including traps, castles, wizards, and even "elemental powers" into their routine. The climax of the scene was funny - someone was talking about going to the "center" of a castle to find treasure, but someone else misheard it as "senator", and the scene then segued into a senator on a talk show whose shtick was "gratuitous profanity" - but since this is a family friendly blog I won't go into it any further.Then on Wednesday, I first went to the Travisa office to drop off the materials for my trip to India, then went back to get my stuff from the hotel. There wasn't really enough time to go to another attraction so I just went to the train station (I figured I might have better luck on the train rather than the bus) and got there about an hour and a half before the train was scheduled to leave. It was a good thing I got there early because I got the last available ticket to Urbana-Champaign. The train left on time and only got back to Urbana-Champaign about 20 minutes after the scheduled time.
Wednesday, November 11, 2009
More on the strike
Here is a letter to the editor in the Daily Illini opposing the strike:
Do Not Support the Strike
Here's my analysis of this argument:
1. The claim about graduate students "colluding to gain market power" doesn't make a lot of sense. By exactly the same logic, one could claim that the university itself consists of a lot of separate employers of graduate students (namely the individual professors) that are "colluding" into one administration to negotiate. So why is that not "market power?" Why is it "collusion" from one side but not from the other?
2. The statement about "if the university paid below the market rate, students would be attracted to other universities, so they would be forced to raise it" makes sense, but that's exactly the point of the strike. The students aren't willing to work for the wage they are being given, so they're going to refuse to work for that wage. That's exactly how the market is supposed to work, isn't it?
3. The statement about "the benefits come to ... those with political clout" doesn't make sense either. The students are asking for wage and benefit increases across the board - as far as I'm aware, they're not asking for any special favors for anyone with "political clout".
Do Not Support the Strike
Here's my analysis of this argument:
1. The claim about graduate students "colluding to gain market power" doesn't make a lot of sense. By exactly the same logic, one could claim that the university itself consists of a lot of separate employers of graduate students (namely the individual professors) that are "colluding" into one administration to negotiate. So why is that not "market power?" Why is it "collusion" from one side but not from the other?
2. The statement about "if the university paid below the market rate, students would be attracted to other universities, so they would be forced to raise it" makes sense, but that's exactly the point of the strike. The students aren't willing to work for the wage they are being given, so they're going to refuse to work for that wage. That's exactly how the market is supposed to work, isn't it?
3. The statement about "the benefits come to ... those with political clout" doesn't make sense either. The students are asking for wage and benefit increases across the board - as far as I'm aware, they're not asking for any special favors for anyone with "political clout".
Wednesday, November 4, 2009
Finally: Proof that the Stimulus is Working!
Jeff Erickson said recently that he wanted to consider hiring me as an RA for next year. The interesting reason is why: he recently received a grant for $200,000, and it was money that came from a program put in place by the stimulus package, so in order to keep the money he has to show that he is creating jobs. I haven't decided yet whether to take that offer or whether to work on a different project (after all, I still have about 1.5 semesters left on my fellowship to decide).
However, maybe that's a good thing: the graduate student employees' union is considering going on strike, because they have been without a contract for over 10 weeks and they claim they are not being paid a living wage. I guess that makes me non-union "scab" labor.
Bonus Question: What is wrong with this analysis of the teaching assistant pay situation?
However, maybe that's a good thing: the graduate student employees' union is considering going on strike, because they have been without a contract for over 10 weeks and they claim they are not being paid a living wage. I guess that makes me non-union "scab" labor.
Bonus Question: What is wrong with this analysis of the teaching assistant pay situation?
Saturday, October 24, 2009
More game happenings
Here are some more interesting things that happened during D+D games:
1. Our mission was to go to a place several days travel away to meet a friendly tribe of goblins to retrieve part of a set of artifacts we were looking for. As we traveled around the road, we ran into several groups of goblins from a different, enemy tribe, which we were able to defeat. Also according to the module (a module is a published "adventure book" for D+D) , "the journey along the road is long and arduous" so ever day of travel we had to make an Endurance skill check and if we failed the skill check we lose a healing surge. We all made fun of this , and our group's ranger, who was riding a horse, thought it was ridiculous that "I"m walking along a road, riding my horse, and I still lose my healing." Fortunately, since the module was "poorly written" (the DM's words) all the skill checks had such a low DC (difficulty class) that most of us made them very easily. (The way a skill check works is that you roll a 20-sided die and add your character's score in that skill, and if the result is equal to or higher than the DC then you pass the check.) And in fact it didn't even matter anyway since you get your healing surges back at the end of each day. But anyway when we got to the rendezvous point, the goblins we were supposed to meet were not there, and in its place were a third tribe of goblins, who had stolen the artifact. They said they would give it to us if we passed their "test" which involved fighting them one-on-one at a time with special rules (no healing allowed, if you push the other guy out of the ring then you win, if you damage the opponent and they don't damage you in one round then you win, there are special "meditation" and "mitigation" skill checks that you can make that give you bonuses). We lost this challenge mainly due to lucky dice rolling on the part of the DM (at one point I think he rolled two or three "natural 20s" on the 20-sided die in a row). The goblins then ran off with the artifact into a cave, and we wrote in our notebook: "Next time, use OUR rules." We pursued them into the cave, but unfortunately the cave ended in a dead end and there was an obelisk that turned out to be a teleportation portal that only goblins could pass through, so we couldn't pursue them any further. Also, we needed information the goblins had in order to complete the rest of our mission, and once the goblins had ran there was no way to get that. (See, the DM wasn't lying when he said the module was poorly written.) We gave up in failure, destroying the portal in order to punish them, and went back to our contact - a military leader - to report back. We were originally planning on claiming that all the goblins were dead when we got there and the artifact was nowhere to be found. However, while talking to the contact it turned out that after we left (but before we arrived at the rendezvous point) they had gotten a letter explaining that the artifact had been stolen. At this point our ranger berated the contact, saying that he should have "used magic" to inform us of the new information while we were on our way and blaming our failure on the "bad intelligence." The scenario ended with us all being shipped off to a far-away land to begin a new adventure ... and we won't know what that will be until Thursday.
2. Our mission was to retrieve a set of four statues that had been illegally smuggled into a city. First we went to a warehouse. While we were on our way the rogue made his Perception check to notice two people following us. Three out of the seven people in the party then made Stealth checks to sneak up behind them, so they immediately ambushed them, killed one of them, and intimidated the other one into surrendering and giving them additional information. The city guards then saw the seven of us standing around a dead body, and obviously wanted to know what happened. The rogue then Bluffed the guards into believing that they attacked first, and the Bluff check worked. Then we got to the warehouse and had to kill more smugglers, though this encounter was easier because if we hadn't killed the other two before, they would have joined forces with the ones in the warehouse. Then later on we found that there was another statue that was being held by a merchant (who was working for the smugglers). The encounter called for us to confront him and then he would run into a building, where we would have to fight more smugglers. However, we dealt with the problem a different way: while he was having tea in an open air market the rogue stole the statue out from under his feet while the rest of the party (including me) attacked and brutally murdered him. Again the guards showed up and this time we Bluffed the guards into believing that he was a spellcaster and we killed him in self-defense since he was about to cast a spell at us. At the end of the scenario, one of the characters whose alignment was "Chaotic Good" decided that "you know what, I might as well just change this right now" and erased the word "Good" to leave just "Chaotic."
3. Our mission was to go through a dungeon to find an evil demon and kill him. The paladin kept using his "Detect Evil" ability on everything as we went through the dungeon to find out where he was:
"You see a circular room with a well in the middle, a gong near the well, and there's a door on the other side."
"I use Detect Evil on the door."
"No, the door is not evil."
"I use Detect Evil on the gong. Is the gong evil?"
"No, no evil there."
"Okay, then let's go down the well."
..later...
"You're all down the well and you see a corridor in front of you. There's a door on the left side of the corridor."
"I use Detect Evil."
"Yeah, there's some evil on the other side of the door."
"How much evil?"
"About two Hit Dice worth of evil."
(Hit Dice are a measure of how powerful monsters are. Our party was made up of several 3rd-4th level characters, so 2 hit dice meant a very weak monster for us. The demon we eventually had to kill near the end was around 10 hit dice.)
On my iPhone (in real life of course) I have an app called the YouMeter. The YouMeter displays a fake "meter" on the screen that you can give it whatever title you want (like "Tragic Fashion Meter") and it goes yup when you push the "Activate" button. (Like all these "gag" apps there's a secret way to control it - where on the button you push it controls how high the meter goes.) So I got lots of laughs by setting it to "Evil Meter" and turning it on the next time the paladin used Detect Evil.
4. I don't just play D+D, I also play board games - the game store had a board game night on Sunday nights. I already talked about realism in D+D, and there's also plenty of realism in board games too. For example one game we were playing was "Power Grid", a game where you build power plants, fuel them, and connect them up. One turn during the "Energy Market" phase we all wanted to buy the oil but there wasn't enough for everyone. Also another game we played was "Automobile" where you play automobile company owners, and at the end of the game nobody had made any money. (Too bad there's no "Bailout" phase in the game.)
1. Our mission was to go to a place several days travel away to meet a friendly tribe of goblins to retrieve part of a set of artifacts we were looking for. As we traveled around the road, we ran into several groups of goblins from a different, enemy tribe, which we were able to defeat. Also according to the module (a module is a published "adventure book" for D+D) , "the journey along the road is long and arduous" so ever day of travel we had to make an Endurance skill check and if we failed the skill check we lose a healing surge. We all made fun of this , and our group's ranger, who was riding a horse, thought it was ridiculous that "I"m walking along a road, riding my horse, and I still lose my healing." Fortunately, since the module was "poorly written" (the DM's words) all the skill checks had such a low DC (difficulty class) that most of us made them very easily. (The way a skill check works is that you roll a 20-sided die and add your character's score in that skill, and if the result is equal to or higher than the DC then you pass the check.) And in fact it didn't even matter anyway since you get your healing surges back at the end of each day. But anyway when we got to the rendezvous point, the goblins we were supposed to meet were not there, and in its place were a third tribe of goblins, who had stolen the artifact. They said they would give it to us if we passed their "test" which involved fighting them one-on-one at a time with special rules (no healing allowed, if you push the other guy out of the ring then you win, if you damage the opponent and they don't damage you in one round then you win, there are special "meditation" and "mitigation" skill checks that you can make that give you bonuses). We lost this challenge mainly due to lucky dice rolling on the part of the DM (at one point I think he rolled two or three "natural 20s" on the 20-sided die in a row). The goblins then ran off with the artifact into a cave, and we wrote in our notebook: "Next time, use OUR rules." We pursued them into the cave, but unfortunately the cave ended in a dead end and there was an obelisk that turned out to be a teleportation portal that only goblins could pass through, so we couldn't pursue them any further. Also, we needed information the goblins had in order to complete the rest of our mission, and once the goblins had ran there was no way to get that. (See, the DM wasn't lying when he said the module was poorly written.) We gave up in failure, destroying the portal in order to punish them, and went back to our contact - a military leader - to report back. We were originally planning on claiming that all the goblins were dead when we got there and the artifact was nowhere to be found. However, while talking to the contact it turned out that after we left (but before we arrived at the rendezvous point) they had gotten a letter explaining that the artifact had been stolen. At this point our ranger berated the contact, saying that he should have "used magic" to inform us of the new information while we were on our way and blaming our failure on the "bad intelligence." The scenario ended with us all being shipped off to a far-away land to begin a new adventure ... and we won't know what that will be until Thursday.
2. Our mission was to retrieve a set of four statues that had been illegally smuggled into a city. First we went to a warehouse. While we were on our way the rogue made his Perception check to notice two people following us. Three out of the seven people in the party then made Stealth checks to sneak up behind them, so they immediately ambushed them, killed one of them, and intimidated the other one into surrendering and giving them additional information. The city guards then saw the seven of us standing around a dead body, and obviously wanted to know what happened. The rogue then Bluffed the guards into believing that they attacked first, and the Bluff check worked. Then we got to the warehouse and had to kill more smugglers, though this encounter was easier because if we hadn't killed the other two before, they would have joined forces with the ones in the warehouse. Then later on we found that there was another statue that was being held by a merchant (who was working for the smugglers). The encounter called for us to confront him and then he would run into a building, where we would have to fight more smugglers. However, we dealt with the problem a different way: while he was having tea in an open air market the rogue stole the statue out from under his feet while the rest of the party (including me) attacked and brutally murdered him. Again the guards showed up and this time we Bluffed the guards into believing that he was a spellcaster and we killed him in self-defense since he was about to cast a spell at us. At the end of the scenario, one of the characters whose alignment was "Chaotic Good" decided that "you know what, I might as well just change this right now" and erased the word "Good" to leave just "Chaotic."
3. Our mission was to go through a dungeon to find an evil demon and kill him. The paladin kept using his "Detect Evil" ability on everything as we went through the dungeon to find out where he was:
"You see a circular room with a well in the middle, a gong near the well, and there's a door on the other side."
"I use Detect Evil on the door."
"No, the door is not evil."
"I use Detect Evil on the gong. Is the gong evil?"
"No, no evil there."
"Okay, then let's go down the well."
..later...
"You're all down the well and you see a corridor in front of you. There's a door on the left side of the corridor."
"I use Detect Evil."
"Yeah, there's some evil on the other side of the door."
"How much evil?"
"About two Hit Dice worth of evil."
(Hit Dice are a measure of how powerful monsters are. Our party was made up of several 3rd-4th level characters, so 2 hit dice meant a very weak monster for us. The demon we eventually had to kill near the end was around 10 hit dice.)
On my iPhone (in real life of course) I have an app called the YouMeter. The YouMeter displays a fake "meter" on the screen that you can give it whatever title you want (like "Tragic Fashion Meter") and it goes yup when you push the "Activate" button. (Like all these "gag" apps there's a secret way to control it - where on the button you push it controls how high the meter goes.) So I got lots of laughs by setting it to "Evil Meter" and turning it on the next time the paladin used Detect Evil.
4. I don't just play D+D, I also play board games - the game store had a board game night on Sunday nights. I already talked about realism in D+D, and there's also plenty of realism in board games too. For example one game we were playing was "Power Grid", a game where you build power plants, fuel them, and connect them up. One turn during the "Energy Market" phase we all wanted to buy the oil but there wasn't enough for everyone. Also another game we played was "Automobile" where you play automobile company owners, and at the end of the game nobody had made any money. (Too bad there's no "Bailout" phase in the game.)
Saturday, October 17, 2009
Goings on at school
I have blogged enough about gaming for now so I will telll you what has been going on at school laterly.
I got the grade on my midterm back in Algorithms. I got 96 out of 100 (the highest grade in the class).
Also I am taking the mandatory CS 591-PHD orientation course, where each week they have a different guest speaker. We have had some cool lectures with some very distinguished lecturers, includnig Dan Reed who told us about high performance computing research going on at Microsoft, and Bill Gropp who told us about the new "Blue Waters" project at UIUC. Blue Waters is slated to be the most powerful supercomputer in the world, with the computing power of over 1 million laptops, and is scheduled to be completed sometime in 2011.
One interesting fact: part of the reason they are building Blue Waters at UIUC is because of the cold climate in Illinois. Supercomputers generate large quantities of heat and thus need to be cooled to avoid overheating and burning out, and that costs a lot of energy. Dan Reed also talked about this problem in regards to large corporate data centers. In fact, he told us, some corporations are discovering that in some cases it is actually cheaper to not even bother with extra cooling and simply replace computers as they fail rather than spend lots of electricity cooling them all. (That solution would not work for Blue Waters because unlike data centers that have lots of separate, redundant computers, Blue Waters is all connected and one part failing could ruin any computation that is in progress.)
On the other hand, this is probably not a good cooling solution for any large-scale computing application.
I got the grade on my midterm back in Algorithms. I got 96 out of 100 (the highest grade in the class).
Also I am taking the mandatory CS 591-PHD orientation course, where each week they have a different guest speaker. We have had some cool lectures with some very distinguished lecturers, includnig Dan Reed who told us about high performance computing research going on at Microsoft, and Bill Gropp who told us about the new "Blue Waters" project at UIUC. Blue Waters is slated to be the most powerful supercomputer in the world, with the computing power of over 1 million laptops, and is scheduled to be completed sometime in 2011.
One interesting fact: part of the reason they are building Blue Waters at UIUC is because of the cold climate in Illinois. Supercomputers generate large quantities of heat and thus need to be cooled to avoid overheating and burning out, and that costs a lot of energy. Dan Reed also talked about this problem in regards to large corporate data centers. In fact, he told us, some corporations are discovering that in some cases it is actually cheaper to not even bother with extra cooling and simply replace computers as they fail rather than spend lots of electricity cooling them all. (That solution would not work for Blue Waters because unlike data centers that have lots of separate, redundant computers, Blue Waters is all connected and one part failing could ruin any computation that is in progress.)
On the other hand, this is probably not a good cooling solution for any large-scale computing application.
Sunday, October 11, 2009
RPG Math - Problem Index
Now that I have finished my 10th RPG Math problem I am going to post an index of all the problems along with what category they are in.
Problem 1: Ineligible Receiver (of bullets) Downfield (Geometry)
Problem 2: Too Many Men on the Playing Field (Exponential Growth)
Problem 3: Take Cover! (Geometry)
Problem 4: Divvying Up The Loot (Algebra)
Bonus Problem: Divvying Up The Loot, Modern-Day Edition (Algorithms)
Problem 5: Mathematically Challenged (Optimization)
Problem 6: Taking Inventory (Algorithms)
Problem 7: By Our Powers Combined (Combinatorics)
Problem 8: Focus Fire! (Optimization)
Problem 9: The Killing Fields (Motion Planning)
Problem 10: All Decked Out (Expected Value)
Problem 1: Ineligible Receiver (of bullets) Downfield (Geometry)
Problem 2: Too Many Men on the Playing Field (Exponential Growth)
Problem 3: Take Cover! (Geometry)
Problem 4: Divvying Up The Loot (Algebra)
Bonus Problem: Divvying Up The Loot, Modern-Day Edition (Algorithms)
Problem 5: Mathematically Challenged (Optimization)
Problem 6: Taking Inventory (Algorithms)
Problem 7: By Our Powers Combined (Combinatorics)
Problem 8: Focus Fire! (Optimization)
Problem 9: The Killing Fields (Motion Planning)
Problem 10: All Decked Out (Expected Value)
RPG Math - Problem 10
Problem 10: All Decked Out
The card game "Dominion" is based on building up your deck of cards during gameplay. There are three types of cards: "Action" cards, "Treasure" cards, and "Victory" cards. Treasure cards have a number of coins on them, while Victory cards have a number of victory points on them.
A player's turn goes as follows. First, he draws five cards from his deck. Then, he plays up to one action card. Action cards can have one or more of the following effects:
"+X Cards" - Immediately draw X more cards.
"+X Actions" - You may play up to X more actions on this turn. (This allows you to create long chains of actions if you play +action cards and then use your new actions to play more +action cards.)
+1 Buy" - Increases the number of cards you can buy in the Buy Phase (See below) by 1.
"+X Coins" - Add X coins to the number of coins you have available in the Buy Phase (see below.)
After you finish playing actions you go into the Buy Phase. You add up the number of coins on all the treasure cards in your hand plus any +coins action cards you played. That is how many coins you have available to buy another card to put into your deck, and better cards cost more gold.
The way you win the game is by having the most victory points worth of Victory Cards in your deck at the end. ut of course Victory Cards are useless when you draw them, so they dilute your deck - and a key strategic element is when to start buying victory cards.
(***)
Here is the problem. Consider a simplified version of the game where you have an unlimited number of actions per round (you can keep playing action cards until you run out) and action cards only have the effects "+X cards" and "+X coins". Give a formula that can be used to calculate, given the composition of your deck, the expected number of coins you will have available to spend at the end of each turn.
You may make the following simplifying approximations:
1. All draws are independent - i.e. if 1/3 of your deck consists of treasure cards with a value of 2 coins, then each time you draw a card, you have a 1/3 chance of getting a treasure card with a value of 2 coins.
2. There is no chance of running out of cards to draw. (In the actual game, once you run out of cards to draw you can reshuffle your deck. It is possible to draw your entire deck in one turn, but that is rare.)
The answer is here.
The card game "Dominion" is based on building up your deck of cards during gameplay. There are three types of cards: "Action" cards, "Treasure" cards, and "Victory" cards. Treasure cards have a number of coins on them, while Victory cards have a number of victory points on them.
A player's turn goes as follows. First, he draws five cards from his deck. Then, he plays up to one action card. Action cards can have one or more of the following effects:
"+X Cards" - Immediately draw X more cards.
"+X Actions" - You may play up to X more actions on this turn. (This allows you to create long chains of actions if you play +action cards and then use your new actions to play more +action cards.)
+1 Buy" - Increases the number of cards you can buy in the Buy Phase (See below) by 1.
"+X Coins" - Add X coins to the number of coins you have available in the Buy Phase (see below.)
After you finish playing actions you go into the Buy Phase. You add up the number of coins on all the treasure cards in your hand plus any +coins action cards you played. That is how many coins you have available to buy another card to put into your deck, and better cards cost more gold.
The way you win the game is by having the most victory points worth of Victory Cards in your deck at the end. ut of course Victory Cards are useless when you draw them, so they dilute your deck - and a key strategic element is when to start buying victory cards.
(***)
Here is the problem. Consider a simplified version of the game where you have an unlimited number of actions per round (you can keep playing action cards until you run out) and action cards only have the effects "+X cards" and "+X coins". Give a formula that can be used to calculate, given the composition of your deck, the expected number of coins you will have available to spend at the end of each turn.
You may make the following simplifying approximations:
1. All draws are independent - i.e. if 1/3 of your deck consists of treasure cards with a value of 2 coins, then each time you draw a card, you have a 1/3 chance of getting a treasure card with a value of 2 coins.
2. There is no chance of running out of cards to draw. (In the actual game, once you run out of cards to draw you can reshuffle your deck. It is possible to draw your entire deck in one turn, but that is rare.)
The answer is here.
Wednesday, October 7, 2009
RPG Math - Problem 9
Recently, I have been talking to some professors in order to get advice on what classes I should take during the next few semesters so I can fill out my Program of Study Form, where I will create a plan for what courses I will take during my time at UIUC. One professor I talked to is Steven LaValle, a robotics researcher who specializes in motion-planning and navigation algorithms for robots. Some of the problems discussed in his book include things like, given a map of an environment and limited sensing ability, what's the best way for the robot to move in order to get enough data to find out where it is in that environment?
Recently, when I was visiting the Amtgard group in Peoria, the first part of the quest involved a motion strategy problem very similar to these. The scenario was as follows:
- The battlefield was approximately a rectangular field. At one corner was the "destination."
- At the beginning of the game, all the 'questers' (about 6-8 of them) were blindfolded, disoriented, and placed at an unknown location on the battlefield.
- The goal of the questers was to get to the destination. If a player ran into the edge of the battlefield, he would be directed back in by a reeve, no penalty suffered. However there were also "kill zones" in the battlefield that contained enemies. If a player moved into (or too close to) one of the "kill zones" then the enemies would kill them. (The player would then come back to life a few minutes later where he was, and would have to move away from the kill zone before continuing.)
- Although questers were blindfolded, they could still hear what was going on, which meant they can hear if someone is getting killed and would then know approximately in what direction that kill zone was.
Although I had actually read some of LaValle's book, I didn't remember enough of the part about motion planning under incomplete information, so that didn't really help me much - I got hit a total of three times (although I only died once - it took two hits to kill me, and I got healed when I got to the destination.) But that did give me an idea for another RPG Math problem. this is a much more simplified version of what happened in the game, but it should still be interesting and give me a chance to talk about some more algorithm techniques. With that out of the way, we now present...
Problem 9: The Killing Fields
Consider a square battlefield X units on a side. The battlefield contains a total of N "kill zones", the location of which is unknown, and each of which is a circle of radius at most 1. (Kill zones may extend off the side edges of the battlefield, but may not cross or overlap the top or bottom.) The goal of the "attacker" is to go from the bottom edge of the battlefield to the top edge of the battlefield. The attacker can start at any point on the bottom edge and move in whatever path he wants to get to the top. If the attacker hits a "kill zone", he is dead, and has to go back to the beginning and choose a new path, and he knows exactly where he was when he was hit. The goal of the attacker is to minimize the number of deaths before he is able to get to the top.
9a. Prove that no matter what method the attacker uses to choose his paths, there is an arrangement of "kill zones" such that he will take at least N deaths. (Hint: Imagine that you were the defender and you knew the attacker's strategy. How would you place the kill zones?)
9b. Suppose that N < (X/4). Show that the attacker has a strategy such that he will never take more than N deaths.
9c. Suppose that N > (X/2). Suppose that the attacker uses the strategy that minimizes the "worst case" number of deaths that he will suffer. What is the maximum number of deahts that he can guarantee he will not suffer more than, in terms of N and X?
The solution is here.
Recently, when I was visiting the Amtgard group in Peoria, the first part of the quest involved a motion strategy problem very similar to these. The scenario was as follows:
- The battlefield was approximately a rectangular field. At one corner was the "destination."
- At the beginning of the game, all the 'questers' (about 6-8 of them) were blindfolded, disoriented, and placed at an unknown location on the battlefield.
- The goal of the questers was to get to the destination. If a player ran into the edge of the battlefield, he would be directed back in by a reeve, no penalty suffered. However there were also "kill zones" in the battlefield that contained enemies. If a player moved into (or too close to) one of the "kill zones" then the enemies would kill them. (The player would then come back to life a few minutes later where he was, and would have to move away from the kill zone before continuing.)
- Although questers were blindfolded, they could still hear what was going on, which meant they can hear if someone is getting killed and would then know approximately in what direction that kill zone was.
Although I had actually read some of LaValle's book, I didn't remember enough of the part about motion planning under incomplete information, so that didn't really help me much - I got hit a total of three times (although I only died once - it took two hits to kill me, and I got healed when I got to the destination.) But that did give me an idea for another RPG Math problem. this is a much more simplified version of what happened in the game, but it should still be interesting and give me a chance to talk about some more algorithm techniques. With that out of the way, we now present...
Problem 9: The Killing Fields
Consider a square battlefield X units on a side. The battlefield contains a total of N "kill zones", the location of which is unknown, and each of which is a circle of radius at most 1. (Kill zones may extend off the side edges of the battlefield, but may not cross or overlap the top or bottom.) The goal of the "attacker" is to go from the bottom edge of the battlefield to the top edge of the battlefield. The attacker can start at any point on the bottom edge and move in whatever path he wants to get to the top. If the attacker hits a "kill zone", he is dead, and has to go back to the beginning and choose a new path, and he knows exactly where he was when he was hit. The goal of the attacker is to minimize the number of deaths before he is able to get to the top.
9a. Prove that no matter what method the attacker uses to choose his paths, there is an arrangement of "kill zones" such that he will take at least N deaths. (Hint: Imagine that you were the defender and you knew the attacker's strategy. How would you place the kill zones?)
9b. Suppose that N < (X/4). Show that the attacker has a strategy such that he will never take more than N deaths.
9c. Suppose that N > (X/2). Suppose that the attacker uses the strategy that minimizes the "worst case" number of deaths that he will suffer. What is the maximum number of deahts that he can guarantee he will not suffer more than, in terms of N and X?
The solution is here.
Thursday, October 1, 2009
Realism in Dungeons and Dragons
On Dungeons + Dragons websites there are a lot of ideas about how to make the game "more realistic." Some of these discussions are quite comical, such as claims that "it's unrealistic that special power X works against monster Y" when at least one (or in some cases both) of X and Y doesn't even exist in the real world, so it makes no sense to ask whether it is being represented "realistically." But today I played a game of Dungeons and Dragons that was quite realistic - maybe a little too realistic.
The setup was as follows. Our party was a group of missionaries for the deity Sarenrae, who preaches "compassion and peace" as her highest virtues. Our objective was to go into a tribe of gnolls (a type of monster), convert them all to Sarenrae's faith, and kill anyone who refused to convert. Helping us were some gnolls from a rival tribe that had a "blood feud" with the tribe we were trying to convert. During the discussion the DM (Dungeon Master) told us about a "serpent king" or something that all the gnolls were ruled by. When a player asked how the two tribes could fighting each other if they were both under the "serpent king," the DM said that "the Iranians and the Iraqis both worship Allah, but they hate each other."Another thing that came up during this talk was Sarenrae's "holy book" that apparently included a section on "who you're allowed to kill." For example you are allowed to kill someone who refuses to convert, but you have to give them a chance to convert first.
Anyway, we went off to our destination and we had to find Flynn, a "gnoll boss" that was the leader of the town. First we went to a goblin who could tell us where Flynn was. The goblin agreed to tell us where Flynn was only if we promised to kill Flynn. Our party's paladin (a paladin is a holy warrior who must follow a strict code of honor or he loses his special powers and becomes a "fighter without bonus feats") refused to promise to kill Flynn (because we have to give him a chance to convert first, and if he converts we aren't allowed to kill him.) Eventually we just went off and searched on our own and eventually found Flynn's lair. There were four gnoll guards that were guarding the stairs up to the lair. We tried to convert them but they at first refused. Then the paladin offered to give them gold to leave their posts, so we could go to the boss (after all the paladin was looking for the non-violent solution). However they agreed only under the condition that we agreed to kill Flynn (because if Flynn found out the guards had left their posts, he would kill them for their disobedience.) For reasons already discussed our paladin couldn't make that promise. The negotiations continued, and after he doubled the gold offer we were close to a deal, but another of our party members made a preemptive strike and attacked the gnoll guards. He thought he was doing our gnoll allies a favor by killing their mortal enemies, but our gnoll allies saw it differently - he saw the "treachery" and feared that we would kill them next, so our gnoll allies turned on us. Also in the chaos, the guards called Flynn to come down and help them in the fight. So we ended up fighting the gnoll guards, our former allies, and Flynn, all at the same time. When explaining why our gnoll allies had turned on us, the DM explained: "The Sunnis and Shiites hate each other, but when the infidels come, they turn on them."
Fortunately for us, all the gnolls were so weak that they were easily dispatched. Maybe it was for the best that that part of the game didn't turn out too realistic.
The setup was as follows. Our party was a group of missionaries for the deity Sarenrae, who preaches "compassion and peace" as her highest virtues. Our objective was to go into a tribe of gnolls (a type of monster), convert them all to Sarenrae's faith, and kill anyone who refused to convert. Helping us were some gnolls from a rival tribe that had a "blood feud" with the tribe we were trying to convert. During the discussion the DM (Dungeon Master) told us about a "serpent king" or something that all the gnolls were ruled by. When a player asked how the two tribes could fighting each other if they were both under the "serpent king," the DM said that "the Iranians and the Iraqis both worship Allah, but they hate each other."Another thing that came up during this talk was Sarenrae's "holy book" that apparently included a section on "who you're allowed to kill." For example you are allowed to kill someone who refuses to convert, but you have to give them a chance to convert first.
Anyway, we went off to our destination and we had to find Flynn, a "gnoll boss" that was the leader of the town. First we went to a goblin who could tell us where Flynn was. The goblin agreed to tell us where Flynn was only if we promised to kill Flynn. Our party's paladin (a paladin is a holy warrior who must follow a strict code of honor or he loses his special powers and becomes a "fighter without bonus feats") refused to promise to kill Flynn (because we have to give him a chance to convert first, and if he converts we aren't allowed to kill him.) Eventually we just went off and searched on our own and eventually found Flynn's lair. There were four gnoll guards that were guarding the stairs up to the lair. We tried to convert them but they at first refused. Then the paladin offered to give them gold to leave their posts, so we could go to the boss (after all the paladin was looking for the non-violent solution). However they agreed only under the condition that we agreed to kill Flynn (because if Flynn found out the guards had left their posts, he would kill them for their disobedience.) For reasons already discussed our paladin couldn't make that promise. The negotiations continued, and after he doubled the gold offer we were close to a deal, but another of our party members made a preemptive strike and attacked the gnoll guards. He thought he was doing our gnoll allies a favor by killing their mortal enemies, but our gnoll allies saw it differently - he saw the "treachery" and feared that we would kill them next, so our gnoll allies turned on us. Also in the chaos, the guards called Flynn to come down and help them in the fight. So we ended up fighting the gnoll guards, our former allies, and Flynn, all at the same time. When explaining why our gnoll allies had turned on us, the DM explained: "The Sunnis and Shiites hate each other, but when the infidels come, they turn on them."
Fortunately for us, all the gnolls were so weak that they were easily dispatched. Maybe it was for the best that that part of the game didn't turn out too realistic.
Wednesday, September 30, 2009
RPG Math - Problem 8 (Now With More Combat Action!)
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.
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 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."
Sunday, August 30, 2009
Ways of Warriors and Warlords, part 2 (Now With Archers!)
This weekend there was a lot of interesting events going on. First of all, there was a meeting of the local Belegarth group. Belegarth is a lot like Amtgard except that there are no character classes, levels, or magic - just fighting. You can, however, still use archery, which I did. I prefer archery to melee fighting in these games because:
1. Since there are far fewer archers than melee fighters, it allows me to have a unique role on the field.
2. It requires tactics and battlefield awareness rather than just raw fighting ability, because you have to scan the battlefield to identify good targets.
3. It's less frustrating, because I'm never up face to face with someone who is much better than me and that I can't beat. If someone charges me then I can run away and find another location.
4. It means that I don't have any problems with identifying where and when someone hit me. This is also harder in Belegarth than it is in Amtgard because in Belegarth, shots must strike with "sufficient force" in order to count.
--
So far I have been to three Belegarth practices. There are two per week - one on Wednesdays on the UIUC south quad (no archery is allowed there) and one on Saturdays. So far, after playing the game for a while, there are a lot of interesting differences between Amtgard and Belegarth in terms of archery.
Reasons why archery is more effective in Belegarth than in Amtgard:
1. There tend to be more people on a side and battle lines tend to be tighter, so it is easier to find targets and to find allies to hide behind.
2. Since there is no magic, archers are the only people on the field who have any kind of ranged fighting ability (except javelin throwers but those aren't usually that big of a threat). Thus as long as our battle line holds and nobody's snuck around it I don't have to worry about anyone except enemy archers.
3. With the exception of shields (see below) and dodging, there is no way to defend against incoming arrows - there's no "protection from projectile" spells, immunities, armor (actually there is armor, but arrows go right through it), etc., and you're not allowed to block arrows with weapons.
4. Head shots are legal in Belegarth, but not in Amtgard.
Reasons why archery is less effective in Belegarth than in Amtgard:
1. Shields are far more prevalent in Belegarth, and shields are very effective as a defense against arrows. (And unlike in Amtgard, there are no "specialty arrows") that can damage shields.
2. The safety requirements on arrows are far more stringent in Belegarth than in Amtgard, making the arrows heavier (due to the extra foam) and less aerodynamic.
3. At least in our group, arrows are not reusable. So once you're out of arrows, you have to switch to a melee weapon.
(1) and (2) combined make it so that it is very hard to hit someone who has a shield, is aware of you, and is not distracted. And if that is the case I don't want to waste an arrow on him, because of (3). That means that lots of times my teammates try to point out specific people on the other team to shoot at, but of course all that does is alert them to the fact that there's an archer there. And then my teammates wonder why I'm not shooting them, when the answer is that I know I won't be able to hit them. (Usually the people my teammates point out is one of the more experienced fighters on the other team - that's why they want them dead - so he is going to be better at blocking.)
Another problem is in figuring out who is on which team. Since there are so many people that can be hard to keep track of, so a couple times so far I have ended up shooting people on my own team. And of course, if I ask someone whose team they are on, all I am doing is alerting them to the fact that I am about to shoot them, and giving them the chance to put their shield up or defend. They actually did try to solve this problem last practice by giving people colored strips of fabric to wear. However, this didn't work very well because the pieces weren't that big and could be placed anywhere on the body, making it so that you had to look around for it. The strips were also easily concealed behind shields.
In one battle last session, it was a "capture the flag" battle, and I saw someone rushing toward our flag, with no visible "team sash". I asked him twice what team he was on, with no response. I let loose with the arrow, and it was a hit. The target turned out to be my own teammate, bringing the enemy flag back to our base! I couldn't see his sash because it was hidden behind his shield. Fortunately by the time he got hit he had already got back to our base, so we still one, and he was okay with it afterwards.
I suggested that they require that the "team sash" be worn on the head to eliminate the problems mentioned above. I don't know yet whether they will implement this suggestion next time. I do know, however, that I am not the only person who has trouble with the teams, because at a previous battle (at the quad so it was melee only) I observed lots of people asking each other what team they are on.
1. Since there are far fewer archers than melee fighters, it allows me to have a unique role on the field.
2. It requires tactics and battlefield awareness rather than just raw fighting ability, because you have to scan the battlefield to identify good targets.
3. It's less frustrating, because I'm never up face to face with someone who is much better than me and that I can't beat. If someone charges me then I can run away and find another location.
4. It means that I don't have any problems with identifying where and when someone hit me. This is also harder in Belegarth than it is in Amtgard because in Belegarth, shots must strike with "sufficient force" in order to count.
--
So far I have been to three Belegarth practices. There are two per week - one on Wednesdays on the UIUC south quad (no archery is allowed there) and one on Saturdays. So far, after playing the game for a while, there are a lot of interesting differences between Amtgard and Belegarth in terms of archery.
Reasons why archery is more effective in Belegarth than in Amtgard:
1. There tend to be more people on a side and battle lines tend to be tighter, so it is easier to find targets and to find allies to hide behind.
2. Since there is no magic, archers are the only people on the field who have any kind of ranged fighting ability (except javelin throwers but those aren't usually that big of a threat). Thus as long as our battle line holds and nobody's snuck around it I don't have to worry about anyone except enemy archers.
3. With the exception of shields (see below) and dodging, there is no way to defend against incoming arrows - there's no "protection from projectile" spells, immunities, armor (actually there is armor, but arrows go right through it), etc., and you're not allowed to block arrows with weapons.
4. Head shots are legal in Belegarth, but not in Amtgard.
Reasons why archery is less effective in Belegarth than in Amtgard:
1. Shields are far more prevalent in Belegarth, and shields are very effective as a defense against arrows. (And unlike in Amtgard, there are no "specialty arrows") that can damage shields.
2. The safety requirements on arrows are far more stringent in Belegarth than in Amtgard, making the arrows heavier (due to the extra foam) and less aerodynamic.
3. At least in our group, arrows are not reusable. So once you're out of arrows, you have to switch to a melee weapon.
(1) and (2) combined make it so that it is very hard to hit someone who has a shield, is aware of you, and is not distracted. And if that is the case I don't want to waste an arrow on him, because of (3). That means that lots of times my teammates try to point out specific people on the other team to shoot at, but of course all that does is alert them to the fact that there's an archer there. And then my teammates wonder why I'm not shooting them, when the answer is that I know I won't be able to hit them. (Usually the people my teammates point out is one of the more experienced fighters on the other team - that's why they want them dead - so he is going to be better at blocking.)
Another problem is in figuring out who is on which team. Since there are so many people that can be hard to keep track of, so a couple times so far I have ended up shooting people on my own team. And of course, if I ask someone whose team they are on, all I am doing is alerting them to the fact that I am about to shoot them, and giving them the chance to put their shield up or defend. They actually did try to solve this problem last practice by giving people colored strips of fabric to wear. However, this didn't work very well because the pieces weren't that big and could be placed anywhere on the body, making it so that you had to look around for it. The strips were also easily concealed behind shields.
In one battle last session, it was a "capture the flag" battle, and I saw someone rushing toward our flag, with no visible "team sash". I asked him twice what team he was on, with no response. I let loose with the arrow, and it was a hit. The target turned out to be my own teammate, bringing the enemy flag back to our base! I couldn't see his sash because it was hidden behind his shield. Fortunately by the time he got hit he had already got back to our base, so we still one, and he was okay with it afterwards.
I suggested that they require that the "team sash" be worn on the head to eliminate the problems mentioned above. I don't know yet whether they will implement this suggestion next time. I do know, however, that I am not the only person who has trouble with the teams, because at a previous battle (at the quad so it was melee only) I observed lots of people asking each other what team they are on.
Wednesday, August 26, 2009
Reflected sound of underground spirits, part 2
As it turns out, one of the people in the local Belegarth group is the owner of Edhellen Armoury, so he was able to answer the question I posed in my previous post.
The answer is that different groups have different standards for stabbing tips, so a stabbing tip that would pass inspection and thus be legal on the field at this group won't pass at all groups. So if they were to advertise on their web site, then they might end up selling stabbing tips that wouldn't pass. But when I called, they knew I was in the area because I had come to Belegarth the previous time, so they knew that their stabbing tip would be legal here.
And in case you're wondering about the title of this post, it comes from the book "The Color of Magic" by Terry Pratchett. It means "economics" ("reflected sound" = echo, "underground spirits" = gnomes, so "echo-gnomics")
The answer is that different groups have different standards for stabbing tips, so a stabbing tip that would pass inspection and thus be legal on the field at this group won't pass at all groups. So if they were to advertise on their web site, then they might end up selling stabbing tips that wouldn't pass. But when I called, they knew I was in the area because I had come to Belegarth the previous time, so they knew that their stabbing tip would be legal here.
And in case you're wondering about the title of this post, it comes from the book "The Color of Magic" by Terry Pratchett. It means "economics" ("reflected sound" = echo, "underground spirits" = gnomes, so "echo-gnomics")
More politics as usual in Illinois
The Illinois government has a program whereby state-level lawmakers can give scholarships to state schools to anyone they want to, subject only to the restriction that the recipient live in the lawmaker's district. Not surprisingly, said scholarships frequently go to relatives of lobbyists or campaign contributors.
In another article about this (not the one I liked, I couldn't find this one online) some of the lawmakers defended themselves by saying that they didn't have any role in choosing who got their scholarships - they delegated that decision to a committee. One lawmaker defended his decision to give a scholarship to the wife of "Mr. Williams," a lobbyist, by saying that "Mr. Williams is a decent man - I know him from his lobbying."
Possibly more surprisingly, most of the scholarships don't go to politically connected individuals. According to the article linked above, 83 scholarships over the past 6 years have gone to people with political connections, and 1,509 scholarships were awarded last year. Assuming no year-to-year change this means that less than 1% of scholarships went to people with political connections.
However, here's the question: What's the purpose of this program, if not to give politicians a way to reward their friends? I don't see why this system is a better way of distributing scholarships than a traditional way where everyone can apply and there are designated criteria for who gets the scholarship. The only thing I can think of is that a politician might know someone personally who would be a qualified recipient, but the qualifications don't look good "on paper" - but that goes back to politicians rewarding their friends.
In another article about this (not the one I liked, I couldn't find this one online) some of the lawmakers defended themselves by saying that they didn't have any role in choosing who got their scholarships - they delegated that decision to a committee. One lawmaker defended his decision to give a scholarship to the wife of "Mr. Williams," a lobbyist, by saying that "Mr. Williams is a decent man - I know him from his lobbying."
Possibly more surprisingly, most of the scholarships don't go to politically connected individuals. According to the article linked above, 83 scholarships over the past 6 years have gone to people with political connections, and 1,509 scholarships were awarded last year. Assuming no year-to-year change this means that less than 1% of scholarships went to people with political connections.
However, here's the question: What's the purpose of this program, if not to give politicians a way to reward their friends? I don't see why this system is a better way of distributing scholarships than a traditional way where everyone can apply and there are designated criteria for who gets the scholarship. The only thing I can think of is that a politician might know someone personally who would be a qualified recipient, but the qualifications don't look good "on paper" - but that goes back to politicians rewarding their friends.
Reflected sound of underground spirits
Here is an interesting puzzle.
Edhellen Armoury sells weapons for LARPs such as Belegarth and Dagorhir. They charge about $25-40 per weapon depending on size. They sell weapons primarily through the web site, but since they are based near here in Illinois, they also sell weapons through one of the local gaming stores, Dragon's Table. Most of the weapons they sell on the site are only legal to slash with, not stab with, because they do not have the required "stabbing tips." It is possible to get a stabbing tip added to the weapon for $10 extra.
A stabbing tip is simply an extra piece of foam that goes on the tip that makes the tip softer. The marginal cost of adding it is certainly far less than $10. (This is not the puzzle - lots of products have "extras" that you can get that cost far more than the cost of adding it, as a way of segmenting the market and making more money. For example the 16 GB iPhone costs $100 more than the 8 GB iPhone, even though the cost of 8 additional GB of hard drive capacity is far less than $100.)
The puzzle is the following:
The existence of the option to buy stabbing tips for extra is not listed anywhere on the site, and none of the weapons that are sold at the Dragon's Table have them. In order to find out that they exist, you have to call them, and then they tell you to buy the items as normal and put a "Special Payment" in for the stabbing tip. The question is: why do they make it so hard to find this information? There are other instances of companies making information about particular products hard to find, one notable example being the Starbucks "Short" latte, as a form of price discrimination. But unlike those other examples, Edhellen makes more money off the swords with stabbing tips, not less, so why would they want to hide it? The only thing I can think of is that the demand isn't high enough for it to be worth putting on the web site, but that's surprising, because I've seen lots of weapons at Belegarth with stabbing tips. (In any case, even if people didn't want the more expensive stabbing tip weapons it might still be worth putting them on the site, because of the "decoy effect" - seeing a more expensive option makes the other option look cheaper and more attractive by comparison.)
Edhellen Armoury sells weapons for LARPs such as Belegarth and Dagorhir. They charge about $25-40 per weapon depending on size. They sell weapons primarily through the web site, but since they are based near here in Illinois, they also sell weapons through one of the local gaming stores, Dragon's Table. Most of the weapons they sell on the site are only legal to slash with, not stab with, because they do not have the required "stabbing tips." It is possible to get a stabbing tip added to the weapon for $10 extra.
A stabbing tip is simply an extra piece of foam that goes on the tip that makes the tip softer. The marginal cost of adding it is certainly far less than $10. (This is not the puzzle - lots of products have "extras" that you can get that cost far more than the cost of adding it, as a way of segmenting the market and making more money. For example the 16 GB iPhone costs $100 more than the 8 GB iPhone, even though the cost of 8 additional GB of hard drive capacity is far less than $100.)
The puzzle is the following:
The existence of the option to buy stabbing tips for extra is not listed anywhere on the site, and none of the weapons that are sold at the Dragon's Table have them. In order to find out that they exist, you have to call them, and then they tell you to buy the items as normal and put a "Special Payment" in for the stabbing tip. The question is: why do they make it so hard to find this information? There are other instances of companies making information about particular products hard to find, one notable example being the Starbucks "Short" latte, as a form of price discrimination. But unlike those other examples, Edhellen makes more money off the swords with stabbing tips, not less, so why would they want to hide it? The only thing I can think of is that the demand isn't high enough for it to be worth putting on the web site, but that's surprising, because I've seen lots of weapons at Belegarth with stabbing tips. (In any case, even if people didn't want the more expensive stabbing tip weapons it might still be worth putting them on the site, because of the "decoy effect" - seeing a more expensive option makes the other option look cheaper and more attractive by comparison.)
Quad Day
This Sunday I went to Quad DAy, which is a day when all the student organizations put up booths to tell you about themselves and try to get you to join. I found lots of organizations that seemed interesting:
- Illini Roleplayers (RPGs and Vampire LARPing)
- Techfront (Science Fiction and Gaming)
- MATRIX (Math Club)
- Pirates of Chambana (Dressing up as pirates, building cardboard pirate ships, and doing "pirate battles")
- Odd Request (Improv Comedy Troupe)
There's going to be a lot of different activities to choose from this weekend. The Illini Roleplayers are doing a gaming convention that lasts all weekend, but there's other activities like tryouts for the Improv Troupe and the Urbana Sweetcorn Festival.
- Illini Roleplayers (RPGs and Vampire LARPing)
- Techfront (Science Fiction and Gaming)
- MATRIX (Math Club)
- Pirates of Chambana (Dressing up as pirates, building cardboard pirate ships, and doing "pirate battles")
- Odd Request (Improv Comedy Troupe)
There's going to be a lot of different activities to choose from this weekend. The Illini Roleplayers are doing a gaming convention that lasts all weekend, but there's other activities like tryouts for the Improv Troupe and the Urbana Sweetcorn Festival.
Saturday, August 22, 2009
Ways of Warriors and Warlords
Over the past couple weeks I have been exploring the gaming scene in Champaign-Urbana (CU).
From talking with some people I found out that there is likely not going to be a large market for Amtgard in this area, because there are several Dagorhir and Belegarth groups (Belegarth is another LARP like Dagorhir that focuses mainly on fighting) in the area, and most of the people in the area who are interested in LARPing are already going to one of those. (This probably explains why there are Amtgard groups in Peoria and Springfield but not CU, as well as why there didn't seem to be anyone currently going to one of the other Amtgard groups that lived closer to CU than to their park.)
I did find that there is a bus that goes to Peoria every day, including weekends. The bus ride is 2 hours long and costs $19 each direction, so it's definitely not something I will want to do every week. But it might be worth doing occasionally, like if there is a special event.
Additionally, I went to some gaming stores to check out the board gaming scene. There's a store, Armored Gopher Games, that is about a 20 minute bike ride away from home that has regular miniatures and Dungeons and Dragons (D+D) campaigns. I joined a D+D campaign that runs every other Friday and played one session so far. There were some funny things that went on. One of the rooms had a puzzle that consisted of a set of 16 plates, each with a different word on it, a door on the east side, and a statue on the south side. We assumed the goal was to open the door, and "door" was one of the words on the plates, so we tried combinations of plates like "Open East Door" and "Unlock East Door" and got nowhere. Then we remembered that we had got a scrap of leather in the previous room that had a picture of a left hand with a down arrow on it. So we tried "Left Hand Down" and that didn't work either. Unfortunately while we were doing this, one of our party members got greedy and tried to pry the gems out of the statue's eyeballs. This triggered the "Open Hell Gate Now" and forced us into combat with hell-spawned monsters. After defeating the monsters we discovered that the puzzle plates were now locked and inoperative. We also discovered that the door on the east side of the room was never locked in the first place. (We also later learned that we almost solved the puzzle: if we had stepped on "Left Hand Down Open" then the statue would have slid away, revealing a shortcut. Since we had to go through the door we had to take the long way around.) The "long way around" consisted of a trap room with traps that pulled us under the floor and attacked us with spears. Some of the characters didn't have the skills required to get out of the trap, so they kept failing their skill rolls to get out, and they were about to get crushed. However we were saved when after 5 rounds, the trap abruptly stopped (because that's what the description of the trap said) and let us out.
Finally, I found a real-life martial arts place, called Hwa Rang Do, in the same shopping center as Armored Gopher Games. I had learned about Hwa Rang Do from the Champaign Arts Festival, and there was a coupon for a free lesson. During the free lesson I learned about some of the basic moves, and also did some grappling, which is like wrestling. Hwa Rang Do grappling is a competitive sport where you get points for putting the opponent in specified positions, for example on the floor with you sitting on top of him or on the floor with you lying on his back. So in order to get the most points you have to shift between the different "scoring positions" while not allowing the opponent to get the upper hand. The cost of tuition at Hwa Rang Do is $90 per month for two 1-hour lessons per week, or you can sign up for the "Warrior's Path" which is $660 up front for training all the way up to the green belt level (green belt is the 4th out of 10 belt levels, IIRC) which on average takes about 10 months. I have not signed up for it, because I'm not sure if it's something I will want to do.
From talking with some people I found out that there is likely not going to be a large market for Amtgard in this area, because there are several Dagorhir and Belegarth groups (Belegarth is another LARP like Dagorhir that focuses mainly on fighting) in the area, and most of the people in the area who are interested in LARPing are already going to one of those. (This probably explains why there are Amtgard groups in Peoria and Springfield but not CU, as well as why there didn't seem to be anyone currently going to one of the other Amtgard groups that lived closer to CU than to their park.)
I did find that there is a bus that goes to Peoria every day, including weekends. The bus ride is 2 hours long and costs $19 each direction, so it's definitely not something I will want to do every week. But it might be worth doing occasionally, like if there is a special event.
Additionally, I went to some gaming stores to check out the board gaming scene. There's a store, Armored Gopher Games, that is about a 20 minute bike ride away from home that has regular miniatures and Dungeons and Dragons (D+D) campaigns. I joined a D+D campaign that runs every other Friday and played one session so far. There were some funny things that went on. One of the rooms had a puzzle that consisted of a set of 16 plates, each with a different word on it, a door on the east side, and a statue on the south side. We assumed the goal was to open the door, and "door" was one of the words on the plates, so we tried combinations of plates like "Open East Door" and "Unlock East Door" and got nowhere. Then we remembered that we had got a scrap of leather in the previous room that had a picture of a left hand with a down arrow on it. So we tried "Left Hand Down" and that didn't work either. Unfortunately while we were doing this, one of our party members got greedy and tried to pry the gems out of the statue's eyeballs. This triggered the "Open Hell Gate Now" and forced us into combat with hell-spawned monsters. After defeating the monsters we discovered that the puzzle plates were now locked and inoperative. We also discovered that the door on the east side of the room was never locked in the first place. (We also later learned that we almost solved the puzzle: if we had stepped on "Left Hand Down Open" then the statue would have slid away, revealing a shortcut. Since we had to go through the door we had to take the long way around.) The "long way around" consisted of a trap room with traps that pulled us under the floor and attacked us with spears. Some of the characters didn't have the skills required to get out of the trap, so they kept failing their skill rolls to get out, and they were about to get crushed. However we were saved when after 5 rounds, the trap abruptly stopped (because that's what the description of the trap said) and let us out.
Finally, I found a real-life martial arts place, called Hwa Rang Do, in the same shopping center as Armored Gopher Games. I had learned about Hwa Rang Do from the Champaign Arts Festival, and there was a coupon for a free lesson. During the free lesson I learned about some of the basic moves, and also did some grappling, which is like wrestling. Hwa Rang Do grappling is a competitive sport where you get points for putting the opponent in specified positions, for example on the floor with you sitting on top of him or on the floor with you lying on his back. So in order to get the most points you have to shift between the different "scoring positions" while not allowing the opponent to get the upper hand. The cost of tuition at Hwa Rang Do is $90 per month for two 1-hour lessons per week, or you can sign up for the "Warrior's Path" which is $660 up front for training all the way up to the green belt level (green belt is the 4th out of 10 belt levels, IIRC) which on average takes about 10 months. I have not signed up for it, because I'm not sure if it's something I will want to do.
Thursday, August 20, 2009
Registering for classes
This past week I have been meeting with various computer science professors in order to decide which classes to sign up for.
The first professor I met with was Michael Heath. I chose him because he works in the field of scientific computing, an area that I have done research and taken courses in in the past and so I might want to have him as my advisor. However he is not teaching any courses this semester. He did however give me a list of courses that I might want to take.
Another professor who I may want to work with is Steven LaValle. His research is in motion-planning algorithms for robots, and has a really cool lab with robots and obstacle courses for the robots to navigate around. I have already read much of the textbook he wrote on the topic. As it turns out, a lot of the problems that need to be solved in order to navigate robots are very similar to the types of problems that are solved in numerical and scientific computing. For example, robot motion planning problems are frequently modeled by specifying a set of parameters that describes a particular configuration of the robot (e.g. the displacement and rotation angles of each of the robot's joints) and then using a sampling method to search through the space of all possible parameters to find a path from the origin to the destination point. This is similar in some ways to numerical optimization problems where the goal is to search through a space of variables in order to find the variable values that optimize an objective function.
Unfortunately, LaValle isn't here this week so I couldn't talk to him. However I did also talk to another professor, Chandra Chekuri, who advised me to take two courses that would be useful in both the scientific computing and robotics fields - Topics in Algorithms and Discrete Mathematics - and also take some seminar courses where I can learn about different research areas. I also met with the director of the graduate program, Roy Campbell, who thought that that plan was a good idea.
Saturday, August 15, 2009
Graduate Student Social
This was a time for all the graduate students to get together. They had pizza an they even got cheese sticks for me. (They remembered that I didn't like pizza with sauce because I ran into the same situation during the visit day before). The cool thing was they just installed a new Wii video game system in the graduate student lounge. They had also sent out an email before asking what Wii video games people like to play because they had to decide which video games they should get to put in the room. One interesting thing I noticed was that there were also several people there from the State Farm insurance company. I didn't know why they were there - were they trying to sell us insurance? As it turned out the reason was that State Farm donated the money to buy the Wii. How that got started I have no idea.
Wednesday, August 12, 2009
Events coming up
Now that I am in my apartment in Illinois, I got a sheet indicating that there are several events coming up on campus. I will blog about them after they happen.
The schedule is as follows:
August 14 - Pizza night with other graduate students
August 16 - "Fun Night" sponsored by International Student and Scholar Services
August 17-21 - Meetings with faculty advisors & get signed up for classes
August 23 - QUAD Day: Learn about student organizations and entertainment available on campus
August 24 - First day of classes!
August 28 - "Meet and Greet BBQ" with faculty, staff, and other students in CS Department
The schedule is as follows:
August 14 - Pizza night with other graduate students
August 16 - "Fun Night" sponsored by International Student and Scholar Services
August 17-21 - Meetings with faculty advisors & get signed up for classes
August 23 - QUAD Day: Learn about student organizations and entertainment available on campus
August 24 - First day of classes!
August 28 - "Meet and Greet BBQ" with faculty, staff, and other students in CS Department
Monday, August 3, 2009
My last day at Amtgard (for now...)
Sunday was my last day at Amtgard before I move out to Illinois. It was also the last day of the current reign period, so we had a coronation, and it was a joint coronation with Bandit Flats East, a park in Delaware. So we had to drive all the way out to Delaware to go to the coronation.
As usual, I ran the kid's quest for the day. My plan was to do a quest based on Greek mythology. The way it was going to work was that there was going to be a series of events where they had to "prove themselves" to the gods in order to get items that would enable them to defeat the evil Minotaur. There were different events based on each god's theme - for example a weapon making tutorial for Hephaestus, an arts and crafts project for Athena, and so on. My original plan was also to spice it up by telling them some of the myths. The problem with this is that most Greek myths are not very kid-friendly, because they involve sex, revenge killing, or both. But I did identify several that were. One that I was planning to use was the story of the contest between Athena and Poseidon. (I think this is a humorous one because it is similar to the modern practice of selling naming rights to sports stadiums, except that they were selling naming rights to a city. In fact there is a Capitol Steps song, a parody of "This Land Is Your Land," that speculates that states will have to begin selling naming rights in order to cover their budget deficits, resulting in states with names like "Okla-Home Depot", "New Texaco", and "North Toyota." Apparently the Greeks had the same idea thousands of years earlier.)
When I got there things did not go out as well as planned. First of all there was a major rainstorm which trapped us in the pavilion. Also, the person who was supposed to help me in the quest, our monarch Perdita, got stuck in traffic and was going to be late. I started the quest anyway, but it was difficult because without an adult to help me, it was hard to get the kids to sit down long enough to listen to the instructions. We finished the arts and crafts and weapon making parts at about 2:00, and we learned that at 4:00 we would have to leave to go to a different site for feast. At about this time I called Perdita to find out where she was. As it turned out she was in Delaware near the park, but got lost because of construction. I gave the phone to someone there who gave her directions. Unfortunately when she got there she was busy with other business and couldn't help in the quest. Fortunately I got someone else to help. Since we were running short on time I had to rush through the rest of the events. I quickly abandoned the idea of telling them the myths when it was clear that after being stuck under the pavilion they just wanted to get up, run around, and fight. At the end, I told them that they had killed the minotaur, and was going to be rewarded with gems, but that robbers had stolen them. I played the robber and when they tried to attack me, I said "you'll never get these gems" and tossed them into a bush as they killed me. What I didn't realize was that the bush had prickly leaves, but fortunately they were able to get the gems out without any cuts. Then I gave them the prizes and let them keep the weapons they had made.
We then went over to feast, which was at a local SPCA office. The only problem with getting there was that only one person knew how to get there, so he had to get out in front an everyone else followed them like a caravan. Of course about half of us had access to GPS (either an in car device or a phone) so if they told us the address we would be able to find it, but they didn't know the address just how to get there. Fortuantely we all arrived without incident. There was a feast and then they gave out awards, of which I received several. There was going to be an auctio nbut it was cancelled due to lack of time and because everyone had to go home.
As usual, I ran the kid's quest for the day. My plan was to do a quest based on Greek mythology. The way it was going to work was that there was going to be a series of events where they had to "prove themselves" to the gods in order to get items that would enable them to defeat the evil Minotaur. There were different events based on each god's theme - for example a weapon making tutorial for Hephaestus, an arts and crafts project for Athena, and so on. My original plan was also to spice it up by telling them some of the myths. The problem with this is that most Greek myths are not very kid-friendly, because they involve sex, revenge killing, or both. But I did identify several that were. One that I was planning to use was the story of the contest between Athena and Poseidon. (I think this is a humorous one because it is similar to the modern practice of selling naming rights to sports stadiums, except that they were selling naming rights to a city. In fact there is a Capitol Steps song, a parody of "This Land Is Your Land," that speculates that states will have to begin selling naming rights in order to cover their budget deficits, resulting in states with names like "Okla-Home Depot", "New Texaco", and "North Toyota." Apparently the Greeks had the same idea thousands of years earlier.)
When I got there things did not go out as well as planned. First of all there was a major rainstorm which trapped us in the pavilion. Also, the person who was supposed to help me in the quest, our monarch Perdita, got stuck in traffic and was going to be late. I started the quest anyway, but it was difficult because without an adult to help me, it was hard to get the kids to sit down long enough to listen to the instructions. We finished the arts and crafts and weapon making parts at about 2:00, and we learned that at 4:00 we would have to leave to go to a different site for feast. At about this time I called Perdita to find out where she was. As it turned out she was in Delaware near the park, but got lost because of construction. I gave the phone to someone there who gave her directions. Unfortunately when she got there she was busy with other business and couldn't help in the quest. Fortunately I got someone else to help. Since we were running short on time I had to rush through the rest of the events. I quickly abandoned the idea of telling them the myths when it was clear that after being stuck under the pavilion they just wanted to get up, run around, and fight. At the end, I told them that they had killed the minotaur, and was going to be rewarded with gems, but that robbers had stolen them. I played the robber and when they tried to attack me, I said "you'll never get these gems" and tossed them into a bush as they killed me. What I didn't realize was that the bush had prickly leaves, but fortunately they were able to get the gems out without any cuts. Then I gave them the prizes and let them keep the weapons they had made.
We then went over to feast, which was at a local SPCA office. The only problem with getting there was that only one person knew how to get there, so he had to get out in front an everyone else followed them like a caravan. Of course about half of us had access to GPS (either an in car device or a phone) so if they told us the address we would be able to find it, but they didn't know the address just how to get there. Fortuantely we all arrived without incident. There was a feast and then they gave out awards, of which I received several. There was going to be an auctio nbut it was cancelled due to lack of time and because everyone had to go home.
Wednesday, July 1, 2009
Ricci v. DeStefano
In the Supreme Court case Ricci v. DeStefano, the New Haven, Conn. fire department instituted a test to determine which firefighters would get promotions. After no black or Hispanic firefighters scored well enough to be eligible for promotions, the department, worried that they could be sued for racial discrimination, threw out the results of the test. Of course, now white firefighters sued them saying that they were being discriminated against, because the the decision to throw out the results was made based on racial factors. The Supreme Court just ruled in favor of the white firefighters.
This case brings up saveral interesting issues. One issue, of course, is whether standardized tests such as the one used in this case are a good way to select job candidates. My general opinion on this question is that although standardized tests are obviously not the solution in every case, they do tend to get an undeserved bad rap. Yes, standardized tests can be biased, and they are clearly an imperfect measure of qualifications. But the appropriate comparison is not with some perfect system, it's with whatever the alternative is. And there are plenty of common selection methods that produce far more inequality and discrimination than any test (and are just as questionable with regards to relevance) yet are rarely controversial. For example:
1. Many employers find new employees based on referrals from current employees - i.e. a current employee knows someone who would be a good fit for the company, and refers them. Of course, for most employers, the set of acquaintances of current employees is not even close to a representative sample of the entire population, and obviously there is no necessary correlation between being friends with a current employee and being qualified for the job. Even in the absence of a formal referral sytem, there are lots of jobs that are filled based on personal connections, and this critique could apply to all of them.
2. Many jobs require a college degree, and employers tend to value degrees from more prestigious schools more than degrees from less prestigious schools. Of course, whether you get a college degree (and where) depends on lots of factors, including where you grew up, whether your parents could afford to send you to college, etc., only some of which have relevance to whatever job you are applying for. And paying for college is a huge barrier for lower-income families. (One common critique of standardized tests like the SAT is that it favors people who can afford expensive test preparation. Which is a higher barrier: spending a few weeks and a few hundred dollars on a test preparation course, or spending four to six years and tens of thousands of dollars on a college education?)
In fact, it seems to me that standardized tests have the potential to mitigate some of these problems. A standardized test can be tailored to the requirements of a particular job, and it can be re-tested, adjusted, and fine-tuned to offer whatever balance is desired between racial balance, screening value, and any other relevant factors. In fact, by bypassing other "screening barriers" such as personal connections and subjective judgments, if a set of effective, general-purpose tests were to be developed, that would have the potential to go a long way toward mitigating racial and socioeconomic disparities.
Of course, this is not a panacea: not all jobs can be easily measured by a test. But for those that can be, it seems that designing an effective test is a much more tractable problem than say, equalizing access to elite schools or giving poor people opportunities to form personal connections with potential future employers.
But as for the Ricci v. DeStefano case, it's actually not clear what effect it will have on the use of testing. Superficially, the decision was in favor of testing (the decision effectively said that the test results should have been kept.) But what it also does is place employers who use tests in a catch-22 situation. If the test comes up with racially disparate results, they have no way to avoid a lawsuit - if they throw out the tests they will get sued by one side, if they keep them they will get sued by the other. So this might end up discouraging employers from using the tests.
(The court opinion said that throwing out the tests would have been okay if there were a "strong basis in evidence" that the city would in fact have been held liable, but that the city failed to meet this standard. But this still doesn't solve the problem - it essentially boils down to saying that an employer can be held liable for failing to be good enough at guessing how the courts will rule. And that's a hard thing to do - just look at how many 5-4 Supreme Court decisions there are.)
It's also still unclear exactly what employers are allowed to do. My understanding is that in this particular case the employer said "We'll be using this test to decide who gets promoted." Suppose that instead, the employer said "We're going to give you all this test, we haven't decided yet what we're going to do with the results." And then they had done the same thing as they did before. Would that have been okay? Or does the decision force employers to pre-commit as to what they are going to do with the test before they give it? If so, it seems like that might hinder development of more effective tests, because employers can't fine-tune the tests once they've been given out. (Although my understanding is that there are firms that do this test design, and they would pre-test the test on people outside the employer. So employers might use this method prior to giving it to their own employees or prospective employees.)
And finally, does the decision apply just to standardized tests, or to any method of avoiding racial discrimination? If the latter, then it seems that since any active attempt to avoid racial discrimination (e.g. against minorities) by definition implies trying to hire more minorities than otherwise, then it could be classified as "reverse discrimination" using exactly the same argument as the white firefighters made. And of course id they don't make that effort, then they're violating their duty to avoid discrimination against minorities. So how are employers possibly supposed to satisfy all their obligations under the law?
This case brings up saveral interesting issues. One issue, of course, is whether standardized tests such as the one used in this case are a good way to select job candidates. My general opinion on this question is that although standardized tests are obviously not the solution in every case, they do tend to get an undeserved bad rap. Yes, standardized tests can be biased, and they are clearly an imperfect measure of qualifications. But the appropriate comparison is not with some perfect system, it's with whatever the alternative is. And there are plenty of common selection methods that produce far more inequality and discrimination than any test (and are just as questionable with regards to relevance) yet are rarely controversial. For example:
1. Many employers find new employees based on referrals from current employees - i.e. a current employee knows someone who would be a good fit for the company, and refers them. Of course, for most employers, the set of acquaintances of current employees is not even close to a representative sample of the entire population, and obviously there is no necessary correlation between being friends with a current employee and being qualified for the job. Even in the absence of a formal referral sytem, there are lots of jobs that are filled based on personal connections, and this critique could apply to all of them.
2. Many jobs require a college degree, and employers tend to value degrees from more prestigious schools more than degrees from less prestigious schools. Of course, whether you get a college degree (and where) depends on lots of factors, including where you grew up, whether your parents could afford to send you to college, etc., only some of which have relevance to whatever job you are applying for. And paying for college is a huge barrier for lower-income families. (One common critique of standardized tests like the SAT is that it favors people who can afford expensive test preparation. Which is a higher barrier: spending a few weeks and a few hundred dollars on a test preparation course, or spending four to six years and tens of thousands of dollars on a college education?)
In fact, it seems to me that standardized tests have the potential to mitigate some of these problems. A standardized test can be tailored to the requirements of a particular job, and it can be re-tested, adjusted, and fine-tuned to offer whatever balance is desired between racial balance, screening value, and any other relevant factors. In fact, by bypassing other "screening barriers" such as personal connections and subjective judgments, if a set of effective, general-purpose tests were to be developed, that would have the potential to go a long way toward mitigating racial and socioeconomic disparities.
Of course, this is not a panacea: not all jobs can be easily measured by a test. But for those that can be, it seems that designing an effective test is a much more tractable problem than say, equalizing access to elite schools or giving poor people opportunities to form personal connections with potential future employers.
But as for the Ricci v. DeStefano case, it's actually not clear what effect it will have on the use of testing. Superficially, the decision was in favor of testing (the decision effectively said that the test results should have been kept.) But what it also does is place employers who use tests in a catch-22 situation. If the test comes up with racially disparate results, they have no way to avoid a lawsuit - if they throw out the tests they will get sued by one side, if they keep them they will get sued by the other. So this might end up discouraging employers from using the tests.
(The court opinion said that throwing out the tests would have been okay if there were a "strong basis in evidence" that the city would in fact have been held liable, but that the city failed to meet this standard. But this still doesn't solve the problem - it essentially boils down to saying that an employer can be held liable for failing to be good enough at guessing how the courts will rule. And that's a hard thing to do - just look at how many 5-4 Supreme Court decisions there are.)
It's also still unclear exactly what employers are allowed to do. My understanding is that in this particular case the employer said "We'll be using this test to decide who gets promoted." Suppose that instead, the employer said "We're going to give you all this test, we haven't decided yet what we're going to do with the results." And then they had done the same thing as they did before. Would that have been okay? Or does the decision force employers to pre-commit as to what they are going to do with the test before they give it? If so, it seems like that might hinder development of more effective tests, because employers can't fine-tune the tests once they've been given out. (Although my understanding is that there are firms that do this test design, and they would pre-test the test on people outside the employer. So employers might use this method prior to giving it to their own employees or prospective employees.)
And finally, does the decision apply just to standardized tests, or to any method of avoiding racial discrimination? If the latter, then it seems that since any active attempt to avoid racial discrimination (e.g. against minorities) by definition implies trying to hire more minorities than otherwise, then it could be classified as "reverse discrimination" using exactly the same argument as the white firefighters made. And of course id they don't make that effort, then they're violating their duty to avoid discrimination against minorities. So how are employers possibly supposed to satisfy all their obligations under the law?
Saturday, June 27, 2009
This week at Amtgard
Today at Amtgard I ran a kid's quest. I hadn't been planning on doing it, but what happened was that there were some kids there and they told me they wanted to "fight the evil ogre." Of course there wasn't any evil ogre before, but there was one now. So I left the base in order to "scout out" the area (i.e. hide the evil ogre's treasure for the kids to find.) The kids said they had a "map" that told them where the ogre was, and that they would "turn me into a crab" so the enemies wouldn't notice me. It took a while to hide all the stuff, so when I came back I said that I was delayed because "it's kind of hard to read a map if you're a crab." The first half of the quest was mostly the kids running around everywhere except where I hid the stuff, making stuff up as they went along. They said their "map" told them where the ogre's "secret weapons" were, but they kept changing their story about where the "secret weapons" were, and never actually found any "secret weapons." (Remember that it was just me and the kids; there were no actual players playing monsters.) Eventually they went over to the area where I hid the stuff. I hid four small pouches and one big bag, and said that the pouches contained the "fire gem," "air gem," "earth gem," and "water gem." They found all the gems except the "air gem" but couldn't find the last one. One of the kids said that maybe the last gem was in the ogre's "main treasure hoard." Of course I knew that I hid it on the ground in the wooded area, but I went to the place I thought I remembered hiding it and it wasn't there. Eventually they found the bag (the "main treasure hoard") and the fourth pouch was in there! (Someone must have been walking through the path in the back of the woods, saw the bag and the pouch, and assumed that the pouch belonged in the bag and so put it there.) At the end I took the ogre mask, put some armor on, and said that the armor was cursed and transformed me into the ogre. Of course they defeated the "ogre" and we all went back to town (the pavilion.) They looked at the treasure and saw lots of potions. I told themthat I had a "magical device that could detect the power of the potions" (i.e. my iPhone, which has an app on it that displays a fake "meter" that you can control by pressing a hidden button) They actually recognized the "magical device" as an iPhone, but went along with it anyway. Overall it was a very fun day, and Colleen rewarded me by giving me a "mithril armor" relic.
Thursday, June 18, 2009
Weight Watchers
I joined Weight Watchers this week. Weight Watchers is a weight loss program that works in an interesting way. Each food is assigned a "point value" based on its calorie content, fiber, and grams of fat. Higher calories and fat mean more points. You have a maximum quota of points based on your weight, age, height, sex, and activity level. Then you keep track of all the foods you eat and try to stay under the point level. There is also a list of "healthy eating options" that you are supposed to have. These include fruits and vegetables, healthy oils, and lean protein. Lean protein was one thing that I thought that it would be hard for me to find because I don't like meat, but it turns out that lots of places have chicken that I can eat. Another thing is that there is a list of "filling foods" that have a low "energy density" (i.e. number of calories per gram.) These are good to eat because they fill you up without lots of calories. As it turns out, 94% fat free, butterless popcorn is a filling food.
Another interesting thing is that it also mentions "fat-free cheese." I had no idea such a thing existed, but if it does, it would help me cut a lot of fat out of my diet.
By the way, an article in Wired magazine (it's about the sixth result on google for "weight watchers" offers the following explanation for Weight Watchers' success: it turns weight loss into a game, similar to computer role-playing games. For example:
- The "point system" where each food costs a certain number of points is similar to systems in games where you spend "points" to cast spells or use special powers.
- There are rewards you get when you reach certain milestones (like losing 5% of your body weight.) This is like in computer games where you can go up in level or get rewards by accomplishing objectives.
- The first ten weeks they give you one "book" a week, which slowly introduces you to new features of the plan. For example the week 1 book just talks about eating healthy and introduces the point system for food, and later books give advice on things like eating out and exercising more. This is similar to computer games where each level introduces more features.
=======
The only problem with Weight Watchers so far is that there is no official iPhone app for it. There are lots of unofficial apps but those only have a very limited set of features. For example the app I am using now just lets you put in foods and point values and track them (and also lets you calculate point values from nutrition data). It doesn't keep track of any of the "healthy eating" items, and doesn't have the list of filling foods. So I still have to carry around the physical book for that. It seems so 20th century.
Another interesting thing is that it also mentions "fat-free cheese." I had no idea such a thing existed, but if it does, it would help me cut a lot of fat out of my diet.
By the way, an article in Wired magazine (it's about the sixth result on google for "weight watchers" offers the following explanation for Weight Watchers' success: it turns weight loss into a game, similar to computer role-playing games. For example:
- The "point system" where each food costs a certain number of points is similar to systems in games where you spend "points" to cast spells or use special powers.
- There are rewards you get when you reach certain milestones (like losing 5% of your body weight.) This is like in computer games where you can go up in level or get rewards by accomplishing objectives.
- The first ten weeks they give you one "book" a week, which slowly introduces you to new features of the plan. For example the week 1 book just talks about eating healthy and introduces the point system for food, and later books give advice on things like eating out and exercising more. This is similar to computer games where each level introduces more features.
=======
The only problem with Weight Watchers so far is that there is no official iPhone app for it. There are lots of unofficial apps but those only have a very limited set of features. For example the app I am using now just lets you put in foods and point values and track them (and also lets you calculate point values from nutrition data). It doesn't keep track of any of the "healthy eating" items, and doesn't have the list of filling foods. So I still have to carry around the physical book for that. It seems so 20th century.
Monday, June 15, 2009
More updates coming...
Sorry about the lack of updates recently. I'm going to be ging on a family reunion this weekend though, and I will be sure to blog all about it when I get back!
Wednesday, May 6, 2009
Graduation Information
Graduation information is as follows:
Gemstone Citation Ceremony:
Wednesday, May 20, 4:30 PM (parking starts at 4:00 PM)
Memorial Chapel
No tickets required
Main Commencement Ceremony:
Thursday, May 21, 7:00 PM (students arrive at 5:45 PM)
Comcast Center
Tickets required - I have tickets for myself + 7 guests
College of CMPS Ceremony:
Friday, May 22, 9:00 AM
Reckord Armory
No tickets required
Gemstone Citation Ceremony:
Wednesday, May 20, 4:30 PM (parking starts at 4:00 PM)
Memorial Chapel
No tickets required
Main Commencement Ceremony:
Thursday, May 21, 7:00 PM (students arrive at 5:45 PM)
Comcast Center
Tickets required - I have tickets for myself + 7 guests
College of CMPS Ceremony:
Friday, May 22, 9:00 AM
Reckord Armory
No tickets required
Tuesday, April 28, 2009
Amtgard News #5: Feast of Fools
First of all, my prediction of "exciting combat action" at the University of Maryland was recently proven correct.
----
Anyway, I went to Feast of Fools, a big Amtgard camping even in Hagerstown last weekend. It lasted from Friday to Monday.
I got there around Friday at 8:00 PM and spent the next hour or so setting up the tent. Some of the poles were broken so we had to tape spare arrow shafts to the poles. We knew this in advance and brought 4 spare arrow shafts to use for this purpose - and it turned out we ended up having to use all of them. Fortunately, we had selected a camp location right next to the security tent, so a security guy helped us set it up by illuminating the area with his flashlight.
The rest of Friday was mostly hanging out in the tavern and fighting on the "ditch field." That was fun except that during one of the battles, while I was fighting someone on the other side, one of my opponent's teammates ran at me at full speed and stabbed me in the side with about a 6 foot long spear. As I write this I can still feel the spot where it hit.
Saturday was the day with most of the action. The first event I participated in was the "Triwizard Tournament." In this tournament, three spellcasters stand at the corner of an equilateral triangle 80 feet on a side. Their goal is to retrieve an object located at the center and bring it back to their corner, and hold it there for 30 seconds (though in practice this turned into the wizards fighting each other and the last one alive wins). However, one of the contestants was high enough level to have Finger of Death (kills any target within 50 feet) and Extension (doubles range of the spell), and could cast each of these twice, so he could just kill both the enemies right off the bat. There was no effective way to defend against this, since casting a protection spell or running 80 feet to charge him both take much longer than casting Extension/Finger of Death. (In battlegames, spells like Finger of Death can be cast a limited number of times "per game", as opposed to most spells which are weaker but are either "per life" or unlimited casts, so that balances them out. A general problem with wizard tournaments is that there's only one "life" in a given round, and everything, including per-game limited spells, resets between rounds. This means that per-game spells tend to dominate the game in wizard tournaments.)
Fortunately I got to play a wizard again as an "evil sorcerer" in a kid's quest. I assumed it would be really easy to kill the kids since I could run faster than them so I could just stay out of their range, but I was wrong. It was about 5 on 1, and a couple of the kids had bows, so they could shoot me while I was trying to cast my spells! Also another kid wanted to play a wizard and be on my team. However, Celwyn said it would be a better idea for him to be on the good guys' team because, as she said, "you said you were going to make spells up? If you cast at us we won't know what the spells are, but he (talking about me, the evil sorcerer) is a really good role-player so he'll be able to make the spells do something." That quest was a lot of fun.
I also participated in three battlegames, and played an archer in all of them. One was a "cone battle." In this battle there are five cones set up across the field. If one team gets two people on each cone they score a point and everything resets. This game was fun and competitive, and I scored lots of kills with my arrows. Several people afterward complimented me on my archery skills.
The second game was a "king of the hill" game. In this game the two teams try to hold a central point for as long as they can. What happened this time was that the other team wiped us out in the first round of fighting. When you die, you can come back to life after 5 minutes (reduced to 2.5 because of the relatively small number of people playing). The rules say that you can delay coming back to life after your count is completed, but most of the other people on the team didn't know that, so they all kept coming back to life one or two at a time and getting slaughtered by the other team. I tried to explain to the team that coming back all at once would be a better idea, but they refused saying that "our goal is to have fun, not to win." Of course, in my opinion, coming to life one at a time, being backed up against your base by a wall of 10 enemies, and being killed within 15 seconds after you come alive every time wasn't much fun either.
The third battlegame was a "defend the castle" game, and just like the previous game, my team had about 10 people on it. However the other team had about 30 people on it. So we tried to defend the castle but got slaughtered pretty easily. The reeve then said that our base is now on the outside, theirs is now on the inside, and we should try to retake the castle. Since it was clear that the match was not even close, the reeve basically said that everyone can stop keeping track of their lives, they can all respawn in 30 seconds, and just have fun killing each other. So that's basically what we did until everyone got tired of playing.
Then there was feast, and after the feast I had to go to a "Belted Family Meeting." Now, you're probably wondering what that is. The story is this: A few months ago, Gailwind Blackfoot (a.k.a. Colleen) aske to take me on as her "man-at-arms". This is kind of like a mentor-student relationship, and she gives me tasks like writing quests, learning the rules and the corpora, and making weapons and equipment. There are also other "family" relationships, like a knight can take a squire. And these all form a whole lineage, kind of like a real life family tree. This was my first belted family meeting so I was kind of embarrased that not only did I not know who was in my belted family, some of the people were people I knew from before (like Yoshi) and I didn't even know they were in my belted family. When they were explaining to me what a belted family was, I pulled out a pen and paper and started trying to draw our "family tree," but Colleen told me that I could do that later.
On Sunday there wasn't a whole lot of fighting going on due to the excessive heat (I think it was almost 100 degrees), except for a couple tournaments. In fact there was so much heat that they had to send out "water bearers" to bring water to the participants so they would stay hydrated and they wouldn't pass out from the heat or anything. I didn't have anything else to do so I volunteered to be a water bearer. Our head medic even said that we should tell the players that that they had to either drink the ater (or pour it over their heads to cool themselves off) or they would be taken off the field.
----
Anyway, I went to Feast of Fools, a big Amtgard camping even in Hagerstown last weekend. It lasted from Friday to Monday.
I got there around Friday at 8:00 PM and spent the next hour or so setting up the tent. Some of the poles were broken so we had to tape spare arrow shafts to the poles. We knew this in advance and brought 4 spare arrow shafts to use for this purpose - and it turned out we ended up having to use all of them. Fortunately, we had selected a camp location right next to the security tent, so a security guy helped us set it up by illuminating the area with his flashlight.
The rest of Friday was mostly hanging out in the tavern and fighting on the "ditch field." That was fun except that during one of the battles, while I was fighting someone on the other side, one of my opponent's teammates ran at me at full speed and stabbed me in the side with about a 6 foot long spear. As I write this I can still feel the spot where it hit.
Saturday was the day with most of the action. The first event I participated in was the "Triwizard Tournament." In this tournament, three spellcasters stand at the corner of an equilateral triangle 80 feet on a side. Their goal is to retrieve an object located at the center and bring it back to their corner, and hold it there for 30 seconds (though in practice this turned into the wizards fighting each other and the last one alive wins). However, one of the contestants was high enough level to have Finger of Death (kills any target within 50 feet) and Extension (doubles range of the spell), and could cast each of these twice, so he could just kill both the enemies right off the bat. There was no effective way to defend against this, since casting a protection spell or running 80 feet to charge him both take much longer than casting Extension/Finger of Death. (In battlegames, spells like Finger of Death can be cast a limited number of times "per game", as opposed to most spells which are weaker but are either "per life" or unlimited casts, so that balances them out. A general problem with wizard tournaments is that there's only one "life" in a given round, and everything, including per-game limited spells, resets between rounds. This means that per-game spells tend to dominate the game in wizard tournaments.)
Fortunately I got to play a wizard again as an "evil sorcerer" in a kid's quest. I assumed it would be really easy to kill the kids since I could run faster than them so I could just stay out of their range, but I was wrong. It was about 5 on 1, and a couple of the kids had bows, so they could shoot me while I was trying to cast my spells! Also another kid wanted to play a wizard and be on my team. However, Celwyn said it would be a better idea for him to be on the good guys' team because, as she said, "you said you were going to make spells up? If you cast at us we won't know what the spells are, but he (talking about me, the evil sorcerer) is a really good role-player so he'll be able to make the spells do something." That quest was a lot of fun.
I also participated in three battlegames, and played an archer in all of them. One was a "cone battle." In this battle there are five cones set up across the field. If one team gets two people on each cone they score a point and everything resets. This game was fun and competitive, and I scored lots of kills with my arrows. Several people afterward complimented me on my archery skills.
The second game was a "king of the hill" game. In this game the two teams try to hold a central point for as long as they can. What happened this time was that the other team wiped us out in the first round of fighting. When you die, you can come back to life after 5 minutes (reduced to 2.5 because of the relatively small number of people playing). The rules say that you can delay coming back to life after your count is completed, but most of the other people on the team didn't know that, so they all kept coming back to life one or two at a time and getting slaughtered by the other team. I tried to explain to the team that coming back all at once would be a better idea, but they refused saying that "our goal is to have fun, not to win." Of course, in my opinion, coming to life one at a time, being backed up against your base by a wall of 10 enemies, and being killed within 15 seconds after you come alive every time wasn't much fun either.
The third battlegame was a "defend the castle" game, and just like the previous game, my team had about 10 people on it. However the other team had about 30 people on it. So we tried to defend the castle but got slaughtered pretty easily. The reeve then said that our base is now on the outside, theirs is now on the inside, and we should try to retake the castle. Since it was clear that the match was not even close, the reeve basically said that everyone can stop keeping track of their lives, they can all respawn in 30 seconds, and just have fun killing each other. So that's basically what we did until everyone got tired of playing.
Then there was feast, and after the feast I had to go to a "Belted Family Meeting." Now, you're probably wondering what that is. The story is this: A few months ago, Gailwind Blackfoot (a.k.a. Colleen) aske to take me on as her "man-at-arms". This is kind of like a mentor-student relationship, and she gives me tasks like writing quests, learning the rules and the corpora, and making weapons and equipment. There are also other "family" relationships, like a knight can take a squire. And these all form a whole lineage, kind of like a real life family tree. This was my first belted family meeting so I was kind of embarrased that not only did I not know who was in my belted family, some of the people were people I knew from before (like Yoshi) and I didn't even know they were in my belted family. When they were explaining to me what a belted family was, I pulled out a pen and paper and started trying to draw our "family tree," but Colleen told me that I could do that later.
On Sunday there wasn't a whole lot of fighting going on due to the excessive heat (I think it was almost 100 degrees), except for a couple tournaments. In fact there was so much heat that they had to send out "water bearers" to bring water to the participants so they would stay hydrated and they wouldn't pass out from the heat or anything. I didn't have anything else to do so I volunteered to be a water bearer. Our head medic even said that we should tell the players that that they had to either drink the ater (or pour it over their heads to cool themselves off) or they would be taken off the field.
Subscribe to:
Posts (Atom)