2
\$\begingroup\$

I've got a game tree structure for my AI that I need to trim in order to gain some depth.

It is a single-player game of perfect information. A good analogy would be a single-player game of Magic the gathering with an oponnenet that plays no card but automaticaly deals you some damage per turn.

Since I don't have an opponent I don't need either minimax (I can do a pure MAX) or a/b pruning.

I got an evaluation function I can use on nodes if necessary. I'm trying to plan ahead and find good combo's of cards to play.

I dont want to hard-code these combos.

I'm finding hard to prune any branch at all since even a branch with bad-scoring node can potentially lead to a good combo that will completely change the game (you know, like : play 5 shitty cards and be almost dead but the 6th card will grant you a win).

Any idea on how to approach pruning in a game tree like that?

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

I suppose it's just the usual trade off. You'll have to decide, based on desired effectiveness of the selected strategy and performance in terms of how long your tree search takes, what you want. You have to decide how many moves into the future you want to take into account, and then you prune on the resulting tree as usual.

Your example of playing 5 bad cards and winning with the 6th one just depends on how far the AI digs into the tree. If your AI plans 5 moves or less, you just won't be able to get that combo because the moves before that will be considered bad. If it plans 6 or more moves ahead, it'll arrive at the solution using normal decision and pruning tactics. You'll have to figure out if looking 6 moves into the future takes too long or not (I don't know the branching factor of your tree).

Also, you could use this as difficulty settings. For example, an easy AI would only consider the next move, a hard one considers the next 5 moves, an expert one considers 10 moves and so on.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Thx for the answer. My branching factor is around 20. For now, I can compute at a depth much lower than what I'd need to see "most" of the obvious combos. To give you an idea, I'd need to triple or quadruple my current depth to have a satifying AI. I agree that I need pruning, even if it is a bit agressive sometimes but I really have no idea on what to prune since any branch can lead to something good potentially. Considering AI difficulty, it is not an issue here since it is easy to tweak with changing the max depth searched as you said. \$\endgroup\$
    – mydi
    Nov 3, 2015 at 10:46
  • \$\begingroup\$ Then I suppose the only way to do that would be to write a really, really good heuristic function that can predict to a reasonable degree what might happen. Perhaps it could know which cards are still in play, what the chances of each one appearing are, and then calculate a few different outcomes for the next couple of moves and take a kind of weighted average score for each. If it only works with cards already on the hand, it might be a good approach to not evaluate single moves, but rather look through your hand and see what combos are possible and how many turns each one would need. \$\endgroup\$
    – Christian
    Nov 3, 2015 at 11:11
  • \$\begingroup\$ My game has perfect information. So the AI knows every card in play and every card it will draw, so there is no need for some "guessing" heuristics as you mentionned in your first paragraph. Your idea of testing all cards against each other to find combos is an interesting one but in pratice, it is equivalent to doing a tree of all possibile combination (wich is what I'm currently doing). Combos can requieres card already in play and/or future cards, I dont think it can be predicted w/o a full tree or a least a tree of adecent depth. \$\endgroup\$
    – mydi
    Nov 3, 2015 at 15:35
  • \$\begingroup\$ If you can't run the full tree for performance reasons, I suppose there's no way around somehow "guessing" things to reduce the workload, rather than calculate everything exactly and evaluate all possible moves. This of course results in less than optimal play a certain percentage of time, but I really see no other way. Of course, I'd be happy to be corrected on this. \$\endgroup\$
    – Christian
    Nov 4, 2015 at 13:42
  • \$\begingroup\$ We are on the same page @ chirtian :) I'm trying to figure out of to reduce my workload (the size of my tree) by guessing what moves I can prune without loosing too much accuracy overall. An example of rules I added recently to reduce a bit the number of branches in the tree is : if you have a Healing spell and you are at full life (assuming a cap), dont bother checking it. It works good in 99.99% cases. In some rare cases when another card in play would grant you a bonus for overheal, it would be suboptimal but since it will be rare, I'm fine with it. I'm looking for other examples like that. \$\endgroup\$
    – mydi
    Nov 5, 2015 at 16:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .