Hello everyone,

I am currently working on an Apples to Apples game, that allows you to play online for free, against human opponents. The human opponents part is working pretty well. In previous games I have coded, such as Battleship and Yahtzee, the AI was not very hard. As you can probably tell, my experience in AI is very limited, as I have absolutely know idea how to code this AI.

Apples to Apples is a card game, where everyone starts out with 7 cards. These cards are called [color=#ff0000]red cards, and have nouns/noun phrases on them (ex: [color=#ff0000]Zucchini, [color=#ff0000]William Shakespeare, [color=#ff0000]Swiss Cheese, etc). The other type of card is called a [color=#008000]green card. Green cards are adjectives, such as [color=#008000]Sensitive, [color=#008000]Fancy, [color=#008000]Believable. The job of the players is to pick the best [color=#ff0000]red card associated with the[color=#ff0000] [color=#008000]green card.

Every round, each person takes a turn being a judge. It is the job of the judge to review all of the [color=#ff0000]red cards that the players handed in, and pick the one that best matches the [color=#008000]green card. By best match, the rules aren't very clear on this - usual choices are most humorous or one that makes the most sense (it really depends on the judge.)

An example round would work like this, with four players named Matt, Mark, Luke and John (starting with Matt as judge):

1. All players are dealt enough[color=#ff0000] red cards until they have 7.
   
2. Since it is Matt's turn to be judge, he will flip over a green card, [color=#008000]Cold.
   
3. The other 3 players, Mark/Luke/John must pick the best [color=#ff0000]red card to match[color=#008000] Cold.
   
4. Matt does not know who submitted what card. He must pick from:[color=#ff0000] Antarctica, [color=#ff0000]Corn on the Cob, and[color=#ff0000] Leeches[color=#008000].
   
5. Matt decides that [color=#ff0000]Antarctica is the best match. He does not have to disclose a reason why. Since Mark won the round, he gets to hold onto [color=#008000]Cold as green cards are used for scoring (a players score is determined by how many green cards they have).
   

If anyone had any ideas on how to code the AI, and point me in the right direction, I'd be very grateful. I have yet to find an Apples to Apples game with a computer player. The only solution I can think of is somehow use the human players data (it is played online, we could somehow log what players use) but I'm not exactly sure how this would work.

It would be trivial to setup a MySQL table with two fields, one that stored the Green Card picked, and another that stored the Red Cards the judge chose from, and the computer player could choose from this. This would not work well, because the odds of having this exact (or maybe even a similar) situation is slim, there are 747 Red Cards, and 249 Green Cards.

I thank you all in advance for any help!

Hi Dave,
Thank you for your reply. Excuse my ignorance, but how do you think the suitability scores would work?

You could always do the google-work up-front to build your database of suitability scores.

If you want to go the high concept route, this seems like a prime application for a Recommender System. (http://en.wikipedia.org/wiki/Recommender_system)'

With a recommender system, you don't have to rely on having data for every combination of cards (747 x 249). A possible system might attempt to identify traits of each card and then group them accordingly. For instance, a card about a movie star might have traits such as entertainment, person, movie, funny, etc... Then when matching a category card such as "Hilarious", you can look at all category cards related to "funny" and see which cards people chose, and then use those results to determine which traits best match "funny". This is a simplified explanation, but I recommend researching this!

You can build an 'on-line' recommender algorith that constantly changes with the times. You can also profile your individual players to attempt to tailor your AI choices to them - just like a real life player would do.

For each green adjective card (249 different), store a list of all the red noun cards (747 different) sorted into the most relevant to least relevant order. 747 * 249 * 4 bytes == 744012 bytes < 1 megabyte, which is not much of data. If you need to optimize the data size, you can use an u16 for element storage, halving that size.

Automated offline google table building sounds like a neat idea. If building the table is a problem or the size of the in-memory data is too large still, you could only store a partial table: i.e. for each green adjective card, store only say 30 most relevant cards, stored in order of relevancy, then for the rest of the cards, choose randomly, or assign a binary {relevant, not relevant} or n-stage {very relevant, somewhat relevant, not relevant} score.