by thedeadwalrus » Tue Feb 23, 2010 4:19 pm
This is something I've been wanting to implement to see if it makes a difference, but my bot is in java and I just don't have the time or motivation to port it to a language that actually functions. So I'll just barf out my thoughts here in case someone wants to give it a shot. I obviously don't know if other bots are already implementing this or not.
So -- minimax is an algorithm for turn based games. Because these bots make simultaneous moves, minimax is incorrect.
This can make a serious difference, for example, in the following situation of depth 1:
RUNNING MINIMAX WITH BOT 1 MOVING FIRST
Bot 1's choices:
Move A = -1 pts
Move B = -3 pts
Bot 2's choices at depth 1:
Move A:1 = -1 pts
Move A:2 = 1 pts
Move B:1 = 2 pts
Move B:2 = -3 pts
Bot 1 is trying to maximize the score. Bot 1, running minimax from its perspective, assumes that if it plays Move A, Bot 2 will play Move 1 and the result will be a score of -1. If Bot 1 plays Move B, Bot 2 will play move 2 and the result will be a score of -3. Bot 1 wants to maximize the score, so according to minimax he will choose move A and get -1 points.
But what about running minimax from Bot 2's perspective (i.e., assuming Bot 2 moves first)?
RUNNING MINIMAX WITH BOT 2 MOVING FIRST
Bot 2's choices:
Move 1 = 2 pts
Move 2 = 1 pts
Bot 1's choices at depth 1:
Move 1:A = -1 pts
Move 1:B = 2 pts
Move 2:A = 1 pts
Move 2:B = -3 pts
Bot 2 is trying to minimize the score. So Bot 2, running minimax from its perspective, assumes that if it plays Move 1, Bot 1 will play Move B and the result will be a score of 2. If Bot 2 plays Move 2, Bot 1 will play move A and the result will be a score of 1. Bot 1 wants to minimize the score, so according to minimax Bot 2 will choose Move 2.
So Bot 1 plays Move A assuming Bot 2 will play Move 1, and Bot 2 will play Move 2 assuming Bot 1 will play Move A.
Bot 1 playing move A and Bot 2 playing move 2 results in a score of 1 pt.
But if Bot 2 had known that Bot 1 was going to pick Move A, it would have picked Move 1 and gotten -1 pt. The problem is that this is not a turn-based game. It's simultaneous.
The game-theoretic optical strategy would be to calculate the oddments and use a mixed strategy. If you were devious, you could also keep track of what moves your opponent has made so far, determine the likelihood that they are using naive minimax, and, if they are, you KNOW what they are going to pick, so you can make the move with the absolute highest payoff. Of course, this become Alice down the rabbit hole if both bots are doing this, and deception starts to come into play.
Minimax does an OK job, and to compute the oddments and payoff values of positions you cannot do pruning, so minimax can go a lot deeper. When the bots are close I am guessing the game-theoretically correct algorithm would win. Hard to know until you try it though.