Minimax Incorrect

[thedeadwalrus]

[jeff.cameron]

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!

Maybe some creative combination of AlphaBeta with this sort of game-theoretically correct algorithm could do very well in practice, and could trick Minimax-based bots that aren't as well-thought-out.

[dutchflyboy]

I don't know if anyone is still interested in the problem, but this is how I solved it:
1. The enemy is NOT a wall
2. Only detect if is leaf node when during maximize (my turn)

Why?
1. This solves the problem where the two players can access the same field in the next turn and play for tie (I had this problem, and I think quite a lot of others had it too). After thinking it through, it became clear that my bot was thinking this was the winning move and didn't understand the enemy could crash into him. For example, player 1 is coming from the right and the other player is coming from the top. Player 1 will test what happens when he goes left. The second player now has two options as there now is a wall in front of him (or so minimax thinks): left or right, both are probably suboptimal. Player 1 will think that this is a move that will give him the necessary edge and play it. Meanwhile, player 2 has had the exact same thought, and tries to play the winning move. In the end both will tie. When change #1 is made, the bot will only tie if he knows the other moves are worse and not whenever possible (If things aren't clear, I've attached a little animation). To detect wether you have this problem, try using your debug command whenever the search hits a position where the two players crashed into each other, mine didn't return anything.

Remark: this had a second advantage: it was much easier to detect crashes. If there is a wall at the position of the player, it crashed.
2nd remark: The move order problem only influenced something when the two players where about to crash.

2. This is only important if change #1 is implemented. The bot will now try out the option of intentionnaly crashing. However, as his move is done before the enemy's, he actually crashes with the wall left behind the enemy. You've probably seen it on the empty map where both start in the center, and one idiot just crashes in his first move. Well, that's the problem. This is prevented by forcing the algorithm to let both sides move.

As far as I know, that solved all the move order problems. Congratulations if you've read all this, I know I've become a bit wordy, but it's quite hard to explain.

[analyst74]

It is in fact still a minimax problem, except that you only evaluate the board after both player have moved instead of after each player has moved, plus a few other exceptions.

[antimatroid]

We had just let the opponent move to where we were in our tree and created that as a terminal lose node. Seems to have alleviated that issue.

[barank]

dutchflyboy - Hmm i think you can avoid that , or maybe simply i got what you said wrong but consider something like this ;

xmap = Get Current Map;
Create first node , add xmap to it ;
Layer 1 - My moves
-Get available moves according to parents map , do all stuff but don't save updated map to node. layer 1 nodes
Layer 2 - His moves
-Get his parents map ( which is still xmap ) , get available moves according to that , Update both this nodes and parent nodes moves on that map & save it to layer 2 nodes. ( now layer 2 nodes has updated map )
Repeat the process.

Well you don't really need to save all map if you don't want to ; you can just save differences , apply & get moves & de-apply (uh , surely there is a word for that but... ) & update differences list etc.

Since layer 1-3-5 doesn't update the map , there will be nodes where opponent and player have same square's (aka tie). Then all you need is a little if clause to stop branching after tie situation.
With something like this ; both player and his opponent will have 3 available moves in the first step of your example (i loved it by the way). And since north & south gives negative voronei territory results ( player is purple right? ) , bot will surely prefer west & tie.

Now I really hope you wont come up & say "i wasn't talking about that , you got me wrong" , which is very probable since i just woke up ( i can also use this as an excuse for grammar mistakes and weird explanation )

[dutchflyboy]

I wasn't talking about that, you got me wrong No, actually what I posted was how I solved the problem, not the statement. The pictures where just to illustrate what I was saying (I must concede that I wasn't very clear). But that doesn't matter, your solution seems quite good. But how did you manage the "undo" function? Do you erase the walls where you have been? If yes, what do you do in case of a crash?

[dutchflyboy]

[barank]

[timwintle]

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.