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!

Actually, as long as your card list is finite and unchangable, you could do the lookup table method. Don't assign the matches, however... assign "suitability" scores. That way, the computer can sort through its hand and decide which one is the "best" match given the cards it holds.

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

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

For each "answer" card, pre-assign how much it matches the description of the "question" card. Sure, that's a lot of work up-front to assign those values, but that's pretty much the only way you can do it. The computer would have no knowledge of the abstract relationships that may/could exist between those two so you are going to have to do the work yourself.

The computer player would look at its hand of "answer" cards and, given a "question" card, determine which of its available choices is the best match simply by which of the suitability values is highest. Sure, you can use some randomness so it doesn't play the same thing every time (I recommend a weighted random based on the suitability values), but the idea is still to use the values to pick.

just an out-of-the-box idea (maybe completely impossible):

have the AI google the combinations made and see what combination provides most search results, pick this as best match. Maybe just a way to work around the problem but it could provide funny results.

just an out-of-the-box idea (maybe completely impossible):

have the AI google the combinations made and see what combination provides most search results, pick this as best match. Maybe just a way to work around the problem but it could provide funny results.

Yeah, now you're getting into a very slimmed down Watson territory.

you could also expand the online log idea, and combine that against what IADaveMark is suggesting, and basically allow online players to shape the ai's suitability score against cards.

basically, if i were to do such a method, i'd start with everything at a suitability score of 0, and as online players are judges, u increase the suitability between the red-green card by one whenever a human judge chooses the two pair(or increase by two if the human judge chooses the computer's answer.).

so over time, your ai should become much stronger/intelligent, while starting out, it'd be very...stupid...(but you could bill this as a feature of the game, similar to the 20Q game online.)

this allows you to do less, while players do the work to shape your game's ai.

i also like Jaap's answer, but in the same token, your relying on google to never change it's api, so you might come back one day and find a broken game.

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.