Just another WordPress.com site

Archive for November, 2011

Surprise Math!

Well things got a bit busy and progress on the project slowed some, but it is still being made! I just keep forgetting to update. We did run into a pretty interesting problem recently, so I figured it is worth an update.

Being a self taught programmer has lead to me having a somewhat warped view on programming. I have always thought of it as throwing my brain in a frying pan for a bit and then with enough time the solution comes. It can be slow, but I always get to my solution. This means that when I have a programming problem it is hard and painful and then boom really easy and generally that process moves at the same pace. First you figure out what you want to do, set it all up and then find where you get stuck then research, research and research some more and then poof you find the right thing and solve it. Our most recent problem actually brought that view into question and it was done with something that was frustratingly simple outside of the realm of programming. This has brought me to conclude that I just program easy things most of the time and am missing out on a world of interesting problems (though I bet stacked overflow still has it all answered).

We currently have all of the players made and are now looking to start the game, so we wrote up the code for the Sheriff starting and started making some progress in that direction, but we got to wondering about what happens when you find to check the distance from player to player to shoot at someone or be shot at. Recall that the game is played in a circle, so the people to one to your left and right are 1 away, the next ones are 2, etc. Something like this from a’s perspective:

This is all simple enough and coding it is pretty painless. You can just represent it as a matrix:

a b c d e
a 0 1 2 2 1
b 1 0 1 2 2
c 2 1 0 1 2
d 2 2 1 0 1
e 1 2 2 1 0

This all came fairly quickly, but it gets interesting when someone dies. When playing at a table, its pretty simple, you just remove that person and the next person that direction is 1 closer and the next one is closer and so on.

It gets tricky when trying to represent it with a matrix. It is worth noting that Adam has a major in computer science and a minor in math and I have a BA in math and am about done with an MS in statistics, which means we should be pretty good at linear algebra. Naturally this was untrue and we busted out some linear algebra information. Using the identity matrix on both sides we sorted out how to zero out a row and a column, but we couldn’t figure out a way to modify it so that when b dies a is now 1 away from c, while updating it from everyone’s perspective. I honestly believe there is a way to do it and I believe that way would involve turning it into a triangle matrix and then holding onto the changes you made to get it that way and then you could find a vector that would operate on it. By this time we were tired of linear algebra, so we hit up the Internet more.

Some things we looked into were convex hulls, which is something neither of us were super familiar with, but it sounded like it had the potential. All the while we were having a pretty good laugh about our troubles representing such a simple thing and it actually got late, so we had to take a break.

Day 2 came and we were determined to solve this problem. I almost emailed the Macalester math department to see if they needed a problem of the week, since we were investing so much time. I started looking for patterns in the 4 player version, then the 5 and the 6 and 7. I noticed that if there were an even number of players left there would would be n value changes from a given players perspective and if there were an odd number of players there would be n-1 changes. I tried to turn this into a set of rules to use, but it was just not quite happening.

We started thinking about the problem as a line of numbers, since that is really all it is. If a wants to shoot c, first it goes from a to b and then from b to c, so there are two jumps, which means the distance is 2. This brought forth lists, which I have personally not played with a ton (though after this I started using them at work). Essentially it is just a data structure that is ordered. We then found that you can make the rule that when you get to the right “end” you go to the left “start” and vice versa. So we have something as simple as

a b c d e

With a link between a and e, so they are next to each other. With a list we can just say remove c when c dies and it updates the list. All that is left is dealing with the two directions. If a wants to shoot e, it either goes to the left 1 or it goes to the right 4, so the distance is just the minimum of this, which is what I planned to code, but Adam being an actual programmer had a more clever solution. His idea was to just go out 1 in both directions until you hit the value in question. It is much simpler and I have to assume more computationally efficient.

So we solved it! It took a while (likely longer than it should have), but it feels good to get a solution. Now for a few more basic framework game concerns and then time to start writing decision rules and taking a stab at this AI!

Tag Cloud