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]

[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]

[Fritzlein]

[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 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).