How to simulate battle between two players?

Question

I've got two players and I want to simulate a game between them. Both have some attributes (power, intelligence...) and different actions. The outcome of some action is based on attribute values and some luck factor.

Algorithm:

• Construct a game tree of all possible moves for both players
  • game tree would probably have limited depth
  • Every level would belong to different player
• Use some heuristics at leaf nodes to find out probability of wining for player who has to make a move
• propagate probabilities up (like minimax algorithm does)
• choose a move with highest probability
• continue at the beginning of this algorithm

So, basically this is minimax algorithm. I've got few question though:

1. How to take luck factor in account?
2. When I make one move, do I have to run whole algorithm again? (building the tree with +1 depth and new root node, calculate new probabilities...)
3. Any other idea for simulating a battle?

Thanks.

Answer 1

While generally your algorithm makes sense there is no way we can guarantee that this algorithm is the best one. For example let's imagine two games:

1. In first game each player has 2 actions: fire with a gun and strike with a sword. In this game each step doesn't affect other steps so building a move tree won't make any sense here. Each player just have to choose the weapon and keep firing/striking and shouting 'with the shield or on it!' till death or win.
2. Second game has also third action - steal opponent's shield. In this case move tree will make more sense since it is pretty clear that if you've decided to steal enemy shield anyway then it will make more sense to steal it before striking with a sword.

So whether you need this move tree or not highly depends on your game rules.

The main option regarding luck factor as I see is whether to include it's influence into move tree or not. It depends on whether luck factor affects every action in the same way. If it is true then luck factor can be omitted while calculating move tree and then applied when you will calculate outcome of chosen action. Otherwise if luck factor affects different actions in different manner (for example even complete loser is able to shot an enemy with a gun but kill with a spoon skill requires good luck) then luck factor should be taken into account while calculating probabilities in move tree.

Whether you need or not to recalculate the entire tree after each node depends on whether you can predict result of chosen action with 100%. For example in chess you can predict that if you decided to move a pawn then that pawn will definitely move where you decided to. This allows you on each step take chosen branch in move tree and calculate one more move for each scenario in it instead of recalculating the full tree from nothing. But this is not applicable if player can decide to shoot with a gun but because of he's unlucky day he will shoot himself in a leg.

Answer 2

You should look into Monte Carlo Tree Search, it sounds as it if will fit in great with your problem.

Rather than using a heuristic, it runs a full game using random players at each branch before expanding the tree. The good thing about this is, that you're actually building a tree of probabilities, AND you do not have to expand the tree to the end or some cutoff with heuristic like MinMax.

MCTS is also the current best method in the game GO, and currently best at playing games with unknown rules. For extra effect, you can use some finite state machine agents instead of random players to make the probability more accurate. And you can also reduce branching factor by using a decider that skips certain branches, using a machine learning derived heuristic. (But that's something you'd do last to increase the speed of the technique)

If you can do MinMax, you can do MCTS without too much trouble :) And MCTS can play far more complex games than MinMax ever will, because of its greatly reduced complexity in comparison. (Good if you intend to expand the rules of the game continously)

Have a look here if you're interested:

http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf

And yes, you have to do this at every move for every player. So both MinMax and MCTS will be slow; all game tree based techniques are slow.

With MinMax you can however preserve some of your tree; move to the branch that is your new state, and remove its parent and the subtrees that are connected to it. Then expand one depth futher in the subtree that remains. But this is speculation; I have never had time to do that before :) (You'll be preserving errors in your probability calculations however)

Good thing about these techniques, is that when you've built them they work. Machine learning techniques runs a lot faster, but requires hours if not days of training prior to the use ;)

Answer 3

What you are asking for is very "vast"...but has been done by many developers.

I would advise that you starting reading a book about Game Design like this one: http://www.amazon.com/Game-Design-Practice-Wordware-Developers/dp/1556229127/ref=cm_cr_pr_product_top

... and also search in www.CodeProject.com and www.codeplex.com for examples of games implementations.

Good luck,