DR =? NP-Complete

Andrea got a late Christmas gift from her grandmother. It is a game called 'Herd your horses'. The game is a roll and move game where you play as mustangs and attempt to gather a herd of mares and make it to a safe place called 'Green river valley'. You can take multiple paths to get there, but there are certain choke-points which everyone must pass through. It is seems to have more strategic depth than monopoly, but it is certainly meant for young horse crazy girls as well. It does have the honor of being the first roll and move game that Andrea will play (all other ones we have tried before were way too boring), so if you really want your three year old girl to play board games with you this might be the right one.

We have limited her to 4 games a day since playing it more than that is a bit ridiculous.

I have (over the last few days) greatly improved the AI for dancing robots. My attempts to make the AI better have gotten me to ponder the game greatly. I wonder if it is NP complete to code an AI that will make optimal decisions based on the information that a player would know.

There is certainly the Knapsack problem that picking parts represents (from n available parts pick the one that will maximize the return that you get from your dance moves (do this repeatedly until you are ready to dance or your chassis is full)) as well as a difficult ordering problem (from your n moves, pick and order up to 5 to maximize your score (different ordering can change your score and the amount of parts you have to discard)).


Comments

Post a Comment

Popular posts from this blog

Skye Frontier

Image
I just played a work in progress by Seth Jaffee, so I thought that I would post about it here. The game called Skye Frontier right now. It is an Isle of Skye and The King of Frontier mashup. Since The King of Frontier seems like a Carcassonne/Puerto Rico mashup, this is a second order mashup. Anyway - the game was totally playable, and allowed for strategic decisions to be made. Alison went all out in combining multiple synergistic goals with building a good kingdom. I just went for a degenerate strategy of building the biggest lake possible and then producing and consuming in a cycle. After the game end we summed up our scores using the remaining money tokens, so you can see that I won by 6 points (78-84), so my strategy didn't seem too overpowered, however perhaps it should be nerfed a bit, since it was pretty powerful, and degenerate strategies (in my opinion) should be less powerful than well-thought-out ones. Here is the end state: the reasoning behind my strategy - spelled ou
Read more

More Automatown and getting ready for SaltCon

Image
Alison and I played Automatown with many of the discussed changes last night. We liked some of them, and others we did not. The game ended up ending in 6 rounds, and it took about 80 minutes. The later rounds were longer than the first few rounds. We also were being distracted by kids, so perhaps we could have gone faster. Alison ended up with 7 workers and 9 points while I had 9 workers and 28 points (more about that later). Having fewer types of resources was very good. It made the economy less confusing, and setup and cleanup much faster. The mats worked well, and during the game, we thought of more things to put on them - (the three starting workers can be added here, as well as a reminder of what level is what in terms of dots.) Here is the mat that we played with: We started with 3 scrap, which was not enough given that we were also playing with the rule that made upgrades cost a scrap. In fact, that rule made us strapped for scrap the whole game. We decided that m
Read more

Three more playtests

Image
On Friday I played another game of Skye Frontier with my dad (also Mike), brother in law (Dave), and nephew (Logan). My dad and nephew play games sometimes, but are not super big into the hobby, and my brother in law is moderately a gamer (he buys games and brings them to my game nights, but he doesn't play all of the newest games). Logan started the game (and picked the blue castle), Dave was white, my dad was yellow, and I was red. My dad and I ended up contending over the lakes, while Dave focused on building mountain regions, and Logan built some of everything. I couldn't get a shipping empire set up because boats were hard to come by, and Logan (and Dave) started grabbing cash at an alarming rate, so I instead focused on building up points using scrolls and by closing regions. With a 1 point per sheep scoring tile out there, we all tried to get sheep, and the build for free action was used a lot. I capped off my regions just in the nick of time, and Dave ended the game (wh
Read more