7
$\begingroup$

I have a game I'm building some ai for that has 2 players making simultaneous moves. In this game there is exactly one move where, if they both make it at the same time, the outcome is different than if they'd made it separately (all other moves are pretty independent).

Anyway, I'm trying to find a good algorithm to throw at it. Minimax with alpha-beta pruning seems like it would be a good candidate if the players were making alternating moves, but not for simultaneous ones. I found a paper(pdf) on the topic, but it's a little over my head- I'm having trouble reading the pseduocode.

So, can someone either help clarify that approach, suggest another way to accomplish alpha-beta pruning on such a game, or suggest a better algorithm entirely?

$\endgroup$
9
$\begingroup$

The thing is that with simultaneous moves, the optimal strategy is harder to guess, because you need to compute something that is not always obviously winning.

Have a look at Nash equilibrium and the prisoner's dilemma if you don't know them yet. This is the kind of reasoning that you will need each time you are considering two simultaneous moves, instead of simply choosing a move that goes into a winning configuration in games with non-simultaneous moves. The concept of dominance replaces the concept of winning.

The algorithm in your reference does that when referring to figures 4 and 5 but first try to figure out what those figures are supposed to do before understanding how they do it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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