Sunday, December 29, 2013

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