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"
Statistics: Posted by paul_mcquesten — Fri Mar 05, 2010 7:52 pm