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.)

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.

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)

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.

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.

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.