[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/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 Sun Nov 19, 2017 10:26 am Advanced search

Minimax Incorrect

Share and discuss ideas for your entries here.

Re: Minimax Incorrect

Postby dutchflyboy » Sun Feb 28, 2010 12:26 pm

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

Re: Minimax Incorrect

Postby Maxime81 » Sun Feb 28, 2010 3:55 pm

Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Minimax Incorrect

Postby thedeadwalrus » Sun Feb 28, 2010 5:30 pm

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.
thedeadwalrus
Lieutenant
 
Posts: 11
Joined: Fri Feb 12, 2010 3:10 pm

Re: Minimax Incorrect

Postby analyst74 » Sun Feb 28, 2010 9:02 pm

analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm

Re: Minimax Incorrect

Postby Fritzlein » Sun Feb 28, 2010 11:05 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Minimax Incorrect

Postby paul_mcquesten » Fri Mar 05, 2010 7:52 pm

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"
Last edited by paul_mcquesten on Fri Mar 05, 2010 11:30 pm, edited 1 time in total.
paul_mcquesten
Lieutenant
 
Posts: 12
Joined: Tue Feb 16, 2010 5:12 am

Re: Minimax Incorrect

Postby luv2run » Fri Mar 05, 2010 11:07 pm

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.
luv2run
Lieutenant
 
Posts: 11
Joined: Sun Feb 28, 2010 4:57 pm

Re: Minimax Incorrect

Postby dutchflyboy » Mon Mar 08, 2010 8:57 pm

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

Previous

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron