[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/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 Fri Sep 22, 2017 6:44 pm Advanced search

Minimax Incorrect

Share and discuss ideas for your entries here.

Minimax Incorrect

Postby thedeadwalrus » Tue Feb 23, 2010 4:19 pm

This is something I've been wanting to implement to see if it makes a difference, but my bot is in java and I just don't have the time or motivation to port it to a language that actually functions. So I'll just barf out my thoughts here in case someone wants to give it a shot. I obviously don't know if other bots are already implementing this or not.

So -- minimax is an algorithm for turn based games. Because these bots make simultaneous moves, minimax is incorrect.

This can make a serious difference, for example, in the following situation of depth 1:

RUNNING MINIMAX WITH BOT 1 MOVING FIRST
Bot 1's choices:
Move A = -1 pts
Move B = -3 pts

Bot 2's choices at depth 1:
Move A:1 = -1 pts
Move A:2 = 1 pts
Move B:1 = 2 pts
Move B:2 = -3 pts

Bot 1 is trying to maximize the score. Bot 1, running minimax from its perspective, assumes that if it plays Move A, Bot 2 will play Move 1 and the result will be a score of -1. If Bot 1 plays Move B, Bot 2 will play move 2 and the result will be a score of -3. Bot 1 wants to maximize the score, so according to minimax he will choose move A and get -1 points.

But what about running minimax from Bot 2's perspective (i.e., assuming Bot 2 moves first)?

RUNNING MINIMAX WITH BOT 2 MOVING FIRST
Bot 2's choices:
Move 1 = 2 pts
Move 2 = 1 pts

Bot 1's choices at depth 1:
Move 1:A = -1 pts
Move 1:B = 2 pts
Move 2:A = 1 pts
Move 2:B = -3 pts

Bot 2 is trying to minimize the score. So Bot 2, running minimax from its perspective, assumes that if it plays Move 1, Bot 1 will play Move B and the result will be a score of 2. If Bot 2 plays Move 2, Bot 1 will play move A and the result will be a score of 1. Bot 1 wants to minimize the score, so according to minimax Bot 2 will choose Move 2.

So Bot 1 plays Move A assuming Bot 2 will play Move 1, and Bot 2 will play Move 2 assuming Bot 1 will play Move A.

Bot 1 playing move A and Bot 2 playing move 2 results in a score of 1 pt.

But if Bot 2 had known that Bot 1 was going to pick Move A, it would have picked Move 1 and gotten -1 pt. The problem is that this is not a turn-based game. It's simultaneous.

The game-theoretic optical strategy would be to calculate the oddments and use a mixed strategy. If you were devious, you could also keep track of what moves your opponent has made so far, determine the likelihood that they are using naive minimax, and, if they are, you KNOW what they are going to pick, so you can make the move with the absolute highest payoff. Of course, this become Alice down the rabbit hole if both bots are doing this, and deception starts to come into play.

Minimax does an OK job, and to compute the oddments and payoff values of positions you cannot do pruning, so minimax can go a lot deeper. When the bots are close I am guessing the game-theoretically correct algorithm would win. Hard to know until you try it though.
thedeadwalrus
Lieutenant
 
Posts: 11
Joined: Fri Feb 12, 2010 3:10 pm

Re: Minimax Incorrect

Postby dhartmei » Tue Feb 23, 2010 6:06 pm

User avatar
dhartmei
Colonel
 
Posts: 65
Joined: Sun Feb 07, 2010 3:58 pm
Location: Basel, Switzerland

Re: Minimax Incorrect

Postby thedeadwalrus » Tue Feb 23, 2010 6:59 pm

The right idea, but the correct solution is not quite so easy as picking the best move. You have to calculate the oddments for a mixed strategy to do it right.

If you did what you suggest, and you simply picked the response that resulted in the highest outcome, that might work against come opponents. But savvy opponents that knew what you were doing would start picking the optimal move to counter the move you were going to pick. Your move would no longer be optimal. You have to have a mixed strategy to do it right.

Here is a simple iterative way to calculate the oddments for a mixed strategy:

http://code.activestate.com/recipes/496825/

If both players have perfect evaluation functions and play the correct oddments, the game is solved.

The interesting thing happens when you model your opponent and realize they are not playing the optimal strategy, but are using a turn-based minimax algorithm or something else sub-optimal. I'm not sure there is enough data in one game to determine what strategy the opponent is using though. It's probably a pretty good guess that most people are using turn-based minimax. Opponent modeling could come more into play for repeated games against the same opponent.
thedeadwalrus
Lieutenant
 
Posts: 11
Joined: Fri Feb 12, 2010 3:10 pm

Re: Minimax Incorrect

Postby dhartmei » Tue Feb 23, 2010 7:09 pm

You don't know who you're playing against in any particular game, there is no pool of statistics to build from ("cumulative history"). You can't store information for subsequent games,
and you wouldn't immediately recognize the same opponent.

If you want to gather the statistics from the first couple of moves you observe the specific opponent perform in one specific game,
how do you decide to move while you are observing? Chances are, if you play suboptimally for the first few steps, you lose just because
of that...
User avatar
dhartmei
Colonel
 
Posts: 65
Joined: Sun Feb 07, 2010 3:58 pm
Location: Basel, Switzerland

Re: Minimax Incorrect

Postby thedeadwalrus » Tue Feb 23, 2010 7:24 pm

Agreed re: the difficulty of opponent modeling. Although if you were calculating (1) what move turn-based minimax would generate and (2) what the simultaneous optimal move would be, all you'd have to do is watch for moves where there would be different plays. If you saw a position that would result in different moves from the two strategies, you would just have to watch which one your opponent played. One observation might not be enough to base your subsequent decisions on, but you could always use Bayes or something to calculate the probabilities and adjust your play accordingly.

I don't think there would be much of a difference except when in close-proximity, and in that case I think that using turn-based minimax might be play losing moves if the other player either (1) is correctly using simultaneous calculations or (2) knows that its opponent is incorrectly using turn-based minimax.

But, since you can't effectively do pruning with mixed strategy calculations, you will only be able to calculate your moves half as deep. Turn-based minimax might therefore end up being stronger than the correct strategy.

I was going to implement this in my bot to experiment with how well mixed strategies performed, but like I said, it's not worth doing it in java, and I don't want to port. I was just throwing this out there to perhaps make things more interesting.
thedeadwalrus
Lieutenant
 
Posts: 11
Joined: Fri Feb 12, 2010 3:10 pm

Re: Minimax Incorrect

Postby tdeluca » Tue Feb 23, 2010 9:39 pm

tdeluca
Cadet
 
Posts: 7
Joined: Sun Feb 07, 2010 5:45 pm

Re: Minimax Incorrect

Postby Savaron » Tue Feb 23, 2010 10:18 pm

edit: actually there is no correct move for both
Savaron
Captain
 
Posts: 22
Joined: Tue Feb 09, 2010 10:32 pm

Re: Minimax Incorrect

Postby thedeadwalrus » Tue Feb 23, 2010 10:27 pm

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

Re: Minimax Incorrect

Postby paul_mcquesten » Wed Feb 24, 2010 1:18 am

paul_mcquesten
Lieutenant
 
Posts: 12
Joined: Tue Feb 16, 2010 5:12 am

Re: Minimax Incorrect

Postby mightybyte » Wed Feb 24, 2010 3:46 am

mightybyte
Cadet
 
Posts: 4
Joined: Sat Feb 06, 2010 2:52 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron