[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Minimax Incorrect

It is currently Tue Dec 12, 2017 10:29 am Advanced search

Minimax Incorrect

Share and discuss ideas for your entries here.

Re: Minimax Incorrect

Postby thedeadwalrus » Wed Feb 24, 2010 4:10 am

thedeadwalrus
Lieutenant
 
Posts: 11
Joined: Fri Feb 12, 2010 3:10 pm

Re: Minimax Incorrect

Postby jeff.cameron » Fri Feb 26, 2010 8:35 am

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.
jeff.cameron
Contest Organizer
 
Posts: 91
Joined: Sun Jan 31, 2010 4:06 am

Re: Minimax Incorrect

Postby dutchflyboy » Sun Feb 28, 2010 12:35 am

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.
Attachments
MiniMaxError1Real.gif
What really happens
MiniMaxError1Real.gif (7.62 KiB) Viewed 3199 times
MiniMaxError1.gif
What minimax thinks will happen
MiniMaxError1.gif (21.44 KiB) Viewed 3199 times
dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: Minimax Incorrect

Postby analyst74 » Sun Feb 28, 2010 1:35 am

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.
analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm

Re: Minimax Incorrect

Postby antimatroid » Sun Feb 28, 2010 3:15 am

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.
antimatroid
Brigadier-General
 
Posts: 126
Joined: Tue Feb 16, 2010 7:41 am

Re: Minimax Incorrect

Postby barank » Sun Feb 28, 2010 4:21 am

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 :D ( i can also use this as an excuse for grammar mistakes and weird explanation ;) )
barank
Lieutenant
 
Posts: 13
Joined: Thu Feb 25, 2010 2:45 am

Re: Minimax Incorrect

Postby dutchflyboy » Sun Feb 28, 2010 10:16 am

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
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: Minimax Incorrect

Postby dutchflyboy » Sun Feb 28, 2010 10:19 am

dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: Minimax Incorrect

Postby barank » Sun Feb 28, 2010 11:38 am

barank
Lieutenant
 
Posts: 13
Joined: Thu Feb 25, 2010 2:45 am

Re: Minimax Incorrect

Postby timwintle » Sun Feb 28, 2010 11:45 am

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.
timwintle
Cadet
 
Posts: 7
Joined: Tue Feb 09, 2010 5:23 pm

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron