Initial AI notes

Hey All,

I wanted to get some notes down for the general strategy of the game and the plan for the AI. To start consider what happens in a turn:

The sheriff goes first and then it goes around clock wise, so consider the sheriffs turn:

Check for Jail or dynamite (the only two things that preclude drawing)

You draw 2 cards (unless it is modified by your character), so there is some type of draw phase

Next there is a main phase (to borrow from magic), where you can play 1 bang card (unless modified), any number of blue cards (cards that stay in play in front of you) and any number of other non-bang cards. This is where the strategy comes in, you have to decide who to shoot, what to card to destroy and really what to do with each card. Do you even want to shoot anyone? Should you hold onto that card? There are a very large number of decisions to be made.

End your turn and move to the next person

There are victory condition checkers (when someone dies, does that end the game?) and rewards to be given out, etc, which are fairly simple and might get a post in the future, but the big challenge now that we have most of the basic game set is getting the strategy coded.

Earlier I presented a list of the character cards and ordered them into groups, so when presented with two options the computer will have the ability to pick wisely and gain from seeing two cards.

Next we have to create a similar list for every card in the game, to help give direction for cards. Consider Cat Balou, which destroys target card or forces a player to discard at random. There a few decisions to make: Should we use it? Who do we target? Do we target their hand or the board? If we target the board, what do we target?

This leads to a decision tree and there has to be logic at each step. Lets walk through each step for Cat Balou.

Should we use it?

Generally, sitting on cards in hand has some risk. There is a chance that someone makes you discard and if you have more cards than you have life you will have to discard. So if at the end of the turn we will have to discard, we should use it. We also have to consider the time value of it, if we have it next turn or the turn after that is there something to be gained. Consider the Bang! card, you need it to not take damage from the Indians card, so if maintaining your life is of concern, you might want to hold on to one. Furthermore, you have to consider threats on the board currently, as well as potential future threats. For Cat Balou, if there are no big scary cards on the table right now and we don’t know of any big scary cards in opponents hands (for a chance to remove them), is it worth holding onto it (risking having it stolen or discarded) to use in the future against potential scary cards. Generally, using it now seems like it is the strongest play, but it  all depends on who you are, so breaking out into roles:

Sheriff/Deputes: You goal is to keep the sheriff alive, so if you see an outlaw with a big scary clearly you target it. The proximity of the outlaw to the sheriff is also a factor, since that dictates how easy it is to shoot him. I think this is one of the roles where it might make sense to play more defensively with it and wait for scary cards to come into play. If an outlaw gets a gun that lets him hit the sheriff and you cat balou it, you have saved a lot of damage on the sheriff. This is the scenario where you want to use it most often here and I think it outweighs the risk of getting it taken or discarded.

Outlaws: The logic for the outlaws is generally straightforward, use whatever it is you have to hurt the sheriff. Unless the deputies have a very high powered card you are scared of, you just want to tax the sheriff more. If the sheriff has something on the board that is effecting the game state, you should remove it (barrels, horses, etc), but if he has nothing it is still worth it to target his hand to get rid of resources. In my current understanding of the game, directing your damage toward the sheriff is almost always (essentially 100% of the time) the proper decision.

Renegade: The logic for the renegade is very complex. You are trying to balance power. Cat Balou allows you to get rid of powerful cards that might tip the scales towards either other side. So if the outlaws throw down a volcanic (big scary gun), you should remove it, if the outlaws are ahead or let them have it for a bit if they are behind. You start out playing as a deputy and the shift from team to team based on the general power levels of them. It is hard to consider individual cards for the renegade, with out first figuring out how it will play.

Who to target/what to do?

Outlaws: Really just target the sheriff, unless there is something very powerful from a deputy.

Sheriff/deputies: target the most powerful threat to the sheriff.

Renegade: target powerful items and try to keep the other two in check.

How we manage the power level of items is yet to be coded. I think the best bet is to go through and rank each card into categories, like we did with character cards and then decide using that. Given the computer having perfect knowledge, if a play reveals a card on a draw from a general store or a character ability, it will be known, so you might have some information about the cards in their hand. So if they have a very powerful card in their hand, you would weight that and assume the other cards are of average power and decide that way. Things on the board are simpler, since if you see something powerful you just go for it. Generally you prefer removing board threats first, since you get them no matter what.

Currently I am working on ranking each card, so we can set this logic up. In the future coming up with ways of adding nuisances, like this card with this character is powerful, etc, will be good, but for now I think it will be a straight ranking.

A note on the renegade

I am not sure if the renegade will be in for the first run through. The logic for the renegade gets a bit more complicated. Since you are playing a balancing game, we will have to come up with a team strength metric. As long as you don’t know who is who, it will be a bit less useful, but as roles become clear the renegade will need a way to say that the outlaws are stronger than the deputies, so I should help the deputies. The factors that go into this decision will be, life totals (with some weighting, because really low life totals mean that the person could drop out quickly), number of cards in hand, what cards in hand (if known), cards on the board and a special emphasis on threats to the sheriff, since that ends the game. It should be fun to write out, but I don’t know if it will be a focus right now.

If you have any thoughts on the ordering of the cards for the power ranking, let me know, that is what I am working on now.

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!

Help us rank character cards in bang

Hey All,

 

Adam and I are working on a ranking system for character cards to make the AI work well. The thing is, I am not 100% on the ordering of the character cards, so if you play Bang and have some thoughts, please share.

http://boardgamegeek.com/thread/355868/poll-rate-the-bang-characters

I found that poll on the Internet and used it as a starting point and from there broke it down into the following groups, going from best to worst.

1 Willy the Kid, Slab the Killer, Calamity Janet

2 Black Jack, Kit Carlson, Suzy Lafayette

3 Bart Cassidy, Pedro Ramirez, Jesse Jones, Jourdonnais

4 Lucky Duke, El Gringo, Sid Ketchum

5 Vulture Sam, Rose Doolan, Paul Regret

 

I am not 100% sold on this, but its a start. I am looking for any thoughts you might have on the ordering. There are no requirements for number of rankings, so if you think that we should have 6 or 7 groups instead of 5 that is fine, as is having 4 groups instead of 5.

The approach we are taking here is to tier the quality of the card, so the AI has a better card, so we don’t just randomly pick and end up with Vulture Sam over Slab the Killer. Within each group we will break ties randomly, so it is very important to have a good break down here.

It is also worth noting that we don’t want to have too many tiers, because if we just ordered them, then you would never have a chance of playing Rose Doolan or Paul Regret (which ever one you defined as the worst), so I think the grouping and deciding with in groups randomly is best, but if you have a case against that approach or really any thoughts on it at all, let me know.

Thanks,

Andy and Adam

 

Evrry Day I’m Shufflin’

Hey-o Internet!

Hot sexy programming date got moved to a Monday, but was still pretty awesome. There is not a whole ton to tell, but we finished up the character cards and job cards, so we have all 3 decks of cards set.

Adam also took the lead (hey, I am terrible at programming and he is a boss at it) on the shuffler.

After reading around a bit, we decided on the Fisher-Yates  shuffle.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

The wikipedia article goes into more detail and does a good job of explaining it, but it really just boils down to assigning a random number (some interesting concerns there. We don’t really deal with it and I believe it is a non-issue for us, but achieving randomness is a lot trickier than you might expect: see this xkcd blog post for some randomness http://blog.xkcd.com/2010/02/09/math-puzzle/) to each card and then order them based on that. I was surprised to see how intuitive the shuffler ended up being. I sort of figured it would be more complicated.

Currently we have 3 decks of cards and the ability to shuffle them,so next week we are going to create a player, which is a job card, a character card, a life total, a standing board (that is cards they have that stay in play) and a hand. I also started looking into sorting out a reasonable approach to the artificial intelligence, but that won’t be for a bit yet.

 

Andy

 

 

 

 

 

 

 

 

 

 

 

 

Playing Programmers

Hello Interwebs!

Statistics project is 1 meeting away from me having to write a paper, but an update is not worth it, since its just obnoxious technical stuff and bad things that happen when there are 30 instances of something happening in a 15k+ individual dataset, BUT I did get a few things done.

My old undergrad roommate and I got together on Saturday to play programmers. He majored in computer science in undergrad, so lets just say he did a lot of the programming and I was more of a “big picture” guy, but it was a good, productive time anyway.

Our goal is to program the game Bang! (http://en.wikipedia.org/wiki/Bang!) in c#. Its a really fun game, but has some balance issues and I think bootstrapping (http://en.wikipedia.org/wiki/Bootstrapping_(statistics)) is a way to balance it and get a better idea of what is going on. For now, just imagine playing hundreds of thousands of games of Bang! and recording their results to get a distribution (breakdown) of win rates, what cards were used, etc. We are a ways from the actually bootstrapping, so I won’t focus on it here, but you get the idea.

On Saturday we set out to make the deck of cards for the original game:  http://www.emilianosciarra.net/ENG/playing_cards.html

 

It took a fair bit of time. We ended up having 1 typo that led to a null reference in the array we were using that took a long time to catch, but we fixed it and currently have the main deck of cards coded.

One thing we came across that I have run into before and always find interesting was some trouble with referencing an object. It tripped up Adam a bit, so maybe its not just my general lack of experience with programming, but I always find it super frustrating.

Consider what we were doing: defining 82 cards and referencing them. We started by creating card1 = card info, card 2 = card info, etc up to card 82. Now if you wanted to systematically reference these cards with a loop, the approach that comes to my mind is just loop through all cards something along the lines of card*, where * is the number you want. You can do this with strings, where you combine outside variables with text and such, but you can’t (rather we couldn’t figure out how to) get it to reference objects in this way. So you could create a variable that was card1, but the way it was combined created a string and now a reference to the card1 object we created earlier. It was not a super hard to fix, we just had to use an array (http://msdn.microsoft.com/en-us/library/aa288453(v=vs.71).aspx), but it is definitely the thing that frustrates me most about programming. I am pretty good at thinking like a computer (in loops, if statements and such), but sometimes how I think about it does not translate to the reasonable approach I was taking.

After reading around a bit, I have a better idea of what it is hard to deal with the approach we were using and why they have the work around options they have. I think things problems like this are really how you learn how to program in a specific language, it seems reasonable, but is not, so go find a functioning way.

Next weekend we are making a shuffler and adding in the character cards and role cards. I might post a bit more on the information we are keeping track of with the cards as well, but I left my notes on it at Adams and doing it from memory seems silly.

So blogging is hard

So my attempt at using a blog to categorize my thoughts is off to a rough start, since I have completely neglected this for so long, but lets try it again by getting a new post!

 

My current project that is first in line is to get my MS project finished! I introduced it briefly in the first post, but I am going to take this post to introduce a bit more information. My buddy at grad school (mark) set me up with two doctors in the UK and his adviser at the University of Minnesota, so I could have a nice project to graduate with. I am of course in the midst of pulling out all of my hair (from a sunburned scalp even!) trying to figure out the tiny details that always fall apart.

In any case, the paper looks at two kinds of hip replacement (full and half). I honestly don’t know a whole ton about the hip replacement side of things, so I would suggest http://en.wikipedia.org/wiki/Hip_replacement for more information on that. Suffice to say, they are different and we are wondering in what way they are different. The way we plan on figuring out their difference is based on the absurdly large and excellent data base that is maintained in the UK about all patients and surgeries that happen. Apparently in order to get paid as a doctor in the UK you have to submit a good chunk of information to the central agency that does the paying. If you were looking for a reliable way to get good information this is it, give me what I want and then I will pay you! So the British doctors have access to this wonderful resource.

The database has the type of surgery, age, sex, 30 day dislocation rate, 6 month dislocation rate, the 4 year dislocation rate, the 6 month revision rate, 4 year revision rate and the charlson score. The dislocation rate data is a binary variable that is a 1 if you have had a dislocation in a given period of time (this is a complication that is associated with hip replacements), the revision rate is whether or not they had to go back and do another surgery on your hip in a give period of time, and the charlson score is a measure of overall health (for instance, if you had 4 heart attacks, you would have a large charlson score and it would suggest that maybe your problems are a result of external forces and not just the hip replacement).

Naturally we needed to find a way to compare this data in a reasonable way. In a previous paper they had done some propensity score matching, so I looked into that and we decided that it was a reasonable approach. Propensity score matching is a way of matching based on different variables. Recall that our goal is the compare people that had half hip replacements with similar people that have had full hip replacements, so we need to find a way of reasonably matching them.

The propensity score matching approach starts with a propensity model, which in this case is a simple logistic regression. I found that a propensity score based on charlson age and sex seemed to have the best AIC value, though the differences between a few different models was minor, so it is reasonable to pick a different model, but in the end the results are the same as long as you include age and charlson. Next I used the package in R called Matching to take these propensity scores and then construct two data sets that are well matched.

The initial results from this suggested that half hip replacement have between a .5 and 1.5 % decrease in dislocations for all time periods. This is about where I am currently.

Next up I am trying to fill out some more detailed tables that subset the data and compare, say only the really sick people or only older people, but the Matching package is doing a damn fine job of hiding the method they use. I have tried a few things, such as a simple t-test and http://en.wikipedia.org/wiki/McNemar’s_test, but they all give incredibly significant p-values (roughly 0), where as the output from the Matching package gives p-values that are more around the .05ish range and they are not always significant.

I have 3 articles I am reading on the method they use, but given the relative difficulty I am having in getting it sorted out, I think I might just go with McNemar’s test, since a bio-statistician my adviser talked to suggested it.

Hello world!

Howdy Internet,

I am in the process of finishing up my MS in statistics, so while I do that I am taking a bit of time to look for a job and more importantly get some projects rolling. My goal here is to get some ideas saved for a few projects and maybe put up some pictures of projects that can have pictures.

Before summer started (while avoiding studying for finals, naturally) I came up with a list of things I wish I knew how to do and maybe some thoughts on how to do it.

Graduate:

I am currently finished with classes (at least by my count, still need to double check that), but I am working on my plan B project, which is to say, the paper I have to present to graduate. A friend of mine was nice enough to introduce me to a great advisor and project and made my life easier, but I am still finishing up a bit of work on it.

I am doing the statistical work for two Doctors in the UK who are writing a paper on hip replacements. There are two kinds of hip replacements (potentially more, but we just look at these two): half replacement and full replacement. It is worth noting that my experience with being a doctor is limited to pretending to diagnose people in an undergraduate neuroscience class, so I won’t comment on the doctor end of things (I really just read the wikipedia and that was about it), but lets agree there are two different types of replacement.  The question we are addressing is, whether or not one is better than the other.  I am using propensity score matching, but I think I will probably post about that another day.

Programming:

I built my first computer when I was 12 and I have always enjoyed programming to some extent, but I unfortunately have little academic experience with it (I took one class and didn’t like it, so I kind of avoided it after that). I am good at practical programming inside of a package (think R, SAS, STATA, matlab, etc), but I think it would be nice to get better at some more programming things.

I worked for an energy trading company for 6 months and I had to learn a decent bit of programming and found that I enjoyed it. I started in VBA, moved to VB, and then did some projects in C# (also learned some SQL). I want to do more of it, so I am rummaging around on the Internet to find some good sources for it. The list I am looking at currently is here: http://www.reddit.com/r/compsci/comments/gprp0/is_there_a_list_of_the_canonical_introductory/

Its kind of dull to just do book exercises, so my plan for working on my programming is to come up with some projects and do them. The one I am most excited about right now is coding the game Bang! and trying to “bootstrap” (simulate) a potential change or rules to make it more fair. I will probably post on this later, but here is a link to the game: http://en.wikipedia.org/wiki/Bang! (its really pretty fun, but pretty unbalanced).

I am still not certain the language I would like to do it in or any of the specifics, but I am thinking of doing C or maybe Java, we will see.

Statistics:

I am looking to go through some books that I have heard were good and can get my hands on and try to work on some applied statistics I ought to know. My buddy swears by: http://www-stat.stanford.edu/~tibs/ElemStatLearn/ for machine learning, so I think I will start there. Granted I have done a lot of statistics recently, so this might get ignored a bit.

Math:

I have never been amazingly gifted mathematically, but I enjoy it and think I should get better at it, so I periodically pick up something and work with it. Reddit has a complex analysis study group I kind of read along with:

http://www.reddit.com/r/math/comments/d5egu/does_anyone_want_to_start_a_complex_analysis_club/

Home remodeling:

I have an ongoing two year basement remodel project I am hoping to finish, along with some other house stuff. Its mostly slow going and dull at times, but I will probably update about it a bit here and there.

Starcraft 2:

Its kind of silly to put a video game on your list of projects you want to accomplish, but it definitely is something I work fairly hard on. I am someone that has to have some kind of competitive outlet, so when I was a kid I played chess, then I did debate in high school, and in college I found competitive video games were the easiest way to get some fairly intense games of skill. At the end of the day I think of it as speed chess with better graphics.

This is about everything I can think of wanting to get done. I am sure I will get about half of it done, if that, but it should be a good time. There are obvious other projects, such as read some fiction and get in a bit better shape (turns out working out is actually kind of fun), but I don’t see me getting too passionate about it, so I doubt I post a ton.

Back to hip replacement statistics!

~Andy