Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What is the correct approach for using miminax in a game where bots make simultaneous moves ?

share|improve this question
1  
Could you provide more context? –  Sidar Apr 29 '13 at 16:51
add comment

1 Answer

Minimax works fine for simultaneous move games; the only modification required is that instead of enumerating an opponent's counter-moves to each possible move, you build a payoff matrix based on what you and your opponent play at the same time.

Recall that in minimax, at each node you enumerate your (or your opponent's) possible moves, evaluate your opponent's (or your) counter-moves to get the best one corresponding to each of your moves, and then pick the move that maximises your payoff. That is, you may have this:

A's choice | B's choice | payoff
---------------------------------
    A1     |     B1     |   +3
    A2     |     B2     |    0
    A3     |     B3     |   +1

Then the choice is clear; A should pick A1 because it leads to the best payoff (because A expects B to play B1, which leads to A playing ... and B playing ... and so on and so on until it leads to a payoff of +3).

With simultaneous moves, you need to consider both players' moves together, in a payoff matrix:

             | B chooses B1 | B chooses B2 | B chooses B3
----------------------------------------------------------
A chooses A1 |      +3      |      -2      |      +2
A chooses A2 |      -1      |       0      |      +4
A chooses A3 |      -4      |      -3      |      +1

Then the choice is not always so obvious, as you need to formulate an effective strategy to pick the best move. For example, in the above example, the choice is not obvious: A may choose A2 since it maximises the minimum expected payoff (-1, when B1 is played), but knowing that A will play A2, B may play B1 to realise the -1 payoff, but knowing that B will play B1, A may play A1 to get the +3 payoff and so on.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.