What are the best AI technique to use when a game is based on some luck? I mean, normally I would use Min-Max... but... What if the results is based on a probability? Like for instance, managing the best hand in cribbage if the "common card" might make all the difference? Or, like many board/table game where the action have a "chance of success"/"chance of failing badly" but the odds are calculable?

Remember that depending on a deck of cards is not entirely luck-based. There are distinct probabilities for each card that you don't know about. Therefore, it is a question of imperfect information which puts it right into the wheelhouse of Bayesian networks. Because we know some of the information, we can make inferences about the information we don't know. As we collect more information, we know more about what we don't know. (*sigh*)

On the other hand, games that involve dice have a different problem. The dice rolls are independant of one another. Therefore we have no additional information about what roll will happen NEXT by what came before. On the other hand, we can determine the likelyhood of certain results by layering the probabilities of multiple dice rolls. This is Markov Chains. For example, give a starting spot on a game board, I can give you percentages of where I will end up after one roll of a d6, two rolls, three rolls, etc. Of course, the farther into the future we look (more rolls), the wider spread the possibilities are and, accordingly, the less accurate our prediction will be. We can still account for this however.

Imagine seeding your mini-max tree with probabilities for each branch. That is, rather than affording all the next moves with equal weight, you weight them according the probability that the result will happen. At that point, when you roll up the scores, you are only taking into account the weighted averages of the results for each sub-tree.

You can use a similar approach with the card game, by the way. i.e. "this play is only bad in the extreme unlikelyhood that he has card X."

Thanks a lot! I didn't thought about "weighting" each node with the probability of it happening. It makes perfect sense in my context.

If you want to know. It is called Expectiminimax.

http://en.wikipedia.org/wiki/Expectiminimax

May depend on what role the AI is playing...

If the AI simulation is supposed to work with an assumption of uncertainty
-- lacking exact knowledge of the underlying game rules (the math..) then the real 'AI' would be trying to build a model of how things work (by observation/generalization and possibly experimentation) and then use that model to decide which actions to take.

Given exact models and equations and all factors (including derived probabilities) made plain its not really AI (though it may use tools which AI often uses and it still might be alot of work depending on the games complexities).

With uncertainties involved (the actions of another player for example) it gets ALOT harder.

Quote: Original post by wodinoneeye
Given exact models and equations and all factors (including derived probabilities) made plain its not really AI (though it may use tools which AI often uses and it still might be alot of work depending on the games complexities).

Making programs that play games is no longer "real AI"? Some people define AI as "making machines do things that machines can't do". Once we solve a particular problem in AI (like playing chess), it is automatically defined out of AI. :)

Quote: Original post by JesterX
Thanks a lot! I didn't thought about "weighting" each node with the probability of it happening. It makes perfect sense in my context.

The enemy land speeder swings into view from around a building -- in hot persuit! Oh, crap! Gotta shake him some kind of way. There's a street intersection just up ahead. If I drop a mine a little to the right, then swing right, he's gonna have to take some time to swing around it. Maybe I've bought enough time to turn and bring guns to fire.

Will he automatically swing around it, knowing I'll be able to shoot if he does? Or will he instead choose to burn right through the mine for an early attack opportunity?

The model of this scene playing out in my head, is a temporal tree of possible scenarios. Which one leads to the best result? That might very well change from moment to moment, shifting the probability curve over which choice to make. The set may also change as new actions become possible -- maybe targetting that water tower will produce a short duration flood, impeding progress.

These are the kind of things I admire in the execution of a human player, and the primary reason I like to watch game Replays. Wouldn't it be great to see them done by an AI player as well?

Does this look like story telling? Each one a little play. The more scenes in the player/AI inventory, the more opportunity to execute one. And many might produce choices at some moments, where there is more than one good answer; a wealth of tactics to draw from.