Minimax Incorrect

[dutchflyboy]

@Barank:

Ok, I understand it now. No, the question was because I thought you directly put "walls[x, y] = true" when you modified the map, which would make it harder to roll back (a friend of mine tried that, it caused quite a few headaches). But talking about expensive code, my code made a clone of the map at each iteration, not exactly free either, but that meant I didn't have any bugs related to movement and that the minimax was entirely recursive.

About the ranking, you never know what will happen during the final tournament

@timwintle:

Isn't that what minimax is supposed to do for you? The algorithm returns you the best move you can make against a perfect opponent, which means that if the enemy doesn't do what you thought he'd do, it's a worse move for him, giving you an advantage. If you do another move, you're basically hoping your opponent makes a mistake, which isn't the best thing to do.

[Maxime81]

Isn't that what minimax is supposed to do for you? The algorithm returns you the best move you can make against a perfect opponent, which means that if the enemy doesn't do what you thought he'd do, it's a worse move for him, giving you an advantage. If you do another move, you're basically hoping your opponent makes a mistake, which isn't the best thing to do.

Sometimes minimax leads you to do a poor move because you're supposing your opponent will do a perfect move... So sometimes you don't take enough risks and finish with a draw instead of winning...

[thedeadwalrus]

Good stuff, and I had the "enemy is not a wall" and "only evaluate leaf nodes on my turn" functions from the beginning.

There is still the problem that you cannot do a naive minimax with simultaneous games. I.e., the only truly correct strategy is a random mixed strategy.

I didn't get around to implementing this, but I'd be curious if anyone did.

[analyst74]

I played around with a few things to try to exploit minimax strategies:

I passed back the move I had predicted the other player would make, along with what the worst move they could make was - and what the score for that was.

e.g. if the other player expected I would go North, and so their best move was to go West, I looked at all my other moves, and saw if their worst move (given that different move) would have been to go west. If so (and if making that move was better for me than them going west after I went north) then I switched my move choice. This worked against some players, and broke against others - I ran out of time so disabled it, but I was going to store a hit ratio for my predictions of their moves, so I could decide when it was a good decision and when I was probably wrong.

I finally got the idea of why MInimax is broken. Thanks!
So basically, with following example:

If I go North: -1
if enemy goes North: -1
if enemy goes South: 1
if I go South: 0
if enemy goes North: 2
if enemy goes South: 0

If the enemy is using minimax, he will decide to go South, because that's the safest route, at which point your best move would be to go North, which is not the optimal move calculated by minimax.

However, as you have experienced, going North will risk losing if enemy did not go to the optimal minimax move(South); while going South will guarantee at least a draw. So unless you can reliably determine that the enemy is using minimax and have exactly the same heuristic evaluation as you do, your risk of losing a draw game is quite high.

Edit: on the other hand, those scores given by heuristic evaluation may not be correct (otherwise they wouldn't be heuristic), so going south may not guarantee a draw, and going north may not end up losing.... ahhh, my mind is exploding.

[Fritzlein]

I was really hoping that people would eventually realize that Minimax can be exploited in some situations in Tron. If anyone can figure this out before the deadline, they may do quite well!

We were aware of this from day one, but it was always far down the list of potential improvements. I was actually somewhat gleeful when this thread started, because I thought it would distract at least some of the competition from more important matters. It's a cool thought experiment, and developers are very prone to working on what is most cool rather than on what will have the most immediate benefit.

Minimax is only wrong when I don't have a dominating move, i.e. only when my best move changes depending on the opponent's best move. It certainly can happen that none of the choices dominates, but I'm guessing it usually doesn't. Furthermore, to even detect whether or not a dominating moves exists, one needs an accurate evaluation function to apply to the resulting position. Even in the endgames our evaluations were only approximate, and when the players could still reach each other our evaluations were downright horrible. So with simultaneous-move game theory we could be spending cycles solving the matrix

Code: Select all

10  3 -7
-2  0  4
-1  3  0


when every number in the matrix is wrong!

Yet still furthermore, in the 2x2 examples posted above, supposing that one player recognized the true nature of the position and calculated an optimal mixed strategy, in so doing he would guarantee that the opponent's move didn't matter. Maybe my correct strategy is 2/3 south and 1/3 north. Maybe I'm stupid and play north every time. But since you are not stupid and correctly play 1/3 south and 2/3 north, you are guaranteeing me my optimum payout even though I am dumb. Therefore, in order to exploit my sub-optimal play, you have play sub-optimally yourself by anticipating exactly the way in which I will be suboptimal.

All of this means getting improvements from this line of thought is a monster challenge. Timwintle seemed to be the only one who attempted it, and judging from his preliminary rank it wasn't a must-have feature.

Assuming that tomorrow we are permitted to replay the games between top players from the final round robin, I would be grateful to anyone who posts a position from an actual tournament game where neither player had a dominating move, such that relying on minimax would actually have been an exploitable error. This really is a cool topic, and despite the fact that I didn't expect it to yield the most immediate gains, I would still be delighted to see a game where it was decisive.

[paul_mcquesten]

Suicide enhanced via MiniMax payoff matrix

My entry has only simple strategies but managed to finish 98th. I think that can only be due to my approach to simultaneity.

See http://en.wikipedia.org/wiki/Minimax example payoff matrix.

It seems to me that several people who used alpha-beta minimax or negamax ignored simultaneity, and used the simple approximation of alternating moves. Besides the fundamental problem of unstable strategies with simultaneous moves in minimax, that introduces an asymmetry in the players' evaluation functions which I believe is detrimental.

Let the parity of a board be whether the number of open squares is odd or even. With alternating moves Player One always sees the true parity, and Player Two the opposite. Furthermore, Player Two sees one less open square and Player One counts some square as open that will not be. Both of those things make the evaluation functions incommensurate, thus inaccurate.

Perhaps a larger effect is that Player Two always knows where Player One actually moved, so Player Two could have the option to achieve or avoid a tie in situations where Player One could only hope. In any event, Player Two's evaluation would always be more accurate (when using the same evaluation function) than in the real game.

I actually calculated the entire (heuristic) payoff matrix for simultaneous moves. The matrix can be 4x4 only on the first move, and will be 3x3 less frequently as the game progresses. Simply list the legal moves for both players on the current board, then fill-in the evaluations for each combination.

Thus, I had no alpha-beta cutoffs, but there are no cutoffs when the matrix is unstable. (Note that the number of static evaluations is the same as for alternating minimax with no cutoffs.)

One should analyze the matrix and do cutoff when it is stable, but I do not yet understand the appropriate alpha-beta updates.

My static evaluation was a standard difference of count of cells that each player could reach first. If they became disconnected I tried to stay alive with my minimax, but did not get a real survival strategy implemented. Because I knew my strategy was weak, I gave a boost to drawing. Since I broke into the top 100 this suicidal impulse must have succeeded with some smarter bots. (I hope that suicide was not against the rules.) I think this success was solely due to my slightly more accurate evaluations when the end-game was within my depth horizon.

Edit: "9x9" -> "3x3"

[luv2run]

I actually did pretty well without doing any minimax. I've been working on implementing a minimax scheme of some kind but I realize now that the problems and difficulties deciding may almost outweigh the benefits, as some of you may be hinting in your posts. Simultaneity is not an easy cookie to crunch either.

[dutchflyboy]

Well, the advantage of MiniMax is that, once implemented, everything is very easy. If the robot isn't smart enough, add a few parameters to the evaluation function. You don't need to rethink the whole code. For example, my code used a very simple evaluation function: squares_I_can_reach-squares_he_can_reach-distance_to_enemy, but this was a simple count, no voronoi territory, no chambers. Only when in survival mode, the evaluation only depended on my own squares, as it doesn't matter what the enemy does. And yet, I still got in the top 100 (81st).